deflate

DEFLATE compression (RFC 1951) — LZ77 + Huffman coding. Internal engine used by gzip, zlib, and zip.

Module deflate | Source packages/front/fw/src/io/compress/deflate.js | Deps bitstream, huffman, lz77 | Worker-safe yes

Resolve

const deflate = runtime.resolve('deflate');
// Returns: { deflateSync, inflateSync, deflate, inflate, DeflateStream, InflateStream }

API

Synchrone

const compressed   = deflate.deflateSync(uint8Array, opts?);  // → Uint8Array
const decompressed = deflate.inflateSync(compressed, opts?);  // → Uint8Array

Asynchrone

const compressed   = await deflate.deflate(uint8Array, opts?);  // → Uint8Array
const decompressed = await deflate.inflate(compressed, opts?);  // → Uint8Array

The async API uses queueMicrotask — it does not block the thread but is not multi-threaded.

Streaming — compression (deflate)

const chunks = [];
const stream = new deflate.DeflateStream(opts?, (chunk) => chunks.push(chunk));

stream.push(data1);
stream.push(data2);
stream.flush();              // flushes the buffer without finalizing
stream.push(lastChunk, true); // finalizes the stream

Streaming — decompression (inflate)

const output = [];
const stream = new deflate.InflateStream(opts?, (chunk) => output.push(chunk));

stream.push(compressedChunk);
stream.push(lastChunk, true);

Options

Compression

The same options reach deflate through gzip, zlib and zip, so gzipSync(data, { level: 9, lazy: true }) is the maximum-ratio request.

Decompression

Error codes

Every error thrown by this module is an Error carrying a numeric e.code. The table lists the complete set — verified against the fail() call sites in deflate.js.

Codes 12 and 13 belong to gzip and zip; deflate never emits them.

Design

Decoder

The decoder (inflateSync, inflate, InflateStream) is written from RFC 1951 and shares its derived tables with the encoder below.

Tables. Nothing is transcribed by hand. LENGTH_EXTRA / LENGTH_BASE (symbols 257–285) and DIST_EXTRA / DIST_BASE (symbols 0–29) are derived at factory time from the RFC §3.2.5 formulas — extra(i) = i < 8 || i === 28 ? 0 : (i - 4) >> 2 for lengths, extra(i) = i < 4 ? 0 : (i - 2) >> 1 for distances — with the bases accumulated from 3 and 1 respectively and the single special case LENGTH_BASE[28] = 258. CODE_LENGTH_ORDER (§3.2.7) and the fixed code lengths (§3.2.6: 8/9/7/8 for the literal code, a flat 5 for the 30 usable distance codes) follow the same rule. The decode tables come from the shared huffman.buildMap(lengths, maxBits, 1) primitive: an entry is (symbol << 4) | codeLength, indexed by the next maxBits bits read LSB-first, and entry 0 means "no code here". deflate.test.js re-derives each table from the RFC formulas, compares it with the RFC tables transcribed literally, and decodes a hand-assembled vector per length and per distance symbol at both ends of its range.

Block state machine. A decoder state — bitPos, finalBlock, phase, storedRemaining, the two tables and their widths, out / outLen / emitted — moves between four phases: HEADER reads BFINAL + BTYPE and the per-type preamble (stored LEN/NLEN, the fixed tables, or the dynamic header of §3.2.7); STORED copies the body of a BTYPE = 0 block, resuming a partial copy; CODES decodes literal/length and distance symbols until end-of-block; DONE is reached when the final block ends.

Resumability. bitstream.readBits pads reads past the end of the buffer with zeros, so an overrun is detected by POSITION, never by an exception: bitPos is snapshotted before each block header and before each symbol, and a read that lands past input.length * 8 — or a table lookup that returns entry 0 while fewer than maxBits bits remain — restores the snapshot. In one-shot mode that condition fails with code 0; in stream mode it returns "need input", InflateStream keeps the bytes from the last consumed byte boundary, and the next push re-reads from the snapshot (a partially read dynamic header is simply re-parsed, which is bounded by the header size). After each push only the last 32 KiB of output are retained as the back-reference window.

Output growth. Without opts.out the buffer starts at max(64 KiB, 3 × input.length) and doubles on demand; the result is a copy trimmed to the exact length. With opts.out the decoder writes directly into the caller's buffer, returns a view into it, and raises code 8 rather than growing. opts.dictionary primes the output with the dictionary's last 32 KiB so back-references into it are ordinary in-buffer copies; combined with opts.out, decoding runs in an internal buffer and the payload alone is copied across at the end.

Known limitation. An over-subscribed or incomplete dynamic Huffman code is not validated when the header is read. Such a stream is not silently accepted: decoding proceeds and ends in code 2, code 3 or code 8 as soon as a hole in the table is hit.

Encoder

The compressor (deflateSync, deflate, DeflateStream) is written from RFC 1951 as well. Its matching pass is the shared lz77 module — deflate owns only the DEFLATE-specific parts: the symbol mapping of §3.2.5, the block-type decision, and the canonical Huffman coding of §3.2.6/§3.2.7.

