High-Quality Encoder Core (qualities 10 and 11)

Scope: src/compressor/core/hq/. This document describes the code as it stands; the Known gaps section lists what is not implemented.

The reference this port follows is google/brotli v1.2.0, commit 028fb5a. BROTLI_MAX_SIMD_QUALITY does not reach these qualities — both use the binary-tree matcher H10 unconditionally — so there is only one semantic profile to match, and the differential tests compare against it byte for byte.

1. Core mechanics

The greedy encoder decides one command at a time and never reconsiders. This one prices every command that could start at every position and then solves for the cheapest path through the whole block:

1. Input is copied into the same ring buffer the greedy path uses.
2. A binary-tree matcher reports every match at a position, ordered by increasing length, rather than a single best one.
3. A cost model puts an f32 price on every literal, command symbol and distance symbol.
4. A dynamic program walks the block, recording at each byte the cheapest way of arriving there, and finally traces the shortest path back into commands.
5. The high-quality meta-block builder re-tunes the distance alphabet, splits all three symbol streams, gathers per-context histograms and clusters them into the context maps the decoder reads.
6. The result is written through the same bit-stream layer every other quality above one uses.

graph TD
    subgraph driver["compressor::core::driver"]
        drv["Encoder::Hq"]
    end

    subgraph hq["compressor::core::hq"]
        enc["encoder<br/>(HqEncoder, dispatch)"]
        params["params<br/>(HqParams, HqQuality)"]
        h10["h10<br/>(BinaryTreeMatcher, BackwardMatch)"]
        utf8["utf8<br/>(IsMostlyUTF8)"]
        lit["literal_cost<br/>(per-literal estimate)"]
        cost["cost<br/>(ZopfliCostModel)"]
        nodes["nodes<br/>(ZopfliNode, StartPosQueue)"]
        zop["zopfli<br/>(the dynamic program)"]
        mb["metablock<br/>(MetaBlockBuilder)"]
        bsp["block_splitter<br/>(BlockSplitter)"]
        clu["cluster<br/>(histogram clustering)"]
    end

    subgraph shared["shared"]
        rb["ringbuffer"]
        cmdmod["command"]
        dist["distance"]
        histo["histogram"]
        bitcost["bit_cost<br/>(BrotliPopulationCost)"]
        bsplit["block_split<br/>(BlockSplit)"]
        mbs["metablock<br/>(MetaBlockSplit)"]
        bs["bitstream<br/>(MetaBlockWriter)"]
        dictionary["dictionary::all_matches"]
        ml["match_len"]
        fmt["format<br/>(ContextMode)"]
    end

    drv --> enc
    enc --> params
    enc --> rb
    enc --> zop
    enc --> mb
    enc --> bs
    zop --> h10
    zop --> cost
    zop --> nodes
    zop --> cmdmod
    cost --> lit
    lit --> utf8
    params --> utf8
    h10 --> dictionary
    h10 --> ml
    mb --> bsp
    mb --> clu
    mb --> histo
    mb --> dist
    mb --> mbs
    bsp --> clu
    bsp --> bsplit
    clu --> bitcost
    bsp --> bitcost

    classDef sharedNode fill:#e8f0f6,stroke:#3a6d8a;
    class rb,cmdmod,dist,histo,bitcost,bsplit,mbs,bs,dictionary,ml,fmt sharedNode;

2. What separates the two qualities

Both qualities run the same code; every difference is a number resolved once in params.rs, from the caller’s parameters alone.

Quality eleven’s second pass is what earns most of its ratio: the first pass prices commands from a literal-cost estimate, and the second re-prices them from the histograms the first pass actually produced.

sequenceDiagram
    participant E as HqEncoder
    participant Z as zopfli
    participant H as H10
    participant M as ZopfliCostModel

    Note over E,M: quality 10 — one pass, matches discovered as it goes
    E->>Z: create_zopfli_backward_references
    Z->>M: set_from_literal_costs
    loop every position
        Z->>H: find_all_matches
        Z->>Z: update_nodes
    end
    Z->>Z: shortest path → commands

    Note over E,M: quality 11 — matches precomputed, two passes
    E->>Z: create_hq_zopfli_backward_references
    loop every position
        Z->>H: find_all_matches → match arena
    end
    Z->>Z: save command count, literals, distance cache
    Z->>M: set_from_literal_costs
    Z->>Z: iterate → first commands
    Z->>Z: restore saved state
    Z->>M: set_from_commands(first commands)
    Z->>Z: iterate → final commands

3. The binary-tree matcher

h10.rs keeps one binary tree per hash bucket, over 1 << 17 buckets. Each tree is ordered lexicographically by the bytes at each position and is a max-heap by position, so one traversal both collects every match worth considering — in strictly increasing length order — and re-roots the tree at the current position.

