nx_range_coder.nx source
↩ module page · 240 lines · 7389 B
1// nx_range_coder.nx -- arithmetic (range) coder for the Nishi voice
2// codec. Phase 4a building block. Pure integer; tier-0 ready.
3//
4// What it does: takes a stream of symbols, each with a probability
5// distribution, and emits a near-optimal-entropy byte stream. The
6// decoder reverses. This is what makes the codec hit its target
7// bitrate -- LPC + ACE produce VALUES; range-coder packs them into
8// BYTES with near-Shannon-optimal density.
9//
10// Algorithm: standard binary arithmetic coder operating on 32-bit
11// integer range. Range starts at [0, 2^32). Each symbol narrows
12// the range proportional to its cumulative probability. When the
13// top byte is determined we emit it. RFC 6716 (Opus) section 4 has
14// the same shape; we re-derive from the algorithm, not the bytes.
15//
16// State is i64 to give headroom on the multiplications.
17//
18// genealogy_id: rissanen_1976_arithmetic_coding + opus_range_coder_4 +
19// rfc_6716_section_4
20// lineage_id: nishi_range_coder_q10
21
22// nx_safety_envelope:
23// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
24// sil_target: SIL1
25// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
26// verdict: NOT_YET_EVALUATED
27
28import "nx_syscalls_x86_64.nx"
29
30// Sealed verdict per encode/decode operation.
31const NX_RC_VERDICT_UNKNOWN: i64 = 0
32const NX_RC_VERDICT_OK: i64 = 1
33const NX_RC_VERDICT_BUF_FULL: i64 = 2
34const NX_RC_VERDICT_BAD_INPUT: i64 = 3
35const NX_RC_VERDICT_N: i64 = 4
36
37// Encoder state.
38struct RcEnc {
39 low: i64, // current low bound (32-bit logical)
40 rng: i64, // current range (32-bit logical)
41 out_buf: *u8,
42 out_cap: i64,
43 out_pos: i64,
44 carry_count: i64, // pending 0xff bytes for carry resolution
45 last_byte: i64, // -1 means "no last byte yet"
46 err: i64 // sticky error (NX_RC_VERDICT_*)
47}
48
49// Decoder state.
50struct RcDec {
51 val: i64, // current value window (32-bit logical)
52 rng: i64, // current range
53 in_buf: *u8,
54 in_len: i64,
55 in_pos: i64,
56 err: i64
57}
58
59func nx_rc_enc_init(s: *RcEnc, out_buf: *u8, out_cap: i64) -> i64 {
60 s.low = 0
61 s.rng = 0xffffffff
62 s.out_buf = out_buf
63 s.out_cap = out_cap
64 s.out_pos = 0
65 s.carry_count = 0
66 s.last_byte = -1
67 s.err = NX_RC_VERDICT_OK
68 return 0
69}
70
71// Internal: emit one byte; resolve carries.
72func _rc_enc_put_byte(s: *RcEnc, b: i64) -> i64 {
73 if s.out_pos >= s.out_cap {
74 s.err = NX_RC_VERDICT_BUF_FULL
75 return -1
76 }
77 s.out_buf[s.out_pos] = b & 0xff
78 s.out_pos = s.out_pos + 1
79 return 0
80}
81
82func _rc_enc_renorm(s: *RcEnc) -> i64 {
83 // While the top byte of low is determined, emit it.
84 while s.rng < 0x1000000 {
85 let byte: i64 = (s.low >> 24) & 0xff
86 if s.last_byte < 0 {
87 s.last_byte = byte
88 } else {
89 if byte == 0xff {
90 s.carry_count = s.carry_count + 1
91 } else {
92 // Carry-out: if there are pending 0xff bytes and the
93 // current emitted byte triggers a carry, propagate.
94 let carry: i64 = (s.low >> 32) & 1
95 if carry == 1 {
96 _rc_enc_put_byte(s, s.last_byte + 1)
97 var k: i64 = 0
98 while k < s.carry_count {
99 _rc_enc_put_byte(s, 0)
100 k = k + 1
101 }
102 } else {
103 _rc_enc_put_byte(s, s.last_byte)
104 var k2: i64 = 0
105 while k2 < s.carry_count {
106 _rc_enc_put_byte(s, 0xff)
107 k2 = k2 + 1
108 }
109 }
110 s.carry_count = 0
111 s.last_byte = byte & 0xff
112 }
113 }
114 s.low = (s.low << 8) & 0xffffffff
115 s.rng = (s.rng << 8) & 0xffffffff
116 }
117 return 0
118}
119
120// Encode a symbol with cumulative-probability [fl, fh) in a total of
121// `ft` (so the symbol occupies fraction (fh - fl) / ft of the range).
122func nx_rc_enc_symbol(s: *RcEnc, fl: i64, fh: i64, ft: i64) -> i64 {
123 if s.err != NX_RC_VERDICT_OK { return -1 }
124 if ft <= 0 { s.err = NX_RC_VERDICT_BAD_INPUT; return -1 }
125 if fl < 0 { s.err = NX_RC_VERDICT_BAD_INPUT; return -1 }
126 if fh > ft { s.err = NX_RC_VERDICT_BAD_INPUT; return -1 }
127 if fl >= fh { s.err = NX_RC_VERDICT_BAD_INPUT; return -1 }
128
129 let r: i64 = s.rng / ft
130 s.low = s.low + r * fl
131 if fh < ft {
132 s.rng = r * (fh - fl)
133 } else {
134 s.rng = s.rng - r * fl
135 }
136 _rc_enc_renorm(s)
137 return 0
138}
139
140// Finalise the encoder. Flushes the final low bytes.
141func nx_rc_enc_done(s: *RcEnc) -> i64 {
142 if s.err != NX_RC_VERDICT_OK { return s.err }
143 // Force-emit the carry-resolved tail.
144 let tail_low: i64 = s.low
145 var i: i64 = 0
146 while i < 4 {
147 let byte: i64 = (tail_low >> (24 - i*8)) & 0xff
148 if s.last_byte < 0 {
149 s.last_byte = byte
150 } else {
151 if byte == 0xff {
152 s.carry_count = s.carry_count + 1
153 } else {
154 _rc_enc_put_byte(s, s.last_byte)
155 var k: i64 = 0
156 while k < s.carry_count {
157 _rc_enc_put_byte(s, 0xff)
158 k = k + 1
159 }
160 s.carry_count = 0
161 s.last_byte = byte
162 }
163 }
164 i = i + 1
165 }
166 if s.last_byte >= 0 {
167 _rc_enc_put_byte(s, s.last_byte)
168 var k2: i64 = 0
169 while k2 < s.carry_count {
170 _rc_enc_put_byte(s, 0xff)
171 k2 = k2 + 1
172 }
173 }
174 return s.out_pos
175}
176
177// Decoder.
178func nx_rc_dec_init(d: *RcDec, in_buf: *u8, in_len: i64) -> i64 {
179 d.in_buf = in_buf
180 d.in_len = in_len
181 d.in_pos = 0
182 d.rng = 0xffffffff
183 d.err = NX_RC_VERDICT_OK
184 // Prime: load first 4 bytes into val.
185 var v: i64 = 0
186 var i: i64 = 0
187 while i < 4 {
188 var b: i64 = 0
189 if d.in_pos < d.in_len {
190 b = d.in_buf[d.in_pos]
191 d.in_pos = d.in_pos + 1
192 }
193 v = (v << 8) | b
194 i = i + 1
195 }
196 d.val = v & 0xffffffff
197 return 0
198}
199
200func _rc_dec_renorm(d: *RcDec) -> i64 {
201 while d.rng < 0x1000000 {
202 var b: i64 = 0
203 if d.in_pos < d.in_len {
204 b = d.in_buf[d.in_pos]
205 d.in_pos = d.in_pos + 1
206 }
207 d.val = ((d.val << 8) | b) & 0xffffffff
208 d.rng = (d.rng << 8) & 0xffffffff
209 }
210 return 0
211}
212
213// Returns the cumulative-frequency target the encoder must have used,
214// for the given `ft`. Caller looks up which symbol bracket contains
215// this value, then calls nx_rc_dec_update to advance.
216func nx_rc_dec_get_target(d: *RcDec, ft: i64) -> i64 {
217 if d.err != NX_RC_VERDICT_OK { return -1 }
218 let r: i64 = d.rng / ft
219 return d.val / r
220}
221
222func nx_rc_dec_update(d: *RcDec, fl: i64, fh: i64, ft: i64) -> i64 {
223 if d.err != NX_RC_VERDICT_OK { return -1 }
224 let r: i64 = d.rng / ft
225 d.val = d.val - r * fl
226 if fh < ft {
227 d.rng = r * (fh - fl)
228 } else {
229 d.rng = d.rng - r * fl
230 }
231 _rc_dec_renorm(d)
232 return 0
233}
234
235// Sealed-enum validity gate.
236func nx_rc_verdict_is_valid(v: i64) -> i64 {
237 if v < 0 { return 0 }
238 if v >= NX_RC_VERDICT_N { return 0 }
239 return 1
240}