perf: FSE decoder — dual-state parallel decoding

[polaz]

Summary

FSE (Finite State Entropy) decodes literal lengths, match lengths, and offsets in every compressed block. The C reference uses dual-state parallelism that the Rust implementation lacks.

C reference optimizations (fse_decompress.c)

Dual-state decoding

Maintains two FSE decoder states (state1, state2) with interleaved I/O:

for (...) {
    op[0] = FSE_decodeSymbol(&state1, &bitD);
    BIT_reloadDStream(&bitD);  // Interleaved reload
    op[1] = FSE_decodeSymbol(&state2, &bitD);
}

This hides the data dependency between decode and reload — while state1 result is being stored, state2 decode begins.

Fast vs standard mode

• Fast: FSE_decodeSymbolFast() — no bounds check (assumes nbBits ≤ available bits)
• Standard: FSE_decodeSymbol() — with bounds checking for correctness

Table layout

• FSE_DTable entries: {symbol, nbBits, newState} packed for cache-line alignment
• Bulk symbol spreading via MEM_write64() with 0x0101010101010101ULL patterns

Current Rust implementation

• fse/fse_decoder.rs — single-state sequential decoding
• No interleaving between decode and reload
• Standard (bounds-checked) mode only

What needs to be implemented

1. Dual-state FSE decode loop — two states with interleaved bit reload
2. Fast decode path — skip bounds check when bit budget is sufficient
3. Bulk table spreading — u64 writes for symbol initialization
4. Conditional reload — compile-time decision based on table log vs container size

Performance impact estimate

• Dual-state: ~15-20% speedup on sequence decoding
• Fast path: ~5-10% additional

Acceptance criteria

• Batched refill for FSE state updates (ensure_bits + update_state_fast)
• Fast decode path for guaranteed-safe cases (get_bits_unchecked)
• Debug assertions for 56-bit budget invariant
• Benchmark shows improvement (~3% on full decode pipeline)
• All roundtrip and corpus tests pass

Scope notes (from implementation)

Dual-state interleaving: The C reference's dual-state pattern (state1/state2 alternating) applies to generic FSE byte-stream decoding. In zstd sequence decoding, we already have 3 independent decoders (LL/ML/OF) — the batched refill across all three is the analogous optimization.

Bulk table spreading: Not applicable with current 8-byte Entry struct layout. The C reference packs entries into 4 bytes ({u16 newState, u8 symbol, u8 nbBits}). Tracked in #56 as a separate refactor.

Extra bits optimization: Attempted replacing get_bits_triple with ensure_bits + unchecked reads — benchmarked ~6% regression. The existing get_bits_triple with #[inline(always)] + #[cold] refill() already generates optimal code via LLVM branch prediction hints.

Time estimate

2d