LZ77 Decoding

Decoding LZ77 is straightforward: maintain an output buffer; for each token, either append a literal or copy bytes from earlier in the buffer.

The subtle bit: when length > offset, the copy reads bytes that are being WRITTEN by the same copy operation. This is intentional — it's how LZ77 expands constant runs efficiently:

input:    aaaaaaaa  (8 a's)
encoded:  a (1,7)
decoded:
  start: "a"
  copy from offset 1, length 7:
    pos 1: out[1-1] = 'a' -> out = "aa"
    pos 2: out[2-1] = 'a' -> out = "aaa"
    ... and so on, byte-by-byte.

This means a single (1, n) token expands to n+1 identical bytes. Run-length encoding for free.

LZ77 + a back-reference encoding scheme + literal-byte encoding scheme + a coding for both = DEFLATE (gzip, zlib). zlib and gzip differ only in container format.