Greedy Encoder Core (qualities 2 to 9)

Scope: src/compressor/core/greedy/. 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. On the platforms this crate targets that build defines BROTLI_MAX_SIMD_QUALITY and therefore selects the tagged H58 and H68 match finders at qualities five and six. This port keeps H5/H6 logical match order, with tag filtering on SIMD backends and an unfiltered scalar oracle. These paths are byte-for-byte equivalent — see §2.2 — and differential tests check that equivalence against the real library.

1. Core mechanics

Where the fast encoder compresses one independent fragment at a time, the greedy encoder is a proper streaming state machine:

1. Input is copied into a ring buffer that keeps the whole sliding window, so a match may reach back past the current block.
2. A match finder, chosen once from the caller’s parameters, turns the new bytes into commands: an insert length, a copy length and a distance.
3. Commands accumulate until a meta-block is worth emitting.
4. The meta-block is split into blocks, each block type gets its own prefix codes, and the whole thing is written to the bit stream — or stored uncompressed when that turns out smaller.

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

    subgraph greedy["compressor::core::greedy"]
        enc["encoder<br/>(GreedyEncoder, dispatch)"]
        params["params<br/>(GreedyParams, HasherPlan)"]
        hash["hashers<br/>(H2, H3, H4, H54, H40/41/42, H5, H6)"]
        refs["backward_references<br/>(greedy search)"]
        score["score<br/>(reference scoring)"]
        ctx["context_model<br/>(literal contexts)"]
        mb["metablock<br/>(greedy builder)"]
        split["split<br/>(greedy block splitters)"]
    end

    subgraph shared["shared"]
        rb["ringbuffer<br/>(RingBuffer)"]
        dict["dictionary<br/>(static words + hash)"]
        cmd["command<br/>(Command, prefix codes)"]
        histo["histogram<br/>(counts, entropy, RLE)"]
        mbs["metablock<br/>(MetaBlockSplit)"]
        bsplit["block_split<br/>(BlockSplit)"]
        bs["bitstream<br/>(MetaBlockWriter)"]
        tables["format<br/>(context LUTs, prefix ranges)"]
        bits["bits (BitWriter)"]
        huff["huffman"]
        ml["match_len"]
        log["fast_log"]
    end

    drv --> enc
    enc --> params
    enc --> rb
    enc --> refs
    enc --> ctx
    enc --> mb
    enc --> bs
    refs --> hash
    refs --> cmd
    refs --> score
    hash --> dict
    hash --> ml
    hash --> score
    mb --> split
    mb --> histo
    mb --> mbs
    split --> histo
    split --> bsplit
    mbs --> bsplit
    bs --> mbs
    bs --> huff
    bs --> bits
    bs --> tables
    ctx --> tables
    ctx --> log
    histo --> log
    cmd --> tables

    classDef greedyNode fill:#f6e8c3,stroke:#8a6d3b;
    class enc,params,hash,refs,score,ctx,mb,split greedyNode;
    classDef sharedNode fill:#e8f0f6,stroke:#3a6d8a;
    class rb,dict,cmd,histo,mbs,bsplit,bs,tables,bits,huff,ml,log sharedNode;

The shaded modules on the right are shared with the high-quality encoder; see hq-encoder.md.

1.1. What each quality adds

Qualities two and three use simpler meta-block storage and flush on a symbol count. Quality two selects H2 and store_meta_block_fast; quality three selects H3 and store_meta_block_trivial. Their intermediate command generation is shared. From quality five through nine the search shape is shared, with depth controlled by quality.

Because the fixed distance code store_meta_block_fast may fall back to is built for the RFC 7932 alphabet, quality two cannot carry a large window; GreedyParams::new refuses one, the same way FastEncoder::new does for qualities zero and one.

2. Parameter resolution and the hasher plan

Everything that decides what the encoder does is resolved once, before any loop runs, by params::GreedyParams::new. Nothing about the running machine takes part, which is what makes the output identical across SIMD backends.

flowchart TD
    q["quality"] --> plan{"which quality?"}
    plan -->|2| h2["H2"]
    plan -->|3| h3["H3"]
    plan -->|4| q4{"size_hint >= 1 MiB?"}
    q4 -->|no| h4["H4"]
    q4 -->|yes| h54["H54"]
    plan -->|5 to 9| q5{"lgwin <= 16?"}
    q5 -->|yes| chain["forgetful chain<br/>H40 / H41 / H42"]
    q5 -->|no| big{"size_hint >= 1 MiB<br/>and lgwin >= 19?"}
    big -->|yes| h6["H6"]
    big -->|no| h5["H5"]

    classDef fixed fill:#d9ead3,stroke:#38761d;
    class h2,h3,h4,h54,chain,h5,h6 fixed;

The depth of whichever matcher is chosen then follows the quality: the bucket matchers take block_bits = quality - 1, and the chain matchers take max_hops = (quality > 6 ? 7 : 8) << (quality - 4).

ChooseHasher sets the type to the quality itself below five, which is where H2, H3 and H4 come from.

Each plan is a distinct Rust type — QuickMatcher<BUCKETS, SWEEP_BITS, HASH_LEN, USE_DICTIONARY, COMPACT>, BucketMatcher<HASH64, BUCKETS, BLOCK, SLOTS> or ChainMatcher<NUM_BANKS, BANK_BITS, LAST> — so the hash width, the table size and, for the bucket matchers, the block depth are compile-time constants inside the probe loop; each bucket quality is its own MatchFinder variant (§2.3). The MatchFinder enum that selects between them is matched once per input block, never per candidate.

The chain depth is an ordinary field used as a loop bound. The cached-distance count is not: as the reference’s NUM_LAST_DISTANCES_TO_CHECK, it is the chain matcher’s LAST parameter, so H40 (four), H41 (ten) and H42 (sixteen) are separate MatchFinder variants and each probe loop has a constant trip count with no bounds check on the cache. The bucket matchers derive their cached-distance count from the block depth.

H2 and H3 share a shape but not a path: with one slot per bucket the probe has no loop to leave, so the reference returns as soon as it has a match and reaches the static dictionary only by falling out of the bottom. H3 never consults the dictionary, so that distinction is invisible there; H2 does, so the single-slot branch must fall through rather than return — the two are the only matchers where the difference is observable.

The chain matcher’s addresses, heads, tiny hashes, bank offsets and free-slot indices are boxed arrays with compile-time lengths, allocated when the matcher is created. Its slots remain a Vec<ChainSlot>: activating a previously unused bank grows that pool. Logical resets retain both fixed tables and activated banks.

H40 and H41 have a single bank, which every store reaches, so the matcher materializes it when it is created and activate_bank folds to offset zero. H42 keeps lazy activation, so a cold call on a short input still allocates only the banks it touches; the growth path is a separate #[cold] function. Keeping that call out of the search and store loops matters: a call that may reallocate slots, reachable from inside the loop, makes the compiler reload every table pointer from the matcher after each store.

The hop loop mirrors the reference’s walk with three changes that leave every result identical:

• the bank is borrowed once per search as a slice of exactly BANK_SIZE entries, so the masked slot index needs no bounds check;
• the candidate filter compares the four bytes that end at offset best_len, and the current position’s side of that compare is read only when best_len changes;
• both sides are read from MatchQuery::window, the ring buffer cut to the mask, so at < window.len() is both the reference’s at <= ring_buffer_mask test and the bounds proof for the read. When the current side falls outside the window, no later candidate can be longer, and the walk stops.

2.2. The tagged matchers

The reference builds H58 and H68 in place of H5 and H6 whenever BROTLI_MAX_SIMD_QUALITY is defined, which on GCC and Clang covers qualities five and six. Those variants store a one-byte tag beside every position and visit only the slots whose tag matches. The bucket matcher keeps tags for the same two qualities (block depth 16 or 32, a compile-time property of the shape). tag_equality is generic over the block width and compares a whole bucket’s tags with one safe fearless_simd vector — sixteen or thirty-two lanes, the only two widths that survive monomorphisation; rotate_candidates drops unfilled slots and rotates the result right by the newest slot, so bit age of the mask names the slot age stores older than the newest one, and one loop over ascending bits walks the bucket newest to oldest — the reference rotates its mask the same way. Slots fill downwards from the top of a block, as the reference’s tagged matchers do, which is what makes that walk a plain rotation. The scalar backend deliberately keeps the unfiltered scan as an independent oracle, and so do a sixteen-slot starter block and the compact layout’s chain walk. Filtering preserves the accepted-match sequence:

