nx_range_coef.nx source
↩ module page · 164 lines · 5238 B
1// nx_range_coef.nx -- adaptive order-0 byte model wrapper around
2// nx_range_coder, sized for the post-RLE coefficient stream.
3//
4// The post-zigzag-RLE byte stream is highly skewed: most run-bytes
5// are small (the longest runs are bounded by 63), and most level-
6// bytes are small (low magnitude after quantisation). An adaptive
7// frequency table tracks the distribution within the message and
8// asks the arithmetic coder for sub-byte symbol widths -- the
9// compounding compression step on top of zigzag + RLE.
10//
11// Adaptation policy: each encoded byte bumps its frequency by 8;
12// after total > 16384 we halve all frequencies (decay to prevent
13// the model from over-committing to the early bytes of the stream).
14//
15// genealogy_id: rissanen_1976_arithmetic_coding +
16// witten_neal_cleary_1987_arithmetic_coding_for_data_compression +
17// nx_range_coder_q10
18// lineage_id: nishi_range_coef_q10
19
20// nx_safety_envelope:
21// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
22// sil_target: SIL1
23// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
24// verdict: NOT_YET_EVALUATED
25
26import "nx_syscalls_x86_64.nx"
27import "nx_range_coder.nx"
28
29// Sealed verdict.
30const NX_RCF_VERDICT_UNKNOWN: i64 = 0
31const NX_RCF_VERDICT_OK: i64 = 1
32const NX_RCF_VERDICT_BUF_FULL: i64 = 2
33const NX_RCF_VERDICT_BAD_INPUT: i64 = 3
34const NX_RCF_VERDICT_TRUNCATED: i64 = 4
35const NX_RCF_VERDICT_N: i64 = 5
36
37const NX_RCF_DECAY_THRESHOLD: i64 = 16384
38const NX_RCF_INCREMENT: i64 = 8
39
40struct RangeCoefModel {
41 freq: *i64, // 256 i64 entries
42 ft: i64
43}
44
45func nx_rcf_model_init(m: *RangeCoefModel, freq_buf: *i64) -> i64 {
46 var i: i64 = 0
47 while i < 256 { freq_buf[i] = 1; i = i + 1 }
48 m.freq = freq_buf
49 m.ft = 256
50 return NX_RCF_VERDICT_OK
51}
52
53// Adapt: bump symbol `b`'s frequency and decay if total grows large.
54func _rcf_adapt(m: *RangeCoefModel, b: i64) -> i64 {
55 m.freq[b] = m.freq[b] + NX_RCF_INCREMENT
56 m.ft = m.ft + NX_RCF_INCREMENT
57 if m.ft > NX_RCF_DECAY_THRESHOLD {
58 var j: i64 = 0
59 while j < 256 {
60 let h: i64 = (m.freq[j] + 1) >> 1
61 m.freq[j] = h
62 j = j + 1
63 }
64 // Recompute ft.
65 var ft2: i64 = 0
66 var k: i64 = 0
67 while k < 256 { ft2 = ft2 + m.freq[k]; k = k + 1 }
68 m.ft = ft2
69 }
70 return 0
71}
72
73// Encode `in_buf[0..in_len)` adaptively into `out_buf`. Prefixes
74// the output with a 2-byte little-endian length (in_len), so the
75// decoder knows when to stop. Returns total bytes written via
76// *out_total.
77func nx_rcf_encode(
78 in_buf: *u8, in_len: i64,
79 out_buf: *u8, out_cap: i64,
80 out_total: *i64
81) -> i64 {
82 if in_len < 0 { return NX_RCF_VERDICT_BAD_INPUT }
83 if in_len > 65535 { return NX_RCF_VERDICT_BAD_INPUT }
84 if out_cap < 8 { return NX_RCF_VERDICT_BUF_FULL }
85
86 // 2-byte LE length prefix.
87 out_buf[0] = in_len & 0xff
88 out_buf[1] = (in_len >> 8) & 0xff
89
90 let freq_buf: *i64 = sys_mmap(256 * 8) as *i64
91 let model: *RangeCoefModel = sys_mmap(64) as *RangeCoefModel
92 nx_rcf_model_init(model, freq_buf)
93
94 let enc: *RcEnc = sys_mmap(128) as *RcEnc
95 nx_rc_enc_init(enc, (out_buf as i64 + 2) as *u8, out_cap - 2)
96
97 var i: i64 = 0
98 while i < in_len {
99 let b: i64 = in_buf[i] & 0xff
100 // Cumulative [fl, fh) for symbol b.
101 var fl: i64 = 0
102 var j: i64 = 0
103 while j < b {
104 fl = fl + model.freq[j]
105 j = j + 1
106 }
107 let fh: i64 = fl + model.freq[b]
108 nx_rc_enc_symbol(enc, fl, fh, model.ft)
109 _rcf_adapt(model, b)
110 i = i + 1
111 }
112
113 let body_bytes: i64 = nx_rc_enc_done(enc)
114 if enc.err != NX_RC_VERDICT_OK { return NX_RCF_VERDICT_BUF_FULL }
115 *out_total = 2 + body_bytes
116 return NX_RCF_VERDICT_OK
117}
118
119func nx_rcf_decode(
120 in_buf: *u8, in_len: i64,
121 out_buf: *u8, out_cap: i64,
122 out_total: *i64
123) -> i64 {
124 if in_len < 2 { return NX_RCF_VERDICT_TRUNCATED }
125 let expected: i64 = in_buf[0] | (in_buf[1] << 8)
126 if expected > out_cap { return NX_RCF_VERDICT_BUF_FULL }
127
128 let freq_buf: *i64 = sys_mmap(256 * 8) as *i64
129 let model: *RangeCoefModel = sys_mmap(64) as *RangeCoefModel
130 nx_rcf_model_init(model, freq_buf)
131
132 let dec: *RcDec = sys_mmap(128) as *RcDec
133 nx_rc_dec_init(dec, (in_buf as i64 + 2) as *u8, in_len - 2)
134
135 var i: i64 = 0
136 while i < expected {
137 let target: i64 = nx_rc_dec_get_target(dec, model.ft)
138 var fl: i64 = 0
139 var byte: i64 = 0
140 var found: i64 = 0
141 while found == 0 {
142 if byte >= 256 { return NX_RCF_VERDICT_TRUNCATED }
143 let next: i64 = fl + model.freq[byte]
144 if target < next {
145 nx_rc_dec_update(dec, fl, next, model.ft)
146 out_buf[i] = byte & 0xff
147 _rcf_adapt(model, byte)
148 found = 1
149 } else {
150 fl = next
151 byte = byte + 1
152 }
153 }
154 i = i + 1
155 }
156 *out_total = expected
157 return NX_RCF_VERDICT_OK
158}
159
160func nx_rcf_verdict_is_valid(v: i64) -> i64 {
161 if v < 0 { return 0 }
162 if v >= NX_RCF_VERDICT_N { return 0 }
163 return 1
164}