code wiki / (root) / nx_zstd_seqdec_gate.nx

nx_zstd_seqdec_gate.nx

buildroot/runtime/nx_zstd_seqdec_gate.nx

8404 B195 linesdepth 5pulls 8 transitivereach 0 importersview sourcekind gate/prooftopic zstd
docsdependenciesstructsconstsfunctions

about

nx_zstd_seqdec_gate.nx -- proves zstd's repeat-offset machine and sequence loop. The repeat-offset rules are pure logic with no bitstream involved, so they can be proven EXHAUSTIVELY -- and they are the part of zstd most likely to be subtly wrong, because the spec's behaviour is genuinely surprising: T2 pins the ZERO-LITERAL SLIDE. With literals the mapping is 1->rep1, 2->rep2, 3->rep3. WITHOUT literals it slides: 1->rep2, 2->rep3, and 3->rep1 MINUS ONE BYTE. That last case is not a repeat at all. A decoder missing it is correct until the first zero-literal sequence and wrong forever after -- and those are common in exactly the repetitive data zstd is best at, so it fails on the files that matter. T3 pins that Offset_Value 1 WITH literals does NOT reorder the history, while every other repeat case moves the used value to the front. Reordering on that one too looks harmless and silently desynchronises from the encoder. T4 pins that idx 1 leaves Repeated_Offset3 untouched while idx 2 and 3 shift it -- the asymmetry inside the reorder itself. license_tier: ORIGINAL

dependencies 7 imports · 0 importers

nx_syscalls.nx nx_zstd_fse.nx nx_zstd_bits.nx nx_zstd_fse_dec.nx nx_zstd_seq.nx nx_zstd_seqtab.nx nx_zstd_seqdec.nx nx_zstd_seqdec_gate.nx

imports: nx_syscalls.nxnx_zstd_fse.nxnx_zstd_bits.nxnx_zstd_fse_dec.nxnx_zstd_seq.nxnx_zstd_seqtab.nxnx_zstd_seqdec.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_zstd_rep_init nx_zstd_rep_apply nx_zstd_seqtab_ll_table sys_mmap ↻ nx_zstd_seqtab_ll nx_fse_build_dtable nx_fse_step sys_mmap ↻ nx_fse_highbit nx_zstd_seqtab_ml_table sys_mmap ↻ nx_zstd_seqtab_ml nx_fse_build_dtable ↻ nx_zstd_seqtab_of_table sys_mmap ↻ nx_zstd_seqtab_of nx_fse_build_dtable ↻ nx_zstd_bits_init nx_zb_at nx_zb_highbit8 sys_mmap ↻ nx_zstd_seq_decode_all sys_mmap ↻ nx_zstd_fse_state_init nx_zstd_bits_read nx_zb_at ↻ nx_zstd_rep_init ↻ nx_zstd_seq_one nx_zstd_fse_state_symbol nx_fse_cell_symbol nx_zstd_ll_base nx_zstd_ml_base nx_zstd_of_base nx_zstd_of_extra nx_zstd_bits_read ↻ nx_zstd_ml_extra nx_zstd_ll_extra nx_zstd_rep_apply ↻

structs

none

consts

none

functions

30func g_puts(s: *u8) -> i64
called by 2: g_putnmain calls 1: sys_write
37func g_putn(v: i64) -> i64
called by 1: main calls 3: sys_mmapg_putssys_write
51func main() -> i64