cubefs

1
package huff0
2

3
import (
4
	"errors"
5
	"fmt"
6
	"io"
7
	"sync"
8

9
	"github.com/klauspost/compress/fse"
10
)
11

12
type dTable struct {
13
	single []dEntrySingle
14
	double []dEntryDouble
15
}
16

17
// single-symbols decoding
18
type dEntrySingle struct {
19
	entry uint16
20
}
21

22
// double-symbols decoding
23
type dEntryDouble struct {
24
	seq   [4]byte
25
	nBits uint8
26
	len   uint8
27
}
28

29
// Uses special code for all tables that are < 8 bits.
30
const use8BitTables = true
31

32
// ReadTable will read a table from the input.
33
// The size of the input may be larger than the table definition.
34
// Any content remaining after the table definition will be returned.
35
// If no Scratch is provided a new one is allocated.
36
// The returned Scratch can be used for encoding or decoding input using this table.
37
func ReadTable(in []byte, s *Scratch) (s2 *Scratch, remain []byte, err error) {
38
	s, err = s.prepare(in)
39
	if err != nil {
40
		return s, nil, err
41
	}
42
	if len(in) <= 1 {
43
		return s, nil, errors.New("input too small for table")
44
	}
45
	iSize := in[0]
46
	in = in[1:]
47
	if iSize >= 128 {
48
		// Uncompressed
49
		oSize := iSize - 127
50
		iSize = (oSize + 1) / 2
51
		if int(iSize) > len(in) {
52
			return s, nil, errors.New("input too small for table")
53
		}
54
		for n := uint8(0); n < oSize; n += 2 {
55
			v := in[n/2]
56
			s.huffWeight[n] = v >> 4
57
			s.huffWeight[n+1] = v & 15
58
		}
59
		s.symbolLen = uint16(oSize)
60
		in = in[iSize:]
61
	} else {
62
		if len(in) < int(iSize) {
63
			return s, nil, fmt.Errorf("input too small for table, want %d bytes, have %d", iSize, len(in))
64
		}
65
		// FSE compressed weights
66
		s.fse.DecompressLimit = 255
67
		hw := s.huffWeight[:]
68
		s.fse.Out = hw
69
		b, err := fse.Decompress(in[:iSize], s.fse)
70
		s.fse.Out = nil
71
		if err != nil {
72
			return s, nil, err
73
		}
74
		if len(b) > 255 {
75
			return s, nil, errors.New("corrupt input: output table too large")
76
		}
77
		s.symbolLen = uint16(len(b))
78
		in = in[iSize:]
79
	}
80

81
	// collect weight stats
82
	var rankStats [16]uint32
83
	weightTotal := uint32(0)
84
	for _, v := range s.huffWeight[:s.symbolLen] {
85
		if v > tableLogMax {
86
			return s, nil, errors.New("corrupt input: weight too large")
87
		}
88
		v2 := v & 15
89
		rankStats[v2]++
90
		// (1 << (v2-1)) is slower since the compiler cannot prove that v2 isn't 0.
91
		weightTotal += (1 << v2) >> 1
92
	}
93
	if weightTotal == 0 {
94
		return s, nil, errors.New("corrupt input: weights zero")
95
	}
96

97
	// get last non-null symbol weight (implied, total must be 2^n)
98
	{
99
		tableLog := highBit32(weightTotal) + 1
100
		if tableLog > tableLogMax {
101
			return s, nil, errors.New("corrupt input: tableLog too big")
102
		}
103
		s.actualTableLog = uint8(tableLog)
104
		// determine last weight
105
		{
106
			total := uint32(1) << tableLog
107
			rest := total - weightTotal
108
			verif := uint32(1) << highBit32(rest)
109
			lastWeight := highBit32(rest) + 1
110
			if verif != rest {
111
				// last value must be a clean power of 2
112
				return s, nil, errors.New("corrupt input: last value not power of two")
113
			}
114
			s.huffWeight[s.symbolLen] = uint8(lastWeight)
115
			s.symbolLen++
116
			rankStats[lastWeight]++
117
		}
118
	}
119

120
	if (rankStats[1] < 2) || (rankStats[1]&1 != 0) {
121
		// by construction : at least 2 elts of rank 1, must be even
122
		return s, nil, errors.New("corrupt input: min elt size, even check failed ")
123
	}
124

125
	// TODO: Choose between single/double symbol decoding
126

127
	// Calculate starting value for each rank
128
	{
129
		var nextRankStart uint32
130
		for n := uint8(1); n < s.actualTableLog+1; n++ {
131
			current := nextRankStart
132
			nextRankStart += rankStats[n] << (n - 1)
133
			rankStats[n] = current
134
		}
135
	}
136

137
	// fill DTable (always full size)
138
	tSize := 1 << tableLogMax
139
	if len(s.dt.single) != tSize {
140
		s.dt.single = make([]dEntrySingle, tSize)
141
	}
142
	cTable := s.prevTable
143
	if cap(cTable) < maxSymbolValue+1 {
144
		cTable = make([]cTableEntry, 0, maxSymbolValue+1)
145
	}
146
	cTable = cTable[:maxSymbolValue+1]
147
	s.prevTable = cTable[:s.symbolLen]
148
	s.prevTableLog = s.actualTableLog
149

150
	for n, w := range s.huffWeight[:s.symbolLen] {
151
		if w == 0 {
152
			cTable[n] = cTableEntry{
153
				val:   0,
154
				nBits: 0,
155
			}
156
			continue
157
		}
158
		length := (uint32(1) << w) >> 1
159
		d := dEntrySingle{
160
			entry: uint16(s.actualTableLog+1-w) | (uint16(n) << 8),
161
		}
162

163
		rank := &rankStats[w]
164
		cTable[n] = cTableEntry{
165
			val:   uint16(*rank >> (w - 1)),
166
			nBits: uint8(d.entry),
167
		}
168

169
		single := s.dt.single[*rank : *rank+length]
170
		for i := range single {
171
			single[i] = d
172
		}
173
		*rank += length
174
	}
175

176
	return s, in, nil
177
}
178

179
// Decompress1X will decompress a 1X encoded stream.
180
// The length of the supplied input must match the end of a block exactly.
181
// Before this is called, the table must be initialized with ReadTable unless
182
// the encoder re-used the table.
183
// deprecated: Use the stateless Decoder() to get a concurrent version.
184
func (s *Scratch) Decompress1X(in []byte) (out []byte, err error) {
185
	if cap(s.Out) < s.MaxDecodedSize {
186
		s.Out = make([]byte, s.MaxDecodedSize)
187
	}
188
	s.Out = s.Out[:0:s.MaxDecodedSize]
189
	s.Out, err = s.Decoder().Decompress1X(s.Out, in)
190
	return s.Out, err
191
}
192

