title: How to rebuild the dynamic Huffman tree from DEFLATE
body: <p>This question is in regards to section 3.2.7 of <a href="https://www.ietf.org/rfc/rfc1951.txt" rel="nofollow noreferrer">RFC-1951</a>, rebuilding the dynamic Huffman tree. </p>
  
  <p>Each code is defined by a sequence of code lengths, such that all codes of a given bit length have lexicographically consecutive values.</p>
  
  <p>For example, here is a rgb(255,0,0) 50x50 png, where the IDAT is a dynamic Huffman tree from DEFLATE.</p>
  
  <pre><code>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  ..
  </code></pre>
  
  <p><a href="https://github.com/madler/infgen/blob/master/infgen.c" rel="nofollow noreferrer">infgen</a> produces this header:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>...the goal is to understand the bits and processes to rebuild the dynamic tree...</p>
  
  <hr>
  
  <p>The first three bits describe the DEFLATE header.</p>
  
  <pre><code>101 &lt;- last block bit, tree type is dynamic. 
  </code></pre>
  
  <p>The next fourteen bits describe the HLIT, HDIST, and HCLEN. </p>
  
  <pre><code>11101 &lt;- HLIT,  29 + 257 = 286 
  01111 &lt;- HDIST, 15 + 1 = 16
  1110 &lt;- HCLEAN, 14 + 4 = 18
  </code></pre>
  
  <p><em>What do these values describe about the dynamic Huffman tree?</em></p>
  
  <hr>
  
  <p>Next, reading three bits at a time and following the permutation table...the lengths are found to be...</p>
  
  <p><code>Lengths: [4, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2]</code> (line 697 of <a href="https://github.com/madler/zlib/blob/master/contrib/puff/puff.c" rel="nofollow noreferrer">puff.c</a>) </p>
  
  <p><em>Are these lengths used to define the literals?</em></p>