nx_rangecoder.nx source
↩ module page · 158 lines · 9364 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
10const RC_MAGIC_4096: i64 = 4096
11const RC_MAGIC_4095: i64 = 4095
12const RC_NCTX: i64 = 11 // contexts used by rc_block_encode/decode (probs array must be >= this, seeded 2048)
13const RC_NCTX8: i64 = 24 // total contexts when 8x8 blocks are in the stream (11 for 4x4 + 13 for 8x8, below)
14// ⚠R1d MEASURED + REVERTED (2026-07-09): contexting the continue/EOB flag by coeff-count (buckets 24..31,
15// helpers rc_fbk4/rc_fbk8) is BIT-EXACT and saves ~0.3% bytes (rd_bench, PSNR unchanged) -- but the 32-ctx
16// probs budget caps it there, and a wire change for 0.3% isn't worth a vcv bump + dual entropy path. STAGED
17// for the batched neural-entropy generation (R2a), not deployed standalone. See vcodec-sota-roadmap memory.
18
19// ---- ENCODER: state = i64[5] = [low, range, cache, cacheSize, outpos] ----
20func rc_enc_init(st: *i64) -> i64 { st[0]=0; st[1]=0xFFFFFFFF; st[2]=0; st[3]=1; st[4]=0; return 0 }
21
22func rc_shift_low(st: *i64, out: *u8) -> i64 {
23 let low: i64 = st[0]
24 let lo32: i64 = low & 0xFFFFFFFF
25 let carry: i64 = (low >> 32) & 0xFF
26 if (lo32 < 0xFF000000) | (carry != 0) {
27 let cs: i64 = st[3]
28 out[st[4]] = ((st[2] + carry) & 0xFF) as u8; st[4] = st[4] + 1 // cache + carry
29 var j: i64 = 1
30 while j < cs { out[st[4]] = ((0xFF + carry) & 0xFF) as u8; st[4] = st[4] + 1; j = j + 1 }
31 st[2] = (lo32 >> 24) & 0xFF // new cache = top byte
32 st[3] = 0
33 }
34 st[3] = st[3] + 1
35 st[0] = (lo32 << 8) & 0xFFFFFFFF
36 return 0
37}
38
39// encode one bit under probability p = P(bit==0) in 1..4095 (12-bit). Renormalize when range < 2^24.
40func rc_enc_bit(st: *i64, out: *u8, p: i64, bit: i64) -> i64 {
41 let bound: i64 = (st[1] >> 12) * p
42 if bit == 0 { st[1] = bound } else { st[0] = st[0] + bound; st[1] = st[1] - bound }
43 while st[1] < 0x1000000 { st[1] = (st[1] << 8) & 0xFFFFFFFF; rc_shift_low(st, out) }
44 return 0
45}
46func 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] }
47
48// ---- DECODER: state = i64[3] = [code, range, inpos] ----
49func rc_dec_init(st: *i64, in_: *u8) -> i64 {
50 st[1]=0xFFFFFFFF; st[0]=0; st[2]=1 // skip the leading 0 byte
51 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 }
52 return 0
53}
54func rc_dec_bit(st: *i64, in_: *u8, p: i64) -> i64 {
55 let bound: i64 = (st[1] >> 12) * p
56 var bit: i64 = 0
57 if st[0] < bound { st[1] = bound } else { st[0] = st[0] - bound; st[1] = st[1] - bound; bit = 1 }
58 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 }
59 return bit
60}
61
62// ---- adaptive context probability (12-bit, shift-5 adaptation). Same update on enc+dec => stay in sync. ----
63func rc_p_update(p: i64, bit: i64) -> i64 { if bit == 0 { return p + ((RC_MAGIC_4096 - p) >> 5) } return p - (p >> 5) }
64
65// Q8 entropy cost of ONE bin under this coder's convention (p = 12-bit probability of ZERO): -log2(q/4096)
66// via an integer linear-mantissa log2 (max err ~0.09 bit). READ-ONLY (no state touched) -- powers x264-style
67// RD estimation in the coder's OWN bits instead of CAVLC tables (P3 rung, 2026-07-12).
68func rc_bits_q8(p: i64, bit: i64) -> i64 {
69 var q: i64 = p
70 if bit != 0 { q = RC_MAGIC_4096 - p }
71 if q < 1 { q = 1 }
72 if q > RC_MAGIC_4095 { q = RC_MAGIC_4095 }
73 var lz: i64 = 0
74 var t: i64 = q
75 while t > 1 { t = t >> 1; lz = lz + 1 }
76 let frac: i64 = ((q << 8) >> lz) - 256
77 return (12 << 8) - ((lz << 8) + frac)
78}
79
80// encode a bit through context array probs[ctx] and adapt it. Mirror on decode.
81func rc_enc_ctx(st: *i64, out: *u8, probs: *i64, ctx: i64, bit: i64) -> i64 {
82 rc_enc_bit(st, out, probs[ctx], bit); probs[ctx] = rc_p_update(probs[ctx], bit); return 0 }
83func rc_dec_ctx(st: *i64, in_: *u8, probs: *i64, ctx: i64) -> i64 {
84 let bit: i64 = rc_dec_bit(st, in_, probs[ctx]); probs[ctx] = rc_p_update(probs[ctx], bit); return bit }
85
86// ---- 4x4 quantized-coefficient block coder (the 36%-vs-CAVLC unit, proven by nx_rangecoder_gain_gate).
87// Same run-length syntax as ve_encode_at but each binary decision is adaptive. Contexts (probs must be sized
88// >= RC_NCTX and pre-seeded to 2048): 0=continue/EOB flag, 1..4=run bits (MSB first), 5..9=level-length bits,
89// 10=level magnitude bits. Enc + dec MUST share the exact context indices to stay in sync. ----
90func rc_block_encode(coeffs: *i64, st: *i64, out: *u8, probs: *i64) -> i64 {
91 var run: i64=0; var k: i64=0
92 while k < 16 {
93 let val: i64 = coeffs[ve_zz_idx(k)]
94 if val == 0 { run = run + 1 } else {
95 rc_enc_ctx(st, out, probs, 0, 1)
96 var b: i64=3; while b >= 0 { rc_enc_ctx(st, out, probs, 1 + (3 - b), (run >> b) & 1); b = b - 1 }
97 let z: i64 = ve_zze(val); let nb: i64 = ve_blen(z)
98 b = 4; while b >= 0 { rc_enc_ctx(st, out, probs, 5 + (4 - b), (nb >> b) & 1); b = b - 1 }
99 var m: i64 = nb - 1; while m >= 0 { rc_enc_ctx(st, out, probs, 10, (z >> m) & 1); m = m - 1 }
100 run = 0
101 }
102 k = k + 1
103 }
104 rc_enc_ctx(st, out, probs, 0, 0); return 0 }
105func rc_block_decode(coeffs: *i64, st: *i64, in_: *u8, probs: *i64) -> i64 {
106 var i: i64=0; while i < 16 { coeffs[i]=0; i=i+1 }
107 var k: i64=0
108 var flag: i64 = rc_dec_ctx(st, in_, probs, 0)
109 while flag == 1 {
110 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 }
111 var nb: i64=0; b = 0; while b < 5 { nb = (nb << 1) | rc_dec_ctx(st, in_, probs, 5 + b); b = b + 1 }
112 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 } }
113 k = k + run
114 if k < 16 { coeffs[ve_zz_idx(k)] = ve_zzd(z); k = k + 1 }
115 flag = rc_dec_ctx(st, in_, probs, 0)
116 }
117 return 0 }
118
119// ---- 8x8 (64-coeff) block coder for the variable-transform-size path (task #46 rung 2). Same adaptive
120// run-length syntax as rc_block_encode but a 6-bit run (zeros-runs reach 63) and its OWN context block
121// 11..23 so 8x8 statistics never pollute the 4x4 contexts in a mixed frame (probs sized >= RC_NCTX8, all
122// pre-seeded 2048). zz8 = caller-provided 8x8 zig-zag table (vc_t8_init generates it). Contexts:
123// 11=continue/EOB flag, 12..17=run bits (MSB first), 18..22=level-length bits, 23=level magnitude bits. ----
124func rc_block64_encode(coeffs: *i64, st: *i64, out: *u8, probs: *i64, zz8: *i64) -> i64 {
125 var run: i64=0; var k: i64=0
126 while k < 64 {
127 let val: i64 = coeffs[zz8[k]]
128 if val == 0 { run = run + 1 } else {
129 rc_enc_ctx(st, out, probs, 11, 1)
130 var b: i64=5; while b >= 0 { rc_enc_ctx(st, out, probs, 12 + (5 - b), (run >> b) & 1); b = b - 1 }
131 let z: i64 = ve_zze(val); let nb: i64 = ve_blen(z)
132 b = 4; while b >= 0 { rc_enc_ctx(st, out, probs, 18 + (4 - b), (nb >> b) & 1); b = b - 1 }
133 var m: i64 = nb - 1; while m >= 0 { rc_enc_ctx(st, out, probs, 23, (z >> m) & 1); m = m - 1 }
134 run = 0
135 }
136 k = k + 1
137 }
138 rc_enc_ctx(st, out, probs, 11, 0); return 0 }
139func rc_block64_decode(coeffs: *i64, st: *i64, in_: *u8, probs: *i64, zz8: *i64) -> i64 {
140 var i: i64=0; while i < 64 { coeffs[i]=0; i=i+1 }
141 var k: i64=0
142 var flag: i64 = rc_dec_ctx(st, in_, probs, 11)
143 while flag == 1 {
144 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 }
145 var nb: i64=0; b = 0; while b < 5 { nb = (nb << 1) | rc_dec_ctx(st, in_, probs, 18 + b); b = b + 1 }
146 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 } }
147 k = k + run
148 if k < 64 { coeffs[zz8[k]] = ve_zzd(z); k = k + 1 }
149 flag = rc_dec_ctx(st, in_, probs, 11)
150 }
151 return 0 }
152
153// ==== R2a rung-1 (2026-07-10): NEIGHBOR-CONTEXT SIGNIFICANCE-MAP 8x8 coefficient coder ====
154// nx_vcodec_entropy_gap MEASURED the prize on 2.9M real coefficients: significance coded with
155// (row-band x causal-neighbor-count) context costs 36.8% FEWER bits than position-only -- the CABAC-class
156// signal the run-length syntax above structurally throws away. This coder replaces run-lengths entirely:
157// PASS 1 (raster order): per-position significance bit, ctx = 32-bucket (row 0..7 x nsig(L,U,UL) 0..3)
158// PASS 2 (raster order): for each significant position, level = 5-bit length (