193
// Decompress4X will decompress a 4X encoded stream.
194
// Before this is called, the table must be initialized with ReadTable unless
195
// the encoder re-used the table.
196
// The length of the supplied input must match the end of a block exactly.
197
// The destination size of the uncompressed data must be known and provided.
198
// deprecated: Use the stateless Decoder() to get a concurrent version.
199
func (s *Scratch) Decompress4X(in []byte, dstSize int) (out []byte, err error) {
200
	if dstSize > s.MaxDecodedSize {
201
		return nil, ErrMaxDecodedSizeExceeded
202
	}
203
	if cap(s.Out) < dstSize {
204
		s.Out = make([]byte, s.MaxDecodedSize)
205
	}
206
	s.Out = s.Out[:0:dstSize]
207
	s.Out, err = s.Decoder().Decompress4X(s.Out, in)
208
	return s.Out, err
209
}
210

211
// Decoder will return a stateless decoder that can be used by multiple
212
// decompressors concurrently.
213
// Before this is called, the table must be initialized with ReadTable.
214
// The Decoder is still linked to the scratch buffer so that cannot be reused.
215
// However, it is safe to discard the scratch.
216
func (s *Scratch) Decoder() *Decoder {
217
	return &Decoder{
218
		dt:             s.dt,
219
		actualTableLog: s.actualTableLog,
220
		bufs:           &s.decPool,
221
	}
222
}
223

224
// Decoder provides stateless decoding.
225
type Decoder struct {
226
	dt             dTable
227
	actualTableLog uint8
228
	bufs           *sync.Pool
229
}
230

231
func (d *Decoder) buffer() *[4][256]byte {
232
	buf, ok := d.bufs.Get().(*[4][256]byte)
233
	if ok {
234
		return buf
235
	}
236
	return &[4][256]byte{}
237
}
238

239
// Decompress1X will decompress a 1X encoded stream.
240
// The cap of the output buffer will be the maximum decompressed size.
241
// The length of the supplied input must match the end of a block exactly.
242
func (d *Decoder) Decompress1X(dst, src []byte) ([]byte, error) {
243
	if len(d.dt.single) == 0 {
244
		return nil, errors.New("no table loaded")
245
	}
246
	if use8BitTables && d.actualTableLog <= 8 {
247
		return d.decompress1X8Bit(dst, src)
248
	}
249
	var br bitReaderShifted
250
	err := br.init(src)
251
	if err != nil {
252
		return dst, err
253
	}
254
	maxDecodedSize := cap(dst)
255
	dst = dst[:0]
256

257
	// Avoid bounds check by always having full sized table.
258
	const tlSize = 1 << tableLogMax
259
	const tlMask = tlSize - 1
260
	dt := d.dt.single[:tlSize]
261

262
	// Use temp table to avoid bound checks/append penalty.
263
	bufs := d.buffer()
264
	buf := &bufs[0]
265
	var off uint8
266

267
	for br.off >= 8 {
268
		br.fillFast()
269
		v := dt[br.peekBitsFast(d.actualTableLog)&tlMask]
270
		br.advance(uint8(v.entry))
271
		buf[off+0] = uint8(v.entry >> 8)
272

273
		v = dt[br.peekBitsFast(d.actualTableLog)&tlMask]
274
		br.advance(uint8(v.entry))
275
		buf[off+1] = uint8(v.entry >> 8)
276

277
		// Refill
278
		br.fillFast()
279

280
		v = dt[br.peekBitsFast(d.actualTableLog)&tlMask]
281
		br.advance(uint8(v.entry))
282
		buf[off+2] = uint8(v.entry >> 8)
283

284
		v = dt[br.peekBitsFast(d.actualTableLog)&tlMask]
285
		br.advance(uint8(v.entry))
286
		buf[off+3] = uint8(v.entry >> 8)
287

288
		off += 4
289
		if off == 0 {
290
			if len(dst)+256 > maxDecodedSize {
291
				br.close()
292
				d.bufs.Put(bufs)
293
				return nil, ErrMaxDecodedSizeExceeded
294
			}
295
			dst = append(dst, buf[:]...)
296
		}
297
	}
298

299
	if len(dst)+int(off) > maxDecodedSize {
300
		d.bufs.Put(bufs)
301
		br.close()
302
		return nil, ErrMaxDecodedSizeExceeded
303
	}
304
	dst = append(dst, buf[:off]...)
305

306
	// br < 8, so uint8 is fine
307
	bitsLeft := uint8(br.off)*8 + 64 - br.bitsRead
308
	for bitsLeft > 0 {
309
		br.fill()
310
		if false && br.bitsRead >= 32 {
311
			if br.off >= 4 {
312
				v := br.in[br.off-4:]
313
				v = v[:4]
314
				low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
315
				br.value = (br.value << 32) | uint64(low)
316
				br.bitsRead -= 32
317
				br.off -= 4
318
			} else {
319
				for br.off > 0 {
320
					br.value = (br.value << 8) | uint64(br.in[br.off-1])
321
					br.bitsRead -= 8
322
					br.off--
323
				}
324
			}
325
		}
326
		if len(dst) >= maxDecodedSize {
327
			d.bufs.Put(bufs)
328
			br.close()
329
			return nil, ErrMaxDecodedSizeExceeded
330
		}
331
		v := d.dt.single[br.peekBitsFast(d.actualTableLog)&tlMask]
332
		nBits := uint8(v.entry)
333
		br.advance(nBits)
334
		bitsLeft -= nBits
335
		dst = append(dst, uint8(v.entry>>8))
336
	}
337
	d.bufs.Put(bufs)
338
	return dst, br.close()
339
}
340

