`nx_inflate.nx` source

↩ module page · 348 lines · 16119 B
1// nx_inflate.nx -- SOVEREIGN DEFLATE DECOMPRESSION (RFC 1951) + gzip (1952) + zlib (1950).
2//
3// WHY THIS EXISTS. Our sovereign HTTPS client could REQUEST gzip and never inflate it. That gap
4// cost us twice: db.bepis.moe and most of the modern web returned bodies we could not read, and
5// worse, the search lane once tokenized COMPRESSED BYTES AS TEXT and poisoned its own index
6// (debt 1785794199) -- a decompressor that is missing does not fail loudly, it corrupts quietly.
7//
8// WHAT WAS ALREADY HERE, AND WHY THIS IS NOT A REBUILD. `_inflate_lib_authored.nx` (builder-
9// generated) already had a structurally correct canonical-Huffman inflate: bit reader, code-length
10// ordering, length/distance tables. That algorithm shape is REUSED here. What it lacked is exactly
11// what makes a decompressor safe to point at the internet:
12//   - NO OUTPUT CAPACITY. `out: *u8` with no bound. A hostile or merely large body writes past the
13//     allocation -- a heap overflow driven by untrusted network input.
14//   - NO DISTANCE VALIDATION. `out[outpos-dist]` with dist > outpos reads BEFORE the buffer.
15//   - NO CONTAINER. Raw DEFLATE only, so HTTP Content-Encoding: gzip was still unreadable.
16//   - NO INTEGRITY CHECK. gzip carries CRC32 + ISIZE precisely so corruption is detectable.
17//   - A DECODE FAILURE READ AS "DONE". An invalid symbol returned -1 and the caller treated it as
18//     end-of-block, so a corrupt stream SILENTLY TRUNCATED instead of erroring -- the same
19//     quiet-corruption shape as the missing decompressor itself.
20//
21// ★★CORRECTION 2026-08-04 (retraction, one day after shipping): THE PREMISE ABOVE WAS INCOMPLETE.
22// The estate ALREADY HELD a complete, capacity-bounded, CRC-verified gzip inflate: nx_gzip_wrap.nx
23// (nx_gzip_inflate, KAT-proven against real python-gzip streams, ~10 consumers incl the browser,
24// nx_page_ingest, nx_research_engine, the CommonCrawl ingest, nx_libdata) plus nx_zlib_wrap.nx for
25// RFC 1950. The corpus-ask before this build surfaced only _inflate_lib_authored.nx and missed both
26// wraps (they are named *_wrap, the search was too narrow). THIS FILE IS THEREFORE A SECOND
27// IMPLEMENTATION of a capability the estate held. The fetch lane was wired to the INCUMBENT
28// (nx_https_get_cli2 -> nx_gzip_inflate/nx_zlib_inflate, 2026-08-04) so this duplicate gains no
29// consumers; its current consumers are nx_gunzip (CLI) + nx_inflate_gate only. What it has that
30// the incumbent lacks: a raw RFC-1951 entry point (no container) + system-gzip cross-impl gate
31// fixtures. CONVERGENCE DEBT 1785854636: fold those into nx_gzip_wrap and retire this file, or
32// demote it to gate-oracle-only. DO NOT ADD NEW CONSUMERS.
33// ★A DECOMPRESSOR IS A PARSER POINTED AT HOSTILE INPUT: every read bounded, every write bounded,
34// every failure LOUD. Truncating quietly is the one behaviour worse than refusing.
35//
36// ERRORS (all distinct, all negative -- a caller can tell WHICH wall fired):
37//   -1 output would exceed capacity      -2 input exhausted / truncated stream
38//   -3 invalid huffman symbol            -4 back-reference distance before buffer start
39//   -5 bad block type (BTYPE=3)          -6 stored-block LEN/NLEN mismatch
40//   -7 not a gzip container              -8 unsupported gzip method/flags
41//   -9 CRC32 mismatch                   -10 ISIZE mismatch
42//  -11 not a zlib container             -12 code-length run overflows the table
43// license_tier: ORIGINAL   No hw writes (Rule 26).
44import "nx_syscalls.nx"
45const INF_MAGIC_1025: i64 = 1025
46const INF_MAGIC_1537: i64 = 1537
47const INF_MAGIC_2049: i64 = 2049
48const INF_MAGIC_3073: i64 = 3073
49const INF_MAGIC_4097: i64 = 4097
50const INF_MAGIC_6145: i64 = 6145
51const INF_MAGIC_8193: i64 = 8193
52const INF_MAGIC_12289: i64 = 12289
53const INF_MAGIC_16385: i64 = 16385
54const INF_MAGIC_24577: i64 = 24577
55
56const INF_CRC_POLY: i64 = 0xEDB88320
57const INF_M32: i64 = 0xFFFFFFFF
58
59// ---- CRC32 (IEEE, reflected) -- gzip's own integrity check -----------------------------------
60func inf_crc32(buf: *u8, n: i64) -> i64 {
  var crc: i64 = INF_M32
  var i: i64 = 0
  while i < n {
      crc = crc ^ ((buf[i] & 0xff) as i64)
      var k: i64 = 0
      while k < 8 {
          let lsb: i64 = crc & 1
          crc = (crc >> 1) & 0x7FFFFFFF
          if lsb == 1 { crc = crc ^ INF_CRC_POLY }
          k = k + 1
      }
      i = i + 1
  }
  return (crc ^ INF_M32) & INF_M32
75}
76
77// ---- bit reader: cur[0] = bit position; cur[1] = sticky "ran off the end" flag ----------------
78func inf_bits(buf: *u8, len: i64, cur: *i64, n: i64) -> i64 {
  var v: i64 = 0
  var g: i64 = 0
  while g < n {
      let bp: i64 = cur[0] >> 3
      if bp >= len { cur[1] = 1; return v }
      let bit: i64 = ((buf[bp] as i64) >> (cur[0] & 7)) & 1
      v = v | (bit << g)
      cur[0] = cur[0] + 1
      g = g + 1
  }
  return v
90}
91
92// canonical huffman: counts per length + symbols in canonical order
93func inf_build(ln: *i64, n: i64, ct: *i64, sy: *i64, off: *i64) -> i64 {
  var i: i64 = 0
  while i <= 15 { ct[i] = 0; i = i + 1 }
  i = 0
  while i < n { ct[ln[i]] = ct[ln[i]] + 1; i = i + 1 }
  ct[0] = 0
  off[1] = 0
  var l: i64 = 1
  while l < 15 { off[l+1] = off[l] + ct[l]; l = l + 1 }
  i = 0
  while i < n {
      if ln[i] != 0 { sy[off[ln[i]]] = i; off[ln[i]] = off[ln[i]] + 1 }
      i = i + 1
  }
  return 0
108}
109func inf_decode(buf: *u8, len: i64, cur: *i64, ct: *i64, sy: *i64) -> i64 {
  var code: i64 = 0
  var first: i64 = 0
  var idx: i64 = 0
  var l: i64 = 1
  while l <= 15 {
      code = code | inf_bits(buf, len, cur, 1)
      if cur[1] == 1 { return 0 - 2 }
      let c: i64 = ct[l]
      if code - first < c { return sy[idx + (code - first)] }
      idx = idx + c
      first = (first + c) << 1
      code = code << 1
      l = l + 1
  }
  return 0 - 3
125}
126
127// ---- the symbol loop. st[0]=outpos. Returns 0 ok or a negative error. ------------------------
128func inf_codes(src: *u8, sl: i64, cur: *i64, out: *u8, outcap: i64, st: *i64,
             lc: *i64, ls: *i64, dc: *i64, ds: *i64,
             lens: *i64, lext: *i64, dists: *i64, dext: *i64) -> i64 {
  var outpos: i64 = st[0]
  var done: i64 = 0
  while done == 0 {
      let sym: i64 = inf_decode(src, sl, cur, lc, ls)
      if sym < 0 { st[0] = outpos; return sym }
      if sym < 256 {
          if outpos >= outcap { st[0] = outpos; return 0 - 1 }
          out[outpos] = sym as u8
          outpos = outpos + 1
      }
      if sym == 256 { done = 1 }
      if sym > 256 {
          let s: i64 = sym - 257
          if s >= 29 { st[0] = outpos; return 0 - 3 }
          let length: i64 = lens[s] + inf_bits(src, sl, cur, lext[s])
          let dsy: i64 = inf_decode(src, sl, cur, dc, ds)
          if dsy < 0 { st[0] = outpos; return dsy }
          if dsy >= 30 { st[0] = outpos; return 0 - 3 }
          let dist: i64 = dists[dsy] + inf_bits(src, sl, cur, dext[dsy])
          if cur[1] == 1 { st[0] = outpos; return 0 - 2 }
          // the back-reference must live INSIDE what we have already produced
          if dist > outpos { st[0] = outpos; return 0 - 4 }
          if dist <= 0 { st[0] = outpos; return 0 - 4 }
          if outpos + length > outcap { st[0] = outpos; return 0 - 1 }
          var ci: i64 = 0
          while ci < length {
              out[outpos] = out[outpos - dist]
              outpos = outpos + 1
              ci = ci + 1
          }
      }
  }
  st[0] = outpos
  return 0
165}
166
167// ---- raw DEFLATE. Returns output length, or a negative error. --------------------------------
168func inf_raw(src: *u8, srclen: i64, out: *u8, outcap: i64) -> i64 {
  let cur: *i64 = sys_mmap(32) as *i64
  cur[0] = 0
  cur[1] = 0
  let st: *i64 = sys_mmap(16) as *i64
  st[0] = 0
  var fin: i64 = 0
175
  let lens: *i64 = sys_mmap(8*29) as *i64
  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
  let lext: *i64 = sys_mmap(8*29) as *i64
  var z: i64 = 0
  while z < 8 { lext[z]=0; z=z+1 }
  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
  let dists: *i64 = sys_mmap(8*30) as *i64
  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]=INF_MAGIC_1025
  dists[21]=INF_MAGIC_1537;dists[22]=INF_MAGIC_2049;dists[23]=INF_MAGIC_3073;dists[24]=INF_MAGIC_4097;dists[25]=INF_MAGIC_6145;dists[26]=INF_MAGIC_8193
  dists[27]=INF_MAGIC_12289;dists[28]=INF_MAGIC_16385;dists[29]=INF_MAGIC_24577
  let dext: *i64 = sys_mmap(8*30) as *i64
  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