The forest — two child links per window position — is sized when the first block prepares the matcher, as the reference’s HashMemAllocInBytes sizes it: a stream whose first block is also its last (position == 0 && is_last) stores only positions below its length, so it gets 2 * input_size links rather than 2 << lgwin; any other stream gets the window’s worth. The forest only grows, and a reused matcher keeps the largest one it has needed; the links of positions a stream never stored are never followed, so nothing is cleared between streams. A forest that has to grow is taken from the allocator’s zeroing path after releasing the old allocation. A non-final first block can reserve a full window of links even for short input; untouched links must not be eagerly materialized. Buckets are initialized with their empty marker on first preparation. ZopfliCostModel::reserve sizes literal prices per block. The model’s literal, command and distance histograms and its per-byte literal price table never change length, so they are Box<[T; N]> tables built by shared::fixed::fixed_table; a literal byte indexes them with no bounds check. The per-byte price spread and the carried cumulative sum walk the price slice 1..=num_bytes by iterator, in the same order and with the same f32 operations as the reference.

Three bounds shape what it finds, all from the reference:

• Search depth 64. A degenerate bucket cannot cost more than that.
• Comparison length 128. Two sequences that agree over 128 bytes are indistinguishable to the tree, so the older node’s children become the new root’s.
• Re-rooting needs 128 bytes of lookahead. Near the tail the traversal still reports matches but leaves the tree alone, because the final sort order of a shorter sequence is not yet known.

flowchart TD
    A["find_all_matches at cur_ix"] --> B["scan_recent_positions<br/>(16 or 64 positions, nearest first)"]
    B --> B1{"candidates contiguous<br/>in the ring?"}
    B1 -->|yes| B2["u8x32 compare of the two<br/>leading bytes; measure the<br/>agreeing lanes, top lane first"]
    B1 -->|"no (wrap, buffer end)"| B3["byte-by-byte walk"]
    B2 --> B3
    B3 --> C{"best_len < max_length?"}
    C -->|no| F["static dictionary"]
    C -->|yes| D["store_and_find_matches"]
    D --> E{"lookahead >= 128?"}
    E -->|yes| E1["re-root the tree at cur_ix"]
    E -->|no| E2["leave the tree unchanged"]
    E1 --> F
    E2 --> F
    F --> G["matches, increasing length"]

The short backward scan exists because the tree indexes four-byte prefixes and therefore cannot see a two- or three-byte repeat at all. It stops above its lower bound, so the oldest position in range is never examined — a reference quirk the port reproduces.

scan_recent_positions runs that scan. A candidate whose first two bytes disagree with the current position cannot match, so while the candidates lie contiguously below cur_ix in the ring, their leading bytes are compared thirty-two at a time (u8x32::simd_eq against two splats, one bitmask) and only the agreeing lanes are measured with find_match_length. Lanes are visited from the top, which is the nearest candidate, and the walk still ends at the first match of three bytes or more, so the matches and their order are exactly the reference’s. A window that wraps around the ring, or lies within two bytes of the buffer’s end, or a span the vector loop could not cover, falls through to the byte-by-byte walk. At quality eleven this filter removed about 150 million of the 278 million instructions the search spent on Alice, most of it the two-byte compare of sixty-three candidates per position; byte_walk in the tests is the transcribed reference loop, and the vector scan is compared against it on every backend, with and without wrapping, over five corpora.

store_range sparsifies: positions older than the last sixty-three are stored every eighth position, and only once the range spans more than 512. A range between 63 and 575 long has its middle skipped entirely.

4. The dynamic program

nodes.rs holds one ZopfliNode per input byte. The reference packs a union into it — cost during the forward pass, a distance shortcut once the node has been evaluated, the next hop while the path is traced back. Rust models that as a plain u32 read and written through f32::to_bits, which keeps the exact aliasing without any unsafe.

stateDiagram-v2
    [*] --> Stub: BrotliInitZopfliNodes
    Stub: length 1, cost = infinity
    Stub --> Reached: update_nodes finds a cheaper way here
    Reached: cost < previous cost
    Reached --> Evaluated: evaluate_node
    Evaluated: cost replaced by the distance shortcut
    Evaluated --> OnPath: compute_shortest_path_from_nodes
    OnPath: shortcut replaced by the next hop
    OnPath --> [*]: create_commands

At each position update_nodes does two things, in this order:

1. Cached distances. For each of the sixteen short distance codes — the four remembered distances and the twelve near misses derived from the two freshest — it measures the match and prices every copy length it allows.
2. Tree matches. From the two cheapest start positions only, because a further start with the same distances rarely pays.