341
// decompress1X8Bit will decompress a 1X encoded stream with tablelog <= 8.
342
// The cap of the output buffer will be the maximum decompressed size.
343
// The length of the supplied input must match the end of a block exactly.
344
func (d *Decoder) decompress1X8Bit(dst, src []byte) ([]byte, error) {
345
	if d.actualTableLog == 8 {
346
		return d.decompress1X8BitExactly(dst, src)
347
	}
348
	var br bitReaderBytes
349
	err := br.init(src)
350
	if err != nil {
351
		return dst, err
352
	}
353
	maxDecodedSize := cap(dst)
354
	dst = dst[:0]
355

356
	// Avoid bounds check by always having full sized table.
357
	dt := d.dt.single[:256]
358

359
	// Use temp table to avoid bound checks/append penalty.
360
	bufs := d.buffer()
361
	buf := &bufs[0]
362
	var off uint8
363

364
	switch d.actualTableLog {
365
	case 8:
366
		const shift = 8 - 8
367
		for br.off >= 4 {
368
			br.fillFast()
369
			v := dt[uint8(br.value>>(56+shift))]
370
			br.advance(uint8(v.entry))
371
			buf[off+0] = uint8(v.entry >> 8)
372

373
			v = dt[uint8(br.value>>(56+shift))]
374
			br.advance(uint8(v.entry))
375
			buf[off+1] = uint8(v.entry >> 8)
376

377
			v = dt[uint8(br.value>>(56+shift))]
378
			br.advance(uint8(v.entry))
379
			buf[off+2] = uint8(v.entry >> 8)
380

381
			v = dt[uint8(br.value>>(56+shift))]
382
			br.advance(uint8(v.entry))
383
			buf[off+3] = uint8(v.entry >> 8)
384

385
			off += 4
386
			if off == 0 {
387
				if len(dst)+256 > maxDecodedSize {
388
					br.close()
389
					d.bufs.Put(bufs)
390
					return nil, ErrMaxDecodedSizeExceeded
391
				}
392
				dst = append(dst, buf[:]...)
393
			}
394
		}
395
	case 7:
396
		const shift = 8 - 7
397
		for br.off >= 4 {
398
			br.fillFast()
399
			v := dt[uint8(br.value>>(56+shift))]
400
			br.advance(uint8(v.entry))
401
			buf[off+0] = uint8(v.entry >> 8)
402

403
			v = dt[uint8(br.value>>(56+shift))]
404
			br.advance(uint8(v.entry))
405
			buf[off+1] = uint8(v.entry >> 8)
406

407
			v = dt[uint8(br.value>>(56+shift))]
408
			br.advance(uint8(v.entry))
409
			buf[off+2] = uint8(v.entry >> 8)
410

411
			v = dt[uint8(br.value>>(56+shift))]
412
			br.advance(uint8(v.entry))
413
			buf[off+3] = uint8(v.entry >> 8)
414

415
			off += 4
416
			if off == 0 {
417
				if len(dst)+256 > maxDecodedSize {
418
					br.close()
419
					d.bufs.Put(bufs)
420
					return nil, ErrMaxDecodedSizeExceeded
421
				}
422
				dst = append(dst, buf[:]...)
423
			}
424
		}
425
	case 6:
426
		const shift = 8 - 6
427
		for br.off >= 4 {
428
			br.fillFast()
429
			v := dt[uint8(br.value>>(56+shift))]
430
			br.advance(uint8(v.entry))
431
			buf[off+0] = uint8(v.entry >> 8)
432

433
			v = dt[uint8(br.value>>(56+shift))]
434
			br.advance(uint8(v.entry))
435
			buf[off+1] = uint8(v.entry >> 8)
436

437
			v = dt[uint8(br.value>>(56+shift))]
438
			br.advance(uint8(v.entry))
439
			buf[off+2] = uint8(v.entry >> 8)
440

441
			v = dt[uint8(br.value>>(56+shift))]
442
			br.advance(uint8(v.entry))
443
			buf[off+3] = uint8(v.entry >> 8)
444

445
			off += 4
446
			if off == 0 {
447
				if len(dst)+256 > maxDecodedSize {
448
					d.bufs.Put(bufs)
449
					br.close()
450
					return nil, ErrMaxDecodedSizeExceeded
451
				}
452
				dst = append(dst, buf[:]...)
453
			}
454
		}
455
	case 5:
456
		const shift = 8 - 5
457
		for br.off >= 4 {
458
			br.fillFast()
459
			v := dt[uint8(br.value>>(56+shift))]
460
			br.advance(uint8(v.entry))
461
			buf[off+0] = uint8(v.entry >> 8)
462

463
			v = dt[uint8(br.value>>(56+shift))]
464
			br.advance(uint8(v.entry))
465
			buf[off+1] = uint8(v.entry >> 8)
466

467
			v = dt[uint8(br.value>>(56+shift))]
468
			br.advance(uint8(v.entry))
469
			buf[off+2] = uint8(v.entry >> 8)
470

471
			v = dt[uint8(br.value>>(56+shift))]
472
			br.advance(uint8(v.entry))
473
			buf[off+3] = uint8(v.entry >> 8)
474

475
			off += 4
476
			if off == 0 {
477
				if len(dst)+256 > maxDecodedSize {
478
					d.bufs.Put(bufs)
479
					br.close()
480
					return nil, ErrMaxDecodedSizeExceeded
481
				}
482
				dst = append(dst, buf[:]...)
483
			}
484
		}
485
	case 4:
486
		const shift = 8 - 4
487
		for br.off >= 4 {
488
			br.fillFast()
489
			v := dt[uint8(br.value>>(56+shift))]
490
			br.advance(uint8(v.entry))
491
			buf[off+0] = uint8(v.entry >> 8)
492

493
			v = dt[uint8(br.value>>(56+shift))]
494
			br.advance(uint8(v.entry))
495
			buf[off+1] = uint8(v.entry >> 8)
496

497
			v = dt[uint8(br.value>>(56+shift))]
498
			br.advance(uint8(v.entry))
499
			buf[off+2] = uint8(v.entry >> 8)
500

501
			v = dt[uint8(br.value>>(56+shift))]
502
			br.advance(uint8(v.entry))
503
			buf[off+3] = uint8(v.entry >> 8)
504

505
			off += 4
506
			if off == 0 {
507
				if len(dst)+256 > maxDecodedSize {
508
					d.bufs.Put(bufs)
509
					br.close()
510
					return nil, ErrMaxDecodedSizeExceeded
511
				}
512
				dst = append(dst, buf[:]...)
513
			}
514
		}
515
	case 3:
516
		const shift = 8 - 3
517
		for br.off >= 4 {
518
			br.fillFast()
519
			v := dt[uint8(br.value>>(56+shift))]
520
			br.advance(uint8(v.entry))
521
			buf[off+0] = uint8(v.entry >> 8)
522

523
			v = dt[uint8(br.value>>(56+shift))]
524
			br.advance(uint8(v.entry))
525
			buf[off+1] = uint8(v.entry >> 8)
526

527
			v = dt[uint8(br.value>>(56+shift))]
528
			br.advance(uint8(v.entry))
529
			buf[off+2] = uint8(v.entry >> 8)
530

531
			v = dt[uint8(br.value>>(56+shift))]
532
			br.advance(uint8(v.entry))
533
			buf[off+3] = uint8(v.entry >> 8)
534

535
			off += 4
536
			if off == 0 {
537
				if len(dst)+256 > maxDecodedSize {
538
					d.bufs.Put(bufs)
539
					br.close()
540
					return nil, ErrMaxDecodedSizeExceeded
541
				}
542
				dst = append(dst, buf[:]...)
543
			}
544
		}
545
	case 2:
546
		const shift = 8 - 2
547
		for br.off >= 4 {
548
			br.fillFast()
549
			v := dt[uint8(br.value>>(56+shift))]
550
			br.advance(uint8(v.entry))
551
			buf[off+0] = uint8(v.entry >> 8)
552

553
			v = dt[uint8(br.value>>(56+shift))]
554
			br.advance(uint8(v.entry))
555
			buf[off+1] = uint8(v.entry >> 8)
556

557
			v = dt[uint8(br.value>>(56+shift))]
558
			br.advance(uint8(v.entry))
559
			buf[off+2] = uint8(v.entry >> 8)
560

561
			v = dt[uint8(br.value>>(56+shift))]
562
			br.advance(uint8(v.entry))
563
			buf[off+3] = uint8(v.entry >> 8)
564

565
			off += 4
566
			if off == 0 {
567
				if len(dst)+256 > maxDecodedSize {
568
					d.bufs.Put(bufs)
569
					br.close()
570
					return nil, ErrMaxDecodedSizeExceeded
571
				}
572
				dst = append(dst, buf[:]...)
573
			}
574
		}
575
	case 1:
576
		const shift = 8 - 1
577
		for br.off >= 4 {
578
			br.fillFast()
579
			v := dt[uint8(br.value>>(56+shift))]
580
			br.advance(uint8(v.entry))
581
			buf[off+0] = uint8(v.entry >> 8)
582

583
			v = dt[uint8(br.value>>(56+shift))]
584
			br.advance(uint8(v.entry))
585
			buf[off+1] = uint8(v.entry >> 8)
586

587
			v = dt[uint8(br.value>>(56+shift))]
588
			br.advance(uint8(v.entry))
589
			buf[off+2] = uint8(v.entry >> 8)
590

591
			v = dt[uint8(br.value>>(56+shift))]
592
			br.advance(uint8(v.entry))
593
			buf[off+3] = uint8(v.entry >> 8)
594

595
			off += 4
596
			if off == 0 {
597
				if len(dst)+256 > maxDecodedSize {
598
					d.bufs.Put(bufs)
599
					br.close()
600
					return nil, ErrMaxDecodedSizeExceeded
601
				}
602
				dst = append(dst, buf[:]...)
603
			}
604
		}
605
	default:
606
		d.bufs.Put(bufs)
607
		return nil, fmt.Errorf("invalid tablelog: %d", d.actualTableLog)
608
	}
609

610
	if len(dst)+int(off) > maxDecodedSize {
611
		d.bufs.Put(bufs)
612
		br.close()
613
		return nil, ErrMaxDecodedSizeExceeded
614
	}
615
	dst = append(dst, buf[:off]...)
616

617
	// br < 4, so uint8 is fine
618
	bitsLeft := int8(uint8(br.off)*8 + (64 - br.bitsRead))
619
	shift := (8 - d.actualTableLog) & 7
620

621
	for bitsLeft > 0 {
622
		if br.bitsRead >= 64-8 {
623
			for br.off > 0 {
624
				br.value |= uint64(br.in[br.off-1]) << (br.bitsRead - 8)
625
				br.bitsRead -= 8
626
				br.off--
627
			}
628
		}
629
		if len(dst) >= maxDecodedSize {
630
			br.close()
631
			d.bufs.Put(bufs)
632
			return nil, ErrMaxDecodedSizeExceeded
633
		}
634
		v := dt[br.peekByteFast()>>shift]
635
		nBits := uint8(v.entry)
636
		br.advance(nBits)
637
		bitsLeft -= int8(nBits)
638
		dst = append(dst, uint8(v.entry>>8))
639
	}
640
	d.bufs.Put(bufs)
641
	return dst, br.close()
642
}
643

