nx_zstd_bits.nx source
↩ module page · 235 lines · 8194 B
1// nx_zstd_bits.nx -- Zstandard's BACKWARD bitstream reader + Huffman weights.
2//
3// The piece between nx_zstd_fse.nx (entropy tables) and a working literals
4// section. Both zstd's Huffman streams and its FSE streams are read BACKWARDS
5// from the end of the buffer, which is unlike every other format in this tree
6// -- DEFLATE, VP8L, FLAC, VP8 and AV1 all read forward.
7//
8// THE STREAM ENDS WITH A MARKER BIT, NOT A LENGTH. The final byte's highest
9// SET bit is a sentinel: it and everything above it is padding, and the real
10// data ends immediately below it. So initialisation must find that bit and
11// start there. A reader that begins at the top of the last byte consumes
12// padding as data and every symbol after it is wrong; a reader that assumes a
13// fixed padding width works only when the payload happens to end byte-aligned.
14// A final byte of ZERO has no marker at all and is corrupt by definition --
15// it is REFUSED here rather than treated as eight padding bits.
16//
17// BITS ARE PACKED LSB-FIRST WITHIN A BYTE, AND READ HIGH-TO-LOW OVERALL. Those
18// two facts together are the whole trick: absolute bit k lives at
19// data[k >> 3] bit (k & 7) counting from the LSB, and reading walks k DOWNWARD
20// with the first bit taken becoming the MOST significant of the result.
21//
22// THE LAST HUFFMAN WEIGHT IS NOT STORED. Weights encode 2^(w-1) each, and the
23// total must reach the next power of two exactly; the final symbol's weight is
24// whatever completes it. A decoder that reads only the stored weights builds a
25// table missing its last symbol, which decodes most literals correctly and
26// then produces one wrong byte wherever that symbol appears.
27//
28// genealogy_id: zstandard_rfc8878_bitstream
29// lineage_id: nx_zstd_bits_v1
30// license_tier: ORIGINAL
31
32import "nx_syscalls.nx"
33
34const NX_ZB_READER_BYTES: i64 = 40
35const NX_ZB_MAX_WEIGHTS: i64 = 256
36const NX_ZB_MAX_TABLELOG: i64 = 12
37
38struct NxZstdBits {
39 data: i64,
40 size: i64,
41 cursor: i64,
42 overflow: i64,
43}
44
45func nx_zb_at(d: *u8, i: i64) -> i64 { return (d[i] as i64) & 255 }
46
47// highest set bit position (0..7) in a byte, or -1 if the byte is zero
48func nx_zb_highbit8(v: i64) -> i64 {
49 let b: i64 = v & 255
50 if b == 0 { return 0 - 1 }
51 var i: i64 = 7
52 while i >= 0 {
53 if ((b >> i) & 1) == 1 { return i }
54 i = i - 1
55 }
56 return 0 - 1
57}
58
59// ===== the backward reader ========================================
60//
61// Positions the cursor just below the sentinel bit. Returns 0 on an empty
62// buffer or a zero final byte, which carries no marker and is corrupt.
63
64func nx_zstd_bits_init(d: *u8, n: i64) -> *NxZstdBits {
65 if n <= 0 { return 0 as *NxZstdBits }
66 let last: i64 = nx_zb_at(d, n - 1)
67 let hb: i64 = nx_zb_highbit8(last)
68 if hb < 0 { return 0 as *NxZstdBits }
69 let b: *NxZstdBits = sys_mmap(NX_ZB_READER_BYTES) as *NxZstdBits
70 b.data = d as i64
71 b.size = n
72 // the sentinel sits at this absolute index; readable data is strictly below
73 b.cursor = (n - 1) * 8 + hb
74 b.overflow = 0
75 return b
76}
77
78func nx_zstd_bits_remaining(b: *NxZstdBits) -> i64 {
79 if b == (0 as *NxZstdBits) { return 0 }
80 return b.cursor
81}
82
83// Reads nbits going DOWNWARD; the first bit taken is the most significant.
84func nx_zstd_bits_read(b: *NxZstdBits, nbits: i64) -> i64 {
85 if b == (0 as *NxZstdBits) { return 0 }
86 if nbits <= 0 { return 0 }
87 if nbits > 32 { return 0 }
88 if b.cursor < nbits { b.overflow = 1; return 0 }
89 let d: *u8 = b.data as *u8
90 var v: i64 = 0
91 var i: i64 = 0
92 while i < nbits {
93 b.cursor = b.cursor - 1
94 let k: i64 = b.cursor
95 let bit: i64 = (nx_zb_at(d, k >> 3) >> (k & 7)) & 1
96 v = (v << 1) | bit
97 i = i + 1
98 }
99 return v
100}
101
102// PEEK does not move the cursor. Huffman decoding needs it: you look at
103// tableLog bits to index the table, learn the code's TRUE length from the
104// entry, and only then consume that many. Consuming tableLog bits up front
105// would over-read every code shorter than the maximum -- which is most of them.
106func nx_zstd_bits_peek(b: *NxZstdBits, nbits: i64) -> i64 {
107 if b == (0 as *NxZstdBits) { return 0 }
108 if nbits <= 0 { return 0 }
109 if nbits > 32 { return 0 }
110 let d: *u8 = b.data as *u8
111 var v: i64 = 0
112 var i: i64 = 0
113 var k: i64 = b.cursor
114 while i < nbits {
115 k = k - 1
116 var bit: i64 = 0
117 // past the start of the stream, peek pads with zeros rather than
118 // reading out of bounds -- the final codes of a stream legitimately
119 // sit against the boundary
120 if k >= 0 { bit = (nx_zb_at(d, k >> 3) >> (k & 7)) & 1 }
121 v = (v << 1) | bit
122 i = i + 1
123 }
124 return v
125}
126
127func nx_zstd_bits_skip(b: *NxZstdBits, nbits: i64) -> i64 {
128 if b == (0 as *NxZstdBits) { return 0 }
129 if nbits < 0 { return 0 }
130 if b.cursor < nbits { b.cursor = 0; b.overflow = 1; return 0 }
131 b.cursor = b.cursor - nbits
132 return 1
133}
134
135// ===== Huffman weights, direct form ===============================
136//
137// A header byte below 128 means the weights follow uncompressed, packed two
138// per byte, HIGH NIBBLE FIRST, with (header + 1) weights present.
139// Returns the number of weights written, or -1.
140
141func nx_zstd_weights_direct(d: *u8, n: i64, off: i64, hdr: i64, out: *i64) -> i64 {
142 if hdr < 0 { return 0 - 1 }
143 if hdr > 127 { return 0 - 1 }
144 let count: i64 = hdr + 1
145 if count > NX_ZB_MAX_WEIGHTS { return 0 - 1 }
146 let bytes: i64 = (count + 1) / 2
147 if off + bytes > n { return 0 - 1 }
148 var i: i64 = 0
149 while i < count {
150 let byte: i64 = nx_zb_at(d, off + (i >> 1))
151 if (i & 1) == 0 {
152 out[i] = (byte >> 4) & 15
153 } else {
154 out[i] = byte & 15
155 }
156 i = i + 1
157 }
158 return count
159}
160
161// ===== completing the weight set ==================================
162//
163// Each non-zero weight w contributes 2^(w-1). The total must reach an exact
164// power of two; the LAST symbol's weight is whatever completes it, and it is
165// never stored. Returns the inferred weight and writes it at out[count],
166// or -1 if the stored weights cannot be completed.
167
168func nx_zstd_weights_complete(out: *i64, count: i64) -> i64 {
169 if count <= 0 { return 0 - 1 }
170 var total: i64 = 0
171 var maxw: i64 = 0
172 var i: i64 = 0
173 while i < count {
174 let w: i64 = out[i]
175 if w < 0 { return 0 - 1 }
176 if w > NX_ZB_MAX_TABLELOG { return 0 - 1 }
177 if w > 0 { total = total + (1 << (w - 1)) }
178 if w > maxw { maxw = w }
179 i = i + 1
180 }
181 if total <= 0 { return 0 - 1 }
182
183 // the smallest power of two strictly greater than the running total
184 var pow: i64 = 1
185 while pow <= total {
186 pow = pow << 1
187 if pow > (1 << 20) { return 0 - 1 }
188 }
189 let rest: i64 = pow - total
190 // the remainder must itself be a power of two, or the set is malformed
191 if (rest & (rest - 1)) != 0 { return 0 - 1 }
192 var last: i64 = 1
193 var p: i64 = 1
194 while p < rest { p = p << 1; last = last + 1 }
195 if last > NX_ZB_MAX_TABLELOG { return 0 - 1 }
196 out[count] = last
197 return last
198}
199
200// ===== table log from the completed weights =======================
201
202func nx_zstd_weights_tablelog(out: *i64, total_count: i64) -> i64 {
203 if total_count <= 0 { return 0 - 1 }
204 var maxw: i64 = 0
205 var i: i64 = 0
206 while i < total_count {
207 if out[i] > maxw { maxw = out[i] }
208 i = i + 1
209 }
210 if maxw <= 0 { return 0 - 1 }
211 if maxw > NX_ZB_MAX_TABLELOG { return 0 - 1 }
212 return maxw
213}
214
215// ===== per-symbol code lengths ====================================
216//
217// A weight of 0 means the symbol is absent; otherwise the code length is
218// (tableLog + 1 - weight). Writes lengths into out_len, returns the count.
219
220func nx_zstd_weights_to_lengths(w: *i64, count: i64, table_log: i64, out_len: *i64) -> i64 {
221 if count <= 0 { return 0 - 1 }
222 if table_log <= 0 { return 0 - 1 }
223 var i: i64 = 0
224 while i < count {
225 if w[i] == 0 {
226 out_len[i] = 0
227 } else {
228 let l: i64 = table_log + 1 - w[i]
229 if l <= 0 { return 0 - 1 }
230 out_len[i] = l
231 }
232 i = i + 1
233 }
234 return count
235}