Description of the QPEG Video Codec by Mike Melanson (mike at multimedia.cx) and Konstantin Shishkov (cannonball at bw-team.com) v1.0: December 11, 2004 ======================================================================= NOTE: The information in this document is now maintained in Wiki format at: http://wiki.multimedia.cx/index.php?title=QPEG ======================================================================= Copyright (c) 2004 Mike Melanson & Konstantin Shishkov Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License". Contents -------- * Introduction * Algorithm Basics * Intraframe Decoding * Interframe Decoding * Acknowledgements * References * ChangeLog * GNU Free Documentation License Introduction ------------ QPEG is a video codec developed by Q-Team. Apparently a play on the common multimedia acronyms JPEG and MPEG, QPEG is a palettized 8-bit video codec that uses run length encoding (RLE), interframe differencing and motion compensation to achieve compression. The QPEG codec is known to be identified by the following FOURCCs: 'QPEG', 'Q1.0', and 'Q1.1'. Algorithm Basics ---------------- Decoding a QPEG frame is a bottom-to-top operation. Multi-byte numbers are big-endian. The palette data for the frame is carried in the container format that holds the QPEG data. This is typically an AVI file. An encoded QPEG data frame has the following layout: bytes 0-3: size of encoded frame (including this size field) bytes 4-131: frame data table byte 132: unknown, always seems to be 0xE0 byte 133: frame type The frame data table is a special 128-byte table used in decoding interframes. A frame type of 0x10 indicates that this is an intraframe (keyframe). A 0x00 indicates an interframe that does not use motion compensation. Any other value for frame type indicates an interframe with motion compensation. Intraframe Decoding ------------------- The encoded data for an intraframe begins at byte 134 of the encoded frame (just after byte 133 which contains 0x10 indicating this frame is an intraframe). The algorithm for decoding intraframe data is a basic RLE algorithm that operates as follows: while (there are still bytes remaining in encoded frame) code = next byte in encoded frame if (code is 0xFC) frame decode is complete if (frame is 0xF8..0xFF, but not 0xFC) output very long run to the decoded frame code2 = next byte in encoded frame code3 = next byte in encoded frame run = ((code & 7) << 16) + (code2 << 8) + (code3) + 2 output next byte in encoded frame to decoded frame (run) times if (code is 0xF0..0xF7) output long run to the decoded frame code2 = next byte in encoded frame run = ((code & 0xF) << 8) + (code2) + 2 output next byte in encoded frame to decoded frame (run) times if (code is 0xE0..0xEF) output short run to the decoded frame run = (code & 0x1F) + 2 output next byte in encoded frame to decoded frame (run) times if (code is 0xC0..0xDF) copy very long run from the encoded frame to the decoded frame code2 = next byte in encoded frame code3 = next byte in encoded frame copy = ((code & 0x3F) << 16) + (code2 << 8) + (code3) + 1 copy (copy) bytes from encoded frame to decoded frame if (code is 0x80..0xBF) copy long run from the encoded frame to the decoded frame code2 = next byte in encoded frame copy = ((code & 0x7F) << 8) + (code2 << 8) + 1 copy (copy) bytes from encoded frame to decoded frame if (code is 0x00..0x7F) copy short run from the encoded frame to the decoded frame copy = code + 1 copy (copy) bytes from encoded frame to decoded frame Interframe Decoding ------------------- An interframe has codes to allow RLE, pixel skipping, and motion compensation (if the frame type is non-zero). The interframe decoding algorithm operates as follows: while (there are still bytes remaining in encoded frame) code = next byte in encoded frame if (frame type is non-zero) while (code & 0xF0 == 0xF0) if (frame type is 1) do motion compensation code = next byte in encoded frame if (code is 0xE0) frame decode is complete if (code > 0xE0) note that code can range from 0xE1..0xFF or 0xE1..0xEF depending on whether this interframe uses motion compensation output short run to the decoded frame run = (code & 0x1F) output next byte in encoded frame to decoded frame (run) times if (code is 0xC0..0xDF) copy short run from the encoded frame to the decoded frame copy = (code & 0x1F) copy (copy) bytes from encoded frame to decoded frame if (code is 0x82..0xBF) general skip code skip the next (code & 0x3F) pixels in the output frame (unchanged from the previous frame) if (code is 0x81) special skip code code2 = next byte in encoded frame skip next (code2 + 320) pixels in the output frame (unchanged from the previous frame) if (code is 0x80) special skip code code2 = next byte in encoded frame skip next (code2 + 64) pixels in the output frame (unchanged from the previous frame) if (code is 0x01..0x7F) special fill code next pixel in output frame = frame data table[code] if (code is 0x00) one-pixel skip skip the next pixel in the output frame (unchanged from the previous frame) Regarding "do motion compensation", the QPEG algorithm allows for copying blocks of pixels from the previous frame to the position referenced by the current pixel accounting. Blocks can be variable-sized with dimensions of 4, 8, 16, 24, and 32. The motion vectors have a range of -8..7. For each iteration through "do motion compensation", the block dimensions are specified by the lower 4 bits of the code variable. The 4 bits (range 0..15) comprise an index into this dimension table: 0: 0 x 0 1: 32 x 32 2: 24 x 32 3: 8 x 32 4: 24 x 24 5: 16 x 16 6: 32 x 16 7: 16 x 32 8: 8 x 16 9: 16 x 8 10: 32 x 24 11: 32 x 8 12: 8 x 8 13: 16 x 24 14: 24 x 16 15: 4 x 4 The next byte is fetched from the encoded frame. The upper 4 bits of this byte comprise the horizontal component of the motion vector. The lower 4 bits comprise the vertical component. Both components are treated as signed, 2's-complement integers. The motion block specified by the dimension index and the motion vector is copied into the current decode coordinates in the decoded frame. Note that after this copy takes place, the decoder should not update its output coordinate accounting variables. The algorithm updates these with subsequent skip codes. Acknowledgements ---------------- Thanks to Michael Niedermayer (michaelni at gmx dot at) for helping to sort out the motion compensation algorithm. References ---------- QPEG Video for Windows Decoding DLL, qpeg32.dll Q-Team, creators of QPEG Codec: http://www.q-team.de/ ChangeLog --------- v1.0: December 11, 2004 - initial release GNU Free Documentation License ------------------------------ see http://www.gnu.org/licenses/fdl.html