198
  let fll: *i64 = sys_mmap(8*288) as *i64
  var q: i64 = 0
  while q < 144 { fll[q]=8; q=q+1 }
  while q < 256 { fll[q]=9; q=q+1 }
  while q < 280 { fll[q]=7; q=q+1 }
  while q < 288 { fll[q]=8; q=q+1 }
  let fdl: *i64 = sys_mmap(8*30) as *i64
  q = 0
  while q < 30 { fdl[q]=5; q=q+1 }
  let ord: *i64 = sys_mmap(8*19) as *i64
  ord[0]=16;ord[1]=17;ord[2]=18;ord[3]=0;ord[4]=8;ord[5]=7;ord[6]=9;ord[7]=6;ord[8]=10
  ord[9]=5;ord[10]=11;ord[11]=4;ord[12]=12;ord[13]=3;ord[14]=13;ord[15]=2;ord[16]=14
  ord[17]=1;ord[18]=15
212
  let lc: *i64 = sys_mmap(8*17) as *i64
  let ls: *i64 = sys_mmap(8*288) as *i64
  let dc: *i64 = sys_mmap(8*17) as *i64
  let ds: *i64 = sys_mmap(8*30) as *i64
  let off: *i64 = sys_mmap(8*17) as *i64
  let cll: *i64 = sys_mmap(8*19) as *i64
  let clc: *i64 = sys_mmap(8*17) as *i64
  let cls: *i64 = sys_mmap(8*19) as *i64
  let al: *i64 = sys_mmap(8*320) as *i64
