Search code examples
huffman-codedeflate

How to rebuild the dynamic Huffman tree from DEFLATE

This question is in regards to section 3.2.7 of RFC-1951, rebuilding the dynamic Huffman tree.

Each code is defined by a sequence of code lengths, such that all codes of a given bit length have lexicographically consecutive values.

For example, here is a rgb(255,0,0) 50x50 png, where the IDAT is a dynamic Huffman tree from DEFLATE.

0000024: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx  CIDATx
000002a: xxxxxxxx 11101101 11001111 00110001 00010001 00000000  ...1..
0000030: 00000000 00001000 00000000 10100001 11101111 01011111  ....._
0000036: 01011010 00110011 10111000 01111010 00001100 00000100  Z3.z..
000003c: 10100000 10101001 11111001 00100000 00010001 00010001  ... ..
0000042: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000048: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000004e: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000054: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000005a: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000060: 00010001 00010001 00010001 00010001 00010001 10010001  ......
0000066: 10001011 00000101 10110000 00110011 01110101 10010110  ...3u.
000006c: 01111001 11000101 00011100 10110001 00000000 00000000  y.....
0000072: 00000000 00000000 01001001 01000101 01001110 01000100  ..

infgen produces this header:

last
dynamic
litlen 0 2
litlen 255 4
litlen 256 4
litlen 274 4
litlen 283 4
litlen 285 1
dist 3 1
dist 15 1

...the goal is to understand the bits and processes to rebuild the dynamic tree...

The first three bits describe the DEFLATE header.

101 <- last block bit, tree type is dynamic.

The next fourteen bits describe the HLIT, HDIST, and HCLEN. 

11101 <- HLIT,  29 + 257 = 286 
01111 <- HDIST, 15 + 1 = 16
1110 <- HCLEAN, 14 + 4 = 18

What do these values describe about the dynamic Huffman tree?

Next, reading three bits at a time and following the permutation table...the lengths are found to be...

Lengths: [4, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2] (line 697 of puff.c)

Are these lengths used to define the literals?

Solution

  • What do these values describe about the dynamic Huffman tree?

    They don't really tell you much about the tree, but rather how many symbols for each type of code are described in the subsequent bits of the dynamic header.

    There are eighteen code length code lengths provided next (three bits each), followed by 286 literal/length codes and then sixteen distance codes, all encoded using the code length code.

    Are these lengths used to define the literals?

    No. The three-bit lengths are for the code length codes. You need to build that code just to read the following literal/length and distance code lengths, which are themselves compressed using that code.

    This is described in section 3.2.7 of RFC 1951:

    "For even greater compactness, the code length sequences themselves are compressed using a Huffman code."