• They select the same bucket. The tagged HashBytes keeps eight more low bits, which the key shifts straight back off.
• They walk the bucket newest to oldest, as the untagged loop does.
• H5 tags depend on the first four bytes. H6 hashes five bytes; within an equal bucket, equal first-four-byte prefixes force the fifth byte to agree (the odd multiplier maps its contribution injectively into the high eight bits). Tag rejection therefore cannot discard a candidate accepted at length four.
• Both stop at the first candidate beyond max_backward, and positions grow monotonically along the ring, so both stop having seen the same prefix.

The accepted-match sets coincide. tests/differential_c.rs checks the consequence directly: qualities six and seven are compared against a C library that really is using the tagged matchers.

2.3. Storage layouts, runs and sweeps

Every bucket shape is its own type: BucketMatcher<HASH64, BUCKETS, BLOCK, SLOTS> takes the bucket count, block depth and total slot count as constants, so MatchFinder holds ten bucket variants (H5Q5–H5Q9, H6Q5–H6Q9) rather than three. The depth is the quality less one, and it fixes the rest of the shape: how many cached distances a search probes (last_distances_for: four up to thirty-two slots, ten up to 128, sixteen beyond) and whether slots carry tags (depth at most thirty-two). With both constants every slot mask, block index and hash shift is an immediate, and the dense tables are arrays whose indexing needs no runtime shape check.

SLOTS is supplied separately because stable Rust cannot express a product of generic constants in an array type. BucketMatcher::new checks SLOTS == BUCKETS * BLOCK in an inline const assertion, so an inconsistent shape fails at compilation. The hash helper uses only HASH64 and BUCKETS; runs keep their existing nested array views and do not carry the storage-size parameter. The inlined fixed_table(initial), shared from crate::shared::fixed with the high-quality cost model, creates an initialized vector of the final length and converts it to a boxed array. The separate inlined fixed_table_from_vec(values, initial) always resizes the supplied vector, including an empty one, before transferring ownership into a boxed array. Neither conversion copies elements. Dense construction establishes all tables; subsequent preparation only clears counters. dense_run returns DenseRun directly: the total array lengths fix the nested array views, so their checked TryFrom conversions fold away in optimized code. The run borrows existing counters, positions and optional tags without allocation or copying. Tagged shapes forward the optional tag reference; untagged shapes supply None without reading the tag pointer. visit_run passes the result directly to its visitor without an outer Option check.

flowchart LR
    Layout["DenseLayout: fixed boxed arrays"] --> Run["dense_run: borrow counters and reshape positions"]
    Layout --> Tags{"BLOCK <= 32?"}
    Tags -->|yes| Borrow["Map optional tag array to nested view"]
    Tags -->|no| None["No tag pointer read"]
    Borrow --> Run
    None --> Run
    Run --> Visitor["visitor.visit: direct DenseRun"]

The reference allocates every bucket’s block up front and never initialises it, reading a slot only below the counter that guards it. Safe Rust has to initialise what it reads, so the bucket matcher picks a layout per stream from what prepare is told about it:

BucketMatcher owns only Layout<BUCKETS, BLOCK, SLOTS>, the retargetable size hint, and the saturating stream count. Each enum variant owns its own storage: CompactLayout has the key map and linked positions; SparseLayout has the boxed index, generation and full/starter pools with optional tags; DenseLayout has Box<[u16; BUCKETS]> counters, Box<[u32; SLOTS]> positions and optional Box<[u8; SLOTS]> tags, absent for untagged shapes. retained_bytes counts array lengths and growable vector capacities, only for the active variant’s allocations. The initial compact variant has no allocations.

graph TD
    Fresh["New table"] --> Allocate["fixed_table: vec of final length"]
    Existing["Existing Vec"] --> Resize["fixed_table_from_vec: resize"]
    Allocate --> Fixed["Box of fixed-size array"]
    Resize --> Fixed
    DenseLayout --> Counters["Box of u16 array: BUCKETS counters"]
    DenseLayout --> Positions["Box of u32 array: SLOTS positions"]
    DenseLayout --> Tags["Optional box of u8 array: SLOTS tags"]
    ChainMatcher --> Tables["Fixed boxed tables: addresses, heads, hashes, bank metadata"]
    ChainMatcher --> Slots["Vec of ChainSlot: H40/H41 bank at creation, H42 banks on first use"]

Dense stores

A dense store bumps the bucket’s u16 counter and writes the position into the slot below the previous one (!count & (BLOCK - 1)), plus the tag on tagged shapes. The shallow tagged shapes (q5 and q6, sixteen and thirty-two slots) address both tables with one flat index key * BLOCK + slot, masked to BUCKETS * BLOCK, a power of two checked at compile time; the deep untagged shapes keep the [[u32; BLOCK]; BUCKETS] row view. Measured with callgrind under lzbench’s fat-LTO profile, the flat index is 1.3% and 1.6% fewer instructions at q5 and q6 and 0.9% more at q8, which is why it is limited to the tagged shapes.

DenseRun::store_range, which records every position a match covered, reads its eight-byte hash inputs from one slice when the range does not wrap the ring and the slice reaches seven bytes past the range’s last position. The positions then hash consecutive bytes, so windows(8) hands the same words store would read, without a bounds check per position; store itself may also read past the mask into the tail copy, so the two agree there too. A range that crosses the mask would read the tail where store reads the ring’s start, and takes the per-position loop. Only the deep untagged shapes take the slice path: for the tagged q5 and q6 loop it measured 3% and 2% more instructions.

flowchart TD
    range["store_range(start, end)"] --> deep{"BLOCK > 32<br/>(untagged q7–q9)?"}
    deep -->|no| each["store each position:<br/>masked eight-byte read, dense_store"]
    deep -->|yes| wraps{"start & mask + count <= mask + 1<br/>and data holds count + 7 bytes?"}
    wraps -->|no| each
    wraps -->|yes| slice["windows(8) over one slice:<br/>hash each word, dense_store"]

Explicit SIMD quick range stores

commit_match passes the search loop’s existing SIMD token to MatchRun::store_range_simd. Its default implementation delegates to the baseline range operation; QuickRun overrides it for both full tables and compact maps. Backend detection stays at the encoder entry. The range wrapper chooses its path before the loop: fewer than sixteen positions, a scalar backend, SSE2, or big-endian targets use the bounded baseline. SSE2’s emulated wide products were slower in the measured workload. Other available backends use the explicit fearless_simd kernel for contiguous ranges.

store_range_vectorized is an out-of-line #[simd] entry so vector temporaries do not extend the search loop’s register requirements. It borrows one bounded slice and advances sixteen-byte windows by eight bytes. quick_hashes8 loads u8x16, duplicates and swizzles its bytes into eight overlapping little-endian words, then multiplies and shifts u64x8. This computes the same hashes as the scalar oracle without gather loads. Eight explicit scalar writes commit the keys in ascending position order: colliding slots must retain the last write, including probing and overwrites in compact maps. Scatter stores are not used. On AArch64, multiplication remains vectorized while the high-bit fields are extracted from the eight product lanes before the ordered writes. This avoids Neon’s variable-shift intrinsics, which Miri cannot interpret, without a Miri-specific production path or skipped SIMD tests. Other architectures use the vector shift directly.

Eight hashes need fifteen input bytes. A final full batch uses a sixteen-byte load only when the extra physical byte exists; that byte never contributes to a hash. Otherwise at most eight bounded, explicitly unrolled scalar stores finish the range. Wrapped ranges or missing lookahead delegate to store_range, whose scalar implementation also serves administrative/history stores and the independent differential oracle. The sparse layout’s store_range places each position through SparseLayout::place, which is push without the store counter, and adds the range’s length to the counter once: the counter sits behind the same reference as the pools a store writes, so counted per store its read-modify-write would chain every store of the range to the one before. No unsafe loads or public API changes are introduced.

flowchart LR
    Search[search_positions with selected SIMD token] --> Commit[commit_match]
    Commit --> Range[MatchRun store_range_simd]
    Range --> Eligible{QuickRun, supported backend, little endian, at least 16 positions?}
    Eligible -->|no| Baseline[bounded scalar store_range]
    Eligible -->|yes| Vector[outlined SIMD feature entry]
    Vector --> Contiguous{range and lookahead fit?}
    Contiguous -->|no| Baseline
    Contiguous -->|yes| Hash[u8x16 load and swizzle; u64x8 multiply and shift]
    Hash --> Store[eight ordered slot overwrites]
    Store --> Hash
    Store --> Tail[bounded scalar tail]

Compact key-map growth

KeyMap::reset clears the existing words, then resizes only up to the larger of its current length and the requested power-of-two length. It retains capacity and initializes newly added words to the empty sentinel. Normal compact inputs are pre-sized to at least two slots per input byte, so grow is a fallback; reused streams of increasing short lengths exercise the reset growth path.

