Everyone knows gzip stores repeated data as go back d bytes and copy n. Almost nobody knows that the copy is normally not a copy.
RFC 1951 lets the distance be smaller than the length. The match then reads bytes that have not been written yet, and the decoder must produce them as it goes.
Decode something: https://dev48.infy.uk/solve/day74-deflate-decoder.html
window: ...abc
match: distance 1, length 5
output: abc + c c c c c <- each byte read after it is written
This is how DEFLATE encodes runs, so it is not an exotic corner. In a 120-file corpus:
| matches that overlap | 5.21% of 44,553 |
| files containing at least one | 92 of 120 |
The finding is what happens next
Two obvious wrong implementations fail on exactly the same condition and produce completely different symptoms:
| implementation | what it returns | caught by |
|---|---|---|
| slice-then-append | a shorter file | every test |
| memcpy from the window | the right length, wrong bytes | almost nothing |
// wrong: reads the window as it was before the match started
out.set(win.subarray(pos - d, pos - d + n), pos);
// right: byte at a time, so each write is visible to the next read
for (let i = 0; i < n; i++) out[pos + i] = out[pos - d + i];
The first is a bug you find in ten minutes because the length check fails. The second passes every length assertion, every "does it round-trip a small file" test, and corrupts exactly the files with runs in them.
The page ships a real encoder alongside the decoder, because a page that shipped a precompressed blob would be proving nothing about either.
101,570 verifier asserts, 9,212 in-page checks, 0 failures.
