Decoding PNG Huffman Tables

?

?# Keyboard Navigation

## Global Keys

[, < / ], > Jump to previous / next episode

W, K, P / S, J, N Jump to previous / next timestamp

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)## Menu toggling

q Quotes
r References
f Filter
y Link
c Credits
## In-Menu and Index Controls

## Quotes and References Menus and Index

Enter Jump to timestamp

## Quotes, References and Credits Menus

o Open URL (in new tab)
## Filter Menu

x, Space Toggle category and focus next

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus## Filter and Link Menus

z Toggle filter / linking mode
## Credits Menu

Enter Open URL (in new tab)

W, K, P / S, J, N Jump to previous / next timestamp

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)

a

w

s

s

d

h
j
k
l

←

↑

↓

↓

→

Esc Close menu / unfocus timestamp

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus

⏫

Previous: 'Parsing ZLIB Headers'

⏫

0:00Recap and set the stage for the day decoding Huffman

🗩

0:00Recap and set the stage for the day decoding Huffman

🗩

0:00Recap and set the stage for the day decoding Huffman

🗩

0:48Bring us up to speed with ParsePNG()

📖

0:48Bring us up to speed with ParsePNG()

📖

0:48Bring us up to speed with ParsePNG()

📖

2:09Return to the PNG^{1} and DEFLATE^{2} specifications with a few words on compressor creation

📖

2:09Return to the PNG^{1} and DEFLATE^{2} specifications with a few words on compressor creation

📖

2:09Return to the PNG^{1} and DEFLATE^{2} specifications with a few words on compressor creation

📖

6:17Set up to handle DEFLATE's use of Huffman coding^{3}

📖

6:17Set up to handle DEFLATE's use of Huffman coding^{3}

📖

6:17Set up to handle DEFLATE's use of Huffman coding^{3}

📖

10:24Slightly organise handmade_png.h and let ComputeHuffman() process the entire HCLENSwizzle table

10:24Slightly organise handmade_png.h and let ComputeHuffman() process the entire HCLENSwizzle table

10:24Slightly organise handmade_png.h and let ComputeHuffman() process the entire HCLENSwizzle table

15:37Stupid Huffman Decoder

🖌

15:37Stupid Huffman Decoder

🖌

15:37Stupid Huffman Decoder

🖌

21:09LUT+Shift Algorithm, Patent Pending 2018®™

🖌

21:09LUT+Shift Algorithm, Patent Pending 2018®™

🖌

21:09LUT+Shift Algorithm, Patent Pending 2018®™

🖌

23:01Consult the DEFLATE spec for the maximum code length^{4}

📖

23:01Consult the DEFLATE spec for the maximum code length^{4}

📖

23:01Consult the DEFLATE spec for the maximum code length^{4}

📖

28:10Consider the feasibility of building a 32k lookup table

🗩

28:10Consider the feasibility of building a 32k lookup table

🗩

28:10Consider the feasibility of building a 32k lookup table

🗩

29:46Introduce AllocateHuffman() and png_huffman_entry struct

29:46Introduce AllocateHuffman() and png_huffman_entry struct

29:46Introduce AllocateHuffman() and png_huffman_entry struct

36:40Determine to implement HuffmanDecode()

🗩

36:40Determine to implement HuffmanDecode()

🗩

36:40Determine to implement HuffmanDecode()

🗩

37:56Encoding symbols: "Numerical" vs "Bit"

🖌

37:56Encoding symbols: "Numerical" vs "Bit"

🖌

37:56Encoding symbols: "Numerical" vs "Bit"

🖌

39:22Relieve png_huffman_entry of containing SymbolLength

39:22Relieve png_huffman_entry of containing SymbolLength

39:22Relieve png_huffman_entry of containing SymbolLength

40:08Introduce PeekBits(), the same as ConsumeBits() just without shifting the bits, and DiscardBits()

40:08Introduce PeekBits(), the same as ConsumeBits() just without shifting the bits, and DiscardBits()

