nx_zstd_fse.nx source
↩ module page · 189 lines · 6592 B
1// nx_zstd_fse.nx -- FSE (tANS) decoding-table construction for Zstandard.
2//
3// FSE is the entropy engine underneath zstd: literal lengths, match lengths
4// and offsets are each FSE-coded, and the literals Huffman weights are too.
5// Nothing in the tree had it -- nx_rans.nx is the same FAMILY (asymmetric
6// numeral systems) but the range variant, not the table-driven one zstd uses.
7//
8// THE SPREAD. A decoding table is built by walking a stride across the table
9// and dropping each symbol `count` times. The stride
10// step = (size>>1) + (size>>3) + 3
11// is chosen to be coprime with the table size so the walk visits every cell
12// exactly once. That coprimality FAILS for size 8 (step 8, 8&7 == 0, the walk
13// never advances) -- which is exactly why zstd's minimum accuracy log is 5.
14// We REFUSE a table_log below that rather than emit a table whose cells were
15// silently overwritten.
16//
17// LOW-PROBABILITY SYMBOLS. A normalized count of -1 means "less than one in
18// this table" -- those symbols are placed from the TOP of the table downward
19// and start at state 1. They are not an error and must not be clamped to 0,
20// or the rarest symbols become undecodable.
21//
22// genealogy_id: zstandard_rfc8878_fse
23// lineage_id: nx_zstd_fse_v1
24// license_tier: ORIGINAL
25
26import "nx_syscalls.nx"
27
28const NX_FSE_MIN_LOG: i64 = 5
29const NX_FSE_MAX_LOG: i64 = 12
30const NX_FSE_MAX_SYMBOL: i64 = 256
31const NX_FSE_TBL_BYTES: i64 = 48
32
33struct NxFseTable {
34 table_log: i64,
35 table_size: i64,
36 symbol: i64,
37 nb_bits: i64,
38 new_state: i64,
39}
40
41// position of the most-significant set bit; -1 for 0
42func nx_fse_highbit(v: i64) -> i64 {
43 if v <= 0 { return 0 - 1 }
44 var x: i64 = v
45 var n: i64 = 0
46 while x > 1 { x = x >> 1; n = n + 1 }
47 return n
48}
49
50func nx_fse_step(table_size: i64) -> i64 {
51 return (table_size >> 1) + (table_size >> 3) + 3
52}
53
54// ===== build the decoding table ===================================
55//
56// norm[s] = normalized count for symbol s: positive = that many cells,
57// -1 = a "less than one" symbol, 0 = absent. The counts must sum to exactly
58// the table size (counting -1 as one cell) -- a table that does not fill
59// exactly is a malformed stream, and we return 0 rather than decode from
60// cells that were never written.
61
62func nx_fse_build_dtable(norm: *i64, max_symbol: i64, table_log: i64) -> *NxFseTable {
63 if table_log < NX_FSE_MIN_LOG { return 0 as *NxFseTable }
64 if table_log > NX_FSE_MAX_LOG { return 0 as *NxFseTable }
65 if max_symbol < 0 { return 0 as *NxFseTable }
66 if max_symbol >= NX_FSE_MAX_SYMBOL { return 0 as *NxFseTable }
67
68 let table_size: i64 = 1 << table_log
69 let mask: i64 = table_size - 1
70 let step: i64 = nx_fse_step(table_size)
71
72 // the counts must account for exactly table_size cells
73 var total: i64 = 0
74 var s: i64 = 0
75 while s <= max_symbol {
76 let c: i64 = norm[s]
77 if c < (0 - 1) { return 0 as *NxFseTable }
78 if c == (0 - 1) { total = total + 1 } else { total = total + c }
79 s = s + 1
80 }
81 if total != table_size { return 0 as *NxFseTable }
82
83 let cell_sym: *i64 = sys_mmap(table_size * 8 + 64) as *i64
84 let cell_bits: *i64 = sys_mmap(table_size * 8 + 64) as *i64
85 let cell_next: *i64 = sys_mmap(table_size * 8 + 64) as *i64
86 let sym_next: *i64 = sys_mmap(NX_FSE_MAX_SYMBOL * 8 + 64) as *i64
87
88 var i: i64 = 0
89 while i < table_size { cell_sym[i] = 0 - 1; i = i + 1 }
90 i = 0
91 while i < NX_FSE_MAX_SYMBOL { sym_next[i] = 0; i = i + 1 }
92
93 // low-probability symbols occupy the top of the table, descending
94 var high_threshold: i64 = table_size - 1
95 s = 0
96 while s <= max_symbol {
97 if norm[s] == (0 - 1) {
98 cell_sym[high_threshold] = s
99 high_threshold = high_threshold - 1
100 sym_next[s] = 1
101 }
102 s = s + 1
103 }
104
105 // everything else is spread by the coprime stride, skipping the
106 // reserved top region
107 var position: i64 = 0
108 s = 0
109 while s <= max_symbol {
110 let c: i64 = norm[s]
111 if c > 0 {
112 var k: i64 = 0
113 while k < c {
114 cell_sym[position] = s
115 position = (position + step) & mask
116 var guard: i64 = 0
117 while position > high_threshold {
118 position = (position + step) & mask
119 guard = guard + 1
120 if guard > table_size { k = c; guard = 0 }
121 }
122 k = k + 1
123 }
124 sym_next[s] = c
125 }
126 s = s + 1
127 }
128
129 // the spread must land back where it started; if it does not, the stride
130 // was not coprime with the size and cells were overwritten
131 if position != 0 { return 0 as *NxFseTable }
132
133 // every cell must have received a symbol
134 i = 0
135 while i < table_size {
136 if cell_sym[i] < 0 { return 0 as *NxFseTable }
137 i = i + 1
138 }
139
140 // per-cell state transition: the number of bits to read next, and the
141 // base state those bits are added to
142 i = 0
143 while i < table_size {
144 let sym: i64 = cell_sym[i]
145 let next_state: i64 = sym_next[sym]
146 sym_next[sym] = next_state + 1
147 let nb: i64 = table_log - nx_fse_highbit(next_state)
148 cell_bits[i] = nb
149 cell_next[i] = (next_state << nb) - table_size
150 i = i + 1
151 }
152
153 let t: *NxFseTable = sys_mmap(NX_FSE_TBL_BYTES) as *NxFseTable
154 t.table_log = table_log
155 t.table_size = table_size
156 t.symbol = cell_sym as i64
157 t.nb_bits = cell_bits as i64
158 t.new_state = cell_next as i64
159 return t
160}
161
162// ===== accessors ==================================================
163//
164// Bounds-checked: an out-of-range state returns -1 rather than reading past
165// the table. A decoder that walks off its table must fail, not improvise.
166
167func nx_fse_cell_symbol(t: *NxFseTable, state: i64) -> i64 {
168 if t == (0 as *NxFseTable) { return 0 - 1 }
169 if state < 0 { return 0 - 1 }
170 if state >= t.table_size { return 0 - 1 }
171 let a: *i64 = t.symbol as *i64
172 return a[state]
173}
174
175func nx_fse_cell_nbbits(t: *NxFseTable, state: i64) -> i64 {
176 if t == (0 as *NxFseTable) { return 0 - 1 }
177 if state < 0 { return 0 - 1 }
178 if state >= t.table_size { return 0 - 1 }
179 let a: *i64 = t.nb_bits as *i64
180 return a[state]
181}
182
183func nx_fse_cell_newstate(t: *NxFseTable, state: i64) -> i64 {
184 if t == (0 as *NxFseTable) { return 0 - 1 }
185 if state < 0 { return 0 - 1 }
186 if state >= t.table_size { return 0 - 1 }
187 let a: *i64 = t.new_state as *i64
188 return a[state]
189}