# Plan: multi-symbol (whole-tree) entropy coding — additive v2 API
> Alternative / successor to [decode-tree-register-resident.md](../../src/compactly/plans/decode-tree-register-resident.md)
> (OPTIMIZING.md TODO #2). v2 is **not** stabilized, so this is an *edit to v2*:
> the existing bit-level CABAC-style `EntropyCoder`/`EntropyDecoder` methods stay
> (for `bool` and independent-bit batches), and we **add** methods that code a whole
> heap-tree symbol (`u8`, `Bits<N>`, `UBits<N>`) in **one** coding step instead of
> `log2(N)`. The central deliverable of this plan is the **new API**.
## Context
The decode hot path on structured records is the per-character / per-byte tree
walk: each `u8` / `Bits<N>` decodes as a `log2(N)`-step **dependent** binary-tree
walk, one coder step (one renormalization) per bit
([bits.rs:64-79](../../src/compactly/src/v2/bits.rs#L64-L79),
[byte.rs:27-38](../../src/compactly/src/v2/byte.rs#L27-L38)). Plan #2 keeps per-bit
coding but holds coder state in registers across the walk — bit-identical. This plan
keeps the adaptive model (`BitContext`, unchanged) and still walks the tree, but
uses the walk to **build one cumulative-frequency interval** for the whole symbol
and do a **single** arithmetic / rANS step.
`compactly` is general-purpose; the design must make **no assumption about the data
distribution** — including arbitrarily skewed fields (enums, sparse/sorted values),
which is exactly where compactly is strong today. The precision section below shows
how to keep the single-step coding distribution-independently near-lossless.
## Established facts (from the code)
- `Probability` is 8-bit: false-prob `= prob/256`
([ans/probability.rs:5-8](../../src/compactly/src/v2/ans/probability.rs#L5-L8)).
- `Ans` state `u32`, renorm near `2^24`; rANS coding is **deferred & reversed** —
`encode_bits` pushes `(bool,Probability)` to a `Vec`, `into_vec` runs the coder
backwards ([ans.rs:54-62,186-204](../../src/compactly/src/v2/ans.rs#L54-L62)).
`Range` is `u64` lo/hi, immediate, `split = lo + (width>>8)*prob`
([arith.rs:139-145](../../src/compactly/src/v2/arith.rs#L139-L145)).
- `u8`/`Bits<N>`/`UBits<N>` share one invariant: a contiguous context array whose
**length is exactly `2^n_bits`** (`ByteContext` = `[BitContext;256]`, `Bits<128>` =
`[BitContext;128]`, `UBits<4>` = `[BitContext;16]`), walked by heap index
`node = (node<<1)+1+bit` ([byte.rs:19-37](../../src/compactly/src/v2/byte.rs#L19-L37)).
So **`n_bits = N.ilog2()` is derivable from the array length** — we never pass it
separately.
- `BitContext::probability()` / `.adapt(bit)` are reused **unchanged**.
## The new API (the heart of this plan)
Design principles, resolving the review points:
- **One const-generic walk, fully unrolled.** The tree walk is a *provided* trait
method `…_tree::<const N>(&mut [BitContext; N], …)`, mirroring how `encode_bit` is
provided over `encode_bits`. `N` is the context-array length, so `n_bits =
N.ilog2()` is a compile-time constant after monomorphization and the loop unrolls
— no separate `n_bits` argument, no `N_MAX` juggling. (Matches the existing
`decode_bits::<const N>(&mut [BitContext; N])` signature exactly.)
- **Coders implement only an interval primitive**, not the walk — so heap-indexing /
CDF / clamp logic is written once.
- **A wrapper type `SymbolRange`** plays the role `Probability` plays for bits.
### 1. `SymbolRange` — the symbol-interval wrapper
```rust
/// A sub-interval [start, start+width) of the fixed total M = 1 << BITS.
/// Invariant: width >= 1 and start + width <= M.
#[derive(Clone, Copy)]
pub struct SymbolRange { start: u32, width: u32 }
impl SymbolRange {
pub const BITS: u32 = 16; // prototype; see precision section
pub const M: u32 = 1 << Self::BITS;
pub fn full() -> Self { Self { start: 0, width: Self::M } }
/// Split point for the false-branch, given the node's bit probability and the
/// number of tree levels `r` still below this node. Reserves room so every
/// descendant leaf keeps width >= 1 (see precision section).
fn split(self, p: Probability, r: u32) -> u32 {
let reserve = 1u32 << (r - 1);
(((self.width as u64 * p.get() as u64) >> 8) as u32)
.clamp(reserve, self.width - reserve)
}
fn lower(self, split: u32) -> Self { Self { start: self.start, width: split } }
fn upper(self, split: u32) -> Self { Self { start: self.start + split, width: self.width - split } }
fn contains(self, slot: u32) -> bool { slot - self.start < self.width } // slot >= start assumed
}
```
### 2. Coder primitives (required) + tree walk (provided)
```rust
pub trait EntropyCoder {
// ...existing encode_bits / encode_bit / encode_incompressible_bytes...
/// Code one symbol occupying `range` of total SymbolRange::M.
fn encode_symbol(&mut self, range: SymbolRange);
/// Walk the heap tree for `value`, building its SymbolRange, then code it once.
/// Provided; unrolls because N (hence n_bits) is a const after monomorphization.
fn encode_tree<const N: usize>(&mut self, ctx: &mut [BitContext; N], value: usize) {
let n_bits = N.ilog2();
let mut range = SymbolRange::full();
let mut node = 0usize;
for i in (0..n_bits).rev() {
let c = &mut ctx[node];
let split = range.split(c.probability(), i + 1); // r = i+1 levels remain
let bit = (value >> i) & 1 == 1;
range = if bit { range.upper(split) } else { range.lower(split) };
*c = c.adapt(bit); // identical adaptation
node = (node << 1) + 1 + bit as usize;
}
self.encode_symbol(range);
}
}
pub trait EntropyDecoder {
// ...existing decode_bits / decode_bit / decode_incompressible_bytes...
/// Peek the current slot in [0, M) without consuming it.
fn decode_symbol_slot(&mut self) -> u32;
/// Consume the symbol whose `range` contains the peeked `slot`.
fn decode_symbol_advance(&mut self, range: SymbolRange, slot: u32);
/// Walk the heap tree driven by the peeked slot; returns the decoded value 0..N.
fn decode_tree<const N: usize>(&mut self, ctx: &mut [BitContext; N]) -> usize {
let n_bits = N.ilog2();
let slot = self.decode_symbol_slot();
let mut range = SymbolRange::full();
let mut node = 0usize;
for i in (0..n_bits).rev() {
let c = &mut ctx[node];
let split = range.split(c.probability(), i + 1);
let bit = !range.lower(split).contains(slot); // slot in upper child?
range = if bit { range.upper(split) } else { range.lower(split) };
*c = c.adapt(bit);
node = (node << 1) + 1 + bit as usize;
}
self.decode_symbol_advance(range, slot);
node - (N - 1) // == decoded value
}
}
```
Both directions touch the same `n_bits` contexts and do the same `adapt`s — adaptive
behaviour is identical to per-bit; only the renorm count drops from `n_bits` to 1.
### 3. Call sites stay trivial and readable (review point 4)
```rust
// byte.rs — u8
fn encode<E>(&self, w: &mut E, ctx: &mut ByteContext) { w.encode_tree(&mut ctx.0, *self as usize) }
fn decode<D>(r: &mut D, ctx: &mut ByteContext) -> Result<u8> { Ok(r.decode_tree(&mut ctx.0) as u8) }
// bits.rs — Bits<N>
fn encode<E>(&self, w: &mut E, ctx: &mut BitsContext<N>) { w.encode_tree(&mut ctx.0, self.value as usize) }
fn decode<D>(r: &mut D, ctx: &mut BitsContext<N>) -> Result<Self> { Ok(Self { value: r.decode_tree(&mut ctx.0) as u8 }) }
```
`UBits<N>` (`small_num!`) is identical. `char` benefits transitively via `Bits`
([string.rs:43-50](../../src/compactly/src/v2/string.rs#L43-L50)). The `N` const flows
from the context array type, so no per-call-site arithmetic. Leave the `Sorted<u8>`
mid-tree-entry path ([byte.rs:343-377](../../src/compactly/src/v2/byte.rs#L343-L377))
on per-bit (it starts `node` nonzero; Plan #14 removes it).
### 4. Coder implementations of the interval primitive
- **`Range`**: `encode_symbol` narrows immediately —
`lo' = lo + (width>>BITS)*start`, `hi' = lo + (width>>BITS)*(start+width_sym)`,
then `ready_bytes()`. `decode_symbol_slot = (value - lo) / (width>>BITS)`;
`advance` narrows the same way + `consume_decoded_bytes`. `u64` width has huge
headroom (BITS of 64 consumed/symbol).
- **`Ans`**: `decode_symbol_slot = state & (M-1)`;
`advance: state = range.width*(state>>BITS) + slot - range.start`, renorm to keep
`state >= M`. Encode is deferred/reversed, so the buffer becomes
`enum Op { Bit(bool, Probability), Sym(SymbolRange) }` replayed in reverse;
`encode_symbol` does rANS `state = (state/width)<<BITS + state%width + start` with
renorm-out (the `/width` divide is rANS's main encode cost). **Impl note:** unify
the renorm invariant so per-bit (M=256) and per-symbol (M=2^16) ops can share one
stream/state range — verify in the prototype.
- **`Millibits`**: `encode_symbol` adds `-log2(width/M)` — a *more* accurate size
estimate than `n_bits` separate per-bit estimates.
- **`Raw`**: pack/unpack the `BITS`-wide slot. Correctness only.
## Precision & correctness — distribution-independent (revises my u64 take)
The per-bit scheme is effectively one symbol over total `256^n_bits` (`2^64` for a
byte), renormalized each level, so its precision is ~unbounded. A single step over
`M = 2^BITS` caps precision at `BITS`. The danger is **information loss**, not just
compression: if a child interval cannot fit all its descendant leaves with width
≥ 1, two values collide and decode becomes ambiguous.
The fix is the **reserve clamp** in `SymbolRange::split`: a node with `r` levels
remaining reserves `2^(r-1)` for each child, so every one of its `2^r` descendant
leaves is guaranteed ≥ 1 slot. This needs only `M >= 2^n_bits`, which holds for all
trees here (`n_bits <= 8`, `M = 2^16`). With this clamp the partition is always
valid and **lossless by construction, for any distribution**.
Compression loss is then *only* the clamp nudging a split, which happens only when a
bit is within `reserve/width ≈ 2^(n_bits-1-BITS)` of certain — for a byte at
`M=2^16` that's `~2^-9 ≈ 0.2%`, i.e. essentially-certain bits that cost ≈0 anyway.
So the size delta vs per-bit is tiny and can fall on either side (single-step also
*avoids* per-level 8-bit rounding waste). It must still be measured across diverse
data, but there is no skew-dependent cliff.
### On widening to u64 / `M = 2^32` (your question)
With the correct reserve clamp, **`M = 2^16` on the existing `u32` `Ans` state is
sufficient and near-lossless for every ≤8-bit tree, regardless of skew** — so u64 is
*not* needed for `u8`/`Bits<N>`/`UBits<N>`. (This supersedes my earlier "~1 skewed
level" framing, which assumed a naive freq≥1 clamp.) u64/`2^32` would only matter if
we later fuse **deeper** trees (>8 bits) into a single symbol; its costs then are: a
64-bit `div` in rANS *encode* (division is the dominant encode cost), doubled state
footprint and 8-byte flush/renorm (worse for any future interleaving,
[[ans-interleaving-dead-end]]). `Range` is already `u64`, so larger `M` is cheap
there — but a shared `M` keeps one format. **Recommendation: `SYMBOL_BITS = 16`,
`u32` `Ans`.** Keep `BITS` a single named const so a future deeper-fusion experiment
can bump it.
## Expected benefit vs cost (honest)
The dominant per-symbol costs — `n_bits` `BitContext` reads and `n_bits` `adapt`
lookups — are **unchanged**. We trade `n_bits - 1` renorm branches for `n_bits`
multiplies + one renorm. So a plausibly wash-to-modest decode win, riding *on top of*
Plan #2's bit-exact register-residency win, with a small, bounded, possibly-positive
size delta. Only measurement decides — land #2 first as the safe baseline.
## Suggested order
1. Land Plan #2 (`decode_tree` register-residency) first.
2. Add `SymbolRange` + the four trait additions; implement for **`Ans` and `Range`**
at `BITS = 16`; route `u8` first.
3. A/B on the `comparison` suite (OPTIMIZING.md methodology: `taskset -c 2 perf stat
-e cpu_core/cycles/`, min of pinned runs, >90% idle), capturing **cycles and
size** across the *full* benchmark set (not one workload).
4. Decide; expand to `Bits<N>`/`UBits<N>`; revisit deeper fusion only if motivated.
## Verification
- **Round-trip incl. forced clamping:** standalone encode→decode over random
bytes/`Bits<N>` and over adversarially-skewed `BitContext`s that force the clamp,
for every coder (mirror `check_ans_coder`/`encode_decode`).
- **Determinism:** assert encode and decode build identical `SymbolRange`s.
- **Mixed-stream:** a struct with interleaved `bool` and `u8` fields round-trips on
both coders (validates the unified renorm invariant).
- **Size + speed gate:** the bench A/B — size delta is make-or-break; a speed win
that worsens compression is a regression here.
- `cargo test` green; `assert_bits!`/`assert_size!` numbers for retargeted types will
**change** (new format) — update and note the shift per CLAUDE.md.
- Update OPTIMIZING.md with measured cycle **and** size deltas.