The cached-distance loop is the hottest code at quality eleven: sixteen probes for each of up to five start positions at every byte, about 24 million probe iterations for Alice. It is written to keep that iteration short while making the reference’s decisions:

• CACHE_PROBES packs kDistanceCacheIndex and kDistanceCacheOffset into one byte pair per code, so a probe is one load.
• Most probes fail on one byte: the copy would have to agree with the continuation byte at cur_ix + best_len. ProbeSite::candidates, in the private compressor::core::cache_probe module shared with the greedy matchers (greedy-encoder.md §2.4), tests all sixteen codes of one start at once. The codes are not sixteen scattered distances: codes 0 and 4–9 are the freshest distance nudged by +3..=-3, seven adjacent ring bytes, and codes 1 and 10–15 are seven more around the second freshest. Two eight-byte reads, with their eighth byte replaced by the third and fourth distances’ bytes, fill one u8x16 in lane order (LANE_CODES); one simd_eq against the continuation, turned into code order by two 256-entry tables (LANE_CODE_BITS), and one u32x16 range test over the sixteen distances derived_distances builds from the cache (distance - 1 < max_distance, the scalar admission below) give the candidate mask.
• The mask is a superset of what the scalar filter admits, never a replacement for it: each admitted code still runs the exact scalar body, including its own byte compare. A run whose seven positions wrap around the ring mask, or whose eight-byte word would read past the bytes the ring holds, is admitted whole (RUN_LANES), and with an attached prefix every distance outside the window is admitted for prefix_copy_length to decide. When a copy extends best_len, the codes after it are filtered again against the new continuation byte — exactly the codes, and the order, the reference’s sequential loop tries next. On alice29.txt this cut quality eleven from 1.479 to 1.156 billion instructions and mapsdatazrh from 3.396 to 2.743 billion (callgrind, one compression), with identical output.
• backward.wrapping_sub(1) < max_distance admits exactly the distances the reference’s three tests admit — backward > dictionary_start + gap, backward <= max_distance, and prev_ix >= cur_ix — because a zero distance wraps below the bound, a negative one wraps above it, and max_distance is never more than dictionary_start. Everything else goes to the cold prefix_copy_length, which holds the attached-prefix arm and the gray-area skip of §11.
• The ring is probed through window = ringbuffer[..=mask], so “would the copy run past the mask” and the slice bound are one get. The continuation byte is read once per probe rather than the reference’s compare-then-index.
• The lengths a match newly reaches are priced by iterating the node slice pos + best_len + 1 ..= pos + len and calling ZopfliNode::record on each node, instead of indexing nodes[pos + l] per length; the tree-match loop does the same over pos + len ..= pos + max_match_len.
• Admitted codes are visited lowest first by clearing the mask’s lowest set bit, with the loop state held by value.

flowchart TD
    Start[Start position k: cache, base cost] --> Stop{best_len >= max_len, or no continuation byte?}
    Stop -->|yes| Done[Next start or tree matches]
    Stop -->|no| Mask["ProbeSite::candidates: two 8-byte runs + 2 bytes -> u8x16 eq; u32x16 range test; tables -> code order"]
    Mask --> Floor[Drop codes below next_code]
    Floor --> Any{Admitted code left?}
    Any -->|no| Done
    Any -->|lowest code| Exact[Exact scalar filter: range, byte compare or prefix arm]
    Exact -->|rejected or no longer copy| Any
    Exact -->|copy longer than best_len| Price[Price newly reached lengths]
    Price --> Extend[best_len = len; next_code = code + 1]
    Extend --> Stop

At quality eleven, 44–57% of the start positions probed at a byte carry a distance cache equal to an earlier start’s at the same byte: starts reached through literals inherit the same four distances. The probes read only the cache and the input, so such a start finds exactly the copies the earlier one found; only the prices differ, because they start from a different cost. update_nodes therefore keeps a ProbeMemo in the start-position queue: per start, its cache and its hits (code, the best_len before the hit, the length found), in probe order. A start whose cache matches an earlier slot replays those hits through the same pricing, in the same order and with the same f32 arithmetic, without calling ProbeSite::candidates or measuring a match. That cut quality eleven by 6–11% of instructions and 3–6% of time. Quality ten probes one start per byte, so the replay is compiled out there (update_nodes’s MEMO parameter is false on the zopfli_compute_shortest_path path).

flowchart TD
    K["start k at this byte"] --> Same{"cache equal to slot j < k?"}
    Same -->|yes| Replay["price slot j's hits (code, best_len, len) in order"]
    Same -->|no| Probe["probe as above; append each hit to slot k"]
    Replay --> Next["k >= 2: next start; else tree matches"]
    Probe --> Next