644
// decompress1X8Bit will decompress a 1X encoded stream with tablelog <= 8.
645
// The cap of the output buffer will be the maximum decompressed size.
646
// The length of the supplied input must match the end of a block exactly.
647
func (d *Decoder) decompress1X8BitExactly(dst, src []byte) ([]byte, error) {
648
	var br bitReaderBytes
649
	err := br.init(src)
650
	if err != nil {
651
		return dst, err
652
	}
653
	maxDecodedSize := cap(dst)
654
	dst = dst[:0]
655

656
	// Avoid bounds check by always having full sized table.
657
	dt := d.dt.single[:256]
658

659
	// Use temp table to avoid bound checks/append penalty.
660
	bufs := d.buffer()
661
	buf := &bufs[0]
662
	var off uint8
663

664
	const shift = 56
665

666
	//fmt.Printf("mask: %b, tl:%d\n", mask, d.actualTableLog)
667
	for br.off >= 4 {
668
		br.fillFast()
669
		v := dt[uint8(br.value>>shift)]
670
		br.advance(uint8(v.entry))
671
		buf[off+0] = uint8(v.entry >> 8)
672

673
		v = dt[uint8(br.value>>shift)]
674
		br.advance(uint8(v.entry))
675
		buf[off+1] = uint8(v.entry >> 8)
676

677
		v = dt[uint8(br.value>>shift)]
678
		br.advance(uint8(v.entry))
679
		buf[off+2] = uint8(v.entry >> 8)
680

681
		v = dt[uint8(br.value>>shift)]
682
		br.advance(uint8(v.entry))
683
		buf[off+3] = uint8(v.entry >> 8)
684

685
		off += 4
686
		if off == 0 {
687
			if len(dst)+256 > maxDecodedSize {
688
				d.bufs.Put(bufs)
689
				br.close()
690
				return nil, ErrMaxDecodedSizeExceeded
691
			}
692
			dst = append(dst, buf[:]...)
693
		}
694
	}
695

696
	if len(dst)+int(off) > maxDecodedSize {
697
		d.bufs.Put(bufs)
698
		br.close()
699
		return nil, ErrMaxDecodedSizeExceeded
700
	}
701
	dst = append(dst, buf[:off]...)
702

703
	// br < 4, so uint8 is fine
704
	bitsLeft := int8(uint8(br.off)*8 + (64 - br.bitsRead))
705
	for bitsLeft > 0 {
706
		if br.bitsRead >= 64-8 {
707
			for br.off > 0 {
708
				br.value |= uint64(br.in[br.off-1]) << (br.bitsRead - 8)
709
				br.bitsRead -= 8
710
				br.off--
711
			}
712
		}
713
		if len(dst) >= maxDecodedSize {
714
			d.bufs.Put(bufs)
715
			br.close()
716
			return nil, ErrMaxDecodedSizeExceeded
717
		}
718
		v := dt[br.peekByteFast()]
719
		nBits := uint8(v.entry)
720
		br.advance(nBits)
721
		bitsLeft -= int8(nBits)
722
		dst = append(dst, uint8(v.entry>>8))
723
	}
724
	d.bufs.Put(bufs)
725
	return dst, br.close()
726
}
727

