Zstandard (zstd)

Deep dive

How it works

In: a byte stream and a level (−131072..22) · Out: a frame of blocks (at most 128 KB each) holding Huffman-coded literals and FSE-coded sequences · State: the window (up to 8 MB at normal levels), entropy tables, 3 repeat offsets; optional dictionary · Cost: decode O(n) at order of 1-2 GB/s per core, level-independent

1. Frame: magic 0xFD2FB528, header (window size, optional content size, dictionary ID), blocks of at most 128 KB, optional 4-byte XXH64 checksum.
2. Block types: raw, RLE, or compressed.
3. Match finding by level: fast, dfast (hash tables), greedy, lazy, lazy2 (hash chains), btlazy2, btopt, btultra, btultra2 (binary trees + price-based optimal parsing).
4. Literals section: raw, RLE, or Huffman (max 11-bit codes, 1 or 4 streams); "treeless" reuses the previous block's table.
5. Sequences section: each sequence's LL, ML and offset are mapped to small codes plus extra bits; the 3 code streams are FSE-coded with predefined, RLE, freshly described, or repeated tables. The bitstream is read backward (ANS is LIFO).
6. Execution: copy LL literals, then copy ML bytes from offset back; repeat offsets are tracked as below.

block = literals (Huffman x4)  +  sequences (FSE: LL codes | OF codes | ML codes, interleaved backward)
exec:  out += lit[..ll]; out += out[-offset .. -offset+ml]   for each sequence

Code

Sequence execution with repeat offsets exactly as RFC 8878 §3.1.1.5 defines it (the subtle part of a zstd decoder), plus practical use of the zstd crate (libzstd bindings).

pub struct Seq { pub ll: usize, pub of: usize, pub ml: usize } // of = Offset_Value from the stream

/// `rep` starts as [1, 4, 8] per frame (or comes from the dictionary).
pub fn execute(lits: &[u8], seqs: &[Seq], rep: &mut [usize; 3], out: &mut Vec<u8>)
    -> Result<(), &'static str> {
    let mut lp = 0;
    for s in seqs {
        out.extend_from_slice(lits.get(lp..lp + s.ll).ok_or("literals overrun")?);
        lp += s.ll;
        let offset = if s.of > 3 {
            let o = s.of - 3; // a real offset: push to the front
            *rep = [o, rep[0], rep[1]];
            o
        } else {
            // 1..3 are repeat codes; when ll == 0 they shift by one and 3 means rep[0] - 1
            let idx = if s.ll == 0 { s.of } else { s.of - 1 };
            let o = if idx == 3 { rep[0] - 1 } else { rep[idx] };
            match idx {
                0 => {}
                1 => rep.swap(0, 1),
                _ => *rep = [o, rep[0], rep[1]],
            }
            o
        };
        if offset == 0 || offset > out.len() { return Err("bad offset"); }
        let start = out.len() - offset;
        for k in 0..s.ml { let b = out[start + k]; out.push(b); } // overlap-safe
    }
    out.extend_from_slice(&lits[lp..]); // trailing literals
    Ok(())
}

use std::io::{self, Read, Write};

/// Streaming file compression with the knobs that matter.
pub fn compress_stream(src: &mut impl Read, dst: impl Write, level: i32) -> io::Result<()> {
    let mut enc = zstd::stream::write::Encoder::new(dst, level)?;
    enc.include_checksum(true)?; // XXH64-based, catches corruption
    enc.multithread(4)?; // crate feature "zstdmt"; jobs of several MB each
    enc.long_distance_matching(true)?; // finds repeats far beyond the normal window
    enc.window_log(27)?; // 128 MB, the largest a default decoder accepts
    io::copy(src, &mut enc)?;
    enc.finish()?;
    Ok(())
}

pub fn decompress_stream(src: impl Read, dst: &mut impl Write) -> io::Result<u64> {
    let mut dec = zstd::stream::read::Decoder::new(src)?;
    dec.window_log_max(31)?; // allow windows above 128 MB (memory = window size)
    io::copy(&mut dec, dst)
}

/// Small messages: one-shot API; reuse a Compressor to avoid re-allocating context (~1 MB+).
pub fn roundtrip(msg: &[u8]) -> io::Result<Vec<u8>> {
    let c = zstd::bulk::compress(msg, 3)?;
    zstd::bulk::decompress(&c, msg.len()) // capacity = max allowed output size
}

