LZ4

Deep dive

How it works

In: a byte block (frame mode: a stream of 64 KB-4 MB blocks) · Out: a sequence stream of token, literals, offset and length extensions · State: a 16 KB hash table per block (4K u32 entries at the default LZ4_MEMORY_USAGE=14); none for decoding · Cost: compress O(n) with one hash probe per position; decompress O(n) copies

Block format (the frame format adds magic 0x184D2204, block sizes 64 KB-4 MB and optional xxHash32 checksums):

sequence = token | [lit-len ext] | literals | offset(u16 LE) | [match-len ext]
token    = (min(lit_len,15) << 4) | min(match_len-4, 15)
ext      = 255, 255, ..., r   (added to 15 when the nibble is 15)

1. Hash the 4 bytes at position i (multiplicative hash, 12-16 bits), look up the last position with the same hash, store i.
2. If the candidate is within 64 KB and its 4 bytes match, extend forward (and backward over pending literals), emit a sequence.
3. If not, advance; the step grows the longer no match is found (skip incompressible data quickly).
4. Format rules: the last 5 bytes are always literals, and the last match must start at least 12 bytes before the end; the last sequence has only literals.

Code

A complete block compressor (greedy, single-probe) and a bounds-checked decompressor; output is compatible with LZ4_decompress_safe.

const MIN_MATCH: usize = 4;
const LAST_LITERALS: usize = 5; // last 5 bytes are always literals
const MF_LIMIT: usize = 12; // last match starts >= 12 bytes before the end
const HASH_LOG: u32 = 12;

fn read_u32(s: &[u8], i: usize) -> u32 { u32::from_le_bytes(s[i..i + 4].try_into().unwrap()) }

fn write_len(out: &mut Vec<u8>, mut n: usize) {
    while n >= 255 { out.push(255); n -= 255; }
    out.push(n as u8);
}

fn emit(out: &mut Vec<u8>, lits: &[u8], m: Option<(usize, usize)>) {
    let ml = m.map_or(0, |(_, len)| len - MIN_MATCH);
    out.push(((lits.len().min(15) as u8) << 4) | ml.min(15) as u8);
    if lits.len() >= 15 { write_len(out, lits.len() - 15); }
    out.extend_from_slice(lits);
    if let Some((offset, _)) = m {
        out.extend_from_slice(&(offset as u16).to_le_bytes());
        if ml >= 15 { write_len(out, ml - 15); }
    }
}

pub fn compress(src: &[u8]) -> Vec<u8> {
    let mut out = Vec::with_capacity(src.len() + src.len() / 255 + 16);
    let mut table = vec![0u32; 1 << HASH_LOG];
    let (mut anchor, mut i) = (0, 0);
    while i + MF_LIMIT <= src.len() {
        let seq = read_u32(src, i);
        let h = (seq.wrapping_mul(2_654_435_761) >> (32 - HASH_LOG)) as usize;
        let mut cand = table[h] as usize;
        table[h] = i as u32;
        if cand >= i || i - cand > 65_535 || read_u32(src, cand) != seq {
            i += 1 + ((i - anchor) >> 6); // accelerate through incompressible data
            continue;
        }
        let mut len = MIN_MATCH;
        while i + len < src.len() - LAST_LITERALS && src[cand + len] == src[i + len] { len += 1; }
        while i > anchor && cand > 0 && src[i - 1] == src[cand - 1] { i -= 1; cand -= 1; len += 1; }
        emit(&mut out, &src[anchor..i], Some((i - cand, len)));
        i += len;
        anchor = i;
    }
    emit(&mut out, &src[anchor..], None);
    out
}

fn read_len(src: &[u8], i: &mut usize) -> Result<usize, &'static str> {
    let mut n = 0;
    loop {
        let b = *src.get(*i).ok_or("truncated")?;
        *i += 1;
        n += b as usize;
        if b != 255 { return Ok(n); }
    }
}

