nx_zstd_lit.nx source
↩ module page · 199 lines · 7023 B
1// nx_zstd_lit.nx -- Zstandard literals section, header and payload.
2//
3// The wiring layer that composes everything below it: nx_zstd_frame (blocks),
4// nx_zstd_bits (the backward reader), nx_zstd_huf (the flat decode table).
5// Raw and RLE literals decode fully here; Huffman-coded literals decode
6// through a table the caller supplies.
7//
8// THE HEADER IS 1 TO 5 BYTES AND THE SIZE FIELDS ARE NOT BYTE-ALIGNED. Two
9// bits of block type and two of size format share byte 0 with the TOP of the
10// regenerated size, so every size read starts at bit 4 of byte 0 and runs into
11// the following bytes little-endian. Reading the size as whole bytes gives a
12// value that is plausible and wrong -- and wrong by a factor of 16, so it
13// usually fails loudly on the first block and silently on a block whose true
14// size happens to be small.
15//
16// SIZE_FORMAT 0 AND 2 MEAN THE SAME THING FOR RAW AND RLE. Both select the
17// one-byte header with a 5-bit size; only the low bit of the format field is
18// consulted. For Compressed and Treeless the same two values mean DIFFERENT
19// things -- 0 is a single stream, 1 is four streams, both with 10-bit sizes.
20// One field, two interpretations, decided by the block type.
21//
22// FOUR STREAMS, NOT ONE. Above the smallest size format, compressed literals
23// are split into four independently-decodable streams so a decoder can run
24// them in parallel. A reader that assumes one stream consumes the first
25// stream's jump table as literal data.
26//
27// genealogy_id: zstandard_rfc8878_literals
28// lineage_id: nx_zstd_lit_v1
29// license_tier: ORIGINAL
30
31import "nx_syscalls.nx"
32import "nx_zstd_bits.nx"
33import "nx_zstd_huf.nx"
34
35const NX_LIT_RAW: i64 = 0
36const NX_LIT_RLE: i64 = 1
37const NX_LIT_COMP: i64 = 2
38const NX_LIT_TREELESS: i64 = 3
39
40const NX_LIT_FLD_TYPE: i64 = 0
41const NX_LIT_FLD_FORMAT: i64 = 1
42const NX_LIT_FLD_REGEN: i64 = 2
43const NX_LIT_FLD_COMPSIZE: i64 = 3
44const NX_LIT_FLD_STREAMS: i64 = 4
45const NX_LIT_FLD_HDRLEN: i64 = 5
46
47func nx_lit_at(d: *u8, i: i64) -> i64 { return (d[i] as i64) & 255 }
48
49// ===== header =====================================================
50//
51// Returns 1 and fills fld, or 0. Refuses rather than guessing when the buffer
52// cannot hold the header the format field declares.
53
54func nx_zstd_lit_header(d: *u8, n: i64, off: i64, fld: *i64) -> i64 {
55 if off >= n { return 0 }
56 let b0: i64 = nx_lit_at(d, off)
57 let btype: i64 = b0 & 3
58 let fmt: i64 = (b0 >> 2) & 3
59
60 var regen: i64 = 0
61 var comp: i64 = 0
62 var streams: i64 = 1
63 var hlen: i64 = 0
64
65 if btype == NX_LIT_RAW {
66 hlen = 0
67 }
68 if btype == NX_LIT_RLE {
69 hlen = 0
70 }
71
72 if btype <= NX_LIT_RLE {
73 // one field only; formats 0 and 2 are the SAME one-byte form
74 if fmt == 1 {
75 if off + 2 > n { return 0 }
76 regen = (b0 >> 4) | (nx_lit_at(d, off + 1) << 4)
77 hlen = 2
78 } else {
79 if fmt == 3 {
80 if off + 3 > n { return 0 }
81 regen = (b0 >> 4) | (nx_lit_at(d, off + 1) << 4) | (nx_lit_at(d, off + 2) << 12)
82 hlen = 3
83 } else {
84 regen = b0 >> 3
85 hlen = 1
86 } }
87 comp = regen
88 if btype == NX_LIT_RLE { comp = 1 }
89 } else {
90 // Compressed or Treeless: two fields packed together from bit 4
91 if fmt == 0 {
92 if off + 3 > n { return 0 }
93 let v: i64 = (b0 >> 4) | (nx_lit_at(d, off+1) << 4) | (nx_lit_at(d, off+2) << 12)
94 regen = v & 1023
95 comp = v >> 10
96 streams = 1
97 hlen = 3
98 } else {
99 if fmt == 1 {
100 if off + 3 > n { return 0 }
101 let v: i64 = (b0 >> 4) | (nx_lit_at(d, off+1) << 4) | (nx_lit_at(d, off+2) << 12)
102 regen = v & 1023
103 comp = v >> 10
104 streams = 4
105 hlen = 3
106 } else {
107 if fmt == 2 {
108 if off + 4 > n { return 0 }
109 let v: i64 = (b0 >> 4) | (nx_lit_at(d, off+1) << 4) | (nx_lit_at(d, off+2) << 12)
110 | (nx_lit_at(d, off+3) << 20)
111 regen = v & 16383
112 comp = v >> 14
113 streams = 4
114 hlen = 4
115 } else {
116 if off + 5 > n { return 0 }
117 let v: i64 = (b0 >> 4) | (nx_lit_at(d, off+1) << 4) | (nx_lit_at(d, off+2) << 12)
118 | (nx_lit_at(d, off+3) << 20) | (nx_lit_at(d, off+4) << 28)
119 regen = v & 262143
120 comp = v >> 18
121 streams = 4
122 hlen = 5
123 } } }
124 }
125
126 if regen < 0 { return 0 }
127 if comp < 0 { return 0 }
128 if off + hlen + comp > n { return 0 }
129
130 fld[NX_LIT_FLD_TYPE] = btype
131 fld[NX_LIT_FLD_FORMAT] = fmt
132 fld[NX_LIT_FLD_REGEN] = regen
133 fld[NX_LIT_FLD_COMPSIZE] = comp
134 fld[NX_LIT_FLD_STREAMS] = streams
135 fld[NX_LIT_FLD_HDRLEN] = hlen
136 return 1
137}
138
139// writes a one-byte Raw or RLE header for sizes below 32
140func nx_zstd_lit_header_write(o: *u8, cap: i64, off: i64, btype: i64, regen: i64) -> i64 {
141 if off >= cap { return 0 }
142 if btype < 0 { return 0 }
143 if btype > 1 { return 0 }
144 if regen < 0 { return 0 }
145 if regen > 31 { return 0 }
146 o[off] = ((btype & 3) | (regen << 3)) as u8
147 return 1
148}
149
150// ===== raw and RLE payloads =======================================
151
152func nx_zstd_lit_raw(d: *u8, n: i64, off: i64, count: i64, out: *u8, cap: i64) -> i64 {
153 if count < 0 { return 0 - 1 }
154 if off + count > n { return 0 - 1 }
155 if count > cap { return 0 - 1 }
156 var i: i64 = 0
157 while i < count { out[i] = d[off + i]; i = i + 1 }
158 return count
159}
160
161func nx_zstd_lit_rle(d: *u8, n: i64, off: i64, count: i64, out: *u8, cap: i64) -> i64 {
162 if count < 0 { return 0 - 1 }
163 if off >= n { return 0 - 1 }
164 if count > cap { return 0 - 1 }
165 let b: u8 = d[off]
166 var i: i64 = 0
167 while i < count { out[i] = b; i = i + 1 }
168 return count
169}
170
171// ===== Huffman-coded literals =====================================
172//
173// Decodes exactly `count` literals from one backward stream. Stops and
174// REFUSES if the stream runs dry early -- a short stream means the header
175// and payload disagree, and emitting the literals decoded so far would hand
176// the caller a partial buffer it cannot distinguish from a complete one.
177
178func nx_zstd_lit_huf(t: *NxZstdHuf, d: *u8, n: i64, off: i64, comp_size: i64,
179 count: i64, out: *u8, cap: i64) -> i64 {
180 if t == (0 as *NxZstdHuf) { return 0 - 1 }
181 if count < 0 { return 0 - 1 }
182 if count > cap { return 0 - 1 }
183 if comp_size <= 0 { return 0 - 1 }
184 if off + comp_size > n { return 0 - 1 }
185
186 let b: *NxZstdBits = nx_zstd_bits_init(d + off, comp_size)
187 if b == (0 as *NxZstdBits) { return 0 - 1 }
188
189 var i: i64 = 0
190 while i < count {
191 let s: i64 = nx_zstd_huf_decode(t, b)
192 if s < 0 { return 0 - 1 }
193 if s > 255 { return 0 - 1 }
194 if b.overflow == 1 { return 0 - 1 }
195 out[i] = (s & 255) as u8
196 i = i + 1
197 }
198 return count
199}