QPEG

This page is based on the document 'Description of the QPEG Video Codec' by Mike Melanson and Konstantin Shishkov found at http://multimedia.cx/qpeg-format.txt.

• FourCCs: QPEG, Q1.0, Q1.1
• Company: Q-Team
• Samples: http://samples.mplayerhq.hu/V-codecs/QPEG/

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.

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.