728
// Decompress4X will decompress a 4X encoded stream.
729
// The length of the supplied input must match the end of a block exactly.
730
// The *capacity* of the dst slice must match the destination size of
731
// the uncompressed data exactly.
732
func (d *Decoder) Decompress4X(dst, src []byte) ([]byte, error) {
733
	if len(d.dt.single) == 0 {
734
		return nil, errors.New("no table loaded")
735
	}
736
	if len(src) < 6+(4*1) {
737
		return nil, errors.New("input too small")
738
	}
739
	if use8BitTables && d.actualTableLog <= 8 {
740
		return d.decompress4X8bit(dst, src)
741
	}
742

743
	var br [4]bitReaderShifted
744
	// Decode "jump table"
745
	start := 6
746
	for i := 0; i < 3; i++ {
747
		length := int(src[i*2]) | (int(src[i*2+1]) << 8)
748
		if start+length >= len(src) {
749
			return nil, errors.New("truncated input (or invalid offset)")
750
		}
751
		err := br[i].init(src[start : start+length])
752
		if err != nil {
753
			return nil, err
754
		}
755
		start += length
756
	}
757
	err := br[3].init(src[start:])
758
	if err != nil {
759
		return nil, err
760
	}
761

762
	// destination, offset to match first output
763
	dstSize := cap(dst)
764
	dst = dst[:dstSize]
765
	out := dst
766
	dstEvery := (dstSize + 3) / 4
767

768
	const tlSize = 1 << tableLogMax
769
	const tlMask = tlSize - 1
770
	single := d.dt.single[:tlSize]
771

772
	// Use temp table to avoid bound checks/append penalty.
773
	buf := d.buffer()
774
	var off uint8
775
	var decoded int
776

777
	// Decode 2 values from each decoder/loop.
778
	const bufoff = 256
779
	for {
780
		if br[0].off < 4 || br[1].off < 4 || br[2].off < 4 || br[3].off < 4 {
781
			break
782
		}
783

784
		{
785
			const stream = 0
786
			const stream2 = 1
787
			br[stream].fillFast()
788
			br[stream2].fillFast()
789

790
			val := br[stream].peekBitsFast(d.actualTableLog)
791
			val2 := br[stream2].peekBitsFast(d.actualTableLog)
792
			v := single[val&tlMask]
793
			v2 := single[val2&tlMask]
794
			br[stream].advance(uint8(v.entry))
795
			br[stream2].advance(uint8(v2.entry))
796
			buf[stream][off] = uint8(v.entry >> 8)
797
			buf[stream2][off] = uint8(v2.entry >> 8)
798

799
			val = br[stream].peekBitsFast(d.actualTableLog)
800
			val2 = br[stream2].peekBitsFast(d.actualTableLog)
801
			v = single[val&tlMask]
802
			v2 = single[val2&tlMask]
803
			br[stream].advance(uint8(v.entry))
804
			br[stream2].advance(uint8(v2.entry))
805
			buf[stream][off+1] = uint8(v.entry >> 8)
806
			buf[stream2][off+1] = uint8(v2.entry >> 8)
807
		}
808

809
		{
810
			const stream = 2
811
			const stream2 = 3
812
			br[stream].fillFast()
813
			br[stream2].fillFast()
814

815
			val := br[stream].peekBitsFast(d.actualTableLog)
816
			val2 := br[stream2].peekBitsFast(d.actualTableLog)
817
			v := single[val&tlMask]
818
			v2 := single[val2&tlMask]
819
			br[stream].advance(uint8(v.entry))
820
			br[stream2].advance(uint8(v2.entry))
821
			buf[stream][off] = uint8(v.entry >> 8)
822
			buf[stream2][off] = uint8(v2.entry >> 8)
823

824
			val = br[stream].peekBitsFast(d.actualTableLog)
825
			val2 = br[stream2].peekBitsFast(d.actualTableLog)
826
			v = single[val&tlMask]
827
			v2 = single[val2&tlMask]
828
			br[stream].advance(uint8(v.entry))
829
			br[stream2].advance(uint8(v2.entry))
830
			buf[stream][off+1] = uint8(v.entry >> 8)
831
			buf[stream2][off+1] = uint8(v2.entry >> 8)
832
		}
833

834
		off += 2
835

836
		if off == 0 {
837
			if bufoff > dstEvery {
838
				d.bufs.Put(buf)
839
				return nil, errors.New("corruption detected: stream overrun 1")
840
			}
841
			copy(out, buf[0][:])
842
			copy(out[dstEvery:], buf[1][:])
843
			copy(out[dstEvery*2:], buf[2][:])
844
			copy(out[dstEvery*3:], buf[3][:])
845
			out = out[bufoff:]
846
			decoded += bufoff * 4
847
			// There must at least be 3 buffers left.
848
			if len(out) < dstEvery*3 {
849
				d.bufs.Put(buf)
850
				return nil, errors.New("corruption detected: stream overrun 2")
851
			}
852
		}
853
	}
854
	if off > 0 {
855
		ioff := int(off)
856
		if len(out) < dstEvery*3+ioff {
857
			d.bufs.Put(buf)
858
			return nil, errors.New("corruption detected: stream overrun 3")
859
		}
860
		copy(out, buf[0][:off])
861
		copy(out[dstEvery:], buf[1][:off])
862
		copy(out[dstEvery*2:], buf[2][:off])
863
		copy(out[dstEvery*3:], buf[3][:off])
864
		decoded += int(off) * 4
865
		out = out[off:]
866
	}
867

868
	// Decode remaining.
869
	remainBytes := dstEvery - (decoded / 4)
870
	for i := range br {
871
		offset := dstEvery * i
872
		endsAt := offset + remainBytes
873
		if endsAt > len(out) {
874
			endsAt = len(out)
875
		}
876
		br := &br[i]
877
		bitsLeft := br.remaining()
878
		for bitsLeft > 0 {
879
			br.fill()
880
			if offset >= endsAt {
881
				d.bufs.Put(buf)
882
				return nil, errors.New("corruption detected: stream overrun 4")
883
			}
884

885
			// Read value and increment offset.
886
			val := br.peekBitsFast(d.actualTableLog)
887
			v := single[val&tlMask].entry
888
			nBits := uint8(v)
889
			br.advance(nBits)
890
			bitsLeft -= uint(nBits)
891
			out[offset] = uint8(v >> 8)
892
			offset++
893
		}
894
		if offset != endsAt {
895
			d.bufs.Put(buf)
896
			return nil, fmt.Errorf("corruption detected: short output block %d, end %d != %d", i, offset, endsAt)
897
		}
898
		decoded += offset - dstEvery*i
899
		err = br.close()
900
		if err != nil {
901
			return nil, err
902
		}
903
	}
904
	d.bufs.Put(buf)
905
	if dstSize != decoded {
906
		return nil, errors.New("corruption detected: short output block")
907
	}
908
	return dst, nil
909
}
910

