LZ77

Deep dive

How it works

In: a byte stream and a window size W · Out: a token stream of literals and (distance, length) pairs · State: the last W bytes, a hash head table and a chain array · Cost: decode O(n); encode O(n·chain) with hash chains

1. Keep a hash table head[h] of the most recent position whose next 3-4 bytes hash to h, and prev[pos % W] linking each position to the previous one with the same hash (a hash chain).
2. At position i, walk the chain for up to max_chain candidates within the window; keep the longest match.
3. Lazy matching: before taking a match at i, check i+1; if it has a longer match, emit a literal and move on.
4. Emit a literal or a (dist, len) pair, insert all covered positions into the hash table, advance.
5. Entropy-code the token stream (DEFLATE: one Huffman code for literals+lengths, one for distances).

input:  a b c a b c a b c x
tokens: a b c (dist=3,len=6) x      overlapping copy repeats "abc"

Decoder: for each token, append the literal or copy len bytes starting dist back, byte by byte when they overlap.

Code

Greedy-plus-lazy LZ77 with hash chains (DEFLATE parameters), and the decoder.

const WIN: usize = 1 << 15; // 32 KB window
const MIN: usize = 3;
const MAX: usize = 258;
const HBITS: u32 = 15;

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Token { Lit(u8), Match { dist: u16, len: u16 } }

struct Finder { head: Vec<u32>, prev: Vec<u32>, max_chain: usize } // positions + 1; 0 = empty

fn hash3(s: &[u8], i: usize) -> usize {
    let v = s[i] as u32 | (s[i + 1] as u32) << 8 | (s[i + 2] as u32) << 16;
    (v.wrapping_mul(0x9E37_79B1) >> (32 - HBITS)) as usize
}

impl Finder {
    fn insert(&mut self, s: &[u8], i: usize) {
        if i + MIN > s.len() { return; }
        let h = hash3(s, i);
        self.prev[i % WIN] = self.head[h];
        self.head[h] = i as u32 + 1;
    }
    /// Longest earlier match for position i (call before insert(i)). Returns (len, dist).
    fn longest(&self, s: &[u8], i: usize) -> (usize, usize) {
        if i + MIN > s.len() { return (0, 0); }
        let max_len = MAX.min(s.len() - i);
        let (mut best_len, mut best_dist) = (0, 0);
        let mut cand = self.head[hash3(s, i)];
        for _ in 0..self.max_chain {
            if cand == 0 { break; }
            let j = cand as usize - 1;
            if i - j >= WIN { break; } // chain is ordered newest-first: everything after is too far
            if s[j + best_len] == s[i + best_len] { // cheap reject: must beat best at its last byte
                let l = s[j..].iter().zip(&s[i..i + max_len]).take_while(|(a, b)| a == b).count();
                if l > best_len {
                    (best_len, best_dist) = (l, i - j);
                    if l == max_len { break; }
                }
            }
            cand = self.prev[j % WIN];
        }
        (best_len, best_dist)
    }
}

pub fn compress(s: &[u8], max_chain: usize) -> Vec<Token> {
    let mut f = Finder { head: vec![0; 1 << HBITS], prev: vec![0; WIN], max_chain };
    let (mut out, mut i) = (Vec::new(), 0);
    while i < s.len() {
        let (len, dist) = f.longest(s, i);
        f.insert(s, i);
        if len < MIN || f.longest(s, i + 1).0 > len { // no match, or lazy: a longer one starts at i+1
            out.push(Token::Lit(s[i]));
            i += 1;
            continue;
        }
        out.push(Token::Match { dist: dist as u16, len: len as u16 });
        for k in i + 1..i + len { f.insert(s, k); }
        i += len;
    }
    out
}

pub fn decompress(tokens: &[Token]) -> Vec<u8> {
    let mut out = Vec::new();
    for &t in tokens {
        match t {
            Token::Lit(b) => out.push(b),
            Token::Match { dist, len } => {
                let start = out.len() - dist as usize; // validate dist <= out.len() on untrusted input
                for k in 0..len as usize { let b = out[start + k]; out.push(b); } // overlap-safe
            }
        }
    }
    out
}

Complexity and constants

