zig-brotli

A Zig 0.17 library that compresses and decompresses Brotli, the compressed data format of RFC 7932.

Its core does no I/O, in either direction. You hand the Compressor or the Decompressor whatever bytes you have and a buffer to write into, and it tells you how much of each it used and whether it wants more input, more room, or is finished. Where the bytes come from and where they go is up to the program that imports it. Input can arrive a byte at a time and output can be drained a byte at a time, and either side resumes exactly where it stopped. For programs that already move their bytes through std.Io, thin adapters put a std.Io.Reader or std.Io.Writer in front of either one.

The API reference is generated from the doc comments, which carry most of the explanation. It is published from the default branch to https://jeff.jcollie.page/zig-brotli/. To read it locally, run zig build docs-serve, which serves it at http://127.0.0.1:8000/; use -Ddocs-port=N for a different port. The pages have to be served rather than opened from disk, because the viewer fetches its data at runtime and a browser refuses to do that from a file:// page.

Quick start

Data that is already in memory takes one call each way:

const std = @import("std");
const brotli = @import("brotli");

pub fn example(gpa: std.mem.Allocator, data: []const u8) !void {
    const compressed = try brotli.compressAlloc(gpa, data, .{ .quality = 6 });
    defer gpa.free(compressed);

    // Fails with error.StreamTooLong rather than produce more than 64 MiB.
    const back = try brotli.decompressAlloc(gpa, compressed, 64 << 20);
    defer gpa.free(back);
}

brotli.compress and brotli.decompress do the same into a buffer you already have. Compressor.maxCompressedSize says how big one must be to compress into; for decompressing, a format such as WOFF2 records the size up front.

With std.Io, compressStream and decompressStream copy one stream from a reader to a writer:

var in = file.reader(io, &in_buffer);
var out = other_file.writer(io, &out_buffer);
_ = try brotli.compressStream(gpa, &in.interface, &out.interface, .{});
try out.interface.flush();

To pull bytes through, CompressReader and DecompressReader are std.Io.Readers over another reader:

var d: brotli.DecompressReader = .init(gpa, &in.interface, &buffer, .{});
defer d.deinit();
const line = try d.reader.takeDelimiterInclusive('\n');

To push them, CompressWriter and DecompressWriter are std.Io.Writers that pass what comes out on to another writer. Call finish at the end:

var c: brotli.CompressWriter = .init(gpa, &out.interface, &buffer, .{});
defer c.deinit();
try c.writer.print("{d} bottles of beer\n", .{n});
// ...more...
try c.finish();

Flushing a CompressWriter makes everything written so far decompressible from what has come out, at the cost of a few bytes, for a reader on the other end of a connection that cannot wait for the whole stream.

std.Io has only error.ReadFailed and error.WriteFailed to report a failure. When the fault is in the stream or the compressor rather than in the underlying reader or writer, the adapter's err field says what it was, and compressStream and decompressStream return that error directly.

Without std.Io, both are driven the same way. A Compressor takes an operation as well, saying whether to keep going (.process), to flush (.flush), or to end the stream (.finish):

var c: brotli.Compressor = .init(gpa, .{ .quality = 6 });
defer c.deinit();

var out: [4096]u8 = undefined;
while (true) {
    const r = try c.compress(input, &out, if (at_end) .finish else .process);
    input = input[r.read..];
    try sink(out[0..r.written]);
    switch (r.status) {
        .done => break, // only after .finish
        .need_input => input = try source(), // all of `input` was used
        .need_output => {}, // `out` filled up; go round again
    }
}

Decompressor.decompress(input, &out) is the same loop without the operation.

To use it from another project, fetch it and import the brotli module in build.zig:

zig fetch --save git+https://git.jcollie.dev/jeff/zig-brotli.git

const brotli = b.dependency("brotli", .{ .target = target, .optimize = optimize });
exe.root_module.addImport("brotli", brotli.module("brotli"));

The API at a glance

The names pair up, one column per direction:

	Compressing	Decompressing
Sans-I/O core	Compressor.compress	Decompressor.decompress
Into a std.Io.Writer	Compressor.compressToWriter	Decompressor.decompressToWriter
A std.Io.Reader of the result	CompressReader	DecompressReader
A std.Io.Writer to write into	CompressWriter	DecompressWriter
Reader to writer	compressStream	decompressStream
Slice to slice	compress	decompress
Slice to allocated slice	compressAlloc	decompressAlloc