911
// Decompress4X will decompress a 4X encoded stream.
912
// The length of the supplied input must match the end of a block exactly.
913
// The *capacity* of the dst slice must match the destination size of
914
// the uncompressed data exactly.
915
func (d *Decoder) decompress4X8bit(dst, src []byte) ([]byte, error) {
916
	if d.actualTableLog == 8 {
917
		return d.decompress4X8bitExactly(dst, src)
918
	}
919

920
	var br [4]bitReaderBytes
921
	start := 6
922
	for i := 0; i < 3; i++ {
923
		length := int(src[i*2]) | (int(src[i*2+1]) << 8)
924
		if start+length >= len(src) {
925
			return nil, errors.New("truncated input (or invalid offset)")
926
		}
927
		err := br[i].init(src[start : start+length])
928
		if err != nil {
929
			return nil, err
930
		}
931
		start += length
932
	}
933
	err := br[3].init(src[start:])
934
	if err != nil {
935
		return nil, err
936
	}
937

938
	// destination, offset to match first output
939
	dstSize := cap(dst)
940
	dst = dst[:dstSize]
941
	out := dst
942
	dstEvery := (dstSize + 3) / 4
943

944
	shift := (56 + (8 - d.actualTableLog)) & 63
945

946
	const tlSize = 1 << 8
947
	single := d.dt.single[:tlSize]
948

949
	// Use temp table to avoid bound checks/append penalty.
950
	buf := d.buffer()
951
	var off uint8
952
	var decoded int
953

954
	// Decode 4 values from each decoder/loop.
955
	const bufoff = 256
956
	for {
957
		if br[0].off < 4 || br[1].off < 4 || br[2].off < 4 || br[3].off < 4 {
958
			break
959
		}
960

961
		{
962
			// Interleave 2 decodes.
963
			const stream = 0
964
			const stream2 = 1
965
			br1 := &br[stream]
966
			br2 := &br[stream2]
967
			br1.fillFast()
968
			br2.fillFast()
969

970
			v := single[uint8(br1.value>>shift)].entry
971
			v2 := single[uint8(br2.value>>shift)].entry
972
			br1.bitsRead += uint8(v)
973
			br1.value <<= v & 63
974
			br2.bitsRead += uint8(v2)
975
			br2.value <<= v2 & 63
976
			buf[stream][off] = uint8(v >> 8)
977
			buf[stream2][off] = uint8(v2 >> 8)
978

979
			v = single[uint8(br1.value>>shift)].entry
980
			v2 = single[uint8(br2.value>>shift)].entry
981
			br1.bitsRead += uint8(v)
982
			br1.value <<= v & 63
983
			br2.bitsRead += uint8(v2)
984
			br2.value <<= v2 & 63
985
			buf[stream][off+1] = uint8(v >> 8)
986
			buf[stream2][off+1] = uint8(v2 >> 8)
987

988
			v = single[uint8(br1.value>>shift)].entry
989
			v2 = single[uint8(br2.value>>shift)].entry
990
			br1.bitsRead += uint8(v)
991
			br1.value <<= v & 63
992
			br2.bitsRead += uint8(v2)
993
			br2.value <<= v2 & 63
994
			buf[stream][off+2] = uint8(v >> 8)
995
			buf[stream2][off+2] = uint8(v2 >> 8)
996

997
			v = single[uint8(br1.value>>shift)].entry
998
			v2 = single[uint8(br2.value>>shift)].entry
999
			br1.bitsRead += uint8(v)
1000
			br1.value <<= v & 63
1001
			br2.bitsRead += uint8(v2)
1002
			br2.value <<= v2 & 63
1003
			buf[stream][off+3] = uint8(v >> 8)
1004
			buf[stream2][off+3] = uint8(v2 >> 8)
1005
		}
1006

1007
		{
1008
			const stream = 2
1009
			const stream2 = 3
1010
			br1 := &br[stream]
1011
			br2 := &br[stream2]
1012
			br1.fillFast()
1013
			br2.fillFast()
1014

1015
			v := single[uint8(br1.value>>shift)].entry
1016
			v2 := single[uint8(br2.value>>shift)].entry
1017
			br1.bitsRead += uint8(v)
1018
			br1.value <<= v & 63
1019
			br2.bitsRead += uint8(v2)
1020
			br2.value <<= v2 & 63
1021
			buf[stream][off] = uint8(v >> 8)
1022
			buf[stream2][off] = uint8(v2 >> 8)
1023

1024
			v = single[uint8(br1.value>>shift)].entry
1025
			v2 = single[uint8(br2.value>>shift)].entry
1026
			br1.bitsRead += uint8(v)
1027
			br1.value <<= v & 63
1028
			br2.bitsRead += uint8(v2)
1029
			br2.value <<= v2 & 63
1030
			buf[stream][off+1] = uint8(v >> 8)
1031
			buf[stream2][off+1] = uint8(v2 >> 8)
1032

1033
			v = single[uint8(br1.value>>shift)].entry
1034
			v2 = single[uint8(br2.value>>shift)].entry
1035
			br1.bitsRead += uint8(v)
1036
			br1.value <<= v & 63
1037
			br2.bitsRead += uint8(v2)
1038
			br2.value <<= v2 & 63
1039
			buf[stream][off+2] = uint8(v >> 8)
1040
			buf[stream2][off+2] = uint8(v2 >> 8)
1041

1042
			v = single[uint8(br1.value>>shift)].entry
1043
			v2 = single[uint8(br2.value>>shift)].entry
1044
			br1.bitsRead += uint8(v)
1045
			br1.value <<= v & 63
1046
			br2.bitsRead += uint8(v2)
1047
			br2.value <<= v2 & 63
1048
			buf[stream][off+3] = uint8(v >> 8)
1049
			buf[stream2][off+3] = uint8(v2 >> 8)
1050
		}
1051

1052
		off += 4
1053

1054
		if off == 0 {
1055
			if bufoff > dstEvery {
1056
				d.bufs.Put(buf)
1057
				return nil, errors.New("corruption detected: stream overrun 1")
1058
			}
1059
			copy(out, buf[0][:])
1060
			copy(out[dstEvery:], buf[1][:])
1061
			copy(out[dstEvery*2:], buf[2][:])
1062
			copy(out[dstEvery*3:], buf[3][:])
1063
			out = out[bufoff:]
1064
			decoded += bufoff * 4
1065
			// There must at least be 3 buffers left.
1066
			if len(out) < dstEvery*3 {
1067
				d.bufs.Put(buf)
1068
				return nil, errors.New("corruption detected: stream overrun 2")
1069
			}
1070
		}
1071
	}
1072
	if off > 0 {
1073
		ioff := int(off)
1074
		if len(out) < dstEvery*3+ioff {
1075
			d.bufs.Put(buf)
1076
			return nil, errors.New("corruption detected: stream overrun 3")
1077
		}
1078
		copy(out, buf[0][:off])
1079
		copy(out[dstEvery:], buf[1][:off])
1080
		copy(out[dstEvery*2:], buf[2][:off])
1081
		copy(out[dstEvery*3:], buf[3][:off])
1082
		decoded += int(off) * 4
1083
		out = out[off:]
1084
	}
1085

1086
	// Decode remaining.
1087
	// Decode remaining.
1088
	remainBytes := dstEvery - (decoded / 4)
1089
	for i := range br {
1090
		offset := dstEvery * i
1091
		endsAt := offset + remainBytes
1092
		if endsAt > len(out) {
1093
			endsAt = len(out)
1094
		}
1095
		br := &br[i]
1096
		bitsLeft := br.remaining()
1097
		for bitsLeft > 0 {
1098
			if br.finished() {
1099
				d.bufs.Put(buf)
1100
				return nil, io.ErrUnexpectedEOF
1101
			}
1102
			if br.bitsRead >= 56 {
1103
				if br.off >= 4 {
1104
					v := br.in[br.off-4:]
1105
					v = v[:4]
1106
					low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
1107
					br.value |= uint64(low) << (br.bitsRead - 32)
1108
					br.bitsRead -= 32
1109
					br.off -= 4
1110
				} else {
1111
					for br.off > 0 {
1112
						br.value |= uint64(br.in[br.off-1]) << (br.bitsRead - 8)
1113
						br.bitsRead -= 8
1114
						br.off--
1115
					}
1116
				}
1117
			}
1118
			// end inline...
1119
			if offset >= endsAt {
1120
				d.bufs.Put(buf)
1121
				return nil, errors.New("corruption detected: stream overrun 4")
1122
			}
1123

1124
			// Read value and increment offset.
1125
			v := single[uint8(br.value>>shift)].entry
1126
			nBits := uint8(v)
1127
			br.advance(nBits)
1128
			bitsLeft -= uint(nBits)
1129
			out[offset] = uint8(v >> 8)
1130
			offset++
1131
		}
1132
		if offset != endsAt {
1133
			d.bufs.Put(buf)
1134
			return nil, fmt.Errorf("corruption detected: short output block %d, end %d != %d", i, offset, endsAt)
1135
		}
1136
		decoded += offset - dstEvery*i
1137
		err = br.close()
1138
		if err != nil {
1139
			d.bufs.Put(buf)
1140
			return nil, err
1141
		}
1142
	}
1143
	d.bufs.Put(buf)
1144
	if dstSize != decoded {
1145
		return nil, errors.New("corruption detected: short output block")
1146
	}
1147
	return dst, nil
1148
}
1149

