The world's smallest PNG

Re:The world's smallest PNG by MrCheeze on Saturday February 03, 2024 @04:00PM (#39244693)

So the one thing this article doesn't explicitly justify is whether the ten-byte zlib string is truly the shortest possible. You could imagine that it might be possible to hand-craft a DEFLATE block which is only three bytes instead of four, and yet still decompresses to at least two bytes (the minimum decompressed size of a PNG scanline).

But by exhaustive search of all DEFLATE blocks that are one to three bytes in length, I can confirm the article is correct. All of them decompress to (at most) one byte of data.

Which isn't a surprising result, but I wasn't actually sure of it before trying it out.

[ Parent | on HN ]

Re:The world's smallest PNG by nayuki on Saturday February 03, 2024 @10:29PM (#39247270)

> this article doesn't explicitly justify is whether the ten-byte zlib string is truly the shortest possible

I know the DEFLATE standard intimately and implemented a decoder and encoder (open source on my website/GitHub).

We know that the smallest image requires 2 bytes - 1 for the row filter and 1 for the pixel(s). For simplicitly, we'll assume the data is (hex) 00 00.

A DEFLATE compressed stream must have at least one block. There are three choices for each block's type - uncompressed, fixed Huffman code, and custom Huffman code. Uncompressed requires 1 byte for {type (2 bits), finality (1 bit), padding (5 bits)} and 4 bytes for the length. So that uses 5 bytes already. Using a fixed Huffman code block lets us encode those 2 bytes as 4 bytes. Using a custom Huffman code requires many, many bytes just to specify the Huffman table. Hence, the OP article's approach is justified.

[ Parent | on HN ]