Vtyjkyuk

As an exercise for myself, I am writing an Ogg Vorbis decoder. Part of the decoding process involves generating Huffman codes from a series of code lengths that is later used when decoding audio packets.

The thing is, I am familiar with Huffman coding from having written a PNG decoder as well. The difference here is that the Huffman tables in the zlib format rely on the code lengths being sorted, whereas the Vorbis specification does not.

Here is an example given in the Vorbis spec (https://xiph.org/vorbis/doc/Vorbis_I_spec.html, section 3.2.1):

There are 8 entries, each with a code length:

• entry 0: length 2


• entry 1: length 4


• entry 2: length 4


• entry 3: length 4


• entry 4: length 4


• entry 5: length 2


• entry 6: length 3


• entry 7: length 3

Assigning codes in order (lowest possible value of the appropriate length to highest) results in the following:

• entry 0: length 2, code 00


• entry 1: length 4, code 0100


• entry 2: length 4, code 0101


• entry 3: length 4, code 0110


• entry 4: length 4, code 0111


• entry 5: length 2, code 10


• entry 6: length 3, code 110


• entry 7: length 3, code 111

I'm having difficulty seeing how to generate those codes from the given lengths. As can be seen above, not all codes of the same length increase monotonically. All the codes of length 4 do because they follow one after the other, but entry 5 (with code 10, or 2 in decimal) does not monotonically follow entry 0 (with code 00).

How would I go about generating these codes?