222
  while fin == 0 {
      let bfinal: i64 = inf_bits(src, srclen, cur, 1)
      let btype: i64 = inf_bits(src, srclen, cur, 2)
      if cur[1] == 1 { return 0 - 2 }
      if bfinal == 1 { fin = 1 }
      if btype == 3 { return 0 - 5 }
      if btype == 0 {
          cur[0] = ((cur[0] + 7) >> 3) << 3
          let bp: i64 = cur[0] >> 3
          if bp + 4 > srclen { return 0 - 2 }
          let bl: i64 = (src[bp] as i64) | (((src[bp+1] & 0xff) as i64) << 8)
          let nl: i64 = (src[bp+2] as i64) | (((src[bp+3] & 0xff) as i64) << 8)
          // NLEN is LEN's one's complement -- the format's own corruption check, so honour it
          if (bl + nl) != 0xFFFF { return 0 - 6 }
          var p: i64 = bp + 4
          if p + bl > srclen { return 0 - 2 }
          if st[0] + bl > outcap { return 0 - 1 }
          var i2: i64 = 0
          while i2 < bl {
              out[st[0]] = src[p]
              st[0] = st[0] + 1
              p = p + 1
              i2 = i2 + 1
          }
          cur[0] = p << 3
      }
      if btype == 1 {
          inf_build(fll, 288, lc, ls, off)
          inf_build(fdl, 30, dc, ds, off)
          let rc: i64 = inf_codes(src, srclen, cur, out, outcap, st, lc, ls, dc, ds, lens, lext, dists, dext)
          if rc != 0 { return rc }
      }
      if btype == 2 {
          let hlit: i64 = inf_bits(src, srclen, cur, 5) + 257
          let hdist: i64 = inf_bits(src, srclen, cur, 5) + 1
          let hclen: i64 = inf_bits(src, srclen, cur, 4) + 4
          if cur[1] == 1 { return 0 - 2 }
          var j: i64 = 0
          while j < 19 { cll[j] = 0; j = j + 1 }
          j = 0
          while j < hclen { cll[ord[j]] = inf_bits(src, srclen, cur, 3); j = j + 1 }
          inf_build(cll, 19, clc, cls, off)
          let total: i64 = hlit + hdist
          if total > 320 { return 0 - 12 }
          var idx: i64 = 0
          while idx < total {
              let s2: i64 = inf_decode(src, srclen, cur, clc, cls)
              if s2 < 0 { return s2 }
              if s2 < 16 { al[idx] = s2; idx = idx + 1 }
              if s2 == 16 {
                  if idx == 0 { return 0 - 3 }
                  var rep: i64 = 3 + inf_bits(src, srclen, cur, 2)
                  let prev: i64 = al[idx-1]
                  if idx + rep > total { return 0 - 12 }
                  while rep > 0 { al[idx] = prev; idx = idx + 1; rep = rep - 1 }
              }
              if s2 == 17 {
                  var rep2: i64 = 3 + inf_bits(src, srclen, cur, 3)
                  if idx + rep2 > total { return 0 - 12 }
                  while rep2 > 0 { al[idx] = 0; idx = idx + 1; rep2 = rep2 - 1 }
              }
              if s2 == 18 {
                  var rep3: i64 = 11 + inf_bits(src, srclen, cur, 7)
                  if idx + rep3 > total { return 0 - 12 }
                  while rep3 > 0 { al[idx] = 0; idx = idx + 1; rep3 = rep3 - 1 }
              }
              if s2 > 18 { return 0 - 3 }
              if cur[1] == 1 { return 0 - 2 }
          }
          inf_build(al, hlit, lc, ls, off)
          let dl: *i64 = ((al as i64) + hlit*8) as *i64
          inf_build(dl, hdist, dc, ds, off)
          let rc2: i64 = inf_codes(src, srclen, cur, out, outcap, st, lc, ls, dc, ds, lens, lext, dists, dext)
          if rc2 != 0 { return rc2 }
      }
  }
  return st[0]