KeyMap::grow doubles the logical length with Vec::resize and rebuilds the open-addressed index in the same vector. Capacity already sufficient for the new length means no allocation; otherwise the allocator may extend or move the buffer. No separate destination vector is created.

Rehashing starts immediately after an empty slot in the old table and visits exactly the old length of slots, wrapping with the old mask. The table is at most half full, so such a slot exists whenever the table is nonempty. This traversal visits each old probe cluster in order. Each entry is removed before reinsertion using the new mask; its destination is in the new half or an already visited old slot. Unread entries cannot be overwritten or mistaken for reinserted entries. The count is rebuilt, and packed keys, counters and chain offsets are preserved. An initially empty table grows to 64 empty slots without a rehash loop.

flowchart TD
    Old["Find an empty slot in the old table"] --> Resize["resize to max of twice old length and 64"]
    Resize --> Count["Reset count; begin after old empty slot"]
    Count --> Next{"Old slots left?"}
    Next -->|yes| Take["Take current entry; leave empty sentinel"]
    Take --> Present{"Entry occupied?"}
    Present -->|yes| Insert["Reinsert using new mask; rebuild count"]
    Present -->|no| Advance["Advance with old mask"]
    Insert --> Advance
    Advance --> Next
    Next -->|no| Ready["All keys reachable in resized table"]

Layout changes occur during prepare, between independent streams, and at a sparse stream’s mid-stream checkpoint, which only ever turns sparse into dense (see Mid-stream promotion). Compact resets reuse its map and chain. Once sparse or dense storage exists, even a tiny one-shot stream keeps it; dense never demotes. Compact-to-sparse moves the larger of the map and chain’s Vec<u64> allocations into the index, clears its previous encoding, resizes it to BUCKETS, and converts it to a boxed array. Growing or shrinking that allocation may relocate it. Sparse-to-dense uses safe Vec::into_flattened to transfer the larger position pool (full or starter) and the larger tag pool without copying, then resizes them to BUCKETS * BLOCK before converting to boxed arrays using the safe TryFrom conversion. Exact final capacity preserves their addresses; growing or shrinking the allocation may relocate it. Dense preparation thereafter clears only counters and retains the fixed-size position and tag allocations. The smaller pools and the sparse index are released. Compact-to-dense allocates new typed buffers. No unsafe type punning is used. Every transition resets counters or stamps before old slots can be read; it transfers storage, not a previous stream’s match history.

stateDiagram-v2
    [*] --> Compact: empty buffers
    Compact --> Compact: one-shot input at most 1024 bytes / reset map and chain
    Compact --> Sparse: below dense threshold / reuse larger u64 buffer
    Compact --> Dense: dense threshold reached / allocate typed tables
    Sparse --> Sparse: below dense threshold / advance generation
    Sparse --> Dense: dense threshold reached / flatten larger pools, resize and convert to fixed arrays
    Sparse --> Dense: checkpoint mid-stream, store rate repays the clear / copy live buckets and tags into a fresh table
    Dense --> Dense: every subsequent stream / clear counters

Mid-stream promotion

The static dense limits are set by the table’s size, not by the input: a q6 stream below 128 KiB and a q7 or q8 first stream below 1 or 2 MiB start on the sparse layout, which costs no clear but pays a dependent index load and block bookkeeping at every store and search. Whether that overhead outgrows the clear depends on how much the stream stores, which only the stream itself reveals: text stores about one position per input byte, incompressible input about a third (the random-data heuristic strides over the rest), and long repetitive copies almost none.

Matcher::checkpoint(position, remaining) lets a matcher act on that. The default returns usize::MAX (never call back). BucketMatcher answers usize::MAX for the compact and dense layouts; on its sparse layout it counts the stores made since its previous checkpoint (SparseLayout::stores, one increment per store, reset with the generation at prepare) and predicts the rest of the stream at that rate. The rest is the size hint less the position, or the current block’s remainder when that is larger or no hint was given. When

stores × remaining ≥ span × SLOTS / PROMOTION_SLOTS_PER_STORE

(32 for the deep shapes, 16 for the tagged ones, whose shallow blocks save less per store while the copy weighs more against a 1–2 MiB table) it builds a fresh dense table (DenseLayout::from(&SparseLayout): each live bucket’s counter, its full block, or its starter’s sixteen slots at the top of the block — where the seventeenth store would have moved them — with the same for its tags, and nothing from a stale generation), drops the sparse storage, and returns usize::MAX. Otherwise it asks to be called again after CHECKPOINT_INTERVAL (16 KiB) more positions. The first checkpoint of a stream has no interval to judge and only records its starting point. The interval is long enough that a repetitive input, which stores at almost every position of its first few kibibytes and then copies to its end, usually reaches that copy before it is judged. Lower bars switched incompressible and repetitive inputs whose store rate later falls, and doubled their time; at the chosen bars no measured input got slower.

sequenceDiagram
    participant CBR as create_backward_references
    participant M as BucketMatcher
    participant Driver as SearchLoop (per run type)

    CBR->>M: checkpoint(block start, block bytes)
    M-->>CBR: CHECKPOINT_INTERVAL or usize::MAX
    loop until position + hash length reaches the block end
        CBR->>M: visit_run(SearchLoop { yield_at: position + interval })
        M->>Driver: visit(SparseRun or DenseRun)
        Driver-->>CBR: cursor (stopped at yield_at or the block end)
        opt not at the block end
            CBR->>M: checkpoint(cursor.position, block remainder)
            alt store rate repays the clear
                M->>M: Sparse → Dense (copy live buckets)
                M-->>CBR: usize::MAX
            else
                M-->>CBR: CHECKPOINT_INTERVAL
            end
        end
    end

Candidate sets and their order are the same in both layouts, so a switch — or none, or one at another position — never changes the output; the differential tests and a unit test that resumes the loop at every position check exactly that.

The dense decision uses the current retargetable size hint, not prepare’s one_shot flag. Unknown-length streams use dense storage on tagged shapes and on-demand layouts on deep shapes. Every shape’s length threshold drops to a sixty-fourth of the table once the matcher has been reused: the table is then zeroed once and later streams only clear its counters. Reused q6 on 64 KiB of incompressible input measured 115 us on demand and 67 us with the table (C 85-92 us); reused text, JSON and repetitive input were unchanged, since the sample already gives them the table or keeps them on demand. The cost is retained memory: a q6 compressor reused on such input now keeps about 3.5 MiB instead of 1.4 MiB, what it already kept for text of the same size. These layout choices preserve candidate order and output; allocation timing is not part of the public reuse contract.

Sampling the first block

Which layout is cheaper depends on how many positions the stream stores, and that depends on the data more than on its length: text, markup, JSON and binary formats store at almost every position, incompressible input about a third as often once the random-data heuristic skips, and repetitive input almost never, because long copies cover it. A tagged shape (q5, q6) whose size is known therefore samples the block prepare receives (greedy::probe::sample_store_outlook) once the input reaches ORDINARY_DENSE_LIMIT, a hundred-and-twenty-eighth of the table:

flowchart TD
    start[BucketMatcher::wants_dense] --> deep{deep shape or unknown length?}
    deep -->|yes| length[size hint at least dense_limit: table/64 once reused]
    deep -->|no| small{input below table/128?}
    small -->|yes| sparse[on demand]
    small -->|no| sample[sample 256 eight-byte windows of the first block]
    sample --> rep{half the windows repeat?}
    rep -->|yes, block at least half the input| sparse
    rep -->|yes, input outruns the block| length
    rep -->|no| entropy{at least 7.6 bits per sampled byte?}
    entropy -->|incompressible| length
    entropy -->|ordinary| dense[dense table]
    sample -->|block shorter than a window| length

