96 lines
7.2 KiB
Plaintext
96 lines
7.2 KiB
Plaintext
[video output=day455 member=cmuratori stream_platform=twitch stream_username=handmade_hero project=code title="Decoding PNG Huffman Tables" vod_platform=youtube id=fuPhHEBTShI annotator=Miblo]
|
|
[0:00][Recap and set the stage for the day decoding Huffman][:compression :speech]
|
|
[0:48][Bring us up to speed with ParsePNG()][:compression :research]
|
|
[2:09][Return to the PNG[ref
|
|
site=W3C
|
|
page="Portable Network Graphics (PNG) Specification (Second Edition)"
|
|
url=https://w3.org/TR/2003/REC-PNG-20031110/] and DEFLATE[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt] specifications with a few words on compressor creation][:compression :research]
|
|
[6:17][Set up to handle DEFLATE's use of Huffman coding[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :research]
|
|
[10:24][Slightly organise handmade_png.h and let ComputeHuffman() process the entire HCLENSwizzle table][:compression]
|
|
[15:37][Stupid Huffman Decoder][:blackboard :compression]
|
|
[21:09][LUT+Shift Algorithm, Patent Pending 2018®™][:blackboard :compression]
|
|
[23:01][Consult the DEFLATE spec for the maximum code length[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :research]
|
|
[28:10][Consider the feasibility of building a 32k lookup table][:compression :memory :speech]
|
|
[29:46][Introduce AllocateHuffman() and png_huffman_entry struct][:compression :memory]
|
|
[36:40][Determine to implement HuffmanDecode()][:compression :speech]
|
|
[37:56][Encoding symbols: "Numerical" vs "Bit"][:blackboard]
|
|
[39:22][Relieve png_huffman_entry of containing SymbolLength][:compression]
|
|
[40:08][Introduce PeekBits(), the same as ConsumeBits() just without shifting the bits, and DiscardBits()][:parsing]
|
|
[46:13][Implement HuffmanDecode(), augmenting png_huffman with MaxCodeLengthInBits][:compression]
|
|
[49:30][Dive into implementing ComputeHuffman()][:compression]
|
|
[53:25][Determining symbol code locations][:blackboard :compression]
|
|
[55:16][Enable ComputeHuffman() to correctly place symbol codes in the table][:compression]
|
|
[59:20][Start to enable ComputeHuffman() to build those Huffman codes, in conjunction with the DEFLATE specification[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt]][:compression]
|
|
[1:03:12][Come to understand DEFLATE's use of Huffman coding[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt] specifications with a few words on compressor creation][:compression :research]
|
|
[1:08:27][Enable ComputeHuffman() to find the numerical value of the smallest code for each code length, and assign numerical values to all the codes][:compression]
|
|
[1:15:13][Consider ourselves done with that part of it][:compression :speech]
|
|
[1:15:46][Make ParsePNG() allocate our Huffman tables][:compression :memory]
|
|
[1:18:54][Determine to go over the LitLenDistTable construction routine and implement the filters][:compression :speech]
|
|
[1:19:58][Step through ParsePNG() and inspect our data, in conjunction with the DEFLATE specification[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :run]
|
|
[1:25:15][Fix AllocateHuffman() to set the MaxCodeLengthInBits][:compression]
|
|
[1:25:40][Continue to step through ComputeHuffman() and consider the use of MaxCodeLengthInBits in the ArbitraryBits computation][:compression :run]
|
|
[1:29:35][Change AllocateHuffman() to set the MaxCodeLengthInBits according to the length of that length it was passed in, i.e. 2^Length][:compression]
|
|
[1:31:30][:Run it and hit our assertion in AllocateHuffman()][:compression]
|
|
[1:31:44][Revert AllocateHuffman() and instead make ParsePNG() pass 8 to it for the DictHuffman allocation][:compression]
|
|
[1:32:16][Continue to step through ComputeHuffman() and inspect our data][:compression :run]
|
|
[1:33:38][Assert in HuffmanDecode() that BitsUsed != 0][:compression]
|
|
[1:34:20][Continue to step through ParsePNG(), hit our assertion in HuffmanDecode() and investigate why][:compression :run]
|
|
[1:35:26][Carefully read 3.1.1 Packing into bytes[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt] to discover that Huffman codes are packed in the opposite direction to everything else][:compression :research]
|
|
[1:45:30][Make ComputeHuffman() flip the bits of Huffman codes][:compression]
|
|
[1:48:12][Step through ComputeHuffman() to watch our bits flip][:compression :run]
|
|
[1:49:07][Fix ComputeHuffman() to flip all our bits correctly][:compression]
|
|
[1:50:13][Step through ComputeHuffman() to see our correctly flipping bits][:compression :run]
|
|
[1:51:17][Consider packing the Huffman codes backwards][:compression :speech]
|
|
[1:53:12][Step through HuffmanDecode() until we assert][:compression :run]
|
|
[1:55:57][Make ParsePNG() increment LitLenCount in the LitLenDistTable construction routine][:compression]
|
|
[1:56:50][:Run until we crash in HuffmanDecode()][:compression]
|
|
[1:57:09][Temporarily prevent ComputeHuffman() from flipping the Huffman bits][:compression]
|
|
[1:57:26][:Run it and crash earlier][:compression]
|
|
[1:58:05][Q&A][:speech]
|
|
[1:58:17][Fix typo in the LitLenDistTable construction in ParsePNG()[ref
|
|
site=GitHub
|
|
page="HandmadeHero / cpp/Issues / Wrong value in LitLenDistTable for value of 17"
|
|
url=https://github.com/HandmadeHero/cpp/issues/74]][:compression]
|
|
[1:59:30][Close that issue[ref
|
|
site=GitHub
|
|
page="HandmadeHero / cpp/Issues / Wrong value in LitLenDistTable for value of 17"
|
|
url=https://github.com/HandmadeHero/cpp/issues/74]][:admin :compression]
|
|
[2:00:15][@ratchetfreak][Q: Don't the bits when reading the table need to be reversed as well?][:compression]
|
|
[2:00:53][@spensasaurusrex][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:12][@mmozeiko][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)][:compression]
|
|
[2:01:28][@somebody_took_my_name][Q: In AllocateHuffman() you use the sizeof the huffman table not the entries to malloc data][:memory]
|
|
[2:01:38][Fix typo in AllocateHuffman()][:memory]
|
|
[2:02:11][Read 10.1 :Compression method 0[ref
|
|
site=W3C
|
|
page="Portable Network Graphics (PNG) Specification (Second Edition)"
|
|
url=https://w3.org/TR/2003/REC-PNG-20031110/]][:compression :research]
|
|
[2:03:04][@ratchetfreak][Q: When reading the 3 bit lengths you'd read, e.g. 0b011, but I believe it should be 0b110[ref
|
|
site=IETF
|
|
page="DEFLATE Compressed Data Format Specification version 1.3"
|
|
url=https://www.ietf.org/rfc/rfc1951.txt]][:compression]
|
|
[2:05:51][@ratchetfreak][Q: Yeah, you are correct][:compression]
|
|
[2:08:29][@ratchetfreak][Q: Only Huffman codes are bit-reversed when looking at the bit from first byte to last, and most significant bit to least significant][:compression]
|
|
[2:09:37][Close down the stream][:speech]
|
|
[/video]
|