nx_zstd_block.nx source

1// nx_zstd_block.nx -- Zstandard compressed-block decompression. 2// 3// The integration layer: literals section + sequences section -> plain bytes. 4// This is what turns the six proven zstd layers into a decoder that actually 5// handles a Compressed block instead of refusing it. 6// 7// WHAT IS WIRED. Raw, RLE and Huffman-coded literals (with a directly-encoded 8// weight table), plus the zero-sequence case where the block's output IS its 9// literals. That is a complete, legal zstd block -- it is what an encoder 10// emits for data it could not match, which is common for already-compressed 11// or high-entropy input. 12// 13// WHAT IS NOT, AND SAYS SO. FSE-coded sequences and FSE-compressed Huffman 14// weights each return their own distinct refusal code. A decoder that quietly 15// emitted the literals for a block that also carried sequences would produce 16// output that is the right LENGTH and the wrong BYTES -- the worst possible 17// failure, because a length check would pass it. 18// 19// THE HUFFMAN TREE DESCRIPTION IS INSIDE THE COMPRESSED SIZE. compressed_size 20// from the literals header covers the tree description AND the stream(s), so 21// the stream length is compressed_size minus the description. Treating 22// compressed_size as the stream alone over-reads by the description length and 23// desynchronises the sequences section that follows. 24// 25// genealogy_id: zstandard_rfc8878_block 26// lineage_id: nx_zstd_block_v1 27// license_tier: ORIGINAL 28 29import "nx_syscalls.nx" 30import "nx_zstd_fse.nx" 31import "nx_zstd_bits.nx" 32import "nx_zstd_huf.nx" 33import "nx_zstd_lit.nx" 34import "nx_zstd_seq.nx" 35import "nx_zstd_fse_dec.nx" 36import "nx_zstd_seqtab.nx" 37import "nx_zstd_seqdec.nx" 38 39const NX_BLK_ERR_MALFORMED: i64 = 0 - 1 40const NX_BLK_ERR_FSE_SEQ: i64 = 0 - 2 41const NX_BLK_ERR_FSE_WEIGHTS: i64 = 0 - 3 42const NX_BLK_ERR_STREAMS4: i64 = 0 - 4 43 44func nx_blk_at(d: *u8, i: i64) -> i64 { return (d[i] as i64) & 255 } 45 46// ===== the Huffman tree description =============================== 47// 48// A header byte below 128 means the weights follow directly. At or above 128 49// they are FSE-compressed, which this layer does not yet build -- refused 50// with its own code so the caller can tell 'unsupported' from 'corrupt'. 51// Returns the description length in bytes, or a negative error. 52 53func nx_zstd_block_tree(d: *u8, n: i64, off: i64, out_t: *i64) -> i64 { 54 if off >= n { return NX_BLK_ERR_MALFORMED } 55 let hdr: i64 = nx_blk_at(d, off) 56 if hdr >= 128 { return NX_BLK_ERR_FSE_WEIGHTS } 57 58 let w: *i64 = sys_mmap(512 * 8) as *i64 59 let count: i64 = nx_zstd_weights_direct(d, n, off + 1, hdr, w) 60 if count < 0 { return NX_BLK_ERR_MALFORMED } 61 let last: i64 = nx_zstd_weights_complete(w, count) 62 if last < 0 { return NX_BLK_ERR_MALFORMED } 63 let tl: i64 = nx_zstd_weights_tablelog(w, count + 1) 64 if tl < 0 { return NX_BLK_ERR_MALFORMED } 65 let t: *NxZstdHuf = nx_zstd_huf_build(w, count + 1, tl) 66 if t == (0 as *NxZstdHuf) { return NX_BLK_ERR_MALFORMED } 67 68 out_t[0] = t as i64 69 // one header byte plus the packed weight nibbles 70 return 1 + ((hdr + 1 + 1) / 2) 71} 72 73// ===== decompress one compressed block ============================ 74// 75// Returns bytes written, or a negative code. d/n is the block payload only 76// (the caller has already consumed the 3-byte block header). 77 78func nx_zstd_block_decompress(d: *u8, n: i64, out: *u8, cap: i64) -> i64 { 79 let lf: *i64 = sys_mmap(128) as *i64 80 if nx_zstd_lit_header(d, n, 0, lf) != 1 { return NX_BLK_ERR_MALFORMED } 81 82 let ltype: i64 = lf[NX_LIT_FLD_TYPE] 83 let regen: i64 = lf[NX_LIT_FLD_REGEN] 84 let csize: i64 = lf[NX_LIT_FLD_COMPSIZE] 85 let hlen: i64 = lf[NX_LIT_FLD_HDRLEN] 86 87 let lit: *u8 = sys_mmap(regen + 64) 88 var got: i64 = 0 - 1 89 90 if ltype == NX_LIT_RAW { 91 got = nx_zstd_lit_raw(d, n, hlen, regen, lit, regen + 64) 92 } else { 93 if ltype == NX_LIT_RLE { 94 got = nx_zstd_lit_rle(d, n, hlen, regen, lit, regen + 64) 95 } else { 96 // Compressed or Treeless: four streams need a jump table this layer 97 // does not read yet, so say so rather than misreading stream one 98 if lf[NX_LIT_FLD_STREAMS] != 1 { return NX_BLK_ERR_STREAMS4 } 99 let tslot: *i64 = sys_mmap(64) as *i64 100 let tlen: i64 = nx_zstd_block_tree(d, n, hlen, tslot) 101 if tlen < 0 { return tlen } 102 let t: *NxZstdHuf = tslot[0] as *NxZstdHuf 103 // the tree description lives INSIDE compressed_size 104 let stream_len: i64 = csize - tlen 105 if stream_len <= 0 { return NX_BLK_ERR_MALFORMED } 106 got = nx_zstd_lit_huf(t, d, n, hlen + tlen, stream_len, regen, lit, regen + 64) 107 } } 108 109 if got < 0 { return NX_BLK_ERR_MALFORMED } 110 if got != regen { return NX_BLK_ERR_MALFORMED } 111 112 // ---- sequences ---- 113 let soff: i64 = hlen + csize 114 let sf: *i64 = sys_mmap(128) as *i64 115 if nx_zstd_seq_header(d, n, soff, sf) != 1 { return NX_BLK_ERR_MALFORMED } 116 let nseq: i64 = sf[NX_SEQ_FLD_COUNT] 117 118 if nseq == 0 { 119 // no sequences: the block's output IS its literals 120 if regen > cap { return NX_BLK_ERR_MALFORMED } 121 var i: i64 = 0 122 while i < regen { out[i] = lit[i]; i = i + 1 } 123 return regen 124 } 125 126 // All three alphabets must use the PREDEFINED distributions. RLE, 127 // FSE_Compressed and Repeat each carry a table description ahead of the 128 // bitstream that this layer does not read yet, so they are refused with 129 // the same distinct code rather than decoded against the wrong tables. 130 if sf[NX_SEQ_FLD_LLMODE] != NX_SEQ_MODE_PREDEFINED { return NX_BLK_ERR_FSE_SEQ } 131 if sf[NX_SEQ_FLD_MLMODE] != NX_SEQ_MODE_PREDEFINED { return NX_BLK_ERR_FSE_SEQ } 132 if sf[NX_SEQ_FLD_OFMODE] != NX_SEQ_MODE_PREDEFINED { return NX_BLK_ERR_FSE_SEQ } 133 134 // the sequence bitstream is everything after the sequences header 135 let bstart: i64 = soff + sf[NX_SEQ_FLD_HDRLEN] 136 let blen: i64 = n - bstart 137 if blen <= 0 { return NX_BLK_ERR_MALFORMED } 138 139 let tll: *NxFseTable = nx_zstd_seqtab_ll_table() 140 let tml: *NxFseTable = nx_zstd_seqtab_ml_table() 141 let tof: *NxFseTable = nx_zstd_seqtab_of_table() 142 if tll == (0 as *NxFseTable) { return NX_BLK_ERR_MALFORMED } 143 if tml == (0 as *NxFseTable) { return NX_BLK_ERR_MALFORMED } 144 if tof == (0 as *NxFseTable) { return NX_BLK_ERR_MALFORMED } 145 146 let sb: *NxZstdBits = nx_zstd_bits_init(d + bstart, blen) 147 if sb == (0 as *NxZstdBits) { return NX_BLK_ERR_MALFORMED } 148 149 let seqs: *i64 = sys_mmap(nseq * 3 * 8 + 64) as *i64 150 if nx_zstd_seq_decode_all(tll, tml, tof, sb, nseq, seqs) != 1 { return NX_BLK_ERR_MALFORMED } 151 152 // execute against the literals; this refuses an offset reaching before the 153 // start of the output rather than copying from nowhere 154 return nx_zstd_seq_execute(lit, regen, seqs, nseq, out, cap) 155}