Repeats are counted against a 4096-bit filter, so a stray collision adds about one window in thirty; ordinary data repeats at most an eighth of its windows at this sampling and repetitive data four fifths or more. The byte histogram for the entropy is built only after the repeat check, because a run of one byte would chain every increment through one counter. The sample costs 0.3-1 us, once per stream. Cold one-shot measurements behind the limits: ordinary data took the dense table faster from 8 KiB at q5 (0.84-0.94 of the on-demand time) and 16 KiB at q6 (0.86-0.98), 0.72-0.89 from 32 KiB; repetitive data lost two to twelve times with it at every size to 128 KiB, but backward65536 cycled to 256 KiB, whose first 64 KiB are runs, stores along its 64 KiB-distant copies and lost half again its time without the table, hence the coverage condition. Deep shapes measured within a few per cent either way on ordinary data and split on repetitive data, so they keep the length rule. Like every layout choice this changes no output. Sparse pools normally grow geometrically. When a pool has promoted 1024 starter blocks, reserve_populated_blocks reserves from the current size hint to avoid repeatedly copying a populated pool. The estimate is one full block per sixteen input bytes, rounded down to a power of two and capped at 16384 blocks and the shape’s bucket count. Unknown hints reserve nothing. This changes capacity only: the fifth store still promotes each starter, tags stay alongside positions, and generation stamps and candidate order are unchanged. The cap limits speculative reservation on large compressible inputs; pools can still grow beyond it on demand. Existing capacity is retained across resets. The size hint itself is retargetable: a reused encoder whose new hint resolves to the same shape and the same match-finder variant takes the hint over (GreedyEncoder::retarget, MatchFinder::retarget) instead of being rebuilt, so a compressor fed inputs of varying lengths keeps its tables; only a hint that crosses the quick matchers’ 2048-byte compact boundary, or changes the plan, still rebuilds. A session of unknown length retargets the same way when it infers its hint before its first encode (Encoder::retarget_size_hint), with the hint and the expected input passed separately: the hint resolves GreedyParams (plan and context-map gate), the expected input the finder variant, layout and window capacity (GreedyEncoder::expecting, GreedyEncoder::retarget(fresh, expected_input)). A rebuild there takes over the header bits an empty first flush already wrote (GreedyEncoder::adopt_stream_head). QuickMatcher::new allocates no full table: the constructor of an encoder that knows its size, or retarget_size_hint for one that inferred it, calls materialize before the window is allocated, so a matcher rebuilt for the quick small-input variant costs no zeroed allocation and the table still comes from fresh pages; prepare allocates one only if neither ran. The table is kept flat on purpose: a zero-filled vector of integers, converted to a boxed array at its final length, comes straight from the allocator’s zeroed pages, whereas a vector of arrays longer than sixteen elements is written out element by element, which for the two-mebibyte quality-six table cost more than compressing a hundred kibibytes. A sparse entry from an earlier generation still names its block but counts as empty, so blocks persist across streams; a compressor that holds the dense table uses it for every later stream, because clearing its counters is cheaper than the on-demand layouts’ extra dependent load per bucket. Every layout empties itself in time that does not depend on what the previous stream stored, which is what the [Sweep::SelfCleaning] result of prepare tells the encoder.

Matcher::prepare reports one of three sweeps, and the encoder records what a reset then has to do: Partial (quick and chain matchers on a short one-shot input) is replayed at reset, because it clears exactly the slots the stream could have dirtied; Full leaves the table dirty, so the next stream is not one-shot and pays for a wipe; SelfCleaning needs nothing. The quick matchers are QuickMatcher<BUCKETS, ...> with their table as a boxed array; a compact quick matcher (size hints up to 2048 bytes) indexes a SmallSlots map for its first stream only, sized for the input so it never rehashes mid-stream, and allocates the table when the replay sweep after that stream asks it to clear, from which point it is cleared by the partial sweep like any other. A map entry is one word — the slot above the position plus one, zero when empty — so clearing it costs half of what a two-word entry did; the packing needs positions below 32767, so prepare allocates the table instead of the map for a stream that is not one shot or is longer than that. The single-slot shapes read and overwrite the same slot at every position and do both with one probe (QuickSlots::replace).

SmallSlots::reset(input_size) reserves at least twice as many entries as input positions before a run starts. Each position selects one deterministic logical slot, including swept shapes; revisiting that position overwrites the same key. The map therefore stays at most half full without a population counter or growth check on each store. A compact run is restricted to a fresh final block at position zero. Nonfinal blocks, prepended history, oversized input and reused streams select a full table before any stores or boundary stitching. Only preparation may resize the map; its capacity and mask remain fixed during the search. The compact/full differential test must prepare the compact side with clear=false: a dirty preparation intentionally materializes a full table.

flowchart TD
    Prepare[QuickMatcher prepare] --> Eligible{fresh one-shot final block and bounded positions?}
    Eligible -->|no| Full[materialize full table before stores]
    Eligible -->|yes| Reserve[reset map with at least twice input_size entries]
    Reserve --> Run[fixed capacity during searches and range stores]
    Run --> Bound[one key per position; at most half full]
    Bound --> Reuse[next stream requests clearing]
    Reuse --> Full

The reference hoists its table pointers into restrict locals for a whole block, so a store through one never makes the compiler reload the others. The RunVisitor trait is the same idea: Matcher::visit_run binds the tables once per input block and hands the visitor — the search loop — the concrete view its layout uses, so the loop is compiled once per view rather than once over a union of them:

Dense runs repeat the BLOCK <= 32 tag invariant at search, store and prefetch call sites. Deep layouts already construct no tag storage; making that constant visible inside the SIMD feature entries removes optional-tag branches and pointer lifetimes from qualities 7–9. The generic dense_store helper still honors a supplied tag array, including in its standalone tests.

flowchart LR
    prepare[prepare: one-shot? input length; size hint; tables held] -->|still compact and at most 1024 bytes| compact[Compact: key map + one chain of nodes]
    prepare -->|known short input, repetitive or incompressible tagged input below the limit, or unknown length on a deep shape| sparse[Sparse: stamped entries + typed pools]
    prepare -->|ordinary tagged input from table/128, size hint at least the dense limit, unknown length on a tagged shape, or table held| dense[Dense: counters and flat key-addressed blocks]
    compact --> run[Matcher::visit_run binds one concrete run for the block]
    sparse --> run
    sparse --> checkpoint{checkpoint: store rate repays the clear?}
    checkpoint -->|yes, mid-stream| dense
    sparse --> promoted{1024 full blocks reached?}
    promoted -->|yes| reserve[Reserve bounded pool capacity from size hint]
    reserve --> run
    dense --> run
    run --> search[find_longest_match: cached distances, tag mask, candidates, one index lookup per position]
    run --> store[store / store_range through the run]
    prepare -. Sweep::SelfCleaning .-> reset[reset: nothing to replay]

2.4. The distance cache

The outlined accept_cached and accept_candidate measurement helpers return an optional pair with a NonZeroUsize score. A winning score is strictly greater than the current unsigned score, so zero cannot represent an accepted match. The niche lets the x86-64 build return the pair in registers without a separate option tag or a caller-provided return buffer. Ring positions and remaining block lengths cross this private helper boundary as u32: the largest ring has 31 address bits and a block has at most 24 length bits. Widening them inside the helper makes these bounds visible to the optimizer while preserving safe slice checks. This is unrelated to the logical stream position, which can span many ring wraps. SIMD selection still happens above the search loop; each helper receives the already selected S token.

Qualities seven and above probe more than the four remembered distances. The extra entries are near misses derived from the two freshest ones — one, two and three either side — which prepare_distance_cache fills whenever the remembered four change. Only those four survive a meta-block; the rest are rebuilt before any search reads them, which is why saved_dist_cache is four wide.

Most cached probes fail on one byte, the byte at cur_ix + best_len that a longer copy would have to repeat. For the shapes that probe the derived distances (blocks above 32 slots: ten probes at qualities seven and eight, sixteen at nine), probe_derived_distances tests them all at once through the private compressor::core::cache_probe module the high-quality search shares (see hq-encoder.md §4). The derived near misses are seven adjacent ring bytes around each of the two freshest distances, so two eight-byte reads and the two single bytes of the third and fourth distances fill one u8x16; one simd_eq against the continuation byte and one u32x16 range test over the cache give a candidate mask in index order. Each candidate still runs the exact scalar filter and accept_cached, lowest index first; when a copy is accepted, the indices after it are filtered again at the new length, which is the order and the information the reference’s loop uses. A run that would wrap around the ring mask, or read past the bytes the ring holds, is let through whole. Without the second run (ten probes), code 1’s byte is read on its own. The mask is a superset of the scalar filter’s admissions only when the cache holds prepare_distance_cache’s entries; a debug assertion checks that, and the search tests prepare their caches as the encoder does. Four-probe shapes and the scalar backend keep the plain loop. The vector range test loads the signed cache directly with i32x16::load_array_ref, then uses Bytes::bitcast to interpret its unchanged bits as u32x16. Zero and negative distances retain their rejection semantics. No owned array mapping or intermediate element conversion is needed; the selected backend owns both the load and range test.

flowchart TD
    Q[find_longest_match] --> Count{"probes > 4 and SIMD backend?"}
    Count -->|no| Plain[scalar loop over the probes]
    Count -->|yes| Cont{continuation byte in the window?}
    Cont -->|no| Bucket[bucket scan]
    Cont -->|yes| Mask["cache_probe: u8x16 byte compare + u32x16 range test -> index mask"]
    Mask --> Next{candidate at or after next_index?}
    Next -->|no| Bucket
    Next -->|lowest| Exact[exact scalar filter]
    Exact -->|rejected| Next
    Exact -->|passes| Accept{accept_cached scores it higher?}
    Accept -->|no| Next
    Accept -->|yes| Raise["best_len = len; next_index = index + 1"]
    Raise --> Cont
    Plain --> Bucket

