nx_deflate_enc_capacity_t278.nx source
↩ module page · 164 lines · 8173 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_try(64) as *i64
70 if (st as i64)<=0 {return 0-1}
71 st[0] = 0; st[1] = 0; st[2] = 0
72 var i: i64 = 0
73 while i < DFE_HSIZE { head[i] = 0 - 1; i = i + 1 }
74 dfe_bits(out, st, 1, 1) // BFINAL=1
75 dfe_bits(out, st, 1, 2) // BTYPE=01 (fixed Huffman)
76 var pos: i64 = 0
77 while pos < slen {
78 var mlen: i64 = 0
79 var mdist: i64 = 0
80 if pos + DFE_MINMATCH <= slen {
81 let h: i64 = dfe_hash(src, pos)
82 let cand: i64 = head[h]
83 if cand >= 0 { if pos - cand <= DFE_WINDOW {
84 let l: i64 = dfe_matchlen(src, cand, pos, slen)
85 if l >= DFE_MINMATCH { mlen = l; mdist = pos - cand }
86 } }
87 head[h] = pos
88 }
89 if mlen >= DFE_MINMATCH {
90 var li: i64 = 28
91 while lbase[li] > mlen { li = li - 1 }
92 dfe_sym(out, st, 257 + li)
93 if lext[li] > 0 { dfe_bits(out, st, mlen - lbase[li], lext[li]) }
94 var di: i64 = 29
95 while dbase[di] > mdist { di = di - 1 }
96 dfe_bits(out, st, dfe_rev(di, 5), 5) // distance: 5-bit fixed, MSB-first
97 if dext[di] > 0 { dfe_bits(out, st, mdist - dbase[di], dext[di]) }
98 var k: i64 = 1
99 while k < mlen {
100 if pos + k + DFE_MINMATCH <= slen { head[dfe_hash(src, pos + k)] = pos + k }
101 k = k + 1
102 }
103 pos = pos + mlen
104 } else {
105 dfe_sym(out, st, src[pos] as i64)
106 pos = pos + 1
107 }
108 }
109 dfe_sym(out, st, 256) // end of block
110 if st[2] > 0 { out[st[0]] = (st[1] & 0xff) as u8; st[0] = st[0] + 1 }
111 let outn: i64 = st[0]
112 sys_munmap_direct(st as *u8, 64)
113 return outn
114}
115
116// fill fixed length/distance base+extra tables (RFC 1951 3.2.5). lbase/lext: 29 slots; dbase/dext: 30 slots.
117func dfe_fill_tables(lbase: *i64, lext: *i64, dbase: *i64, dext: *i64) -> i64 {
118 lbase[0]=3; lbase[1]=4; lbase[2]=5; lbase[3]=6; lbase[4]=7; lbase[5]=8; lbase[6]=9; lbase[7]=10
119 lbase[8]=11; lbase[9]=13; lbase[10]=15; lbase[11]=17; lbase[12]=19; lbase[13]=23; lbase[14]=27; lbase[15]=31
120 lbase[16]=35; lbase[17]=43; lbase[18]=51; lbase[19]=59; lbase[20]=67; lbase[21]=83; lbase[22]=99; lbase[23]=115
121 lbase[24]=131; lbase[25]=163; lbase[26]=195; lbase[27]=227; lbase[28]=258
122 lext[0]=0; lext[1]=0; lext[2]=0; lext[3]=0; lext[4]=0; lext[5]=0; lext[6]=0; lext[7]=0
123 lext[8]=1; lext[9]=1; lext[10]=1; lext[11]=1; lext[12]=2; lext[13]=2; lext[14]=2; lext[15]=2
124 lext[16]=3; lext[17]=3; lext[18]=3; lext[19]=3; lext[20]=4; lext[21]=4; lext[22]=4; lext[23]=4
125 lext[24]=5; lext[25]=5; lext[26]=5; lext[27]=5; lext[28]=0
126 dbase[0]=1; dbase[1]=2; dbase[2]=3; dbase[3]=4; dbase[4]=5; dbase[5]=7; dbase[6]=9; dbase[7]=13
127 dbase[8]=17; dbase[9]=25; dbase[10]=33; dbase[11]=49; dbase[12]=65; dbase[13]=97; dbase[14]=129; dbase[15]=193
128 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
129 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
130 dext[0]=0; dext[1]=0; dext[2]=0; dext[3]=0; dext[4]=1; dext[5]=1; dext[6]=2; dext[7]=2
131 dext[8]=3; dext[9]=3; dext[10]=4; dext[11]=4; dext[12]=5; dext[13]=5; dext[14]=6; dext[15]=6
132 dext[16]=7; dext[17]=7; dext[18]=8; dext[19]=8; dext[20]=9; dext[21]=9; dext[22]=10; dext[23]=10
133 dext[24]=11; dext[25]=11; dext[26]=12; dext[27]=12; dext[28]=13; dext[29]=13
134 return 0
135}
136
137// convenience: allocate tables + compress. returns compressed length into out.
138// ⚠CONTRACT: out must be sized >= slen + (slen >> 1) + 64 -- fixed-Huffman EXPANDS high-entropy
139// input (worst case ~1.30x); the old "slen+64" note overflowed on random/binary payloads.
140// bounded-VSZ 2026-07-20: all working tables munmapped (was ~258KB leaked PER CALL -- hot-loop
141// callers like a git pack walk leaked ~0.8MB per request).
142func dfe_compress(src: *u8, slen: i64, out: *u8) -> i64 {
143 let head: *i64 = sys_mmap_try(DFE_HSIZE * 8) as *i64
144 let lbase: *i64 = sys_mmap_try(29 * 8) as *i64
145 let lext: *i64 = sys_mmap_try(29 * 8) as *i64
146 let dbase: *i64 = sys_mmap_try(30 * 8) as *i64
147 let dext: *i64 = sys_mmap_try(30 * 8) as *i64
148 if (head as i64)<=0 || (lbase as i64)<=0 || (lext as i64)<=0 || (dbase as i64)<=0 || (dext as i64)<=0 {
149 if (head as i64)>0 {sys_munmap_direct(head as *u8,DFE_HSIZE*8)}
150 if (lbase as i64)>0 {sys_munmap_direct(lbase as *u8,29*8)}
151 if (lext as i64)>0 {sys_munmap_direct(lext as *u8,29*8)}
152 if (dbase as i64)>0 {sys_munmap_direct(dbase as *u8,30*8)}
153 if (dext as i64)>0 {sys_munmap_direct(dext as *u8,30*8)}
154 return 0-1
155 }
156 dfe_fill_tables(lbase, lext, dbase, dext)
157 let zn: i64 = dfe_deflate(src, slen, out, head, lbase, lext, dbase, dext)
158 sys_munmap_direct(head as *u8, DFE_HSIZE * 8)
159 sys_munmap_direct(lbase as *u8, 29 * 8)
160 sys_munmap_direct(lext as *u8, 29 * 8)
161 sys_munmap_direct(dbase as *u8, 30 * 8)
162 sys_munmap_direct(dext as *u8, 30 * 8)
163 return zn
164}