Capstan.Zstd.Fse (Capstan v1.2.1)

Copy Markdown View Source

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

build(counts, accuracy_log)

@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).

decode(state, cells, reader)

@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.

read_table(bin, max_symbol_value, max_accuracy_log \\ 9)

@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).

symbol(state, cells)

The cell for a state without consuming bits (final-symbol peeks).

table_log(table_size)

The table's accuracy-log-equivalent: highbit of the table size.