Instructions for one compression (callgrind, default release profile) against the plain loop: q7 -5.8 to -7.7%, q9 -8.1 to -15.5% on alice29.txt, lcet10.txt and mapsdatazrh; q8 -0.9% and -4.4% on two of them and +0.9% on lcet10.txt, where inlining the filter costs the bucket loop more register pressure than the probes save. Outlining it was worse on every case.

The distance alphabet is resolved in the same pass: font mode asks for one postfix bit and twelve direct codes, every other mode uses what the caller configured, and qualities below four always use neither.

2.5. Bucket prefetch

From quality six up the bucket tables outgrow the L2 cache (2.5 MiB at six, 8 to 32 MiB at seven to nine), and the load of a bucket’s newest slot was the single most sampled instruction of the search. The reference prefetches the bucket, the next sixteen slots and the tag row at the start of each FindLongestMatch. Here the hint is issued one search earlier: every iteration of search_positions first calls MatchRun::prefetch for the following position, and commit_match does the same for the position after the match before store_range records the match’s bytes. The dense and sparse runs hash that position, read its counter or sparse entry, and hint the lines holding the newest slot, the slot sixteen older (blocks deeper than sixteen) and the tag row; the other runs keep the trait’s empty default, since their tables fit in L2. A prefetch at search start, as in C, measured slower on binary input (q7 +2%) than this.

The hint is shared::baseline::prefetch, a read hint into L1 through branches (prefetcht0 on x86-64, prfm pldl1keep on AArch64; see shared-primitives.md). It is a read hint although the bucket is later written: the search reads it first, and the store finds the line already exclusive to the encoder’s thread. It never changes a result, so output is unchanged. Buckets deeper than 32 slots get two of their lines, as in the reference.

sequenceDiagram
    participant L as search_positions
    participant R as DenseRun / SparseRun
    participant C as cache
    L->>R: prefetch(position + 1)
    R->>C: prefetch L1 (newest slot, slot + 16, tag row)
    L->>R: find_longest_match(position)
    Note over R,C: bucket for position was hinted one iteration earlier
    alt match found
        L->>R: prefetch(position + len)
        L->>R: store_range_simd(selected token, match bytes)
    end

3. Streaming lifecycle

stateDiagram-v2
    [*] --> Empty: GreedyEncoder::new
    Empty --> Buffering: encode_block(input, false)
    Buffering --> Buffering: meta-block not due yet
    Buffering --> Emitting: is_last, or a flush condition fires
    Emitting --> Buffering: meta-block written, is_last = false
    Emitting --> Finished: meta-block written, is_last = true
    Empty --> Finished: encode_block(&[], true)
    Finished --> [*]

    note right of Buffering
        commands accumulate,
        encode_block returns no bytes
    end note
    note right of Emitting
        one meta-block, then
        num_literals and commands reset
    end note

A meta-block is emitted when any of these holds, mirroring EncodeData:

• this is the last block;
• a quality that does not split blocks — two or three — has buffered 0x2FFF literals and commands together;
• the caller asked for a flush, which forces the meta-block out and then realigns the stream to a byte boundary; see compressor.md §3.1;
• another whole input block would not fit inside the largest meta-block;
• buffered literals or commands reached an eighth of the largest meta-block.

Because encode_block may return nothing, the driver and both streaming adapters treat an empty result as normal rather than as end of stream.

4. Command generation

backward_references::create_backward_references is the port of CreateBackwardReferences, and its decision order is the compression format’s semantics: which candidate wins, when a match is delayed by a byte, which positions are stored and which are skipped are all visible in the output.

create_backward_references resolves the loop-invariant Block, refreshes the distance cache, and runs the loop through Matcher::visit_run as the SearchLoop visitor, so the loop is monomorphised per concrete run (§2.3). The loop stops at the first of the block’s searchable end and the position the matcher’s last Matcher::checkpoint allowed — one precomputed bound, so a matcher that never asks to be called back costs the loop nothing — and create_backward_references then checkpoints and re-enters visit_run with the cursor, which is how a sparse bucket matcher switches layout mid-block (§2.3). Block::store_end is derived from the block’s first position on every entry, so a resumed loop bounds its stores exactly as an uninterrupted one would. The loop body is split in two functions. The search at every position stays in the loop; everything a found match entails — the delayed search, the distance cache update, the command and the stores — lives in commit_match, which re-enters the SIMD feature context and is left for the compiler to inline. Both feature-context closures move their captures: the context is a separate function, and a capture by reference is a pointer it dereferences at every use, where a moved value is a local it keeps in a register. The loop’s state (position, insert length, the random-heuristics horizon, the matcher run) is passed to the commit path by value and back, so nothing in the hot loop has an address the compiler must keep current in memory. The static-dictionary probe likewise works on a copy of the search result.

The query a search receives derives its rare-path values on demand rather than carrying them: MatchQuery::dictionary_start computes the capped distance to the start of the stream only for the dictionary probe and the attached-prefix search, and the window a candidate is measured against (current_window) is cut only once a candidate has passed the byte compare. Inside the bucket scan the running result lives in locals (Found) and is written back once at the end, and the two measuring steps — accept_cached for a cached distance, accept_candidate for a bucket slot — are out of line and return by value: the candidate loop is a filter that rejects most of what it sees, and it stays in registers only while it holds about a dozen values. The greedy matchers measure a match with match_len_at, which settles the first eight bytes with one load per side and a trailing-zero count before cutting any window, and only then continues with match_len_windows, a whole-word scan with one overlapping word at the tail (§8.1) — together the reference’s FindMatchLengthWithLimit without its byte loop. The quick matchers measure behind an out-of-line call that re-enters the SIMD feature context. H2 and H3 use match_len_at_outlined, which settles the first word inline and calls match_len_tail for the rest: inlined, that scan’s setup does not depend on the slot, so it was hoisted in front of the slot loop and paid, with its spills, at every position, although only about a quarter of the candidates get past the first word. The four-slot H4 and H54 use match_len_at_current, which also cuts the current window behind the call: with four slots the compiler cut that window in front of the slot loop and kept it across all four, at every position, although only the few candidates that pass the first-byte compare are measured (measured on H4 text: about 2.5% fewer instructions per stream). The one- and two-slot matchers measured 1-4% slower that way, so the choice is made per matcher at compile time. current_window and the candidate cut mask their index and length to 32 bits, which proves the slice end neither overflows nor precedes the start and leaves one compare.

The bucket continuation filter uses the concrete run’s physical bucket width. Compact chains, shallow buckets (N <= 32), the four-position starter blocks and full buckets wider than 128 slots keep Best { len, word } and consider: each candidate checks the four bytes at its masked position plus len - 3. Only full buckets with 32 < N <= 128 use best_word and a borrowed continuation slice. These are the 64/128-slot full buckets used at qualities seven and eight; the 256-slot quality-nine bucket retains the original filter. scan_bucket handles the selected widths in an early-return branch, leaving the original shallow and wider-bucket implementation below it.

raw_continuation_window prepares the suffix after the cached-distance probes have raised the initial comparison length to at least three. The width choice is constant for the concrete run and outside the candidate loop; it does not add backend detection or SIMD dispatch.

Let W be the original physical window, data[..min(mask.saturating_add(1), data.len())]. For comparison length L, the continuation is W[L - 3..], or an empty slice when the suffix is outside that window. A candidate’s masked position p then reads continuation[p..p + 4], which is exactly the former W[p + L - 3..p + L + 1] check. The filter need not add the comparison offset to each rejected candidate or retain it separately from the suffix. The current four-byte word is cached as before. This slice is the physical continuation filter, distinct from current_window, which bounds the actual match measurement against remaining input.

consider_raw_rebased first applies the same logical backward-distance guard: an old or future position outside max_backward stops the scan before a physical read. An unavailable four-byte window or a different word skips that candidate. A matching word calls the existing accept_candidate with the same SIMD token, original data, current position, match-length limit, distance and score. After acceptance, it updates Found and best_word, then rebuilds the continuation from the original data and mask at the accepted length. It never derives the next continuation from the previous suffix. A closer candidate can win on score with a shorter length, so rebuilding must also move the start backwards and expose positions the old suffix could not read.

Within the 64/128-slot branch, scan_bucket first selects the permitted algorithm from its existing concrete SIMD token and hash shape:

The exact Level match distinguishes AVX2 from AVX-512; it uses scan.simd.level() from the selected S, with x86-only enum arms behind target configuration. Non-x86 targets set the permission to false. The gate depends only on the concrete token and the HASH64/N constants, before any candidate loop. It introduces no CPU feature detection and does not select a different backend. For example, an AVX-512 H5 query retains its AVX-512 measurement token while using the general rebased filter. The policy records measured native algorithm combinations; the public backend selection stays unchanged.

An allowed entry can then select consider_raw_young once for this bucket search. Runtime eligibility requires a nonempty bucket, max_backward == cur_ix, cur_ix <= mask, and a low-ones mask (mask & mask.wrapping_add(1) == 0). Only then does it read the newest logical position and require that head to be at most cur_ix. The loaded head is reused as the first candidate. A failed policy or state condition falls through to the same general rebased loop; aged history, wrapped logical positions, unusual masks and future heads retain its per-candidate distance guard and masking. Compact, shallow/Starter4 and N>128/q9 use the original Best/consider implementation.

Reachable bucket slots are already ordered newest to oldest by non-increasing logical position. The head check therefore proves 0 <= previous <= head <= current <= mask for every visited slot. Combined with max_backward == current, this makes every distance admissible: current - previous <= current == max_backward. The low-ones mask also gives previous & mask == previous and current & mask == current. A young candidate’s stored logical position is already its physical index; the helper reads the bounded continuation directly, with no per-candidate distance test or position masking. Only a matching four-byte word computes the actual current - previous distance for the unchanged accept_candidate and Found. It does not recover distance from a masked difference. A debug assertion checks the nonfuture-position invariant before the read. The one head check relies on the existing chronology; it does not validate an arbitrary unordered array.

Young and general rebased loops share the same cached word, bounded suffix, measurement/scoring rules and original-window rebuild after acceptance, including a shorter accepted length. The choice is local to this bucket search; no mode flag is stored in the matcher or encoder, and no backend detection is added. The same previously selected SIMD token reaches the measurement entry.

flowchart TD
    Probes["Cached-distance probes; comparison length L at least 3"] --> Shape{"Full bucket with 32 < N <= 128?"}
    Shape -->|no: compact, shallow, starter or N > 128| Original["Best len/word and original consider filter"]
    Original --> Stop["Finish scan; write back Found once"]
    Shape -->|yes| Policy{"AVX2 N64/128, or AVX-512 H6 N128?"}
    Policy -->|no| GeneralInit["Prepare bounded original-window suffix and best_word"]
    Policy -->|yes| Eligible{"Slots present, max_backward == current, current <= mask, low-ones mask?"}
    Eligible -->|no| GeneralInit
    Eligible -->|yes| Head{"Load newest once: head <= current?"}
    Head -->|future| GeneralInit
    Head -->|nonfuture| YoungInit["Prepare suffix and best_word; reuse loaded head"]
    GeneralInit --> GeneralMore{"Slots remain?"}
    GeneralMore -->|no| Stop
    GeneralMore -->|yes| Distance["Read slot; apply backward-distance guard"]
    Distance -->|outside history| Stop
    Distance -->|valid| GeneralRead["Mask previous position; bounded four-byte continuation check"]
    GeneralRead -->|missing or different| GeneralNext["Advance newest to oldest"]
    GeneralRead -->|equal| GeneralMeasure["accept_candidate with original data and selected SIMD token"]
    GeneralMeasure -->|score does not improve| GeneralNext
    GeneralMeasure -->|accepted| GeneralRebase["Update Found/word; rebuild from ORIGINAL W, even for shorter length"]
    GeneralRebase --> GeneralNext
    GeneralNext --> GeneralMore
    YoungInit --> YoungRead["Bounded four-byte continuation check at direct logical position"]
    YoungRead -->|missing or different| YoungNext["Decrease remaining count"]
    YoungRead -->|equal| YoungDistance["Compute actual current - previous"]
    YoungDistance --> YoungMeasure["Same accept_candidate, data, token and scoring"]
    YoungMeasure -->|score does not improve| YoungNext
    YoungMeasure -->|accepted| YoungRebase["Same Found/word update; rebuild from ORIGINAL W"]
    YoungRebase --> YoungNext
    YoungNext --> YoungMore{"Slots remain?"}
    YoungMore -->|no| Stop
    YoungMore -->|yes| YoungAdvance["Advance slot and load next logical position"]
    YoungAdvance --> YoungRead

The ring data is borrowed read-only throughout the search. No storage allocation, public API, low-level error, candidate ordering, distance scoring or match measurement ABI changes; Found is still committed to the search result once the scan ends. All supported SIMD levels and the scalar baseline preserve the same candidate-order, scoring, output and error invariants. Depth, exact token/hash policy and query state choose the filter implementation; the existing feature-enabled measurement entry owns the SIMD context. The specialization adds no public API, persistent matcher state, buffer ownership, allocation or error path; only the local reject work changes.

The static-dictionary probe is chosen at compile time (search_dictionary::<SHALLOW>). A shallow probe (the quick matchers) hashes the four bytes inline and answers an empty bucket — about three quarters of the probes on text — without a call, counting the lookup exactly as the out-of-line probe would; only a filled bucket copies the search result and calls probe_shallow, so an empty bucket stores nothing. The deep probe of the bucket matchers keeps its hash inside probe_deep, so their search loop is unchanged. None of this changes a decision: the sequence below is the same as the reference’s.

sequenceDiagram
    participant Search as create_backward_references
    participant Finder as Matcher
    participant Dict as dictionary
    participant Prefix as attached prefix
    participant Cmds as command buffer

    loop while position + hash length < end
        Search->>Finder: find_longest_match(position)
        Finder->>Finder: probe the four cached distances
        Finder->>Finder: probe the hash bucket
        opt nothing beat the minimum score
            alt shallow and the bucket is empty
                Finder->>Finder: count the lookup inline
            else
                Finder->>Dict: probe_shallow(key) / probe_deep
            end
        end
        Finder-->>Search: SearchResult
        opt a context is attached (q5 and above)
            Search->>Prefix: find_match(position)
            Prefix-->>Search: improved SearchResult
        end
        alt no match
            Search->>Search: one more literal, maybe stride ahead
        else match found
            loop at most four times
                Search->>Finder: find_longest_match(position + 1)
                Finder-->>Search: SearchResult
                break delayed match not 175 points better
                    Search->>Search: keep the earlier match
                end
                Search->>Search: emit one literal, take the later match
            end
            Search->>Search: update the distance cache
            Search->>Cmds: append one command
            Search->>Finder: store_range_simd with the selected token over matched bytes
        end
    end

4.1. The attached prefix

An attached RFC 9841 prefix widens the distance space rather than the search. Every distance that would address the dictionary sits past the window by gap — the total attached bytes — so three things shift together, exactly as they do in the reference:

• the match finder is told the static dictionary starts at dictionary_start + gap rather than dictionary_start, which pushes the built-in dictionary past the attached one;
• SharedContextInner::find_match runs after the ordinary search at each position and may replace its result, using dictionary_start itself as the boundary between window and prefix;
• compute_distance_code and the distance-cache update both compare against dictionary_start + gap, so a prefix reference is coded as an ordinary distance but never enters the cache.

extend_last_command handles prefix copies: a copy whose distance is past the window continues into the concatenated prefix, and unlike the search it runs on across attachment seams. See shared-brotli.md.

create_backward_references is generic over a const ENABLE_PREFIX: bool, and GreedyEncoder::create_references instantiates both — the reference’s ENABLE_COMPOUND_DICTIONARY, which it uses to compile the same function twice per match finder. The prefix-enabled and ordinary loops are separately monomorphized. The high-quality path does the same with its own ENABLE_PREFIX (see hq-encoder.md).

Two details separate the qualities:

• Delayed search. Below quality five the delayed candidate starts from the length already found, which lets the finder reject most candidates without measuring them. Quality five gives that shortcut up and searches everything again — this is a compression-semantics difference, not a tuning flag. The flag is a run-time field of the block, read once per match. Taking it from the finder type instead was tried and reverted: it cut instructions at qualities five to nine by 0.5-1%, but single-core time did not change measurably, and as a constant in the quick finders it made quality four execute up to 5% more instructions.
• Sparse search. After sixty-four literals without a match the scan strides forward two bytes at a time and stores every second position; after four times that, four bytes at a time. The exact thresholds and stores come from the reference, because they change which positions are findable later.

extend_last_command runs before the search when the previous block ended exactly on a command boundary: bytes that continue that command’s copy are absorbed into it instead of starting a new one.