Both report progress with the same Status and Result types.

Compressing

Quality runs from 0, fastest, to 11, smallest, and defaults to 6. The window runs from 1 KiB to 16 MiB (window_bits 10 to 24) and defaults to 4 MiB. A bigger window finds more copies in a long input and asks more memory of whoever decompresses it.

Input is cut into meta-blocks of 64 KiB to 256 KiB. Each is parsed into literals and backward copies by a match finder that searches harder at higher qualities: hash chains up to quality 5, and from quality 6 a binary tree of earlier positions ordered by what follows them, as LZMA and the reference compressor's top qualities use, which finds the longest matches by visiting a few dozen positions rather than walking hundreds. From quality 4 the parse looks a byte ahead before committing to a match. Copies reusing one of the four most recent distances are written with the short codes the format has for them. The higher qualities bring in the rest of what the format offers:

• The static dictionary, from quality 4. Positions are also looked up in an index of the dictionary's 13,504 words, under the 86 transforms that leave the start of a word in place: the word as it is, capitalized or in capitals, cut short, and followed by a space, punctuation, " the ", " of " and the like. Every match is checked by applying the transform and comparing, so a lookup can only ever find what is there. The index is built once, and shared by every compressor in the process.
• Context modeling for literals, from quality 4. The context mode whose 64 contexts best tell the literals apart is chosen, and their statistics are clustered into 8 to 32 codes.
• Block splitting, from quality 7. Each of a meta-block's three streams — literals, commands and distances — is divided into blocks of up to eight types, each with codes of its own, where the statistics change part way through. The types are found by clustering stretches of the stream, then refined by assigning every symbol to the type that codes it best allowing for the cost of a switch, the way the reference compressor does it. With context modeling, each block type's contexts are clustered, then the clusters of all the types.
• Optimal parsing, at quality 10 and 11. Rather than taking the best match at each position as it comes, the parse is the cheapest path through the meta-block, where every position is reachable by a literal or by a copy of any length from any candidate distance, including the recent distances along the path, and every step is priced by a model of what its symbols will cost. The model starts as a guess and is refined from the previous pass's choices, two passes at quality 10 and three at 11.

Each is used only where it pays: context modeling and block splitting are measured against not using them, header and all. A meta-block that would come out larger than its input is stored instead, so incompressible data grows by a few bytes per 64 KiB at most.

Input	This library, q3	q6	q9	q11	Reference, q5	q9	q11
80 KiB of generated English	36,810	31,713	31,395	29,855	35,097	34,985	29,876
3 MiB of generated English	1,327,091	1,195,053	1,155,830	1,091,986	1,213,949	1,161,499	1,080,054
48 KiB of audio-like samples	47,203	41,463	41,463	41,446	47,200	47,200	41,174
96 KiB of text, noise and samples	64,318	56,156	54,276	52,693	60,750	60,706	54,494

On the 3 MiB input, on one machine, quality 0 to 3 compresses at about 45 MB/s, quality 6 at about 7 MB/s, quality 9 at about 4 MB/s, and quality 11 at about 1.8 MB/s. The reference compressor takes 0.12 s at quality 5 and 3.6 s at quality 11 on the same input, against 0.28 s and 1.7 s here. zig build interop prints the full table of sizes.

The levels are this library's own and do not produce the same bytes as the reference compressor's levels of the same number.

Memory

The compressor keeps up to a window of past input to find copies in, plus the meta-block being gathered, and hash tables that grow with the quality: about 64 KiB at quality 0 and 8.5 MiB from quality 9, though never much bigger than an input compressed in one go. From quality 4 it also needs 64 KiB of working space for context modeling, and at quality 10 and 11 the optimal parse needs about 40 bytes for each byte of the meta-block, some 10 MiB. All of it is allocated as it is first needed.

Decompressing

