Handmade Hero»Episode Guide
Decoding PNG Huffman Tables
?
?

Keyboard Navigation

Global Keys

[, < / ], > Jump to previous / next episode
W, K, P / S, J, N Jump to previous / next marker
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 Movement

a
w
s
d
h j k l


Quotes and References Menus

Enter Jump to timecode

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)
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 PNG1 and DEFLATE2 specifications with a few words on compressor creation
📖
2:09Return to the PNG1 and DEFLATE2 specifications with a few words on compressor creation
📖
2:09Return to the PNG1 and DEFLATE2 specifications with a few words on compressor creation
📖
6:17Set up to handle DEFLATE's use of Huffman coding3
📖
6:17Set up to handle DEFLATE's use of Huffman coding3
📖
6:17Set up to handle DEFLATE's use of Huffman coding3
📖
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 length4
📖
23:01Consult the DEFLATE spec for the maximum code length4
📖
23:01Consult the DEFLATE spec for the maximum code length4
📖
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()
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 specification5
59:20Start to enable ComputeHuffman() to build those Huffman codes, in conjunction with the DEFLATE specification5
59:20Start to enable ComputeHuffman() to build those Huffman codes, in conjunction with the DEFLATE specification5
1:03:12Come to understand DEFLATE's use of Huffman coding6 specifications with a few words on compressor creation
📖
1:03:12Come to understand DEFLATE's use of Huffman coding6 specifications with a few words on compressor creation
📖
1:03:12Come to understand DEFLATE's use of Huffman coding6 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: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 specification7
🏃
1:19:58Step through ParsePNG() and inspect our data, in conjunction with the DEFLATE specification7
🏃
1:19:58Step through ParsePNG() and inspect our data, in conjunction with the DEFLATE specification7
🏃
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: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: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: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:34:20Continue to step through ParsePNG(), hit our assertion in HuffmanDecode() and investigate why
🏃
1:35:26Carefully read 3.1.1 Packing into bytes8 to discover that Huffman codes are packed in the opposite direction to everything else
📖
1:35:26Carefully read 3.1.1 Packing into bytes8 to discover that Huffman codes are packed in the opposite direction to everything else
📖
1:35:26Carefully read 3.1.1 Packing into bytes8 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 issue10
🗹
1:59:30Close that issue10
🗹
1:59:30Close that issue10
🗹
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:01:38Fix typo in AllocateHuffman()
2:01:38Fix typo in AllocateHuffman()
2:02:11Read 10.1 Compression method 011
📖
2:02:11Read 10.1 Compression method 011
📖
2:02:11Read 10.1 Compression method 011
📖
2:03:04ratchetfreak Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b11012
🗪
2:03:04ratchetfreak Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b11012
🗪
2:03:04ratchetfreak Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b11012
🗪
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
🗩