nx_zstd_seq.nx source
↩ module page · 262 lines · 8711 B
1// nx_zstd_seq.nx -- Zstandard sequences: header, code tables, execution.
2//
3// The last zstd layer. A sequence is a triple (literal_length, match_length,
4// offset): copy N literals, then copy M bytes from earlier in the OUTPUT. The
5// literals come from nx_zstd_lit; this turns them plus the sequence list into
6// the decompressed bytes.
7//
8// THE MATCH COPY MUST BE BYTE BY BYTE. An offset SMALLER than the match length
9// is legal and extremely common -- it is how zstd encodes runs, and the copy
10// deliberately reads bytes it wrote moments earlier in the same operation.
11// A bulk move that reads the whole source region up front produces the wrong
12// bytes for every position past the first `offset` of them. offset=1 with
13// match_length=100 is a 100-byte run of one value; a bulk copy gives one byte
14// and 99 of whatever was already there.
15//
16// THE SEQUENCE COUNT IS 1, 2 OR 3 BYTES with a discontinuous encoding: below
17// 128 it is the byte itself, below 255 it is a two-byte form biased by 0x8000,
18// and exactly 255 escapes to a three-byte form biased by 0x7F00. Treating it
19// as a plain varint mis-sizes the header and every table after it.
20//
21// THE LITERAL AND MATCH LENGTH CODES ARE BASELINE PLUS EXTRA BITS, and the
22// baselines are NOT uniform -- the first 16 literal-length codes are the value
23// itself, then the table jumps. Match lengths start at 3, not 0, because a
24// match shorter than 3 is never worth encoding.
25//
26// genealogy_id: zstandard_rfc8878_sequences
27// lineage_id: nx_zstd_seq_v1
28// license_tier: ORIGINAL
29
30import "nx_syscalls.nx"
31
32const NX_SEQ_MODE_PREDEFINED: i64 = 0
33const NX_SEQ_MODE_RLE: i64 = 1
34const NX_SEQ_MODE_FSE: i64 = 2
35const NX_SEQ_MODE_REPEAT: i64 = 3
36
37const NX_SEQ_FLD_COUNT: i64 = 0
38const NX_SEQ_FLD_LLMODE: i64 = 1
39const NX_SEQ_FLD_OFMODE: i64 = 2
40const NX_SEQ_FLD_MLMODE: i64 = 3
41const NX_SEQ_FLD_HDRLEN: i64 = 4
42
43func nx_seq_at(d: *u8, i: i64) -> i64 { return (d[i] as i64) & 255 }
44
45// ===== sequence count: 1, 2 or 3 bytes, discontinuous =============
46
47func nx_zstd_seq_header(d: *u8, n: i64, off: i64, fld: *i64) -> i64 {
48 if off >= n { return 0 }
49 let b0: i64 = nx_seq_at(d, off)
50 var count: i64 = 0
51 var p: i64 = off
52
53 if b0 == 0 {
54 // no sequences at all: the block is literals only, and NO mode byte follows
55 fld[NX_SEQ_FLD_COUNT] = 0
56 fld[NX_SEQ_FLD_LLMODE] = 0
57 fld[NX_SEQ_FLD_OFMODE] = 0
58 fld[NX_SEQ_FLD_MLMODE] = 0
59 fld[NX_SEQ_FLD_HDRLEN] = 1
60 return 1
61 }
62 if b0 < 128 {
63 count = b0
64 p = off + 1
65 } else {
66 if b0 < 255 {
67 if off + 2 > n { return 0 }
68 count = ((b0 - 128) << 8) + nx_seq_at(d, off + 1)
69 p = off + 2
70 } else {
71 if off + 3 > n { return 0 }
72 count = nx_seq_at(d, off + 1) + (nx_seq_at(d, off + 2) << 8) + 32512
73 p = off + 3
74 } }
75
76 if p >= n { return 0 }
77 let modes: i64 = nx_seq_at(d, p)
78 // the low two bits are reserved and MUST be zero
79 if (modes & 3) != 0 { return 0 }
80 fld[NX_SEQ_FLD_COUNT] = count
81 fld[NX_SEQ_FLD_LLMODE] = (modes >> 6) & 3
82 fld[NX_SEQ_FLD_OFMODE] = (modes >> 4) & 3
83 fld[NX_SEQ_FLD_MLMODE] = (modes >> 2) & 3
84 fld[NX_SEQ_FLD_HDRLEN] = (p - off) + 1
85 return 1
86}
87
88// ===== literal-length codes =======================================
89//
90// Codes 0..15 are the value itself with no extra bits; above that the table
91// jumps and each code carries a baseline plus a fixed number of extra bits.
92
93func nx_zstd_ll_base(code: i64) -> i64 {
94 if code < 0 { return 0 - 1 }
95 if code <= 15 { return code }
96 if code == 16 { return 16 }
97 if code == 17 { return 18 }
98 if code == 18 { return 20 }
99 if code == 19 { return 22 }
100 if code == 20 { return 24 }
101 if code == 21 { return 28 }
102 if code == 22 { return 32 }
103 if code == 23 { return 40 }
104 if code == 24 { return 48 }
105 if code == 25 { return 64 }
106 if code == 26 { return 128 }
107 if code == 27 { return 256 }
108 if code == 28 { return 512 }
109 if code == 29 { return 1024 }
110 if code == 30 { return 2048 }
111 if code == 31 { return 4096 }
112 if code == 32 { return 8192 }
113 if code == 33 { return 16384 }
114 if code == 34 { return 32768 }
115 if code == 35 { return 65536 }
116 return 0 - 1
117}
118
119func nx_zstd_ll_extra(code: i64) -> i64 {
120 if code < 0 { return 0 - 1 }
121 if code <= 15 { return 0 }
122 if code <= 19 { return 1 }
123 if code <= 21 { return 2 }
124 if code <= 23 { return 3 }
125 if code == 24 { return 4 }
126 if code == 25 { return 6 }
127 if code == 26 { return 7 }
128 if code == 27 { return 8 }
129 if code == 28 { return 9 }
130 if code == 29 { return 10 }
131 if code == 30 { return 11 }
132 if code == 31 { return 12 }
133 if code == 32 { return 13 }
134 if code == 33 { return 14 }
135 if code == 34 { return 15 }
136 if code == 35 { return 16 }
137 return 0 - 1
138}
139
140// ===== match-length codes =========================================
141//
142// Match lengths start at THREE -- a shorter match is never encoded.
143
144func nx_zstd_ml_base(code: i64) -> i64 {
145 if code < 0 { return 0 - 1 }
146 if code <= 31 { return code + 3 }
147 if code == 32 { return 35 }
148 if code == 33 { return 37 }
149 if code == 34 { return 39 }
150 if code == 35 { return 41 }
151 if code == 36 { return 43 }
152 if code == 37 { return 47 }
153 if code == 38 { return 51 }
154 if code == 39 { return 59 }
155 if code == 40 { return 67 }
156 if code == 41 { return 83 }
157 if code == 42 { return 99 }
158 if code == 43 { return 131 }
159 if code == 44 { return 259 }
160 if code == 45 { return 515 }
161 if code == 46 { return 1027 }
162 if code == 47 { return 2051 }
163 if code == 48 { return 4099 }
164 if code == 49 { return 8195 }
165 if code == 50 { return 16387 }
166 if code == 51 { return 32771 }
167 if code == 52 { return 65539 }
168 return 0 - 1
169}
170
171func nx_zstd_ml_extra(code: i64) -> i64 {
172 if code < 0 { return 0 - 1 }
173 if code <= 31 { return 0 }
174 if code <= 35 { return 1 }
175 if code <= 37 { return 2 }
176 if code <= 39 { return 3 }
177 if code <= 41 { return 4 }
178 if code == 42 { return 5 }
179 if code == 43 { return 7 }
180 if code == 44 { return 8 }
181 if code == 45 { return 9 }
182 if code == 46 { return 10 }
183 if code == 47 { return 11 }
184 if code == 48 { return 12 }
185 if code == 49 { return 13 }
186 if code == 50 { return 14 }
187 if code == 51 { return 15 }
188 if code == 52 { return 16 }
189 return 0 - 1
190}
191
192// ===== offset codes ===============================================
193//
194// An offset code N carries baseline 2^N and N extra bits. Values 1..3 are the
195// repeat-offset slots; a literal offset is the decoded value minus 3.
196
197func nx_zstd_of_base(code: i64) -> i64 {
198 if code < 0 { return 0 - 1 }
199 if code > 31 { return 0 - 1 }
200 return 1 << code
201}
202
203func nx_zstd_of_extra(code: i64) -> i64 {
204 if code < 0 { return 0 - 1 }
205 if code > 31 { return 0 - 1 }
206 return code
207}
208
209// ===== execution ==================================================
210//
211// seqs holds nseq triples laid out as (literal_length, match_length, offset).
212// Returns bytes written, or -1. Refuses an offset that reaches before the
213// start of the output, or a literal run longer than the literals available --
214// both would read memory the stream never provided.
215
216func nx_zstd_seq_execute(lit: *u8, lit_len: i64, seqs: *i64, nseq: i64,
217 out: *u8, cap: i64) -> i64 {
218 if lit_len < 0 { return 0 - 1 }
219 if nseq < 0 { return 0 - 1 }
220
221 var lp: i64 = 0
222 var op: i64 = 0
223 var s: i64 = 0
224 var k: i64 = 0
225
226 while s < nseq {
227 let ll: i64 = seqs[s * 3]
228 let ml: i64 = seqs[s * 3 + 1]
229 let off: i64 = seqs[s * 3 + 2]
230 if ll < 0 { return 0 - 1 }
231 if ml < 0 { return 0 - 1 }
232 if off < 1 { return 0 - 1 }
233 if lp + ll > lit_len { return 0 - 1 }
234 if op + ll + ml > cap { return 0 - 1 }
235
236 k = 0
237 while k < ll { out[op + k] = lit[lp + k]; k = k + 1 }
238 lp = lp + ll
239 op = op + ll
240
241 // an offset reaching before the start of the output is malformed
242 if off > op { return 0 - 1 }
243
244 // BYTE BY BYTE: offset may be smaller than the match length, and the
245 // copy is REQUIRED to read bytes it wrote earlier in this same loop
246 k = 0
247 while k < ml {
248 out[op + k] = out[op + k - off]
249 k = k + 1
250 }
251 op = op + ml
252 s = s + 1
253 }
254
255 // whatever literals remain after the last sequence are copied verbatim
256 let tail: i64 = lit_len - lp
257 if tail < 0 { return 0 - 1 }
258 if op + tail > cap { return 0 - 1 }
259 k = 0
260 while k < tail { out[op + k] = lit[lp + k]; k = k + 1 }
261 return op + tail
262}