Complexity and constants

• Decode memory: window size (up to 8 MB at normal levels) + ~100 KB of tables. Encode memory grows with level: order of 1 MB at level 1 to hundreds of MB at 19-22 with --long.
• Decode speed is level-independent: order of 1-2 GB/s per core on x86 and Apple silicon; it is bound by the sequence-execution loop and Huffman decoding.
• Compression time per level is roughly geometric: each step of 2-3 levels at the high end halves speed for 1-2 % ratio.
• Block size cap 128 KB keeps entropy tables local; small inputs (< 1 KB) pay ~10-30 bytes of header/table overhead, use dictionaries.

Efficiency

• Cost: decode order of 1-2 GB/s per core on x86 and Apple silicon, independent of level, bound by the sequence-execution loop and Huffman decoding. Encode: level 1 order of 400-500 MB/s at ratio about 2.9 on Silesia (zlib -1: about 2.7 at about 100 MB/s); level 19 order of 3-10 MB/s with ratio near xz. Memory: decode needs the window plus about 100 KB of tables; encode from order of 1 MB at level 1 to hundreds of MB at levels 19-22 with --long. Inputs under 1 KB pay about 10-30 bytes of header and table overhead.
• Levers:
  • reuse contexts (ZSTD_CCtx, zstd::bulk::Compressor) — avoids allocations larger than a small message — many small calls
  • trained dictionary — large ratio gain on sub-KB records — small similar messages
  • pledged source size — smaller window and tables, size in the header — inputs of known length
  • multithreading (-T0) — jobs of several MB with overlap, one standard frame out — large inputs, encode only
  • --long long-distance matching — big wins on tarballs, VM images, backups — far repeats
• Naive → standard → state of the art:
  • zlib -1 · ratio about 2.7 at about 100 MB/s
  • zstd level 1-3 · ratio about 2.9 at order of 400-500 MB/s
  • zstd level 19 with --long or a dictionary · ratio near xz at order of 3-10 MB/s, decode still 1+ GB/s

Implementation notes

• Reuse contexts (ZSTD_CCtx / zstd::bulk::Compressor): creating one costs allocations bigger than a small message.
• Pledged source size (set_pledged_src_size) lets the encoder shrink window and tables for small inputs and records the size in the header.
• Multithreading splits input into jobs (by default several MB, depending on level) with overlap so matches cross job borders; output is a single standard frame.
• Long-distance matching uses a rolling hash over the full window; big wins on tarballs, VM images and backups with far repeats.
• --patch-from=old: uses an old file as dictionary for binary diffs, competitive with bsdiff at much higher speed.
• Seekable format (contrib): independent frames + an index in a skippable frame, for random access.
• Adaptive (--adapt) switches level based on I/O speed in streaming pipelines.

Pitfalls

• Huge windows (--long=31) produce frames that default decoders reject (Frame requires too much memory); decoders must opt in with window_log_max, and memory = window.
• Assuming the content size is in the header: streaming frames often omit it; never trust it for allocation without a cap.
• Levels 20+ ("ultra") use much more memory on both sides through larger windows.
• Compressing many tiny records independently: per-frame overhead and cold statistics; use a dictionary or batch records.
• Mixing up zstd -T0 (multithreaded encode) with decode: decompression is single-threaded per frame.

Variants and alternatives

In production

Operating systems and storage: Linux kernel (btrfs, squashfs, f2fs, zram, kernel and initramfs images), OpenZFS, Arch Linux and Fedora packages. Web: HTTP Content-Encoding: zstd (Chrome, Firefox; RFC 8878). Databases and data formats: RocksDB, Kafka, Parquet/ORC/Arrow, PostgreSQL WAL and backup compression, MySQL binlog transaction compression.

Implementations

Sources

• Y. Collet, M. Kucherawy, RFC 8878: Zstandard Compression and the 'application/zstd' Media Type, 2021. RFC
• Y. Collet, zstd_compression_format.md and benchmarks in the README, github.com/facebook/zstd. spec · code
• J. Duda, Asymmetric numeral systems, arXiv:1311.2540, 2013. arXiv