`nx_gzip_lib.nx` source

↩ module page · 689 lines · 32361 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 {
  let fd: i64 = sys_openat_rd(path)
  if fd < 0 { return 0 - 1 }
  var n: i64 = 0
  var go: i64 = 1
  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 } }
  // A read that stopped because the BUFFER filled is not a completed read. Probe one more byte:
  // if the file still has data, REFUSE (0-2) instead of returning a truncated prefix -- a prefix
  // compresses cleanly into a plausible but WRONG artifact, with no error anywhere. (1785933265)
  if n >= cap {
      let probe: *u8 = sys_mmap(8)
      if sys_read(fd, probe, 1) > 0 { sys_close(fd); return 0 - 2 }
  }
  sys_close(fd)
  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 {
  let fd: i64 = sys_openat_rd(path)
  if fd < 0 { return 0 - 1 }
  let sz: i64 = sys_lseek(fd, 0, 2)
  sys_close(fd)
  return sz
58}
59func gz_write(path: *u8, buf: *u8, n: i64) -> i64 {
  let fd: i64 = sys_openat_wr(path, 420)
  if fd < 0 { return 0 - 1 }
  var w: i64 = 0
  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 } }
  sys_close(fd)
  return 0
66}
67
68func gz_crc32(bytes: *u8, n: i64) -> i64 {
  var crc: i64 = 0xFFFFFFFF
  var i: i64 = 0
  while i < n {
      crc = crc ^ (bytes[i] & 0xff)
      var bit: i64 = 0
      while bit < 8 {
          let lsb: i64 = crc & 1
          let mask: i64 = 0 - lsb
          crc = ((crc >> 1) & 0x7FFFFFFFFFFFFFFF) ^ (mask & 0xEDB88320)
          crc = crc & 0xFFFFFFFF
          bit = bit + 1
      }
      i = i + 1
  }
  return (crc ^ 0xFFFFFFFF) & 0xFFFFFFFF
84}
85
86func gz_rev(v: i64, n: i64) -> i64 {
  var r: i64 = 0
  var i: i64 = 0
  while i < n { r = (r << 1) | ((v >> i) & 1); i = i + 1 }
  return r
91}
92func gz_fixed(sym: i64, out2: *i64) -> i64 {
  if sym <= 143 { out2[0] = 0x30 + sym; out2[1] = 8; return 0 }
  if sym <= 255 { out2[0] = 0x190 + (sym - 144); out2[1] = 9; return 0 }
  if sym <= 279 { out2[0] = sym - 256; out2[1] = 7; return 0 }
  out2[0] = 0xC0 + (sym - 280); out2[1] = 8
  return 0
98}
99func gz_putbits(ob: *u8, bw: *i64, val: i64, nbits: i64) -> i64 {
  var buf: i64 = bw[1] | ((val & ((1 << nbits) - 1)) << bw[2])
  var cnt: i64 = bw[2] + nbits
  while cnt >= 8 { ob[bw[0]] = (buf & 0xff) as u8; bw[0] = bw[0] + 1; buf = buf >> 8; cnt = cnt - 8 }
  bw[1] = buf
  bw[2] = cnt
  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 {
  var i: i64 = 28
  var found: i64 = 0
  while found == 0 { if lb[i] <= length { found = 1 } else { i = i - 1 } }
  out3[0] = 257 + i
  out3[1] = le[i]
  out3[2] = length - lb[i]
  return 0
118}
119func gz_distcode(db: *i64, de: *i64, dist: i64, out3: *i64) -> i64 {
  var i: i64 = 29
  var found: i64 = 0
  while found == 0 { if db[i] <= dist { found = 1 } else { i = i - 1 } }
  out3[0] = i
  out3[1] = de[i]
  out3[2] = dist - db[i]
  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 {
  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
  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
  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
  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
  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
  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
  return 0
138}
139func gz_fill_dist(db: *i64, de: *i64) -> i64 {
  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
  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
  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
  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
  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
  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
  return 0
147}
148
149// ---- DYNAMIC HUFFMAN (BTYPE=10) HELPERS -- 2026-08-29, PF3 --------------------------------------
150// The frequency-to-code-length build existed NOWHERE in this corpus (measured 2026-08-28: the decode
151// side has canonical-from-lengths only, and the one heap organ is a different dialect). Written here
152// once, in this file's own plain-i64 dialect, because this is the ONE gzip DEFLATE source since the
153// 2026-08-28 merge. O(k^2) two-smallest selection: k<=286 so ~82k compares per build -- microseconds.
154// NO VARIABLE SHIFTS anywhere in these helpers: gz_dh_pow2 multiplies instead, because a variable
155// shift amount is a construct this file has never used and a silent miscompile in the organ that
156// compresses every response is the worst available failure class.
157func gz_dh_pow2(k: i64) -> i64 { var r: i64 = 1; var j: i64 = 0; while j < k { r = r * 2; j = j + 1 } return r }
158
159// fixed-Huffman litlen code lengths (RFC 1951 3.2.6), for the fixed-vs-dynamic cost comparison
160func gz_dh_fixlen(s: i64) -> i64 {
  if s < 144 { return 8 }
  if s < 256 { return 9 }
  if s < 280 { return 7 }
  return 8
165}
166
167// RFC 1951 3.2.7 code-length-alphabet permutation -- copied as VALUES from the spec (the decode side
168// carries the same table in _deflate_cl_order, a different dialect; values copied, code not imported)
169func gz_dh_fill_clperm(p: *i64) -> i64 {
  p[0]=16; p[1]=17; p[2]=18; p[3]=0; p[4]=8; p[5]=7; p[6]=9; p[7]=6; p[8]=10; p[9]=5
  p[10]=11; p[11]=4; p[12]=12; p[13]=3; p[14]=13; p[15]=2; p[16]=14; p[17]=1; p[18]=15
  return 0
173}
174
175// code LENGTHS (<= maxbits) from frequencies over n symbols. lens must arrive zeroed; returns the
176// count of used symbols. Length limiting is zlib's own gen_bitlen repair, transcribed faithfully:
177// clamp the histogram tail onto maxbits as counted overflow, then repeatedly move one node up from
178// the deepest occupied sub-max level -- the accounting REARRANGES A COMPLETE TREE, so the result is
179// complete by construction, never merely under the Kraft cap. An under-full litlen or code-length
180// tree is REJECTED by zlib-family inflaters, so "<= cap" is not good enough here and a home-grown
181// deepen-until-it-fits loop (which can overshoot below the cap) was deliberately not used.
182func gz_dh_lens(freq: *i64, n: i64, maxbits: i64, lens: *i64) -> i64 {
  let wf: *i64 = sys_mmap(n * 16 + 64) as *i64
  let wp: *i64 = sys_mmap(n * 16 + 64) as *i64
  let wa: *i64 = sys_mmap(n * 16 + 64) as *i64
  var used: i64 = 0
  var i: i64 = 0
  while i < n {
      wp[i] = 0 - 1
      if freq[i] > 0 { wf[i] = freq[i]; wa[i] = 1; used = used + 1 } else { wf[i] = 0; wa[i] = 0 }
      i = i + 1
  }
  if used == 0 { return 0 }
  if used == 1 {
      i = 0
      while i < n { if wa[i] == 1 { lens[i] = 1 } i = i + 1 }
      return 1
  }
  var tot: i64 = n
  var live: i64 = used
  while live > 1 {
      var a: i64 = 0 - 1
      var b: i64 = 0 - 1
      i = 0
      while i < tot {
          if wa[i] == 1 {
              if a < 0 { a = i } else {
                  if wf[i] < wf[a] { b = a; a = i } else {
                      if b < 0 { b = i } else { if wf[i] < wf[b] { b = i } }
                  }
              }
          }
          i = i + 1
      }
      wa[a] = 0; wa[b] = 0
      wf[tot] = wf[a] + wf[b]
      wp[a] = tot; wp[b] = tot
      wp[tot] = 0 - 1
      wa[tot] = 1
      tot = tot + 1
      live = live - 1
  }
  // raw depth histogram. Raw depth of any leaf < used <= 286, so 300 slots cover it; the histogram
  // always has an entry at depth <= log2(used) < maxbits, so the repair's downward scan terminates.
  let blc: *i64 = sys_mmap(300 * 8 + 64) as *i64
  var z: i64 = 0
  while z < 300 { blc[z] = 0; z = z + 1 }
  i = 0
  while i < n {
      if freq[i] > 0 {
          var d: i64 = 0
          var pp: i64 = wp[i]
          while pp >= 0 { d = d + 1; pp = wp[pp] }
          blc[d] = blc[d] + 1
      }
      i = i + 1
  }
  // ⚠CORRECTED 2026-08-29, SAME DAY, CAUGHT BY THE ROUND-TRIP ORACLE BEFORE ANY PROMOTE. The first
  // draft counted over-deep LEAVES and ran zlib's repair loop overflow/2 times -- but zlib's own
  // gen_bitlen counts over-deep NODES INCLUDING INTERNAL ONES (its overflow++ fires before the
  // leaf test), so on /world/beach the litlen code came out OVER-SUBSCRIBED BY EXACTLY ONE KRAFT
  // UNIT (32769 of 32768) and zlib-strict inflaters refused the block as an invalid literal/lengths
  // set. A COUNT COPIED WITHOUT ITS COUNTING RULE IS A DIFFERENT ALGORITHM WEARING THE SAME NAME.
  // The fix loops on the MEASURED INVARIANT instead of any counter: clamping only ever leaves the
  // Kraft sum AT or ABOVE the cap, each move is worth exactly -1 unit, so repair-until-equal is
  // exact completeness by construction -- and the shallow-entry scan below always terminates while
  // kraft exceeds the cap, because 286 codes all at maxbits could only sum to 286 of 32768.
  var b2: i64 = maxbits + 1
  while b2 < 300 { blc[maxbits] = blc[maxbits] + blc[b2]; blc[b2] = 0; b2 = b2 + 1 }
  let cap: i64 = gz_dh_pow2(maxbits)
  var kraft: i64 = 0
  var bk: i64 = 1
  while bk <= maxbits { kraft = kraft + blc[bk] * gz_dh_pow2(maxbits - bk); bk = bk + 1 }
  while kraft > cap {
      var bits: i64 = maxbits - 1
      while blc[bits] == 0 { bits = bits - 1 }
      blc[bits] = blc[bits] - 1
      blc[bits + 1] = blc[bits + 1] + 2
      blc[maxbits] = blc[maxbits] - 1
      kraft = kraft - 1
  }
  // assign: least-frequent symbols take the longest codes. Selection sort, freq ascending with
  // index-order ties -- deterministic, so the same input always emits the same bytes.
  let ord: *i64 = sys_mmap(n * 8 + 64) as *i64
  var m: i64 = 0
  i = 0
  while i < n { if freq[i] > 0 { ord[m] = i; m = m + 1 } i = i + 1 }
  i = 0
  while i < m {
      var sm: i64 = i
      var j: i64 = i + 1
      while j < m { if wf[ord[j]] < wf[ord[sm]] { sm = j } j = j + 1 }
      let tmp: i64 = ord[i]; ord[i] = ord[sm]; ord[sm] = tmp
      i = i + 1
  }
  var oi: i64 = 0
  var bb: i64 = maxbits
  while bb >= 1 {
      var cc: i64 = blc[bb]
      while cc > 0 { lens[ord[oi]] = bb; oi = oi + 1; cc = cc - 1 }
      bb = bb - 1
  }
  return used
284}
285
286// canonical codes from lengths (RFC 1951 3.2.2); MSB-first values, emitted through gz_puthuff
287func gz_dh_canon(lens: *i64, n: i64, maxbits: i64, codes: *i64) -> i64 {
  let blc: *i64 = sys_mmap((maxbits + 2) * 8 + 16) as *i64
  let nxt: *i64 = sys_mmap((maxbits + 2) * 8 + 16) as *i64
  var b: i64 = 0
  while b <= maxbits { blc[b] = 0; nxt[b] = 0; b = b + 1 }
  var i: i64 = 0
  while i < n { if lens[i] > 0 { blc[lens[i]] = blc[lens[i]] + 1 } i = i + 1 }
  var code: i64 = 0
  blc[0] = 0
  b = 1
  while b <= maxbits { code = (code + blc[b - 1]) * 2; nxt[b] = code; b = b + 1 }
  i = 0
  while i < n { if lens[i] > 0 { codes[i] = nxt[lens[i]]; nxt[lens[i]] = nxt[lens[i]] + 1 } i = i + 1 }
  return 0
301}
302
303// RLE the concatenated length sequence (RFC 1951 3.2.7: 16 repeats the PREVIOUS code 3-6 times,
304// 17/18 are zero runs 3-10/11-138). Fills (sym, extraval) pairs, bumps clfreq, accumulates the
305// extra-bit total into xbits[0]. Returns the pair count. Built ONCE and used for both the cost
306// count and the emit, so the two cannot disagree about what the header contains.
307func gz_dh_clrle(seq: *i64, total: i64, outsym: *i64, outext: *i64, clfreq: *i64, xbits: *i64) -> i64 {
  var m: i64 = 0
  var i: i64 = 0
  while i < total {
      let v: i64 = seq[i]
      var run: i64 = 1
      var scan: i64 = 1
      while scan == 1 {
          if i + run < total { if seq[i + run] == v { run = run + 1 } else { scan = 0 } } else { scan = 0 }
      }
      let adv: i64 = run
      if v == 0 {
          var z: i64 = run
          while z > 0 {
              if z >= 11 {
                  var r18: i64 = z
                  if r18 > 138 { r18 = 138 }
                  outsym[m] = 18; outext[m] = r18 - 11; clfreq[18] = clfreq[18] + 1; xbits[0] = xbits[0] + 7
                  m = m + 1; z = z - r18
              } else {
                  if z >= 3 {
                      outsym[m] = 17; outext[m] = z - 3; clfreq[17] = clfreq[17] + 1; xbits[0] = xbits[0] + 3
                      m = m + 1; z = 0
                  } else {
                      var k: i64 = 0
                      while k < z { outsym[m] = 0; outext[m] = 0; clfreq[0] = clfreq[0] + 1; m = m + 1; k = k + 1 }
                      z = 0
                  }
              }
          }
      } else {
          outsym[m] = v; outext[m] = 0; clfreq[v] = clfreq[v] + 1; m = m + 1
          var rem: i64 = run - 1
          while rem > 0 {
              if rem >= 3 {
                  var r16: i64 = rem
                  if r16 > 6 { r16 = 6 }
                  outsym[m] = 16; outext[m] = r16 - 3; clfreq[16] = clfreq[16] + 1; xbits[0] = xbits[0] + 2
                  m = m + 1; rem = rem - r16
              } else {
                  var k2: i64 = 0
                  while k2 < rem { outsym[m] = v; outext[m] = 0; clfreq[v] = clfreq[v] + 1; m = m + 1; k2 = k2 + 1 }
                  rem = 0
              }
          }
      }
      i = i + adv
  }
  return m
356}
357
358func gz_deflate(src: *u8, n: i64, mode: i64, ob: *u8, bw: *i64) -> i64 {
  if mode == 0 {
      gz_putbits(ob, bw, 1, 1)
      gz_putbits(ob, bw, 0, 2)
      gz_flushbits(ob, bw)
      let len: i64 = n & 0xffff
      ob[bw[0]] = (len & 0xff) as u8; bw[0] = bw[0] + 1
      ob[bw[0]] = ((len >> 8) & 0xff) as u8; bw[0] = bw[0] + 1
      let nlen: i64 = (len ^ 0xffff) & 0xffff
      ob[bw[0]] = (nlen & 0xff) as u8; bw[0] = bw[0] + 1
      ob[bw[0]] = ((nlen >> 8) & 0xff) as u8; bw[0] = bw[0] + 1
      var k: i64 = 0
      while k < len { ob[bw[0]] = src[k]; bw[0] = bw[0] + 1; k = k + 1 }
      return 0
  }
  let lb: *i64 = sys_mmap(29 * 8 + 8) as *i64
  let le: *i64 = sys_mmap(29 * 8 + 8) as *i64
  let db: *i64 = sys_mmap(30 * 8 + 8) as *i64
  let de: *i64 = sys_mmap(30 * 8 + 8) as *i64
  gz_fill_len(lb, le)
  gz_fill_dist(db, de)
  let head: *i64 = sys_mmap(GZ_HSIZE * 8 + 8) as *i64
  var hi: i64 = 0
  while hi < GZ_HSIZE { head[hi] = 0 - 1; hi = hi + 1 }
  let prev: *i64 = sys_mmap(n * 8 + 8) as *i64
  let c2: *i64 = sys_mmap(32) as *i64
  let e3: *i64 = sys_mmap(32) as *i64
  // ★LAZY MATCHING (2026-08-28), proven byte-identical on promote day, UNCHANGED below -- and
  // ★DYNAMIC HUFFMAN (BTYPE=10), 2026-08-29, PF3. The encoder is now TWO-PASS: the same lazy
  // matcher appends TOKENS instead of bits, frequencies drive per-block optimal code lengths
  // (gz_dh_lens, zlib gen_bitlen repair), and the block is emitted with whichever of FIXED and
  // DYNAMIC MEASURES smaller -- an arithmetic choice per input, never a mode flag, so no input can
  // regress against the old encoder beyond the few header bits the comparison itself accounts.
  // Extra bits (length/distance) cost the same under both codes and cancel out of the comparison.
  // Token stride 6: lsym, lext_n, lext_v, dsym (-1 = literal), dext_n, dext_v. The buffer derives
  // from input size and mmap faults pages on demand -- address space, not resident memory (the
  // buffer-cap law); the incumbent already mmaps n*8 for prev per call, this is the same class.
  let toks: *i64 = sys_mmap(n * 48 + 4096) as *i64
  var nt: i64 = 0
  let lfreq: *i64 = sys_mmap(288 * 8 + 16) as *i64
  let dfreq: *i64 = sys_mmap(32 * 8 + 16) as *i64
  var zi: i64 = 0
  while zi < 288 { lfreq[zi] = 0; zi = zi + 1 }
  zi = 0
  while zi < 32 { dfreq[zi] = 0; zi = zi + 1 }
  var pend_len: i64 = 0
  var pend_dist: i64 = 0
  var pend_pos: i64 = 0
  var i: i64 = 0
  while i < n {
      var best_len: i64 = 0
      var best_dist: i64 = 0
      if i + 2 < n {
          let h: i64 = gz_hash3(src[i], src[i+1], src[i+2])
          var cand: i64 = head[h]
          prev[i] = cand
          head[h] = i
          var depth: i64 = 0
          var scanning: i64 = 1
          while scanning == 1 {
              if cand < 0 { scanning = 0 } else {
                  if i - cand > GZ_WINDOW { scanning = 0 } else {
                      if depth >= GZ_MAXCHAIN { scanning = 0 } else {
                          var maxl: i64 = n - i
                          if maxl > GZ_MAXMATCH { maxl = GZ_MAXMATCH }
                          var l: i64 = 0
                          var mgo: i64 = 1
                          while mgo == 1 { if l < maxl { if src[i+l] == src[cand+l] { l = l + 1 } else { mgo = 0 } } else { mgo = 0 } }
                          if l > best_len { best_len = l; best_dist = i - cand }
                          cand = prev[cand]
                          depth = depth + 1
                      }
                  }
              }
          }
      }
      if pend_len >= GZ_MINMATCH {
          if best_len > pend_len {
              // the match one byte later is STRICTLY longer: spend src[pend_pos] as a literal
              // and carry the better match forward. This is the whole of lazy matching.
              let ls0: i64 = src[pend_pos] & 0xff
              toks[nt*6] = ls0; toks[nt*6+1] = 0; toks[nt*6+2] = 0; toks[nt*6+3] = 0 - 1; toks[nt*6+4] = 0; toks[nt*6+5] = 0
              lfreq[ls0] = lfreq[ls0] + 1
              nt = nt + 1
              pend_len = best_len; pend_dist = best_dist; pend_pos = i
              i = i + 1
          } else {
              gz_lencode(lb, le, pend_len, e3)
              toks[nt*6] = e3[0]; toks[nt*6+1] = e3[1]; toks[nt*6+2] = e3[2]
              lfreq[e3[0]] = lfreq[e3[0]] + 1
              gz_distcode(db, de, pend_dist, e3)
              toks[nt*6+3] = e3[0]; toks[nt*6+4] = e3[1]; toks[nt*6+5] = e3[2]
              dfreq[e3[0]] = dfreq[e3[0]] + 1
              nt = nt + 1
              // ⚠EVERY POSITION IS INSERTED INTO THE HASH CHAIN EXACTLY ONCE, BY THE SEARCH ABOVE.
              // pend_pos and i (== pend_pos+1) are already in, so only the match INTERIOR is added
              // here. Re-inserting i would set prev[i]=i -- a self-loop whose first candidate gives
              // dist=0, an ILLEGAL DEFLATE distance that gunzip rejects. That is why the pending
              // match is CARRIED rather than recomputed at i+1.
              var k: i64 = i + 1
              let endm: i64 = pend_pos + pend_len
              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 }
              i = pend_pos + pend_len
              pend_len = 0
          }
      } else {
          if best_len >= GZ_MINMATCH {
              pend_len = best_len; pend_dist = best_dist; pend_pos = i
              i = i + 1
          } else {
              let ls1: i64 = src[i] & 0xff
              toks[nt*6] = ls1; toks[nt*6+1] = 0; toks[nt*6+2] = 0; toks[nt*6+3] = 0 - 1; toks[nt*6+4] = 0; toks[nt*6+5] = 0
              lfreq[ls1] = lfreq[ls1] + 1
              nt = nt + 1
              i = i + 1
          }
      }
  }
  // A match still HELD at end-of-input must still be emitted or its bytes vanish silently. On this
  // matcher the case is unreachable (a pending match forces i=pend_pos+1<n, and a match needs
  // i+2<n), but silent data loss is exactly what the gzip trailer CRC32 exists to catch, so the
  // branch is written rather than argued away.
  if pend_len >= GZ_MINMATCH {
      gz_lencode(lb, le, pend_len, e3)
      toks[nt*6] = e3[0]; toks[nt*6+1] = e3[1]; toks[nt*6+2] = e3[2]
      lfreq[e3[0]] = lfreq[e3[0]] + 1
      gz_distcode(db, de, pend_dist, e3)
      toks[nt*6+3] = e3[0]; toks[nt*6+4] = e3[1]; toks[nt*6+5] = e3[2]
      dfreq[e3[0]] = dfreq[e3[0]] + 1
      nt = nt + 1
  }
  // ---- code builds: EOB counted, per-block optimal lengths, canonical codes ----
  lfreq[256] = lfreq[256] + 1
  let llen: *i64 = sys_mmap(288 * 8 + 16) as *i64
  let lcode: *i64 = sys_mmap(288 * 8 + 16) as *i64
  let dlen: *i64 = sys_mmap(32 * 8 + 16) as *i64
  let dcode: *i64 = sys_mmap(32 * 8 + 16) as *i64
  zi = 0
  while zi < 288 { llen[zi] = 0; lcode[zi] = 0; zi = zi + 1 }
  zi = 0
  while zi < 32 { dlen[zi] = 0; dcode[zi] = 0; zi = zi + 1 }
  gz_dh_lens(lfreq, 286, 15, llen)
  let dused: i64 = gz_dh_lens(dfreq, 30, 15, dlen)
  // an under-full DISTANCE tree decodes differently across implementations, so COMPLETE it: two
  // length-1 codes are a complete tree every decoder reads, and the unused one is never sent.
  // (zlib emits exactly this shape for the same reason.)
  if dused == 0 { dlen[0] = 1; dlen[1] = 1 }
  if dused == 1 { if dlen[0] > 0 { dlen[1] = 1 } else { dlen[0] = 1 } }
  gz_dh_canon(llen, 286, 15, lcode)
  gz_dh_canon(dlen, 30, 15, dcode)
  var hlit: i64 = 286
  var sh: i64 = 1
  while sh == 1 { if hlit > 257 { if llen[hlit - 1] == 0 { hlit = hlit - 1 } else { sh = 0 } } else { sh = 0 } }
  var hdist: i64 = 30
  sh = 1
  while sh == 1 { if hdist > 1 { if dlen[hdist - 1] == 0 { hdist = hdist - 1 } else { sh = 0 } } else { sh = 0 } }
  // ---- code-length header: one RLE list serves both the cost count and the emit ----
  let seq: *i64 = sys_mmap(320 * 8 + 16) as *i64
  zi = 0
  while zi < hlit { seq[zi] = llen[zi]; zi = zi + 1 }
  var zj: i64 = 0
  while zj < hdist { seq[hlit + zj] = dlen[zj]; zj = zj + 1 }
  let clsym: *i64 = sys_mmap(320 * 8 + 16) as *i64
  let clext: *i64 = sys_mmap(320 * 8 + 16) as *i64
  let clfreq: *i64 = sys_mmap(19 * 8 + 16) as *i64
  let clx: *i64 = sys_mmap(16) as *i64
  zi = 0
  while zi < 19 { clfreq[zi] = 0; zi = zi + 1 }
  clx[0] = 0
  let ncl: i64 = gz_dh_clrle(seq, hlit + hdist, clsym, clext, clfreq, clx)
  let cllen: *i64 = sys_mmap(19 * 8 + 16) as *i64
  let clcode: *i64 = sys_mmap(19 * 8 + 16) as *i64
  zi = 0
  while zi < 19 { cllen[zi] = 0; clcode[zi] = 0; zi = zi + 1 }
  gz_dh_lens(clfreq, 19, 7, cllen)
  gz_dh_canon(cllen, 19, 7, clcode)
  let perm: *i64 = sys_mmap(19 * 8 + 16) as *i64
  gz_dh_fill_clperm(perm)
  var hclen: i64 = 19
  sh = 1
  while sh == 1 { if hclen > 4 { if cllen[perm[hclen - 1]] == 0 { hclen = hclen - 1 } else { sh = 0 } } else { sh = 0 } }
  // ---- MEASURED cost of everything that differs between the two encodings (extras cancel) ----
  var fixcost: i64 = 0
  zi = 0
  while zi < 286 { if lfreq[zi] > 0 { fixcost = fixcost + lfreq[zi] * gz_dh_fixlen(zi) } zi = zi + 1 }
  zi = 0
  while zi < 30 { if dfreq[zi] > 0 { fixcost = fixcost + dfreq[zi] * 5 } zi = zi + 1 }
  var dyncost: i64 = 14 + hclen * 3 + clx[0]
  zi = 0
  while zi < ncl { dyncost = dyncost + cllen[clsym[zi]]; zi = zi + 1 }
  zi = 0
  while zi < 286 { if lfreq[zi] > 0 { dyncost = dyncost + lfreq[zi] * llen[zi] } zi = zi + 1 }
  zi = 0
  while zi < 30 { if dfreq[zi] > 0 { dyncost = dyncost + dfreq[zi] * dlen[zi] } zi = zi + 1 }
  // ---- emit: the smaller encoding wins; the fixed path reproduces the old encoder exactly ----
  gz_putbits(ob, bw, 1, 1)
  if dyncost < fixcost {
      gz_putbits(ob, bw, 2, 2)
      gz_putbits(ob, bw, hlit - 257, 5)
      gz_putbits(ob, bw, hdist - 1, 5)
      gz_putbits(ob, bw, hclen - 4, 4)
      zi = 0
      while zi < hclen { gz_putbits(ob, bw, cllen[perm[zi]], 3); zi = zi + 1 }
      zi = 0
      while zi < ncl {
          let cs: i64 = clsym[zi]
          gz_puthuff(ob, bw, clcode[cs], cllen[cs])
          if cs == 16 { gz_putbits(ob, bw, clext[zi], 2) }
          if cs == 17 { gz_putbits(ob, bw, clext[zi], 3) }
          if cs == 18 { gz_putbits(ob, bw, clext[zi], 7) }
          zi = zi + 1
      }
      var t: i64 = 0
      while t < nt {
          let s: i64 = toks[t*6]
          gz_puthuff(ob, bw, lcode[s], llen[s])
          if toks[t*6+1] > 0 { gz_putbits(ob, bw, toks[t*6+2], toks[t*6+1]) }
          let dsy: i64 = toks[t*6+3]
          if dsy >= 0 {
              gz_puthuff(ob, bw, dcode[dsy], dlen[dsy])
              if toks[t*6+4] > 0 { gz_putbits(ob, bw, toks[t*6+5], toks[t*6+4]) }
          }
          t = t + 1
      }
      gz_puthuff(ob, bw, lcode[256], llen[256])
  } else {
      gz_putbits(ob, bw, 1, 2)
      var t2: i64 = 0
      while t2 < nt {
          let s2: i64 = toks[t2*6]
          gz_fixed(s2, c2)
          gz_puthuff(ob, bw, c2[0], c2[1])
          if toks[t2*6+1] > 0 { gz_putbits(ob, bw, toks[t2*6+2], toks[t2*6+1]) }
          let dsy2: i64 = toks[t2*6+3]
          if dsy2 >= 0 {
              gz_puthuff(ob, bw, dsy2, 5)
              if toks[t2*6+4] > 0 { gz_putbits(ob, bw, toks[t2*6+5], toks[t2*6+4]) }
          }
          t2 = t2 + 1
      }
      gz_fixed(256, c2)
      gz_puthuff(ob, bw, c2[0], c2[1])
  }
  gz_flushbits(ob, bw)
  return 0
603}
604
605func gz_compress(src: *u8, n: i64, mode: i64, ob: *u8) -> i64 {
  ob[0] = 0x1f as u8
  ob[1] = 0x8b as u8
  ob[2] = 0x08 as u8
  ob[3] = 0x00 as u8
  ob[4] = 0 as u8; ob[5] = 0 as u8; ob[6] = 0 as u8; ob[7] = 0 as u8
  ob[8] = 0x00 as u8
  ob[9] = 0xff as u8
  let bw: *i64 = sys_mmap(32) as *i64
  bw[0] = 10
  bw[1] = 0
  bw[2] = 0
  gz_deflate(src, n, mode, ob, bw)
  var o: i64 = bw[0]
  let crc: i64 = gz_crc32(src, n)
  ob[o] = (crc & 0xff) as u8; o = o + 1
  ob[o] = ((crc >> 8) & 0xff) as u8; o = o + 1
  ob[o] = ((crc >> 16) & 0xff) as u8; o = o + 1
  ob[o] = ((crc >> 24) & 0xff) as u8; o = o + 1
  let isize: i64 = n & 0xffffffff
  ob[o] = (isize & 0xff) as u8; o = o + 1
  ob[o] = ((isize >> 8) & 0xff) as u8; o = o + 1
  ob[o] = ((isize >> 16) & 0xff) as u8; o = o + 1
  ob[o] = ((isize >> 24) & 0xff) as u8; o = o + 1
  return o
630}
631
632// RETIRED CLI ENTRY (2026-08-08). This file is the IMPORTABLE half of nx_gzip: NishiLang cannot
633// import a module that defines main(), which is the only reason the estate's own RFC-1951 DEFLATE
634// compressor could not be wired into the web server -- nx_gzip.nx's own header calls compression
635// "the #1 remaining HOSTING SOTA gap" while the code to close it already existed and shipped as a
636// CLI. Renaming main() here (rather than deleting the body) keeps this file byte-comparable to
637// nx_gzip.nx so the two can be diffed for drift until nx_gzip.nx is collapsed onto this lib.
638// OWED, DECLARED, NOT HIDDEN: this is currently a SECOND COPY of the deflate implementation, which
639// is the estate's duplicate-source defect. nx_gzip.nx MUST be reduced to `import nx_gzip_lib.nx`
640// + main(), and the correctness oracle (standard gunzip byte-identity) re-run, before this is
641// considered done. Two copies of one ruler is exactly the shape this codebase forbids.
642func gzlib_retired_cli_main(argc: i64, argv: *i64) -> i64 {
  if argc < 2 { gz_w("usage: nx_gzip <infile> <outfile> [mode 0|2] | selftest\n" as *u8); sys_exit(2); return 2 }
  let v: *u8 = argv[1] as *u8
  if v[0] == (115 as u8) { if v[1] == (101 as u8) {
      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
      var mn: i64 = 0
      while msg[mn] != (0 as u8) { mn = mn + 1 }
      let ob: *u8 = sys_mmap(mn * 2 + GZ_MAGIC_4096)
      let olen: i64 = gz_compress(msg, mn, 2, ob)
      gz_write("/tmp/nxgzip_selftest.gz" as *u8, ob, olen)
      gz_w("NX-GZIP selftest in=" as *u8)
      gz_wn(mn)
      gz_w(" out=" as *u8)
      gz_wn(olen)
      gz_w(" -> /tmp/nxgzip_selftest.gz (verify: gunzip -c reproduces input)\n" as *u8)
      sys_exit(0)
      return 0
  } }
  if argc < 3 { gz_w("usage: nx_gzip <infile> <outfile> [mode]\n" as *u8); sys_exit(2); return 2 }
  let inpath: *u8 = argv[1] as *u8
  let outpath: *u8 = argv[2] as *u8
  var mode: i64 = 2
  if argc >= 4 { let ms: *u8 = argv[3] as *u8; if ms[0] == (48 as u8) { mode = 0 } }
  let fsz: i64 = gz_filesize(inpath)
  if fsz < 0 { gz_w("NX-GZIP FAIL cannot read infile\n" as *u8); sys_exit(3); return 3 }
  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 }
  let sb: *u8 = sys_mmap(fsz + GZ_MAGIC_4096)
  let n: i64 = gz_read(inpath, sb, fsz)
  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 }
  if n < 0 { gz_w("NX-GZIP FAIL cannot read infile\n" as *u8); sys_exit(3); return 3 }
  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 }
  let ob: *u8 = sys_mmap(n * 2 + GZ_MAGIC_4096)
  let olen: i64 = gz_compress(sb, n, mode, ob)
  if gz_write(outpath, ob, olen) != 0 { gz_w("NX-GZIP FAIL cannot write outfile\n" as *u8); sys_exit(3); return 3 }
  gz_w("NX-GZIP ok in=" as *u8)
  gz_wn(n)
  gz_w(" out=" as *u8)
  gz_wn(olen)
  gz_w(" mode=" as *u8)
  gz_wn(mode)
  var ratio: i64 = 0
  if n > 0 { ratio = (olen * 100) / n }
  gz_w(" ratio_pct=" as *u8)
  gz_wn(ratio)
  gz_w("\n" as *u8)
  sys_exit(0)
  return 0
689}
nx_gzip_lib.nx source

`nx_gzip_lib.nx` source
