Search code examples
compressionpngimage-compression

Why is the maximum look ahead buffer for PNG LZSS 258 bytes?


I was watching this video from Reducible about the PNG file format, and he mentioned at 10:29 that the maximum size of the look ahead buffer for PNG LZSS is 258 bytes. I looked it up, and I found many resources(ex. 1, 2) about PNG specific LZSS that mentioned the maximum size of the look ahead buffer of 258 bytes, but none explained why. It would seem to me like a more sensible maximum would be 256, being 2^8, but maybe I'm missing something. Any help understanding why it is 258 would be greatly appreciated.


Solution

  • PNG uses Deflate compression, originally designed as a compression method for PKZip. Deflate is not LZSS — it is LZ77 + Huffman coding. (LZSS doesn't use Huffman coding, and it compares lengths of matches to the text to decide which to emit. Deflate simply emits matches of length three or greater.)

    The maximum length of a match is 258, which is what you are referring to as "look ahead". The only thing we really know about why 258 is that Phil Katz (the PK in PKZip) picked 258. He never provided rationale for any of the Deflate design choices.

    My guess is that he picked 258 since the range of match lengths 3..258 can be represented in eight bits — the match length minus three is 0..255. There could be some advantage to that on the processors of the day, around 1990. But that is only a guess.