Decoding PNG Length and Distance Extra Bits
References ▼
IETF
DEFLATE Compressed Data Format Specification version 1.3
[1]17:20[2]34:00[3]42:05
[5]1:14:39[7]1:44:05
Computer Graphics at Stanford University
Bit Twiddling Hacks
[4]1:08:05
libpng.org
PNG (Portable Network Graphics) Specification, Version 1.2
[6]1:34:47
Filter mode:
Topics
Media
art
asm
compression
memory
optimisation
parsing
(null topic)
🖌Blackboard
🗪Chat Comment
🏃In-Game
🖮Programming🟉
📖Research
🗩Speech
🎭
🏟
🔗
Link to: current timestamp
Credits
Host
Casey Muratori
Indexer
Matt Mascarenhas
?
?

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

a
w
s
d
h j k l
←
↑
↓
→

Esc Close menu / unfocus timestamp

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)
0:06Recap and set the stage debugging our PNG reader, with a few words on implementing from a specification
🗩
0:06Recap and set the stage debugging our PNG reader, with a few words on implementing from a specification
🗩
0:06Recap and set the stage debugging our PNG reader, with a few words on implementing from a specification
🗩
2:12Step through ParsePNG() and consider our current situation
🏃
2:12Step through ParsePNG() and consider our current situation
🏃
2:12Step through ParsePNG() and consider our current situation
🏃
6:41A few thoughts on compressor scheme quality in terms of its possibility for erroneous output
🗩
6:41A few thoughts on compressor scheme quality in terms of its possibility for erroneous output
🗩
6:41A few thoughts on compressor scheme quality in terms of its possibility for erroneous output
🗩
8:43Continue to step through ParsePNG()
🏃
8:43Continue to step through ParsePNG()
🏃
8:43Continue to step through ParsePNG()
🏃
10:44Change ParsePNG() to allocate 7 bits for the DictHuffman
10:44Change ParsePNG() to allocate 7 bits for the DictHuffman
10:44Change ParsePNG() to allocate 7 bits for the DictHuffman
11:41Step through ComputeHuffman()
🏃
11:41Step through ComputeHuffman()
🏃
11:41Step through ComputeHuffman()
🏃
14:14vaualbus Q: I think there is a typo in the code you copied from the standard. You have a < instead of <=
🗪
14:14vaualbus Q: I think there is a typo in the code you copied from the standard. You have a < instead of <=
🗪
14:14vaualbus Q: I think there is a typo in the code you copied from the standard. You have a < instead of <=
🗪
15:19Continue to step through ComputeHuffman() where it bit-flips the Huffman codes
🏃
15:19Continue to step through ComputeHuffman() where it bit-flips the Huffman codes
🏃
15:19Continue to step through ComputeHuffman() where it bit-flips the Huffman codes
🏃
17:20Carefully read the DEFLATE spec on the endianness of Huffman codes1
📖
17:20Carefully read the DEFLATE spec on the endianness of Huffman codes1
📖
17:20Carefully read the DEFLATE spec on the endianness of Huffman codes1
📖
19:47Continue to step through ComputeHuffman() where it enters the Huffman codes into the symbol table
🏃
19:47Continue to step through ComputeHuffman() where it enters the Huffman codes into the symbol table
🏃
19:47Continue to step through ComputeHuffman() where it enters the Huffman codes into the symbol table
🏃
23:48LSB vs MSB Huffman
🖌
23:48LSB vs MSB Huffman
🖌
23:48LSB vs MSB Huffman
🖌
29:09Change ComputeHuffman() to put the bit-flipped Huffman code before its entry index, before bit-flipping that whole thing
29:09Change ComputeHuffman() to put the bit-flipped Huffman code before its entry index, before bit-flipping that whole thing
29:09Change ComputeHuffman() to put the bit-flipped Huffman code before its entry index, before bit-flipping that whole thing
30:02Step through ComputeHuffman() to see that it decompresses all our symbols
🏃
30:02Step through ComputeHuffman() to see that it decompresses all our symbols
🏃
30:02Step through ComputeHuffman() to see that it decompresses all our symbols
🏃
32:37Let ParsePNG() read to the end of the file, run it and crash on the second time through the loop
🏃
🖮
32:37Let ParsePNG() read to the end of the file, run it and crash on the second time through the loop
🏃
🖮
32:37Let ParsePNG() read to the end of the file, run it and crash on the second time through the loop
🏃
🖮
34:00Consult the Huffman decode part of the DEFLATE specification2
📖
34:00Consult the Huffman decode part of the DEFLATE specification2
📖
34:00Consult the Huffman decode part of the DEFLATE specification2
📖
35:05Make ParsePNG() copy the data to output, renaming ConsumeBits() to ConsumeSize() and introducing a u16 version of EndianSwap()
35:05Make ParsePNG() copy the data to output, renaming ConsumeBits() to ConsumeSize() and introducing a u16 version of EndianSwap()
35:05Make ParsePNG() copy the data to output, renaming ConsumeBits() to ConsumeSize() and introducing a u16 version of EndianSwap()
39:06Inspect the disassembly for EndianSwap(LEN) to see that it was optimised out
🏃
39:06Inspect the disassembly for EndianSwap(LEN) to see that it was optimised out
🏃
39:06Inspect the disassembly for EndianSwap(LEN) to see that it was optimised out
🏃
39:31Prevent the compiler from optimising out the EndianSwap(LEN)
39:31Prevent the compiler from optimising out the EndianSwap(LEN)
39:31Prevent the compiler from optimising out the EndianSwap(LEN)
40:34Inspect the disassembly for EndianSwap(LEN) to see that it it didn't do the expected byte-swap
🏃
40:34Inspect the disassembly for EndianSwap(LEN) to see that it it didn't do the expected byte-swap
🏃
40:34Inspect the disassembly for EndianSwap(LEN) to see that it it didn't do the expected byte-swap
🏃
41:19Fix the u16 version of EndianSwap()
41:19Fix the u16 version of EndianSwap()
41:19Fix the u16 version of EndianSwap()
41:42Inspect the disassembly for EndianSwap(LEN) to see that it it did a rol
🏃
41:42Inspect the disassembly for EndianSwap(LEN) to see that it it did a rol
🏃
41:42Inspect the disassembly for EndianSwap(LEN) to see that it it did a rol
🏃
42:05Begin to enable ParsePNG() to perform the Huffman decompress using a LengthExtra table of pre-subtracted lengths, in conjunction with the DEFLATE specification3
42:05Begin to enable ParsePNG() to perform the Huffman decompress using a LengthExtra table of pre-subtracted lengths, in conjunction with the DEFLATE specification3
42:05Begin to enable ParsePNG() to perform the Huffman decompress using a LengthExtra table of pre-subtracted lengths, in conjunction with the DEFLATE specification3
1:01:57Bit reversal
🖌
1:01:57Bit reversal
🖌
1:01:57Bit reversal
🖌
1:08:05Research bit reversal4
📖
1:08:05Research bit reversal4
📖
1:08:05Research bit reversal4
📖
1:10:49Introduce ReverseBits() for ComputeHuffman() and ParsePNG() to call
1:10:49Introduce ReverseBits() for ComputeHuffman() and ParsePNG() to call
1:10:49Introduce ReverseBits() for ComputeHuffman() and ParsePNG() to call
1:14:39Create a DistExtra table to enable ParsePNG() to interpret the extra bits5
1:14:39Create a DistExtra table to enable ParsePNG() to interpret the extra bits5
1:14:39Create a DistExtra table to enable ParsePNG() to interpret the extra bits5
1:22:54Enable ParsePNG() to decode the symbols using our lookup tables
1:22:54Enable ParsePNG() to decode the symbols using our lookup tables
1:22:54Enable ParsePNG() to decode the symbols using our lookup tables
1:32:39Step through ParsePNG() to see what it does
🏃
1:32:39Step through ParsePNG() to see what it does
🏃
1:32:39Step through ParsePNG() to see what it does
🏃
1:33:55Fix ParsePNG() to use the PNGDistExtra table when setting the DistTab
1:33:55Fix ParsePNG() to use the PNGDistExtra table when setting the DistTab
1:33:55Fix ParsePNG() to use the PNGDistExtra table when setting the DistTab
1:34:12Continue to step through ParsePNG() to see that it's working
🏃
1:34:12Continue to step through ParsePNG() to see that it's working
🏃
1:34:12Continue to step through ParsePNG() to see that it's working
🏃
1:34:47Consult the PNG spec in preparation for implementing the filter6
1:34:47Consult the PNG spec in preparation for implementing the filter6
1:34:47Consult the PNG spec in preparation for implementing the filter6
1:36:08Let AllocatePixels() allocate space for the filter
1:36:08Let AllocatePixels() allocate space for the filter
1:36:08Let AllocatePixels() allocate space for the filter
1:38:54Hit an assertion in ParsePNG()
🏃
1:38:54Hit an assertion in ParsePNG()
🏃
1:38:54Hit an assertion in ParsePNG()
🏃
1:39:36Q&A
🗩
1:39:36Q&A
🗩
1:39:36Q&A
🗩
1:40:05ratchetfreak Q: LitLen-256 should be LitLen-257
🗪
1:40:05ratchetfreak Q: LitLen-256 should be LitLen-257
🗪
1:40:05ratchetfreak Q: LitLen-256 should be LitLen-257
🗪
1:40:15Fix the LenTabIndex initialisation in ParsePNG() to LitLen - 257
1:40:15Fix the LenTabIndex initialisation in ParsePNG() to LitLen - 257
1:40:15Fix the LenTabIndex initialisation in ParsePNG() to LitLen - 257
1:40:30Step through ParsePNG()
🏃
1:40:30Step through ParsePNG()
🏃
1:40:30Step through ParsePNG()
🏃
1:41:16alexkelbo Q: Once this works, do you think it could be SIMDied?
🗪
1:41:16alexkelbo Q: Once this works, do you think it could be SIMDied?
🗪
1:41:16alexkelbo Q: Once this works, do you think it could be SIMDied?
🗪
1:41:46nothings2 Q: That LitLen bug came from me. It'll also be clearer if you write "LitLen >= 257" instead of "LitLen > 256"
🗪
1:41:46nothings2 Q: That LitLen bug came from me. It'll also be clearer if you write "LitLen >= 257" instead of "LitLen > 256"
🗪
1:41:46nothings2 Q: That LitLen bug came from me. It'll also be clearer if you write "LitLen >= 257" instead of "LitLen > 256"
🗪
1:41:55Change "LitLen > 256" to "LitLen >= 257" in ParsePNG()
1:41:55Change "LitLen > 256" to "LitLen >= 257" in ParsePNG()
1:41:55Change "LitLen > 256" to "LitLen >= 257" in ParsePNG()
1:42:28iantjac 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)
🗪
1:42:28iantjac 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)
🗪
1:42:28iantjac 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)
🗪
1:43:16mmozeiko Q: Should ReverseBits table be u16 and not u32?
🗪
1:43:16mmozeiko Q: Should ReverseBits table be u16 and not u32?
🗪
1:43:16mmozeiko Q: Should ReverseBits table be u16 and not u32?
🗪
1:43:21Reduce the ReverseBits table size from u32 to u16
1:43:21Reduce the ReverseBits table size from u32 to u16
1:43:21Reduce the ReverseBits table size from u32 to u16
1:44:05nothings2 Q: No bit reversal is needed. See Deflate spec 3.1.1 first two bullet points7
🗪
1:44:05nothings2 Q: No bit reversal is needed. See Deflate spec 3.1.1 first two bullet points7
🗪
1:44:05nothings2 Q: No bit reversal is needed. See Deflate spec 3.1.1 first two bullet points7
🗪
1:45:44vaualbus 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 <
🗪
1:45:44vaualbus 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 <
🗪
1:45:44vaualbus 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 <
🗪
1:47:07mtsmox Q: BTYPE==0 should read from CompData I think, instead of At?
🗪
1:47:07mtsmox Q: BTYPE==0 should read from CompData I think, instead of At?
🗪
1:47:07mtsmox Q: BTYPE==0 should read from CompData I think, instead of At?
🗪
1:47:21Fix ParsePNG() to read from CompData rather than At in the BTYPE==0 case
1:47:21Fix ParsePNG() to read from CompData rather than At in the BTYPE==0 case
1:47:21Fix ParsePNG() to read from CompData rather than At in the BTYPE==0 case
1:48:08nothings2 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:08nothings2 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:08nothings2 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:25Prevent ParsePNG() from reversing the extra bits
1:48:25Prevent ParsePNG() from reversing the extra bits
1:48:25Prevent ParsePNG() from reversing the extra bits
1:48:53Step through ParsePNG() to see that we're sort of okay, but not quite right
🏃
1:48:53Step through ParsePNG() to see that we're sort of okay, but not quite right
🏃
1:48:53Step through ParsePNG() to see that we're sort of okay, but not quite right
🏃
1:50:45vaualbus Q: Yes, that loop
🗪
1:50:45vaualbus Q: Yes, that loop
🗪
1:50:45vaualbus Q: Yes, that loop
🗪
1:52:58Stop now with a glimpse into the future
🗩
1:52:58Stop now with a glimpse into the future
🗩
1:52:58Stop now with a glimpse into the future
🗩