`nx_zstd_frame.nx` source

↩ module page · 248 lines · 8565 B
1// nx_zstd_frame.nx -- Zstandard frame and block layer, writer and reader.
2//
3// Sits above nx_zstd_fse.nx (the entropy tables). This layer is what makes a
4// .zst file walkable: magic, a variable-length frame header, then a chain of
5// blocks each with its own 3-byte header. Raw and RLE blocks decode fully
6// here -- a frame built only from those is a completely valid zstd file that
7// any zstd tool will read -- so this is a working decoder for that subset,
8// not a stub.
9//
10// COMPRESSED BLOCKS ARE REFUSED, NOT GUESSED. The literals+sequences layer is
11// not built yet, so a Compressed block returns a distinct refusal code rather
12// than emitting whatever the raw bytes happen to look like. A decoder that
13// silently passes through undecoded data is worse than one that stops.
14//
15// THE HEADER LENGTH IS COMPUTED, NOT ASSUMED. Frame_Content_Size is 0, 1, 2,
16// 4 or 8 bytes, Dictionary_ID is 0, 1, 2 or 4, and the Window_Descriptor is
17// ABSENT when Single_Segment_flag is set. Five independent choices, so the
18// header is anywhere from 2 to 14 bytes. Assuming a length works on files
19// from one encoder and fails on the next.
20//
21// THE 2-BYTE FCS IS BIASED BY 256. A two-byte Frame_Content_Size stores
22// (size - 256), so a naive read reports every such frame 256 bytes short.
23// This only affects frames between 256 and 65791 bytes, which is precisely
24// the range small test files land in.
25//
26// genealogy_id: zstandard_rfc8878_frame
27// lineage_id:   nx_zstd_frame_v1
28// license_tier: ORIGINAL
29
30import "nx_syscalls.nx"
31
32const NX_ZSTD_MAGIC:      i64 = 0xfd2fb528
33const NX_ZSTD_BLK_RAW:    i64 = 0
34const NX_ZSTD_BLK_RLE:    i64 = 1
35const NX_ZSTD_BLK_COMP:   i64 = 2
36const NX_ZSTD_BLK_RESV:   i64 = 3
37
38// frame field slots
39const NX_ZF_CONTENTSIZE: i64 = 0
40const NX_ZF_WINDOWSIZE:  i64 = 1
41const NX_ZF_DICTID:      i64 = 2
42const NX_ZF_CHECKSUM:    i64 = 3
43const NX_ZF_SINGLESEG:   i64 = 4
44const NX_ZF_HDRLEN:      i64 = 5
45
46// block field slots
47const NX_ZB_LAST:    i64 = 0
48const NX_ZB_TYPE:    i64 = 1
49const NX_ZB_SIZE:    i64 = 2
50const NX_ZB_DATAOFF: i64 = 3
51const NX_ZB_NEXT:    i64 = 4
52
53// decode outcomes
54const NX_ZSTD_OK:            i64 = 1
55const NX_ZSTD_ERR_MALFORMED: i64 = 0
56const NX_ZSTD_ERR_COMPRESSED: i64 = 0 - 2
57
58func nx_zstd_at(d: *u8, i: i64) -> i64 { return (d[i] as i64) & 255 }
59
60func nx_zstd_le(d: *u8, off: i64, n: i64) -> i64 {
61    var v: i64 = 0
62    var i: i64 = 0
63    while i < n { v = v | (nx_zstd_at(d, off + i) << (i * 8)); i = i + 1 }
64    return v
65}
66
67func nx_zstd_le_w(o: *u8, off: i64, v: i64, n: i64) -> i64 {
68    var i: i64 = 0
69    while i < n { o[off + i] = ((v >> (i * 8)) & 255) as u8; i = i + 1 }
70    return n
71}
72
73// ===== field-size tables ==========================================
74//
75// Both are irregular: neither is simply the flag value.
76
77func nx_zstd_fcs_size(flag: i64, single_segment: i64) -> i64 {
78    if flag == 0 {
79        if single_segment == 1 { return 1 }
80        return 0
81    }
82    if flag == 1 { return 2 }
83    if flag == 2 { return 4 }
84    return 8
85}
86
87func nx_zstd_did_size(flag: i64) -> i64 {
88    if flag == 0 { return 0 }
89    if flag == 1 { return 1 }
90    if flag == 2 { return 2 }
91    return 4
92}
93
94// ===== window size from the descriptor byte =======================
95
96func nx_zstd_window_size(desc: i64) -> i64 {
97    let exponent: i64 = (desc >> 3) & 31
98    let mantissa: i64 = desc & 7
99    let window_log: i64 = 10 + exponent
100    if window_log > 40 { return 0 - 1 }
101    let base: i64 = 1 << window_log
102    return base + (base / 8) * mantissa
103}
104
105// ===== frame header ===============================================
106
107func nx_zstd_frame_parse(d: *u8, n: i64, fld: *i64) -> i64 {
108    if n < 5 { return NX_ZSTD_ERR_MALFORMED }
109    if nx_zstd_le(d, 0, 4) != NX_ZSTD_MAGIC { return NX_ZSTD_ERR_MALFORMED }
110
111    let desc: i64 = nx_zstd_at(d, 4)
112    let fcs_flag: i64 = (desc >> 6) & 3
113    let single: i64 = (desc >> 5) & 1
114    let unused: i64 = (desc >> 4) & 1
115    let reserved: i64 = (desc >> 3) & 1
116    let checksum: i64 = (desc >> 2) & 1
117    let did_flag: i64 = desc & 3
118    // both must be zero: a decoder that ignores them resynchronises on junk
119    if unused != 0 { return NX_ZSTD_ERR_MALFORMED }
120    if reserved != 0 { return NX_ZSTD_ERR_MALFORMED }
121
122    var p: i64 = 5
123    var window: i64 = 0
124    if single == 0 {
125        if p >= n { return NX_ZSTD_ERR_MALFORMED }
126        window = nx_zstd_window_size(nx_zstd_at(d, p))
127        if window < 0 { return NX_ZSTD_ERR_MALFORMED }
128        p = p + 1
129    }
130
131    let did_sz: i64 = nx_zstd_did_size(did_flag)
132    if p + did_sz > n { return NX_ZSTD_ERR_MALFORMED }
133    var dictid: i64 = 0
134    if did_sz > 0 { dictid = nx_zstd_le(d, p, did_sz) }
135    p = p + did_sz
136
137    let fcs_sz: i64 = nx_zstd_fcs_size(fcs_flag, single)
138    if p + fcs_sz > n { return NX_ZSTD_ERR_MALFORMED }
139    var csize: i64 = 0 - 1
140    if fcs_sz > 0 {
141        csize = nx_zstd_le(d, p, fcs_sz)
142        // the two-byte form is biased by 256
143        if fcs_sz == 2 { csize = csize + 256 }
144    }
145    p = p + fcs_sz
146
147    // with a single segment the window IS the content size
148    if single == 1 { window = csize }
149
150    fld[NX_ZF_CONTENTSIZE] = csize
151    fld[NX_ZF_WINDOWSIZE]  = window
152    fld[NX_ZF_DICTID]      = dictid
153    fld[NX_ZF_CHECKSUM]    = checksum
154    fld[NX_ZF_SINGLESEG]   = single
155    fld[NX_ZF_HDRLEN]      = p
156    return NX_ZSTD_OK
157}
158
159// writes a single-segment frame header with a 4-byte content size
160func nx_zstd_frame_write(o: *u8, cap: i64, content_size: i64) -> i64 {
161    if content_size < 0 { return 0 }
162    if cap < 9 { return 0 }
163    nx_zstd_le_w(o, 0, NX_ZSTD_MAGIC, 4)
164    // fcs_flag 2 (four bytes), single_segment set, no checksum, no dict
165    o[4] = ((2 << 6) | (1 << 5)) as u8
166    nx_zstd_le_w(o, 5, content_size, 4)
167    return 9
168}
169
170// ===== block header ===============================================
171
172func nx_zstd_block_parse(d: *u8, n: i64, off: i64, fld: *i64) -> i64 {
173    if off + 3 > n { return NX_ZSTD_ERR_MALFORMED }
174    let h: i64 = nx_zstd_le(d, off, 3)
175    let last: i64 = h & 1
176    let btype: i64 = (h >> 1) & 3
177    let bsize: i64 = h >> 3
178    if btype == NX_ZSTD_BLK_RESV { return NX_ZSTD_ERR_MALFORMED }
179
180    var stored: i64 = bsize
181    if btype == NX_ZSTD_BLK_RLE { stored = 1 }
182    if off + 3 + stored > n { return NX_ZSTD_ERR_MALFORMED }
183
184    fld[NX_ZB_LAST]    = last
185    fld[NX_ZB_TYPE]    = btype
186    fld[NX_ZB_SIZE]    = bsize
187    fld[NX_ZB_DATAOFF] = off + 3
188    fld[NX_ZB_NEXT]    = off + 3 + stored
189    return NX_ZSTD_OK
190}
191
192func nx_zstd_block_write(o: *u8, cap: i64, off: i64, last: i64, btype: i64,
193                         data: *u8, size: i64) -> i64 {
194    if btype < 0 { return 0 }
195    if btype > 2 { return 0 }
196    if size < 0 { return 0 }
197    var stored: i64 = size
198    if btype == NX_ZSTD_BLK_RLE { stored = 1 }
199    if off + 3 + stored > cap { return 0 }
200    let h: i64 = (last & 1) | ((btype & 3) << 1) | (size << 3)
201    nx_zstd_le_w(o, off, h, 3)
202    var i: i64 = 0
203    while i < stored { o[off + 3 + i] = data[i]; i = i + 1 }
204    return off + 3 + stored
205}
206
207// ===== decode a whole frame =======================================
208//
209// Returns bytes written, 0 on malformed input, or NX_ZSTD_ERR_COMPRESSED if
210// the frame needs the literals+sequences layer that is not built yet.
211
212func nx_zstd_decode(d: *u8, n: i64, out: *u8, cap: i64) -> i64 {
213    let fld: *i64 = sys_mmap(128) as *i64
214    if nx_zstd_frame_parse(d, n, fld) != NX_ZSTD_OK { return NX_ZSTD_ERR_MALFORMED }
215    var p: i64 = fld[NX_ZF_HDRLEN]
216
217    let blk: *i64 = sys_mmap(128) as *i64
218    var outp: i64 = 0
219    var go: i64 = 1
220    while go == 1 {
221        let r: i64 = nx_zstd_block_parse(d, n, p, blk)
222        if r != NX_ZSTD_OK { return NX_ZSTD_ERR_MALFORMED }
223        let btype: i64 = blk[NX_ZB_TYPE]
224        let bsize: i64 = blk[NX_ZB_SIZE]
225        let doff: i64 = blk[NX_ZB_DATAOFF]
226
227        if btype == NX_ZSTD_BLK_COMP { return NX_ZSTD_ERR_COMPRESSED }
228        if outp + bsize > cap { return NX_ZSTD_ERR_MALFORMED }
229
230        if btype == NX_ZSTD_BLK_RAW {
231            var i: i64 = 0
232            while i < bsize { out[outp + i] = d[doff + i]; i = i + 1 }
233            outp = outp + bsize
234        } else {
235            let b: u8 = d[doff]
236            var i: i64 = 0
237            while i < bsize { out[outp + i] = b; i = i + 1 }
238            outp = outp + bsize
239        }
240
241        if blk[NX_ZB_LAST] == 1 { go = 0 } else { p = blk[NX_ZB_NEXT] }
242    }
243
244    // a declared content size must MATCH what the blocks produced
245    let declared: i64 = fld[NX_ZF_CONTENTSIZE]
246    if declared >= 0 { if declared != outp { return NX_ZSTD_ERR_MALFORMED } }
247    return outp
248}
nx_zstd_frame.nx source

`nx_zstd_frame.nx` source
