Implementing PNG Reconstruction Filters
References ▼
W3C
Portable Network Graphics (PNG) Specification (Second Edition)
[1]33:27[2]40:27[3]49:05
[4]1:08:10[6]2:04:09
IETF
DEFLATE Compressed Data Format Specification version 1.3
[5]1:58:56
Linux Programmer's Manual
mmap(2)
[7]2:14:49
Filter mode:
Topics
Media
art
compression
data structure
language
memory
parsing
performance
(null topic)
🗹Administrivia
🗪Chat Comment
🎨Drawing
🏃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:00Recap and set the stage for the day continuing with our PNG reader
🗩
0:00Recap and set the stage for the day continuing with our PNG reader
🗩
0:00Recap and set the stage for the day continuing with our PNG reader
🗩
2:44Our understanding of the DEFLATE encoding
🗩
2:44Our understanding of the DEFLATE encoding
🗩
2:44Our understanding of the DEFLATE encoding
🗩
6:00Pull up our piece of structured art
🎨
6:00Pull up our piece of structured art
🎨
6:00Pull up our piece of structured art
🎨
7:43Create a simpler piece of structured art
🎨
7:43Create a simpler piece of structured art
🎨
7:43Create a simpler piece of structured art
🎨
11:33A few thoughts on structured art
🗩
11:33A few thoughts on structured art
🗩
11:33A few thoughts on structured art
🗩
12:33Add a BYTE == 1 case in ParsePNG() by advice of mmozeiko
12:33Add a BYTE == 1 case in ParsePNG() by advice of mmozeiko
12:33Add a BYTE == 1 case in ParsePNG() by advice of mmozeiko
13:51Run our PNG reader on gimp_8x8_compression0.png to see which compression case we hit in ParsePNG()
🏃
13:51Run our PNG reader on gimp_8x8_compression0.png to see which compression case we hit in ParsePNG()
🏃
13:51Run our PNG reader on gimp_8x8_compression0.png to see which compression case we hit in ParsePNG()
🏃
16:19Prevent ParsePNG() from performing integral promotion on the LEN != NLEN comparison
16:19Prevent ParsePNG() from performing integral promotion on the LEN != NLEN comparison
16:19Prevent ParsePNG() from performing integral promotion on the LEN != NLEN comparison
16:43Continue to step through ParsePNG()
🏃
16:43Continue to step through ParsePNG()
🏃
16:43Continue to step through ParsePNG()
🏃
18:32Prevent ParsePNG() from calling EndianSwap() on the LEN
18:32Prevent ParsePNG() from calling EndianSwap() on the LEN
18:32Prevent ParsePNG() from calling EndianSwap() on the LEN
18:53Continue to step through ParsePNG() to completion, and inspect the DecompressedPixels
🏃
18:53Continue to step through ParsePNG() to completion, and inspect the DecompressedPixels
🏃
18:53Continue to step through ParsePNG() to completion, and inspect the DecompressedPixels
🏃
24:57Deduce that the DecompressedPixels contain row transform filter indicators that we have not yet learnt
🏃
24:57Deduce that the DecompressedPixels contain row transform filter indicators that we have not yet learnt
🏃
24:57Deduce that the DecompressedPixels contain row transform filter indicators that we have not yet learnt
🏃
26:56Rename DecompressedPixels to FinalPixels, initialising it before the parsing loop in ParsePNG()
26:56Rename DecompressedPixels to FinalPixels, initialising it before the parsing loop in ParsePNG()
26:56Rename DecompressedPixels to FinalPixels, initialising it before the parsing loop in ParsePNG()
27:59Crash 4coder and step into it to see what's going on
🗹
27:59Crash 4coder and step into it to see what's going on
🗹
27:59Crash 4coder and step into it to see what's going on
🗹
30:10Continue setting up ParsePNG() to apply the filters to the FinalPixels
30:10Continue setting up ParsePNG() to apply the filters to the FinalPixels
30:10Continue setting up ParsePNG() to apply the filters to the FinalPixels
33:274.3 Reference image to PNG image transformation1
📖
33:274.3 Reference image to PNG image transformation1
📖
33:274.3 Reference image to PNG image transformation1
📖
40:279 Filtering (PNG)2
📖
40:279 Filtering (PNG)2
📖
40:279 Filtering (PNG)2
📖
49:05Finish setting up ParsePNG() to apply the filters to our parsed pixels, noting that it seems tailor-made for SIMD3
49:05Finish setting up ParsePNG() to apply the filters to our parsed pixels, noting that it seems tailor-made for SIMD3
49:05Finish setting up ParsePNG() to apply the filters to our parsed pixels, noting that it seems tailor-made for SIMD3
1:08:10Introduce our PNGFilter*() functions4
1:08:10Introduce our PNGFilter*() functions4
1:08:10Introduce our PNGFilter*() functions4
1:22:16Introduce PNGFilterReconstruct() to perform the filtering part of ParsePNG()
1:22:16Introduce PNGFilterReconstruct() to perform the filtering part of ParsePNG()
1:22:16Introduce PNGFilterReconstruct() to perform the filtering part of ParsePNG()
1:26:03Step through PNGFilterReconstruct() to see what we end up with
🏃
1:26:03Step through PNGFilterReconstruct() to see what we end up with
🏃
1:26:03Step through PNGFilterReconstruct() to see what we end up with
🏃
1:29:32Add assertions in the untested Average and Paeth filter cases in PNGFilterReconstruct()
1:29:32Add assertions in the untested Average and Paeth filter cases in PNGFilterReconstruct()
1:29:32Add assertions in the untested Average and Paeth filter cases in PNGFilterReconstruct()
1:30:55Run the program on the compressed gimp_8x8.png to see that it looks right
🏃
1:30:55Run the program on the compressed gimp_8x8.png to see that it looks right
🏃
1:30:55Run the program on the compressed gimp_8x8.png to see that it looks right
🏃
1:39:16Draw a more complicated image
🎨
1:39:16Draw a more complicated image
🎨
1:39:16Draw a more complicated image
🎨
1:41:00Run it on our more complicated, uncompressed image and hit the Paeth filter
🏃
1:41:00Run it on our more complicated, uncompressed image and hit the Paeth filter
🏃
1:41:00Run it on our more complicated, uncompressed image and hit the Paeth filter
🏃
1:42:40Remove that assertion from the Paeth filter case in PNGFilterReconstruct()
1:42:40Remove that assertion from the Paeth filter case in PNGFilterReconstruct()
1:42:40Remove that assertion from the Paeth filter case in PNGFilterReconstruct()
1:42:53Step through PNGFilterReconstruct() into PNGFilter4() (Paeth) to see that it looks reasonable
🏃
1:42:53Step through PNGFilterReconstruct() into PNGFilter4() (Paeth) to see that it looks reasonable
🏃
1:42:53Step through PNGFilterReconstruct() into PNGFilter4() (Paeth) to see that it looks reasonable
🏃
1:46:21Run it on our compressed complex image, to see that it look good too
🏃
1:46:21Run it on our compressed complex image, to see that it look good too
🏃
1:46:21Run it on our compressed complex image, to see that it look good too
🏃
1:46:57Run it on our fully complex gimp_test.png and crash in ParsePNG()
🏃
1:46:57Run it on our fully complex gimp_test.png and crash in ParsePNG()
🏃
1:46:57Run it on our fully complex gimp_test.png and crash in ParsePNG()
🏃
1:48:41Step through ConsumeSize() to realise that the crash occurs even in the first IDAT chunk, so the bug must be in the Huffman decode
1:48:41Step through ConsumeSize() to realise that the crash occurs even in the first IDAT chunk, so the bug must be in the Huffman decode
1:48:41Step through ConsumeSize() to realise that the crash occurs even in the first IDAT chunk, so the bug must be in the Huffman decode
1:53:53Perform coverage checking on every EncodedLen case in ParsePNG() to find that the 16-long (0x10) case is never used in the successfully parsed file
🏃
1:53:53Perform coverage checking on every EncodedLen case in ParsePNG() to find that the 16-long (0x10) case is never used in the successfully parsed file
🏃
1:53:53Perform coverage checking on every EncodedLen case in ParsePNG() to find that the 16-long (0x10) case is never used in the successfully parsed file
🏃
1:58:563.2.7 Compression with dynamic Huffman codes BTYE=105
📖
1:58:563.2.7 Compression with dynamic Huffman codes BTYE=105
📖
1:58:563.2.7 Compression with dynamic Huffman codes BTYE=105
📖
2:01:44Step through the BTYPE=10 case in ParsePNG() to see that the LitLenDistTable seems to be built correctly
🏃
2:01:44Step through the BTYPE=10 case in ParsePNG() to see that the LitLenDistTable seems to be built correctly
🏃
2:01:44Step through the BTYPE=10 case in ParsePNG() to see that the LitLenDistTable seems to be built correctly
🏃
2:02:40Consider our current situation and ways to proceed
🗩
2:02:40Consider our current situation and ways to proceed
🗩
2:02:40Consider our current situation and ways to proceed
🗩
2:03:18Q&A
🗩
2:03:18Q&A
🗩
2:03:18Q&A
🗩
2:03:38ratchetfreak Q: The LEN, NLEN is so the decompressor can resync with a compressor if a block got corrupted (and the compressor emitted an empty block) by looking for the bytes 0000FFFF, mostly handy for byte streams
🗪
2:03:38ratchetfreak Q: The LEN, NLEN is so the decompressor can resync with a compressor if a block got corrupted (and the compressor emitted an empty block) by looking for the bytes 0000FFFF, mostly handy for byte streams
🗪
2:03:38ratchetfreak Q: The LEN, NLEN is so the decompressor can resync with a compressor if a block got corrupted (and the compressor emitted an empty block) by looking for the bytes 0000FFFF, mostly handy for byte streams
🗪
2:04:09rooctag Q: C is up and left6
🗪
2:04:09rooctag Q: C is up and left6
🗪
2:04:09rooctag Q: C is up and left6
🗪
2:05:26Fix PNGFilterReconstruct() to correctly filter Paeth
2:05:26Fix PNGFilterReconstruct() to correctly filter Paeth
2:05:26Fix PNGFilterReconstruct() to correctly filter Paeth
2:06:24geekengale Q: Did I see for(;;) in your code? What's that for / how does it work?
🗪
2:06:24geekengale Q: Did I see for(;;) in your code? What's that for / how does it work?
🗪
2:06:24geekengale Q: Did I see for(;;) in your code? What's that for / how does it work?
🗪
2:07:56john_diresta Q: In the memory window when you were writing the "decoded" pixel (non-compressed 8x8) you were writing to some memory that you have not allocated, accordingly to the ASCII representation, there were some strings about a path in windows
🗪
2:07:56john_diresta Q: In the memory window when you were writing the "decoded" pixel (non-compressed 8x8) you were writing to some memory that you have not allocated, accordingly to the ASCII representation, there were some strings about a path in windows
🗪
2:07:56john_diresta Q: In the memory window when you were writing the "decoded" pixel (non-compressed 8x8) you were writing to some memory that you have not allocated, accordingly to the ASCII representation, there were some strings about a path in windows
🗪
2:09:16Brian Q: In Day 055 when you create the hash table, you added your TODO on getting a better hash. Other than for educational purposes investigating better hashes, what kinds of problems would you start to see if the hash was not good enough? Like would it pop-up when you are profiling or something? Would you get any errors?
🗪
2:09:16Brian Q: In Day 055 when you create the hash table, you added your TODO on getting a better hash. Other than for educational purposes investigating better hashes, what kinds of problems would you start to see if the hash was not good enough? Like would it pop-up when you are profiling or something? Would you get any errors?
🗪
2:09:16Brian Q: In Day 055 when you create the hash table, you added your TODO on getting a better hash. Other than for educational purposes investigating better hashes, what kinds of problems would you start to see if the hash was not good enough? Like would it pop-up when you are profiling or something? Would you get any errors?
🗪
2:11:09sharlock93 Q: There is a VS plugin that lets you see images in memory. It's called Image Watch. Was pretty useful when I did the PNG decoding
🗪
2:11:09sharlock93 Q: There is a VS plugin that lets you see images in memory. It's called Image Watch. Was pretty useful when I did the PNG decoding
🗪
2:11:09sharlock93 Q: There is a VS plugin that lets you see images in memory. It's called Image Watch. Was pretty useful when I did the PNG decoding
🗪
2:11:38john_diresta Q: Oh okay, it's that it looked strange. Usually it's filled with 0xDD of 0xCD if I remember correctly, or maybe it's just for stack memory?
🗪
2:11:38john_diresta Q: Oh okay, it's that it looked strange. Usually it's filled with 0xDD of 0xCD if I remember correctly, or maybe it's just for stack memory?
🗪
2:11:38john_diresta Q: Oh okay, it's that it looked strange. Usually it's filled with 0xDD of 0xCD if I remember correctly, or maybe it's just for stack memory?
🗪
2:13:22uplinkcoder Q: Try a big empty image which compresses very well
🗪
2:13:22uplinkcoder Q: Try a big empty image which compresses very well
🗪
2:13:22uplinkcoder Q: Try a big empty image which compresses very well
🗪
2:14:49quickshift_ Q: So on Linux, would you have to use calloc() instead of VirtualAlloc() or is there an alternative?7
🗪
2:14:49quickshift_ Q: So on Linux, would you have to use calloc() instead of VirtualAlloc() or is there an alternative?7
🗪
2:14:49quickshift_ Q: So on Linux, would you have to use calloc() instead of VirtualAlloc() or is there an alternative?7
🗪
2:15:32sgtrumbi Q: Will you integrate the decoder directly into the game or into the simple_preprocessor?
🗪
2:15:32sgtrumbi Q: Will you integrate the decoder directly into the game or into the simple_preprocessor?
🗪
2:15:32sgtrumbi Q: Will you integrate the decoder directly into the game or into the simple_preprocessor?
🗪
2:16:04Close it up with a glimpse into the future
🗩
2:16:04Close it up with a glimpse into the future
🗩
2:16:04Close it up with a glimpse into the future
🗩