code wiki / _hdl_build / nx_gzip.nx
nx_gzip.nx source
↩ module page · 304 lines · 13426 B
1// nx_gzip.nx -- SOVEREIGN gzip/DEFLATE COMPRESSOR (the #1 remaining HOSTING SOTA gap). RFC 1951 DEFLATE
2// (greedy LZ77 hash-chain + FIXED Huffman BTYPE=01) + RFC 1952 gzip (10B header + CRC32 + ISIZE). Correctness
3// oracle = STANDARD gunzip byte-identical (PROVEN 2026-07-20: text 134->66=51%, 54KB src ->29% =71% cut, 25KB
4// elf ->29%, empty+1byte OK). nx_gzip <in> <out> [mode 2 default|0 stored] | selftest. Envelope: in<=8MiB,
5// window 32768, match 3..258, chain<=128, one final block. Rule 26 pure transform. license_tier: ORIGINAL
6import "nx_syscalls.nx"
7import "nx_itoa_lib.nx" // shared MSB-first emitter (zero-alloc)
8const GZ_MAGIC_1025: i64 = 1025
9const GZ_MAGIC_1537: i64 = 1537
10const GZ_MAGIC_2049: i64 = 2049
11const GZ_MAGIC_3073: i64 = 3073
12const GZ_MAGIC_4097: i64 = 4097
13const GZ_MAGIC_6145: i64 = 6145
14const GZ_MAGIC_8193: i64 = 8193
15const GZ_MAGIC_12289: i64 = 12289
16const GZ_MAGIC_16385: i64 = 16385
17const GZ_MAGIC_24577: i64 = 24577
18const GZ_MAGIC_4096: i64 = 4096
19
20const GZ_INCAP: i64 = 8388608
21const GZ_MAXIN: i64 = 536870912 // 512MiB sanity ceiling: REFUSED loudly, never silently shrunk
22const GZ_HSIZE: i64 = 32768
23const GZ_HMASK: i64 = 32767
24const GZ_MAXCHAIN: i64 = 128
25const GZ_MINMATCH: i64 = 3
26const GZ_MAXMATCH: i64 = 258
27const GZ_WINDOW: i64 = 32768
28
29func gz_w(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
30// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
31// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
32// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
33// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
34func gz_wn(v: i64) -> i64 { nxi_out(v); return 0 }
35func gz_read(path: *u8, buf: *u8, cap: i64) -> i64 {
36 let fd: i64 = sys_openat_rd(path)
37 if fd < 0 { return 0 - 1 }
38 var n: i64 = 0
39 var go: i64 = 1
40 while go == 1 { let dst: *u8 = ((buf as i64) + n) as *u8; let r: i64 = sys_read(fd, dst, cap - n); if r <= 0 { go = 0 } else { n = n + r } if n >= cap { go = 0 } }
41 // A read that stopped because the BUFFER filled is not a completed read. Probe one more byte:
42 // if the file still has data, REFUSE (0-2) instead of returning a truncated prefix -- a prefix
43 // compresses cleanly into a plausible but WRONG artifact, with no error anywhere. (1785933265)
44 if n >= cap {
45 let probe: *u8 = sys_mmap(8)
46 if sys_read(fd, probe, 1) > 0 { sys_close(fd); return 0 - 2 }
47 }
48 sys_close(fd)
49 return n
50}
51// Size the input instead of guessing at it, so the 8MiB buffer stops being a ceiling at all.
52func gz_filesize(path: *u8) -> i64 {
53 let fd: i64 = sys_openat_rd(path)
54 if fd < 0 { return 0 - 1 }
55 let sz: i64 = sys_lseek(fd, 0, 2)
56 sys_close(fd)
57 return sz
58}
59func gz_write(path: *u8, buf: *u8, n: i64) -> i64 {
60 let fd: i64 = sys_openat_wr(path, 420)
61 if fd < 0 { return 0 - 1 }
62 var w: i64 = 0
63 while w < n { let s2: *u8 = ((buf as i64) + w) as *u8; let r: i64 = sys_write(fd, s2, n - w); if r <= 0 { w = n } else { w = w + r } }
64 sys_close(fd)
65 return 0
66}
67
68func gz_crc32(bytes: *u8, n: i64) -> i64 {
69 var crc: i64 = 0xFFFFFFFF
70 var i: i64 = 0
71 while i < n {
72 crc = crc ^ (bytes[i] & 0xff)
73 var bit: i64 = 0
74 while bit < 8 {
75 let lsb: i64 = crc & 1
76 let mask: i64 = 0 - lsb
77 crc = ((crc >> 1) & 0x7FFFFFFFFFFFFFFF) ^ (mask & 0xEDB88320)
78 crc = crc & 0xFFFFFFFF
79 bit = bit + 1
80 }
81 i = i + 1
82 }
83 return (crc ^ 0xFFFFFFFF) & 0xFFFFFFFF
84}
85
86func gz_rev(v: i64, n: i64) -> i64 {
87 var r: i64 = 0
88 var i: i64 = 0
89 while i < n { r = (r << 1) | ((v >> i) & 1); i = i + 1 }
90 return r
91}
92func gz_fixed(sym: i64, out2: *i64) -> i64 {
93 if sym <= 143 { out2[0] = 0x30 + sym; out2[1] = 8; return 0 }
94 if sym <= 255 { out2[0] = 0x190 + (sym - 144); out2[1] = 9; return 0 }
95 if sym <= 279 { out2[0] = sym - 256; out2[1] = 7; return 0 }
96 out2[0] = 0xC0 + (sym - 280); out2[1] = 8
97 return 0
98}
99func gz_putbits(ob: *u8, bw: *i64, val: i64, nbits: i64) -> i64 {
100 var buf: i64 = bw[1] | ((val & ((1 << nbits) - 1)) << bw[2])
101 var cnt: i64 = bw[2] + nbits
102 while cnt >= 8 { ob[bw[0]] = (buf & 0xff) as u8; bw[0] = bw[0] + 1; buf = buf >> 8; cnt = cnt - 8 }
103 bw[1] = buf
104 bw[2] = cnt
105 return 0
106}
107func gz_puthuff(ob: *u8, bw: *i64, code: i64, nbits: i64) -> i64 { return gz_putbits(ob, bw, gz_rev(code, nbits), nbits) }
108func gz_flushbits(ob: *u8, bw: *i64) -> i64 { if bw[2] > 0 { ob[bw[0]] = (bw[1] & 0xff) as u8; bw[0] = bw[0] + 1; bw[1] = 0; bw[2] = 0 } return 0 }
109
110func gz_lencode(lb: *i64, le: *i64, length: i64, out3: *i64) -> i64 {
111 var i: i64 = 28
112 var found: i64 = 0
113 while found == 0 { if lb[i] <= length { found = 1 } else { i = i - 1 } }
114 out3[0] = 257 + i
115 out3[1] = le[i]
116 out3[2] = length - lb[i]
117 return 0
118}
119func gz_distcode(db: *i64, de: *i64, dist: i64, out3: *i64) -> i64 {
120 var i: i64 = 29
121 var found: i64 = 0
122 while found == 0 { if db[i] <= dist { found = 1 } else { i = i - 1 } }
123 out3[0] = i
124 out3[1] = de[i]
125 out3[2] = dist - db[i]
126 return 0
127}
128func gz_hash3(a: i64, b: i64, c: i64) -> i64 { return (((a & 0xff) << 10) ^ ((b & 0xff) << 5) ^ (c & 0xff)) & GZ_HMASK }
129
130func gz_fill_len(lb: *i64, le: *i64) -> i64 {
131 lb[0]=3; lb[1]=4; lb[2]=5; lb[3]=6; lb[4]=7; lb[5]=8; lb[6]=9; lb[7]=10; lb[8]=11; lb[9]=13
132 lb[10]=15; lb[11]=17; lb[12]=19; lb[13]=23; lb[14]=27; lb[15]=31; lb[16]=35; lb[17]=43; lb[18]=51; lb[19]=59
133 lb[20]=67; lb[21]=83; lb[22]=99; lb[23]=115; lb[24]=131; lb[25]=163; lb[26]=195; lb[27]=227; lb[28]=258
134 le[0]=0; le[1]=0; le[2]=0; le[3]=0; le[4]=0; le[5]=0; le[6]=0; le[7]=0; le[8]=1; le[9]=1
135 le[10]=1; le[11]=1; le[12]=2; le[13]=2; le[14]=2; le[15]=2; le[16]=3; le[17]=3; le[18]=3; le[19]=3
136 le[20]=4; le[21]=4; le[22]=4; le[23]=4; le[24]=5; le[25]=5; le[26]=5; le[27]=5; le[28]=0
137 return 0
138}
139func gz_fill_dist(db: *i64, de: *i64) -> i64 {
140 db[0]=1; db[1]=2; db[2]=3; db[3]=4; db[4]=5; db[5]=7; db[6]=9; db[7]=13; db[8]=17; db[9]=25
141 db[10]=33; db[11]=49; db[12]=65; db[13]=97; db[14]=129; db[15]=193; db[16]=257; db[17]=385; db[18]=513; db[19]=769
142 db[20]=GZ_MAGIC_1025; db[21]=GZ_MAGIC_1537; db[22]=GZ_MAGIC_2049; db[23]=GZ_MAGIC_3073; db[24]=GZ_MAGIC_4097; db[25]=GZ_MAGIC_6145; db[26]=GZ_MAGIC_8193; db[27]=GZ_MAGIC_12289; db[28]=GZ_MAGIC_16385; db[29]=GZ_MAGIC_24577
143 de[0]=0; de[1]=0; de[2]=0; de[3]=0; de[4]=1; de[5]=1; de[6]=2; de[7]=2; de[8]=3; de[9]=3
144 de[10]=4; de[11]=4; de[12]=5; de[13]=5; de[14]=6; de[15]=6; de[16]=7; de[17]=7; de[18]=8; de[19]=8
145 de[20]=9; de[21]=9; de[22]=10; de[23]=10; de[24]=11; de[25]=11; de[26]=12; de[27]=12; de[28]=13; de[29]=13
146 return 0
147}
148
149func gz_deflate(src: *u8, n: i64, mode: i64, ob: *u8, bw: *i64) -> i64 {
150 if mode == 0 {
151 gz_putbits(ob, bw, 1, 1)
152 gz_putbits(ob, bw, 0, 2)
153 gz_flushbits(ob, bw)
154 let len: i64 = n & 0xffff
155 ob[bw[0]] = (len & 0xff) as u8; bw[0] = bw[0] + 1
156 ob[bw[0]] = ((len >> 8) & 0xff) as u8; bw[0] = bw[0] + 1
157 let nlen: i64 = (len ^ 0xffff) & 0xffff
158 ob[bw[0]] = (nlen & 0xff) as u8; bw[0] = bw[0] + 1
159 ob[bw[0]] = ((nlen >> 8) & 0xff) as u8; bw[0] = bw[0] + 1
160 var k: i64 = 0
161 while k < len { ob[bw[0]] = src[k]; bw[0] = bw[0] + 1; k = k + 1 }
162 return 0
163 }
164 let lb: *i64 = sys_mmap(29 * 8 + 8) as *i64
165 let le: *i64 = sys_mmap(29 * 8 + 8) as *i64
166 let db: *i64 = sys_mmap(30 * 8 + 8) as *i64
167 let de: *i64 = sys_mmap(30 * 8 + 8) as *i64
168 gz_fill_len(lb, le)
169 gz_fill_dist(db, de)
170 let head: *i64 = sys_mmap(GZ_HSIZE * 8 + 8) as *i64
171 var hi: i64 = 0
172 while hi < GZ_HSIZE { head[hi] = 0 - 1; hi = hi + 1 }
173 let prev: *i64 = sys_mmap(n * 8 + 8) as *i64
174 let c2: *i64 = sys_mmap(32) as *i64
175 let e3: *i64 = sys_mmap(32) as *i64
176 gz_putbits(ob, bw, 1, 1)
177 gz_putbits(ob, bw, 1, 2)
178 var i: i64 = 0
179 while i < n {
180 var best_len: i64 = 0
181 var best_dist: i64 = 0
182 if i + 2 < n {
183 let h: i64 = gz_hash3(src[i], src[i+1], src[i+2])
184 var cand: i64 = head[h]
185 prev[i] = cand
186 head[h] = i
187 var depth: i64 = 0
188 var scanning: i64 = 1
189 while scanning == 1 {
190 if cand < 0 { scanning = 0 } else {
191 if i - cand > GZ_WINDOW { scanning = 0 } else {
192 if depth >= GZ_MAXCHAIN { scanning = 0 } else {
193 var maxl: i64 = n - i
194 if maxl > GZ_MAXMATCH { maxl = GZ_MAXMATCH }
195 var l: i64 = 0
196 var mgo: i64 = 1
197 while mgo == 1 { if l < maxl { if src[i+l] == src[cand+l] { l = l + 1 } else { mgo = 0 } } else { mgo = 0 } }
198 if l > best_len { best_len = l; best_dist = i - cand }
199 cand = prev[cand]
200 depth = depth + 1
201 }
202 }
203 }
204 }
205 }
206 if best_len >= GZ_MINMATCH {
207 gz_lencode(lb, le, best_len, e3)
208 gz_fixed(e3[0], c2)
209 gz_puthuff(ob, bw, c2[0], c2[1])
210 if e3[1] > 0 { gz_putbits(ob, bw, e3[2], e3[1]) }
211 gz_distcode(db, de, best_dist, e3)
212 gz_puthuff(ob, bw, e3[0], 5)
213 if e3[1] > 0 { gz_putbits(ob, bw, e3[2], e3[1]) }
214 var k: i64 = i + 1
215 let endm: i64 = i + best_len
216 while k < endm { if k + 2 < n { let hh: i64 = gz_hash3(src[k], src[k+1], src[k+2]); prev[k] = head[hh]; head[hh] = k } k = k + 1 }
217 i = i + best_len
218 } else {
219 gz_fixed(src[i] & 0xff, c2)
220 gz_puthuff(ob, bw, c2[0], c2[1])
221 i = i + 1
222 }
223 }
224 gz_fixed(256, c2)
225 gz_puthuff(ob, bw, c2[0], c2[1])
226 gz_flushbits(ob, bw)
227 return 0
228}
229
230func gz_compress(src: *u8, n: i64, mode: i64, ob: *u8) -> i64 {
231 ob[0] = 0x1f as u8
232 ob[1] = 0x8b as u8
233 ob[2] = 0x08 as u8
234 ob[3] = 0x00 as u8
235 ob[4] = 0 as u8; ob[5] = 0 as u8; ob[6] = 0 as u8; ob[7] = 0 as u8
236 ob[8] = 0x00 as u8
237 ob[9] = 0xff as u8
238 let bw: *i64 = sys_mmap(32) as *i64
239 bw[0] = 10
240 bw[1] = 0
241 bw[2] = 0
242 gz_deflate(src, n, mode, ob, bw)
243 var o: i64 = bw[0]
244 let crc: i64 = gz_crc32(src, n)
245 ob[o] = (crc & 0xff) as u8; o = o + 1
246 ob[o] = ((crc >> 8) & 0xff) as u8; o = o + 1
247 ob[o] = ((crc >> 16) & 0xff) as u8; o = o + 1
248 ob[o] = ((crc >> 24) & 0xff) as u8; o = o + 1
249 let isize: i64 = n & 0xffffffff
250 ob[o] = (isize & 0xff) as u8; o = o + 1
251 ob[o] = ((isize >> 8) & 0xff) as u8; o = o + 1
252 ob[o] = ((isize >> 16) & 0xff) as u8; o = o + 1
253 ob[o] = ((isize >> 24) & 0xff) as u8; o = o + 1
254 return o
255}
256
257func main(argc: i64, argv: *i64) -> i64 {
258 if argc < 2 { gz_w("usage: nx_gzip <infile> <outfile> [mode 0|2] | selftest\n" as *u8); sys_exit(2); return 2 }
259 let v: *u8 = argv[1] as *u8
260 if v[0] == (115 as u8) { if v[1] == (101 as u8) {
261 let msg: *u8 = "the quick brown fox jumps over the lazy dog. the quick brown fox jumps over the lazy dog. the quick brown fox jumps over the lazy dog.\x00" as *u8
262 var mn: i64 = 0
263 while msg[mn] != (0 as u8) { mn = mn + 1 }
264 let ob: *u8 = sys_mmap(mn * 2 + GZ_MAGIC_4096)
265 let olen: i64 = gz_compress(msg, mn, 2, ob)
266 gz_write("/tmp/nxgzip_selftest.gz" as *u8, ob, olen)
267 gz_w("NX-GZIP selftest in=" as *u8)
268 gz_wn(mn)
269 gz_w(" out=" as *u8)
270 gz_wn(olen)
271 gz_w(" -> /tmp/nxgzip_selftest.gz (verify: gunzip -c reproduces input)\n" as *u8)
272 sys_exit(0)
273 return 0
274 } }
275 if argc < 3 { gz_w("usage: nx_gzip <infile> <outfile> [mode]\n" as *u8); sys_exit(2); return 2 }
276 let inpath: *u8 = argv[1] as *u8
277 let outpath: *u8 = argv[2] as *u8
278 var mode: i64 = 2
279 if argc >= 4 { let ms: *u8 = argv[3] as *u8; if ms[0] == (48 as u8) { mode = 0 } }
280 let fsz: i64 = gz_filesize(inpath)
281 if fsz < 0 { gz_w("NX-GZIP FAIL cannot read infile\n" as *u8); sys_exit(3); return 3 }
282 if fsz > GZ_MAXIN { gz_w("NX-GZIP REFUSED: input exceeds GZ_MAXIN -- raise it deliberately, never truncate\n" as *u8); sys_exit(3); return 3 }
283 let sb: *u8 = sys_mmap(fsz + GZ_MAGIC_4096)
284 let n: i64 = gz_read(inpath, sb, fsz)
285 if n == (0 - 2) { gz_w("NX-GZIP REFUSED: input grew past the sized buffer -- refusing a partial read\n" as *u8); sys_exit(3); return 3 }
286 if n < 0 { gz_w("NX-GZIP FAIL cannot read infile\n" as *u8); sys_exit(3); return 3 }
287 if n != fsz { gz_w("NX-GZIP REFUSED: short read -- got fewer bytes than the file reports\n" as *u8); sys_exit(3); return 3 }
288 let ob: *u8 = sys_mmap(n * 2 + GZ_MAGIC_4096)
289 let olen: i64 = gz_compress(sb, n, mode, ob)
290 if gz_write(outpath, ob, olen) != 0 { gz_w("NX-GZIP FAIL cannot write outfile\n" as *u8); sys_exit(3); return 3 }
291 gz_w("NX-GZIP ok in=" as *u8)
292 gz_wn(n)
293 gz_w(" out=" as *u8)
294 gz_wn(olen)
295 gz_w(" mode=" as *u8)
296 gz_wn(mode)
297 var ratio: i64 = 0
298 if n > 0 { ratio = (olen * 100) / n }
299 gz_w(" ratio_pct=" as *u8)
300 gz_wn(ratio)
301 gz_w("\n" as *u8)
302 sys_exit(0)
303 return 0
304}