1150
// Decompress4X will decompress a 4X encoded stream.
1151
// The length of the supplied input must match the end of a block exactly.
1152
// The *capacity* of the dst slice must match the destination size of
1153
// the uncompressed data exactly.
1154
func (d *Decoder) decompress4X8bitExactly(dst, src []byte) ([]byte, error) {
1155
	var br [4]bitReaderBytes
1156
	start := 6
1157
	for i := 0; i < 3; i++ {
1158
		length := int(src[i*2]) | (int(src[i*2+1]) << 8)
1159
		if start+length >= len(src) {
1160
			return nil, errors.New("truncated input (or invalid offset)")
1161
		}
1162
		err := br[i].init(src[start : start+length])
1163
		if err != nil {
1164
			return nil, err
1165
		}
1166
		start += length
1167
	}
1168
	err := br[3].init(src[start:])
1169
	if err != nil {
1170
		return nil, err
1171
	}
1172

1173
	// destination, offset to match first output
1174
	dstSize := cap(dst)
1175
	dst = dst[:dstSize]
1176
	out := dst
1177
	dstEvery := (dstSize + 3) / 4
1178

1179
	const shift = 56
1180
	const tlSize = 1 << 8
1181
	const tlMask = tlSize - 1
1182
	single := d.dt.single[:tlSize]
1183

1184
	// Use temp table to avoid bound checks/append penalty.
1185
	buf := d.buffer()
1186
	var off uint8
1187
	var decoded int
1188

1189
	// Decode 4 values from each decoder/loop.
1190
	const bufoff = 256
1191
	for {
1192
		if br[0].off < 4 || br[1].off < 4 || br[2].off < 4 || br[3].off < 4 {
1193
			break
1194
		}
1195

1196
		{
1197
			// Interleave 2 decodes.
1198
			const stream = 0
1199
			const stream2 = 1
1200
			br1 := &br[stream]
1201
			br2 := &br[stream2]
1202
			br1.fillFast()
1203
			br2.fillFast()
1204

1205
			v := single[uint8(br1.value>>shift)].entry
1206
			v2 := single[uint8(br2.value>>shift)].entry
1207
			br1.bitsRead += uint8(v)
1208
			br1.value <<= v & 63
1209
			br2.bitsRead += uint8(v2)
1210
			br2.value <<= v2 & 63
1211
			buf[stream][off] = uint8(v >> 8)
1212
			buf[stream2][off] = uint8(v2 >> 8)
1213

1214
			v = single[uint8(br1.value>>shift)].entry
1215
			v2 = single[uint8(br2.value>>shift)].entry
1216
			br1.bitsRead += uint8(v)
1217
			br1.value <<= v & 63
1218
			br2.bitsRead += uint8(v2)
1219
			br2.value <<= v2 & 63
1220
			buf[stream][off+1] = uint8(v >> 8)
1221
			buf[stream2][off+1] = uint8(v2 >> 8)
1222

1223
			v = single[uint8(br1.value>>shift)].entry
1224
			v2 = single[uint8(br2.value>>shift)].entry
1225
			br1.bitsRead += uint8(v)
1226
			br1.value <<= v & 63
1227
			br2.bitsRead += uint8(v2)
1228
			br2.value <<= v2 & 63
1229
			buf[stream][off+2] = uint8(v >> 8)
1230
			buf[stream2][off+2] = uint8(v2 >> 8)
1231

1232
			v = single[uint8(br1.value>>shift)].entry
1233
			v2 = single[uint8(br2.value>>shift)].entry
1234
			br1.bitsRead += uint8(v)
1235
			br1.value <<= v & 63
1236
			br2.bitsRead += uint8(v2)
1237
			br2.value <<= v2 & 63
1238
			buf[stream][off+3] = uint8(v >> 8)
1239
			buf[stream2][off+3] = uint8(v2 >> 8)
1240
		}
1241

1242
		{
1243
			const stream = 2
1244
			const stream2 = 3
1245
			br1 := &br[stream]
1246
			br2 := &br[stream2]
1247
			br1.fillFast()
1248
			br2.fillFast()
1249

1250
			v := single[uint8(br1.value>>shift)].entry
1251
			v2 := single[uint8(br2.value>>shift)].entry
1252
			br1.bitsRead += uint8(v)
1253
			br1.value <<= v & 63
1254
			br2.bitsRead += uint8(v2)
1255
			br2.value <<= v2 & 63
1256
			buf[stream][off] = uint8(v >> 8)
1257
			buf[stream2][off] = uint8(v2 >> 8)
1258

1259
			v = single[uint8(br1.value>>shift)].entry
1260
			v2 = single[uint8(br2.value>>shift)].entry
1261
			br1.bitsRead += uint8(v)
1262
			br1.value <<= v & 63
1263
			br2.bitsRead += uint8(v2)
1264
			br2.value <<= v2 & 63
1265
			buf[stream][off+1] = uint8(v >> 8)
1266
			buf[stream2][off+1] = uint8(v2 >> 8)
1267

1268
			v = single[uint8(br1.value>>shift)].entry
1269
			v2 = single[uint8(br2.value>>shift)].entry
1270
			br1.bitsRead += uint8(v)
1271
			br1.value <<= v & 63
1272
			br2.bitsRead += uint8(v2)
1273
			br2.value <<= v2 & 63
1274
			buf[stream][off+2] = uint8(v >> 8)
1275
			buf[stream2][off+2] = uint8(v2 >> 8)
1276

1277
			v = single[uint8(br1.value>>shift)].entry
1278
			v2 = single[uint8(br2.value>>shift)].entry
1279
			br1.bitsRead += uint8(v)
1280
			br1.value <<= v & 63
1281
			br2.bitsRead += uint8(v2)
1282
			br2.value <<= v2 & 63
1283
			buf[stream][off+3] = uint8(v >> 8)
1284
			buf[stream2][off+3] = uint8(v2 >> 8)
1285
		}
1286

1287
		off += 4
1288

1289
		if off == 0 {
1290
			if bufoff > dstEvery {
1291
				d.bufs.Put(buf)
1292
				return nil, errors.New("corruption detected: stream overrun 1")
1293
			}
1294
			copy(out, buf[0][:])
1295
			copy(out[dstEvery:], buf[1][:])
1296
			copy(out[dstEvery*2:], buf[2][:])
1297
			copy(out[dstEvery*3:], buf[3][:])
1298
			out = out[bufoff:]
1299
			decoded += bufoff * 4
1300
			// There must at least be 3 buffers left.
1301
			if len(out) < dstEvery*3 {
1302
				d.bufs.Put(buf)
1303
				return nil, errors.New("corruption detected: stream overrun 2")
1304
			}
1305
		}
1306
	}
1307
	if off > 0 {
1308
		ioff := int(off)
1309
		if len(out) < dstEvery*3+ioff {
1310
			return nil, errors.New("corruption detected: stream overrun 3")
1311
		}
1312
		copy(out, buf[0][:off])
1313
		copy(out[dstEvery:], buf[1][:off])
1314
		copy(out[dstEvery*2:], buf[2][:off])
1315
		copy(out[dstEvery*3:], buf[3][:off])
1316
		decoded += int(off) * 4
1317
		out = out[off:]
1318
	}
1319

1320
	// Decode remaining.
1321
	remainBytes := dstEvery - (decoded / 4)
1322
	for i := range br {
1323
		offset := dstEvery * i
1324
		endsAt := offset + remainBytes
1325
		if endsAt > len(out) {
1326
			endsAt = len(out)
1327
		}
1328
		br := &br[i]
1329
		bitsLeft := br.remaining()
1330
		for bitsLeft > 0 {
1331
			if br.finished() {
1332
				d.bufs.Put(buf)
1333
				return nil, io.ErrUnexpectedEOF
1334
			}
1335
			if br.bitsRead >= 56 {
1336
				if br.off >= 4 {
1337
					v := br.in[br.off-4:]
1338
					v = v[:4]
1339
					low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
1340
					br.value |= uint64(low) << (br.bitsRead - 32)
1341
					br.bitsRead -= 32
1342
					br.off -= 4
1343
				} else {
1344
					for br.off > 0 {
1345
						br.value |= uint64(br.in[br.off-1]) << (br.bitsRead - 8)
1346
						br.bitsRead -= 8
1347
						br.off--
1348
					}
1349
				}
1350
			}
1351
			// end inline...
1352
			if offset >= endsAt {
1353
				d.bufs.Put(buf)
1354
				return nil, errors.New("corruption detected: stream overrun 4")
1355
			}
1356

1357
			// Read value and increment offset.
1358
			v := single[br.peekByteFast()].entry
1359
			nBits := uint8(v)
1360
			br.advance(nBits)
1361
			bitsLeft -= uint(nBits)
1362
			out[offset] = uint8(v >> 8)
1363
			offset++
1364
		}
1365
		if offset != endsAt {
1366
			d.bufs.Put(buf)
1367
			return nil, fmt.Errorf("corruption detected: short output block %d, end %d != %d", i, offset, endsAt)
1368
		}
1369

1370
		decoded += offset - dstEvery*i
1371
		err = br.close()
1372
		if err != nil {
1373
			d.bufs.Put(buf)
1374
			return nil, err
1375
		}
1376
	}
1377
	d.bufs.Put(buf)
1378
	if dstSize != decoded {
1379
		return nil, errors.New("corruption detected: short output block")
1380
	}
1381
	return dst, nil
1382
}
1383

