FSE (Finite State Entropy) decoding for zstd (RFC 8878 §4.1): the normalized probability table description (forward bitstream), the decoding-table construction, and one decode step.
A table cell is {symbol, nb_bits, new_state_base}; decoding reads symbol
from the current state and computes the next state as
new_state_base + read_bits(nb_bits) (a reverse reader).
Summary
Functions
Builds the decoding table from normalized counts (with -1 = lowprob).
One FSE decode step: {symbol, next_reader} for the current state.
Parses an FSE table description from the head of bin. Returns
{:ok, cells, max_symbol, rest} where cells maps state (0..tableSize-1)
to {symbol, nb_bits, new_state_base} and rest is the unconsumed,
byte-aligned remainder. max_accuracy_log is the context's cap (RFC 8878:
9 for LL/ML tables, 8 for offset tables, 6 for Huffman-weight tables).
The cell for a state without consuming bits (final-symbol peeks).
The table's accuracy-log-equivalent: highbit of the table size.
Functions
@spec build([integer()], non_neg_integer()) :: {:ok, %{ optional(non_neg_integer()) => {non_neg_integer(), non_neg_integer(), non_neg_integer()} }} | {:error, term()}
Builds the decoding table from normalized counts (with -1 = lowprob).
Lowprob (-1) cells are placed from the table's END retreating; regular
symbols spread from position 0 with the RFC step
(ts >>> 1) + (ts >>> 3) + 3, skipping occupied lowprob cells; place FIRST
then advance. Each cell's nb/newState derive from the per-symbol nextState
counter (count, count+1, ... in position order).
@spec decode( bitreader_state :: non_neg_integer(), map(), Capstan.Zstd.BitReader.Reverse.t() ) :: {non_neg_integer(), non_neg_integer(), Capstan.Zstd.BitReader.Reverse.t()}
One FSE decode step: {symbol, next_reader} for the current state.
@spec read_table(binary(), non_neg_integer(), non_neg_integer()) :: {:ok, %{ optional(non_neg_integer()) => {non_neg_integer(), non_neg_integer(), non_neg_integer()} }, non_neg_integer(), binary()} | {:error, term()}
Parses an FSE table description from the head of bin. Returns
{:ok, cells, max_symbol, rest} where cells maps state (0..tableSize-1)
to {symbol, nb_bits, new_state_base} and rest is the unconsumed,
byte-aligned remainder. max_accuracy_log is the context's cap (RFC 8878:
9 for LL/ML tables, 8 for offset tables, 6 for Huffman-weight tables).
The cell for a state without consuming bits (final-symbol peeks).
The table's accuracy-log-equivalent: highbit of the table size.