Decoder Internals

The seq decoder (decode_normal in lib/entropy/lz6seq.c) runs in three phases per block. Each phase is shaped by what the profiler showed, not by symmetry with the encoder.

 1. tables                     three tANS decode tables (ll / ml / of), one array
 2. literals                   whole literal stream ──► padded buffer (raw: used in place)
 3. sequence pipeline          stage A: one backward bitstream ──► (ll, ml, offset), prefetch source
                               stage B: 64 sequences later, copy literals + match

Phase 1: tables

Since seq v2 the ll/ml/of symbols are table ANS (zstd FSE-style): a symbol costs one table load plus a bit read, with no multiply. Since v1.6.7-pre each 8-byte entry is {next state, nbBits, nbExtra, base} (zstd's seqSymbol): the entry already holds the field's base value and its extra-bit count, so a field is base + read(nbExtra) with no further table lookups or per-symbol branches (rep codes are flagged in base). The encoder defaults to LL/ML tables of 2^10 entries and offsets of 2^11, 32 KB in total, so they stay in L1. Since v1.6.11-pre the three tables live in one array and every state already includes its table's offset (seq_build_dtable adds it to next), so the loop keeps one table pointer.

Phase 2: literals in bulk

All literals are decoded into a buffer padded by 32 bytes before the sequence loop. The previous decoder produced them in per-sequence chunks of 1-4 bytes, reloading the coder state each time.

• Huffman uses a two-symbol lookup table: when the code at the head of the window leaves room for a second complete code inside the k-bit index, one lookup emits both (like zstd's HUF X2). A 64-bit window holds ≥ 57 valid bits, which is enough for 4 lookups (up to 8 literals) per load.
• Huffman, 4 streams (since v1.6.11-pre, stream format unchanged). For complete prefix codes and blocks with several symbols per table entry, the four streams are decoded in lockstep: 4-6 symbols per stream per iteration (NS * K <= 56 bits, so one 8-byte window load per stream per iteration is enough), one lookup per symbol into a table widened to K = 9, 11 or 12 bits (symbol bytes, then length bytes), no per-symbol branch, bounds checked once per batch of iterations; the batches shrink towards the stream ends and the 1-2 symbol loop above finishes the tails. Codes with a long code or an unused slot (corrupt headers) keep the old path. It has a BMI2 clone like the sequence loop.
• FSE order-0 / order-1 (range ANS) renormalise branch-free: a valid state needs at most 2 bytes per symbol, so blocks of (bytes left)/2 symbols run unchecked and only the stream tail is checked.
• Raw literals are copied straight from the input block.

Phase 3: two-stage sequence pipeline

Stage A reads one sequence from the bitstream:

• It reads the three table entries through pointers (no struct copies). Those entries give every bit the sequence will read (offset residual, ml and ll extras, three state updates), so one branch-free refill covers them. The checked refill runs only within 24 bytes of the stream start, or when the extras exceed a threshold computed once per block (56 - (log_ll + log_ml + log_of); every entry's nbBits is at most its table's log).
• The rep stack lives in three scalars. An offset coded explicitly is always pushed, even when it equals rep0 (the encoder never emits that, it codes rep0).
• On x86-64 the BMI2 clone keeps the bit position negated (p = -consumed) and extracts a field with one bzhi (bzhiq as inline asm: GCC turns the mask into mov/shlx/not/and and never emits bzhi itself); the plain clone keeps the old shift pair, which is cheaper than shift + mask without BMI2.
• Stage A never reads the output. It tracks the future output position and prefetches the match source (2 cache lines) 64 sequences ahead (the prefetch needs no range guard: it never faults). With a 32MB window, far matches otherwise miss every cache level one at a time; 16 sequences ahead left webster 17% slower than 64, 128 gained 1-2 points more but cost small cache-resident files 1-3%.

The last sequence is read outside the loop (it has no state update), so the loop carries no more/done bookkeeping: min(sc-1, 63) sequences fill the ring, the steady state reads one and executes one per iteration (no scheduling branch, as in zstd's prefetch loop), then the ring drains. The ring is three uint32_t arrays (ll, ml, offset: all below 2^26 by construction of the code tables).

Stage B executes a sequence and has two paths:

• Fast path, taken when the three tests of zstd's decoder hold: the sequence fits with room for the wide copies (oend - o >= ll + ml + 32), its literals exist, and 1 <= offset <= bytes written (one unsigned compare: offset 0 wraps). The first 16 bytes of the literals are copied unconditionally, then 2 x 16 in a loop while more remain; a match with offset ≥ 16 is copied the same way. Offsets 1-15 use the overlapCopy8 spread (zstd's technique) and then 8-byte moves. Raw literals are read in place only when 32 bytes of the block follow them (the wide copies over-read), otherwise from the padded copy.
• Exact path for everything else (the end of the block, corrupt input, the literals-only last sequence): the old fully checked code, so the decoder never writes past the declared size, even with dstCap == isize. -DLZ6SEQ_FORCE_SLOW_B=N sends every Nth sequence through it, which lets the tests exercise it with valid streams.

At the end the output must be exactly isize bytes, and the decoder checks that exactly the stream's bits were consumed (tbr_exact), failing the block otherwise; there is no per-field check. A truncated or corrupt bitstream reads into the zero padding instead of out of bounds.

The byte-plane merge of plane blocks interleaves lanes with SSE2 (16 bytes of every lane per step, punpck; stride 2 and 4) and falls back to the scalar loop for the tail and on targets without SSE2.

Where the time goes now

Instructions per sequence at level 3 (xml / dickens / samba), exact counts around the decode loop: v1.6.10-pre 253 / 232 / 278, v1.6.11-pre 163 / 143 / 163 (zstd: 121-136 measured earlier); per output byte -36..-41% on text, -57% on mr. Decode cycles, size-weighted over Silesia + AIT, one pinned core: -38.2% / -40.9% / -38.1% / -37.8% at levels 1 / 3 / 8 / 15. What bought it (instructions per byte): the stage rewrite alone -18..-33% on text and -7..-13% on mr; SSE2 plane merge + the Huffman lockstep loop -48..-52% on mr, -27..-46% on sao, -36..-43% on x-ray, -13..-24% on mozilla; the negated bit reader -1..-8%. SEQ_AHEAD 16 -> 64 does not change the instruction count (it hides latency): -2.6% (L1) .. -9.8% (L3) of cycles, webster -17%. The decoder was not re-profiled by phase after the rewrite.

Tried and not kept: an unconditional 2 x 16 B match copy for offsets >= 16 (-0.8% weighted at L3, but dickens +1.8% and sao +2.1% elsewhere; with a per-block picker the duplicated code lost 1.5-5%), a run-time SEQ_AHEAD (+2.5-4% instructions), the rep history in two registers (0.6 instructions per sequence), keeping "an explicit offset equal to rep0 leaves the history alone" (+2-4% instructions for a case no encoder produces), a forward LSB bitstream, unit-record tables, AVX2 plane/literal lanes, a hot/cold split of stage A, and every compiler flag, PGO and clang (bakeoff/SINGLE_THREAD_STUDY.md). Before the rewrite, splitting the sequences into two interleaved bitstreams was 6.5% slower (more instructions and register pressure), and reading all of a sequence's bits in one go (9% fewer instructions) had added 4-6% cycles through the longer state-to-load chain (both measured on the v1.6.7-pre loop, not re-tried on this one).

BMI2. On x86-64 (GCC/clang) the decode body, and the Huffman fast loop, are compiled twice, the second time with target("bmi2"), and picked per call with __builtin_cpu_supports. Bit reads are variable-count shifts: they cost 3 uops as shl/shr %cl and 1 as shlx/shrx; the BMI2 clone also uses bzhi (see Stage A). Other targets (ARM64, 32-bit, MSVC) build the plain body only.

Safety

Every length, offset and stream bound is still validated. The decoder is gated by bakeoff/seqgate.sh (the standing gate; see Development), on both decoder clones (BMI2 and plain) and decoding from an exact-size source and an exact-size destination, so ASAN sees a read past the end of the stream and a write past the end of the output:

• the two memory-safety bugs fixed in v1.6.11-pre (an oversubscribed Huffman code-length set stored one uint16 past its lookup table; a block that ends right after its literals read the 4-byte sequence count past the stream) as PoCs that must run clean;
• round trips under ASAN + UBSan (edge sizes 0..300 and 1000..1000000, tiny blocks of 8..707 bytes, AIT and Silesia slices, all literal modes, plane blocks) and a 32-bit build with sanitizers;
• mutation fuzzing of valid streams (bit flips, truncation, garbage runs, header corruption), 300000 mutants per clone for a finished change, and a differential run against the previous decoder (return code and an FNV hash of the output must match on every mutant);
• the Huffman literal blocks (valid and mutated) against the previous Huffman decoder, the SSE2 plane merge against a scalar reference (every plane size 0..300), and the rep-offset rule (rpzero);
• the repository fuzzers bench_seq --fuzz (raw streams) and --ffuzz (frames through LZ6F_decompress), valgrind memcheck on the CLI decode, ThreadSanitizer at -T4, aarch64 under qemu-user, and the Windows binaries on Windows 7 SP1 and 10.

See Development.