300}
301
302// ---- gzip container (RFC 1952): header, raw deflate, then VERIFY crc32 + isize ---------------
303func inf_gunzip(src: *u8, srclen: i64, out: *u8, outcap: i64) -> i64 {
  if srclen < 18 { return 0 - 7 }
  if (src[0] & 0xff) as i64 != 0x1f { return 0 - 7 }
  if (src[1] & 0xff) as i64 != 0x8b { return 0 - 7 }
  if (src[2] & 0xff) as i64 != 8 { return 0 - 8 }
  let flg: i64 = (src[3] & 0xff) as i64
  var p: i64 = 10
  if (flg & 4) != 0 {
      if p + 2 > srclen { return 0 - 2 }
      let xl: i64 = ((src[p] & 0xff) as i64) | (((src[p+1] & 0xff) as i64) << 8)
      p = p + 2 + xl
  }
  if (flg & 8) != 0 {
      while p < srclen { if src[p] == (0 as u8) { p = p + 1; break } p = p + 1 }
  }
  if (flg & 16) != 0 {
      while p < srclen { if src[p] == (0 as u8) { p = p + 1; break } p = p + 1 }
  }
  if (flg & 2) != 0 { p = p + 2 }
  if p >= srclen { return 0 - 2 }
  // the deflate stream runs to the 8-byte trailer
  let dlen: i64 = srclen - 8 - p
  if dlen <= 0 { return 0 - 2 }
  let n: i64 = inf_raw(((src as i64) + p) as *u8, dlen, out, outcap)
  if n < 0 { return n }
  let t: i64 = srclen - 8
  let want: i64 = ((src[t] & 0xff) as i64) | (((src[t+1] & 0xff) as i64) << 8)
                | (((src[t+2] & 0xff) as i64) << 16) | (((src[t+3] & 0xff) as i64) << 24)
  let isz: i64 = ((src[t+4] & 0xff) as i64) | (((src[t+5] & 0xff) as i64) << 8)
                | (((src[t+6] & 0xff) as i64) << 16) | (((src[t+7] & 0xff) as i64) << 24)
  if inf_crc32(out, n) != (want & INF_M32) { return 0 - 9 }
  if (n & INF_M32) != (isz & INF_M32) { return 0 - 10 }
  return n
336}
337
338// ---- zlib container (RFC 1950): 2-byte header, deflate body ----------------------------------
339func inf_zlib(src: *u8, srclen: i64, out: *u8, outcap: i64) -> i64 {
  if srclen < 6 { return 0 - 11 }
  let cmf: i64 = (src[0] & 0xff) as i64
  let flg: i64 = (src[1] & 0xff) as i64
  if (cmf & 15) != 8 { return 0 - 11 }
  if ((cmf * 256 + flg) % 31) != 0 { return 0 - 11 }
  var p: i64 = 2
  if (flg & 32) != 0 { p = p + 4 }
  return inf_raw(((src as i64) + p) as *u8, srclen - p, out, outcap)
348}
nx_inflate.nx source

`nx_inflate.nx` source