• ZopfliCostModel rearranges command-symbol prices into rows indexed by insert code, last-distance policy, and copy code whenever either initializer rebuilds a model for at least 128 bytes. Only insert codes reachable within the block are rebuilt; all 24 copy codes are covered, including dictionary length codes. Rows follow the 704 symbol prices in the same vector, whose capacity is retained between blocks. Symbol pricing and minimum-cost reduction use only the original prefix. A shorter block truncates the vector to that prefix and uses one 32-slot stack row, filled when a useful match needs prices. This avoids growing the price allocation for cold small inputs. Failed cached probes and tree matches with no new copy lengths do not request a row. The copy-length loop borrows the selected row, eliminating repeated command-prefix construction. Rows have 32 slots to expose the five-bit copy-code bound to the optimizer; the dynamic program reads codes below 24.

flowchart LR
    Literal[Literal priors] --> Symbols[Command symbol prices]
    Histogram[Previous-pass command histogram] --> Symbols
    Symbols --> Size{Block has at least 128 bytes?}
    Size -->|yes| Rows[Prepare reachable insert-code rows after symbol prices]
    Size -->|no| Small[Keep symbol prefix; retain capacity]
    Small --> Match[Useful match fills one stack row]
    Rows --> Start[Borrow row outside copy-length loop]
    Match --> Start
    Start --> Length[Copy loop reads exact price by length code]
    Length --> Compare[Original f32 addition order and strict comparison]
    Compare --> Record[Record cheaper node]

Two shortcuts keep it tractable. compute_minimum_copy_length refuses to price a copy shorter than one already known to reach its destination more cheaply. And a copy longer than BROTLI_LONG_COPY_QUICK_STEP lets the search stride past the positions it covers, evaluating them but not searching them.

StartPosQueue keeps the eight cheapest command starts, sorted. It is a ring whose insertion shifts the cheaper prefix and stops at the first candidate with an equal or higher cost difference. The new entry precedes equal-cost entries, as in the reference’s strict adjacent-swap comparisons. Starts have finite cost differences. The untouched suffix is already sorted, so this produces the same ordering and eviction as visiting every adjacent pair, including after the ring wraps. A differential test compares every rank and distance cache after 4096 insertions with ties and extreme finite costs.

5. Numerical determinism

Every comparison in the dynamic program is a strict < on an f32, so the arithmetic is part of the output, not an implementation detail:

• Rearranged command prices copy the original f32 bits. No distance or extra-bit price is folded into them: additions keep their original order. The implicit last-distance command condition remains exactly code == 0, insert code below eight, and copy code below sixteen. Tests compare every legal length-code pair across both model initializers.

• FastLog2 returns a double in the reference and is narrowed to f32 at each use, so the intermediate is computed at full width and rounded once.

• The cumulative literal costs are built with an explicit carry that recovers the precision a running f32 sum would throw away. Over a long block a naive sum drifts low by orders of magnitude more than the carried one, and the search starts preferring literals it should not.

• The literal-cost estimator’s constants — window widths 495 and 2000, the additive nudges, the halving below one bit, the prologue surcharge — were tuned by the reference against its corpora and are reproduced exactly.

• The estimator reads every byte of a block through one contiguous slice (contiguous_block): the block itself when it does not wrap the ring buffer, which is every block of a one-shot stream, and a copy in the LiteralCostArena otherwise. Every read lies inside pos..pos + len, so the mask is applied in one place and the sliding-window loops index a plain slice.

• Both estimator models take two logarithms per byte, of the in-window count and of one symbol’s count. A window holds at most 2 * 2000 bytes, so every such count is below LOG2_WINDOW_END (4001). Counts below 256 read the shared LOG2_TABLE; counts from 256 read a Box<[f64; 3745]> tail that LiteralCostArena builds the first time it prices a block of at least 256 bytes, since a shorter block cannot hold a larger count. The tail is collected from shared::fast_log::log2, the library logarithm fast_log2 itself falls back to past its table, so no entry goes through the table check. Both lengths are in the types, so the bound checks compare against constants. A missing tail, or a count past it, computes log2 instead. Every path returns the same f64 the library call would, so nothing rounds differently; tests compare the tail bit for bit with fast_log2 and the priced blocks with and without it. The arena keeps the tail across blocks and streams and counts it in its retained bytes.

flowchart TD
    Block["estimate_bit_costs_for_literals(len)"] --> Long{"len >= 256?"}
    Long -- yes --> Build["build the tail once<br/>(3745 log2 calls, collected)"]
    Long -- no --> Keep["keep whatever tail exists"]
    Build --> Loop["per-byte loop: log2(in_window) - log2(histo)"]
    Keep --> Loop
    Loop --> Small{"count < 256?"}
    Small -- yes --> Table["LOG2_TABLE[count]"]
    Small -- no --> Tail{"tail built and<br/>count < 4001?"}
    Tail -- yes --> TailRead["tail[count - 256]"]
    Tail -- no --> Compute["log2(count)"]