1384
// matches will compare a decoding table to a coding table.
1385
// Errors are written to the writer.
1386
// Nothing will be written if table is ok.
1387
func (s *Scratch) matches(ct cTable, w io.Writer) {
1388
	if s == nil || len(s.dt.single) == 0 {
1389
		return
1390
	}
1391
	dt := s.dt.single[:1<<s.actualTableLog]
1392
	tablelog := s.actualTableLog
1393
	ok := 0
1394
	broken := 0
1395
	for sym, enc := range ct {
1396
		errs := 0
1397
		broken++
1398
		if enc.nBits == 0 {
1399
			for _, dec := range dt {
1400
				if uint8(dec.entry>>8) == byte(sym) {
1401
					fmt.Fprintf(w, "symbol %x has decoder, but no encoder\n", sym)
1402
					errs++
1403
					break
1404
				}
1405
			}
1406
			if errs == 0 {
1407
				broken--
1408
			}
1409
			continue
1410
		}
1411
		// Unused bits in input
1412
		ub := tablelog - enc.nBits
1413
		top := enc.val << ub
1414
		// decoder looks at top bits.
1415
		dec := dt[top]
1416
		if uint8(dec.entry) != enc.nBits {
1417
			fmt.Fprintf(w, "symbol 0x%x bit size mismatch (enc: %d, dec:%d).\n", sym, enc.nBits, uint8(dec.entry))
1418
			errs++
1419
		}
1420
		if uint8(dec.entry>>8) != uint8(sym) {
1421
			fmt.Fprintf(w, "symbol 0x%x decoder output mismatch (enc: %d, dec:%d).\n", sym, sym, uint8(dec.entry>>8))
1422
			errs++
1423
		}
1424
		if errs > 0 {
1425
			fmt.Fprintf(w, "%d errros in base, stopping\n", errs)
1426
			continue
1427
		}
1428
		// Ensure that all combinations are covered.
1429
		for i := uint16(0); i < (1 << ub); i++ {
1430
			vval := top | i
1431
			dec := dt[vval]
1432
			if uint8(dec.entry) != enc.nBits {
1433
				fmt.Fprintf(w, "symbol 0x%x bit size mismatch (enc: %d, dec:%d).\n", vval, enc.nBits, uint8(dec.entry))
1434
				errs++
1435
			}
1436
			if uint8(dec.entry>>8) != uint8(sym) {
1437
				fmt.Fprintf(w, "symbol 0x%x decoder output mismatch (enc: %d, dec:%d).\n", vval, sym, uint8(dec.entry>>8))
1438
				errs++
1439
			}
1440
			if errs > 20 {
1441
				fmt.Fprintf(w, "%d errros, stopping\n", errs)
1442
				break
1443
			}
1444
		}
1445
		if errs == 0 {
1446
			ok++
1447
			broken--
1448
		}
1449
	}
1450
	if broken > 0 {
1451
		fmt.Fprintf(w, "%d broken, %d ok\n", broken, ok)
1452
	}
1453
}
1454