• Decompresses every stream RFC 7932 allows: window sizes from 1 KiB to 16 MiB, uncompressed and metadata meta-blocks, all four literal context modes, block switching, context maps with run-length coding and move-to-front, and the 122,784-byte static dictionary with all 121 word transforms.
• Rejects what the RFC says to reject: padding bits that are not zero, meta-block lengths written with spare nibbles, prefix codes that are incomplete or name a symbol twice, distances that resolve to zero, and commands that write past the end of their meta-block. Each has its own error in Decompressor.Error.
• Stops at the end of the stream and leaves any bytes after it unread, so a stream embedded in a larger file ends where it should. decompressStream and DecompressReader leave them in the input reader. decompress, decompressAlloc and DecompressWriter treat them as an error (error.TrailingData).

It does not support the "large window" extension of the reference implementation (windows over 16 MiB, flagged by a header the RFC reserves), or shared dictionaries. Both are extensions to RFC 7932, not part of it.

Memory

The decompressor allocates its sliding window and the prefix code tables of the meta-block it is reading. The window starts at 64 KiB and doubles as output is produced, up to the size the stream declares, so a short stream costs little whatever window it declares. Options.max_window_bits refuses streams that declare more than you want to hold. The tables are reused from one meta-block to the next. The Decompressor value itself is about 21 KiB, most of it the literal context map. reset readies it for another stream and keeps what it has allocated.

How it works

The decompressor is a state machine with one state for each point in the format where it may have to stop. Bits are drawn from the caller's buffer into a 64-bit accumulator that lasts from one call to the next, and every read is all or nothing: if a value's bits have not all arrived, none are taken and the call returns .need_input. Decoding a prefix-coded symbol near the end of the input uses the bits that are there, so a short code is never held up waiting for bits it does not use, and a valid stream is never mistaken for a truncated one. Each read takes exactly the bits the format says are next.

Output goes into the sliding window first and is copied out to the caller's buffer from there. Until the window reaches the size the stream declares it never wraps, and it grows rather than overwrite anything that could still be referred to. After that it wraps, and it stops for .need_output before overwriting anything not yet handed over. Prefix codes are decoded through two-level lookup tables: the first eight bits of a code index a 256-entry table, and longer codes follow a link to a second table sized to the longest code under that prefix.

The compressor gathers input until it has a meta-block's worth, or is told to flush or finish, then parses the block, builds its prefix codes, and writes it into an output buffer that compress drains into the caller's. Bits left over from one meta-block carry into the next; a flush ends with an empty metadata block that carries the stream to a byte boundary. Prefix codes are length-limited Huffman codes, written with the run-length coding of code lengths the format provides, exactly as the reference compressor does.

The parts of the format that do not depend on direction are their own modules, used by both sides and exported for anyone else who wants them:

Module	What it holds
brotli.format	The constants and code tables of the format, both ways round: from a code to its lengths and from a length to its code.
brotli.context	The four literal context modes and their lookup tables.
brotli.dictionary	The static dictionary and its per-length word counts and offsets.
brotli.transform	The 121 word transforms, and apply.
brotli.prefix_code	Canonical code assignment, length-limited Huffman code lengths, and the decompressor's table builder.
brotli.stream	Status and Result.

The std.Io adapters add no buffering of their own. Each passes its input reader's buffered bytes straight to the core and has it write straight into the destination writer's buffer. Only a writer with no buffer at all is written through a small buffer on the stack.

zbrotli

zig build also installs zbrotli, a small command-line front end that compresses or decompresses standard input to standard output:

$ zbrotli -q 9 -w 24 < data > data.br
$ zbrotli -d < data.br > data

It is how zig build interop checks the library against the reference implementation, and an example of driving the library through std.Io.

Testing

$ nix develop
$ zig build test --summary all          # every test
$ zig build test -Doptimize=ReleaseFast # again without safety checks
$ zig build test --fuzz=1M              # a bounded fuzzing run
$ zig build interop                     # against the reference implementation
$ zig build coverage                    # kcov report in zig-out/coverage

The tests have several layers:

