5.21% of DEFLATE Matches Copy Bytes That Have Not Been Written Yet

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.