46:13Implement HuffmanDecode(), augmenting png_huffman with MaxCodeLengthInBits

46:13Implement HuffmanDecode(), augmenting png_huffman with MaxCodeLengthInBits

46:13Implement HuffmanDecode(), augmenting png_huffman with MaxCodeLengthInBits

49:30Dive into implementing ComputeHuffman()

49:30Dive into implementing ComputeHuffman()

49:30Dive into implementing ComputeHuffman()

53:25Determining symbol code locations

🖌

53:25Determining symbol code locations

🖌

53:25Determining symbol code locations

🖌

55:16Enable ComputeHuffman() to correctly place symbol codes in the table

55:16Enable ComputeHuffman() to correctly place symbol codes in the table

55:16Enable ComputeHuffman() to correctly place symbol codes in the table

59:20Start to enable ComputeHuffman() to build those Huffman codes, in conjunction with the DEFLATE specification^{5}

59:20Start to enable ComputeHuffman() to build those Huffman codes, in conjunction with the DEFLATE specification^{5}

1:03:12Come to understand DEFLATE's use of Huffman coding^{6} specifications with a few words on compressor creation

📖

1:03:12Come to understand DEFLATE's use of Huffman coding^{6} specifications with a few words on compressor creation

📖

📖

1:08:27Enable ComputeHuffman() to find the numerical value of the smallest code for each code length, and assign numerical values to all the codes

1:08:27Enable ComputeHuffman() to find the numerical value of the smallest code for each code length, and assign numerical values to all the codes

1:15:13Consider ourselves done with that part of it

🗩

1:15:13Consider ourselves done with that part of it

🗩

1:15:13Consider ourselves done with that part of it

🗩

1:15:46Make ParsePNG() allocate our Huffman tables

1:15:46Make ParsePNG() allocate our Huffman tables

1:15:46Make ParsePNG() allocate our Huffman tables

1:18:54Determine to go over the LitLenDistTable construction routine and implement the filters

🗩

1:18:54Determine to go over the LitLenDistTable construction routine and implement the filters

🗩

1:18:54Determine to go over the LitLenDistTable construction routine and implement the filters

🗩

1:19:58Step through ParsePNG() and inspect our data, in conjunction with the DEFLATE specification^{7}

🏃

1:19:58Step through ParsePNG() and inspect our data, in conjunction with the DEFLATE specification^{7}

🏃

🏃

1:25:15Fix AllocateHuffman() to set the MaxCodeLengthInBits

1:25:15Fix AllocateHuffman() to set the MaxCodeLengthInBits

1:25:15Fix AllocateHuffman() to set the MaxCodeLengthInBits

1:25:40Continue to step through ComputeHuffman() and consider the use of MaxCodeLengthInBits in the ArbitraryBits computation

🏃

1:25:40Continue to step through ComputeHuffman() and consider the use of MaxCodeLengthInBits in the ArbitraryBits computation

🏃

🏃

1:29:35Change AllocateHuffman() to set the MaxCodeLengthInBits according to the length of that length it was passed in, i.e. 2^Length

1:29:35Change AllocateHuffman() to set the MaxCodeLengthInBits according to the length of that length it was passed in, i.e. 2^Length

1:31:30Run it and hit our assertion in AllocateHuffman()

🏃

1:31:30Run it and hit our assertion in AllocateHuffman()

🏃

1:31:30Run it and hit our assertion in AllocateHuffman()

🏃

1:31:44Revert AllocateHuffman() and instead make ParsePNG() pass 8 to it for the DictHuffman allocation

1:31:44Revert AllocateHuffman() and instead make ParsePNG() pass 8 to it for the DictHuffman allocation

1:32:16Continue to step through ComputeHuffman() and inspect our data

🏃

1:32:16Continue to step through ComputeHuffman() and inspect our data

🏃

1:32:16Continue to step through ComputeHuffman() and inspect our data

🏃

1:33:38Assert in HuffmanDecode() that BitsUsed != 0

