= Deflate overlapping copy
{c}
In a <Deflate overlapping copy>, $\ell>d$: some source <bytes> are created by the very copy being decoded. For each step $i=0,\ldots,\ell-1$, read the current <output> at index $n+i-d$ and append that <byte> at index $n+i$. Because $d\geq1$, the source index is always smaller than the destination index, so the needed <byte> exists when it is read.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[RFC 1951, section 3.2.3, printed p. 11: overlapping string references]{ref}
For `ABC` followed by $(9,3)$, the source indices are $0,1,2,3,4,5,6,7,8$ and the destination indices are $3,4,5,6,7,8,9,10,11$. Steps 0 through 2 copy the original `ABC`; steps 3 through 5 copy the `ABC` just appended; steps 6 through 8 copy the next newly appended `ABC`. Thus the final <output> is exactly `ABCABCABCABC`. Taking a snapshot of the original three-<byte> source slice would produce only three <bytes>; that operation does not implement the specified nine-<byte> copy.
\Image[/deflate-overlapping-copy-trace.png]
{title=Nine successive copies at distance three extend ABC to ABCABCABCABC using newly produced bytes}
The reusable idea is a short description of periodic continuation: the decoder repeatedly looks a fixed distance behind its growing <output>. A <Deflate backreference> can also reach across a <Deflate block framing> boundary. Changing the block's <Huffman codes> does not by itself erase the decoded history.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[RFC 1951, sections 2 and 3.2.3: independent block codes, references across blocks]{ref}
Back to article page