pub fn decompress(src: &[u8], max_out: usize) -> Result<Vec<u8>, &'static str> {
    let (mut out, mut i) = (Vec::with_capacity(max_out), 0);
    loop {
        let token = *src.get(i).ok_or("truncated")?;
        i += 1;
        let mut lit = (token >> 4) as usize;
        if lit == 15 { lit += read_len(src, &mut i)?; }
        let lits = src.get(i..i + lit).ok_or("truncated")?;
        if out.len() + lit > max_out { return Err("output overflow"); }
        out.extend_from_slice(lits);
        i += lit;
        if i == src.len() { return Ok(out); } // last sequence: literals only
        let off = u16::from_le_bytes(src.get(i..i + 2).ok_or("truncated")?.try_into().unwrap()) as usize;
        i += 2;
        let mut mlen = (token & 15) as usize + MIN_MATCH;
        if token & 15 == 15 { mlen += read_len(src, &mut i)?; }
        if off == 0 || off > out.len() { return Err("bad offset"); }
        if out.len() + mlen > max_out { return Err("output overflow"); }
        let start = out.len() - off;
        if off >= mlen { out.extend_from_within(start..start + mlen); }
        else { for k in 0..mlen { let b = out[start + k]; out.push(b); } } // overlap repeats pattern
    }
}

Complexity and constants

• Compressor state: one hash table, 4K u32 entries = 16 KB at the default LZ4_MEMORY_USAGE=14, fits L1. No other memory.
• Per position: one 4-byte load, multiply, table load/store, compare; matches extend 8 bytes per step with XOR + trailing_zeros.
• Decoder: per sequence one token read, two copies; the reference decoder copies in 8-16-byte chunks ("wild copy") and needs output slack, which is why LZ4_decompress_safe handles the last 12 bytes specially.
• Ratio vs speed knobs: acceleration (skip faster, worse ratio), HC levels 3-12 (hash chains / optimal parsing, same decoder).

Efficiency

• Cost: one modern x86 core: order of 500-800 MB/s compress, 3-5 GB/s decompress, ratio about 2.1 on Silesia; LZ4-HC about 2.7 at order of 40 MB/s with the same decode speed. Per position one 4-byte load, a multiply, a table load and store and a compare; matches extend 8 bytes per step. State: a 16 KB hash table that fits L1. Bound: compute for compress, memory bandwidth for decompress.
• Levers:
  • acceleration (skip faster) — incompressible data (JPEG, encrypted) runs at multiple GB/s instead of 500 MB/s — mixed data
  • LZ4-HC levels 3-12 — ratio about 2.7 with the same decoder — write-once, read-many data
  • dictionary or linked blocks — much better ratio on small blocks — records and 4 KB pages
  • store the decompressed size beside the block — one allocation, rejects bombs — block API
  • wild copies in 8-16-byte chunks — decoder runs near memcpy speed — needs output slack at the end
• Naive → standard → state of the art:
  • zstd level 1-3 · 25-40 % smaller at similar compress speed
  • LZ4 fast mode · order of 500-800 MB/s compress, 3-5 GB/s decompress
  • LZ4-HC for cold data · ratio about 2.7, order of 40 MB/s compress, same decode speed

Implementation notes

• Dependent blocks: frame "linked blocks" mode lets block k reference the previous 64 KB; better ratio for small blocks, but blocks can no longer be decoded independently.
• Dictionary: LZ4_loadDict / LZ4_compress_fast_continue prime the 64 KB window; big win for small records.
• Know the decompressed size: the block format does not store it; store it beside the block (as RocksDB, Kafka, ClickHouse do) to allocate once and reject bombs.
• Skip-ahead: the acceleration step makes incompressible data (JPEG, encrypted) run at multiple GB/s instead of 500 MB/s.
• SIMD is not the bottleneck: speed comes from byte-aligned tokens and unaligned 8/16-byte copies, so LZ4 is fast on any 64-bit CPU, including ARM.

Pitfalls

• Using LZ4_decompress_fast (deprecated) on untrusted input: it trusts the stream and can read out of bounds.
• Violating end-of-block rules (match in the last 5 bytes) produces streams that some decoders reject.
• Block vs frame format confusion: raw LZ4_compress_default output is not a .lz4 file.
• Tiny blocks (4 KB pages) compress poorly without a dictionary or linked blocks.
• Hash table not cleared between independent blocks: references into the previous block, which the decoder lacks.

Variants and alternatives

In production

Operating systems and file systems: Linux kernel (zram, squashfs, crypto API), OpenZFS (default when compression=on). Databases and search: RocksDB, Cassandra (default SSTable compressor), ClickHouse (default column codec), Lucene stored fields (BEST_SPEED), Hadoop. Messaging: Apache Kafka. Games: Unity caches AssetBundles with chunk-based LZ4.

Implementations

Sources

• Y. Collet, LZ4 Block Format Description and LZ4 Frame Format Description, github.com/lz4/lz4 (doc/), current version. block · frame · code
• J. Ziv, A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Trans. Information Theory, 1977. paper
• Unity Manual, AssetBundle caching and compression (LZMA and chunk-based LZ4). docs