`nx_gzip_kat.nx` source

↩ module page · 201 lines · 11127 B
1// nx_gzip_kat.nx -- THE SOVEREIGN DEFLATE ROUND-TRIP KAT: the rostered tooth for /compare/performance
2// PF3 (dynamic Huffman) and the lazy-matching rung, 2026-09-01. Until today the proof that gz_compress
3// emits streams every inflater accepts lived in ONE session record (nx_gunzip by hand, zlib-strict on
4// a laptop, GNU gzip on another machine). A proof nobody re-runs is a claim. This gate re-runs it on
5// every roster beat against the SHIPPED artifacts -- the wasm module every world page carries and a
6// served world page -- plus an adversarial synthetic set, through the estate's own inflater with its
7// CRC32 and ISIZE checks armed.
8//
9// WHY THE TEETH ARE SHAPED THIS WAY:
10//   - round-trip = inflate returns EXACTLY n bytes AND every byte matches. A stub that copies input
11//     through fails the gzip-magic tooth; a stub that emits nothing fails round-trip; a stream one
12//     Kraft unit over-subscribed (the 2026-08-29 defect) fails inflate.
13//   - the MODULE must come back BTYPE=10 (dynamic) and under GK_MODULE_PERMIL_BAR. The bar is DERIVED
14//     from the board's own measurements on this module class: lazy+fixed measured 499 permil, zlib -9
15//     429, lazy+dynamic 430. 460 sits between the encoder this rung replaced and the encoder it
16//     shipped, with 39 permil of margin to each -- so the fixed-Huffman encoder CANNOT pass this tooth
17//     and the shipped one passes it with room for input drift. Not a taste.
18//   - a TINY input must come back BTYPE=01 (fixed): the block choice is an arithmetic comparison per
19//     input, never a mode flag, and this is the input where fixed wins.
20//   - neg-control-corrupt-stream: one flipped byte in the compressed body must be REFUSED or must not
21//     reproduce the input. A round-trip oracle that cannot fail is decoration.
22//   - adversarial-kraft-limiter: gz_dh_lens over 40 exponentially skewed symbols (raw depth 39) must
23//     return a COMPLETE 15-bit code (Kraft sum exactly 2^15) with no length over 15 and no used
24//     symbol at 0. This is the arithmetic that came out one unit over on 2026-08-29.
25// PRECONDITIONS are declared with gv_need (SKIP, never RED): the module and the page are estate
26// artifacts that may be absent on a foreign tree.
27// license_tier: ORIGINAL   No hw writes (Rule 26).   expect_exit: 0
28import "nx_syscalls.nx"
29import "nx_gzip_lib.nx"
30import "nx_inflate.nx"
31import "nx_gate_verdict.nx"
32
33const GK_MODULE: *u8 = "buildroot/_build/nx_wasm_craft_emit.wasm"
34const GK_PAGE: *u8 = "sites/nishifamily/world/beach.html"
35const GK_SYN_N: i64 = 65536
36const GK_MODULE_PERMIL_BAR: i64 = 460
37const GK_SLACK: i64 = 4096
38const GK_NAMECAP: i64 = 512
39const GK_LCG_A: i64 = 1103515245
40const GK_LCG_C: i64 = 12345
41const GK_LCG_MASK: i64 = 2147483647
42const GK_LCG_SEED: i64 = 20260901
43const GK_SKEW_SYMS: i64 = 40
44const GK_SKEW_VALS: i64 = 16
45const GK_SKEW_TOP: i64 = 32768
46const GK_MAXBITS: i64 = 15
47const GK_LITLEN_N: i64 = 286
48const GK_GZ_HDR: i64 = 10
49const GK_FLIP: i64 = 85
50const GK_ASCII_A: i64 = 65
51const GK_ASCII_a: i64 = 97
52
53// BTYPE of the first deflate block: bit 0 of the first deflate byte is BFINAL, bits 1-2 are BTYPE
54func gk_btype(ob: *u8) -> i64 { return ((ob[GK_GZ_HDR] as i64) >> 1) & 3 }
55
56// compress, inflate through the sovereign decoder, byte-compare. Prints the fixture line, adds the
57// round-trip and gzip-magic teeth, hands the compressed buffer back through obout, returns its length.
58func gk_roundtrip(name: *u8, src: *u8, n: i64, ctr: *i64, obout: *i64) -> i64 {
59    let ob: *u8 = sys_mmap(n * 2 + GK_SLACK)
60    let olen: i64 = gz_compress(src, n, 2, ob)
61    let out: *u8 = sys_mmap(n + GK_SLACK)
62    let rc: i64 = inf_gunzip(ob, olen, out, n + GK_SLACK)
63    var same: i64 = 0
64    if rc == n {
65        same = 1
66        var i: i64 = 0
67        while i < n { if out[i] != src[i] { same = 0; i = n } i = i + 1 }
68    }
69    var magic: i64 = 0
70    if olen > GK_GZ_HDR { if (ob[0] as i64) == 31 { if (ob[1] as i64) == 139 { magic = 1 } } }
71    gv_puts("  fixture " as *u8); gv_puts(name); gv_puts(": in=" as *u8); gv_num(n); gv_puts(" out=" as *u8); gv_num(olen)
72    gv_puts(" btype=" as *u8); gv_num(gk_btype(ob)); gv_puts(" inflate_rc=" as *u8); gv_num(rc); gv_puts("\n" as *u8)
73    let nb: *u8 = sys_mmap(GK_NAMECAP)
74    var o: i64 = gv_cat(nb, 0, name)
75    o = gv_cat(nb, o, ": gzip magic present" as *u8)
76    nb[o] = 0 as u8
77    gv_check(nb, magic, ctr)
78    let nb2: *u8 = sys_mmap(GK_NAMECAP)
79    var o2: i64 = gv_cat(nb2, 0, name)
80    o2 = gv_cat(nb2, o2, ": round-trips byte-identical through inf_gunzip (CRC32 and ISIZE armed)" as *u8)
81    nb2[o2] = 0 as u8
82    gv_check(nb2, same, ctr)
83    obout[0] = ob as i64
84    return olen
85}
86
87func main() -> i64 {
88    let ctr: *i64 = gv_ctr()
89    gv_head("=== nx_gzip_kat -- sovereign DEFLATE round-trip KAT (PF3 dynamic Huffman + lazy matching) ===" as *u8)
90    let box: *i64 = sys_mmap(16) as *i64
91    let obb: *i64 = sys_mmap(16) as *i64
92
93    // ---- the shipped module: the payload the rung was measured on ----
94    let mod: *u8 = sys_read_file(GK_MODULE, box)
95    var have_mod: i64 = 0
96    if (mod as i64) != 0 { if box[0] > 0 { have_mod = 1 } }
97    if gv_need("module artifact readable (buildroot/_build/nx_wasm_craft_emit.wasm)" as *u8, have_mod, ctr) == 1 {
98        let mn: i64 = box[0]
99        let mlen: i64 = gk_roundtrip("module" as *u8, mod, mn, ctr, obb)
100        let mob: *u8 = obb[0] as *u8
101        gv_check("module: block is BTYPE=10 dynamic Huffman (the PF3 contract, read from the stream bits)" as *u8, (gk_btype(mob) == 2) as i64, ctr)
102        let permil: i64 = mlen * 1000 / mn
103        gv_puts("  module permil=" as *u8); gv_num(permil); gv_puts(" bar=" as *u8); gv_num(GK_MODULE_PERMIL_BAR); gv_puts(" (lazy+fixed measured 499, zlib -9 measured 429)\n" as *u8)
104        gv_check("module: compressed size under the derived bar -- a fixed-Huffman encoder cannot pass this tooth" as *u8, (permil <= GK_MODULE_PERMIL_BAR) as i64, ctr)
105        // neg-control: one flipped byte mid-stream must be refused or must not reproduce the input
106        let cob: *u8 = sys_mmap(mn * 2 + GK_SLACK)
107        var ci: i64 = 0
108        while ci < mlen { cob[ci] = mob[ci]; ci = ci + 1 }
109        let mid: i64 = mlen / 2
110        cob[mid] = ((cob[mid] as i64) ^ GK_FLIP) as u8
111        let cout: *u8 = sys_mmap(mn + GK_SLACK)
112        let crc9: i64 = inf_gunzip(cob, mlen, cout, mn + GK_SLACK)
113        var bad_fires: i64 = 0
114        if crc9 != mn { bad_fires = 1 } else {
115            var cj: i64 = 0
116            while cj < mn { if cout[cj] != mod[cj] { bad_fires = 1; cj = mn } cj = cj + 1 }
117        }
118        let gout: *u8 = sys_mmap(mn + GK_SLACK)
119        let grc: i64 = inf_gunzip(mob, mlen, gout, mn + GK_SLACK)
120        var good_fires: i64 = 1
121        if grc == mn { good_fires = 0 }
122        gv_puts("  corrupt-stream inflate_rc=" as *u8); gv_num(crc9); gv_puts(" clean-stream inflate_rc=" as *u8); gv_num(grc); gv_puts("\n" as *u8)
123        gv_bite("neg-control-corrupt-stream: a flipped byte is refused or fails to reproduce; the clean stream reproduces" as *u8, bad_fires, good_fires, ctr)
124    }
125
126    // ---- a served world page: the response class the front door compresses ----
127    let pg: *u8 = sys_read_file(GK_PAGE, box)
128    var have_pg: i64 = 0
129    if (pg as i64) != 0 { if box[0] > 0 { have_pg = 1 } }
130    if gv_need("served world page readable (sites/nishifamily/world/beach.html)" as *u8, have_pg, ctr) == 1 {
131        let pn: i64 = box[0]
132        let plen: i64 = gk_roundtrip("page" as *u8, pg, pn, ctr, obb)
133        gv_check("page: block is BTYPE=10 dynamic Huffman" as *u8, (gk_btype(obb[0] as *u8) == 2) as i64, ctr)
134        gv_check("page: output strictly smaller than input" as *u8, (plen < pn) as i64, ctr)
135    }
136
137    // ---- the adversarial synthetic set ----
138    let e0: *u8 = sys_mmap(GK_SLACK)
139    gk_roundtrip("empty" as *u8, e0, 0, ctr, obb)
140    let e1: *u8 = sys_mmap(GK_SLACK)
141    e1[0] = GK_ASCII_A as u8
142    gk_roundtrip("one-byte" as *u8, e1, 1, ctr, obb)
143    gv_check("tiny input chooses BTYPE=01 fixed -- the block choice is arithmetic per input, not a mode flag" as *u8, (gk_btype(obb[0] as *u8) == 1) as i64, ctr)
144    let z: *u8 = sys_mmap(GK_SYN_N)
145    gk_roundtrip("zeros-64k" as *u8, z, GK_SYN_N, ctr, obb)
146    let r: *u8 = sys_mmap(GK_SYN_N)
147    var x: i64 = GK_LCG_SEED
148    var ri: i64 = 0
149    while ri < GK_SYN_N { x = (x * GK_LCG_A + GK_LCG_C) & GK_LCG_MASK; r[ri] = ((x >> 16) & 255) as u8; ri = ri + 1 }
150    let rl: i64 = gk_roundtrip("lcg-random-64k" as *u8, r, GK_SYN_N, ctr, obb)
151    gv_check("incompressible input stays inside input plus the stored-block envelope" as *u8, (rl < GK_SYN_N + GK_SLACK) as i64, ctr)
152    let m: *u8 = sys_mmap(GK_SYN_N)
153    var mi: i64 = 0
154    while mi < GK_SYN_N { m[mi] = (GK_ASCII_a + (mi % 3)) as u8; mi = mi + 1 }
155    gk_roundtrip("abc-run-64k" as *u8, m, GK_SYN_N, ctr, obb)
156    let k: *u8 = sys_mmap(GK_SYN_N)
157    var ki: i64 = 0
158    var sym: i64 = 0
159    var cnt: i64 = GK_SKEW_TOP
160    while sym < GK_SKEW_VALS {
161        var c2: i64 = 0
162        while c2 < cnt { if ki < GK_SYN_N { k[ki] = (sym * 7 + 3) as u8; ki = ki + 1 } c2 = c2 + 1 }
163        cnt = cnt / 2
164        sym = sym + 1
165    }
166    gk_roundtrip("exp-skew-64k" as *u8, k, ki, ctr, obb)
167
168    // ---- the length limiter, driven directly on an input that REQUIRES limiting ----
169    let fq: *i64 = sys_mmap(GK_LITLEN_N * 8 + 64) as *i64
170    let ln: *i64 = sys_mmap(GK_LITLEN_N * 8 + 64) as *i64
171    var fi: i64 = 0
172    while fi < GK_LITLEN_N { fq[fi] = 0; ln[fi] = 0; fi = fi + 1 }
173    var f: i64 = 1
174    var si: i64 = 0
175    while si < GK_SKEW_SYMS { fq[si] = f; f = f * 2; si = si + 1 }
176    let used: i64 = gz_dh_lens(fq, GK_LITLEN_N, GK_MAXBITS, ln)
177    var kraft: i64 = 0
178    var over: i64 = 0
179    var zero_used: i64 = 0
180    var nz_unused: i64 = 0
181    var li: i64 = 0
182    while li < GK_LITLEN_N {
183        if ln[li] > GK_MAXBITS { over = over + 1 }
184        if fq[li] > 0 { if ln[li] == 0 { zero_used = zero_used + 1 } else { if ln[li] <= GK_MAXBITS { kraft = kraft + gz_dh_pow2(GK_MAXBITS - ln[li]) } } }
185        if fq[li] == 0 { if ln[li] != 0 { nz_unused = nz_unused + 1 } }
186        li = li + 1
187    }
188    gv_puts("  kraft: used=" as *u8); gv_num(used); gv_puts(" sum=" as *u8); gv_num(kraft); gv_puts(" of " as *u8); gv_num(gz_dh_pow2(GK_MAXBITS))
189    gv_puts(" over15=" as *u8); gv_num(over); gv_puts(" used-at-zero=" as *u8); gv_num(zero_used); gv_puts(" unused-nonzero=" as *u8); gv_num(nz_unused); gv_puts("\n" as *u8)
190    gv_check("adversarial-kraft-limiter: 40 exponentially skewed symbols (raw depth 39) yield a COMPLETE 15-bit code, Kraft sum exactly 2^15" as *u8, (kraft == gz_dh_pow2(GK_MAXBITS)) as i64, ctr)
191    var shape_ok: i64 = 1
192    if over != 0 { shape_ok = 0 }
193    if zero_used != 0 { shape_ok = 0 }
194    if nz_unused != 0 { shape_ok = 0 }
195    if used != GK_SKEW_SYMS { shape_ok = 0 }
196    gv_check("kraft-limiter shape: no length over 15, every used symbol coded, no unused symbol coded, used count exact" as *u8, shape_ok, ctr)
197
198    let rc: i64 = gv_verdict("GZIP-KAT" as *u8, ctr, "sovereign DEFLATE round-trip KAT over shipped artifacts and an adversarial set" as *u8)
199    sys_exit(rc)
200    return rc
201}
nx_gzip_kat.nx source

`nx_gzip_kat.nx` source
