cubefs

1
// Copyright 2018 Klaus Post. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4
// Based on work Copyright (c) 2013, Yann Collet, released under BSD License.
5

6
package huff0
7

8
import (
9
	"encoding/binary"
10
	"errors"
11
	"fmt"
12
	"io"
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 bitReaderBytes struct {
19
	in       []byte
20
	off      uint // next byte to read is at in[off - 1]
21
	value    uint64
22
	bitsRead uint8
23
}
24

25
// init initializes and resets the bit reader.
26
func (b *bitReaderBytes) 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.advance(8 - uint8(highBit32(uint32(v))))
46
	return nil
47
}
48

49
// peekBitsFast requires that at least one bit is requested every time.
50
// There are no checks if the buffer is filled.
51
func (b *bitReaderBytes) peekByteFast() uint8 {
52
	got := uint8(b.value >> 56)
53
	return got
54
}
55

56
func (b *bitReaderBytes) advance(n uint8) {
57
	b.bitsRead += n
58
	b.value <<= n & 63
59
}
60

61
// fillFast() will make sure at least 32 bits are available.
62
// There must be at least 4 bytes available.
63
func (b *bitReaderBytes) fillFast() {
64
	if b.bitsRead < 32 {
65
		return
66
	}
67

68
	// 2 bounds checks.
69
	v := b.in[b.off-4 : b.off]
70
	v = v[:4]
71
	low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
72
	b.value |= uint64(low) << (b.bitsRead - 32)
73
	b.bitsRead -= 32
74
	b.off -= 4
75
}
76

77
// fillFastStart() assumes the bitReaderBytes is empty and there is at least 8 bytes to read.
78
func (b *bitReaderBytes) fillFastStart() {
79
	// Do single re-slice to avoid bounds checks.
80
	b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
81
	b.bitsRead = 0
82
	b.off -= 8
83
}
84

85
// fill() will make sure at least 32 bits are available.
86
func (b *bitReaderBytes) fill() {
87
	if b.bitsRead < 32 {
88
		return
89
	}
90
	if b.off > 4 {
91
		v := b.in[b.off-4:]
92
		v = v[:4]
93
		low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
94
		b.value |= uint64(low) << (b.bitsRead - 32)
95
		b.bitsRead -= 32
96
		b.off -= 4
97
		return
98
	}
99
	for b.off > 0 {
100
		b.value |= uint64(b.in[b.off-1]) << (b.bitsRead - 8)
101
		b.bitsRead -= 8
102
		b.off--
103
	}
104
}
105

106
// finished returns true if all bits have been read from the bit stream.
107
func (b *bitReaderBytes) finished() bool {
108
	return b.off == 0 && b.bitsRead >= 64
109
}
110

111
func (b *bitReaderBytes) remaining() uint {
112
	return b.off*8 + uint(64-b.bitsRead)
113
}
114

115
// close the bitstream and returns an error if out-of-buffer reads occurred.
116
func (b *bitReaderBytes) close() error {
117
	// Release reference.
118
	b.in = nil
119
	if b.remaining() > 0 {
120
		return fmt.Errorf("corrupt input: %d bits remain on stream", b.remaining())
121
	}
122
	if b.bitsRead > 64 {
123
		return io.ErrUnexpectedEOF
124
	}
125
	return nil
126
}
127

128
// bitReaderShifted reads a bitstream in reverse.
129
// The last set bit indicates the start of the stream and is used
130
// for aligning the input.
131
type bitReaderShifted struct {
132
	in       []byte
133
	off      uint // next byte to read is at in[off - 1]
134
	value    uint64
135
	bitsRead uint8
136
}
137

138
// init initializes and resets the bit reader.
139
func (b *bitReaderShifted) init(in []byte) error {
140
	if len(in) < 1 {
141
		return errors.New("corrupt stream: too short")
142
	}
143
	b.in = in
144
	b.off = uint(len(in))
145
	// The highest bit of the last byte indicates where to start
146
	v := in[len(in)-1]
147
	if v == 0 {
148
		return errors.New("corrupt stream, did not find end of stream")
149
	}
150
	b.bitsRead = 64
151
	b.value = 0
152
	if len(in) >= 8 {
153
		b.fillFastStart()
154
	} else {
155
		b.fill()
156
		b.fill()
157
	}
158
	b.advance(8 - uint8(highBit32(uint32(v))))
159
	return nil
160
}
161

162
// peekBitsFast requires that at least one bit is requested every time.
163
// There are no checks if the buffer is filled.
164
func (b *bitReaderShifted) peekBitsFast(n uint8) uint16 {
165
	return uint16(b.value >> ((64 - n) & 63))
166
}
167

168
func (b *bitReaderShifted) advance(n uint8) {
169
	b.bitsRead += n
170
	b.value <<= n & 63
171
}
172

173
// fillFast() will make sure at least 32 bits are available.
174
// There must be at least 4 bytes available.
175
func (b *bitReaderShifted) fillFast() {
176
	if b.bitsRead < 32 {
177
		return
178
	}
179

180
	// 2 bounds checks.
181
	v := b.in[b.off-4 : b.off]
182
	v = v[:4]
183
	low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
184
	b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
185
	b.bitsRead -= 32
186
	b.off -= 4
187
}
188

189
// fillFastStart() assumes the bitReaderShifted is empty and there is at least 8 bytes to read.
190
func (b *bitReaderShifted) fillFastStart() {
191
	// Do single re-slice to avoid bounds checks.
192
	b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
193
	b.bitsRead = 0
194
	b.off -= 8
195
}
196

197
// fill() will make sure at least 32 bits are available.
198
func (b *bitReaderShifted) fill() {
199
	if b.bitsRead < 32 {
200
		return
201
	}
202
	if b.off > 4 {
203
		v := b.in[b.off-4:]
204
		v = v[:4]
205
		low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
206
		b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
207
		b.bitsRead -= 32
208
		b.off -= 4
209
		return
210
	}
211
	for b.off > 0 {
212
		b.value |= uint64(b.in[b.off-1]) << ((b.bitsRead - 8) & 63)
213
		b.bitsRead -= 8
214
		b.off--
215
	}
216
}
217

218
// finished returns true if all bits have been read from the bit stream.
219
func (b *bitReaderShifted) finished() bool {
220
	return b.off == 0 && b.bitsRead >= 64
221
}
222

223
func (b *bitReaderShifted) remaining() uint {
224
	return b.off*8 + uint(64-b.bitsRead)
225
}
226

227
// close the bitstream and returns an error if out-of-buffer reads occurred.
228
func (b *bitReaderShifted) close() error {
229
	// Release reference.
230
	b.in = nil
231
	if b.remaining() > 0 {
232
		return fmt.Errorf("corrupt input: %d bits remain on stream", b.remaining())
233
	}
234
	if b.bitsRead > 64 {
235
		return io.ErrUnexpectedEOF
236
	}
237
	return nil
238
}
239