Decoding PNG Huffman Tables — Handmade Hero — Episode Guide

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¹ and DEFLATE² specifications with a few words on compressor creation

📖

2:09Return to the PNG¹ and DEFLATE² specifications with a few words on compressor creation

📖

2:09Return to the PNG¹ and DEFLATE² specifications with a few words on compressor creation

📖

6:17Set up to handle DEFLATE's use of Huffman coding³

📖

6:17Set up to handle DEFLATE's use of Huffman coding³

📖

6:17Set up to handle DEFLATE's use of Huffman coding³

📖

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⁴

📖

23:01Consult the DEFLATE spec for the maximum code length⁴

📖

23:01Consult the DEFLATE spec for the maximum code length⁴

📖

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

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

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

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

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

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

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

📖

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

📖

1:03:12Come to understand DEFLATE's use of Huffman coding⁶ 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: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: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⁷

🏃

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

🏃

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

🏃

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: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: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: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: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:34:20Continue to step through ParsePNG(), hit our assertion in HuffmanDecode() and investigate why

🏃

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

📖

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

📖

1:35:26Carefully read 3.1.1 Packing into bytes⁸ 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: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: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: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: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()⁹

1:59:30Close that issue¹⁰

🗹

1:59:30Close that issue¹⁰

🗹

1:59:30Close that issue¹⁰

🗹

2:00:15ratchetfreak Q: Don't the bits when reading the table need to be reversed as well?

🗪

2:00:15ratchetfreak Q: Don't the bits when reading the table need to be reversed as well?

🗪

2:00:15ratchetfreak Q: Don't the bits when reading the table need to be reversed as well?

🗪

2:00:53spensasaurusrex Q: How many hours long is this series now? I've dabbled in the first dozen or so episodes, but trying to catch up on so much content is discouraging

🗪

2:00:53spensasaurusrex Q: How many hours long is this series now? I've dabbled in the first dozen or so episodes, but trying to catch up on so much content is discouraging

🗪

2:00:53spensasaurusrex Q: How many hours long is this series now? I've dabbled in the first dozen or so episodes, but trying to catch up on so much content is discouraging

🗪

2:01:12mmozeiko Q: You said multiple times that PNG spec does not allow fixed Huffman codes, but this is not true: PNG spec explicitly says that both fixed and dynamic Huffmans are allowed (section 10.1)

🗪

2:01:12mmozeiko Q: You said multiple times that PNG spec does not allow fixed Huffman codes, but this is not true: PNG spec explicitly says that both fixed and dynamic Huffmans are allowed (section 10.1)

🗪

2:01:12mmozeiko Q: You said multiple times that PNG spec does not allow fixed Huffman codes, but this is not true: PNG spec explicitly says that both fixed and dynamic Huffmans are allowed (section 10.1)

🗪

2:01:28somebody_took_my_name Q: In AllocateHuffman() you use the sizeof the huffman table not the entries to malloc data

🗪

2:01:28somebody_took_my_name Q: In AllocateHuffman() you use the sizeof the huffman table not the entries to malloc data

🗪

2:01:28somebody_took_my_name Q: In AllocateHuffman() you use the sizeof the huffman table not the entries to malloc data

🗪

2:01:38Fix typo in AllocateHuffman()

2:02:11Read 10.1 Compression method 0¹¹

📖

2:02:11Read 10.1 Compression method 0¹¹

📖

2:02:11Read 10.1 Compression method 0¹¹

📖

2:03:04ratchetfreak Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b110¹²

🗪

2:03:04ratchetfreak Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b110¹²

🗪

2:03:04ratchetfreak Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b110¹²

🗪

2:05:51ratchetfreak Q: Yeah, you are correct

🗪

2:05:51ratchetfreak Q: Yeah, you are correct

🗪

2:05:51ratchetfreak Q: Yeah, you are correct

🗪

2:08:29ratchetfreak Q: Only Huffman codes are bit-reversed when looking at the bit from first byte to last, and most significant bit to least significant

🗪

2:08:29ratchetfreak Q: Only Huffman codes are bit-reversed when looking at the bit from first byte to last, and most significant bit to least significant

🗪

2:08:29ratchetfreak Q: Only Huffman codes are bit-reversed when looking at the bit from first byte to last, and most significant bit to least significant

🗪

2:09:37Close down the stream

🗩

2:09:37Close down the stream

🗩

2:09:37Close down the stream

🗩

Keyboard Navigation

Global Keys

Menu toggling

In-Menu and Index Controls

Quotes and References Menus and Index

Quotes, References and Credits Menus

Filter Menu

Filter and Link Menus

Credits Menu