seqdec_generic.go raw
1 //go:build !amd64 || appengine || !gc || noasm
2 // +build !amd64 appengine !gc noasm
3
4 package zstd
5
6 import (
7 "fmt"
8 "io"
9 )
10
11 // decode sequences from the stream with the provided history but without dictionary.
12 func (s *sequenceDecs) decodeSyncSimple(hist []byte) (bool, error) {
13 return false, nil
14 }
15
16 // decode sequences from the stream without the provided history.
17 func (s *sequenceDecs) decode(seqs []seqVals) error {
18 br := s.br
19
20 // Grab full sizes tables, to avoid bounds checks.
21 llTable, mlTable, ofTable := s.litLengths.fse.dt[:maxTablesize], s.matchLengths.fse.dt[:maxTablesize], s.offsets.fse.dt[:maxTablesize]
22 llState, mlState, ofState := s.litLengths.state.state, s.matchLengths.state.state, s.offsets.state.state
23 s.seqSize = 0
24 litRemain := len(s.literals)
25
26 maxBlockSize := maxCompressedBlockSize
27 if s.windowSize < maxBlockSize {
28 maxBlockSize = s.windowSize
29 }
30 for i := range seqs {
31 var ll, mo, ml int
32 if br.cursor > 4+((maxOffsetBits+16+16)>>3) {
33 // inlined function:
34 // ll, mo, ml = s.nextFast(br, llState, mlState, ofState)
35
36 // Final will not read from stream.
37 var llB, mlB, moB uint8
38 ll, llB = llState.final()
39 ml, mlB = mlState.final()
40 mo, moB = ofState.final()
41
42 // extra bits are stored in reverse order.
43 br.fillFast()
44 mo += br.getBits(moB)
45 if s.maxBits > 32 {
46 br.fillFast()
47 }
48 ml += br.getBits(mlB)
49 ll += br.getBits(llB)
50
51 if moB > 1 {
52 s.prevOffset[2] = s.prevOffset[1]
53 s.prevOffset[1] = s.prevOffset[0]
54 s.prevOffset[0] = mo
55 } else {
56 // mo = s.adjustOffset(mo, ll, moB)
57 // Inlined for rather big speedup
58 if ll == 0 {
59 // There is an exception though, when current sequence's literals_length = 0.
60 // In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
61 // an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
62 mo++
63 }
64
65 if mo == 0 {
66 mo = s.prevOffset[0]
67 } else {
68 var temp int
69 if mo == 3 {
70 temp = s.prevOffset[0] - 1
71 } else {
72 temp = s.prevOffset[mo]
73 }
74
75 if temp == 0 {
76 // 0 is not valid; input is corrupted; force offset to 1
77 println("WARNING: temp was 0")
78 temp = 1
79 }
80
81 if mo != 1 {
82 s.prevOffset[2] = s.prevOffset[1]
83 }
84 s.prevOffset[1] = s.prevOffset[0]
85 s.prevOffset[0] = temp
86 mo = temp
87 }
88 }
89 br.fillFast()
90 } else {
91 if br.overread() {
92 if debugDecoder {
93 printf("reading sequence %d, exceeded available data\n", i)
94 }
95 return io.ErrUnexpectedEOF
96 }
97 ll, mo, ml = s.next(br, llState, mlState, ofState)
98 br.fill()
99 }
100
101 if debugSequences {
102 println("Seq", i, "Litlen:", ll, "mo:", mo, "(abs) ml:", ml)
103 }
104 // Evaluate.
105 // We might be doing this async, so do it early.
106 if mo == 0 && ml > 0 {
107 return fmt.Errorf("zero matchoff and matchlen (%d) > 0", ml)
108 }
109 if ml > maxMatchLen {
110 return fmt.Errorf("match len (%d) bigger than max allowed length", ml)
111 }
112 s.seqSize += ll + ml
113 if s.seqSize > maxBlockSize {
114 return fmt.Errorf("output bigger than max block size (%d)", maxBlockSize)
115 }
116 litRemain -= ll
117 if litRemain < 0 {
118 return fmt.Errorf("unexpected literal count, want %d bytes, but only %d is available", ll, litRemain+ll)
119 }
120 seqs[i] = seqVals{
121 ll: ll,
122 ml: ml,
123 mo: mo,
124 }
125 if i == len(seqs)-1 {
126 // This is the last sequence, so we shouldn't update state.
127 break
128 }
129
130 // Manually inlined, ~ 5-20% faster
131 // Update all 3 states at once. Approx 20% faster.
132 nBits := llState.nbBits() + mlState.nbBits() + ofState.nbBits()
133 if nBits == 0 {
134 llState = llTable[llState.newState()&maxTableMask]
135 mlState = mlTable[mlState.newState()&maxTableMask]
136 ofState = ofTable[ofState.newState()&maxTableMask]
137 } else {
138 bits := br.get32BitsFast(nBits)
139 lowBits := uint16(bits >> ((ofState.nbBits() + mlState.nbBits()) & 31))
140 llState = llTable[(llState.newState()+lowBits)&maxTableMask]
141
142 lowBits = uint16(bits >> (ofState.nbBits() & 31))
143 lowBits &= bitMask[mlState.nbBits()&15]
144 mlState = mlTable[(mlState.newState()+lowBits)&maxTableMask]
145
146 lowBits = uint16(bits) & bitMask[ofState.nbBits()&15]
147 ofState = ofTable[(ofState.newState()+lowBits)&maxTableMask]
148 }
149 }
150 s.seqSize += litRemain
151 if s.seqSize > maxBlockSize {
152 return fmt.Errorf("output bigger than max block size (%d)", maxBlockSize)
153 }
154 err := br.close()
155 if err != nil {
156 printf("Closing sequences: %v, %+v\n", err, *br)
157 }
158 return err
159 }
160
161 // executeSimple handles cases when a dictionary is not used.
162 func (s *sequenceDecs) executeSimple(seqs []seqVals, hist []byte) error {
163 // Ensure we have enough output size...
164 if len(s.out)+s.seqSize > cap(s.out) {
165 addBytes := s.seqSize + len(s.out)
166 s.out = append(s.out, make([]byte, addBytes)...)
167 s.out = s.out[:len(s.out)-addBytes]
168 }
169
170 if debugDecoder {
171 printf("Execute %d seqs with literals: %d into %d bytes\n", len(seqs), len(s.literals), s.seqSize)
172 }
173
174 var t = len(s.out)
175 out := s.out[:t+s.seqSize]
176
177 for _, seq := range seqs {
178 // Add literals
179 copy(out[t:], s.literals[:seq.ll])
180 t += seq.ll
181 s.literals = s.literals[seq.ll:]
182
183 // Malformed input
184 if seq.mo > t+len(hist) || seq.mo > s.windowSize {
185 return fmt.Errorf("match offset (%d) bigger than current history (%d)", seq.mo, t+len(hist))
186 }
187
188 // Copy from history.
189 if v := seq.mo - t; v > 0 {
190 // v is the start position in history from end.
191 start := len(hist) - v
192 if seq.ml > v {
193 // Some goes into the current block.
194 // Copy remainder of history
195 copy(out[t:], hist[start:])
196 t += v
197 seq.ml -= v
198 } else {
199 copy(out[t:], hist[start:start+seq.ml])
200 t += seq.ml
201 continue
202 }
203 }
204
205 // We must be in the current buffer now
206 if seq.ml > 0 {
207 start := t - seq.mo
208 if seq.ml <= t-start {
209 // No overlap
210 copy(out[t:], out[start:start+seq.ml])
211 t += seq.ml
212 } else {
213 // Overlapping copy
214 // Extend destination slice and copy one byte at the time.
215 src := out[start : start+seq.ml]
216 dst := out[t:]
217 dst = dst[:len(src)]
218 t += len(src)
219 // Destination is the space we just added.
220 for i := range src {
221 dst[i] = src[i]
222 }
223 }
224 }
225 }
226 // Add final literals
227 copy(out[t:], s.literals)
228 if debugDecoder {
229 t += len(s.literals)
230 if t != len(out) {
231 panic(fmt.Errorf("length mismatch, want %d, got %d, ss: %d", len(out), t, s.seqSize))
232 }
233 }
234 s.out = out
235
236 return nil
237 }
238