code wiki / _hdl_build / nx_room_fec.nx
nx_room_fec.nx source
↩ module page · 258 lines · 10664 B
1// nx_room_fec.nx -- X-ROOM (overseas-grade): sovereign DETERMINISTIC Reed-Solomon
2// systematic ERASURE CODE over GF(256) -- Forward Error Correction for high-RTT,
3// lossy intercontinental video calls.
4//
5// WHY (the overseas-call performance axis): at ~250ms intercontinental RTT a
6// retransmit (ARQ) costs a full round-trip = an audible/visible STALL. FEC recovers
7// lost packets from PARITY already in flight -> ZERO added latency, NO retransmit.
8// k data shards + m parity shards (n=k+m). ANY m losses out of n reconstruct exactly.
9//
10// EXCEED axis (honest) vs Zoom/Teams/WebRTC FlexFEC: a PROVABLE MDS guarantee --
11// deterministic, integer-exact, audit-replayable recovery of EVERY <=m erasure
12// pattern (the gate proves all C(n,m) of them), sovereign (own GF(256), no library).
13// HONEST SCOPE: ERASURE coding (lost-packet positions known from RTP seq numbers) --
14// not error correction of silently-corrupted survivors; rate-adaptive FEC = deeper rung.
15//
16// CONSTRUCTION: generator G (n x k) = [ I_k ; Cauchy ]. Cauchy[j][i] = 1/((k+j) ^ i)
17// in GF(256) -> every k x k submatrix invertible (MDS). Decode = pick any k surviving
18// rows, solve the k x k GF system by Gauss-Jordan -> the original data shards.
19//
20// main() is the SELF-VALIDATING GATE. Evidence -> knowledge/status/room_fec.log.
21// license_tier: ORIGINAL
22import "nx_syscalls.nx"
23
24const FEC_LOG: *u8 = "knowledge/status/room_fec.log"
25const GF_POLY: i64 = 0x11d // primitive polynomial x^8+x^4+x^3+x^2+1
26
27func fw(fd: i64, s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(fd, s, n); return 0 }
28func fwn(fd: i64, v: i64) -> i64 { let bb: *u8 = sys_mmap(28); var m: i64=v; if m<0 {m=0-m; sys_write(fd,"-" as *u8,1)}; let t: *u8 = sys_mmap(28); var k: i64=0; if m==0 {t[0]=48;k=1}; while m>0 {t[k]=(48+(m%10)) as u8; m=m/10; k=k+1}; var i: i64=0; while i<k {bb[i]=t[k-1-i]; i=i+1}; sys_write(fd, bb, k); return 0 }
29
30// ---- GF(256) tables: exp[0..511] (doubled, no mod in mul), log[0..255] ----
31func gf_init(exp: *i64, log: *i64) -> i64 {
32 var x: i64 = 1
33 var i: i64 = 0
34 while i < 255 {
35 exp[i] = x
36 log[x] = i
37 x = x << 1
38 if (x & 256) != 0 { x = x ^ GF_POLY }
39 i = i + 1
40 }
41 i = 255
42 while i < 512 { exp[i] = exp[i - 255]; i = i + 1 }
43 log[0] = 0
44 return 0
45}
46func gf_mul(exp: *i64, log: *i64, a: i64, b: i64) -> i64 {
47 if a == 0 { return 0 }
48 if b == 0 { return 0 }
49 return exp[log[a] + log[b]]
50}
51func gf_inv(exp: *i64, log: *i64, a: i64) -> i64 {
52 return exp[255 - log[a]]
53}
54
55// build generator G (n x k), flattened row-major: top k rows = identity, bottom m = Cauchy.
56func fec_build_G(exp: *i64, log: *i64, G: *i64, k: i64, m: i64) -> i64 {
57 let n: i64 = k + m
58 var r: i64 = 0
59 while r < k {
60 var i: i64 = 0
61 while i < k { if i == r { G[r*k+i] = 1 } else { G[r*k+i] = 0 } i = i + 1 }
62 r = r + 1
63 }
64 var j: i64 = 0
65 while j < m {
66 var i: i64 = 0
67 while i < k {
68 G[(k+j)*k + i] = gf_inv(exp, log, (k + j) ^ i) // 1/((k+j) ^ i); disjoint -> never 0
69 i = i + 1
70 }
71 j = j + 1
72 }
73 return 0
74}
75
76// encode: data (k x S) -> shards (n x S). shard[r][c] = sum_i G[r][i]*data[i][c].
77func fec_encode(exp: *i64, log: *i64, G: *i64, data: *i64, shards: *i64, k: i64, m: i64, S: i64) -> i64 {
78 let n: i64 = k + m
79 var r: i64 = 0
80 while r < n {
81 var c: i64 = 0
82 while c < S {
83 var acc: i64 = 0
84 var i: i64 = 0
85 while i < k { acc = acc ^ gf_mul(exp, log, G[r*k+i], data[i*S+c]); i = i + 1 }
86 shards[r*S+c] = acc
87 c = c + 1
88 }
89 r = r + 1
90 }
91 return 0
92}
93
94// Gauss-Jordan solve A (k x k) * X = B (k x S) over GF(256), in place; B becomes X.
95// returns 0 ok, -1 singular (should not happen for an MDS submatrix).
96func gf_solve(exp: *i64, log: *i64, A: *i64, B: *i64, k: i64, S: i64) -> i64 {
97 var col: i64 = 0
98 while col < k {
99 var p: i64 = 0 - 1
100 var pr: i64 = col
101 while pr < k { if p < 0 { if A[pr*k+col] != 0 { p = pr } } pr = pr + 1 }
102 if p < 0 { return 0 - 1 } // no pivot found -> singular (should not happen for MDS)
103 if p != col {
104 var j: i64 = 0
105 while j < k { let t: i64 = A[col*k+j]; A[col*k+j] = A[p*k+j]; A[p*k+j] = t; j = j + 1 }
106 j = 0
107 while j < S { let t: i64 = B[col*S+j]; B[col*S+j] = B[p*S+j]; B[p*S+j] = t; j = j + 1 }
108 }
109 let inv: i64 = gf_inv(exp, log, A[col*k+col])
110 var j2: i64 = 0
111 while j2 < k { A[col*k+j2] = gf_mul(exp, log, A[col*k+j2], inv); j2 = j2 + 1 }
112 j2 = 0
113 while j2 < S { B[col*S+j2] = gf_mul(exp, log, B[col*S+j2], inv); j2 = j2 + 1 }
114 var r: i64 = 0
115 while r < k {
116 if r != col {
117 let f: i64 = A[r*k+col]
118 if f != 0 {
119 var j3: i64 = 0
120 while j3 < k { A[r*k+j3] = A[r*k+j3] ^ gf_mul(exp, log, f, A[col*k+j3]); j3 = j3 + 1 }
121 j3 = 0
122 while j3 < S { B[r*S+j3] = B[r*S+j3] ^ gf_mul(exp, log, f, B[col*S+j3]); j3 = j3 + 1 }
123 }
124 }
125 r = r + 1
126 }
127 col = col + 1
128 }
129 return 0
130}
131
132// decode: given shards (n x S) and erased[n] flags, recover data into out (k x S).
133// returns 0 ok, -1 if fewer than k shards survive (beyond the m-erasure bound).
134func fec_decode(exp: *i64, log: *i64, G: *i64, shards: *i64, erased: *i64, out: *i64, k: i64, m: i64, S: i64) -> i64 {
135 let n: i64 = k + m
136 let A: *i64 = sys_mmap(8 * k * k) as *i64
137 var got: i64 = 0
138 var r: i64 = 0
139 while r < n {
140 if got < k { if erased[r] == 0 {
141 var i: i64 = 0
142 while i < k { A[got*k+i] = G[r*k+i]; i = i + 1 }
143 var c: i64 = 0
144 while c < S { out[got*S+c] = shards[r*S+c]; c = c + 1 }
145 got = got + 1
146 } }
147 r = r + 1
148 }
149 if got < k { return 0 - 1 } // beyond the recovery bound (honest limit)
150 return gf_solve(exp, log, A, out, k, S) // out becomes the recovered data
151}
152
153// byte-exact compare of recovered out (k x S) vs original data; 1 if equal.
154func fec_data_eq(out: *i64, data: *i64, k: i64, S: i64) -> i64 {
155 var i: i64 = 0
156 while i < k {
157 var c: i64 = 0
158 while c < S { if out[i*S+c] != data[i*S+c] { return 0 } c = c + 1 }
159 i = i + 1
160 }
161 return 1
162}
163
164// run EVERY 3-erasure pattern (C(n,3)); return how many recovered byte-exact.
165func fec_exhaustive3(exp: *i64, log: *i64, G: *i64, shards: *i64, data: *i64, erased: *i64, out: *i64, k: i64, m: i64, S: i64) -> i64 {
166 let n: i64 = k + m
167 var recovered: i64 = 0
168 var a: i64 = 0
169 while a < n {
170 var b: i64 = a + 1
171 while b < n {
172 var cc: i64 = b + 1
173 while cc < n {
174 var z: i64 = 0
175 while z < n { erased[z] = 0; z = z + 1 }
176 erased[a] = 1; erased[b] = 1; erased[cc] = 1
177 let rc: i64 = fec_decode(exp, log, G, shards, erased, out, k, m, S)
178 if rc == 0 { if fec_data_eq(out, data, k, S) == 1 { recovered = recovered + 1 } }
179 cc = cc + 1
180 }
181 b = b + 1
182 }
183 a = a + 1
184 }
185 return recovered
186}
187
188func main() -> i64 {
189 let exp: *i64 = sys_mmap(8 * 512) as *i64
190 let log: *i64 = sys_mmap(8 * 256) as *i64
191 gf_init(exp, log)
192 // GF sanity: 2*128 in GF(256) with 0x11d = 1 (2^1 * 2^7 = 2^8 = reduce); inv self-check.
193 var ok: i64 = 1
194 if gf_mul(exp, log, 3, gf_inv(exp, log, 3)) != 1 { ok = 0 } // a * a^-1 = 1
195 if gf_mul(exp, log, 7, gf_inv(exp, log, 7)) != 1 { ok = 0 }
196
197 let k: i64 = 4
198 let m: i64 = 3
199 let n: i64 = k + m // 7
200 let S: i64 = 4
201 let G: *i64 = sys_mmap(8 * n * k) as *i64
202 fec_build_G(exp, log, G, k, m)
203
204 // original data: 4 shards x 4 bytes, deterministic non-trivial content
205 let data: *i64 = sys_mmap(8 * k * S) as *i64
206 var i: i64 = 0
207 while i < k {
208 var c: i64 = 0
209 while c < S { data[i*S+c] = (i*53 + c*29 + 17) & 255; c = c + 1 }
210 i = i + 1
211 }
212 let shards: *i64 = sys_mmap(8 * n * S) as *i64
213 fec_encode(exp, log, G, data, shards, k, m, S)
214
215 // systematic check: first k shards == data
216 if fec_data_eq(shards, data, k, S) != 1 { ok = 0 }
217
218 let erased: *i64 = sys_mmap(8 * n) as *i64
219 let out: *i64 = sys_mmap(8 * k * S) as *i64
220
221 // --- CORE: EXHAUSTIVE recovery of EVERY 3-erasure pattern (C(7,3)=35). All byte-exact. ---
222 let patterns: i64 = 35
223 let recovered_all: i64 = fec_exhaustive3(exp, log, G, shards, data, erased, out, k, m, S)
224 if recovered_all != 35 { ok = 0 } // MDS: ALL 3-loss patterns recover byte-exact
225
226 // --- neg-control / honest bound: 4 erasures (> m) -> decode MUST fail (cannot recover) ---
227 var z2: i64 = 0
228 while z2 < n { erased[z2] = 0; z2 = z2 + 1 }
229 erased[0]=1; erased[1]=1; erased[2]=1; erased[3]=1
230 let rc4: i64 = fec_decode(exp, log, G, shards, erased, out, k, m, S)
231 if rc4 != (0 - 1) { ok = 0 } // beyond bound -> honest FAIL, not a fake success
232
233 // --- tamper: corrupt one Cauchy matrix entry -> a 3-erasure recovery NO LONGER byte-exact ---
234 G[(k)*k + 0] = (G[(k)*k + 0] ^ 1) // flip a bit in the first parity row
235 var z3: i64 = 0
236 while z3 < n { erased[z3] = 0; z3 = z3 + 1 }
237 erased[0]=1; erased[1]=1; erased[2]=1 // erase 3 data shards -> needs the (now-corrupt) parity
238 fec_decode(exp, log, G, shards, erased, out, k, m, S)
239 var tampered_diff: i64 = 0
240 if fec_data_eq(out, data, k, S) == 0 { tampered_diff = 1 }
241 if tampered_diff != 1 { ok = 0 } // a corrupt matrix MUST break recovery (matrix is load-bearing)
242
243 fw(1, "ROOMFECGATE k=4 m=3 n=7 patterns=" as *u8); fwn(1, patterns)
244 fw(1, " recovered=" as *u8); fwn(1, recovered_all); fw(1, "/35 over_bound_rc=" as *u8); fwn(1, rc4)
245 fw(1, " tamper_broke=" as *u8); fwn(1, tampered_diff)
246 if ok == 1 { fw(1, " verdict=GREEN\n" as *u8) } else { fw(1, " verdict=RED\n" as *u8) }
247
248 let lf: i64 = sys_openat_append(FEC_LOG, 420)
249 if lf >= 0 {
250 fw(lf, "ROOMFECGATE k=4 m=3 n=7 patterns=" as *u8); fwn(lf, patterns)
251 fw(lf, " recovered=" as *u8); fwn(lf, recovered_all); fw(lf, "/35 over_bound_rc=" as *u8); fwn(lf, rc4)
252 fw(lf, " tamper_broke=" as *u8); fwn(lf, tampered_diff)
253 if ok == 1 { fw(lf, " verdict=GREEN\n" as *u8) } else { fw(lf, " verdict=RED\n" as *u8) }
254 sys_close(lf)
255 }
256 if ok == 1 { sys_exit(0) } else { sys_exit(1) }
257 return 0
258}