nx_zstd_fse_dec.nx source

1// nx_zstd_fse_dec.nx -- the FSE decoding state machine for zstd sequences. 2// 3// nx_zstd_fse.nx builds the table; this drives it. An FSE decoder is a state 4// that indexes the table: the entry names the symbol, and the NEXT state is 5// that entry's baseline plus a few freshly-read bits. Literal lengths, match 6// lengths and offsets each run their own independent state over the SAME 7// backward bitstream. 8// 9// THE SYMBOL COMES BEFORE THE UPDATE. Read the symbol at the CURRENT state, 10// then consume bits to move to the next. Doing it the other way round yields 11// a stream that is off by one symbol from the first sequence onward -- it 12// decodes, it is the right length, and every value is wrong. 13// 14// THE THREE STATES INTERLEAVE IN A FIXED ORDER. zstd initialises literal 15// length, then offset, then match length; and on each sequence it updates them 16// in the reverse order. They share one bit reader, so any deviation shifts 17// every subsequent read. This module exposes init/symbol/next as separate 18// operations precisely so the caller can express that ordering explicitly 19// rather than burying it in a loop. 20// 21// WHAT IS PROVEN HERE: the state machine's mechanics and invariants. The 22// PREDEFINED distribution tables for the three sequence alphabets are spec 23// DATA, not derivable, and are deliberately NOT included -- transcribing them 24// from memory would produce a decoder that looks right and disagrees with 25// every other implementation. They need to come from the specification text. 26// 27// genealogy_id: zstandard_rfc8878_fse_decoding 28// lineage_id: nx_zstd_fse_dec_v1 29// license_tier: ORIGINAL 30 31import "nx_syscalls.nx" 32import "nx_zstd_fse.nx" 33import "nx_zstd_bits.nx" 34 35// ===== state init ================================================= 36// 37// The initial state is tableLog raw bits off the backward stream. 38// Returns -1 if the table is absent or the stream is exhausted. 39 40func nx_zstd_fse_state_init(t: *NxFseTable, b: *NxZstdBits) -> i64 { 41 if t == (0 as *NxFseTable) { return 0 - 1 } 42 if b == (0 as *NxZstdBits) { return 0 - 1 } 43 let s: i64 = nx_zstd_bits_read(b, t.table_log) 44 if b.overflow == 1 { return 0 - 1 } 45 if s < 0 { return 0 - 1 } 46 if s >= t.table_size { return 0 - 1 } 47 return s 48} 49 50// ===== the symbol at the CURRENT state ============================ 51// 52// Always read before advancing. Reversing the two is a silent off-by-one 53// across the whole sequence list. 54 55func nx_zstd_fse_state_symbol(t: *NxFseTable, state: i64) -> i64 { 56 return nx_fse_cell_symbol(t, state) 57} 58 59// ===== advance to the next state ================================== 60// 61// newState = baseline + the next nbBits from the stream. nbBits may be ZERO, 62// which is legal and common for high-probability symbols -- a decoder that 63// treats zero as an error or reads a bit anyway desynchronises immediately. 64 65func nx_zstd_fse_state_next(t: *NxFseTable, b: *NxZstdBits, state: i64) -> i64 { 66 if t == (0 as *NxFseTable) { return 0 - 1 } 67 if b == (0 as *NxZstdBits) { return 0 - 1 } 68 let nb: i64 = nx_fse_cell_nbbits(t, state) 69 if nb < 0 { return 0 - 1 } 70 let base: i64 = nx_fse_cell_newstate(t, state) 71 if base < 0 { return 0 - 1 } 72 var add: i64 = 0 73 if nb > 0 { 74 add = nx_zstd_bits_read(b, nb) 75 if b.overflow == 1 { return 0 - 1 } 76 } 77 let ns: i64 = base + add 78 if ns < 0 { return 0 - 1 } 79 if ns >= t.table_size { return 0 - 1 } 80 return ns 81} 82 83// ===== bits remaining before a state can still advance ============ 84// 85// A caller decoding a known number of sequences needs to know whether the 86// stream can still feed them. Returns the bit count the next advance from 87// this state would consume, or -1. 88 89func nx_zstd_fse_state_cost(t: *NxFseTable, state: i64) -> i64 { 90 return nx_fse_cell_nbbits(t, state) 91}