nx_deflate_fixed.nx source

1// nx_deflate_fixed.nx -- SOVEREIGN DEFLATE ENCODER (RFC1951 block type 1, fixed Huffman). 2// rung 1: literals + EOB (bit-packing proven vs our inflate). rung 2 (THIS): LZ77 back-references 3// = actual COMPRESSION. THE codec-exceed unlock (X-CDC-DEFLATE-ENC-001): the team owned inflate 4// (decode) but no compressor; now a sovereign same-corpus PNG/gzip-class baseline is measurable. 5// Self-validating: dfl_decode wraps our _inflate_lib inflate, so (dfl_encode,dfl_decode) is an 6// inverse pair the EARNED pe16 GATE_HARNESS gates (3rd rider) -- no external tool, no fabrication. 7// 8// Bit conventions (match _inflate_lib ibr/ihd EXACTLY): bitstream LSB-first per byte; Huffman codes 9// MSB-first; extra bits LSB-first. Fixed lit/len codes: sym 0-143->8b 0x30+s, 144-255->9b 0x190+, 10// 256-279->7b s-256, 280-287->8b 0xC0+(s-280). Fixed distance: 5-bit code = dist-symbol. Match 11// emission order (per icodes): length-code, length-extra, distance-code, distance-extra. 12// Greedy longest-match over a back-window (brute-force; correctness-first -- hash-chain speed = rung3). 13// LAWS: struct-free, integer-only, flat ifs, no &&/||, <=6 args. license_tier: ORIGINAL 14import "_inflate_lib_authored.nx" 15import "nx_syscalls.nx" 16const K_MAGIC_1025: i64 = 1025 17const K_MAGIC_1537: i64 = 1537 18const K_MAGIC_2049: i64 = 2049 19const K_MAGIC_3073: i64 = 3073 20const K_MAGIC_4097: i64 = 4097 21const K_MAGIC_6145: i64 = 6145 22const K_MAGIC_8193: i64 = 8193 23const K_MAGIC_12289: i64 = 12289 24const K_MAGIC_16385: i64 = 16385 25const K_MAGIC_24577: i64 = 24577 26const K_MAGIC_32768: i64 = 32768 27 28func dfl_putbit(out: *u8, bp: *i64, b: i64) -> i64 { 29 let pos: i64 = bp[0] 30 let byte: i64 = pos >> 3 31 let off: i64 = pos & 7 32 if off == 0 { out[byte] = 0 as u8 } 33 if b != 0 { out[byte] = ((out[byte] as i64) | (1 << off)) as u8 } 34 bp[0] = pos + 1 35 return 0 36} 37// Huffman code: MSB-first (the order ihd reads) 38func dfl_putcode(out: *u8, bp: *i64, code: i64, len: i64) -> i64 { 39 var i: i64 = len - 1 40 while i >= 0 { dfl_putbit(out, bp, (code >> i) & 1); i = i - 1 } 41 return 0 42} 43// extra bits: LSB-first (the order ibr reads) 44func dfl_putbits_lsb(out: *u8, bp: *i64, v: i64, k: i64) -> i64 { 45 var i: i64 = 0 46 while i < k { dfl_putbit(out, bp, (v >> i) & 1); i = i + 1 } 47 return 0 48} 49// length symbol: largest ls in 0..28 with lens[ls] <= L 50func dfl_lensym(L: i64, lens: *i64) -> i64 { 51 var ls: i64 = 28 52 while ls >= 0 { if lens[ls] <= L { return ls } ls = ls - 1 } 53 return 0 54} 55// distance symbol: largest ds in 0..29 with dists[ds] <= D 56func dfl_distsym(D: i64, dists: *i64) -> i64 { 57 var ds: i64 = 29 58 while ds >= 0 { if dists[ds] <= D { return ds } ds = ds - 1 } 59 return 0 60} 61// match length of src[a..] vs src[b..] (a<b=pos), capped at 258, bounded by n 62func dfl_matchlen(src: *u8, n: i64, a: i64, b: i64) -> i64 { 63 var k: i64 = 0 64 while k < 258 { 65 if b + k >= n { return k } 66 if src[a + k] != src[b + k] { return k } 67 k = k + 1 68 } 69 return k 70} 71// greedy longest match at pos within back-window -> res[0]=len res[1]=dist 72func dfl_match(src: *u8, n: i64, pos: i64, window: i64, res: *i64) -> i64 { 73 res[0] = 0 74 res[1] = 0 75 var start: i64 = pos - window 76 if start < 0 { start = 0 } 77 var best: i64 = 0 78 var bdist: i64 = 0 79 var j: i64 = pos - 1 80 while j >= start { 81 let ml: i64 = dfl_matchlen(src, n, j, pos) 82 if ml > best { best = ml; bdist = pos - j } 83 j = j - 1 84 } 85 res[0] = best 86 res[1] = bdist 87 return 0 88} 89 90func dfl_encode(src: *u8, n: i64, out: *u8, outcap: i64) -> i64 { 91 if n < 0 { return 0 - 11 } 92 let maxb: i64 = (3 + 9 * n + 7 + 7) / 8 + 2 93 if maxb > outcap { return 0 - 10 } 94 let lens: *i64 = sys_mmap(8 * 29) as *i64 95 lens[0]=3;lens[1]=4;lens[2]=5;lens[3]=6;lens[4]=7;lens[5]=8;lens[6]=9;lens[7]=10;lens[8]=11;lens[9]=13;lens[10]=15;lens[11]=17;lens[12]=19;lens[13]=23;lens[14]=27;lens[15]=31;lens[16]=35;lens[17]=43;lens[18]=51;lens[19]=59;lens[20]=67;lens[21]=83;lens[22]=99;lens[23]=115;lens[24]=131;lens[25]=163;lens[26]=195;lens[27]=227;lens[28]=258 96 let lext: *i64 = sys_mmap(8 * 29) as *i64 97 lext[0]=0;lext[1]=0;lext[2]=0;lext[3]=0;lext[4]=0;lext[5]=0;lext[6]=0;lext[7]=0;lext[8]=1;lext[9]=1;lext[10]=1;lext[11]=1;lext[12]=2;lext[13]=2;lext[14]=2;lext[15]=2;lext[16]=3;lext[17]=3;lext[18]=3;lext[19]=3;lext[20]=4;lext[21]=4;lext[22]=4;lext[23]=4;lext[24]=5;lext[25]=5;lext[26]=5;lext[27]=5;lext[28]=0 98 let dists: *i64 = sys_mmap(8 * 30) as *i64 99 dists[0]=1;dists[1]=2;dists[2]=3;dists[3]=4;dists[4]=5;dists[5]=7;dists[6]=9;dists[7]=13;dists[8]=17;dists[9]=25;dists[10]=33;dists[11]=49;dists[12]=65;dists[13]=97;dists[14]=129;dists[15]=193;dists[16]=257;dists[17]=385;dists[18]=513;dists[19]=769;dists[20]=K_MAGIC_1025;dists[21]=K_MAGIC_1537;dists[22]=K_MAGIC_2049;dists[23]=K_MAGIC_3073;dists[24]=K_MAGIC_4097;dists[25]=K_MAGIC_6145;dists[26]=K_MAGIC_8193;dists[27]=K_MAGIC_12289;dists[28]=K_MAGIC_16385;dists[29]=K_MAGIC_24577 100 let dext: *i64 = sys_mmap(8 * 30) as *i64 101 dext[0]=0;dext[1]=0;dext[2]=0;dext[3]=0;dext[4]=1;dext[5]=1;dext[6]=2;dext[7]=2;dext[8]=3;dext[9]=3;dext[10]=4;dext[11]=4;dext[12]=5;dext[13]=5;dext[14]=6;dext[15]=6;dext[16]=7;dext[17]=7;dext[18]=8;dext[19]=8;dext[20]=9;dext[21]=9;dext[22]=10;dext[23]=10;dext[24]=11;dext[25]=11;dext[26]=12;dext[27]=12;dext[28]=13;dext[29]=13 102 let bp: *i64 = sys_mmap(16) as *i64 103 bp[0] = 0 104 let res: *i64 = sys_mmap(16) as *i64 105 dfl_putbit(out, bp, 1) // BFINAL 106 dfl_putbit(out, bp, 1) // BTYPE bit0 107 dfl_putbit(out, bp, 0) // BTYPE bit1 -> 01 fixed 108 var i: i64 = 0 109 while i < n { 110 dfl_match(src, n, i, K_MAGIC_32768, res) 111 let mlen: i64 = res[0] 112 let mdist: i64 = res[1] 113 if mlen >= 3 { 114 let ls: i64 = dfl_lensym(mlen, lens) 115 let lsym: i64 = 257 + ls 116 if lsym <= 279 { dfl_putcode(out, bp, lsym - 256, 7) } 117 if lsym > 279 { dfl_putcode(out, bp, 192 + (lsym - 280), 8) } 118 dfl_putbits_lsb(out, bp, mlen - lens[ls], lext[ls]) 119 let ds: i64 = dfl_distsym(mdist, dists) 120 dfl_putcode(out, bp, ds, 5) 121 dfl_putbits_lsb(out, bp, mdist - dists[ds], dext[ds]) 122 i = i + mlen 123 } 124 if mlen < 3 { 125 let b: i64 = src[i] & 0xff 126 if b <= 143 { dfl_putcode(out, bp, 48 + b, 8) } 127 if b > 143 { dfl_putcode(out, bp, 400 + (b - 144), 9) } 128 i = i + 1 129 } 130 } 131 dfl_putcode(out, bp, 0, 7) // EOB 132 return (bp[0] + 7) >> 3 133} 134 135func dfl_decode(enc: *u8, m: i64, out: *u8, outcap: i64) -> i64 { 136 return inflate(enc, m, out) 137}