perf: bitstream reader — branchless operations and bulk reload

[polaz]

Summary

Bitstream reading is the foundation of all entropy decoding (Huffman + FSE). The C reference uses carefully tuned branchless operations that the Rust bit reader partially lacks.

C reference optimizations (bitstream.h, bits.h)

1. Bit container sizing

• Uses size_t as bit container (64-bit on x86-64)
• STREAM_ACCUMULATOR_MIN_64 = 57 bits — reload threshold tuned per architecture
• Forward write / backward read (LIFO stack) for natural FSE decode order

2. BMI2 fast path

• BIT_getLowerBits() uses _bzhi_u64() (BMI2 instruction) for O(1) bit masking
• Fallback: BIT_mask[] pre-computed lookup table (32 entries)

3. CTZ/CLZ intrinsics

• ZSTD_countTrailingZeros32/64() → __builtin_ctz() (Rust: trailing_zeros())
• ZSTD_highBit32() → __builtin_clz() with DeBruijn fallback
• Used in match length counting and symbol weight calculation

4. Branchless reload

• Conditional reload based on compile-time threshold, not runtime check
• Eliminates branch on every symbol decode

Current Rust implementation

• bit_io/bit_reader.rs and bit_reader_reverse.rs — functional but with branches
• ringbuffer.rs:200, 240 — branch-heavy logic in hot path (noted as TODO)
• No BMI2 conditional compilation
• Uses Rust's built-in trailing_zeros() / leading_zeros() (good, but no bulk masking)

What needs to be implemented

1. Branchless bit reload — compile-time threshold check, not runtime
2. Pre-computed mask table — BIT_mask[33] equivalent for fast masking
3. BMI2 feature detection — #[cfg(target_feature = "bmi2")] for _bzhi_u64
4. Bulk bit consumption — read multiple symbols before reloading container
5. Reverse reader optimization — eliminate error handling for >56 bit requests (as noted in upstream feat: dictionary builder — FastCOVER algorithm and dictionary finalization #25)

Performance impact estimate

• Branchless reload: ~5-10% on entropy-heavy data
• BMI2 masking: ~3-5% on supported CPUs
• Cumulative effect across all entropy decoding: significant

Acceptance criteria

• Branchless reload logic
• Pre-computed mask table
• Optional BMI2 fast path behind cfg
• Benchmark shows improvement
• No regression on non-BMI2 platforms

Time estimate

2d

[coderabbitai]

🔗 Related PRs

#2 - feat: managed fork setup — README, FUNDING, crate rename to structured-zstd [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!