0

I am looking for a way to retrieve the minCode, maxCode and valPtr from an arbitrary Huffman table.

For instance, the following is a Huffman DC table generated by JpegSnoop:

Destination ID = 0
  Class = 0 (DC / Lossless Table)
    Codes of length 01 bits (000 total): 
    Codes of length 02 bits (001 total): 00 
    Codes of length 03 bits (005 total): 01 02 03 04 05 
    Codes of length 04 bits (001 total): 06 
    Codes of length 05 bits (001 total): 07 
    Codes of length 06 bits (001 total): 08 
    Codes of length 07 bits (001 total): 09 
    Codes of length 08 bits (001 total): 0A 
    Codes of length 09 bits (001 total): 0B 
    Codes of length 10 bits (000 total): 
    Codes of length 11 bits (000 total): 
    Codes of length 12 bits (000 total): 
    Codes of length 13 bits (000 total): 
    Codes of length 14 bits (000 total): 
    Codes of length 15 bits (000 total): 
    Codes of length 16 bits (000 total): 
    Total number of codes: 012

And the following are its Mincode, MaxCode and valPtr respectively:

{ 0, 0, 2, 14, 30, 62, 126, 254, 510, 0, 0, 0, 0, 0, 0, 0 },//YDC
{ -1, 0, 6, 14, 30, 62, 126, 254, 510, -1, -1, -1, -1, -1, -1, -1 },//YDC
{ 0, 0, 1, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0, 0, 0, 0 },//YDC

Now I'm really confused about how these values were derived.

I checked the itu-t81 file, but it was not very clear.

NBG
  • 30
  • 7

2 Answers2

1

To generate the code bits, you start with all zero bits. Within each code length, increment the code like an integer for each symbol. When stepping up a code length, increment and then add a zero bit to the end.

So for your example code, we have each length, followed by the corresponding codes in binary:

2: 00
3: 010, 011, 100, 101, 110
4: 1110
5: 11110
6: 111110
7: 1111110
8: 11111110
9: 111111110

Converting those to the corresponding integer ranges for each bit length, we have:

2: 0..0
3: 2..6
4: 14..14
5: 30..30
6: 62..62
7: 126..126
8: 254..254
9: 510..510

You can see exactly those ranges in your MinCode and MaxCode vectors.

You also have a list of symbols that correspond to the codes. In this example, that list is simply:

00 01 02 03 04 05 06 07 08 09 0A 0B

(The particular values of the symbols are not relevant to the valPtr vector. Those could be anything.)

The codes are assigned to the symbols from shortest to longest, and within each length, in integer order. The valPtr vector is simply the index of the first symbol in that vector that corresponds to each bit length. To generate the vector, start at zero, and add the number of symbols of each code length to get the starting index for the next code length.

1: 0, 0 symbols
2: 0 + 0 = 0, 1 2-bit symbol
3: 0 + 1 = 1, 5 3-bit symbols
4: 1 + 5 = 6, 1 4-bit symbol
5: 6 + 1 = 7, 1 5-bit symbol
6: 7 + 1 = 8, 1 6-bit symbol
7: 8 + 1 = 9, 1 7-bit symbol
8: 9 + 1 = 10, 1 8-bit symbol
9: 10 + 1 = 11

The valPtr example vector are the numbers after the equal signs above.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • Thank you @mark, I understood you until the "The codes are assigned to the symbols from shortest to longest" part. Could you please elaborate on that part (the last part). – NBG Jun 28 '22 at 16:41
  • A 2-bit code is shorter than a 9-bit code. – Mark Adler Jun 28 '22 at 18:19
  • Alright, in the first part, you incremented the integer form, converted to binary, added a '1' bit then a '0' bit right? – NBG Jun 28 '22 at 18:22
  • Converted? The binary values _are_ integers. Just displayed as binary. There is no "added a '1' bit". You increment the binary integer after each code. When going to the next bit length, you add a zero bit on the end. Which is the same as doubling the integer. – Mark Adler Jun 28 '22 at 18:46
  • Understood, You were just dealing with the binary values from a certain point, I was dealing with its decimal equiv. What I did now is converting the first decimal value to binary, append a zero bit, then add one (in binary). this gave me the correct next value. Thank you so much! – NBG Jun 28 '22 at 19:19
0

Thanks, I have created a code that decodes the tables and returns the desired values. The code may be found on my GitHub Here.

NBG
  • 30
  • 7