• Unit tests in each source file, including checks of the static dictionary, the context lookup tables and the transform list against the CRC-32 values RFC 7932 publishes for them, and of every table the compressor reads backwards against the decompressor reading it forwards.
• The reference implementation's synthetic streams (tests/synth.zig): 46 streams written by hand for the Brotli project to reach corners of the format no compressor produces, 18 of which a decompressor must reject. They are converted from its go/brotli/synth_test.go by tools/convert_synth.py.
• Reference compressor vectors (tests/data): 34 streams made by tools/make_vectors.py with the reference compressor, over generated text, noise, audio-like samples, zeros and mixtures, at every quality level, at window sizes from 1 KiB to 16 MiB, and in every compressor mode. Only the compressed streams are kept, with the length and SHA-256 of what each must decompress to. One of them decompresses to 17 MiB with copies that reach back almost the full 16 MiB window after it has wrapped.
• Every stream fed in pieces: whole, a byte of input and a byte of output at a time, and at awkward step sizes, so that each one stops and resumes at every point the decompressor can.
• Round trips through the compressor (tests/compress_test.zig): what the vectors decompress to, compressed at every quality and at window sizes the input overruns many times, whole and in pieces, with flushes after which everything so far must decompress, and checked against maxCompressedSize.
• The std.Io adapters (tests/io_test.zig), both directions, through a reader that hands over one byte per call, a writer with no buffer, writer buffers of several sizes, and the peeking calls of the std.Io.Reader API.
• Two fuzzers (tests/fuzz.zig): one edits streams and feeds them to the decompressor in fuzzer-chosen pieces, where a crash or a leak is a finding and an error is the expected outcome; the other builds inputs, compresses them with fuzzer-chosen options, pieces and flushes, and requires them back.
• Interoperability (zig build interop, tools/interop.py): this library's output at every quality and several window sizes decompressed by the reference implementation, and the reference implementation's output decompressed by this library, all through zbrotli.

CI runs the suite in Debug, ReleaseSafe and ReleaseFast, checks interoperability, then fuzzes, on every push.

Layout

Path	What it is
src/root.zig	The public API, and the one-call functions.
src/Compressor.zig	The sans-I/O streaming compressor and its match finder.
src/Decompressor.zig	The sans-I/O streaming decompressor.
src/CompressReader.zig, src/CompressWriter.zig, src/DecompressReader.zig, src/DecompressWriter.zig	The std.Io adapters.
src/BitReader.zig, src/BitWriter.zig	The bit streams, the reader resumable at any bit.
src/MetaBlockEncoder.zig	Choosing how a meta-block is coded, and writing it.
src/store.zig	Writing headers, prefix codes and context maps.
src/DictionaryIndex.zig	Finding static dictionary words, transformed, in the input.
src/literal_contexts.zig	Choosing a literal context mode.
src/block_split.zig, src/histogram.zig	Block splitting, and the histogram clustering it and context modeling share.
src/optimal_parse.zig	Optimal parsing.
src/prefix_code.zig	Canonical prefix codes, Huffman code lengths, and decoding tables.
src/format.zig, src/context.zig, src/dictionary.zig, src/transform.zig	The format's tables, shared by both directions.
src/dictionary.bin	The static dictionary, from RFC 7932 Appendix A.
src/stream.zig	The status and result of a streaming call.
tests/	The test vectors and the tests.
tools/zbrotli.zig	The command-line front end.
tools/interop.py	The check against the reference implementation.
tools/convert_synth.py, tools/make_vectors.py	How the test vectors were made.
tools/docs_server.zig	The server behind zig build docs-serve.

Where this lives

git clone https://git.jcollie.dev/jeff/zig-brotli.git

• https://git.jcollie.dev/jeff/zig-brotli
• https://tangled.org/jcollie.dev/zig-brotli

It is on Radicle as rad:z3K2AqnGdDK3zTVdirKbPhDB44e9. A Radicle repository can only be found by its identifier, so that is all a peer needs to fetch it:

rad clone rad:z3K2AqnGdDK3zTVdirKbPhDB44e9

License

MIT; see LICENSES/MIT.txt. The project follows the REUSE specification, so every file states its own copyright and license, either in a header or in REUSE.toml. The static dictionary and the synthetic test streams come from the Brotli reference implementation, © the Brotli Authors and Google, also under the MIT license.

References cited

• Alakuijala, J. and Z. Szabadka. Brotli Compressed Data Format. RFC 7932. Internet Engineering Task Force (IETF), July 2016. https://www.rfc-editor.org/info/rfc7932
• The Brotli Authors. Brotli, version 1.2.0. Google, 2025. The reference implementation; the source of the synthetic test streams, the compressor the test vectors were made with, and the decompressor this library's output is checked against. https://github.com/google/brotli