Matching. lz77.encodeTokens is called once per compression unit with windowBits: 15, minMatch: 3, maxMatch: 258 and an injected hashFn — the 3-byte Fibonacci hash imul(d[i] | d[i+1] << 8 | d[i+2] << 16, 0x9E3779B1) >>> (32 - hashBits), i.e. exactly the bytes that define a minimum-length match, and with the chainSkip walk on. Search effort per level, as shipped (zlib's shape for chainDepth / niceLength / goodLength / maxLazy):

level defaults to 6 and is clamped to 0..9. No level turns lazy matching on: goodLength / maxLazy (levels 1–3: the lz77 defaults) only act under the lazy option below.

Lazy matching is an option, not a level. { lazy: true } enables lz77's lazy probe at every level ≥ 1 — the same engine with one more probe per match, throttled by the level's goodLength / maxLazy. It is what buys the ratio (−0.67 % bytes at levels 8–9 on the bench corpora, and better than zlib on the text corpus) and what costs the time (+18 % at level 8, +90 % on the JSON corpus). The default stays the fast configuration because that is the one that meets the batch's < +5 % time gate at every level. Measured on the option-vs-separate-path question: the lazy test is taken once per match, on a hoisted local, and an interleaved A/B of the shipped scanner against the same file with the lazy branch deleted gives an aggregate Δ of +0.1 % / +1.5 % / +0.5 % (levels 1 / 4 / 8) in one load order and −1.1 % / +0.2 % / −1.0 % in the other — noise, so one loop and one option rather than two scan functions.

mem → hashBits. With mem given, the hash table is min(22, 12 + mem) bits wide; without it the width tracks the input size, clamp(ceil(log2(inputLength)), 12, 20).

Blocks and cost. The scan of a compression unit is one lz77.encodeTokens call whose packed (len | 0, dist | byte) pairs are read in place: a block is a window [from, to) of 16 384 tokens over that buffer, tallied in one pass into the literal/length and distance frequencies and the total of extra bits, then written; the tail block carries BFINAL. The pairs are never copied into a second layout. For each block three exact bit costs are computed and the cheapest wins:

Trees come from huffman.buildTree(freqs, 15) (7 for the code-length code) and codes from huffman.buildMap(lengths, maxBits, 0), which are already bit-reversed for bitstream.writeBits. A block with no distance token is written with HDIST = 1 and a single distance length of zero, as §3.2.7 allows. The dynamic form is skipped when the literal/length or code-length code would hold a single symbol: that code is incomplete, which §3.2.7 tolerates only for distances. An empty input is therefore one empty final fixed block — the two bytes 03 00.

BLOCK_TOKENS stays at 16 384: huffman.buildTree uses a frequency sentinel of 25 001, so a block's symbol total must stay below it.

Memory. The token buffer is the encoder's working set: deflateSync on N bytes holds an Int32Array of 2 × N entries — 8 bytes per input byte — until it returns (up to 8 MiB of it is kept between calls as a scratch buffer; larger ones are transient). DeflateStream compresses in 64 KiB units and stays bounded. A resumable scanner filling a fixed BLOCK_TOKENS buffer would remove this and is the recorded follow-up.

Streaming. DeflateStream keeps the last 32 KiB of input as a window and buffers pushes until 64 KiB or final, then compresses window ++ pending with start = window.length. Whole bytes go out through ondata; a trailing partial byte stays in the carry and opens the next unit, so flush() never forces byte alignment. The contract is that the concatenation of every ondata chunk is one valid raw DEFLATE stream — where the chunk boundaries fall is not part of it, and they differ from the pre-batch engine's.

Benchmark

Final gate record on the merged tree, full baseline sha b10c8a6da43e8c598645d097a678c38249ddebbc (git merge-base master HEAD), with the batch's exact command:

bun packages/front/fw/tools/bench/deflate-levels.js \
    --baseline b10c8a6da43e8c598645d097a678c38249ddebbc --reps 7 --warmup 3 \
    --json bench-final.json

Host: win32 / 13th Gen Intel(R) Core(TM) i7-13700KF / Bun 1.3.13. Six deterministic corpora (text = the RFC 7932 dictionary blob, source = brotli.js, json, random, repeat, small = 200 × 2 KiB calls), levels 1–9, median of 7 timed reps after 3 warm-ups. Artifact of the benchmark run (not shipped), generated 2026-09-05T10:53:48.246Z. Every output of both engines round-trips through our inflateSync, and the fw test suite cross-checks the same corpora against node:zlib. Δ is new against old; a negative Δtime is faster. The ruled gate is Δtime < +5 % per level, with a proposed ratio tolerance of Δratio ≤ +1 %.

Default configuration (shipped table, lazy off)

All nine levels PASS both thresholds: Δtime is negative (faster) at every level and Δratio stays within ±1 % (better than the baseline at levels 1–3, at parity elsewhere — the largest regression is +0.48 % at level 4). Per corpus, the persistent residual is the incompressible random corpus (+13 … +53 % in this run — the known fixed per-position cost of the generic scanner over an engine that inlines its probe, the analysis' fix 7, deliberately not taken); repeat is the biggest winner at −46 … −56 %.

Measurement caveat. Individual per-corpus cells of this sequential harness move by up to ±30–50 % between runs on this host, in both directions — the aggregate per level, not any single cell, is what the gate reads. The text corpus at level 4 is a reproducible instance of this (this run: old 2.79 ms / new 3.82 ms, a cell Δtime of +37 %, while the level's aggregate is still −10.2 %): an earlier interleaved-repetition investigation traced it to a JIT-state carry-over that appears only when the repeat corpus runs immediately before text in the same process at level 4, disappears when level 4 runs alone or in a directory-to-directory interleaved comparison — there this engine is byte-identical to the analysis' p6nl prototype at every cell and within ±1 % of its time — and is unrelated to the engine change. Read the aggregates, not the cells; a finer per-corpus verdict needs interleaved A/B repetitions (backlog item proposed in the perf-landing session, not yet filed as this task's perimeter excludes the bench tool).

{ lazy: true } (same engine, lazy matching on) — supplementary, not gated

Measured separately by the perf-landing session at --warmup 15 --reps 11 (not re-run by this task: the batch gate covers only the default configuration above).

Lazy matching is where the ratio comes from — and where the time goes at the two top levels: json +85 … +91 %, text +38 … +40 %, source +6 … −13 %, small −9 … −14 %. At level 9 with lazy the text corpus compresses to 58 286 bytes, below zlib's 59 319 at its level 9; at level 4 the zlib-shaped table (maxLazy 4) gives up ratio on json (+4.5 %) for a −13 % time, the trade the analysis flagged and the owner accepted.

Artifacts of the lazy run: the default-configuration output and the lazy-configuration output (not shipped). Re-run with bun packages/front/fw/tools/bench/deflate-levels.js --baseline b10c8a6da43e8c598645d097a678c38249ddebbc --warmup 15 --reps 11 [--opts '{"lazy":true}']. The gate table above (default configuration) was re-run for this record with the batch's own --reps 7 --warmup 3; artifact of the gate run (not shipped).

Clean-room huffman/bitstream rewrite (2026-09)

deflate.js itself is unchanged by the clean-room rewrite; this record measures the effect on the deflate codec of the underlying huffman/bitstream clean-room rewrite (see huffman, bitstream) plus the perf pass landed on huffman.js (two-queue fast path ahead of package-merge). Same six corpora and levels 1-9, --reps 7 --warmup 3, baseline sha d47f8fc7a68809f519fe7d36ff2b0ba88bcacdbd (git merge-base master HEAD taken before the rewrite). Host win32 / 13th Gen Intel(R) Core(TM) i7-13700KF / Bun 1.3.13. Generated 2026-09-24T20:49:44.085Z (gitignored bench artifact). Rule: Δenc < +5 %, Δdec < +5 % per level and per corpus; Δbytes ≤ 0.

43/54 PASS, 11/54 FAIL. Δbytes is +0.000 % on every one of the 54 cells (the deflate codec's own bit-packing is untouched; only the huffman/bitstream primitives underneath it changed). Every red cell is a time cell, and it is the harness's own measurement noise: a later measurement ruling accepted these cells as the measured floor, based on a live-vs-live identical-code A/A run at the same parameters that puts 10-21 of these 54 cells past |5 %|, while at --reps 15 all sub-millisecond and GC-heavy cells stabilise. The residual cells above are accepted as the measurement floor, not a regression — the same acceptance applies to brotli.md, lz4.md, huffman.md and bitstream.md.

Provenance

In-house implementation from RFC 1951; the earlier fflate-derived implementation has since been replaced. The LZ77 matching pass is the shared lz77 module.

Example

const deflate = runtime.resolve('deflate');

const data = new TextEncoder().encode('Hello World '.repeat(500));

// Sync
const compressed   = deflate.deflateSync(data, { level: 6 });
const decompressed = deflate.inflateSync(compressed);

// With dictionary (better compression for similar data)
const dict = new TextEncoder().encode('Hello World ');
const c = deflate.deflateSync(data, { level: 9, dictionary: dict });
const d = deflate.inflateSync(c, { dictionary: dict });

Worker Usage

const worker = fw.createWorker(
    function ({ libs, args }) {
        const deflate = libs.deflate;
        const compressed = deflate.deflateSync(args.data, { level: 6 });
        self.postMessage(compressed, [compressed.buffer]);
    },
    { dependencies: ['deflate'], args: { data: new Uint8Array(largeData) } }
);

Notes

• This module is the low-level primitive. For common usage, prefer gzip or zlib which add a header + checksum.
• The DeflateStream / InflateStream streams are reused internally by gzip and zlib.
• Both halves implement RFC 1951 §3.2.3–§3.2.7 directly — see Design › Decoder for the table derivation, the block state machine and the resumability rule, and Design › Encoder for the level table, the lazy opt-in, the block-cost rule and the streaming chunk contract; Benchmark carries the measured record against the pre-batch engine.

See also

• gzip — DEFLATE + gzip header + CRC32
• zlib — DEFLATE + zlib header + Adler32
• zip — multi-file archiving
• lz77 — the hash-chain matcher the encoder scans with