nx_zstd_seqdec.nx source
↩ module page · 185 lines · 6578 B
1// nx_zstd_seqdec.nx -- zstd sequence decoding: repeat offsets + the loop.
2//
3// The last piece of zstd's compressed path, built on RFC 8878 rather than
4// recollection. Two things here are easy to get subtly wrong and impossible
5// to notice without the spec.
6//
7// REPEAT OFFSETS SHIFT WHEN LITERALS_LENGTH IS ZERO. An Offset_Value of 1..3
8// names one of three remembered offsets -- but ONLY when the sequence carries
9// literals. When Literals_Length is zero the whole mapping slides by one:
10// 1 means Repeated_Offset2, 2 means Repeated_Offset3, and 3 means
11// Repeated_Offset1 MINUS ONE BYTE. That last case is not a typo and not a
12// repeat at all; it is a distinct encoding that exists because
13// Repeated_Offset1 is unreachable in that position. A decoder missing this
14// produces correct output until the first zero-literal sequence and wrong
15// output forever after -- and zero-literal sequences are common in
16// highly-repetitive data, which is exactly what zstd is good at.
17//
18// AN OFFSET_VALUE OF 1 WITH LITERALS DOES NOT REORDER THE HISTORY. Every other
19// repeat case moves the used offset to the front. Reordering on this one too
20// looks harmless and desynchronises the history from the encoder's.
21//
22// THE ORDER IS FIXED AND ASYMMETRIC. Extra bits are read offset, then match
23// length, then literals length. States are updated literals length, then match
24// length, then offset. The two orders are NOT the same, and all three states
25// share one bit reader, so any deviation shifts every subsequent read.
26//
27// genealogy_id: rfc8878_sequence_decoding
28// lineage_id: nx_zstd_seqdec_v1
29// license_tier: ORIGINAL
30
31import "nx_syscalls.nx"
32import "nx_zstd_fse.nx"
33import "nx_zstd_bits.nx"
34import "nx_zstd_fse_dec.nx"
35import "nx_zstd_seq.nx"
36
37const NX_REP_INIT1: i64 = 1
38const NX_REP_INIT2: i64 = 4
39const NX_REP_INIT3: i64 = 8
40
41// ===== the repeat-offset history ==================================
42//
43// rep[0..2] are Repeated_Offset1..3. The first block starts at 1, 4, 8.
44
45func nx_zstd_rep_init(rep: *i64) -> i64 {
46 rep[0] = NX_REP_INIT1
47 rep[1] = NX_REP_INIT2
48 rep[2] = NX_REP_INIT3
49 return 3
50}
51
52// Maps an Offset_Value to a real offset and updates the history in place.
53// Returns the offset, or -1 if the result would be unusable.
54func nx_zstd_rep_apply(rep: *i64, offset_value: i64, literals_length: i64) -> i64 {
55 if offset_value < 1 { return 0 - 1 }
56 if literals_length < 0 { return 0 - 1 }
57
58 var offset: i64 = 0
59
60 if offset_value > 3 {
61 offset = offset_value - 3
62 rep[2] = rep[1]
63 rep[1] = rep[0]
64 rep[0] = offset
65 return offset
66 }
67
68 // the zero-literal slide: 1->rep2, 2->rep3, 3->rep1 minus one byte
69 var idx: i64 = offset_value - 1
70 if literals_length == 0 { idx = offset_value }
71
72 if idx == 0 {
73 // Offset_Value 1 with literals: use Repeated_Offset1 and DO NOT reorder
74 return rep[0]
75 }
76
77 if idx == 3 {
78 offset = rep[0] - 1
79 } else {
80 offset = rep[idx]
81 }
82 if offset < 1 { return 0 - 1 }
83
84 // move the used value to the front; idx 1 leaves Repeated_Offset3 alone
85 if idx != 1 { rep[2] = rep[1] }
86 rep[1] = rep[0]
87 rep[0] = offset
88 return offset
89}
90
91// ===== one sequence ===============================================
92//
93// Reads three codes from three states over one shared stream, in the spec's
94// order. Writes (literal_length, match_length, offset) into out.
95// `last` suppresses the state update after the final sequence.
96
97func nx_zstd_seq_one(tll: *NxFseTable, tml: *NxFseTable, tof: *NxFseTable,
98 b: *NxZstdBits, st: *i64, rep: *i64, out: *i64, last: i64) -> i64 {
99 if b == (0 as *NxZstdBits) { return 0 }
100
101 // symbols come from the CURRENT states, before any update
102 let ll_code: i64 = nx_zstd_fse_state_symbol(tll, st[0])
103 let ml_code: i64 = nx_zstd_fse_state_symbol(tml, st[1])
104 let of_code: i64 = nx_zstd_fse_state_symbol(tof, st[2])
105 if ll_code < 0 { return 0 }
106 if ml_code < 0 { return 0 }
107 if of_code < 0 { return 0 }
108
109 let ll_base: i64 = nx_zstd_ll_base(ll_code)
110 let ml_base: i64 = nx_zstd_ml_base(ml_code)
111 let of_base: i64 = nx_zstd_of_base(of_code)
112 if ll_base < 0 { return 0 }
113 if ml_base < 0 { return 0 }
114 if of_base < 0 { return 0 }
115
116 // EXTRA BITS: offset, then match length, then literals length
117 var of_val: i64 = of_base
118 let of_bits: i64 = nx_zstd_of_extra(of_code)
119 if of_bits > 0 { of_val = of_val + nx_zstd_bits_read(b, of_bits) }
120
121 var ml: i64 = ml_base
122 let ml_bits: i64 = nx_zstd_ml_extra(ml_code)
123 if ml_bits > 0 { ml = ml + nx_zstd_bits_read(b, ml_bits) }
124
125 var ll: i64 = ll_base
126 let ll_bits: i64 = nx_zstd_ll_extra(ll_code)
127 if ll_bits > 0 { ll = ll + nx_zstd_bits_read(b, ll_bits) }
128
129 if b.overflow == 1 { return 0 }
130
131 let offset: i64 = nx_zstd_rep_apply(rep, of_val, ll)
132 if offset < 1 { return 0 }
133
134 out[0] = ll
135 out[1] = ml
136 out[2] = offset
137
138 // STATE UPDATES: literals length, then match length, then offset --
139 // a DIFFERENT order from the extra-bit reads above
140 if last == 0 {
141 st[0] = nx_zstd_fse_state_next(tll, b, st[0])
142 st[1] = nx_zstd_fse_state_next(tml, b, st[1])
143 st[2] = nx_zstd_fse_state_next(tof, b, st[2])
144 if st[0] < 0 { return 0 }
145 if st[1] < 0 { return 0 }
146 if st[2] < 0 { return 0 }
147 }
148 return 1
149}
150
151// ===== the whole sequence list ====================================
152//
153// Initialises the three states in the spec's order (literals length, offset,
154// match length) and decodes nseq sequences into a flat triple array.
155
156func nx_zstd_seq_decode_all(tll: *NxFseTable, tml: *NxFseTable, tof: *NxFseTable,
157 b: *NxZstdBits, nseq: i64, out: *i64) -> i64 {
158 if nseq < 0 { return 0 }
159 if nseq == 0 { return 1 }
160
161 let st: *i64 = sys_mmap(64) as *i64
162 // INIT ORDER: literals length, offset, match length
163 st[0] = nx_zstd_fse_state_init(tll, b)
164 st[2] = nx_zstd_fse_state_init(tof, b)
165 st[1] = nx_zstd_fse_state_init(tml, b)
166 if st[0] < 0 { return 0 }
167 if st[1] < 0 { return 0 }
168 if st[2] < 0 { return 0 }
169
170 let rep: *i64 = sys_mmap(64) as *i64
171 nx_zstd_rep_init(rep)
172
173 let one: *i64 = sys_mmap(64) as *i64
174 var i: i64 = 0
175 while i < nseq {
176 var last: i64 = 0
177 if i == nseq - 1 { last = 1 }
178 if nx_zstd_seq_one(tll, tml, tof, b, st, rep, one, last) != 1 { return 0 }
179 out[i * 3] = one[0]
180 out[i * 3 + 1] = one[1]
181 out[i * 3 + 2] = one[2]
182 i = i + 1
183 }
184 return 1
185}