nx_bitstream.nx source
↩ module page · 312 lines · 10686 B
1// nx_bitstream.nx -- bit-level reader for packed-binary formats.
2//
3// The foundation primitive that every bit-packed format decoder
4// composes against:
5// - DEFLATE (RFC 1951) -- LSB-first
6// - GIF LZW -- LSB-first
7// - JPEG Huffman segments -- MSB-first
8// - FLAC / Vorbis / Opus -- MSB-first
9// - VP8 / VP9 -- mixed (arithmetic + raw)
10// - MP3 / AAC -- MSB-first
11//
12// Two-variant API: read_lsb_first vs read_msb_first. Caller picks
13// per spec. Both share the same backing byte buffer + bit cursor.
14//
15// genealogy_id: substrate_format_decoders_foundation_2026_05_16
16// lineage_id: bitstream_v1
17
18// nx_safety_envelope:
19// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
20// sil_target: SIL1
21// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
22// verdict: NOT_YET_EVALUATED
23
24import "nx_syscalls.nx"
25import "nx_runtime.nx"
26import "nx_tier.nx"
27const NX_MAGIC_61185: i64 = 61185
28
29// ===== bitstream struct ===========================================
30
31struct NxBitStream {
32 data: *u8, // byte buffer
33 size: nx_int, // bytes available
34 byte_pos: nx_int, // current byte index [0, size)
35 bit_pos: nx_int, // 0..7 within current byte
36 overflow: nx_int, // 1 if read past end attempted
37}
38
39const NX_BS_BYTES: nx_size = 40
40
41// ===== alloc ======================================================
42
43func nx_bitstream_alloc(data: *u8, size: nx_int) -> *NxBitStream {
44 if size < 0 { return 0 as *NxBitStream }
45 let p: *u8 = sys_mmap(NX_BS_BYTES)
46 let bs: *NxBitStream = p as *NxBitStream
47 bs.data = data
48 bs.size = size
49 bs.byte_pos = 0
50 bs.bit_pos = 0
51 bs.overflow = 0
52 return bs
53}
54
55// ===== bits remaining =============================================
56
57func nx_bitstream_bits_remaining(bs: *NxBitStream) -> nx_int {
58 if bs.byte_pos >= bs.size { return 0 }
59 let full_bytes_remaining: nx_int = bs.size - bs.byte_pos - 1
60 let bits_in_current: nx_int = 8 - bs.bit_pos
61 return bits_in_current + full_bytes_remaining * 8
62}
63
64// ===== read u8 helper =============================================
65
66func _bs_peek_byte(bs: *NxBitStream, offset: nx_int) -> nx_int {
67 let pos: nx_int = bs.byte_pos + offset
68 if pos < 0 { return 0 }
69 if pos >= bs.size { return 0 }
70 let b: nx_int = bs.data[pos] as nx_int
71 return b & 255
72}
73
74// ===== read LSB-first ============================================
75//
76// DEFLATE / GIF-LZW convention: the FIRST bit consumed is the
77// LEAST-significant bit of the first byte. Multi-bit values
78// accumulate with later bits at HIGHER positions.
79//
80// Bit layout (byte 0xAB = 10101011):
81// bit 0 = 1 (LSB)
82// bit 1 = 1
83// bit 2 = 0
84// bit 3 = 1
85// bit 4 = 0
86// bit 5 = 1
87// bit 6 = 0
88// bit 7 = 1 (MSB)
89//
90// Reading 3 bits from 0xAB at bit_pos=0 -> bits 0,1,2 = 1,1,0 -> 011 (LSB-first) = 3.
91
92func nx_bitstream_read_lsb(bs: *NxBitStream, n_bits: nx_int) -> nx_int {
93 if n_bits <= 0 { return 0 }
94 if n_bits > 32 { return 0 }
95 if nx_bitstream_bits_remaining(bs) < n_bits {
96 bs.overflow = 1
97 return 0
98 }
99 var result: nx_int = 0
100 var bits_done: nx_int = 0
101 while bits_done < n_bits {
102 let cur_byte: nx_int = _bs_peek_byte(bs, 0)
103 let bits_in_byte: nx_int = 8 - bs.bit_pos
104 var take: nx_int = bits_in_byte
105 let remaining: nx_int = n_bits - bits_done
106 if take > remaining { take = remaining }
107 let shift_from: nx_int = bs.bit_pos
108 let mask: nx_int = (1 << take) - 1
109 let chunk: nx_int = (cur_byte >> shift_from) & mask
110 result = result | (chunk << bits_done)
111 bs.bit_pos = bs.bit_pos + take
112 if bs.bit_pos >= 8 {
113 bs.byte_pos = bs.byte_pos + 1
114 bs.bit_pos = 0
115 }
116 bits_done = bits_done + take
117 }
118 return result
119}
120
121// ===== read MSB-first =============================================
122//
123// JPEG / FLAC / MP3 / AAC convention: the FIRST bit consumed is the
124// MOST-significant bit of the first byte. Multi-bit values
125// accumulate with later bits at LOWER positions.
126//
127// Reading 3 bits from 0xAB at bit_pos=0 -> bits 7,6,5 = 1,0,1 -> 101 = 5.
128
129func nx_bitstream_read_msb(bs: *NxBitStream, n_bits: nx_int) -> nx_int {
130 if n_bits <= 0 { return 0 }
131 if n_bits > 32 { return 0 }
132 if nx_bitstream_bits_remaining(bs) < n_bits {
133 bs.overflow = 1
134 return 0
135 }
136 var result: nx_int = 0
137 var bits_done: nx_int = 0
138 while bits_done < n_bits {
139 let cur_byte: nx_int = _bs_peek_byte(bs, 0)
140 let bits_in_byte: nx_int = 8 - bs.bit_pos
141 var take: nx_int = bits_in_byte
142 let remaining: nx_int = n_bits - bits_done
143 if take > remaining { take = remaining }
144 // For MSB-first, the bit we want next is at position (8 - 1 - bit_pos).
145 // After taking `take` bits, the chunk lives at positions
146 // [8 - bit_pos - take, 8 - bit_pos)
147 // within the byte (high to low).
148 let high_pos: nx_int = 8 - bs.bit_pos
149 let shift_from: nx_int = high_pos - take
150 let mask: nx_int = (1 << take) - 1
151 let chunk: nx_int = (cur_byte >> shift_from) & mask
152 result = (result << take) | chunk
153 bs.bit_pos = bs.bit_pos + take
154 if bs.bit_pos >= 8 {
155 bs.byte_pos = bs.byte_pos + 1
156 bs.bit_pos = 0
157 }
158 bits_done = bits_done + take
159 }
160 return result
161}
162
163// ===== peek (non-consuming) ======================================
164
165func nx_bitstream_peek_lsb(bs: *NxBitStream, n_bits: nx_int) -> nx_int {
166 let saved_byte: nx_int = bs.byte_pos
167 let saved_bit: nx_int = bs.bit_pos
168 let saved_overflow: nx_int = bs.overflow
169 let val: nx_int = nx_bitstream_read_lsb(bs, n_bits)
170 bs.byte_pos = saved_byte
171 bs.bit_pos = saved_bit
172 bs.overflow = saved_overflow
173 return val
174}
175
176func nx_bitstream_peek_msb(bs: *NxBitStream, n_bits: nx_int) -> nx_int {
177 let saved_byte: nx_int = bs.byte_pos
178 let saved_bit: nx_int = bs.bit_pos
179 let saved_overflow: nx_int = bs.overflow
180 let val: nx_int = nx_bitstream_read_msb(bs, n_bits)
181 bs.byte_pos = saved_byte
182 bs.bit_pos = saved_bit
183 bs.overflow = saved_overflow
184 return val
185}
186
187// ===== byte align (skip remaining bits of current byte) ==========
188
189func nx_bitstream_byte_align(bs: *NxBitStream) -> nx_int {
190 if bs.bit_pos > 0 {
191 bs.byte_pos = bs.byte_pos + 1
192 bs.bit_pos = 0
193 }
194 return 0
195}
196
197// ===== skip n bits ===============================================
198
199func nx_bitstream_skip_bits(bs: *NxBitStream, n_bits: nx_int) -> nx_int {
200 if n_bits <= 0 { return 0 }
201 if nx_bitstream_bits_remaining(bs) < n_bits {
202 bs.overflow = 1
203 return 0 - 1
204 }
205 let total_bits: nx_int = bs.bit_pos + n_bits
206 bs.byte_pos = bs.byte_pos + (total_bits / 8)
207 bs.bit_pos = total_bits & 7
208 return 0
209}
210
211// ===== read aligned byte =========================================
212//
213// After byte_align, read one full byte. Convenience for DEFLATE
214// stored blocks + JPEG markers + WAV/RIFF chunk headers.
215
216func nx_bitstream_read_byte_aligned(bs: *NxBitStream) -> nx_int {
217 if bs.bit_pos != 0 { nx_bitstream_byte_align(bs) }
218 if bs.byte_pos >= bs.size {
219 bs.overflow = 1
220 return 0
221 }
222 let v: nx_int = bs.data[bs.byte_pos] as nx_int
223 bs.byte_pos = bs.byte_pos + 1
224 return v & 255
225}
226
227// ===== self-test ==================================================
228
229func main() -> nx_int {
230 // Test buffer: 0xAB 0xCD 0xEF 0x01 = 10101011 11001101 11101111 00000001
231 let buf: *u8 = (sys_mmap(4)) as *u8
232 buf[0] = 0xAB as u8
233 buf[1] = 0xCD as u8
234 buf[2] = 0xEF as u8
235 buf[3] = 0x01 as u8
236
237 // ---- bits_remaining ----
238 let bs1: *NxBitStream = nx_bitstream_alloc(buf, 4)
239 if nx_bitstream_bits_remaining(bs1) != 32 { return 1 }
240
241 // ---- LSB-first: 3 bits of 0xAB (10101011) -> bits 0,1,2 = 1,1,0 -> 011 = 3
242 let v3: nx_int = nx_bitstream_read_lsb(bs1, 3)
243 if v3 != 3 { return 2 }
244 if bs1.bit_pos != 3 { return 3 }
245 if nx_bitstream_bits_remaining(bs1) != 29 { return 4 }
246
247 // ---- LSB-first: next 5 bits of 0xAB -> bits 3,4,5,6,7 = 1,0,1,0,1 -> 10101 = 21
248 let v5: nx_int = nx_bitstream_read_lsb(bs1, 5)
249 if v5 != 21 { return 5 }
250 if bs1.byte_pos != 1 { return 6 }
251 if bs1.bit_pos != 0 { return 7 }
252
253 // ---- LSB-first cross-byte: next 8 bits = 0xCD = 205
254 let v8: nx_int = nx_bitstream_read_lsb(bs1, 8)
255 if v8 != 205 { return 8 }
256
257 // ---- LSB-first multi-byte: next 16 bits = 0xEF + 0x01.
258 // In LSB-first, value = byte0 | (byte1 << 8) = 0xEF | (0x01 << 8) = 0x01EF = 495
259 let v16: nx_int = nx_bitstream_read_lsb(bs1, 16)
260 if v16 != 495 { return 9 }
261 if nx_bitstream_bits_remaining(bs1) != 0 { return 10 }
262
263 // ---- LSB-first overflow ----
264 let v_over: nx_int = nx_bitstream_read_lsb(bs1, 1)
265 if bs1.overflow != 1 { return 11 }
266
267 // ---- MSB-first: from byte 0xAB
268 let bs2: *NxBitStream = nx_bitstream_alloc(buf, 4)
269 // 3 MSB bits of 0xAB = bits 7,6,5 = 1,0,1 -> 101 = 5
270 let m3: nx_int = nx_bitstream_read_msb(bs2, 3)
271 if m3 != 5 { return 20 }
272 if bs2.bit_pos != 3 { return 21 }
273 // next 5 MSB bits = bits 4,3,2,1,0 = 0,1,0,1,1 -> 01011 = 11
274 let m5: nx_int = nx_bitstream_read_msb(bs2, 5)
275 if m5 != 11 { return 22 }
276 if bs2.byte_pos != 1 { return 23 }
277 // Next full byte 0xCD as 8 MSB bits = 205
278 let m8: nx_int = nx_bitstream_read_msb(bs2, 8)
279 if m8 != 205 { return 24 }
280 // Next 16 MSB bits = 0xEF01 = 61185
281 let m16: nx_int = nx_bitstream_read_msb(bs2, 16)
282 if m16 != NX_MAGIC_61185 { return 25 }
283
284 // ---- peek_lsb (non-consuming) ----
285 let bs3: *NxBitStream = nx_bitstream_alloc(buf, 4)
286 let pk: nx_int = nx_bitstream_peek_lsb(bs3, 3)
287 if pk != 3 { return 30 }
288 if bs3.bit_pos != 0 { return 31 } // not advanced
289 let pk2: nx_int = nx_bitstream_read_lsb(bs3, 3)
290 if pk2 != 3 { return 32 }
291
292 // ---- byte_align ----
293 let bs4: *NxBitStream = nx_bitstream_alloc(buf, 4)
294 nx_bitstream_read_lsb(bs4, 3)
295 nx_bitstream_byte_align(bs4)
296 if bs4.byte_pos != 1 { return 40 }
297 if bs4.bit_pos != 0 { return 41 }
298
299 // ---- skip_bits ----
300 let bs5: *NxBitStream = nx_bitstream_alloc(buf, 4)
301 nx_bitstream_skip_bits(bs5, 11)
302 if bs5.byte_pos != 1 { return 50 }
303 if bs5.bit_pos != 3 { return 51 }
304
305 // ---- read_byte_aligned ----
306 let bs6: *NxBitStream = nx_bitstream_alloc(buf, 4)
307 nx_bitstream_read_lsb(bs6, 3)
308 let baligned: nx_int = nx_bitstream_read_byte_aligned(bs6)
309 if baligned != 205 { return 60 } // skipped rest of byte 0 -> read 0xCD = 205
310
311 return 0
312}