is_mostly_utf8 scans a contiguous run in place, counting eight ASCII bytes at a time when a word has no high bit and no NUL — each parses as a one-byte sequence — and falls back to the per-byte masked decoder only for a run that wraps. The reference’s size_utf8 > 0.75 * length is exact in an f64, so it becomes an integer target, the next integer above the product, and either scan stops as soon as the count reaches it or an invalid byte leaves too few bytes for it to be reached. Binary input settles after about a quarter of the run: mapsdatazrh q10 -1.3% instructions.

6. The high-quality meta-block

Three things happen here that the greedy builder does not do.

The distance alphabet is re-chosen per block. Every legal combination of postfix bits and direct codes is priced by building the distance histogram it would produce; the search walks postfix bits outward and direct-code counts upward, carrying an awkward index between rows exactly as the reference does. The commands’ distance prefixes are then rewritten in place.

Literal histograms are gathered per block type and per context — sixty-four of them per type — rather than through a fixed static map.

Everything is clustered. cluster.rs repeatedly merges the histogram pair whose combination saves the most bits, until no merge pays or the format’s limit of 256 is reached. The candidate pairs live in a bounded array with the best one first, which the reference calls a heap and treats as one only at that first position; reproducing that — including which pair is displaced when the array is full — is what keeps the merge order, and therefore the context map, identical.

No histogram is copied to be read. A candidate pair’s combined cost is priced from Histogram::set_sum, which writes left + right into the scratch histogram in one pass, where the reference clones one side and adds the other. A merge adds the absorbed histogram into the survivor through split_at_mut, since pairs are always ordered idx1 < idx2, and remapping adds every input histogram into its cluster straight from the borrowed input.

HistogramPair is #[repr(C)], laid out in declaration order as the reference’s struct is, because the queue compaction after a merge copies whole pairs. population_cost finds the first five used symbols, which decide its closed forms, through first_used_symbols: it skips each block of sixteen unused counts with one combined test instead of a branch per symbol, which matters for the sparse histograms clustering prices.

flowchart LR
    Pair["candidate pair idx1 < idx2"] --> Sum["tmp.set_sum(out[idx1], out[idx2])"]
    Sum --> Cost["population_cost(tmp)"]
    Cost --> Best{"best saving?"}
    Best -->|merge| Split["out.split_at_mut(idx2)"]
    Split --> Add["out[idx1].add_histogram(&out[idx2])"]

flowchart TD
    A["commands"] --> B["choose_distance_params<br/>price every (npostfix, ndirect)"]
    B --> C["recompute_distance_prefixes"]
    C --> D["BlockSplitter::split<br/>literals, commands, distances"]
    D --> E["build_histograms_with_context"]
    E --> F["cluster literals → literal_context_map"]
    E --> G["cluster distances → distance_context_map"]
    F --> H["MetaBlockSplit"]
    G --> H
    D --> H
    H --> I["optimize_histograms"]
    I --> J["MetaBlockWriter::store_meta_block"]

7. The block splitter

block_splitter.rs sees a whole symbol stream at once. It seeds a handful of entropy codes from pseudo-random samples, refines them with more samples, then solves for the cheapest assignment of codes to symbols by dynamic programming, repeats that a few times, and finally clusters the resulting blocks down to at most 256 types.

The sampling generator is seeded at seven and multiplied by 16807. The sequence decides which stretches of the stream seed the entropy codes, so it is part of the output: change it and a different partition falls out.

Switching block type is discounted over the first 2000 symbols, which lets the partition adapt quickly before the statistics settle.

Each split stream keeps a SplitArena. Buffers whose length follows the stream (histograms, costs, block ids and lengths, cluster lists) are retained Vecs; the four per-batch tables of the 64-block pre-clustering (sizes, new_clusters, symbols, remap) always hold exactly 64 entries, so they are inline [u32; 64] arrays zeroed per split. The block ids, insertion costs, running costs, switch bitmap and id remap are resized to the stream without a preceding clear(): find_blocks and remap_block_ids write every entry they later read, so a kept buffer is not zeroed again (the switch bitmap, up to thirteen bytes per symbol, was previously zeroed twice per split). Refinement adds each sample histogram into its target directly. Insertion costs are built row by row: the log2 totals of at most 100 histograms go to a stack array, each symbol’s row is written from it, and its padding lanes are zeroed explicitly. Block lengths come from chunk_by over the assigned ids, whose run count is the block count the trace-back produced, and per-block histograms are counted with add_vector over each block’s slice. Together with clustering without copies, q10/q11 compression runs 0.7-2.3% fewer instructions (callgrind, alice29.txt, mapsdatazrh, 1 KiB and 64 KiB random inputs), with byte-identical output.

