Files
Claude fbae955a74 std/brotli: speed up qualities 0 to 9 and the decoder
Encoder (output stays byte-exact with libbrotlienc v1.2.1):
- H58/H68 (q5-6): match the tags 8 at a time (SWAR, like
  GetMatchingTagMask's non-SSE2 code) and visit the matches with a de
  Bruijn ctz; inline the bucket entry check into the H5/H6 and H58/H68
  loops, caching the 4 bytes compared at best_len; a dedicated H58/H68
  store and hash.
- find_last_distances caches the current byte at best_len.
- ctz64 and a branch-free log2_floor_non_zero (de Bruijn tables), and
  find_match_length_with_limit uses ctz.
- load32le, load64le, peek_u16, poke_u16 and poke_u32 use one bounds
  check each.

Decoder (same output and statuses):
- The literal fast path keeps pos and the counts in local variables.
- Copies of at most 16 bytes, with a distance of at least 16, copy 16
  bytes (like the C code; the window gap keeps the extra bytes unread).

script/manual-test-brotli-float.c also checks log2_floor_non_zero (every
u32) and ctz64.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978BikvkegL2JUkqoB1e
2026-10-28 08:50:15 +00:00

1305 lines
77 KiB
Markdown

# Brotli
Brotli is a general purpose compression format, combining LZ77 style
length-distance back-references, Huffman coding, second order context modeling
and a built-in static dictionary. It is specified by [RFC
7932](https://www.rfc-editor.org/rfc/rfc7932). The reference implementation is
at [github.com/google/brotli](https://github.com/google/brotli).
This package (`std/brotli`) has a decoder and an encoder (see the "Encoder"
section below). The decoder aims for exact parity with the reference
implementation's decoder (libbrotlidec), version v1.2.1, and in
particular its `c/dec/decode.c` file: the same output for valid input and the
same verdict (and the same error code, mapped as below) for invalid input. The
Wuffs code mirrors the C code's logic and validation checks, function by
function, and comments like "Mirrors ReadHuffmanCode in decode.c" name the
corresponding C function. The C code's explicit state machine (its
`BROTLI_STATE_ETC` enums) is replaced by Wuffs coroutines.
## Format Overview
A brotli stream starts with a 1, 4 or 7 bit `WBITS` header, giving the window
size (the maximum back-reference distance, plus 16). It is followed by a
sequence of metablocks. Each metablock header gives its uncompressed length
(`MLEN`) and whether it is the last metablock. A metablock is one of:
- a metadata block, whose payload is skipped (it does not produce output),
- an uncompressed block, whose payload is byte-aligned and copied verbatim, or
- a compressed block.
A compressed metablock header defines, for each of three block categories
(literals, insert-and-copy commands and distances), the number of block types
and the prefix codes for block type switches and block lengths. It then gives
the distance parameters (`NPOSTFIX` and `NDIRECT`), the literal context modes,
the literal and distance context maps (run-length and move-to-front encoded)
and finally the groups of prefix (Huffman) codes. Each prefix code is either a
"simple" code (up to 4 symbols) or a "complex" code (code lengths that are
themselves prefix coded).
The metablock body is a sequence of commands. Each command inserts zero or more
literal bytes (decoded with a prefix code chosen by the context map, from the
previous two bytes and the current literal block type) and then copies bytes,
either from earlier in the output (an LZ77 back-reference, possibly re-using
one of the last four distances) or, for distances beyond the maximum possible
back-reference, a transformed word from the static dictionary.
The final metablock is followed by zero padding up to a byte boundary. The
decoder does not read any further than that.
## Workbuf Layout
Without the large-window quirk and without attached dictionaries (see the
"Large Window" and "Dictionaries" sections below), `workbuf_len` is `(1 << 24)
+ 542` bytes, both minimum and maximum: the largest (non-large-window) brotli
window size plus some slack. The slack
mirrors the C code's `kRingBufferWriteAheadSlack`, which its fast paths use to
write (and discard) a few bytes past the ring buffer's end. This
implementation's fast paths (see below) do not write past the ring buffer's
end, but it still reserves the slack, so that adding such fast paths later
will not change the `workbuf_len` API. A
workbuf shorter than the stream's window size plus 542 bytes is rejected with
`base."#bad workbuf length"`.
The first `(1 << WBITS)` bytes of the workbuf are the history ring buffer.
Decoded bytes are written to the ring buffer and then copied to the `dst`
`io_writer`. Before the ring buffer wraps around, all of its bytes must have
been copied to `dst`, so `transform_io` can suspend with `$short write`.
The C code's ring buffer (`s->ringbuffer_size`) can start smaller than the
window size (its "canny ring buffer allocation") and grows over successive
metablocks. The Wuffs ring buffer is always `(1 << WBITS)` bytes long, but the
decoder still tracks the C code's (virtual) ring buffer size, as it decides
when the C code calls `WriteRingBuffer`. That in turn decides whether some
invalid input (an overrun metablock) is reported as `BLOCK_LENGTH_1` or
`BLOCK_LENGTH_2`, and when the C code's `max_distance` becomes fixed.
Everything else (the Huffman tables, context maps, etc.) lives in the decoder
struct, not the workbuf. The Huffman tables use the same 8-bit root table and
second level table layout as the C code, sized per tree as the C code
allocates them.
## Status Mapping
Every `BROTLI_DECODER_ERROR_FORMAT_*` error code (and running out of input) has
a corresponding Wuffs status:
| libbrotlidec error code | Wuffs status |
| ----------------------------------------------------- | ----------------------------------------------------- |
| `BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE` | `"#bad exuberant nibble"` |
| `BROTLI_DECODER_ERROR_FORMAT_RESERVED` | `"#bad reserved bit"` |
| `BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE` | `"#bad exuberant metadata nibble"` |
| `BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET` | `"#bad simple Huffman alphabet"` |
| `BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME` | `"#bad simple Huffman symbol"` |
| `BROTLI_DECODER_ERROR_FORMAT_CL_SPACE` | `"#bad code length code lengths"` |
| `BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE` | `"#bad Huffman space"` |
| `BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT` | `"#bad context map repeat"` |
| `BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1` | `"#bad block length"` |
| `BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2` | `"#bad metablock length"` |
| `BROTLI_DECODER_ERROR_FORMAT_TRANSFORM` | `"#bad transform"` |
| `BROTLI_DECODER_ERROR_FORMAT_DICTIONARY` | `"#bad dictionary"` |
| `BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS` | `"#bad window bits"` or `"#unsupported large window"` |
| `BROTLI_DECODER_ERROR_FORMAT_PADDING_1` | `"#bad padding"` |
| `BROTLI_DECODER_ERROR_FORMAT_PADDING_2` | `"#bad final padding"` |
| `BROTLI_DECODER_ERROR_FORMAT_DISTANCE` | `"#bad distance"` |
| `BROTLI_DECODER_ERROR_FORMAT_BLOCK_SWITCH` | `"#bad block switch"` |
| `BROTLI_DECODER_ERROR_COMPOUND_DICTIONARY` | `"#bad compound dictionary"` |
| `BROTLI_DECODER_NEEDS_MORE_INPUT` (with closed `src`) | `"#truncated input"` |
Notes:
- `"#unsupported large window"` is for the large-window escape `WBITS` value
(`0010001`) when the `QUIRK_LARGE_WINDOW` quirk is not set. libbrotlidec
(with `BROTLI_DECODER_PARAM_LARGE_WINDOW` not set, the default) rejects it
with `BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS`. For standard
(non-large-window) brotli, no other `WBITS` value is invalid. With the quirk
set, `"#bad window bits"` is for a large-window header with a non-zero
reserved bit or with window bits outside of `[10 ..= 30]`.
- Like the C code, which error an overrun metablock produces (`"#bad block
length"` or `"#bad metablock length"`) can depend on how the input is split
across `transform_io` calls. When the C code runs out of input, it first
tries to flush its output (`WriteRingBuffer`) and that checks for an overrun
metablock. A Wuffs `$short read` suspension corresponds to the C code's
running out of input. With the whole input in one call, the two always
agree. With split input, there is one known difference: when the C code
runs out of input in the middle of a command's, distance's or block
switch's extra bits, it rolls back to the start of that (partially read)
item and copies the unused input bytes into an internal buffer
(`BrotliDecoderState.buffer`). On the next call, it re-reads the item from
that buffer, appending one new input byte at a time, and every time that
buffer runs dry it runs out of input again (and checks for an overrun
metablock again), at points where the Wuffs decoder just reads on. So, for
an invalid stream whose overrun happens just after such a resumption,
libbrotlidec can report `BLOCK_LENGTH_1` (`"#bad block length"`) where this
package reports `"#bad metablock length"` (`BLOCK_LENGTH_2`). Mirroring
that would need mirroring the C code's bit reader buffering (including its
fast path's prefetching, which decides how many bytes are rolled back), so
this is a deliberate deviation. For example, the 36-byte stream `09 83 04
00 00 36 e0 28 0a 61 d0 09 07 93 e3 b6 38 e4 02 00 b0 dc 1a a5 6f 3f 00 20
00 e2 b0 00 6a dd 07 00`, split after bytes 24, 25 and 30, gives
`BLOCK_LENGTH_1` from libbrotlidec v1.2.1 and `"#bad metablock length"`
here (and `BLOCK_LENGTH_2` from both when given in one piece), as checked
by `test_mimic_brotli_decode_split_block_length`. Differential fuzzing
(see `script/manual-test-brotli-fuzz.c`) found no other difference.
- `"#bad block switch"` needs more than `(1 << 24)` commands in one metablock.
It is implemented but not tested.
- The remaining libbrotlidec error codes do not apply: `DICTIONARY_NOT_SET`
(it needs a word list without data, which libbrotlidec only has when built
with `BROTLI_EXTERNAL_DICTIONARY_DATA` and not given that data),
`INVALID_ARGUMENTS`, the `ALLOC_*` codes (this decoder does not allocate)
and `UNREACHABLE`.
The `"#internal error: etc"` statuses should never happen. They are
consistency checks, generally where the C code relies on (unchecked)
invariants for memory safety but Wuffs requires explicit bounds checks.
## Differences from the C Code
- The bit reader reads input bytes only when it needs them (like the C code's
"safe" `BrotliSafeReadBits` and `SafeReadSymbol` functions), so that
`transform_io` can suspend at any point. Between reads, fewer than 8 bits
are buffered. The fast path, `process_commands_fast` (like the C code's
`ProcessCommands`, as opposed to `SafeProcessCommands`), is not a coroutine.
It reads ahead (up to 8 bytes at a time) into a 64-bit bit buffer while the
input has enough bytes, and when it returns to `process_commands` (at a
block switch, a ring buffer event, a dictionary reference or when the input
runs low), it gives back the whole bytes left in that buffer, which restores
the "fewer than 8 bits" state exactly. `process_commands` tracks where it is
within a command (`cmd_state`), so that either can pick up where the other
left off. Within `process_commands`, `read_symbol_fast` and `read_bits_fast`
(which are not coroutines either) read the same bytes at the same times as
the coroutines `read_symbol` and `read_bits`, which finish the job when the
input runs out. All paths produce the same output and errors.
- Dictionary words, and LZ77 copies that wrap around the physical ring buffer
or reach the C code's (virtual) ring buffer size, are written to the ring
buffer one byte at a time, with ring buffer events (the C code's
`WriteRingBuffer` and `WrapRingBuffer` calls) at the same positions as the
C code. Other LZ77 copies are written in chunks of at most the copy distance
(so that each chunk's source bytes are final), which is equivalent.
- On error, the Wuffs decoder may have already written more output to `dst`
than libbrotlidec would have (libbrotlidec does not flush on error), but
what both have written agrees.
## TODO
- More fast paths, for example for dictionary words, for copies that wrap
around the ring buffer and for block switches.
## Encoder
This package also has an `encoder`, which implements the `base.io_transformer`
interface. It aims for byte-exact parity with the reference implementation's
encoder (libbrotlienc), version v1.2.1: for the same parameters and the same
sequence of operations, it produces exactly the same bytes. Like the decoder,
the Wuffs code mirrors the C code function by function, with comments like
"Mirrors BrotliCompressFragmentFast in compress_fragment.c". Its floating
point arithmetic (the C code's `double`s) uses `std/softfloat`, so that the
results are bit-exact regardless of the compiler and CPU.
All qualities (0 to 11) are implemented: qualities 0 and 1 (the C code's
`FAST_ONE_PASS_COMPRESSION_QUALITY` and `FAST_TWO_PASS_COMPRESSION_QUALITY`,
implemented by `compress_fragment.c` and `compress_fragment_two_pass.c`) and
qualities 2 to 9 (the C code's `EncodeData` path: a ring buffer, hashers,
`BrotliCreateBackwardReferences` with static dictionary matching, and
`WriteMetaBlockInternal`, which picks `BrotliStoreMetaBlockFast` at quality
2, `BrotliStoreMetaBlockTrivial` at quality 3 and, at qualities 4 to 9, the
literal context modeling heuristics, `BrotliBuildMetaBlockGreedy`,
`BrotliOptimizeHistograms` and `BrotliStoreMetaBlock`) and qualities 10 and
11 (the default is 11: the same `EncodeData` path with the H10 binary tree
hasher, `BrotliCreateZopfliBackwardReferences` at quality 10 and
`BrotliCreateHqZopfliBackwardReferences` at quality 11, and then
`ChooseContextMode`, `BrotliBuildMetaBlock`, `BrotliOptimizeHistograms` and
`BrotliStoreMetaBlock`). Large-window brotli (see "Encoder Large Window"
below) works at qualities 3 to 11 with lgwin 10 to 30. Like the C code,
qualities 0 to 2 ignore the large-window quirk.
Raw (LZ77 prefix) dictionaries (see "Encoder Dictionaries" below) work at
all qualities, and, like the C code, qualities 0 and 1 ignore them.
The source files are:
- `encode_brotli.wuffs`: the `encoder` struct, its public methods and the
`encode.c` streaming logic (`BrotliEncoderCompressStream`,
`BrotliEncoderCompressStreamFast`, `ProcessMetadata`, `EnsureInitialized`,
`InjectBytePaddingBlock`, etc).
- `encode_quirks.wuffs`: the encoder's quirk keys.
- `encode_bit_writer.wuffs`: `write_bits.h`, `fast_log.h`,
`find_match_length.h` and small `brotli_bit_stream.c` helpers.
- `encode_entropy.wuffs`: `entropy_encode.c` (Huffman tree construction) and
the `brotli_bit_stream.c` functions that store Huffman codes.
- `encode_fragment_fast.wuffs`: `compress_fragment.c` (quality 0).
- `encode_fragment_two_pass.wuffs`: `compress_fragment_two_pass.c` (quality
1).
- `encode_bit_cost.wuffs`: `bit_cost.c`, `bit_cost_inc.h` and `fast_log.h`
(`BrotliBitsEntropy`, `BrotliPopulationCost{Literal,Command,Distance}`), as
methods of the `bit_cost` struct.
- `encode_histogram.wuffs`: `histogram.h`, `histogram_inc.h` and
`histogram.c` (histogram helpers and `BrotliBuildHistogramsWithContext`),
also as `bit_cost` methods.
- `encode_data.wuffs`: the rest of `encode.c` that qualities 2 to 11 use
(`EncodeData`, `WriteMetaBlockInternal`, `ShouldCompress`,
`DecideOverLiteralContextModeling`, `ChooseContextMap`, `UpdateSizeHint`,
`ExtendLastCommand`, etc), `ringbuffer.h`, the `quality.h` helpers and the
workbuf layout.
- `encode_hasher.wuffs`: `hash.h` and the `hash_*_inc.h` hashers (H2, H3, H4,
H54, H5, H6, H58, H68, H40, H41 and H42) and `SearchInStaticDictionary`
(with `static_dict.c`'s matching), as one set of functions selected by the
hasher type at run time.
- `encode_hasher_composite.wuffs`: the large-window hashers:
`hash_composite_inc.h` (H35, H55 and H65, which combine H3, H54 or H6 with
a rolling hasher) and `hash_rolling_inc.h` (`HROLLING_FAST` and
`HROLLING`).
- `encode_dictionary.wuffs`: `compound_dictionary.c`
(`CreatePreparedDictionary`, `AttachPreparedDictionary`), the raw
dictionary cases of `BrotliEncoderPrepareDictionary` and
`BrotliEncoderAttachPreparedDictionary` (as `add_dictionary`), the
compound dictionary search of `hash.h` (`FindCompoundDictionaryMatch`,
`LookupCompoundDictionaryMatch`) and the compound dictionary branch of
`ExtendLastCommand`.
- `encode_backward_references.wuffs`: `backward_references.c` and
`backward_references_inc.h` (`BrotliCreateBackwardReferences`),
`command.h` and `ComputeDistanceCode`.
- `encode_bit_stream.wuffs`: `brotli_bit_stream.c` (`StoreMetaBlockHeader`,
`BrotliStoreUncompressedMetaBlock`, `BrotliStoreMetaBlockTrivial`,
`BrotliStoreMetaBlockFast`, `BrotliStoreMetaBlock`, block split codes,
`EncodeContextMap` with move-to-front and run-length coding,
`BuildAndStoreEntropyCodes`, etc).
- `encode_hash_to_binary_tree.wuffs`: `hash_to_binary_tree_inc.h` (the H10
hasher of qualities 10 and 11, including `StoreRange`,
`StitchToPreviousBlock` and `FindAllMatches`).
- `encode_static_dict.wuffs`: `static_dict.c`'s
`BrotliFindAllStaticDictionaryMatches` (every transform), with the
`static_dict_lut.h` tables.
- `encode_literal_cost.wuffs`: `literal_cost.c`
(`BrotliEstimateBitCostsForLiterals`, with `utf8_util.c`'s
`BrotliIsMostlyUTF8`), in f32 arithmetic via `std/softfloat`.
- `encode_zopfli.wuffs`: `backward_references_hq.c` (the `ZopfliNode` array,
`ZopfliCostModel`, `StartPosQueue`, `UpdateNodes`,
`ZopfliComputeShortestPath`, `ZopfliCreateCommands`,
`BrotliCreateZopfliBackwardReferences` and
`BrotliCreateHqZopfliBackwardReferences`), with the C code's f32 costs as
binary32 bit patterns.
- `encode_store_hq.wuffs`: the quality 10 and 11 parts of
`WriteMetaBlockInternal` (`ChooseContextMode`, the `metablock_builder` call
and `BrotliStoreMetaBlock` with any literal context mode and context maps)
and the quality 10 and 11 workbuf sizing.
- `encode_metablock_greedy.wuffs`: `BrotliBuildMetaBlockGreedy` (and its
greedy block splitters, `metablock_inc.h`) and `BrotliOptimizeHistograms`
for its output.
- `encode_util.wuffs`: little-endian workbuf accessors.
- `encode_block_splitter.wuffs`: `block_splitter.c` and
`block_splitter_inc.h` (`BrotliSplitBlock`), as methods of the
`metablock_builder` struct.
- `encode_cluster.wuffs`: `cluster.c` and `cluster_inc.h`
(`BrotliClusterHistograms` and its helpers), also as `metablock_builder`
methods.
- `encode_metablock.wuffs`: the `metablock_builder` struct and `metablock.c`
(`BrotliInitDistanceParams`, `BrotliBuildMetaBlock`,
`BrotliOptimizeHistograms`). See "Encoder Metablock Builder" below.
Only qualities 10 and 11 use `BrotliBuildMetaBlock` (lower qualities use
some of the smaller functions: `BrotliInitDistanceParams`,
`PrefixEncodeCopyDistance`, `CommandRestoreDistanceCode` and
`BrotliOptimizeHuffmanCountsForRle`).
- `encode_tester.wuffs`: TEST ONLY. The `metablock_tester` struct exposes
the internal functions above to C test programs. It is not part of the
encoder API.
- `common_encoder_tables.wuffs`: tables generated by `go run
script/print-brotli-tables.go -encoder` from the C code (including the
static dictionary hash tables of `dictionary_hash.c` and the
`static_dict_lut.h` buckets and words).
### Encoder API
In addition to the `base.io_transformer` methods, the encoder has:
- `request_flush!() status`: the next `transform_io` call acts like the C
code's `BROTLI_OPERATION_FLUSH` (instead of `PROCESS` or `FINISH`) until
the flush is complete. It returns `"#bad call sequence"` while a metadata
request is pending.
- `request_emit_metadata!(length: u64) status`: the next `transform_io` call
acts like `BROTLI_OPERATION_EMIT_METADATA`, with the next `length` bytes of
`src` as the metadata block's contents. `length` can be at most `1 << 24`
(otherwise `"#bad argument"`). It returns `"#bad call sequence"` while
another request is pending.
- `max_compressed_size(input_size: u64) u64`: mirrors
`BrotliEncoderMaxCompressedSize` (0 means overflow).
- `add_dictionary!(dict_type: u32, dict: roslice u8, workbuf: slice u8)
status` and `add_dictionary_workbuf_len(dict_len: u64) u64`: attach a raw
dictionary, like `BrotliEncoderPrepareDictionary` plus
`BrotliEncoderAttachPreparedDictionary`. See "Encoder Dictionaries" below.
`dst_history_retain_length` is 0: the encoder never re-reads `dst`.
### Encoder Quirks
Each quirk mirrors one `BrotliEncoderParameter`, with the value semantics of
`BrotliEncoderSetParameter`. Values are stored as is (and must fit in a u32,
otherwise `set_quirk` returns `"#bad argument"`). Like the C code, they are
sanitized (`SanitizeParams`, `ComputeLgBlock`, `ChooseDistanceParams`) at the
first `transform_io` call, after which `set_quirk` returns
`"#bad call sequence"`. Quirks and dictionaries (`add_dictionary`) can be set
in any order before that first call.
| Quirk | C parameter |
| ---------------------------------------- | ---------------------------------------------- |
| `QUIRK_ENCODER_QUALITY` | `BROTLI_PARAM_QUALITY` (default 11) |
| `QUIRK_LGWIN` | `BROTLI_PARAM_LGWIN` (default 22) |
| `QUIRK_LGBLOCK` | `BROTLI_PARAM_LGBLOCK` |
| `QUIRK_MODE` | `BROTLI_PARAM_MODE` |
| `QUIRK_DISABLE_LITERAL_CONTEXT_MODELING` | `BROTLI_PARAM_DISABLE_LITERAL_CONTEXT_MODELING` (0 or 1) |
| `QUIRK_SIZE_HINT` | `BROTLI_PARAM_SIZE_HINT` |
| `QUIRK_LARGE_WINDOW` (shared with the decoder) | `BROTLI_PARAM_LARGE_WINDOW` (0 or 1) |
| `QUIRK_NPOSTFIX` | `BROTLI_PARAM_NPOSTFIX` |
| `QUIRK_NDIRECT` | `BROTLI_PARAM_NDIRECT` |
| `QUIRK_STREAM_OFFSET` | `BROTLI_PARAM_STREAM_OFFSET` (at most `1 << 30`) |
The quality quirk is not named `QUIRK_QUALITY` because that name would clash
with `base.QUIRK_QUALITY`. At qualities 0 and 1, only the quality, lgwin and
stream offset affect the output (lgblock, mode, size hint, large window,
npostfix, ndirect and literal context modeling are stored, sanitized and then
ignored, as in the C code). At qualities 2 to 9, they have the same effect as
in the C code: large window (see "Encoder Large Window" below), lgblock (at
qualities 4 and above; the C code's
`ComputeLgBlock` fixes it to 14 below that), npostfix, ndirect and the mode
(only `BROTLI_MODE_FONT` matters, through `ChooseDistanceParams`, at
qualities 4 and above), disabling literal context modeling (at qualities 5
and above) and the size hint (the hasher choice at qualities 4 and above and
the complex static context map at qualities 5 and above). An unset (zero)
size hint is replaced by the C code's `UpdateSizeHint` estimate.
### Encoder Workbuf Layout
Any attached dictionaries come first (see "Encoder Dictionaries" below): the
workbuf's first `D` bytes hold them (with their prepared hash tables) and
everything described in this section starts at offset `D` (so all of the
offsets and lengths below are relative to `workbuf[D ..]`, and `workbuf_len`
is `D` more than the lengths given here). `D` is 0 without dictionaries.
At qualities 0 and 1, the workbuf is the C code's metablock storage (its
`GetBrotliStorage` buffer): `workbuf_len` is `(2 << lgwin) + 503 + 16` bytes
(the storage for a `1 << lgwin` byte block plus 16 bytes of slack for 8-byte
bit writes), where lgwin is the sanitized value. A shorter workbuf still works
if every input block is shorter: a block of `n` bytes needs `(2 * n) + 519`
bytes, otherwise `transform_io` returns `"#bad workbuf length"`.
At qualities 2 to 9, the workbuf holds everything whose size depends on the
input or on the parameters, in this order (see `compute_layout_offset` in
`encode_data.wuffs`). Here `rb_bits` is `1 + max(lgwin, lgblock)` (the C
code's `ComputeRbBits`), `max_len` is `1 << min(rb_bits, 24)` (the C code's
`MaxMetablockSize`) and `cmds_cap` is the commands capacity (see below):
1. The metablock storage: `(2 * max_len) + 503 + 16` bytes, like at
qualities 0 and 1 but for the largest metablock.
2. The hasher's memory (the C code's `common->extra[0 .. 3]`): the sum of
`FN(HashMemAllocInBytes)` for the hasher that `ChooseHasher` picks. When
the size hint quirk is unset (zero), that choice depends on the input's
length (through `UpdateSizeHint`), so this is the larger of the two
possible choices (for a size hint below or at least 1 MiB). With lgwin
above 24 (large window), the composite hashers H35, H55 and H65 add their
rolling hasher's table (`(1 << 24)` u32le values, 64 MiB) after H3's,
H54's or H6's memory.
3. The commands: `16 * cmds_cap` bytes, in the C struct order: `insert_len_`
(u32le), `copy_len_` (u32le, the copy length in the low 25 bits and
`copy_code - copy_len` in the high 7 bits), `dist_extra_` (u32le),
`cmd_prefix_` (u16le) and `dist_prefix_` (u16le). `cmds_cap` is
`min(prior + ((1 << lgblock) / 2) + 1, (max_len / 2) + 1)`, where `prior`
is `(max_len / 8) - 1` (and at most `MAX_NUM_DELAYED_SYMBOLS - 1`, which
is `0x2FFE`, below quality 4): `EncodeData` keeps (merges with the next
input block) fewer than that many commands and, like the C code's
`num_commands_ + bytes / 2 + 1` allocation, each input block of `n` bytes
adds at most `(n / 2) + 1` commands.
4. At qualities 4 and above, `BrotliBuildMetaBlockGreedy`'s `MetaBlockSplit`
and `BrotliStoreMetaBlock`'s scratch space:
- the block types (u8) and then the block lengths (u32le) of the literal,
command and distance block splits, with room for `(max_len / 512) + 1`,
`(cmds_cap / 1024) + 1` and `(cmds_cap / 512) + 1` blocks (the C
code's `max_num_blocks`, given that a metablock has at most `max_len`
literals and `cmds_cap` commands),
- the histograms (u32le counts, without the C code's `total_count_` and
`bit_cost_` fields, which are not needed here): up to 260 literal
histograms (`(256 / 13) + 1` block types of 13 contexts), 257 command
histograms and 257 distance histograms of 256, 704 and 544 counts,
- the block splitters' `combined_histo` (2 * 13 * 256 u32le counts),
- the literal context map (256 * 64 bytes),
- `EncodeContextMap`'s `rle_symbols` (256 * 64 u32le values) and
- the block encoders' depths (u8) and then bits (u16le) for up to 256
histograms per category.
5. The ring buffer (the C code's `RingBuffer.buffer_`): `2 + (1 << rb_bits) +
(1 << lgblock) + 7` bytes. The first 2 bytes are the copy of the last two
bytes that precede `data_`, the tail (`1 << lgblock` bytes) mirrors the
start of the buffer and the 7 trailing bytes are the C code's slack for
8-byte loads.
Unlike the C code, which allocates its storage, ring buffer and command
buffers as it goes (for the actual metablock and block sizes, and the actual
input length), `workbuf_len` is the worst case for the sanitized parameters,
so that one workbuf works for any input. A shorter workbuf still works for
short inputs, because the ring buffer is the last region and the encoder
only touches its first `2 + n + 7` bytes for an input of `n` bytes, as long
as the ring buffer never wraps around. Precisely, at qualities 2 to 11
(where, at qualities 10 and 11, `workbuf_len` means its `min_incl`):
- `transform_io` returns `"#bad workbuf length"` if the workbuf is shorter
than `workbuf_len - R + 18`, where `R` is the ring buffer region's length
(`2 + (1 << rb_bits) + (1 << lgblock) + 7`), i.e. if it does not reach 16
bytes into the ring buffer's data.
- If any `transform_io` call gets a workbuf shorter than `workbuf_len`, then
from then on (for the rest of the stream), before copying input into the
ring buffer, `transform_io` returns `"#bad workbuf length"` (without
consuming that input) if the total input so far (not counting metadata)
would be `n` bytes with `n + 16 > (1 << rb_bits)` (the ring buffer would
wrap, or its tail would be needed) or with the workbuf shorter than
`workbuf_len - R + 2 + n + 16`.
So, for a total input of `n` bytes with `n + 16 <= (1 << rb_bits)`, a
workbuf of `workbuf_len - R + n + 18` bytes produces the same output as one
of `workbuf_len` bytes. The parity test checks this with exactly that length
(and that one byte less fails). This matters most for large-window brotli,
whose ring buffer is up to 2 GiB. Some examples of `workbuf_len` (in MiB,
with the default lgblock and an unset size hint):
| quality | lgwin 10 | lgwin 16 | lgwin 18 | lgwin 22 | lgwin 24 |
| ------- | -------- | -------- | -------- | -------- | -------- |
| 0, 1 | 0.0 | 0.1 | 0.5 | 8.0 | 32.0 |
| 2, 3 | 0.5 | 1.0 | 2.1 | 24.6 | 64.6 |
| 4 | 7.9 | 7.9 | 9.8 | 47.3 | 103.4 |
| 5 | 4.4 | 4.4 | 7.0 | 45.9 | 102.0 |
| 7 | 4.4 | 4.4 | 13.8 | 51.4 | 107.5 |
| 9 | 5.1 | 5.1 | 39.5 | 77.1 | 133.2 |
With the large-window quirk (at qualities 3 and above; lgwin up to 24 gives
the same numbers as without it), larger lgwin values double the ring buffer
for each extra bit, and lgwin above 24 adds the composite hashers' 64 MiB
rolling hash table (at quality 4 and at qualities 5 to 9 with lgwin of at
least 19, only for a size hint of at least 1 MiB, or an unset one, as
`ChooseHasher` otherwise keeps H3, H5 or H58):
| quality | lgwin 25 | lgwin 26 | lgwin 28 | lgwin 30 |
| ------- | -------- | -------- | -------- | -------- |
| 3 | 160.6 | 224.6 | 608.6 | 2144.6 |
| 4 | 199.4 | 263.4 | 647.4 | 2183.4 |
| 5 | 197.5 | 261.5 | 645.5 | 2181.5 |
| 7 | 203.5 | 267.5 | 651.5 | 2187.5 |
| 9 | 229.2 | 293.2 | 677.2 | 2213.2 |
At qualities 10 and 11, `workbuf_len` is a range instead (see the next
section).
Fixed-size state (the hash table and command and literal buffers of
qualities 0 and 1, the Huffman scratch space, the greedy block splitters'
state, the block encoders' block type and length codes, etc) lives in the `encoder` struct (which is therefore
about 2.5 MiB). It does not need zero-initializing:
`WUFFS_INITIALIZE__LEAVE_INTERNAL_BUFFERS_UNINITIALIZED` is fine. At
qualities 0 and 1, the input block is not copied: the encoder compresses
directly from `src`. At qualities 2 to 9, like the C code, the input is
copied into the ring buffer.
### Qualities 10 and 11 Workbuf Length
At qualities 10 and 11, the workbuf has the same regions as at quality 9
(with `cmds_cap` computed the same way), except that:
- region 2 is the H10 hasher: `4 << 17` bytes of buckets (u32le) and then
the binary tree forest (`8 << lgwin` bytes, u32le),
- region 4 keeps only the literal context map, `rle_symbols` and the block
encoders' depths and bits, followed by a variable region, and
- the ring buffer (region 5) is still the last region, after the variable
region.
The variable region's length is set at the first `transform_io` call: it is
its minimum length (see below) plus however much of the workbuf beyond
`workbuf_len().min_incl` there is (up to the worst case), and the ring
buffer moves along with it. Later `transform_io` calls should pass a
workbuf of the same length. A workbuf shorter than `min_incl` follows the
short workbuf rules above (with the minimum variable region).
The variable region holds, at different times, the Zopfli scratch space
(while `EncodeData` computes the backward references: `(n + 1)` 16-byte
`ZopfliNode`s, `(n + 2)` f32 literal costs and, at quality 10, room for one
position's matches or, at quality 11, `n` u32 match counts followed by the
8-byte `BackwardMatch`es of the whole input block, for an input block of `n`
bytes) and then the `metablock_builder`'s workbuf (see "Encoder Metablock
Builder" below), whose results the metablock store then reads.
The C code allocates these as it goes, for the actual input, and their worst
cases are huge (see `workbuf_len_worst_case` below), so `workbuf_len` returns
a range whose `max_incl` is the C code's worst case for the sanitized
parameters (saturating at `0xFFFF_FFFF_FFFF_FFFF`) and whose `min_incl` is a
practical bound. Both have the same fixed regions, with a variable region of
`max(Z, M)` bytes, where `L` is the most literals that a metablock
can hold (`min(max_len, (max_len / 8) + (1 << lgblock))`, since `EncodeData`
merges another input block only while there are fewer than `max_len / 8`
literals) and:
- `Z` is the Zopfli scratch space for `n = 1 << lgblock` bytes, with up to
100 `BackwardMatch`es per byte (`max_incl`: up to 2 from the short
distance scan, 64 from the binary tree and 34 from the static dictionary)
or 16 per byte (`min_incl`), and
- `M` is the `metablock_builder`'s `workbuf_len_worst_case(L, cmds_cap)`
(`max_incl`) or `workbuf_len_practical(L, cmds_cap)` (`min_incl`).
With raw dictionaries attached (see "Encoder Dictionaries" below), both
`min_incl` and `max_incl` also include the dictionaries' `D` bytes, and, at
quality 11, `Z` has room for 256 more `BackwardMatch`es (the C code's
`shadow_matches` in `BrotliCreateHqZopfliBackwardReferences`: scratch space
past the current position's matches, where the binary tree's and the
compound dictionary's matches are found before `MergeMatches` merges them)
and, for `max_incl`, up to 164 `BackwardMatch`es per byte (64 more, the
C code's `match_limit`, from the compound dictionary). At quality 10, the
C code's matches buffer (`2 * (MAX_NUM_MATCHES_H10 + 64)` entries, for one
position) already has room for its `lz_matches_offset` of
`MAX_NUM_MATCHES_H10 + 128`, so `Z` is unchanged. In practice `M` is the
larger of the two, so only `D` changes the table below.
`workbuf_len_practical` is `workbuf_len_worst_case` with these caps:
`FindBlocks` makes at most `(k / 16) + 1` blocks for `k` literals, commands
or distances (instead of one block per symbol), `ClusterBlocks`' first phase
makes at most `(k / 64) + 64` clusters and there are at most that many (and
at most 256) block types. Over 142 files from `test/data` (including
`harvesters.bmp`, 3 MiB, and other images, text, JSON and binaries) and some
synthetic inputs, at qualities 10 and 11 and lgwins 16 and 24, the C
algorithm's actual maxima were one block per 83 literals (per 85 commands,
per 154 distances), one first-phase cluster per 286 literals (per 915
commands) and about 7.4 `BackwardMatch`es per byte (for random text over a
2-letter alphabet; at most 2.3 for the files), so the caps have a margin of
at least 4x. The largest `metablock_builder` workbuf used was 43.7 MB, for
2.1 MiB of literals.
This is one documented deviation from the C code: with a workbuf of at least
`min_incl` but less than `max_incl` bytes, an input that needs more than the
variable region holds makes `transform_io` return `"#bad workbuf length"`
(where the C code would allocate more memory). A workbuf of `max_incl` bytes
never fails. In MiB (with the default lgblock, which is
`min(18, lgwin)` for lgwin above 16 and 16 otherwise), `min_incl` and
`max_incl` are:
| quality | lgwin 10 | lgwin 16 | lgwin 18 | lgwin 22 | lgwin 24 |
| ------- | ------------- | ------------- | ------------- | -------------- | -------------- |
| 10 | 91.7 .. 288.0 | 92.2 .. 288.5 | 128.7 .. 914.2 | 403.0 .. 5116.1 | 775.5 .. 9678.1 |
| 11 | 91.7 .. 288.0 | 92.2 .. 288.5 | 128.7 .. 914.2 | 403.0 .. 5116.1 | 775.5 .. 9678.1 |
(Quality 11's extra `BackwardMatch` storage fits in the space that the
`metablock_builder` needs anyway, so the two rows are equal. With lgblock
24, `min_incl` is about 2.1 GiB at quality 10 and 2.6 GiB at quality 11.)
At qualities 10 and 11, every command's distance code is less than `1 <<
25` (distances are at most `(1 << lgwin) - 16` or, for static dictionary
words, at most the C code's `max_distance` check in `FindAllMatchesH10` and
less than `(1 << 24) + (1 << 17)`, plus 15 for the distance code), which
satisfies the `metablock_builder`'s precondition (distance codes at most the
distance params' `max_distance`, which is at least `(1 << 26) - 4` without
large-window brotli). With raw dictionaries attached, the static dictionary
words start `gap` further away and compound dictionary matches can be
further away too, but explicit distances are still at most `max_distance`
(`FindAllMatchesH10` and `FindAllCompoundDictionaryMatches` skip longer
ones, and distance cache hits use short distance codes), as in the C code.
### Encoder Operation Mapping
Each `transform_io` call (initial or resumed) corresponds to one or more
`BrotliEncoderCompressStream` calls, with `src`'s readable bytes as the C
code's `available_in` and `dst`'s writable bytes as `available_out`. The
operation is:
- `EMIT_METADATA` if `request_emit_metadata` is pending (until the metadata
block is complete),
- otherwise `FLUSH` if `request_flush` is pending (until the flush is
complete),
- otherwise `FINISH` if `src` is closed,
- otherwise `PROCESS`.
`transform_io` suspends with `"$short write"` when there is pending output
(the C code's `BrotliEncoderHasMoreOutput`) but `dst` is full, suspends with
`"$short read"` when all of `src` is consumed (and, for a flush, the flush is
complete) and returns ok once the stream is finished (the C code's
`BrotliEncoderIsFinished`). So these two loops produce the same bytes:
- C: for each chunk, call `BrotliEncoderCompressStream(op)` until all of the
chunk is consumed and there is no more output (or, for `FINISH`, until
finished).
- Wuffs: for each chunk, call `request_flush` (for `FLUSH`) or
`request_emit_metadata(len)` (for `EMIT_METADATA`), make `src` hold exactly
that chunk (closed for `FINISH`) and call `transform_io` until it returns
`"$short read"` (or ok for `FINISH`), giving it more `dst` room after each
`"$short write"`.
At qualities 0 and 1 the C code compresses each call's available input
immediately (in blocks of at most `1 << lgwin` bytes), so the output depends
on how the input is split into chunks. The test programs' encode drivers
(`wuffs_brotli_encode_plan` in `test/c/std/brotli.c` and
`mimic_brotli_encode` in `test/c/mimiclib/brotli.c`) run the same "plan" of
(operation, length) steps with each library.
At qualities 2 to 9 the C code copies the input into its ring buffer and
only compresses it (`EncodeData`) when an input block (`1 << lgblock` bytes)
is full, or on a flush or finish, so the output depends on the chunking only
through the flushes (and the `UpdateSizeHint` estimate, which depends on how
much input is available when the first block is compressed). The Wuffs
encoder makes the same `EncodeData` calls, at the same points. One
`transform_io` call can correspond to several C calls: with a stream offset
(the C code's "flint"), a C call can return early, with input left, after
emitting the flint, and its callers then call it again.
The C code emits the flint with a forced flush. If `dst` fills up before that
flush's output is all written, the C call returns with the stream still in
the flush-requested state, and the next `BrotliEncoderCompressStream` call
that has input fails (it requires `stream_state_ == BROTLI_STREAM_PROCESSING`
when `*available_in != 0`). The Wuffs encoder mirrors this: `transform_io`
returns `"#bad call sequence"` there, after writing the same bytes as the C
code. The differential fuzzer (`script/manual-test-brotli-fuzz.c -enc`)
checks that both encoders fail at the same point with equal output.
One libbrotlienc bug is not mirrored. When `ProcessMetadata` has no room in
`dst` for a metadata block's body, it copies up to 16 bytes into `tiny_buf_`
and points `next_out_` at it. Pushing those out leaves `next_out_` just past
`tiny_buf_` (at `remaining_metadata_bytes_`), and nothing resets it when the
metadata block ends. At qualities 0 and 1, `BrotliEncoderCompressStreamFast`
compresses into the caller's buffer without touching `next_out_`, so a later
flush's `InjectBytePaddingBlock` writes its padding bits through the stale
pointer, over `remaining_metadata_bytes_`. The bytes written are still right,
but every later `BrotliEncoderCompressStream` call fails, as if a metadata
block were in progress. The Wuffs encoder writes the same bytes and carries
on, which is what libbrotlienc does once `ProcessMetadata` sets `next_out_` to
`NULL` when the metadata block ends. The
`test_mimic_brotli_encode_metadata_stale_pointer` test in
`test/c/std/brotli.c` shows it at quality 1.
Neither encoder's output is fully determined by its input and parameters.
libbrotlienc's `RingBufferWrite` allocates only the first write's bytes when
that write is shorter than the ring buffer's tail, and when it later grows the
buffer it copies them but leaves the tail (the copy of the buffer's start,
past its end) uninitialized. Match finding near the ring buffer's end can read
those bytes, so the output can depend on what that `malloc`'d memory held. The
Wuffs encoder reads the corresponding `workbuf` bytes, which the caller need
not initialize. Given the same memory contents (e.g. zeroed), both produce
the same bytes, and both outputs decode correctly.
### Encoder Large Window
The `QUIRK_LARGE_WINDOW` quirk mirrors `BROTLI_PARAM_LARGE_WINDOW`
(large-window brotli is an incompatible extension of RFC 7932, decodable by
this package's decoder with the same quirk, see "Large Window" above, and by
libbrotlidec with `BROTLI_DECODER_PARAM_LARGE_WINDOW`). Like the C code's
`SanitizeParams`, `EnsureInitialized` and `ChooseHasher`:
- At qualities 0 to 2 (the C code's `MAX_QUALITY_FOR_STATIC_ENTROPY_CODES`
and below), the quirk is ignored: lgwin is clamped to 24 and the output is
standard brotli.
- At qualities 3 and above, lgwin is clamped to `[10 ..= 30]` (instead of
`[10 ..= 24]`) and the stream starts with the 14-bit large-window header
(`EncodeWindowBits`), even for lgwin 24 and below. The distance parameters
(`BrotliInitDistanceParams` with `large_window`) allow distances up to
`BROTLI_MAX_ALLOWED_DISTANCE` with an alphabet of up to
`BROTLI_LARGE_MAX_DISTANCE_BITS` (62) distance bits, so the distance
Huffman codes are stored with a larger alphabet size than without the
quirk, even when no distance is large. Backward distances are at most
`(1 << lgwin) - 16`, so their extra bits (at most 30) fit in a command's
32-bit `dist_extra_`, as in the C code.
- lgwin above 24 changes the hasher (only at qualities 3 to 9; the C code's
qualities 10 and 11 use H10 regardless): H3 becomes H35 (H3 plus
`HROLLING_FAST`), H54 becomes H55 (H54 plus `HROLLING_FAST`) and H6 and
H68 become H65 (H6, not H68, plus `HROLLING`). H5, H58 and H40 to H42 stay
as they are, so qualities 5 to 9 only use H65 when the size hint (set or
estimated by `UpdateSizeHint`) is at least 1 MiB (and lgwin is at least 19,
which it is). The rolling hashers find matches of at least 32 bytes at any
distance in the window (`HROLLING_FAST` only at positions and distances
that are multiples of 4) and do not search the static dictionary.
- lgblock is unaffected (it is at most 24), but `rb_bits` (and so the ring
buffer) grows with lgwin. Metablocks are still at most `1 << 24` bytes.
- At qualities 10 and 11, the H10 hasher's binary tree forest grows with
lgwin (`8 << lgwin` bytes, so 8 GiB at lgwin 30, as in the C code, which
allocates the same), and the Zopfli and static dictionary distance limits
use the large-window `max_distance`.
Positions (the C code's `size_t` and the `WrapPosition`'ed `uint32_t`
values) and distances are `base.u64` throughout the encoder, so nothing is
truncated for windows up to `1 << 30`. The rolling hashers' table holds
32-bit positions, like the C code's.
### Encoder Dictionaries
`encoder.add_dictionary!(dict_type: base.u32, dict: roslice base.u8, workbuf:
slice base.u8) base.status` mirrors the C API's
`BrotliEncoderPrepareDictionary(BROTLI_SHARED_DICTIONARY_RAW, ...)`
followed by `BrotliEncoderAttachPreparedDictionary`: it attaches a raw (LZ77
prefix) dictionary, as the next chunk of the C code's compound dictionary.
The decoder must be given the same dictionaries, in the same order (with
this package's `decoder.add_dictionary` or libbrotlidec's
`BrotliDecoderAttachDictionary`, as `DICTIONARY_TYPE_RAW` /
`BROTLI_SHARED_DICTIONARY_RAW`).
Ordering: like quirks, dictionaries must be added before the first
`transform_io` call (the C API's "before the first
`BrotliEncoderCompressStream`"). Quirks and dictionaries can be set in any
order (preparing a raw dictionary does not depend on any parameter: the
`quality` argument of `BrotliEncoderPrepareDictionary` is unused for raw
dictionaries). Call `workbuf_len` after the last `add_dictionary` and
`set_quirk` call.
Like the decoder, the encoder copies each dictionary into the workbuf, so
every `add_dictionary` and `transform_io` call must be passed the same
workbuf (or at least one whose first bytes hold the same contents). Each
dictionary is followed by its prepared hash tables (the C code's
`PreparedDictionary`), which `add_dictionary` builds exactly like
`CreatePreparedDictionary` and `CreatePreparedDictionaryWithParams` in
`compound_dictionary.c`, so that the compound dictionary search finds the
same candidates in the same order:
- The hash table size depends only on the dictionary length `n`: 17 bucket
bits and 7 slot bits for `n` up to 2 MiB, one more of each for each
doubling of `n` (18 and 8 up to 4 MiB, etc), up to 22 and 12 (for more than
32 MiB). Each position `i` with `i + 7 < n` is hashed (the low 40 bits of
its 8 little-endian bytes, times `kPreparedDictionaryHashMul64Long`), with
at most 32 positions per bucket (the most recent ones), and the bucket
limits are lowered per slot so that each slot has fewer than 65535 items.
- Its layout, after the `n` dictionary bytes, is `slot_offsets` (`1 <<
slot_bits` u32le values), `heads` (`1 << bucket_bits` u16le values, 0xFFFF
for an empty bucket) and `items` (`num_items` u32le values, each a
dictionary position, with the high bit marking the end of a bucket's
chain), like the C struct's dynamic members.
So the workbuf layout is:
[0 .. D) the dictionaries, each one being its n bytes, then
(4 << slot_bits) + (2 << bucket_bits) + (4 * num_items)
bytes of hash tables. num_items is at most max(0, n - 7).
[D .. ) the encoder's other regions (see "Encoder Workbuf Layout").
Preparing a dictionary needs some scratch space (the C code's temporary
"bloated" hasher: `(6 << bucket_bits) + (4 * n)` bytes), which `add_dictionary`
puts after the largest possible hash tables. So `add_dictionary`'s workbuf
must be at least `add_dictionary_workbuf_len(n)` bytes long: `D` (for the
dictionaries added so far) plus `n + (4 << slot_bits) + (2 << bucket_bits) +
(4 * max(0, n - 7))` plus that scratch space. For example, for a 1 MiB
dictionary that is `D` plus about 9.8 MiB, and for a 40 MiB dictionary `D`
plus about 384 MiB. After the call, `D` grows by the dictionary's bytes and
actual hash tables (e.g. by at most 5.3 MiB for 1 MiB of dictionary).
The compound dictionary then affects compression like in the C code:
- Qualities 0 and 1 (`BrotliEncoderCompressStreamFast`) ignore it.
- At qualities 2 to 9, its total size (the C code's `gap`) is added to the
static dictionary's base distance (`dictionary_start + gap` in
`CreateBackwardReferences`), and distances up to `dictionary_start + gap`
(which include compound dictionary references) update the distance cache.
`ExtendLastCommand` can extend a copy from the compound dictionary.
- Only the hashers that `BrotliCreateBackwardReferences` instantiates with
`ENABLE_COMPOUND_DICTIONARY` search the dictionaries (with
`LookupCompoundDictionaryMatch`, after the hasher's own search, for each
chunk in order): H5, H6, H58, H68, H40, H41, H42, H55 and H65. So
qualities 5 to 9 search them, quality 4 only with the large-window H55
(lgwin above 24 and a big size hint), and qualities 2 and 3 (H2, H3, H35)
and quality 4 with H4 or H54 never do (the C code falls back to its
non-dictionary variant for those hashers). The search only finds matches
that are within `params.dist.max_distance` (`BROTLI_MAX_DISTANCE`, or
`BROTLI_MAX_ALLOWED_DISTANCE` for large-window brotli) and that do not
cross a chunk's end.
- At qualities 10 and 11 (`BrotliCreateZopfliBackwardReferences` and
`BrotliCreateHqZopfliBackwardReferences` in `backward_references_hq.c`),
for each position, `LookupAllCompoundDictionaryMatches` finds up to 64
matches (of length 4 or more, each longer than the previous one, over the
chunks in order) in the dictionaries, which `MergeMatches` merges (by
length, then distance) with the H10 binary tree's and static dictionary's
matches. The binary tree's static dictionary matches start at
`dictionary_start + gap`, and `UpdateNodes`, `EvaluateNode` (via
`ComputeDistanceShortcut`) and `BrotliZopfliCreateCommands` treat
distances up to `dictionary_start + gap` as non-static-dictionary ones
(which update the distance cache). `UpdateNodes` also tries the distance
cache's distances that land in the compound dictionary (finding the chunk
and matching up to its end).
- With `QUIRK_STREAM_OFFSET`, `dictionary_start` is `min(position +
stream_offset, max_backward_limit)`, as in the C code (whose output then
continues another stream and can only be decoded after it).
`add_dictionary` statuses (the C code's functions return `NULL` or
`BROTLI_FALSE`):
| Condition | Wuffs status | C code |
| ------------------------------------------------------------ | ---------------------------------------------- | ------ |
| `transform_io` has been called | `base."#bad call sequence"` | accepted (see below) |
| `DICTIONARY_TYPE_SERIALIZED` | `"#unsupported serialized encoder dictionary"` | `BrotliEncoderPrepareDictionary` returns `NULL` |
| unknown `dict_type` | `base."#bad argument"` | `BrotliEncoderPrepareDictionary` returns `NULL` |
| a 16th dictionary | `"#too many compound dictionaries"` | `BrotliEncoderAttachPreparedDictionary` fails |
| more than `0x7FFF_FFFF` bytes of dictionaries in total | `"#too much dictionary data"` | accepted |
| `workbuf` shorter than `add_dictionary_workbuf_len(n)` | `base."#bad workbuf length"` | n/a |
An empty dictionary is accepted (and counts towards the 15), like in the C
code. On failure, the encoder's state is unchanged. A `transform_io` call
with a workbuf shorter than `D` returns `base."#bad workbuf length"`.
Differences from the C code:
- Serialized (shared) dictionaries are rejected, exactly like the default
(non-`BROTLI_EXPERIMENTAL`) libbrotlienc build, whose
`BrotliEncoderPrepareDictionary` returns `NULL` for them. (The decoder, in
contrast, accepts them, like an experimental libbrotlidec build.) With an
experimental build, the C encoder would also use their custom static
dictionaries; that is not implemented.
- The C code's `BrotliEncoderAttachPreparedDictionary` accepts a raw
dictionary even after compression has started (it only checks
`is_initialized_` for serialized dictionaries). The compound dictionary's
size then changes mid-stream, so the static dictionary references before
and after that point use different distance bases, and the output is
generally not decodable. Here, `add_dictionary` returns `"#bad call
sequence"` once `transform_io` has been called.
- The C code holds each dictionary's length in a `uint32_t` (and item
offsets in 31 bits). This package rejects more than `0x7FFF_FFFF` bytes
of dictionaries in total (like its decoder).
- When `ExtendLastCommand` extends a copy past the end of a compound
dictionary chunk into an empty chunk, the C code reads (one or more
bytes) past the end of that empty chunk's (zero-length) data. Here, the
extension stops there. This needs an empty dictionary attached after a
non-empty one and a copy extension that reaches the non-empty one's end
(with empty dictionaries only before the non-empty ones, the behaviors are
the same).
- Like the C code's `BrotliEncoderPrepareDictionary` with the default
allocator, there is no separate "prepared dictionary" object that could be
shared between encoders: each encoder prepares its own copy (the C code's
"lean" prepared dictionaries reference the caller's bytes instead).
### Encoder Testing
`wuffs test -mimic std/brotli` (including its encoder dictionary tests)
checks byte-exact parity with libbrotlienc
over a grid of qualities (0 to 11), lgwins, modes, input chunkings, flushes,
metadata blocks, size hints and other parameters (lgblock, npostfix, ndirect,
disabling literal context modeling, stream offset, large window), as well as
round trips through the decoder. Its large-window tests cover qualities 3 to
9 with lgwin 18 to 30 (and the H35, H55 and H65 hashers) on small files and
on a 46 MiB input with repeats at distances of about 20 and 40 MiB, decoded
by both this package's decoder and libbrotlidec.
`script/manual-test-brotli-float.c` checks the encoder's package-private
float fast paths (`encode_float.wuffs`, which spare the hot loops the
cross-package `std/softfloat` calls) against the C compiler's hardware float
and double arithmetic, for operands biased towards their edge cases, and
checks the integer bit helpers (`log2_floor_non_zero` for every 32-bit value,
and `ctz64`).
`script/manual-test-brotli-encoder-parity.c` runs a larger grid over every
file in `test/data/brotli`, some larger files in `test/data` (up to about
400 KiB) and some synthetic inputs (up to 1 MiB). Its `-q=LO-HI` and
`-shard=K/N` options select the qualities (0 to 11) and split the inputs
over several processes, `-lw` runs only its large-window grid (lgwin 10 to 30 at
qualities 2 to 9, with various chunkings, flushes, size hints and other
parameters, each also with the shortest workbuf that should work) and `-big`
replaces the inputs with synthetic ones of 3 to 70 MiB with repeats at
distances of up to 40 MiB. `-dict` replaces the usual grid with a
dictionary grid (see "Encoder Dictionaries" above): for each input, seven
sets of raw dictionaries (a prefix of the input, the whole input,
`test/data/enwik5`, noise plus the input's middle third, 15 pieces of the
input, tiny and empty dictionaries, and the input's swapped halves plus some
text), with qualities 0 to 11, lgwins, chunkings, flushes, metadata blocks,
size hints, stream offsets, large window and other parameters, plus
dictionaries of 2 MiB to 40 MiB (every hash table size) with a 1 MiB input.
Each dictionary configuration's output is also decoded by libbrotlidec and
by this package's decoder (with the same dictionaries), except with a
stream offset, and the whole-input and big dictionaries check that the
output is smaller than without them (at qualities 5 and above, unless it is
already tiny). With `-dict` (and `-q=0-9`) it runs 419,802 configurations,
all byte-exact against libbrotlienc v1.2.1 on x86-64, with 356,546 round
trips through both decoders. With `-dict -q=10-11` (which uses the
smallest dictionary grid for inputs longer than 64 KiB), shards 0 to 47 of
90 (except 43 and 46: 98 inputs, including all of the 2 to 40 MiB
dictionaries) ran 39,800 configurations, also all byte-exact, with 33,814
round trips through both decoders and 80 smaller-with-dictionary checks. With
`-q=0-9` (the default) and without `-dict` it runs 814,706
configurations (96,688 of them in the large-window grid), all byte-exact
against libbrotlienc v1.2.1 on x86-64. With `-lw -big` it runs 720 more
(on 3, 6 and 12 MiB inputs with the large-window grid and on 24, 40 and
70 MiB inputs with one-shot and streaming large-window configurations at
lgwin 24 to 30), also all byte-exact.
At qualities 10 and 11 (which use the smaller grid for inputs longer than
64 KiB, and the `workbuf_len` minimum, so that the practical bound is
exercised), `-q=10-11` ran 144,036 configurations over 179 inputs before
the large-window grid was added to the default grid, and, afterwards,
`-q=10-11 -lw` ran 24,172 configurations (22,990 also with the shortest
workbuf) and `-q=10-11` on a third of the inputs (shards 0, 3, 6, etc of
60) another 55,450 (7,740 also with the shortest workbuf), all byte-exact,
except for 474 configurations skipped because their workbuf would be more
than 12 GiB (large-window brotli with lgwin 30 and lgblock 24). `-oneshot=W`
checks one configuration per input and quality (lgwin W, the whole input
in one `FINISH` step), e.g. for the 3 MiB `test/data/harvesters.bmp` at
qualities 10 and 11 with lgwin 22 and 24, also byte-exact. At qualities 10
and 11 the Wuffs encoder is roughly 6 times slower than libbrotlienc,
so the full `-q=10-11` grid takes a few CPU hours.
`script/manual-test-brotli-fuzz.c` is a differential fuzzer (see its header
comment) that feeds the same random inputs, parameters and operation
sequences to both libraries. On the final code it ran 1,014,752 random
encoder configurations (5,936 of them at qualities 10 and 11), 3.76 million
mutated decoder inputs (each decoded four ways, about 180 thousand of them
also with `QUIRK_REPORT_METADATA`, comparing 24.9 million metadata blocks
with libbrotlidec's callbacks) and 289,484 API edge case checks, all without
an unexplained difference. The differences that it found are documented
above (and in "Status Mapping"), or were fixed.
### Encoder Differences from the C Code
- At qualities 0 and 1, the input block is not copied (see the workbuf
layout above). Output is always staged in the workbuf (or a small internal
buffer) and then copied to `dst`. The C code sometimes writes directly to
`next_out`. The bytes are the same.
- The C code instantiates each hasher (and the block splitters) from
templates. Here, each template is one set of functions, parameterized at
run time (e.g. by the hasher type). The H58 and H68 hashers' SIMD tag
matching (`GetMatchingTagMask` in `matching_tag_mask.h`) is computed one
tag at a time, which finds the same candidates in the same order. Like the
x86-64 GCC reference build (where `BROTLI_MAX_SIMD_QUALITY` is 6, as in
any build with a 64-bit `__builtin_ctzll`), qualities 5 and 6 with lgwin
above 16 use H58 or H68 instead of H5 or H6. libbrotlienc builds where
`BROTLI_MAX_SIMD_QUALITY` is undefined (no 64-bit count-trailing-zeros
builtin) or 7 (MSVC on x86-64) choose differently and so produce
different (but valid) output at those qualities.
- The composite hashers (H35, H55 and H65) are not separate hasher types
here: `hasher_type` is their first hasher (H3, H54 or H6) and a non-zero
`hr_jump` (4 for `HROLLING_FAST`, 1 for `HROLLING`) adds the rolling
hasher, whose functions run after the first hasher's, like the C code's
composite `FN(Prepare)`, `FN(StitchToPreviousBlock)` and
`FN(FindLongestMatch)`. The C code's composite hasher defers its inner
hashers' `FN(Initialize)` to its first `FN(Prepare)`. Here, the first
hasher's `FN(Initialize)` runs in `hasher_setup` (it does not touch the
hasher's memory, so this is equivalent) and the rolling hasher's at the
first `hasher_prepare`. The C code's composite gives its first hasher a
copy of its `HasherCommon` (with zeroed static dictionary statistics);
here, the first hasher uses the encoder's statistics, which the composite
itself never uses, so the result is the same.
- The workbuf's regions are in a different order than the C code's
allocations and the ring buffer is fully reserved from the start (see the
workbuf layout above). This does not change the output.
- `BrotliBuildMetaBlockGreedy`'s two kinds of block splitter (one for a
single histogram per block type, `metablock_inc.h`, and one for several
literal contexts, `ContextBlockSplitter` in `metablock.c`) are one
implementation here, as they make the same decisions with one context.
- Wuffs' C code generator does not support `slice base.u16` or
`slice base.u32` arguments (and mishandles `copy_from_slice` on `base.u16`
arrays), so some functions (e.g. `create_huffman_tree`,
`convert_bit_depths_to_symbols`) take a selector naming one of the
encoder's arrays instead of a slice.
- Like the C code, there is no fallback to an uncompressed stream (that is
only in the C code's one-shot `BrotliEncoderCompress`).
- At qualities 10 and 11, a workbuf between `workbuf_len`'s `min_incl` and
`max_incl` can be too short for an unusual input, which then fails with
`"#bad workbuf length"` (see "Qualities 10 and 11 Workbuf Length").
- At qualities 10 and 11, the C code's f32 costs (`ZopfliNode` costs, the
cost model and literal costs) are computed with `std/softfloat`'s binary32
operations, rounding each operation to f32 like an SSE2 build (whose
`float` arithmetic has no excess precision).
### Encoder Metablock Builder
The `metablock_builder` struct (a `pri struct`, embeddable in the encoder
with one field, e.g. `mb : metablock_builder` in the private data section)
implements the quality 10 and 11 metablock construction (`BrotliBuildMetaBlock`)
and `BrotliOptimizeHistograms`. The encoder has one (its `mb` field) and
uses it at qualities 10 and 11 (and its smaller helpers at lower
qualities). Its
fixed-size state (about 0.8 MiB: FindBlocks' cost arrays and a 64Ki-entry
FastLog2 cache in its `bit_cost`) lives in the struct; everything that the C
code allocates on the heap lives in a caller-supplied workbuf. The FastLog2
cache (like the encoder's own `bit_cost` one) is filled lazily, one entry at
a time, when `fast_log2_memo` first needs that entry (a bitmap, zeroed when the
struct is initialized, records which entries are valid): typically only a few
thousand of the 65536 entries are ever used, and each one costs a (slow, exact)
software `log2`.
Data formats (all little-endian, matching the C structs' memory layout on a
64-bit little-endian machine, so that results can be compared with `memcmp`):
- A command is 16 bytes: `insert_len_` (u32), `copy_len_` (u32), `dist_extra_`
(u32), `cmd_prefix_` (u16), `dist_prefix_` (u16), as built by `command.h`'s
`InitCommand` / `InitInsertCommand`.
- A histogram is `(4 * data_size) + 16` bytes: `data_size` u32 counts, the
u64 `total_count_` and the binary64 bits of `bit_cost_`. `data_size` is 256
(literals, 1040 bytes), 704 (commands, 2832 bytes) or 544 (distances, 2192
bytes).
- A BlockSplit's types are u8s and its lengths u32s. Context maps are u32s.
- Doubles are binary64 bit patterns (u64), computed with `std/softfloat` in
the C code's operation order.
Usage, mirroring the C code's `WriteMetaBlockInternal` for quality >= 10:
```
// Once per metablock. The params are the C code's block_params, a copy of
// the encoder's params: init_distance_params must be called each time,
// because build_meta_block overwrites the dist_etc fields with the chosen
// distance params.
this.mb.set_params!(quality: q, large_window: lw,
disable_literal_context_modeling: dlcm)
this.mb.init_distance_params!(npostfix: np, ndirect: nd, large_window: lw)
status = this.mb.build_meta_block!(wb: workbuf, ringbuffer: rb, pos: pos,
mask: mask, prev_byte: pb, prev_byte2: pb2, cmds: cmds,
num_commands: n, literal_context_mode: mode)
// Optional (quality >= 4): ndc is min(this.mb.dist_alphabet_size_limit, 544).
this.mb.optimize_histograms!(wb: workbuf, num_distance_codes: ndc)
```
The exact signatures are:
- `set_params!(quality: u32, large_window: bool,
disable_literal_context_modeling: bool)`.
- `init_distance_params!(npostfix: u32, ndirect: u32, large_window: bool)`
(`BrotliInitDistanceParams`; sets `dist_postfix_bits`,
`dist_num_direct_codes`, `dist_alphabet_size_max`,
`dist_alphabet_size_limit` and `dist_max_distance`).
- `build_meta_block!(wb: slice u8, ringbuffer: roslice u8, pos: u64, mask:
u64, prev_byte: u8, prev_byte2: u8, cmds: slice u8, num_commands: u64,
literal_context_mode: u32) status`. `ringbuffer` must be at least `mask + 1`
bytes. `literal_context_mode` is a `ContextType` (0 = LSB6, 1 = MSB6, 2 =
UTF8, 3 = SIGNED). Like the C code, it rewrites the commands'
`dist_prefix_` and `dist_extra_` fields for the chosen distance params and
leaves those params in the `dist_etc` fields. Like the encoder's commands,
every command's distance code must be at most the given params'
`max_distance` (with larger, invalid distance codes, the C code's
`ComputeDistanceCost` writes past the end of its distance histogram, which
the Wuffs code cannot mirror: it ignores out-of-range histogram symbols
instead). It returns
`"#bad workbuf length"` if `wb` is too short (the results are then invalid
but `cmds` may already be rewritten, so retrying needs the original
commands).
- `optimize_histograms!(wb: slice u8, num_distance_codes: u32)` works on the
MetaBlockSplit described by the fields below, whether `build_meta_block`
or the caller (e.g. a greedy builder) filled them in.
- `workbuf_len_worst_case(num_literals: u64, num_commands: u64) u64` is an
upper bound on the workbuf length that `build_meta_block` needs, where
`num_literals` is the sum of the commands' insert lengths. It assumes the
worst case for every run-time-sized allocation (one `FindBlocks` block per
symbol, 256 block types with 64 literal contexts each, full histogram pair
queues), so it is far larger than what real inputs need: about 76 MiB for
a 1 KiB metablock, 2.6 GiB for 1 MiB of literals and 128 Ki commands, and
41 GiB for 16 MiB of literals and 4 Mi commands. These are the C code's
own worst cases (`ClusterBlocks` and `BrotliClusterHistograms` size their
histogram pair queues by the number of blocks and clusters), not artifacts
of the port. `wb_high` records what a call actually used: over the parity
harness's inputs, at most about 42 MB (for 1.3 MiB of literals split into
256 literal block types).
- `workbuf_len_practical(num_literals: u64, num_commands: u64) u64` is the
same bound with caps on the numbers of blocks and clusters (see
"Qualities 10 and 11 Workbuf Length"), which the encoder uses for its
`workbuf_len().min_incl`.
The MetaBlockSplit result is described by these fields, indexed by category
(0 = literal, 1 = command, 2 = distance), with offsets into `wb`:
| Field | C code |
| ---------------------- | ----------------------------------------------- |
| `split_num_types[c]` | `{literal,command,distance}_split.num_types` |
| `split_num_blocks[c]` | `..._split.num_blocks` |
| `split_types_off[c]` | `..._split.types` (u8 array) |
| `split_lengths_off[c]` | `..._split.lengths` (u32 array) |
| `context_map_off[c]` | `{literal,distance}_context_map` (u32 array; none for commands) |
| `context_map_size[c]` | `{literal,distance}_context_map_size` |
| `histograms_off[c]` | `{literal,command,distance}_histograms` |
| `histograms_size[c]` | `..._histograms_size` |
Workbuf layout during `build_meta_block` (a bump allocator, `wb_top`, carves
regions out of `wb` in this order; "scratch" regions are released when the
C code frees them, so later regions reuse their bytes):
1. Scratch: one distance histogram for the distance parameter search.
2. The three BlockSplits' types and lengths arrays, sized for one block per
symbol (`max(1, n)` entries, where n is the number of literals, commands
or distance codes).
3. Scratch: `BrotliSplitBlock`'s literal / command code / distance code
arrays and `SplitByteVector`'s histograms, block ids, bitmaps and
`ClusterBlocks` state.
4. The command histograms, literal context map, literal histograms (room for
`64 * num_literal_types`), distance context map and distance histograms
(room for `4 * num_distance_types`).
5. Scratch: the per-context literal and distance histograms that are then
clustered, and `BrotliClusterHistograms`' state (cluster sizes, histogram
pairs, etc).
After `build_meta_block` returns, the results (regions 2 and 4) are below
`wb_top`, and `wb[wb_top ..]` is free for the caller (e.g. for storing the
metablock) for as long as it needs the results.
### Encoder TODO
- `workbuf_len` is a worst case (or, at qualities 10 and 11, a practical
bound). A future option could take the input length (like the C code's
size hint) to give a tighter bound.
- Speed. On a mix of text, JSON, map data, an image and an ISO image (on
x86-64, lgwin 22, one call each, reusing the workbuf), the Wuffs encoder
takes about 1.2 to 1.8 times libbrotlienc's time at qualities 0 to 8 (about
1.8 times at the qualities 4 to 6 that web servers use for on-the-fly
compression) and about the same time at quality 9. At qualities 10 and 11
it takes about 2 times libbrotlienc's time on text and 3.5 to 4 times on
images (such as the 3 MiB `test/data/harvesters.bmp`), mostly because of
the soft float arithmetic in the Zopfli cost model, the block splitter and
histogram clustering. Decoding takes about 1.2 to 1.6 times libbrotlidec's
time. The workbuf is sized for the window (about 48 to 62 MiB at lgwin 22
and qualities 5 to 9), so callers that compress many small inputs should
reuse it: allocating and first touching a fresh one for each call costs
more than the compression of a small input.
- Serialized (shared) dictionaries, which only an experimental
(`BROTLI_EXPERIMENTAL`) libbrotlienc build supports.
- Changing parameters mid-stream.
## Large Window
Large-window brotli (an incompatible extension of RFC 7932, with window sizes
up to `(1 << 30)` bytes) is enabled by the `QUIRK_LARGE_WINDOW` quirk. It
mirrors libbrotlidec's `BROTLI_DECODER_PARAM_LARGE_WINDOW` parameter: it must
be set before decoding starts (afterwards, `set_quirk` returns `"#bad call
sequence"`, like `BrotliDecoderSetParameter` failing once the decoder has
left its `BROTLI_STATE_UNINITED` state). With the quirk set:
- a stream that starts with the large-window `WBITS` escape is decoded as a
large-window stream: the escape is followed by a reserved bit (that must be
zero) and 6 window bits (that must be in `[10 ..= 30]`), otherwise the
decoder fails with `"#bad window bits"`.
- a stream that does not start with that escape is decoded as standard brotli,
exactly as without the quirk.
- `workbuf_len` is `(1 << 30) + 542` bytes (plus any dictionaries), the
largest large-window window size plus slack. As before, the workbuf only
needs to be as long as the stream's actual window size plus 542 bytes (plus
any dictionaries). Without the quirk, it is `(1 << 24) + 542` bytes (plus
any dictionaries), as before.
For a large-window stream, like the C code, the distance alphabet's
`alphabet_size_max` uses `BROTLI_LARGE_MAX_DISTANCE_BITS` (62) and its
`alphabet_size_limit` comes from `BrotliCalculateDistanceCodeLimit` (at most
544 symbols, so that no distance exceeds `BROTLI_MAX_ALLOWED_DISTANCE`). Up to
29 extra distance bits are read (the C code's `BrotliSafeReadBits32`) and the
distance is calculated with 64-bit arithmetic, like the C code's
`brotli_reg_t`. The Huffman table stride for distance trees is sized for 544
symbols in both modes.
The `DECODER_WORKBUF_LEN_MAX_INCL_WORST_CASE` constant is now the overall
worst case: `(1 << 30) + 542` plus the maximum total dictionary length
(`0x7FFF_FFFF`). The new `DECODER_WORKBUF_LEN_STANDARD` and
`DECODER_WORKBUF_LEN_LARGE_WINDOW` constants give the window-only values.
## Dictionaries
`decoder.add_dictionary!(dict_type: base.u32, dict: roslice base.u8, workbuf:
slice base.u8) base.status` mirrors libbrotlidec's
`BrotliDecoderAttachDictionary`. `dict_type` is `DICTIONARY_TYPE_RAW` (0, the
C code's `BROTLI_SHARED_DICTIONARY_RAW`) or `DICTIONARY_TYPE_SERIALIZED` (1,
`BROTLI_SHARED_DICTIONARY_SERIALIZED`). It must be called before decoding
starts. It can be called multiple times.
Wuffs structs cannot hold pointers or slices, so `add_dictionary` copies the
dictionary bytes into the workbuf. Every `add_dictionary` and `transform_io`
call must be passed the same workbuf (or at least one whose first bytes hold
the same dictionary bytes). The `add_dictionary` workbuf only needs to be long
enough to hold all of the dictionaries added so far. Call `workbuf_len` after
the last `add_dictionary` call: it grows by each dictionary's length.
The workbuf layout is:
[0 .. D) the attached dictionaries, concatenated, where D is
the total length of all successfully added
dictionaries (raw or serialized, in full).
[D .. D + W + 542) the history ring buffer (W = 1 << WBITS) and slack.
The dictionaries come first because their position should not depend on the
stream's window size, which is only known once decoding has started.
Raw dictionaries are LZ77 prefix dictionaries. Like the C code (its
`BrotliDecoderCompoundDictionary` and `AttachCompoundDictionary`,
`InitializeCompoundDictionaryCopy` and `CopyFromCompoundDictionary`
functions), at most 15 such "compound dictionary" chunks (raw dictionaries
plus serialized dictionaries' LZ77 prefixes) can be attached. A backward
reference distance `d` beyond the current maximum LZ77 distance `m` (but
within `BROTLI_MAX_ALLOWED_DISTANCE`) refers to the compound dictionary when
`d - m - 1` is less than the compound dictionary's total size `T`, at address
`T - (d - m)`. A copy that would extend past the compound dictionary's end
fails with `"#bad compound dictionary"`. Otherwise, the static dictionary's
address is `d - m - 1 - T`.
Serialized dictionaries are parsed and validated like
`BrotliSharedDictionaryAttach` (`DecodeSharedDictionary`,
`DryParseDictionary`, `ParseDictionary`, `ParseWordList`,
`ParseTransformsList` and `ParsePrefixSuffixTable` in
`c/common/shared_dictionary.c`): the `0x91 0x00` magic, an optional LZ77
prefix (at most 1073741823 bytes), up to 64 custom word lists (word lengths 4
to 31, at most 15 size bits per length), up to 64 custom transform lists (up
to 256 prefix/suffix stringlets, up to 255 transforms, transform types up to
`BROTLI_TRANSFORM_SHIFT_ALL`, with 16-bit parameters for the
`BROTLI_TRANSFORM_SHIFT_FIRST` and `BROTLI_TRANSFORM_SHIFT_ALL` types), up to
64 (word list, transform list) combinations and an optional 64-entry context
map. The parsed metadata lives in fixed-size decoder fields (`wl_etc`, `tl_etc`
and `sd_etc`), with offsets into the copied bytes in the workbuf. Like the C
code:
- only one attached serialized dictionary can have custom word lists or
transform lists (otherwise `"#unsupported multiple custom static
dictionaries"`), and
- attaching a serialized dictionary without custom word lists or transform
lists (only an LZ77 prefix) resets the static dictionary to the built-in
(RFC 7932) one, even if an earlier serialized dictionary had custom lists.
Static dictionary references then mirror `ProcessCommandsInternal`: the word
list and transform list are selected by the literal context (`BROTLI_CONTEXT(p1,
p2, context_lookup)`) through the context map (if enabled), with the C code's
fall back to the other (word list, transform list) combinations when the
address is out of range, and words are transformed like
`BrotliTransformDictionaryWord` (including `Shift` for the shift transforms).
Transformed words can be up to 541 bytes long.
`add_dictionary` statuses (the C code just returns `BROTLI_FALSE`):
| Condition | Wuffs status |
| -------------------------------------------------------------- | ----------------------------------------------------- |
| decoding has started | `base."#bad call sequence"` |
| unknown `dict_type` | `base."#bad argument"` |
| more than 15 compound dictionary chunks | `"#too many compound dictionaries"` |
| invalid serialized dictionary | `"#bad shared dictionary"` |
| a second serialized dictionary with custom lists | `"#unsupported multiple custom static dictionaries"` |
| more than `0x7FFF_FFFF` bytes of dictionaries in total | `"#too much dictionary data"` |
| `workbuf` shorter than the dictionaries so far plus this one | `base."#bad workbuf length"` |
Differences from the C code:
- On failure, `add_dictionary` leaves the decoder unchanged. libbrotlidec's
`BrotliDecoderAttachDictionary` can fail after partially updating its shared
dictionary (e.g. after counting a serialized dictionary's LZ77 prefix or
reading its number of word lists), which can affect later attach calls.
- libbrotlicommon only parses serialized dictionaries when built with
`BROTLI_EXPERIMENTAL`, which is not the default. A default build rejects
every serialized dictionary. This package always accepts them, matching an
experimental build. The mimic tests skip serialized dictionary cases when
the linked libbrotlidec rejects them; they pass, with no skips, when linked
against a `BROTLI_EXPERIMENTAL` build.
- The C code holds the compound dictionary's total size in an `int`. This
package rejects more than `0x7FFF_FFFF` bytes of dictionaries in total
(counting serialized dictionaries in full), where the C code would overflow.
- `BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET` cannot happen (see above).
## Metadata Blocks
libbrotlidec can report metadata blocks' contents through callbacks
(`BrotliDecoderSetMetadataCallbacks`). Wuffs code cannot call back into its
caller. By default, metadata blocks are skipped (validated and consumed but
not reported), exactly as libbrotlidec does without callbacks.
With the `QUIRK_REPORT_METADATA` quirk, the decoder reports them instead. At
each metadata block (after every previously decoded byte has been written to
`dst`), `transform_io` returns `base."@metadata reported"`, and
`metadata_length()` returns the block's length, which can be zero (the C
code's start callback's `size`). The next `metadata_length()` bytes that
`transform_io` writes to `dst` (over one or more subsequent calls) are the
block's contents (the C code's chunk callbacks' data). Decoded bytes follow as
usual. The decoded output (the bytes outside of metadata blocks) is the same
with or without the quirk. `test_mimic_brotli_decode_metadata` checks that the
lengths and contents match libbrotlidec's callbacks.