lz77

Lempel-Ziv 77 string-match encoder (hash-chain) — shared primitive for codecs.

Module lz77 | Source packages/front/fw/src/io/compress/lz77.js | Deps none | Worker-safe yes

Generic LZ77 matching primitive usable by any codec that emits a token stream (literal | <length, distance>): DEFLATE (RFC 1951), Brotli (RFC 7932), Snappy, etc. Classic hash-chain implementation with:

• Configurable sliding window (windowBits, max 22).
• Parameterizable min/max match length.
• Chain depth (chainDepth) — speed/ratio trade-off; niceLength ends the search at a position early.
• Optional lazy matching (lazy) — probes the next position before emitting the current match, throttled by goodLength / maxLazy (zlib semantics).
• Optional chain-skip walk (chainSkip) — the fflate heuristic that continues the walk on the sparsest chain inside the current best match.

The scan runs once, in encodeTokens, and packs the token stream as (len|0, dist|byte) pairs into an Int32Array (8 bytes per input byte past start); encode replays that buffer through two callbacks (literal(pos), match(pos, len, dist)). Both accept opts.tokens to reuse a caller-owned buffer across calls.

Resolve

const lz77 = runtime.resolve('lz77');
// { encode, encodeTokens, findMatch, decodeStream, DEFAULT }

API

Options

With the defaults, goodLength / maxLazy never trigger and chainSkip is off: an option set that predates them scans exactly as before.

Callbacks

{
    literal(pos: number): void,
    // data[pos] is emitted as-is as a literal byte.

    match(pos: number, len: number, dist: number): void,
    // Match of `len` bytes at `pos`, copying from `pos - dist`.
}

Examples

Simple round-trip

const lz77 = runtime.resolve('lz77');
const data = new TextEncoder().encode('ABCDABCDABCD');

const ops = [];
lz77.encode(data, { minMatch: 4 }, {
    literal: pos => ops.push({ lit: data[pos] }),
    match:   (pos, len, dist) => ops.push({ len, dist }),
});

// Reconstruction
const out = new Uint8Array(data.length);
lz77.decodeStream(out, ops);
new TextDecoder().decode(out);  // 'ABCDABCDABCD'

For a DEFLATE-like codec (minMatch=3)

lz77.encode(data, { minMatch: 3, windowBits: 15, chainDepth: 32, lazy: true }, {
    literal: pos => emitLiteral(data[pos]),
    match:   (pos, len, dist) => emitMatch(len, dist),
});

For a Brotli-like codec (minMatch=4)

lz77.encode(data, { minMatch: 4, windowBits: 22, chainDepth: 16, lazy: true }, {
    literal: pos => insertBuffer.push(data[pos]),
    match:   (pos, len, dist) => emitIacCommand(insertBuffer, len, dist),
});

Packed tokens (the scan itself)

encodeTokens is the scan: it packs the (literal | match) sequence directly into an Int32Array as (len|0, dist|byte) pairs, optionally reusing a caller-supplied buffer. encode is a replay of that buffer, so a consumer that can read pairs saves one call per token.

const lz77 = runtime.resolve('lz77');
const data = new TextEncoder().encode('ABCDABCDABCD');

const { tokens, count } = lz77.encodeTokens(data, { minMatch: 4 });
for (let k = 0; k < count; ++k) {
    const a = tokens[2 * k], b = tokens[2 * k + 1];
    if (a === 0) consumeLiteral(b);        // b = the literal byte
    else consumeMatch(a, b);               // a = len, b = dist
}

// Reuse a preallocated buffer across calls (throws if too small):
const buf = new Int32Array(2 * data.length);
lz77.encodeTokens(data, { minMatch: 4, tokens: buf });

Worker Usage

const worker = fw.createWorker(
    function ({ libs, args }) {
        const lz77 = libs.lz77;
        let matches = 0, lits = 0;
        lz77.encode(args[0], { minMatch: 4 }, {
            literal: () => ++lits,
            match: () => ++matches,
        });
        self.postMessage({ matches, lits });
    },
    { dependencies: ['lz77'], args: [new TextEncoder().encode('ABCDABCD')] }
);

Notes

• The implementation uses a Knuth-style multiplicative hash over 3 or 4 bytes (depending on minMatch). No optimal distribution guarantees — tune hashBits to the typical input size.
• The tail (the last minMatch-1 bytes) is always emitted as literals — no match is possible when there are not enough bytes to form a hash key.
• chainDepth=1 produces a "fast" encoder (single probe per position); high values (32-256) approach an optimal match at the cost of throughput.
• After a lazy win the start of the winning match is inserted into the chains like any other match start: earlier versions never inserted it, which left those positions unreachable by later probes — on a 256 KiB JSON corpus that alone cost +2.8 % of output.
• The probe reports its distance through a factory-scope side channel rather than a { len, dist } object, so the hot loop allocates nothing per match; findMatch wraps it into the documented object for callers.
• No Huffman optimisation or entropy encoding — that is the consumer codec's responsibility.
• Worker-safe: pure factory, no window/document access.
• hashFn MUST be pure and read only data[pos .. pos + minMatch - 1] — its return value is masked internally (& ((1 << hashBits) - 1)), so it may return any integer without risking an out-of-range hash-table index.

See also

• bitstream — bit-level primitive used by consumer codecs
• huffman — entropy coding that naturally follows LZ77
• deflate — example codec (RFC 1951) using LZ77 + Huffman
• brotli — consumer codec (RFC 7932)