After an admitted extension attempt, its symbol is rebuilt from the stored insert length and copy_len_code(). That accessor reconstructs the encoded copy length using its signed delta or experimental absolute-length tag. It therefore keeps the symbol consistent with the extra-bit lookup even when the prefix path returns without absorbing input. This shared helper also serves the high-quality encoder; its SIMD token and distance checks do not change.

5. Meta-block construction

flowchart TD
    cmds["commands + ring buffer"] --> should{"ShouldCompress?"}
    should -->|no| destination{"non-Flush append destination?"}
    destination -->|yes| direct["seed after existing output prefix<br/>append verbatim payload directly"]
    destination -->|no| lazy["reserve scratch capacity; seed carried bits"]
    lazy --> raw["store_uncompressed_meta_block<br/>BitWriter over Vec; append initialized payload"]
    direct --> metadata["relative bit position, carried byte, appended flag"]
    should -->|yes| scratch["initialize bounded scratch; seed carried bits"]
    scratch --> q{"quality splits blocks?"}
    q -->|"no, q2"| fastst["store_meta_block_fast<br/>static command and distance codes<br/>below 129 commands"]
    q -->|"no, q3"| trivial["store_meta_block_trivial<br/>one code per stream"]
    q -->|"yes, q4 and above"| ctx["decide_over_literal_context_modeling<br/>(q5 and above)"]
    ctx --> build["build_meta_block_greedy<br/>literal / command / distance splitters"]
    build --> opt["optimize_histograms<br/>(RLE-friendly counts)"]
    opt --> store["store_meta_block<br/>block switches, context maps, codes"]
    fastst --> grew{"grew by more than four bytes?"}
    trivial --> grew
    store --> grew
    grew -->|yes| fallback["rewind slice writer; restore remembered cache<br/>store uncompressed into initialized scratch"]
    grew -->|no| done["save partial byte and positions; clear commands"]
    fallback --> done
    raw --> done
    metadata --> done

encode_data evaluates should_compress before growing initialized output scratch. A nonempty block selected for verbatim storage reserves payload plus header/slack capacity and initializes only the carried prefix before using BitWriter<Vec<u8>>. The private ByteBuffer implementation overwrites an existing initialized overlap and appends the remaining payload safely, avoiding a zero-fill before copying it. Retained initialized storage is reused without clearing or truncating it. The generic uncompressed header/store helpers also retain the slice-backed instantiation for compressed-output rollback.

Both uncompressed paths restore the four remembered distance-cache entries; derived entries are rebuilt before the next search. The common completion path preserves any partial byte, advances the flush/processed positions and clears the command/literal counters. Empty finalization and flush padding retain their existing handling. Final uncompressed payloads still append a final empty block. For a non-Flush Destination::Append, Delivery::encode calls the private GreedyEncoder::encode_block_append with a borrowed Vec<u8>. encode_data receives this optional destination once per block. Known verbatim blocks write after its existing prefix and return BlockEmission: a relative bit position, the carried byte and an appended flag. The writer’s absolute position is checked, and its slack is truncated after the partial byte has been saved. Capacity includes sixteen extra bytes for the initial large-window/meta-block headers, final empty block and word-writer slack.

The common state update sets scratch output_len to zero for directly appended bytes, preventing a duplicate copy. Compressed attempts and their size-expansion fallback keep the scratch writer and are appended by the entry point afterward. Fixed/uninitialized slices, session pending output and Flush also retain scratch. The encoder accepts a Vec without depending on the stream output types; no SIMD dispatch or public API changes occur at this storage choice.

store_meta_block_fast is quality two’s storage — BrotliStoreMetaBlockFast. Below a hundred and twenty-nine commands only the literal code is built from the data; the command and distance codes are the fixed ones the format defines, written as the fifty-nine and twenty-eight literal bits their descriptions encode to. Above that all three codes are built, but by the leaves-ordered-by- count builder build_and_store_huffman_tree_fast rather than the full package-merge store_meta_block_trivial uses.

Both paths write their commands through store_data_with_huffman_codes. It narrows the literal depth and bit tables to exactly 256 entries once per meta-block, so a literal byte indexes them with no bounds check in the per-literal loop; the command and distance tables keep their checked lookups because static and built codes have different lengths. On a 285 KB binary map (mapsdatazrh) this is 3.3% fewer instructions at q2 and 0.1% on text at q2 and q3.

ShouldCompress refuses blocks of at most two bytes outright, and samples every thirteenth literal of a block that is almost all literals: if the sample’s entropy exceeds 7.92 bits per byte the block is stored verbatim, which is both smaller and much faster than coding noise.

5.1. Block splitting

The greedy splitters consume symbols in order. Every time one has collected its target number of symbols it compares the entropy of the block it just gathered against the entropy of merging it into the last, or the second-last, block:

flowchart TD
    add["add_symbol"] --> full{"block_size == target?"}
    full -->|no| add
    full -->|yes| diff["entropy(current + last) - entropy(current) - entropy(last),<br/>and the same against the second-last"]
    diff --> new{"both above the threshold<br/>and types left?"}
    new -->|yes| open["open a new block type"]
    new -->|no| second{"second-last better by 20?"}
    second -->|yes| reuse["reuse the second-last type"]
    second -->|no| merge["merge into the last block,<br/>and gather more next time"]

Quality five may run the literal splitter per context instead, keeping one histogram per context of every block type and deciding on the total entropy change across all of them.

Without contexts, build_meta_block_greedy hands each command’s literal run to BlockSplitter::add_bytes as one slice whenever the run does not wrap the ring (ringbuffer::contiguous, bounded by the mask rather than the buffer length, since the tail copy past the mask is not the wrapped bytes). The splitter cuts the run where the current block fills, so its counts and block boundaries are those of one add_symbol per byte, and looks up the current histogram once per piece. The previous two bytes are tracked, and re-read after each copy, only when a context splitter is running. On the first 60 MB of silesia.tar this is 2.9% fewer instructions at q4 and 1–2% at q5 and q6.

flowchart TD
    cmd["command: insert_len literals"] --> plain{"single literal context?"}
    plain -->|yes| wrap{"run inside the mask?"}
    wrap -->|yes| bytes["add_bytes(slice):<br/>pieces up to the block's end"]
    wrap -->|no| sym["add_symbol per masked byte"]
    plain -->|no| ctx["per literal: context(prev1, prev2),<br/>ContextBlockSplitter::add_symbol"]
    ctx --> prev["track prev1, prev2;<br/>re-read them after a copy"]

The combined histograms are not materialised for the decision: bits_entropy_of_sum accumulates the summed counts in the same order bits_entropy would, so the result is bit-identical, and a block that merges is added into its neighbour in place. A splitter creates a block type’s histograms when it first advances into them, so a short input never zeroes histograms it will not fill, and a retained buffer keeps whatever the last meta-block left in the rest until they are cleared on use.

5.2. Literal context modelling

Only quality five and above reach this, and only when the meta-block is at least sixty-four bytes long. The decision samples sixty-four byte strides every four kibibytes:

flowchart TD
    start["meta-block"] --> gate{"quality >= 5, enabled,<br/>length >= 64?"}
    gate -->|no| one["one context"]
    gate -->|yes| complex{"size hint >= 1 MiB?"}
    complex -->|yes| try13["sample 13-context map<br/>over the top five bits"]
    try13 --> ok{"entropy <= 3.0 and<br/>saving >= 0.2 bits?"}
    ok -->|yes| thirteen["13 contexts"]
    ok -->|no| bigram
    complex -->|no| bigram["sample UTF-8 prefix bigrams"]
    bigram --> choose{"saving >= 0.2 bits?"}
    choose -->|no| one
    choose -->|yes| two["2 contexts"]

The reference’s three-context map is deliberately priced out of reach below quality seven, and ChooseContextMode only returns CONTEXT_SIGNED at quality ten, so CONTEXT_UTF8 is the only literal context mode these qualities can emit. Only that one lookup table is carried.

6. The ring buffer

The layout matters for the emitted bytes, not just for correctness: match finding reads whole words past the current position, and the reference defines exactly what those bytes are.

graph LR
    subgraph buffer["RingBuffer::data"]
        head["2 bytes<br/>copy of the window end"]
        window["1 &lt;&lt; rb_bits bytes<br/>the sliding window"]
        tail["1 &lt;&lt; lgblock bytes<br/>copy of the window start"]
        slack["7 bytes<br/>zeros"]
    end
    head --- window --- tail --- slack

