EDIT: I read the original article in the opposite way and described the largest PNG file with single pixel, oops. It's still a good tidbit so here is the original comment.
There is a much easier way. You can put an arbitrary number of empty uncompressed blocks, which are normally used for the sync flush (Z_SYNC_FLUSH in zlib). Such blocks do not affect any other block or zlib checksum (but do affect PNG checksum). For example a DEFLATE stream `7801 (00 0000 ffff)* 01 0100 feff xx yyyy yyyy` is always valid and decompresses into a single byte `xx` where `yyyy` is a big-endian representation of `xx + 1`. Also PNG IDAT chunks have to be implicitly concatenated, so you can technically have an arbitrary large PNG file of single pixel if you really want.
I think you missed the point of trying to make the largest image dimensions within the smallest file size. It looks like you're describing the opposite.
With a bit of math, it should be possible to devise a sequence of zlib flush blocks (and other tricks) that don't affect the PNG checksum, either.
As for the "other tricks", you can get 10 bits of do-nothing padding by starting and immediately ending a fixed-huffman block, and various other lengths by starting and immediately ending dynamic huffman blocks. I use the former in unPNG[1] to pad things out to word boundaries, for alignment.
I'll throw another idea in to the air. How about least bytes per pixel (or most pixels per byte) PNG. Is this stable system or does it go to the infinity?
So now we have 2064 pixels in 67 bytes. 30.8 pixels per byte or 3.39 pixels per bit
It's bounded, because the underlying DEFLATE algorithm has the maximum compression ratio of 1032:1 [1]. You still need at least one literal code and end-of-block code, but the former can be encoded in a separate block so you can indeed use only two bits per each run of 258 bytes.
At one point you will be also bounded by the maximum size of IDAT chunk, which is 2^31 - 1 bytes with a 4-byte-long chunk name included, and after that point you will constantly need 12 bytes of overhead for each additional 2^31 - 5 bytes. And we will eventually hit the maximum permitted dimension of (2^31 - 1) by (2^31 - 1) pixels. Since the long-term overhead (12 bytes) is much smaller than the one-time overhead (>50 bytes), the biggest image will result in the best ratio. Such biggest image needs at least N = (2^31 - 1) * (2^28 + 1) uncompressed bytes of IDAT, as each scanline needs one filter byte and 2^31 - 1 bits pack into 2^28 bytes.
We can now compress them down to ceil(N / 1032) compressed bytes plus small overhead, which should be divided into ceil((ceil(N / 1032) + eps) / (2^31 - 5)) = 260,112 IDAT chunks. Each chunk of 2^31 - 5 bytes contains at most ceil((2^31 - 5) * 1032 / (2^28 + 1)) + 1 = 8256 scanline boundary, which consists of one filter byte and one unused padding bit. Therefore we should have (2^31 - 5) * 1032 * 8 - 8256 * 9 uncompressed bytes (i.e. pixels) per each chunk, giving the upper bound of ~4127.99997308 pixels per byte. The actual value will be very slightly lower than that due to the one-time overhead---aforementioned significant digits did account for this.
IIRC, you could create even smaller PNG files (~50 bytes) that violate the spec but some browsers would render. Probably by omitting the IEND chunk or CRCs. Maybe this is fixed in browsers these days. Or I mixed it up with GIF files.
You can indeed, if you slice off everything after and including the zlib adler32 checksum. In some situations you might need to add some extra (compressed) padding bytes to flush the pixel data you care about through the parser state machine. This works in every browser I tested (as a consequence of their ability to preview partially-downloaded files) but not in many standalone image viewers (since they usually expect whole files).
12 comments
[ 1.4 ms ] story [ 50.1 ms ] threadThere is a much easier way. You can put an arbitrary number of empty uncompressed blocks, which are normally used for the sync flush (Z_SYNC_FLUSH in zlib). Such blocks do not affect any other block or zlib checksum (but do affect PNG checksum). For example a DEFLATE stream `7801 (00 0000 ffff)* 01 0100 feff xx yyyy yyyy` is always valid and decompresses into a single byte `xx` where `yyyy` is a big-endian representation of `xx + 1`. Also PNG IDAT chunks have to be implicitly concatenated, so you can technically have an arbitrary large PNG file of single pixel if you really want.
As for the "other tricks", you can get 10 bits of do-nothing padding by starting and immediately ending a fixed-huffman block, and various other lengths by starting and immediately ending dynamic huffman blocks. I use the former in unPNG[1] to pad things out to word boundaries, for alignment.
[1] https://github.com/davidBuchanan314/unpng
So now we have 2064 pixels in 67 bytes. 30.8 pixels per byte or 3.39 pixels per bit
At one point you will be also bounded by the maximum size of IDAT chunk, which is 2^31 - 1 bytes with a 4-byte-long chunk name included, and after that point you will constantly need 12 bytes of overhead for each additional 2^31 - 5 bytes. And we will eventually hit the maximum permitted dimension of (2^31 - 1) by (2^31 - 1) pixels. Since the long-term overhead (12 bytes) is much smaller than the one-time overhead (>50 bytes), the biggest image will result in the best ratio. Such biggest image needs at least N = (2^31 - 1) * (2^28 + 1) uncompressed bytes of IDAT, as each scanline needs one filter byte and 2^31 - 1 bits pack into 2^28 bytes.
We can now compress them down to ceil(N / 1032) compressed bytes plus small overhead, which should be divided into ceil((ceil(N / 1032) + eps) / (2^31 - 5)) = 260,112 IDAT chunks. Each chunk of 2^31 - 5 bytes contains at most ceil((2^31 - 5) * 1032 / (2^28 + 1)) + 1 = 8256 scanline boundary, which consists of one filter byte and one unused padding bit. Therefore we should have (2^31 - 5) * 1032 * 8 - 8256 * 9 uncompressed bytes (i.e. pixels) per each chunk, giving the upper bound of ~4127.99997308 pixels per byte. The actual value will be very slightly lower than that due to the one-time overhead---aforementioned significant digits did account for this.
[1] https://stackoverflow.com/a/16794960
And they're used in real production systems :)
https://www.bamsoftware.com/hacks/deflate.html