• Memory: DEFLATE encoder ≈ 2 × 32 KB window + 2 × 64 KB hash/chain arrays, order of 256 KB; decoder needs only the 32 KB window.
• zlib presets (good, lazy, nice, chain): level 1 = (4, 4, 8, 4), level 6 = (8, 16, 128, 128), level 9 = (32, 258, 258, 4096). Each step up roughly halves speed for 1-3 % ratio.
• Order of magnitude on one modern core: zlib compresses at 20-120 MB/s depending on level and decompresses at 300-500 MB/s; libdeflate decompresses at order of 1 GB/s+.
• Match verification is a memcmp; compare 8 bytes at a time with u64 XOR + trailing_zeros / 8 for the mismatch position.

Efficiency

• Cost: on one modern core zlib compresses at 20-120 MB/s depending on level and decompresses at 300-500 MB/s; libdeflate decompresses at order of 1 GB/s or more. Memory: DEFLATE encoder about 2 x 32 KB window + 2 x 64 KB hash/chain arrays, order of 256 KB; the decoder needs only the 32 KB window. Each zlib level step up roughly halves speed for 1-3 % ratio. Bound: match finding (cache misses on the chain) for encode, copy bandwidth for decode.
• Levers:
  • hash 4 bytes with min match 4 — fewer false candidates — fast modes
  • cap max_chain and use a nice-length early exit — avoids degenerate chains on aaaa… — all hash-chain encoders
  • compare 8 bytes at a time (u64 XOR + trailing_zeros / 8) — faster match verification — encoder inner loop
  • wild copy of 16 bytes, pattern expansion for dist < 16 — decoder near memcpy speed — needs output slack
  • optimal parsing (zstd btopt/btultra, LZMA) — order of 5-10 % ratio for about 10x encode cost — write-once data
• Naive → standard → state of the art:
  • brute-force window scan · O(n·W) per stream
  • hash chains with lazy matching (zlib) · 20-120 MB/s compress
  • binary-tree match finders with optimal parsing, repeat offsets · order of 5-10 % smaller at about 10x encode cost

Implementation notes

• Hash 4 bytes (with min match 4) for fast modes: fewer false candidates; 3-byte matches rarely pay off except at short distances (zlib drops 3-byte matches further than 4096 back).
• Binary-tree match finders (LZMA bt4, zstd btlazy2+) keep each hash bucket as a binary search tree over suffixes: finds all useful matches in O(log w), needed for optimal parsing.
• Optimal parsing: instead of greedy choices, run a shortest-path (dynamic programming) over positions with token costs from the entropy coder's current statistics (zstd btopt/btultra, LZMA). Gains order of 5-10 % ratio at 10× encode cost.
• Repeat offsets: real data reuses the same distance (columns, structs); zstd and LZMA keep the last 3-4 distances and code "reuse offset k" cheaply.
• Decoder copies: copy 16 bytes at a time with wildcopy (overwrite up to 15 bytes past the end, requiring output slack) and special-case dist < 16 by pattern expansion.

Pitfalls

• Decoder without checking dist <= bytes produced so far: memory disclosure/overflow, classic CVE material.
• Using memmove/copy_within for overlapping matches: it copies the original bytes, but LZ semantics require replicating the just-written ones.
• Hash chain degeneracy on long runs (aaaa…): every position chains to the previous one; cap max_chain and use a "nice length" early exit.
• Window/table not reset between independent streams: references into stale data.
• Long-distance matches with short length cost more bits than the literals they replace; let the cost model decide.

Variants and alternatives

In production

File formats and web: DEFLATE (gzip, zlib, PNG, ZIP, HTTP Content-Encoding: gzip, RFC 1952). General codecs and databases: LZ4, Snappy, zstd, LZMA/xz/7-Zip, Brotli, LZFSE. Games: Oodle (game assets).

Implementations

Sources

• J. Ziv, A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Trans. Information Theory, 1977. paper
• J. A. Storer, T. G. Szymanski, Data Compression via Textual Substitution, JACM, 1982. paper
• P. Deutsch, RFC 1951: DEFLATE Compressed Data Format Specification 1.3, 1996. RFC
• T. C. Bell, J. G. Cleary, I. H. Witten, Text Compression, Prentice Hall, 1990.
• P. Deutsch, RFC 1952: GZIP file format specification version 4.3, 1996. RFC
• RAD Game Tools, Oodle data compression (Kraken, Mermaid, Selkie, Leviathan). site