Decoding MPEG-like bitstreams

While developing jPSXdec for the last 4 years, I've run across three different methods of decoding bitstreams.

If you'd like to learn more about what part this plays in MPEG and PlayStation .STR decoding, check out my thorough document on the subject: PlayStation_STR_format.txt

Approach 1: Brute force

This is the most obvious approach. For each code, peek the next n-bits until the bits match something.

Next17Bits = Peek17Bits()
For Each Possible Code
    If Next17Bits starts with code bits
        Skip bit code length
        If END_OF_BLOCK code
            return END_OF_BLOCK
        Else If ESCAPE_CODE
            ParseEscapeCode()
        Else
            return matching code
        End If
    End if
Next

In the worst case, this approach requires 111 conditional checks to identify a bit code. To be honest, I've never actually seen this implemented anywhere besides by me years ago when first learning about bitstream parsing.

Approach 2: Binary tree

I actually ran across this approach implemented in the Serial Experiments Lain PlayStation game. You have a tree of conditionals testing the value of each bit until a match is found.

If ReadNextBit() == '1'
    If ReadNextBit() == '0'
        return END_OF_BLOCK
    Else
        If ReadNextBit() == '0'
            return ('11+0'.ZeroRun, '11+0'.AC)
        Else
            return ('11+1'.ZeroRun, '11+1'.AC)
        End If
    End If
Else
    If ReadNextBit() == '1'
        If ReadNextBit() == '1'
            // '011s'
            ...
        Else
            // '010... and so on
        End If
    Else
        // '00... and so on
    End If
End If

The branching can be optimized a bit for most leaves: once the length of the bit code is clear, the remaining bits can be used as the index in several small lookup tables. The jPSXdec implementation only requires (in the worst case) 12 branches to determine the longest bit codes.

Approach 3: Array lookup

I believe this type of approach is used in ffmpeg and the Q-gears decoder. Thanks to the unspoken tradition of never documenting anything, I was unable to understand what it was doing. It wasn't until I reverse-engineered the .iki bitstream parsing that I finally saw how this approach works.

At least for MPEG-1 (and PSX STR), you can take advantage of its particular set of variable length bit codes. Only the first code ('11s') and the end-of-block code ('10') need special parsing. The rest of the codes fall under one of three groups. The group a code belongs to can be determined by looking at how many initial zeros it has.

• Group one starts with between 1 and 4 zeros (this also includes the escape code 000001).
• Group two starts with between 6 and 8 zeros.
• Group three starts with between 9 and 11 zeros.

All codes in their groups:

    [Special handling]
    01 // end-of-block
    11s
    ---- [Group 1] ----
    0 11s
    0 100s
    0 101s
    0 0101s
    0 0110s
    0 0111s
    0 00100s
    0 00101s
    0 00110s
    0 00111s
    0 000100s
    0 000101s
    0 000110s
    0 000111s
    0 00001 // escape code
    0 0100000s
    0 0100001s
    0 0100010s
    0 0100011s
    0 0100100s
    0 0100101s
    0 0100110s
    0 0100111s
    ---- [Group 2] ----
    000000 1000s
    000000 1001s
    000000 1010s
    000000 1011s
    000000 1100s
    000000 1101s
    000000 1110s
    000000 1111s
    000000 010000s
    000000 010001s
    000000 010010s
    000000 010011s
    000000 010100s
    000000 010101s
    000000 010110s
    000000 010111s
    000000 011000s
    000000 011001s
    000000 011010s
    000000 011011s
    000000 011100s
    000000 011101s
    000000 011110s
    000000 011111s
    000000 0010000s
    000000 0010001s
    000000 0010010s
    000000 0010011s
    000000 0010100s
    000000 0010101s
    000000 0010110s
    000000 0010111s
    000000 0011000s
    000000 0011001s
    000000 0011010s
    000000 0011011s
    000000 0011100s
    000000 0011101s
    000000 0011110s
    000000 0011111s
    ---- [Group 3] ----
    000000000 10000s
    000000000 10001s
    000000000 10010s
    000000000 10011s
    000000000 10100s
    000000000 10101s
    000000000 10110s
    000000000 10111s
    000000000 11000s
    000000000 11001s
    000000000 11010s
    000000000 11011s
    000000000 11100s
    000000000 11101s
    000000000 11110s
    000000000 11111s
    000000000 010000s
    000000000 010001s
    000000000 010010s
    000000000 010011s
    000000000 010100s
    000000000 010101s
    000000000 010110s
    000000000 010111s
    000000000 011000s
    000000000 011001s
    000000000 011010s
    000000000 011011s
    000000000 011100s
    000000000 011101s
    000000000 011110s
    000000000 011111s
    000000000 0010000s
    000000000 0010001s
    000000000 0010010s
    000000000 0010011s
    000000000 0010100s
    000000000 0010101s
    000000000 0010110s
    000000000 0010111s
    000000000 0011000s
    000000000 0011001s
    000000000 0011010s
    000000000 0011011s
    000000000 0011100s
    000000000 0011101s
    000000000 0011110s
    000000000 0011111s

Each group has its own lookup table of 256 entries, and each code will be associated with one or more entries in the lookup table. After stripping off the minimum number of zeros in the group, no entry in the group will have more than 8 bits remaining in the bit code. For codes that have 8 bits remaining, its value identifies the associated table index. For the bit codes that have fewer than 8 bits remaining, you have to walk through every combination of the remaining bits to find all associated indexes.

Example:

Group 1 code: 00110s
Use 0 for sign bit for now: 001100
Strip off first leading 0: 01100
Find all combinations of remaining bits:

    01100+000 = 96 (table index)
    01100+001 = 97
    01100+010 = 98
    01100+011 = 99
    01100+100 = 100
    01100+101 = 101
    01100+110 = 102
    01100+111 = 103

Thus bit code 00110s will be associated with table indexes 96-103.

Now each table entry needs three values: the inverse discreet cosine transform (IDCT) run of zero-value alternating current (AC) coefficients, the non-zero AC coefficient value, and the length of the bitstream bits that should be skipped.

Once all three tables are constructed, the following pseudo code will parse your bitstream.

If ReadNextBit() == '1'
    If ReadNextBit() == '0'
        return END_OF_BLOCK
    Else
        If ReadNextBit() == '0'
            return ('11+0'.ZeroRun, '11+0'.AC)
        Else
            return ('11+1'.ZeroRun, '11+1'.AC)
        End If
    End If
Else
    Next16Bits = Peek16Bits()
    If NumberOfLeadingZeros(Next16Bits) <= 4
        Match = LookupTable1[(Next16Bits >> 8) & 0xff]
    Else If NumberOfLeadingZeros(Next16Bits) <= 8
        Match = LookupTable2[(Next16Bits >> 3) & 0xff]
    Else If NumberOfLeadingZeros(Next16Bits) <= 11
        Match = LookupTable3[Next16Bits & 0xff]
    Else
        // bitstream error
    End If
    If Match == ESCAPE_CODE
        SkipBits(ESCAPE_CODE.BitLength)
        ParseEscapeCode()
    Else
        SkipBits(Match.BitLength)
        return (Match.ZeroRun, Match.AC)
    End If
End If

Of course the implementation details can vary, but this gives the idea. The Approach 3 I implemented for jPSXdec requires about 8 conditionals to identify a bit code in the worst case. I've found it to be about 10%-15% faster than the Approach 2 I've been using.