flowchart TD
    Ids["block ids after find_blocks + remap"] --> Runs["chunk_by equal ids → block_lengths"]
    Runs --> Batch["64-block batch: add_vector per block"]
    Batch --> Scratch["inline [u32; 64] sizes / new_clusters / symbols / remap"]
    Scratch --> Combine["combine_batch"]
    Combine --> Final["combine surviving clusters"]
    Final --> Assign["assign: add_vector per block, move_cost per cluster"]

8. Context mode

Quality ten is the first quality that considers anything but the UTF-8 literal context model. ChooseContextMode runs BrotliIsMostlyUTF8 over the whole pending meta-block; data that does not look like text is modelled as signed integers instead. The chosen mode reaches both the histogram builder and the bit writer, which stores its two-bit code once per literal block type.

Copy-length pricing uses the shared compile-time class table for lengths 10 through 2117. Short lengths retain direct subtraction and larger lengths use class 23. This preserves the reference classes and floating-point addition order in the Zopfli cost loop.

9. SIMD dispatch

HqEncoder retains the Backend detected when the Compressor was built. Stitching, block assignment and Zopfli reference search each match it with fearless_simd::dispatch! at their block-level call and call #[simd] functions (fearless_simd_macros): stitch_to_previous_block, assign_blocks, create_zopfli_backward_references and create_hq_zopfli_backward_references. Each inner search is monomorphized on that concrete token and on whether a prefix is attached (§11); no block reselects the backend. update_nodes, BinaryTreeMatcher::find_all_matches and BinaryTreeMatcher::store are #[simd] as well, allowing comparisons to inline within these separately compiled functions.

#[simd] makes the body an always-inlined closure and calls it through a feature-enabled entry generated for the token’s level, with each argument passed separately. When LLVM keeps such a function out of line — store runs once per position and is not inlined into the Zopfli loop — the call crosses from a baseline function into the feature-enabled entry at every position. Simd::vectorize passed the captured arguments there as one struct behind a pointer; the macro passes them in registers.

sequenceDiagram
    participant Driver as Zopfli loop (S features)
    participant Store as BinaryTreeMatcher::store (baseline)
    participant Entry as generated entry (S features)
    Driver->>Store: store(simd, data, mask, ix)
    Store->>Entry: token level folds to S, self, data, mask, ix as arguments
    Entry->>Entry: inlined body: store_and_find_matches
    Entry-->>Driver: return
``` The tree traversal is always inlined into
`find_all_matches` or the feature-enabled `store` body, and `scan_recent_positions`
takes the same token for its `u8x32` prefilter, which every backend implements
(the fallback lane by lane). `update_nodes` uses the token the same way for its
`u8x16`/`u32x16` distance-cache prefilter (§4), inlined into its body.
`dictionary::all_matches::find_all` is `#[simd]` too: `find_all_matches`
crosses into its feature entry once per position, and its four word families
are inlined there, so each candidate word — at most 24 bytes — is compared
with one `u8x32` `simd_eq` and the mask's trailing ones. The case transforms
flip the uppercase bit of the word's ASCII lowercase letters (all of them, or
lane 0 alone, which must also be lowercase) before comparing. Fewer than 32
readable bytes on either side — the dictionary's last words, the end of the
input — fall back to the scalar comparison. Quality ten on text: -5.6 to -5.8%
instructions (`alice29.txt`, `lcet10.txt`), quality eleven -2.5%. Copy extension dispatches the retained
backend into `extend_last_command`, as described in
[encoder workspace](encoder-workspace.md).

