cinera_handmade.network/cmuratori/hero/code/code456.hmml

[video output=day456 member=cmuratori stream_platform=twitch stream_username=handmade_hero project=code title="Decoding PNG Length and Distance Extra Bits" vod_platform=youtube id=_D_v9DwymgM annotator=Miblo]
[0:06][Recap and set the stage debugging our PNG reader, with a few words on implementing from a specification][:compression :parsing :speech]
[2:12][Step through ParsePNG() and consider our current situation][:compression :parsing :run]
[6:41][A few thoughts on compressor scheme quality in terms of its possibility for erroneous output][:compression :speech]
[8:43][Continue to step through ParsePNG()][:compression :parsing :run]
[10:44][Change ParsePNG() to allocate 7 bits for the DictHuffman][:compression :memory]
[11:41][Step through ComputeHuffman()][:compression :run]
[14:14][@vaualbus][Q: I think there is a typo in the code you copied from the standard. You have a < instead of <=]
[15:19][Continue to step through ComputeHuffman() where it bit-flips the Huffman codes][:compression :run]
[17:20][Carefully read the DEFLATE spec on the endianness of Huffman codes[ref
    site=IETF
    page="DEFLATE Compressed Data Format Specification version 1.3"
    url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :research]
[19:47][Continue to step through ComputeHuffman() where it enters the Huffman codes into the symbol table][:compression :run]
[23:48][LSB vs MSB Huffman][:blackboard :compression :memory]
[29:09][Change ComputeHuffman() to put the bit-flipped Huffman code before its entry index, before bit-flipping that whole thing][:compression :memory]
[30:02][Step through ComputeHuffman() to see that it decompresses all our symbols][:compression :run]
[32:37][Let ParsePNG() read to the end of the file, :run it and crash on the second time through the loop][:compression :programming]
[34:00][Consult the Huffman decode part of the DEFLATE specification[ref
    site=IETF
    page="DEFLATE Compressed Data Format Specification version 1.3"
    url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :research]
[35:05][Make ParsePNG() copy the data to output, renaming ConsumeBits() to ConsumeSize() and introducing a u16 version of EndianSwap()][:compression]
[39:06][Inspect the disassembly for EndianSwap(LEN) to see that it was optimised out][:asm :compression :memory :run]
[39:31][Prevent the compiler from optimising out the EndianSwap(LEN)][:compression :memory]
[40:34][Inspect the disassembly for EndianSwap(LEN) to see that it it didn't do the expected byte-swap][:asm :compression :memory :run]
[41:19][Fix the u16 version of EndianSwap()][:compression :memory]
[41:42][Inspect the disassembly for EndianSwap(LEN) to see that it it did a rol][:asm :compression :memory :run]
[42:05][Begin to enable ParsePNG() to perform the Huffman decompress using a LengthExtra table of pre-subtracted lengths, 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:01:57][Bit reversal][:blackboard :memory]
[1:08:05][:Research bit reversal[ref
    site="Computer Graphics at Stanford University"
    page="Bit Twiddling Hacks"
    url=http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious]][:memory]
[1:10:49][Introduce ReverseBits() for ComputeHuffman() and ParsePNG() to call][:compression :memory]
[1:14:39][Create a DistExtra table to enable ParsePNG() to interpret the extra bits[ref
    site=IETF
    page="DEFLATE Compressed Data Format Specification version 1.3"
    url=https://www.ietf.org/rfc/rfc1951.txt]][:compression]
[1:22:54][Enable ParsePNG() to decode the symbols using our lookup tables][:compression]
[1:32:39][Step through ParsePNG() to see what it does][:compression :parsing :run]
[1:33:55][Fix ParsePNG() to use the PNGDistExtra table when setting the DistTab][:compression]
[1:34:12][Continue to step through ParsePNG() to see that it's working][:compression :parsing :run]
[1:34:47][Consult the PNG spec in preparation for implementing the filter[ref
        site=libpng.org
        page="PNG (Portable Network Graphics) Specification, Version 1.2"
        url=http://www.libpng.org/pub/png/spec/1.2/PNG-Contents.html]]
[1:36:08][Let AllocatePixels() allocate space for the filter][:memory]
[1:38:54][Hit an assertion in ParsePNG()][:compression :run]
[1:39:36][Q&A][:speech]
[1:40:05][@ratchetfreak][Q: LitLen-256 should be LitLen-257][:compression]
[1:40:15][Fix the LenTabIndex initialisation in ParsePNG() to LitLen - 257][:compression]
[1:40:30][Step through ParsePNG()][:compression :run]
[1:41:16][@alexkelbo][Q: Once this works, do you think it could be SIMDied?][:optimisation]
[1:41:46][@nothings2][Q: That LitLen bug came from me. It'll also be clearer if you write "LitLen >= 257" instead of "LitLen > 256"][:compression]
[1:41:55][Change "LitLen > 256" to "LitLen >= 257" in ParsePNG()][:compression]
[1:42:28][@iantjac][Q: When you are making a PNG reader, I assume you want game textures to be in PNG format. For my projects I create uncompressed image data, and then archive all of them with some compressor. Is my approach a bad one? (I ask because you have decided to use PNGs)][:art]
[1:43:16][@mmozeiko][Q: Should ReverseBits table be u16 and not u32?][:compression]
[1:43:21][Reduce the ReverseBits table size from u32 to u16][:compression]
[1:44:05][@nothings2][Q: No bit reversal is needed. See Deflate spec 3.1.1 first two bullet points[ref
    site=IETF
    page="DEFLATE Compressed Data Format Specification version 1.3"
    url=https://www.ietf.org/rfc/rfc1951.txt]][:compression]
[1:45:44][@vaualbus][Q: By the way the <= I was referring to at the begin is in the loop in the Huffman decode function, the one with BitIndex in the spec. That loop has <= whereas you have <][:compression]
[1:47:07][@mtsmox][Q: BTYPE==0 should read from CompData I think, instead of At?][:compression]
[1:47:21][Fix ParsePNG() to read from CompData rather than At in the BTYPE==0 case][:compression]
[1:48:08][@nothings2][Q: "the extra bits, after being unpacked as described in 3.1.1, should be interpreted as a machine integer stored...", I guess is what they meant]
[1:48:25][Prevent ParsePNG() from reversing the extra bits][:compression :memory]
[1:48:53][Step through ParsePNG() to see that we're sort of okay, but not quite right][:compression :run]
[1:50:45][@vaualbus][Q: Yes, that loop]
[1:52:58][Stop now with a glimpse into the future][:speech]
[/video]
Cinera 0.7.0 Update Add output parameter to all of hero/code, hero/intro-to-c and hero/misc, preserving the current URLs while allowing different .hmml filenames, notably for hero/misc which now gets sorted chronologically. Update the cinera__*.css files 2020-05-09 20:59:36 +00:00			`[video output=day456 member=cmuratori stream_platform=twitch stream_username=handmade_hero project=code title="Decoding PNG Length and Distance Extra Bits" vod_platform=youtube id=_D_v9DwymgM annotator=Miblo]`
Annotate hero/code456 2018-06-11 19:03:24 +00:00			`[0:06][Recap and set the stage debugging our PNG reader, with a few words on implementing from a specification][:compression :parsing :speech]`
			`[2:12][Step through ParsePNG() and consider our current situation][:compression :parsing :run]`
			`[6:41][A few thoughts on compressor scheme quality in terms of its possibility for erroneous output][:compression :speech]`
			`[8:43][Continue to step through ParsePNG()][:compression :parsing :run]`
			`[10:44][Change ParsePNG() to allocate 7 bits for the DictHuffman][:compression :memory]`
			`[11:41][Step through ComputeHuffman()][:compression :run]`
			`[14:14][@vaualbus][Q: I think there is a typo in the code you copied from the standard. You have a < instead of <=]`
			`[15:19][Continue to step through ComputeHuffman() where it bit-flips the Huffman codes][:compression :run]`
			`[17:20][Carefully read the DEFLATE spec on the endianness of Huffman codes[ref`
			`site=IETF`
			`page="DEFLATE Compressed Data Format Specification version 1.3"`
			`url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :research]`
			`[19:47][Continue to step through ComputeHuffman() where it enters the Huffman codes into the symbol table][:compression :run]`
			`[23:48][LSB vs MSB Huffman][:blackboard :compression :memory]`
			`[29:09][Change ComputeHuffman() to put the bit-flipped Huffman code before its entry index, before bit-flipping that whole thing][:compression :memory]`
			`[30:02][Step through ComputeHuffman() to see that it decompresses all our symbols][:compression :run]`
			`[32:37][Let ParsePNG() read to the end of the file, :run it and crash on the second time through the loop][:compression :programming]`
			`[34:00][Consult the Huffman decode part of the DEFLATE specification[ref`
			`site=IETF`
			`page="DEFLATE Compressed Data Format Specification version 1.3"`
			`url=https://www.ietf.org/rfc/rfc1951.txt]][:compression :research]`
			`[35:05][Make ParsePNG() copy the data to output, renaming ConsumeBits() to ConsumeSize() and introducing a u16 version of EndianSwap()][:compression]`
			`[39:06][Inspect the disassembly for EndianSwap(LEN) to see that it was optimised out][:asm :compression :memory :run]`
			`[39:31][Prevent the compiler from optimising out the EndianSwap(LEN)][:compression :memory]`
			`[40:34][Inspect the disassembly for EndianSwap(LEN) to see that it it didn't do the expected byte-swap][:asm :compression :memory :run]`
			`[41:19][Fix the u16 version of EndianSwap()][:compression :memory]`
			`[41:42][Inspect the disassembly for EndianSwap(LEN) to see that it it did a rol][:asm :compression :memory :run]`
			`[42:05][Begin to enable ParsePNG() to perform the Huffman decompress using a LengthExtra table of pre-subtracted lengths, 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:01:57][Bit reversal][:blackboard :memory]`
			`[1:08:05][:Research bit reversal[ref`
			`site="Computer Graphics at Stanford University"`
			`page="Bit Twiddling Hacks"`
			`url=http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious]][:memory]`
			`[1:10:49][Introduce ReverseBits() for ComputeHuffman() and ParsePNG() to call][:compression :memory]`
			`[1:14:39][Create a DistExtra table to enable ParsePNG() to interpret the extra bits[ref`
			`site=IETF`
			`page="DEFLATE Compressed Data Format Specification version 1.3"`
			`url=https://www.ietf.org/rfc/rfc1951.txt]][:compression]`
			`[1:22:54][Enable ParsePNG() to decode the symbols using our lookup tables][:compression]`
			`[1:32:39][Step through ParsePNG() to see what it does][:compression :parsing :run]`
			`[1:33:55][Fix ParsePNG() to use the PNGDistExtra table when setting the DistTab][:compression]`
			`[1:34:12][Continue to step through ParsePNG() to see that it's working][:compression :parsing :run]`
			`[1:34:47][Consult the PNG spec in preparation for implementing the filter[ref`
			`site=libpng.org`
			`page="PNG (Portable Network Graphics) Specification, Version 1.2"`
			`url=http://www.libpng.org/pub/png/spec/1.2/PNG-Contents.html]]`
			`[1:36:08][Let AllocatePixels() allocate space for the filter][:memory]`
			`[1:38:54][Hit an assertion in ParsePNG()][:compression :run]`
			`[1:39:36][Q&A][:speech]`
			`[1:40:05][@ratchetfreak][Q: LitLen-256 should be LitLen-257][:compression]`
			`[1:40:15][Fix the LenTabIndex initialisation in ParsePNG() to LitLen - 257][:compression]`
			`[1:40:30][Step through ParsePNG()][:compression :run]`
			`[1:41:16][@alexkelbo][Q: Once this works, do you think it could be SIMDied?][:optimisation]`
			`[1:41:46][@nothings2][Q: That LitLen bug came from me. It'll also be clearer if you write "LitLen >= 257" instead of "LitLen > 256"][:compression]`
			`[1:41:55][Change "LitLen > 256" to "LitLen >= 257" in ParsePNG()][:compression]`
			`[1:42:28][@iantjac][Q: When you are making a PNG reader, I assume you want game textures to be in PNG format. For my projects I create uncompressed image data, and then archive all of them with some compressor. Is my approach a bad one? (I ask because you have decided to use PNGs)][:art]`
			`[1:43:16][@mmozeiko][Q: Should ReverseBits table be u16 and not u32?][:compression]`
			`[1:43:21][Reduce the ReverseBits table size from u32 to u16][:compression]`
			`[1:44:05][@nothings2][Q: No bit reversal is needed. See Deflate spec 3.1.1 first two bullet points[ref`
			`site=IETF`
			`page="DEFLATE Compressed Data Format Specification version 1.3"`
			`url=https://www.ietf.org/rfc/rfc1951.txt]][:compression]`
			`[1:45:44][@vaualbus][Q: By the way the <= I was referring to at the begin is in the loop in the Huffman decode function, the one with BitIndex in the spec. That loop has <= whereas you have <][:compression]`
			`[1:47:07][@mtsmox][Q: BTYPE==0 should read from CompData I think, instead of At?][:compression]`
			`[1:47:21][Fix ParsePNG() to read from CompData rather than At in the BTYPE==0 case][:compression]`
			`[1:48:08][@nothings2][Q: "the extra bits, after being unpacked as described in 3.1.1, should be interpreted as a machine integer stored...", I guess is what they meant]`
			`[1:48:25][Prevent ParsePNG() from reversing the extra bits][:compression :memory]`
			`[1:48:53][Step through ParsePNG() to see that we're sort of okay, but not quite right][:compression :run]`
			`[1:50:45][@vaualbus][Q: Yes, that loop]`
			`[1:52:58][Stop now with a glimpse into the future][:speech]`
			`[/video]`