nx_zstd_fse_dec_gate.nx
buildroot/runtime/nx_zstd_fse_dec_gate.nx
about
nx_zstd_fse_dec_gate.nx -- proves the FSE decoding state machine.
T3 is the invariant that matters most: over a long decode the state must
ALWAYS stay inside the table and the symbol must always be one the
distribution actually contains. An FSE decoder whose newState baseline or
nbBits is off produces in-range garbage for a while and then walks out of
the table -- so a single decode proves nothing and a long run proves a lot.
T4 pins that nbBits of ZERO is legal. High-probability symbols cost no bits
to advance from; a decoder that treats zero as an error, or reads a bit
anyway, desynchronises on the first such state. The test asserts at least
one zero-cost state exists in a skewed distribution and that advancing from
it consumes nothing.
T5 pins DETERMINISM: the same stream and table must produce the same symbol
sequence every time. That is what makes an entropy decoder usable at all.
NOT PROVEN HERE, DELIBERATELY: the predefined distributions for literal
lengths, match lengths and offsets. Those are spec DATA and are not in the
module -- transcribing them from memory would yield a decoder that looks
right and disagrees with every other implementation.
license_tier: ORIGINAL
dependencies 4 imports · 0 importers
imports: nx_syscalls.nxnx_zstd_fse.nxnx_zstd_bits.nxnx_zstd_fse_dec.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| none |
functions
| 29 | func g_puts(s: *u8) -> i64 |
| 36 | func g_putn(v: i64) -> i64 |
| 50 | func main() -> i64 |