nx_rangecoder.nx source
↩ module page · 232 lines · 14107 B
1// nx_rangecoder.nx -- sovereign BINARY RANGE CODER (CABAC/VP8-class), the entropy-coding SOTA lever (task #31).
2// The current nx_ventropy is CAVLC (fixed 4-bit run + 5-bit level-length) -> wasteful when the real symbol
3// distribution is skewed (it almost always is). A range coder with ADAPTIVE per-context probabilities codes
4// each binary decision at its true entropy (a p=0.97 flag costs ~0.04 bit, not 1). Design = the LZMA range
5// coder (carry via a cache byte + a pending-0xFF counter -- exact, well-understood), 12-bit probabilities,
6// adaptive update toward the observed bit. Bit-exact by construction; a divergence shows in the roundtrip gate.
7// license_tier: ORIGINAL
8
9import "nx_ventropy.nx" // ve_zz_idx / ve_zze / ve_blen / ve_zzd -- the coefficient block binarization
10// The 12-bit probability scale (P(bit==0) lives in 1..4095 of 4096), named ONCE and read by every site.
11const RC_MAGIC_4096: i64 = 4096
12const RC_MAGIC_4095: i64 = 4095
13const RC_NCTX: i64 = 11 // contexts used by rc_block_encode/decode (probs array must be >= this, seeded 2048)
14const RC_NCTX8: i64 = 24 // total contexts when 8x8 blocks are in the stream (11 for 4x4 + 13 for 8x8, below)
15// ⚠R1d MEASURED + REVERTED (2026-07-09): contexting the continue/EOB flag by coeff-count (buckets 24..31,
16// helpers rc_fbk4/rc_fbk8) is BIT-EXACT and saves ~0.3% bytes (rd_bench, PSNR unchanged) -- but the 32-ctx
17// probs budget caps it there, and a wire change for 0.3% isn't worth a vcv bump + dual entropy path. STAGED
18// for the batched neural-entropy generation (R2a), not deployed standalone. See vcodec-sota-roadmap memory.
19
20// ---- ENCODER: state = i64[5] = [low, range, cache, cacheSize, outpos] ----
21func rc_enc_init(st: *i64) -> i64 { st[0]=0; st[1]=0xFFFFFFFF; st[2]=0; st[3]=1; st[4]=0; return 0 }
22
23func rc_shift_low(st: *i64, out: *u8) -> i64 {
24 let low: i64 = st[0]
25 let lo32: i64 = low & 0xFFFFFFFF
26 let carry: i64 = (low >> 32) & 0xFF
27 if (lo32 < 0xFF000000) | (carry != 0) {
28 let cs: i64 = st[3]
29 out[st[4]] = ((st[2] + carry) & 0xFF) as u8; st[4] = st[4] + 1 // cache + carry
30 var j: i64 = 1
31 while j < cs { out[st[4]] = ((0xFF + carry) & 0xFF) as u8; st[4] = st[4] + 1; j = j + 1 }
32 st[2] = (lo32 >> 24) & 0xFF // new cache = top byte
33 st[3] = 0
34 }
35 st[3] = st[3] + 1
36 st[0] = (lo32 << 8) & 0xFFFFFFFF
37 return 0
38}
39
40// encode one bit under probability p = P(bit==0) in 1..4095 (12-bit). Renormalize when range < 2^24.
41func rc_enc_bit(st: *i64, out: *u8, p: i64, bit: i64) -> i64 {
42 let bound: i64 = (st[1] >> 12) * p
43 if bit == 0 { st[1] = bound } else { st[0] = st[0] + bound; st[1] = st[1] - bound }
44 while st[1] < 0x1000000 { st[1] = (st[1] << 8) & 0xFFFFFFFF; rc_shift_low(st, out) }
45 return 0
46}
47func rc_enc_flush(st: *i64, out: *u8) -> i64 { var i: i64=0; while i < 5 { rc_shift_low(st, out); i=i+1 } return st[4] }
48
49// ---- DECODER: state = i64[3] = [code, range, inpos] ----
50func rc_dec_init(st: *i64, in_: *u8) -> i64 {
51 st[1]=0xFFFFFFFF; st[0]=0; st[2]=1 // skip the leading 0 byte
52 var i: i64=0; while i < 4 { st[0] = ((st[0] << 8) | (in_[st[2]] & 0xFF)) & 0xFFFFFFFF; st[2]=st[2]+1; i=i+1 }
53 return 0
54}
55func rc_dec_bit(st: *i64, in_: *u8, p: i64) -> i64 {
56 let bound: i64 = (st[1] >> 12) * p
57 var bit: i64 = 0
58 if st[0] < bound { st[1] = bound } else { st[0] = st[0] - bound; st[1] = st[1] - bound; bit = 1 }
59 while st[1] < 0x1000000 { st[1]=(st[1]<<8)&0xFFFFFFFF; st[0]=((st[0]<<8)|(in_[st[2]]&0xFF))&0xFFFFFFFF; st[2]=st[2]+1 }
60 return bit
61}
62
63// ---- adaptive context probability (12-bit, shift-5 adaptation). Same update on enc+dec => stay in sync. ----
64func rc_p_update(p: i64, bit: i64) -> i64 { if bit == 0 { return p + ((RC_MAGIC_4096 - p) >> 5) } return p - (p >> 5) }
65
66// Q8 entropy cost of ONE bin under this coder's convention (p = 12-bit probability of ZERO): -log2(q/4096)
67// via an integer linear-mantissa log2 (max err ~0.09 bit). READ-ONLY (no state touched) -- powers x264-style
68// RD estimation in the coder's OWN bits instead of CAVLC tables (P3 rung, 2026-07-12).
69func rc_bits_q8(p: i64, bit: i64) -> i64 {
70 var q: i64 = p
71 if bit != 0 { q = RC_MAGIC_4096 - p }
72 if q < 1 { q = 1 }
73 if q > RC_MAGIC_4095 { q = RC_MAGIC_4095 }
74 var lz: i64 = 0
75 var t: i64 = q
76 while t > 1 { t = t >> 1; lz = lz + 1 }
77 let frac: i64 = ((q << 8) >> lz) - 256
78 return (12 << 8) - ((lz << 8) + frac)
79}
80
81// encode a bit through context array probs[ctx] and adapt it. Mirror on decode.
82func rc_enc_ctx(st: *i64, out: *u8, probs: *i64, ctx: i64, bit: i64) -> i64 {
83 rc_enc_bit(st, out, probs[ctx], bit); probs[ctx] = rc_p_update(probs[ctx], bit); return 0 }
84func rc_dec_ctx(st: *i64, in_: *u8, probs: *i64, ctx: i64) -> i64 {
85 let bit: i64 = rc_dec_bit(st, in_, probs[ctx]); probs[ctx] = rc_p_update(probs[ctx], bit); return bit }
86
87// ---- 4x4 quantized-coefficient block coder (the 36%-vs-CAVLC unit, proven by nx_rangecoder_gain_gate).
88// Same run-length syntax as ve_encode_at but each binary decision is adaptive. Contexts (probs must be sized
89// >= RC_NCTX and pre-seeded to 2048): 0=continue/EOB flag, 1..4=run bits (MSB first), 5..9=level-length bits,
90// 10=level magnitude bits. Enc + dec MUST share the exact context indices to stay in sync. ----
91func rc_block_encode(coeffs: *i64, st: *i64, out: *u8, probs: *i64) -> i64 {
92 var run: i64=0; var k: i64=0
93 while k < 16 {
94 let val: i64 = coeffs[ve_zz_idx(k)]
95 if val == 0 { run = run + 1 } else {
96 rc_enc_ctx(st, out, probs, 0, 1)
97 var b: i64=3; while b >= 0 { rc_enc_ctx(st, out, probs, 1 + (3 - b), (run >> b) & 1); b = b - 1 }
98 let z: i64 = ve_zze(val); let nb: i64 = ve_blen(z)
99 b = 4; while b >= 0 { rc_enc_ctx(st, out, probs, 5 + (4 - b), (nb >> b) & 1); b = b - 1 }
100 var m: i64 = nb - 1; while m >= 0 { rc_enc_ctx(st, out, probs, 10, (z >> m) & 1); m = m - 1 }
101 run = 0
102 }
103 k = k + 1
104 }
105 rc_enc_ctx(st, out, probs, 0, 0); return 0 }
106func rc_block_decode(coeffs: *i64, st: *i64, in_: *u8, probs: *i64) -> i64 {
107 var i: i64=0; while i < 16 { coeffs[i]=0; i=i+1 }
108 var k: i64=0
109 var flag: i64 = rc_dec_ctx(st, in_, probs, 0)
110 while flag == 1 {
111 var run: i64=0; var b: i64=0; while b < 4 { run = (run << 1) | rc_dec_ctx(st, in_, probs, 1 + b); b = b + 1 }
112 var nb: i64=0; b = 0; while b < 5 { nb = (nb << 1) | rc_dec_ctx(st, in_, probs, 5 + b); b = b + 1 }
113 var z: i64=0; if nb > 0 { var m: i64=0; while m < nb { z = (z << 1) | rc_dec_ctx(st, in_, probs, 10); m = m + 1 } }
114 k = k + run
115 if k < 16 { coeffs[ve_zz_idx(k)] = ve_zzd(z); k = k + 1 }
116 flag = rc_dec_ctx(st, in_, probs, 0)
117 }
118 return 0 }
119
120// ---- 8x8 (64-coeff) block coder for the variable-transform-size path (task #46 rung 2). Same adaptive
121// run-length syntax as rc_block_encode but a 6-bit run (zeros-runs reach 63) and its OWN context block
122// 11..23 so 8x8 statistics never pollute the 4x4 contexts in a mixed frame (probs sized >= RC_NCTX8, all
123// pre-seeded 2048). zz8 = caller-provided 8x8 zig-zag table (vc_t8_init generates it). Contexts:
124// 11=continue/EOB flag, 12..17=run bits (MSB first), 18..22=level-length bits, 23=level magnitude bits. ----
125func rc_block64_encode(coeffs: *i64, st: *i64, out: *u8, probs: *i64, zz8: *i64) -> i64 {
126 var run: i64=0; var k: i64=0
127 while k < 64 {
128 let val: i64 = coeffs[zz8[k]]
129 if val == 0 { run = run + 1 } else {
130 rc_enc_ctx(st, out, probs, 11, 1)
131 var b: i64=5; while b >= 0 { rc_enc_ctx(st, out, probs, 12 + (5 - b), (run >> b) & 1); b = b - 1 }
132 let z: i64 = ve_zze(val); let nb: i64 = ve_blen(z)
133 b = 4; while b >= 0 { rc_enc_ctx(st, out, probs, 18 + (4 - b), (nb >> b) & 1); b = b - 1 }
134 var m: i64 = nb - 1; while m >= 0 { rc_enc_ctx(st, out, probs, 23, (z >> m) & 1); m = m - 1 }
135 run = 0
136 }
137 k = k + 1
138 }
139 rc_enc_ctx(st, out, probs, 11, 0); return 0 }
140func rc_block64_decode(coeffs: *i64, st: *i64, in_: *u8, probs: *i64, zz8: *i64) -> i64 {
141 var i: i64=0; while i < 64 { coeffs[i]=0; i=i+1 }
142 var k: i64=0
143 var flag: i64 = rc_dec_ctx(st, in_, probs, 11)
144 while flag == 1 {
145 var run: i64=0; var b: i64=0; while b < 6 { run = (run << 1) | rc_dec_ctx(st, in_, probs, 12 + b); b = b + 1 }
146 var nb: i64=0; b = 0; while b < 5 { nb = (nb << 1) | rc_dec_ctx(st, in_, probs, 18 + b); b = b + 1 }
147 var z: i64=0; if nb > 0 { var m: i64=0; while m < nb { z = (z << 1) | rc_dec_ctx(st, in_, probs, 23); m = m + 1 } }
148 k = k + run
149 if k < 64 { coeffs[zz8[k]] = ve_zzd(z); k = k + 1 }
150 flag = rc_dec_ctx(st, in_, probs, 11)
151 }
152 return 0 }
153
154// ==== R2a rung-1 (2026-07-10): NEIGHBOR-CONTEXT SIGNIFICANCE-MAP 8x8 coefficient coder ====
155// nx_vcodec_entropy_gap MEASURED the prize on 2.9M real coefficients: significance coded with
156// (row-band x causal-neighbor-count) context costs 36.8% FEWER bits than position-only -- the CABAC-class
157// signal the run-length syntax above structurally throws away. This coder replaces run-lengths entirely:
158// PASS 1 (raster order): per-position significance bit, ctx = 32-bucket (row 0..7 x nsig(L,U,UL) 0..3)
159// PASS 2 (raster order): for each significant position, level = 5-bit length (
160
161// ==== FFV1-INSPIRED ADVANCED ADAPTATION (task: integer entropy-coding improvement; ADDITIVE, measure-first) ====
162// RFC 9043's range coder gets its edge from a per-context state whose adaptation rate is NON-UNIFORM: it moves
163// fast while a context is uncertain and only in tiny steps once the context is confidently skewed. That both
164// LOWERS steady-state variance (the dominant redundancy of an adaptive coder -- ~rate/(4 ln2) bits per bin) and
165// lets the probability reach MORE EXTREME values than our fixed multiplicative shift, which STALLS at ~[31,4065]
166// (a p=0.999 flag is forced to p=0.992). rc_p_update_adv reproduces both properties with pure integers, fully
167// parameterised so a gate can A/B it against the shipped shift-5 update on real residuals -- NOT wired into any
168// shipped path here (the shipped rc_p_update / rc_block* / rc_sig* are untouched). cfg layout:
169// cfg[0]=s_start (shift when a context is fresh -- small => fast early convergence, reaches extremes)
170// cfg[1]=s_floor (shift once warmed up; >= s_start -- large => low steady-state variance)
171// cfg[2]=minstep (guaranteed +/- step so p can CRAWL to the clamp instead of stalling short of it)
172// cfg[3]=lo cfg[4]=hi (probability clamp; tighter-than-natural => model the true extremes)
173// cfg=[5,5,0,1,4095] is BIT-IDENTICAL to the shipped rc_p_update (asserted in nx_vcodec_ffv1_entropy_gate).
174func rc_ilog2(n: i64) -> i64 { var r: i64=0; var t: i64=n; while t > 1 { t = t >> 1; r = r + 1 } return r }
175func rc_p_update_adv(p: i64, bit: i64, n: i64, cfg: *i64) -> i64 {
176 var s: i64 = cfg[0] + rc_ilog2(n + 1)
177 if s > cfg[1] { s = cfg[1] }
178 if bit == 0 {
179 var d: i64 = (RC_MAGIC_4096 - p) >> s
180 if d < cfg[2] { d = cfg[2] }
181 var q: i64 = p + d
182 if q > cfg[4] { q = cfg[4] }
183 return q
184 }
185 var e: i64 = p >> s
186 if e < cfg[2] { e = cfg[2] }
187 var r2: i64 = p - e
188 if r2 < cfg[3] { r2 = cfg[3] }
189 return r2
190}
191// enc/dec one bit through probs[ctx], the per-context symbol count cnt[ctx] driving the adaptive rate. Mirror
192// on decode. cnt must be sized like probs and zeroed at the start of each stream (same as probs<-seed).
193func rc_enc_ctx_adv(st: *i64, out: *u8, probs: *i64, cnt: *i64, ctx: i64, bit: i64, cfg: *i64) -> i64 {
194 rc_enc_bit(st, out, probs[ctx], bit)
195 probs[ctx] = rc_p_update_adv(probs[ctx], bit, cnt[ctx], cfg)
196 if cnt[ctx] < 65535 { cnt[ctx] = cnt[ctx] + 1 }
197 return 0 }
198func rc_dec_ctx_adv(st: *i64, in_: *u8, probs: *i64, cnt: *i64, ctx: i64, cfg: *i64) -> i64 {
199 let bit: i64 = rc_dec_bit(st, in_, probs[ctx])
200 probs[ctx] = rc_p_update_adv(probs[ctx], bit, cnt[ctx], cfg)
201 if cnt[ctx] < 65535 { cnt[ctx] = cnt[ctx] + 1 }
202 return bit }
203// 8x8 run-length block coder (the LIVE entropy path) driven by the advanced adaptation. IDENTICAL syntax and
204// context indices to rc_block64_encode; only the probability update differs. cnt sized >= RC_NCTX8, zeroed.
205func rc_block64_encode_adv(coeffs: *i64, st: *i64, out: *u8, probs: *i64, cnt: *i64, zz8: *i64, cfg: *i64) -> i64 {
206 var run: i64=0; var k: i64=0
207 while k < 64 {
208 let val: i64 = coeffs[zz8[k]]
209 if val == 0 { run = run + 1 } else {
210 rc_enc_ctx_adv(st, out, probs, cnt, 11, 1, cfg)
211 var b: i64=5; while b >= 0 { rc_enc_ctx_adv(st, out, probs, cnt, 12 + (5 - b), (run >> b) & 1, cfg); b = b - 1 }
212 let z: i64 = ve_zze(val); let nb: i64 = ve_blen(z)
213 b = 4; while b >= 0 { rc_enc_ctx_adv(st, out, probs, cnt, 18 + (4 - b), (nb >> b) & 1, cfg); b = b - 1 }
214 var m: i64 = nb - 1; while m >= 0 { rc_enc_ctx_adv(st, out, probs, cnt, 23, (z >> m) & 1, cfg); m = m - 1 }
215 run = 0
216 }
217 k = k + 1
218 }
219 rc_enc_ctx_adv(st, out, probs, cnt, 11, 0, cfg); return 0 }
220func rc_block64_decode_adv(coeffs: *i64, st: *i64, in_: *u8, probs: *i64, cnt: *i64, zz8: *i64, cfg: *i64) -> i64 {
221 var i: i64=0; while i < 64 { coeffs[i]=0; i=i+1 }
222 var k: i64=0
223 var flag: i64 = rc_dec_ctx_adv(st, in_, probs, cnt, 11, cfg)
224 while flag == 1 {
225 var run: i64=0; var b: i64=0; while b < 6 { run = (run << 1) | rc_dec_ctx_adv(st, in_, probs, cnt, 12 + b, cfg); b = b + 1 }
226 var nb: i64=0; b = 0; while b < 5 { nb = (nb << 1) | rc_dec_ctx_adv(st, in_, probs, cnt, 18 + b, cfg); b = b + 1 }
227 var z: i64=0; if nb > 0 { var m: i64=0; while m < nb { z = (z << 1) | rc_dec_ctx_adv(st, in_, probs, cnt, 23, cfg); m = m + 1 } }
228 k = k + run
229 if k < 64 { coeffs[zz8[k]] = ve_zzd(z); k = k + 1 }
230 flag = rc_dec_ctx_adv(st, in_, probs, cnt, 11, cfg)
231 }
232 return 0 }