code wiki / (root) / nx_zstd_fse_dec_gate.nx

nx_zstd_fse_dec_gate.nx

buildroot/runtime/nx_zstd_fse_dec_gate.nx

10197 B231 linesdepth 4pulls 5 transitivereach 0 importersview sourcekind gate/prooftopic zstd
docsdependenciesstructsconstsfunctions

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

nx_syscalls.nx nx_zstd_fse.nx nx_zstd_bits.nx nx_zstd_fse_dec.nx nx_zstd_fse_dec_gate.nx

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

main sys_mmap nx_fse_build_dtable nx_fse_step sys_mmap ↻ nx_fse_highbit nx_zstd_bits_init nx_zb_at nx_zb_highbit8 sys_mmap ↻ nx_zstd_bits_remaining nx_zstd_fse_state_init nx_zstd_bits_read nx_zb_at ↻ nx_zstd_fse_state_symbol nx_fse_cell_symbol nx_zstd_fse_state_cost nx_fse_cell_nbbits nx_zstd_fse_state_next nx_fse_cell_nbbits ↻ nx_fse_cell_newstate nx_zstd_bits_read ↻ g_puts sys_write sys_exit g_putn sys_mmap ↻ g_puts ↻ sys_write ↻

structs

none

consts

none

functions

29func g_puts(s: *u8) -> i64
called by 2: g_putnmain calls 1: sys_write
36func g_putn(v: i64) -> i64
called by 1: main calls 3: sys_mmapg_putssys_write
50func main() -> i64