```mermaid
graph LR
    selected[retained Backend: dispatch! per call] --> stitch[boundary stitching]
    selected --> search[Zopfli search]
    selected --> assignment[SIMD block-assignment forward pass]
    search --> arena[flat retained match arena]
    prefix[retained prefix scratch] --> merge[backwards in-place merge]
    arena --> merge
    merge --> costs[retained costs and nodes]
    costs --> mb[retained MetaBlockSplit and builder]
    mb --> assignment
    mb --> writer[retained entropy-code arrays]

Prefix matches merge backwards into the flat arena tail. Earlier positions remain untouched; equal tree matches precede equal prefix matches, preserving dictionary length codes. No temporary merged vector or split_off allocation is needed. Meta-block splits, histogram clusters, entropy-code arrays and cost histograms survive reset and are included in retained-byte accounting.

Alongside shared find_match_length, the block splitter vectorizes its forward assignment pass. MetaBlockBuilder::build, BlockSplitter::split, and find_blocks take the retained Backend; find_blocks dispatches it. Once insertion costs are prepared, one assign_blocks call enters a feature-enabled loop over the entire symbol stream. No backend detection or dynamic dispatch occurs per symbol.

The borrowed BlockCosts holds f64 insertion costs, mutable accumulated costs, switch bits, and block ids; histogram counts fit in a byte and each symbol addresses a complete row. find_blocks lays rows out at padded_histograms(n), the histogram count rounded up to whole eight-lane vectors (COST_LANES), and the retained arena is sized for the first, largest count of a split. Padding lanes carry a zero price and a NaN cost: NaN < x and NaN >= x are both false, so a padding lane never becomes the minimum, never sets a switch bit and stays NaN, and the scalar oracle over the same padded rows gives the same answer. The switch bitmap keeps ceil(n / 8) bytes per symbol, which the padded width fills exactly; traceback only reads bits of real ids.

Eight histogram lanes update independently with fearless_simd::f64x8. Each lane keeps its first strict minimum and that histogram’s id, carried as an exact small integer in a second f64x8 (ids are below 256; u64 lanes have no vector minimum before AVX-512 and fearless_simd lowers them lane by lane). After the row, reduce_min gives the minimum cost, and a masked reduce_min over the ids of the lanes equal to it gives the smallest tied id — the scalar scan’s tie order, including ties whose smaller id sits in a higher lane of a later chunk. Unclaimed lanes hold NO_HISTOGRAM (+∞), which converts to the u64::MAX id the kernel reports when nothing undercut the 1e99 start. Subtraction and clamping retain the scalar arithmetic order, including the first 2000 symbols’ switch-cost adjustment. Each eight-lane comparison supplies one switch bitmap byte. A row that is not a whole number of vectors (only unit tests pass one) finishes with scalar operations. The fallback backend executes the original scalar pass. Traceback and clustering stay scalar. No public API is introduced. Differential tests compare cost bits, ids, and switch bitmaps on every available backend, including ties, cross-chunk ties, NaN padding, tails, empty streams, and the prologue boundary; full encoder tests also check C output identity.

flowchart TD
    Row["symbol row: padded_histograms(n) lanes"] --> Chunk["per f64x8 chunk:<br/>cost += price, store"]
    Chunk --> Lt{"cost < lane minimum?<br/>(false for NaN padding)"}
    Lt -->|yes| Keep["lane minimum = cost<br/>lane id = chunk id"]
    Lt -->|no| Next[next chunk]
    Keep --> Next
    Next --> Chunk
    Next -->|row done| Min["min_cost = minima.reduce_min()"]
    Min --> Id["best_id = select(minima == min_cost, ids, +inf).reduce_min()"]
    Id --> Sub["per chunk: delta = cost - min_cost<br/>delta >= switch cost → clamp, set bit"]
    Sub --> Out["block_id[byte] = best_id"]

Copy-length codes below 2118 use a compile-time table derived from the format’s copy-length bases. Lengths below ten retain their direct subtraction, and longer lengths retain the final unbounded code. This removes logarithms from repeated Zopfli length pricing without changing the order of floating-point cost sums.

flowchart LR
    Length[Candidate copy length] --> Small{Below ten?}
    Small -->|yes| Direct[Length minus two]
    Small -->|no| Bounded{Below 2118?}
    Bounded -->|yes| Table[Compile-time copy-code table]
    Bounded -->|no| Final[Code 23]
    Direct --> Price[Existing command and distance pricing]
    Table --> Price
    Final --> Price

10. Verification

The shims live in brotli-ffi/shim/, outside vendor/, and expose four encoder-internal functions that have no public header. They exist only so the port can be compared against the reference it was translated from.

10.1. Input sizes in the integration sweeps

These qualities are expensive: in the debug build the tests run in, quality eleven costs about a second per hundred and fifty kilobytes, against a hundredth of that at quality nine. Left unbounded, the sweeps that run every quality over every corpus at every window size take tens of minutes.

support::prefix_for therefore caps qualities ten and eleven at 64 KiB in the sweeps that exist to cover shapes — differential_c, randomized, roundtrip, simd_backends and the per-corpus vendor tests. The cap is under their 256 KiB default block, so those runs exercise a single block only.

Large-input coverage moves to the tests built for it, which run these qualities unbounded:

• vendor_corpus::multi_fragment_input_matches_the_c_encoder — a 2 MiB prefix of bb.binast, eight blocks at their default, at three window sizes.
• streaming.rs — chunk-boundary independence and one-shot equivalence.

The tradeoff is deliberate and worth naming: a regression that needs both a large input and one of the capped sweeps’ shapes would be missed.

11. The attached prefix

An attached RFC 9841 prefix reaches these qualities in three places, all of them the reference’s:

1. Collection. After the binary tree has produced a position’s matches, SharedContextInner::find_all_matches collects up to sixty-four more from the attachments, from a minimum length of three, and merge_prefix_matches merges the two ascending-by-length sequences into one — MergeMatches. The dynamic program then prices them together, indistinguishably.
2. Cached distances. update_nodes gains the branch that the reference’s comment calls the way out of the “gray area”: a cached distance past max_distance but at most dictionary_start is unusable, while one past dictionary_start addresses the prefix and is measured against it. That branch lives in prefix_copy_length, the cold arm the probe loop takes for every distance outside 1..=max_distance. Without an attachment gap is zero, the prefix path is unreachable, and the arm only skips.
3. Coding. gap shifts dictionary_start everywhere a distance is classified, so create_commands marks a prefix reference as a dictionary reference and leaves the distance cache alone, and evaluate_node’s shortcut chain skips it for the same reason.

flowchart TD
    pos["position"] --> tree["BinaryTreeMatcher::find_all_matches<br/>dictionary_start + gap"]
    pos --> pre{"context attached?"}
    pre -->|no| prices
    pre -->|yes| lookup["SharedContextInner::find_all_matches<br/>min length 3, at most 64, dictionary_start"]
    tree --> merge
    lookup --> merge["merge_prefix_matches<br/>ascending by length, then distance"]
    merge --> prices["update_nodes prices every candidate"]
    prices --> cache{"cached distance?"}
    cache -->|"<= max_distance"| ring["measure against the ring buffer"]
    cache -->|"> dictionary_start"| dict["measure against the prefix"]
    cache -->|otherwise| grey["gray area: skip"]

The match itself stops at the end of the attachment it was found in, which is the reference’s limit; only extend_last_command runs on across seams.

Whether a prefix is attached is a type-level choice, as on the greedy path. HqEncoder::create_references dispatches the backend, matches on the quality and on attached.is_some(), and calls create_zopfli_backward_references or create_hq_zopfli_backward_references with const ENABLE_PREFIX: bool. The parameter reaches zopfli_compute_shortest_path, zopfli_iterate and update_nodes. With it false, the entry points replace attached with a constant None, so gap is a constant zero and every prefix test folds away, and the probe loop in update_nodes loses its prefix_copy_length arm. On inputs without a prefix this cut executed instructions by 0.1-2.6% at quality ten and 0.2-2.9% at quality eleven, with identical output.

flowchart LR
    hq["create_references: dispatch!(backend)"] --> q{"quality, attached?"}
    q -->|"Q10, none"| a["create_zopfli_backward_references::<S, false, I>"]
    q -->|"Q10, some"| b["create_zopfli_backward_references::<S, true, I>"]
    q -->|"Q11, none"| c["create_hq_zopfli_backward_references::<S, false, I>"]
    q -->|"Q11, some"| d["create_hq_zopfli_backward_references::<S, true, I>"]

Known gaps

• Large-window history stops at 30 bits. Window::large reaches these qualities and DistanceParams::for_window computes the widened RFC 9841 alphabet and its alphabet_size_limit, but retained history is capped at 30 bits by ResolvedWindow::encoder_bits, so the binary tree never indexes a window wider than that. See shared-brotli.md.
• Custom static dictionaries and offsets are experimental. The immutable flat index merges per-length transformed candidates into Zopfli matches using the current meta-block literal context. Extended packed length modifiers keep long transforms’ base lengths intact. Headerless continuations shift logical dictionary placement but not history availability. See rfc9841-encoding.md for both flows and their limits.
• Histogram merging runs at the baseline instruction set. BlockSplitter::split and the histogram helpers it calls (Histogram::add_histogram, block histogram rebuilds) sit outside every #[simd] region, so on x86-64 their autovectorized loops use SSE2 xmm registers even on AVX2 hosts (about 1.6% of quality 10 on mapsdatazrh). Only the block-assignment pass enters the selected backend. Building the whole program for x86-64-v3 sped qualities 10 and 11 up by at most 2% (i7-13700KF, 2026-10-08), so moving them is not pursued.
• hotpath instrumentation. Encoder block operations, Zopfli search passes, literal-cost estimation, and find_blocks have timing hooks. Individual per-candidate updates and clustering do not have separate timing hooks; sampling or instruction profiling is needed to resolve their costs.

Independent parallel fragments

The parallel fragment adapter builds HqEncoder<true> once per worker. The specialized Zopfli path excludes cache-relative distance edges and dictionary candidates. begin_fragment starts headerless and seeds the ring and literal context from the common raw prefix. The serial specialization retains both search mechanisms. See parallel compression for reset ownership, alignment checks, and current cancellation limitations.