Understanding Deflate

Re:Understanding Deflate by Dylan16807 on Wednesday September 17, 2025 @09:17PM (#45283719)

> That said, even in this simple case, decoding by hand was a pain.

Well doing it by hand at this level is mostly decoding quasi-ASCII by hand, and the compression isn't making it significantly more painful.

If you reorder the static huffman table and byte align things, the encoded data could look more like:

  T O B E O R N O T T 0x85 0x09 T 0x88 0x0F 0xFF

So short lengths become 0x80 + length and short distances encode as themselves.

This version is pretty easy to decode by hand, and still 16 bytes. I'm arguably cheating by removing the 3 bit header, but even 17 bytes would be good.

Though the encoder deciding to repeat those Ts doesn't make much sense, shouldn't this be compressed to literal("TOBEORNOT") copy(6,9) copy(9,15)?

[ Parent | on HN ]

Re:Understanding Deflate by ack_complete on Wednesday September 17, 2025 @09:34PM (#45283861)

Many Deflate encoders, including zlib/gzip, are greedy encoders that work forwards, either for speed or to support streaming compression. They encode runs as they are found scanning forward, with limited lookahead to try to allow longer matches to preempt immediately preceding shorter matches. There is an "optimal parse" strategy that maximizes the runs found by processing the entire file backwards.

If you repack the plaintext using zopfli, it does encode the text as you suggest.

[ Parent | on HN ]

Re:Understanding Deflate by Dylan16807 on Wednesday September 17, 2025 @09:46PM (#45283972)

Being greedy is fine here, though. It's the exact same match but somehow cut one byte short.

Also I just tested something. If you stick a random extra letter onto the start of the string, the mistake goes away and the output shrinks by a byte. Is it possibly an issue with finding matches that start at byte 0...?

More testing: Removing the Ts that fail to match to get TOBEORNOTOBEOROBEORNOT shrinks the output by 2 bytes. Changing the first character to ZOBEORNOTOBEOROBEORNOT stays at the same shrunken size. Then removing that Z to get OBEORNOTOBEOROBEORNOT makes it balloon back up as now it fails to match the O twice.

If I take the original string and start prepending unique letters, the first one shrinks and fixes the matching, and then each subsequent letter adds one byte. So it's not that matching needs some particular alignment, it's only failing to match the very first byte.

A new test: XPPPPPPPP appears to encode as X, P, then a copy command. And PPPPPPPPP encodes as P, P, then a copy. Super wrong.

[ Parent | on HN ]

Re:Understanding Deflate by ack_complete on Thursday September 18, 2025 @01:44AM (#45285894)

Interesting, I can also reproduce this. I wonder if it's an artifact of zlib's sliding window setup. The odd part is that if I try various libs with advzip, both the libdeflate and 7z modes show the same artifact, only the zopfli mode is able to avoid it. Doesn't seem to be a format violation as gzip -t doesn't complain about a copy at position 0.

[ Parent | on HN ]

Re:Understanding Deflate by zmodem on Thursday September 18, 2025 @04:38AM (#45287127)

> Though the encoder deciding to repeat those Ts doesn't make much sense, shouldn't this be compressed to literal("TOBEORNOT") copy(6,9) copy(9,15)?

IIRC zlib won't consider matches at offset 0: https://github.com/madler/zlib/blob/5a82f71ed1dfc0bec044d970...

[ Parent | on HN ]