blob: 9efe34feb34815ad118ef6ebeb51121f39d91e25 [file] [log] [blame]
Pragya Arya324337e2020-02-20 14:35:08 +05301// Copyright 2019+ Klaus Post. All rights reserved.
2// License information can be found in the LICENSE file.
3// Based on work by Yann Collet, released under BSD License.
4
5package zstd
6
7import (
8 "errors"
9 "fmt"
10)
11
12const (
13 tablelogAbsoluteMax = 9
14)
15
16const (
17 /*!MEMORY_USAGE :
18 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
19 * Increasing memory usage improves compression ratio
20 * Reduced memory usage can improve speed, due to cache effect
21 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
22 maxMemoryUsage = 11
23
24 maxTableLog = maxMemoryUsage - 2
25 maxTablesize = 1 << maxTableLog
26 maxTableMask = (1 << maxTableLog) - 1
27 minTablelog = 5
28 maxSymbolValue = 255
29)
30
31// fseDecoder provides temporary storage for compression and decompression.
32type fseDecoder struct {
33 dt [maxTablesize]decSymbol // Decompression table.
34 symbolLen uint16 // Length of active part of the symbol table.
35 actualTableLog uint8 // Selected tablelog.
36 maxBits uint8 // Maximum number of additional bits
37
38 // used for table creation to avoid allocations.
39 stateTable [256]uint16
40 norm [maxSymbolValue + 1]int16
41 preDefined bool
42}
43
44// tableStep returns the next table index.
45func tableStep(tableSize uint32) uint32 {
46 return (tableSize >> 1) + (tableSize >> 3) + 3
47}
48
49// readNCount will read the symbol distribution so decoding tables can be constructed.
50func (s *fseDecoder) readNCount(b *byteReader, maxSymbol uint16) error {
51 var (
52 charnum uint16
53 previous0 bool
54 )
55 if b.remain() < 4 {
56 return errors.New("input too small")
57 }
58 bitStream := b.Uint32()
59 nbBits := uint((bitStream & 0xF) + minTablelog) // extract tableLog
60 if nbBits > tablelogAbsoluteMax {
61 println("Invalid tablelog:", nbBits)
62 return errors.New("tableLog too large")
63 }
64 bitStream >>= 4
65 bitCount := uint(4)
66
67 s.actualTableLog = uint8(nbBits)
68 remaining := int32((1 << nbBits) + 1)
69 threshold := int32(1 << nbBits)
70 gotTotal := int32(0)
71 nbBits++
72
73 for remaining > 1 && charnum <= maxSymbol {
74 if previous0 {
75 //println("prev0")
76 n0 := charnum
77 for (bitStream & 0xFFFF) == 0xFFFF {
78 //println("24 x 0")
79 n0 += 24
80 if r := b.remain(); r > 5 {
81 b.advance(2)
82 bitStream = b.Uint32() >> bitCount
83 } else {
84 // end of bit stream
85 bitStream >>= 16
86 bitCount += 16
87 }
88 }
89 //printf("bitstream: %d, 0b%b", bitStream&3, bitStream)
90 for (bitStream & 3) == 3 {
91 n0 += 3
92 bitStream >>= 2
93 bitCount += 2
94 }
95 n0 += uint16(bitStream & 3)
96 bitCount += 2
97
98 if n0 > maxSymbolValue {
99 return errors.New("maxSymbolValue too small")
100 }
101 //println("inserting ", n0-charnum, "zeroes from idx", charnum, "ending before", n0)
102 for charnum < n0 {
103 s.norm[uint8(charnum)] = 0
104 charnum++
105 }
106
107 if r := b.remain(); r >= 7 || r+int(bitCount>>3) >= 4 {
108 b.advance(bitCount >> 3)
109 bitCount &= 7
110 bitStream = b.Uint32() >> bitCount
111 } else {
112 bitStream >>= 2
113 }
114 }
115
116 max := (2*threshold - 1) - remaining
117 var count int32
118
119 if int32(bitStream)&(threshold-1) < max {
120 count = int32(bitStream) & (threshold - 1)
121 if debug && nbBits < 1 {
122 panic("nbBits underflow")
123 }
124 bitCount += nbBits - 1
125 } else {
126 count = int32(bitStream) & (2*threshold - 1)
127 if count >= threshold {
128 count -= max
129 }
130 bitCount += nbBits
131 }
132
133 // extra accuracy
134 count--
135 if count < 0 {
136 // -1 means +1
137 remaining += count
138 gotTotal -= count
139 } else {
140 remaining -= count
141 gotTotal += count
142 }
143 s.norm[charnum&0xff] = int16(count)
144 charnum++
145 previous0 = count == 0
146 for remaining < threshold {
147 nbBits--
148 threshold >>= 1
149 }
150
151 //println("b.off:", b.off, "len:", len(b.b), "bc:", bitCount, "remain:", b.remain())
152 if r := b.remain(); r >= 7 || r+int(bitCount>>3) >= 4 {
153 b.advance(bitCount >> 3)
154 bitCount &= 7
155 } else {
156 bitCount -= (uint)(8 * (len(b.b) - 4 - b.off))
157 b.off = len(b.b) - 4
158 //println("b.off:", b.off, "len:", len(b.b), "bc:", bitCount, "iend", iend)
159 }
160 bitStream = b.Uint32() >> (bitCount & 31)
161 //printf("bitstream is now: 0b%b", bitStream)
162 }
163 s.symbolLen = charnum
164 if s.symbolLen <= 1 {
165 return fmt.Errorf("symbolLen (%d) too small", s.symbolLen)
166 }
167 if s.symbolLen > maxSymbolValue+1 {
168 return fmt.Errorf("symbolLen (%d) too big", s.symbolLen)
169 }
170 if remaining != 1 {
171 return fmt.Errorf("corruption detected (remaining %d != 1)", remaining)
172 }
173 if bitCount > 32 {
174 return fmt.Errorf("corruption detected (bitCount %d > 32)", bitCount)
175 }
176 if gotTotal != 1<<s.actualTableLog {
177 return fmt.Errorf("corruption detected (total %d != %d)", gotTotal, 1<<s.actualTableLog)
178 }
179 b.advance((bitCount + 7) >> 3)
180 // println(s.norm[:s.symbolLen], s.symbolLen)
181 return s.buildDtable()
182}
183
184// decSymbol contains information about a state entry,
185// Including the state offset base, the output symbol and
186// the number of bits to read for the low part of the destination state.
187// Using a composite uint64 is faster than a struct with separate members.
188type decSymbol uint64
189
190func newDecSymbol(nbits, addBits uint8, newState uint16, baseline uint32) decSymbol {
191 return decSymbol(nbits) | (decSymbol(addBits) << 8) | (decSymbol(newState) << 16) | (decSymbol(baseline) << 32)
192}
193
194func (d decSymbol) nbBits() uint8 {
195 return uint8(d)
196}
197
198func (d decSymbol) addBits() uint8 {
199 return uint8(d >> 8)
200}
201
202func (d decSymbol) newState() uint16 {
203 return uint16(d >> 16)
204}
205
206func (d decSymbol) baseline() uint32 {
207 return uint32(d >> 32)
208}
209
210func (d decSymbol) baselineInt() int {
211 return int(d >> 32)
212}
213
214func (d *decSymbol) set(nbits, addBits uint8, newState uint16, baseline uint32) {
215 *d = decSymbol(nbits) | (decSymbol(addBits) << 8) | (decSymbol(newState) << 16) | (decSymbol(baseline) << 32)
216}
217
218func (d *decSymbol) setNBits(nBits uint8) {
219 const mask = 0xffffffffffffff00
220 *d = (*d & mask) | decSymbol(nBits)
221}
222
223func (d *decSymbol) setAddBits(addBits uint8) {
224 const mask = 0xffffffffffff00ff
225 *d = (*d & mask) | (decSymbol(addBits) << 8)
226}
227
228func (d *decSymbol) setNewState(state uint16) {
229 const mask = 0xffffffff0000ffff
230 *d = (*d & mask) | decSymbol(state)<<16
231}
232
233func (d *decSymbol) setBaseline(baseline uint32) {
234 const mask = 0xffffffff
235 *d = (*d & mask) | decSymbol(baseline)<<32
236}
237
238func (d *decSymbol) setExt(addBits uint8, baseline uint32) {
239 const mask = 0xffff00ff
240 *d = (*d & mask) | (decSymbol(addBits) << 8) | (decSymbol(baseline) << 32)
241}
242
243// decSymbolValue returns the transformed decSymbol for the given symbol.
244func decSymbolValue(symb uint8, t []baseOffset) (decSymbol, error) {
245 if int(symb) >= len(t) {
246 return 0, fmt.Errorf("rle symbol %d >= max %d", symb, len(t))
247 }
248 lu := t[symb]
249 return newDecSymbol(0, lu.addBits, 0, lu.baseLine), nil
250}
251
252// setRLE will set the decoder til RLE mode.
253func (s *fseDecoder) setRLE(symbol decSymbol) {
254 s.actualTableLog = 0
255 s.maxBits = symbol.addBits()
256 s.dt[0] = symbol
257}
258
259// buildDtable will build the decoding table.
260func (s *fseDecoder) buildDtable() error {
261 tableSize := uint32(1 << s.actualTableLog)
262 highThreshold := tableSize - 1
263 symbolNext := s.stateTable[:256]
264
265 // Init, lay down lowprob symbols
266 {
267 for i, v := range s.norm[:s.symbolLen] {
268 if v == -1 {
269 s.dt[highThreshold].setAddBits(uint8(i))
270 highThreshold--
271 symbolNext[i] = 1
272 } else {
273 symbolNext[i] = uint16(v)
274 }
275 }
276 }
277 // Spread symbols
278 {
279 tableMask := tableSize - 1
280 step := tableStep(tableSize)
281 position := uint32(0)
282 for ss, v := range s.norm[:s.symbolLen] {
283 for i := 0; i < int(v); i++ {
284 s.dt[position].setAddBits(uint8(ss))
285 position = (position + step) & tableMask
286 for position > highThreshold {
287 // lowprob area
288 position = (position + step) & tableMask
289 }
290 }
291 }
292 if position != 0 {
293 // position must reach all cells once, otherwise normalizedCounter is incorrect
294 return errors.New("corrupted input (position != 0)")
295 }
296 }
297
298 // Build Decoding table
299 {
300 tableSize := uint16(1 << s.actualTableLog)
301 for u, v := range s.dt[:tableSize] {
302 symbol := v.addBits()
303 nextState := symbolNext[symbol]
304 symbolNext[symbol] = nextState + 1
305 nBits := s.actualTableLog - byte(highBits(uint32(nextState)))
306 s.dt[u&maxTableMask].setNBits(nBits)
307 newState := (nextState << nBits) - tableSize
308 if newState > tableSize {
309 return fmt.Errorf("newState (%d) outside table size (%d)", newState, tableSize)
310 }
311 if newState == uint16(u) && nBits == 0 {
312 // Seems weird that this is possible with nbits > 0.
313 return fmt.Errorf("newState (%d) == oldState (%d) and no bits", newState, u)
314 }
315 s.dt[u&maxTableMask].setNewState(newState)
316 }
317 }
318 return nil
319}
320
321// transform will transform the decoder table into a table usable for
322// decoding without having to apply the transformation while decoding.
323// The state will contain the base value and the number of bits to read.
324func (s *fseDecoder) transform(t []baseOffset) error {
325 tableSize := uint16(1 << s.actualTableLog)
326 s.maxBits = 0
327 for i, v := range s.dt[:tableSize] {
328 add := v.addBits()
329 if int(add) >= len(t) {
330 return fmt.Errorf("invalid decoding table entry %d, symbol %d >= max (%d)", i, v.addBits(), len(t))
331 }
332 lu := t[add]
333 if lu.addBits > s.maxBits {
334 s.maxBits = lu.addBits
335 }
336 v.setExt(lu.addBits, lu.baseLine)
337 s.dt[i] = v
338 }
339 return nil
340}
341
342type fseState struct {
343 dt []decSymbol
344 state decSymbol
345}
346
347// Initialize and decodeAsync first state and symbol.
348func (s *fseState) init(br *bitReader, tableLog uint8, dt []decSymbol) {
349 s.dt = dt
350 br.fill()
351 s.state = dt[br.getBits(tableLog)]
352}
353
354// next returns the current symbol and sets the next state.
355// At least tablelog bits must be available in the bit reader.
356func (s *fseState) next(br *bitReader) {
357 lowBits := uint16(br.getBits(s.state.nbBits()))
358 s.state = s.dt[s.state.newState()+lowBits]
359}
360
361// finished returns true if all bits have been read from the bitstream
362// and the next state would require reading bits from the input.
363func (s *fseState) finished(br *bitReader) bool {
364 return br.finished() && s.state.nbBits() > 0
365}
366
367// final returns the current state symbol without decoding the next.
368func (s *fseState) final() (int, uint8) {
369 return s.state.baselineInt(), s.state.addBits()
370}
371
372// final returns the current state symbol without decoding the next.
373func (s decSymbol) final() (int, uint8) {
374 return s.baselineInt(), s.addBits()
375}
376
377// nextFast returns the next symbol and sets the next state.
378// This can only be used if no symbols are 0 bits.
379// At least tablelog bits must be available in the bit reader.
380func (s *fseState) nextFast(br *bitReader) (uint32, uint8) {
381 lowBits := uint16(br.getBitsFast(s.state.nbBits()))
382 s.state = s.dt[s.state.newState()+lowBits]
383 return s.state.baseline(), s.state.addBits()
384}