cubefs

1
// 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

5
package zstd
6

7
import (
8
	"encoding/binary"
9
	"errors"
10
	"fmt"
11
	"io"
12
	"math/bits"
13
)
14

15
// bitReader reads a bitstream in reverse.
16
// The last set bit indicates the start of the stream and is used
17
// for aligning the input.
18
type bitReader struct {
19
	in       []byte
20
	off      uint   // next byte to read is at in[off - 1]
21
	value    uint64 // Maybe use [16]byte, but shifting is awkward.
22
	bitsRead uint8
23
}
24

25
// init initializes and resets the bit reader.
26
func (b *bitReader) init(in []byte) error {
27
	if len(in) < 1 {
28
		return errors.New("corrupt stream: too short")
29
	}
30
	b.in = in
31
	b.off = uint(len(in))
32
	// The highest bit of the last byte indicates where to start
33
	v := in[len(in)-1]
34
	if v == 0 {
35
		return errors.New("corrupt stream, did not find end of stream")
36
	}
37
	b.bitsRead = 64
38
	b.value = 0
39
	if len(in) >= 8 {
40
		b.fillFastStart()
41
	} else {
42
		b.fill()
43
		b.fill()
44
	}
45
	b.bitsRead += 8 - uint8(highBits(uint32(v)))
46
	return nil
47
}
48

49
// getBits will return n bits. n can be 0.
50
func (b *bitReader) getBits(n uint8) int {
51
	if n == 0 /*|| b.bitsRead >= 64 */ {
52
		return 0
53
	}
54
	return int(b.get32BitsFast(n))
55
}
56

57
// get32BitsFast requires that at least one bit is requested every time.
58
// There are no checks if the buffer is filled.
59
func (b *bitReader) get32BitsFast(n uint8) uint32 {
60
	const regMask = 64 - 1
61
	v := uint32((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
62
	b.bitsRead += n
63
	return v
64
}
65

66
func (b *bitReader) get16BitsFast(n uint8) uint16 {
67
	const regMask = 64 - 1
68
	v := uint16((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
69
	b.bitsRead += n
70
	return v
71
}
72

73
// fillFast() will make sure at least 32 bits are available.
74
// There must be at least 4 bytes available.
75
func (b *bitReader) fillFast() {
76
	if b.bitsRead < 32 {
77
		return
78
	}
79
	// 2 bounds checks.
80
	v := b.in[b.off-4:]
81
	v = v[:4]
82
	low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
83
	b.value = (b.value << 32) | uint64(low)
84
	b.bitsRead -= 32
85
	b.off -= 4
86
}
87

88
// fillFastStart() assumes the bitreader is empty and there is at least 8 bytes to read.
89
func (b *bitReader) fillFastStart() {
90
	// Do single re-slice to avoid bounds checks.
91
	b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
92
	b.bitsRead = 0
93
	b.off -= 8
94
}
95

96
// fill() will make sure at least 32 bits are available.
97
func (b *bitReader) fill() {
98
	if b.bitsRead < 32 {
99
		return
100
	}
101
	if b.off >= 4 {
102
		v := b.in[b.off-4:]
103
		v = v[:4]
104
		low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
105
		b.value = (b.value << 32) | uint64(low)
106
		b.bitsRead -= 32
107
		b.off -= 4
108
		return
109
	}
110
	for b.off > 0 {
111
		b.value = (b.value << 8) | uint64(b.in[b.off-1])
112
		b.bitsRead -= 8
113
		b.off--
114
	}
115
}
116

117
// finished returns true if all bits have been read from the bit stream.
118
func (b *bitReader) finished() bool {
119
	return b.off == 0 && b.bitsRead >= 64
120
}
121

122
// overread returns true if more bits have been requested than is on the stream.
123
func (b *bitReader) overread() bool {
124
	return b.bitsRead > 64
125
}
126

127
// remain returns the number of bits remaining.
128
func (b *bitReader) remain() uint {
129
	return b.off*8 + 64 - uint(b.bitsRead)
130
}
131

132
// close the bitstream and returns an error if out-of-buffer reads occurred.
133
func (b *bitReader) close() error {
134
	// Release reference.
135
	b.in = nil
136
	if !b.finished() {
137
		return fmt.Errorf("%d extra bits on block, should be 0", b.remain())
138
	}
139
	if b.bitsRead > 64 {
140
		return io.ErrUnexpectedEOF
141
	}
142
	return nil
143
}
144

145
func highBits(val uint32) (n uint32) {
146
	return uint32(bits.Len32(val) - 1)
147
}
148