• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1Running deflate-degenerate-huffman-unused.deflate through script/print-bits.go
2and adding commentary:
3
4    offset  xoffset ASCII   hex     binary
5    000000  0x0000  .       0x05    0b_...._.101  Dynamic Huffman block, final
6    000000  0x0000  .       0x04    0b_0000_0...  NumLCodes: 257
7    000001  0x0001  .       0xC0    0b_...0_0000  NumDCodes: 1
8    000001  0x0001  .       0xC0    0b_110._....  NumCLCodeLengths: 18
9    000002  0x0002  !       0x21    0b_...._...1
10
11Decode the H-CL Huffman table (NumCLCodeLengths = 18). Recall the peculiar
12code_order: 16, 17, 18, 0, 8, ..., 2, 14, 1, 15:
13
14    000002  0x0002  !       0x21    0b_0010_000.  CLCodeLengths: 18 x 3 bits
15    000003  0x0003  .       0x01    0b_0000_0001    CLCLs[ 1] is 2
16    000004  0x0004  .       0x00    0b_0000_0000    CLCLs[ 2] is 2
17    000005  0x0005  .       0x00    0b_0000_0000    CLCLs[17] is 2
18    000006  0x0006  .       0x00    0b_0000_0000    CLCLs[18] is 2
19    000007  0x0007  .       0x80    0b_1000_0000
20    000008  0x0008  .       0xA0    0b_.010_0000
21
22The H-CL Huffman table is:
23"00" -> CodeLength=1
24"01" -> CodeLength=2
25"10" -> CodeLength=17 which means a block of ( 3 + 3_extra_bits) zeroes
26"11" -> CodeLength=18 which means a block of (11 + 7_extra_bits) zeroes
27
28Decode the H-L Huffman table (NumLCodes = 257):
29
30    000008  0x0008  .       0xA0    0b_1..._....  "11" is CL=18: 11+7extra
31    000009  0x0009  .       0xB7    0b_...._...1
32    000009  0x0009  .       0xB7    0b_1011_011.  7extra=91: 102 zeroes
33    000010  0x000A  V       0x56    0b_...._..10  "01" is CL= 2 (102='f')
34    000010  0x000A  V       0x56    0b_...._01..  "10" is CL=17:  3+3extra
35    000010  0x000A  V       0x56    0b_.101_....  3extra=5: 8 zeroes
36    000010  0x000A  V       0x56    0b_0..._....  "00" is CL= 1 (111='o')
37    000011  0x000B  .       0xFE    0b_...._...0
38    000011  0x000B  .       0xFE    0b_...._.11.  "11" is CL=18: 11+7extra
39    000011  0x000B  .       0xFE    0b_1111_1...  7extra=127: 138 zeroes
40    000012  0x000C  7       0x37    0b_...._..11
41    000012  0x000C  7       0x37    0b_...._01..  "10" is CL=17:  3+3extra
42    000012  0x000C  7       0x37    0b_.011_....  3extra=3: 6 zeroes
43    000012  0x000C  7       0x37    0b_0..._....  "01" is CL=2 (256=EOB)
44    000013  0x000D  .       0x89    0b_...._...1
45
46The H-L Huffman table is:
47"0"  -> 'o'
48"10" -> 'f'
49"11" -> EOB
50
51Decode the H-D Huffman table (NumDCodes = 1):
52
53    000013  0x000D  .       0x89    0b_...._.00.  "00" is CL= 1 (DCode 0)
54
55The H-D Huffman table is:
56"0"  -> 0
57This table is incomplete: there is no entry starting with a "1" bit. It is
58therefore degenerate, but not used below.
59
60Apply H-L and H-D.
61
62    000013  0x000D  .       0x89    0b_...0_1...  lcode:  102  literal 'f'
63    000013  0x000D  .       0x89    0b_..0._....  lcode:  111  literal 'o'
64    000013  0x000D  .       0x89    0b_.0.._....  lcode:  111  literal 'o'
65    000013  0x000D  .       0x89    0b_1..._....  lcode:  256  end of block
66    000014  0x000E  .       0x01    0b_...._...1
67