`nx_rans.nx` source

↩ module page · 132 lines · 5345 B
1// nx_rans.nx -- SOVEREIGN, PATENT-FREE static-frequency rANS entropy coder. The keystone of the
2// patent-free video-codec arc (project-sovereign-patent-free-codec-2026-06-20). rANS = the range
3// variant of Asymmetric Numeral Systems (J. Duda, dedicated to the PUBLIC DOMAIN; the USPTO rejected
4// Google's attempt to patent ANS use, 2018). This is PLAIN static-frequency rANS -- explicitly NOT the
5// Petagene Markov+escape-code variant (US9847791B2) and NOT the Microsoft two-phase / switchable-width
6// / fragment-flush hardware variant (US11234023B2) -- so it reads on no active claim (deep-research
7// verified 2026-06-20). Byte-oriented, 32-bit state in the ryg style (RANS_L = 1<<23, 8-bit
8// renormalization), SCALE_BITS supplied by the caller (12 = a 4096-entry table).
9// LOSSLESS: rans_decode(rans_encode(x)) == x, bit-exact -- the COMPLETE correctness criterion for an
10// entropy stage whose encoder AND decoder we both own (no external interop, so round-trip self-proof
11// is sufficient and total). license_tier: ORIGINAL
12import "nx_syscalls.nx"
13
14// counts[256] <- byte histogram of data[0..n)
15func rans_count(data: *u8, n: i64, counts: *i64) -> i64 {
16    var s: i64 = 0
17    while s < 256 { counts[s] = 0; s = s + 1 }
18    var i: i64 = 0
19    while i < n { let b: i64 = data[i] as i64; counts[b] = counts[b] + 1; i = i + 1 }
20    return 0
21}
22
23// freqs[256] <- counts normalized so sum == (1<<scale_bits); every nonzero count keeps freq >= 1.
24// returns 0 on success, <0 on error (empty input / unfixable).
25func rans_normalize(counts: *i64, freqs: *i64, scale_bits: i64) -> i64 {
26    let M: i64 = 1 << scale_bits
27    var total: i64 = 0
28    var s: i64 = 0
29    while s < 256 { total = total + counts[s]; freqs[s] = 0; s = s + 1 }
30    if total == 0 { return 0 - 1 }
31    var sum: i64 = 0
32    var maxf: i64 = 0
33    var maxs: i64 = 0
34    s = 0
35    while s < 256 {
36        if counts[s] > 0 {
37            var f: i64 = (counts[s] * M) / total
38            if f < 1 { f = 1 }
39            freqs[s] = f
40            sum = sum + f
41            if f > maxf { maxf = f; maxs = s }
42        }
43        s = s + 1
44    }
45    // correct rounding drift by adjusting the most-frequent symbol so the total is exactly M
46    freqs[maxs] = freqs[maxs] + (M - sum)
47    if freqs[maxs] < 1 { return 0 - 2 }
48    return 0
49}
50
51// cum[0..256] = prefix sums of freqs; cum[256] == total (== M). returns total.
52func rans_cum(freqs: *i64, cum: *i64) -> i64 {
53    var c: i64 = 0
54    var s: i64 = 0
55    while s < 256 { cum[s] = c; c = c + freqs[s]; s = s + 1 }
56    cum[256] = c
57    return c
58}
59
60// slot2sym[0..M) = inverse map: each cumulative slot -> its symbol.
61func rans_build_slot2sym(freqs: *i64, cum: *i64, slot2sym: *i64) -> i64 {
62    var s: i64 = 0
63    while s < 256 {
64        if freqs[s] > 0 {
65            var k: i64 = cum[s]
66            let e: i64 = cum[s] + freqs[s]
67            while k < e { slot2sym[k] = s; k = k + 1 }
68        }
69        s = s + 1
70    }
71    return 0
72}
73
74// encode data[0..n) into out (forward-readable); returns encoded length in bytes (or <0 on overflow).
75// rANS encodes in REVERSE symbol order, emitting renorm bytes backward, then flushes the 32-bit state
76// so that the forward byte order is [state b0,b1,b2,b3][renorm bytes] -- exactly what rans_decode reads.
77func rans_encode(data: *u8, n: i64, freqs: *i64, cum: *i64, scale_bits: i64, out: *u8, outcap: i64) -> i64 {
78    let RANS_L: i64 = 1 << 23
79    let tmp: *u8 = sys_mmap(outcap + 16)
80    var ptr: i64 = outcap
81    var x: i64 = RANS_L
82    var i: i64 = n - 1
83    while i >= 0 {
84        let sym: i64 = data[i] as i64
85        let f: i64 = freqs[sym]
86        let start: i64 = cum[sym]
87        let x_max: i64 = ((RANS_L >> scale_bits) << 8) * f
88        while x >= x_max {
89            ptr = ptr - 1
90            if ptr < 0 { return 0 - 1 }
91            tmp[ptr] = (x & 0xff) as u8
92            x = x >> 8
93        }
94        x = ((x / f) << scale_bits) + (x % f) + start
95        i = i - 1
96    }
97    // flush 32-bit state, lowest byte last so forward order is b0,b1,b2,b3
98    ptr = ptr - 1; tmp[ptr] = ((x >> 24) & 0xff) as u8
99    ptr = ptr - 1; tmp[ptr] = ((x >> 16) & 0xff) as u8
100    ptr = ptr - 1; tmp[ptr] = ((x >> 8) & 0xff) as u8
101    ptr = ptr - 1; tmp[ptr] = (x & 0xff) as u8
102    let len: i64 = outcap - ptr
103    var j: i64 = 0
104    while j < len { out[j] = tmp[ptr + j]; j = j + 1 }
105    return len
106}
107
108// decode n symbols from enc[0..enclen) into out[0..n); returns bytes consumed (== enclen for a valid
109// stream). Reads past enclen are guarded (treated as 0) so a corrupted/short stream can't run OOB.
110func rans_decode(enc: *u8, enclen: i64, n: i64, freqs: *i64, cum: *i64, scale_bits: i64, slot2sym: *i64, out: *u8) -> i64 {
111    let RANS_L: i64 = 1 << 23
112    let mask: i64 = (1 << scale_bits) - 1
113    var x: i64 = (enc[0] as i64) | ((enc[1] as i64) << 8) | ((enc[2] as i64) << 16) | ((enc[3] as i64) << 24)
114    var pos: i64 = 4
115    var i: i64 = 0
116    while i < n {
117        let slot: i64 = x & mask
118        let sym: i64 = slot2sym[slot]
119        out[i] = sym as u8
120        let f: i64 = freqs[sym]
121        let start: i64 = cum[sym]
122        x = (f * (x >> scale_bits)) + slot - start
123        while x < RANS_L {
124            var nb: i64 = 0
125            if pos < enclen { nb = enc[pos] as i64 }
126            x = (x << 8) | nb
127            pos = pos + 1
128        }
129        i = i + 1
130    }
131    return pos
132}
nx_rans.nx source

`nx_rans.nx` source
