nx_deflate_enc.nx source
↩ module page · 155 lines · 7603 B
1// nx_deflate_enc.nx -- SOVEREIGN DEFLATE (RFC 1951) COMPRESSOR: LZ77 + FIXED Huffman (BTYPE=01). Pure integer,
2// no zlib. The COUNTERPART to nx_deflate.nx (which only inflates). Turns our uncompressed PNGs (590KB/frame
3// raw) into real compressed ones so renders ship full-resolution. LZ77 hashes 3 bytes -> most-recent position
4// (single candidate, extends fully -> zero/near-repeat runs after PNG filtering compress well = RLE-class +
5// literal-repeat). Bit packing per spec: data elements LSB-first, Huffman codes MSB-first (bit-reversed).
6// Verified round-trip against nx_deflate's inflate. license_tier: ORIGINAL
7import "nx_syscalls.nx"
8const DFE_MAGIC_1025: i64 = 1025
9const DFE_MAGIC_1537: i64 = 1537
10const DFE_MAGIC_2049: i64 = 2049
11const DFE_MAGIC_3073: i64 = 3073
12const DFE_MAGIC_4097: i64 = 4097
13const DFE_MAGIC_6145: i64 = 6145
14const DFE_MAGIC_8193: i64 = 8193
15const DFE_MAGIC_12289: i64 = 12289
16const DFE_MAGIC_16385: i64 = 16385
17const DFE_MAGIC_24577: i64 = 24577
18
19const DFE_HSIZE: i64 = 32768
20const DFE_WINDOW: i64 = 32768
21const DFE_MINMATCH: i64 = 3
22const DFE_MAXMATCH: i64 = 258
23
24// bit writer state: st[0]=out index, st[1]=bit accumulator, st[2]=bit count
25func dfe_bits(out: *u8, st: *i64, val: i64, n: i64) -> i64 {
26 let mask: i64 = (1 << n) - 1
27 st[1] = st[1] | ((val & mask) << st[2])
28 st[2] = st[2] + n
29 while st[2] >= 8 {
30 out[st[0]] = (st[1] & 0xff) as u8
31 st[0] = st[0] + 1
32 st[1] = st[1] >> 8
33 st[2] = st[2] - 8
34 }
35 return 0
36}
37func dfe_rev(code: i64, n: i64) -> i64 {
38 var r: i64 = 0
39 var i: i64 = 0
40 while i < n { r = (r << 1) | ((code >> i) & 1); i = i + 1 }
41 return r
42}
43// fixed-Huffman literal/length symbol (0..287), MSB-first (reverse then LSB-write)
44func dfe_sym(out: *u8, st: *i64, s: i64) -> i64 {
45 if s < 144 { dfe_bits(out, st, dfe_rev(0x30 + s, 8), 8); return 0 }
46 if s < 256 { dfe_bits(out, st, dfe_rev(0x190 + (s - 144), 9), 9); return 0 }
47 if s < 280 { dfe_bits(out, st, dfe_rev(s - 256, 7), 7); return 0 }
48 dfe_bits(out, st, dfe_rev(0xC0 + (s - 280), 8), 8)
49 return 0
50}
51func dfe_hash(src: *u8, p: i64) -> i64 {
52 return (((src[p] as i64) << 10) ^ ((src[p + 1] as i64) << 5) ^ (src[p + 2] as i64)) & (DFE_HSIZE - 1)
53}
54func dfe_matchlen(src: *u8, a: i64, b: i64, slen: i64) -> i64 {
55 var l: i64 = 0
56 while l < DFE_MAXMATCH {
57 if b + l >= slen { return l }
58 let sa: *u8 = (src as i64 + a + l) as *u8
59 let sb: *u8 = (src as i64 + b + l) as *u8
60 if sa[0] != sb[0] { return l }
61 l = l + 1
62 }
63 return l
64}
65
66// compress src[0..slen) into out; returns compressed byte length. head/lbase/lext/dbase/dext are caller-mmap'd.
67// bounded-VSZ 2026-07-20: the bit-writer state is munmapped before return (hot-loop callers stay flat).
68func dfe_deflate(src: *u8, slen: i64, out: *u8, head: *i64, lbase: *i64, lext: *i64, dbase: *i64, dext: *i64) -> i64 {
69 let st: *i64 = sys_mmap(64) as *i64
70 st[0] = 0; st[1] = 0; st[2] = 0
71 var i: i64 = 0
72 while i < DFE_HSIZE { head[i] = 0 - 1; i = i + 1 }
73 dfe_bits(out, st, 1, 1) // BFINAL=1
74 dfe_bits(out, st, 1, 2) // BTYPE=01 (fixed Huffman)
75 var pos: i64 = 0
76 while pos < slen {
77 var mlen: i64 = 0
78 var mdist: i64 = 0
79 if pos + DFE_MINMATCH <= slen {
80 let h: i64 = dfe_hash(src, pos)
81 let cand: i64 = head[h]
82 if cand >= 0 { if pos - cand <= DFE_WINDOW {
83 let l: i64 = dfe_matchlen(src, cand, pos, slen)
84 if l >= DFE_MINMATCH { mlen = l; mdist = pos - cand }
85 } }
86 head[h] = pos
87 }
88 if mlen >= DFE_MINMATCH {
89 var li: i64 = 28
90 while lbase[li] > mlen { li = li - 1 }
91 dfe_sym(out, st, 257 + li)
92 if lext[li] > 0 { dfe_bits(out, st, mlen - lbase[li], lext[li]) }
93 var di: i64 = 29
94 while dbase[di] > mdist { di = di - 1 }
95 dfe_bits(out, st, dfe_rev(di, 5), 5) // distance: 5-bit fixed, MSB-first
96 if dext[di] > 0 { dfe_bits(out, st, mdist - dbase[di], dext[di]) }
97 var k: i64 = 1
98 while k < mlen {
99 if pos + k + DFE_MINMATCH <= slen { head[dfe_hash(src, pos + k)] = pos + k }
100 k = k + 1
101 }
102 pos = pos + mlen
103 } else {
104 dfe_sym(out, st, src[pos] as i64)
105 pos = pos + 1
106 }
107 }
108 dfe_sym(out, st, 256) // end of block
109 if st[2] > 0 { out[st[0]] = (st[1] & 0xff) as u8; st[0] = st[0] + 1 }
110 let outn: i64 = st[0]
111 sys_munmap(st as *u8, 64)
112 return outn
113}
114
115// fill fixed length/distance base+extra tables (RFC 1951 3.2.5). lbase/lext: 29 slots; dbase/dext: 30 slots.
116func dfe_fill_tables(lbase: *i64, lext: *i64, dbase: *i64, dext: *i64) -> i64 {
117 lbase[0]=3; lbase[1]=4; lbase[2]=5; lbase[3]=6; lbase[4]=7; lbase[5]=8; lbase[6]=9; lbase[7]=10
118 lbase[8]=11; lbase[9]=13; lbase[10]=15; lbase[11]=17; lbase[12]=19; lbase[13]=23; lbase[14]=27; lbase[15]=31
119 lbase[16]=35; lbase[17]=43; lbase[18]=51; lbase[19]=59; lbase[20]=67; lbase[21]=83; lbase[22]=99; lbase[23]=115
120 lbase[24]=131; lbase[25]=163; lbase[26]=195; lbase[27]=227; lbase[28]=258
121 lext[0]=0; lext[1]=0; lext[2]=0; lext[3]=0; lext[4]=0; lext[5]=0; lext[6]=0; lext[7]=0
122 lext[8]=1; lext[9]=1; lext[10]=1; lext[11]=1; lext[12]=2; lext[13]=2; lext[14]=2; lext[15]=2
123 lext[16]=3; lext[17]=3; lext[18]=3; lext[19]=3; lext[20]=4; lext[21]=4; lext[22]=4; lext[23]=4
124 lext[24]=5; lext[25]=5; lext[26]=5; lext[27]=5; lext[28]=0
125 dbase[0]=1; dbase[1]=2; dbase[2]=3; dbase[3]=4; dbase[4]=5; dbase[5]=7; dbase[6]=9; dbase[7]=13
126 dbase[8]=17; dbase[9]=25; dbase[10]=33; dbase[11]=49; dbase[12]=65; dbase[13]=97; dbase[14]=129; dbase[15]=193
127 dbase[16]=257; dbase[17]=385; dbase[18]=513; dbase[19]=769; dbase[20]=DFE_MAGIC_1025; dbase[21]=DFE_MAGIC_1537; dbase[22]=DFE_MAGIC_2049; dbase[23]=DFE_MAGIC_3073
128 dbase[24]=DFE_MAGIC_4097; dbase[25]=DFE_MAGIC_6145; dbase[26]=DFE_MAGIC_8193; dbase[27]=DFE_MAGIC_12289; dbase[28]=DFE_MAGIC_16385; dbase[29]=DFE_MAGIC_24577
129 dext[0]=0; dext[1]=0; dext[2]=0; dext[3]=0; dext[4]=1; dext[5]=1; dext[6]=2; dext[7]=2
130 dext[8]=3; dext[9]=3; dext[10]=4; dext[11]=4; dext[12]=5; dext[13]=5; dext[14]=6; dext[15]=6
131 dext[16]=7; dext[17]=7; dext[18]=8; dext[19]=8; dext[20]=9; dext[21]=9; dext[22]=10; dext[23]=10
132 dext[24]=11; dext[25]=11; dext[26]=12; dext[27]=12; dext[28]=13; dext[29]=13
133 return 0
134}
135
136// convenience: allocate tables + compress. returns compressed length into out.
137// ⚠CONTRACT: out must be sized >= slen + (slen >> 1) + 64 -- fixed-Huffman EXPANDS high-entropy
138// input (worst case ~1.30x); the old "slen+64" note overflowed on random/binary payloads.
139// bounded-VSZ 2026-07-20: all working tables munmapped (was ~258KB leaked PER CALL -- hot-loop
140// callers like a git pack walk leaked ~0.8MB per request).
141func dfe_compress(src: *u8, slen: i64, out: *u8) -> i64 {
142 let head: *i64 = sys_mmap(DFE_HSIZE * 8) as *i64
143 let lbase: *i64 = sys_mmap(29 * 8) as *i64
144 let lext: *i64 = sys_mmap(29 * 8) as *i64
145 let dbase: *i64 = sys_mmap(30 * 8) as *i64
146 let dext: *i64 = sys_mmap(30 * 8) as *i64
147 dfe_fill_tables(lbase, lext, dbase, dext)
148 let zn: i64 = dfe_deflate(src, slen, out, head, lbase, lext, dbase, dext)
149 sys_munmap(head as *u8, DFE_HSIZE * 8)
150 sys_munmap(lbase as *u8, 29 * 8)
151 sys_munmap(lext as *u8, 29 * 8)
152 sys_munmap(dbase as *u8, 30 * 8)
153 sys_munmap(dext as *u8, 30 * 8)
154 return zn
155}