1:33:38Assert in HuffmanDecode() that BitsUsed != 0

1:33:38Assert in HuffmanDecode() that BitsUsed != 0

1:34:20Continue to step through ParsePNG(), hit our assertion in HuffmanDecode() and investigate why

🏃

1:34:20Continue to step through ParsePNG(), hit our assertion in HuffmanDecode() and investigate why

🏃

🏃

1:35:26Carefully read 3.1.1 Packing into bytes^{8} to discover that Huffman codes are packed in the opposite direction to everything else

📖

1:35:26Carefully read 3.1.1 Packing into bytes^{8} to discover that Huffman codes are packed in the opposite direction to everything else

📖

📖

1:45:30Make ComputeHuffman() flip the bits of Huffman codes

1:45:30Make ComputeHuffman() flip the bits of Huffman codes

1:45:30Make ComputeHuffman() flip the bits of Huffman codes

1:48:12Step through ComputeHuffman() to watch our bits flip

🏃

1:48:12Step through ComputeHuffman() to watch our bits flip

🏃

1:48:12Step through ComputeHuffman() to watch our bits flip

🏃

1:49:07Fix ComputeHuffman() to flip all our bits correctly

1:49:07Fix ComputeHuffman() to flip all our bits correctly

1:49:07Fix ComputeHuffman() to flip all our bits correctly

1:50:13Step through ComputeHuffman() to see our correctly flipping bits

🏃

1:50:13Step through ComputeHuffman() to see our correctly flipping bits

🏃

1:50:13Step through ComputeHuffman() to see our correctly flipping bits

🏃

1:51:17Consider packing the Huffman codes backwards

🗩

1:51:17Consider packing the Huffman codes backwards

🗩

1:51:17Consider packing the Huffman codes backwards

🗩

1:53:12Step through HuffmanDecode() until we assert

🏃

1:53:12Step through HuffmanDecode() until we assert

🏃

1:53:12Step through HuffmanDecode() until we assert

🏃

1:55:57Make ParsePNG() increment LitLenCount in the LitLenDistTable construction routine

1:55:57Make ParsePNG() increment LitLenCount in the LitLenDistTable construction routine

1:55:57Make ParsePNG() increment LitLenCount in the LitLenDistTable construction routine

1:56:50Run until we crash in HuffmanDecode()

🏃

1:56:50Run until we crash in HuffmanDecode()

🏃

1:56:50Run until we crash in HuffmanDecode()

🏃

1:57:09Temporarily prevent ComputeHuffman() from flipping the Huffman bits

1:57:09Temporarily prevent ComputeHuffman() from flipping the Huffman bits

1:57:09Temporarily prevent ComputeHuffman() from flipping the Huffman bits

1:57:26Run it and crash earlier

🏃

1:57:26Run it and crash earlier

🏃

1:57:26Run it and crash earlier

🏃

1:58:05Q&A

🗩

1:58:05Q&A

🗩

1:58:05Q&A

🗩

1:58:17Fix typo in the LitLenDistTable construction in ParsePNG()^{9}

1:58:17Fix typo in the LitLenDistTable construction in ParsePNG()^{9}

1:58:17Fix typo in the LitLenDistTable construction in ParsePNG()^{9}

1:59:30Close that issue^{10}

🗹

1:59:30Close that issue^{10}

🗹

1:59:30Close that issue^{10}

🗹

2:01:38Fix typo in AllocateHuffman()

2:01:38Fix typo in AllocateHuffman()

2:01:38Fix typo in AllocateHuffman()

2:02:11Read 10.1 Compression method 0^{11}

📖

2:02:11Read 10.1 Compression method 0^{11}

📖

2:02:11Read 10.1 Compression method 0^{11}

📖

2:09:37Close down the stream

🗩

2:09:37Close down the stream

🗩

2:09:37Close down the stream

🗩

⏬

Next: 'Decoding PNG Length and Distance Extra Bits'

⏬