• Until the first wrap approaches, storage grows with the written prefix and seven lookahead bytes. The configured logical window mask never changes.
• A write ending within eight bytes of the window end materializes the full layout before copying input. The last two window bytes are initialized to zero, and deferred tail copies are replayed from the existing prefix.
• The reference skips tail copying for a short first write. tail_start records that skipped range, preserving its first-byte sentinel 241 until a later write overwrites it.
• After every write the seven bytes past the data are cleared, so hashing never depends on memory the encoder did not write. Reset retains allocation capacity and clears the prefix position, allocation state and skipped-tail boundary.

stateDiagram-v2
    [*] --> Empty
    Empty --> Prefix: write ending before window end minus eight
    Prefix --> Prefix: grow initialized prefix and lookahead
    Empty --> Full: write reaches window end region
    Prefix --> Full: initialize tail and replay deferred copies
    Full --> Full: circular writes with immediate tail mirroring
    Prefix --> Empty: reset, retain capacity
    Full --> Empty: reset, retain capacity

Absolute positions are wrapped into 32 bits by wrap_position, which keeps the first three gibibytes contiguous and then alternates between two gibibyte-wide halves so the “already lapped” property survives the truncation.

7. SIMD dispatch

graph TD
    A["Compressor::new()"] -->|"Backend::default: detect or no_std baseline"| B["Backend stored in the Compressor"]
    B -->|"new encoder"| D["GreedyEncoder<INDEPENDENT> retains the Backend"]
    D -->|"dispatch!(backend) once per block"| E["select concrete matcher and run once per block"]
    E --> V["SearchLoop::visit<R>"]
    V -->|"#[simd] search_positions: S feature context"| F["find_longest_match(simd, ...)"]
    F --> G1["tag_equality(simd, ...)"]
    F --> G2["match_len_at: first word, then match_len_windows (scalar words)"]

    classDef once fill:#d9ead3,stroke:#38761d;
    class D once;

The backend is detected once, when the Compressor is built, and the encoder retains it. The greedy loops run at that same backend as every other encoder kernel; the scalar backend keeps them scalar, as the unfiltered oracle. Per block, create_references matches the backend with fearless_simd::dispatch!, then the MatchFinder enum, and calls create_backward_references, a #[simd] function that enters S’s feature context; the concrete token reaches the tag filter without inner dispatch. Whether a prefix is attached and whether the encoder serves an independent worker (INDEPENDENT) are type-level choices made at the same point.

SearchLoop::visit specializes the matcher and run, then calls search_positions, the #[simd] function that holds the per-position loop; commit_match is #[simd] as well. The #[simd] attribute from fearless_simd_macros turns the function body into an always-inlined closure and calls it through a feature-enabled entry generated for the token’s level, passing every argument separately rather than as one captured struct, so the generic fearless_simd operations become native instructions. Passing a token to an out-of-line function alone does not enable its target features: a baseline compilation instead calls feature-enabled helpers for each vector comparison and mask operation. Entering the context after matcher and run specialization also keeps each search body separate, rather than forcing every matcher into one large outer dispatch function.

The nested feature entries use the existing token; they perform no detection or virtual dispatch. All entries are outside the search loop. The candidate measurements accept_cached and accept_candidate stay out of line on purpose (§2) and are #[simd] with an #[inline(always)] wrapper, so the search loop calls the level’s feature-enabled entry directly and the 32-byte compares inline into it; the same holds for match_len_tail and match_len_at_current. The macro’s fearless_simd helper owns the feature proof; no handwritten target_feature or unsafe block is needed. Scalar and SIMD paths keep the same matcher state, candidate order, score arithmetic, and error propagation.

Everything else — match-length scans in the greedy matchers, bucket stores, the exact check behind each cached-distance candidate, distance-cache transitions, the greedy and lazy decisions, Huffman construction, bit writing — is scalar, because the reference’s decision order is not reorderable and a vector unit cannot help without changing it.

8. The static dictionary

Brotli’s built-in dictionary is 122,784 bytes of words plus a 32,768-bucket hash over their four-byte prefixes, carried as binary blobs beside the module and embedded with include_bytes!.

Only the encoder side is needed. A dictionary match is emitted as an ordinary distance beyond the end of the window:

distance = max_backward + 1 + word_index + (transform_id << size_bits[len])

and the decoder is the side that applies the transform, so the transform table itself never has to be carried — the encoder only computes which transform id a given prefix cut corresponds to.

Probing is self-limiting: once a stream has gone a hundred and twenty-eight lookups per match, the encoder stops paying for it.

8.1. Prefix-length scans

Every “how many leading bytes agree” question — static dictionary words, the HQ dictionary matcher and the attached prefix search — goes through shared::match_len: common_prefix_len scans whole eight-byte words and then bytes with the bounds established once, which is all a dictionary word of at most twenty-four bytes needs, and common_prefix_len_simd adds the native-vector loop of find_match_length for the attached prefix, whose matches run as long as the window allows. SharedContextInner::find_match takes the SIMD token and enters its feature context itself, so the vector compare stays inline however it is reached.

9. Error propagation

The greedy tree defines no error type of its own. GreedyParams::new reports an unimplemented quality as the private UnsupportedQuality, which the public EncodeError reports as an internal invariant because no validated configuration can reach it, and the only other failure is BufferOverflow, raised when the bit writer runs past the scratch buffer or its checked capacity calculation overflows. Compressed blocks reserve 2 * bytes + 503 plus writer slack, as before; known uncompressed scratch blocks reserve bytes + 503 plus slack and initialize the output only as written. Direct verbatim appends reserve payload plus sixteen bytes and check the caller prefix offset before converting it to a bit position. Neither overflow is reachable for a valid bounded meta-block.

10. Verification

The direct young-helper differential test exercises its arithmetic on every available backend independently of the production policy. Whole-scan tests verify the same result when the policy selects the general fallback instead.

Known gaps

• The large-window match finders are unreachable. Window::large reaches these qualities, so a large window is declared and the widened distance alphabet is used, but ResolvedWindow::encoder_bits caps retained history at 30 bits and every matcher is sized from that. The reference’s H35, H55 and H65 composite match finders are selected only above that cap, so they are never built. See shared-brotli.md.
• An attached prefix reaches only qualities five and above. The reference compiles its compound-dictionary search for H5, H6, H40, H41, H42, H55 and H65 only, so H2, H3, H4 and H54 have nowhere to put a prefix match; where the reference then ignores the dictionary, this crate refuses. Experimental custom static dictionaries use the same quality floor.
• Custom static and offset mechanics are experimental. The selected UTF-8 context combination replaces the implicit built-in probe; headerless continuations poison the distance cache and shift dictionary placement without inventing history. See rfc9841-encoding.md.
• Histogram accumulation and context sampling remain scalar. Bucket tag filtering and the high-quality match-length scans have SIMD implementations; the greedy matchers scan whole words.
• Cold bucket matchers initialize their tables. The reference leaves its bucket table uninitialised; safe Rust cannot. A cold q5–q8 call either zeroes a 1–16 MiB table (from the dense limit, or after a mid-stream promotion) or stays on the sparse layout, whose dependent index load costs 10–30% on text below the promotion point. Cold q5–q8 calls on 2–32 KiB inputs still run at roughly 0.7–0.85 of the reference; reused compressors keep their tables and pay neither cost.
• Short one-shot inputs pay for initialised memory. A cold call on at most a kibibyte indexes the compact map and allocates and zeroes its scratch per call. See the benchmark guide for separate cold and reused measurements.
• Small-window chain matchers trail the reference even when reused. Windows of at most sixteen bits send qualities five to nine through H40/H41/H42. With a reused compressor and identical output, q5–q8 on 2–64 KiB inputs run at roughly 0.84–0.91 of the reference and q9 at 0.94–0.99 (Intel i7-13700KF, x86-64 AVX2, against C 1.1.0). Under callgrind the hop loop costs about as many instructions per hop as the reference; what is left is per-position work around it — the distance-cache probes, the query, the stores — compiled into one large function whose loops spill table pointers and limits to the stack.

Independent parallel fragments

The parallel fragment adapter builds GreedyEncoder<true> once per worker. DictionaryStats::DISABLED keeps static-dictionary lookup disabled. prepend_history first takes the input before the segment as already-emitted history, the way brotli 1.0’s BrotliEncoderSetCustomDictionary did: window, positions, prior bytes and MatchFinder::prepend, which stores each position whose lookahead lies inside it, except the earlier periods of short-period runs (see parallel compression). begin_fragment then starts headerless, fills the four remembered distances (and saved_dist_cache) with -16 so that no short code refers to the decoder’s inherited cache, and seeds the ring and literal context with the raw prefix. Distances are then coded by the serial compute_distance_code, which only returns short codes for slots the fragment’s own copies filled; the common fragment writer owns those prefix bytes in the output. Serial kernels use false and retain their existing behavior. See parallel compression for reset invariants and assembly.