blob: a4979e8868a5232c30ce74f858fe81e8377e574c [file] [log] [blame]
Scott Bakered4efab2020-01-13 19:12:25 -08001// 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
6package huff0
7
8import (
David K. Bainbridgebd6b2882021-08-26 13:31:02 +00009 "encoding/binary"
Scott Bakered4efab2020-01-13 19:12:25 -080010 "errors"
11 "io"
12)
13
14// bitReader reads a bitstream in reverse.
15// The last set bit indicates the start of the stream and is used
16// for aligning the input.
17type bitReader struct {
18 in []byte
19 off uint // next byte to read is at in[off - 1]
20 value uint64
21 bitsRead uint8
22}
23
24// init initializes and resets the bit reader.
25func (b *bitReader) init(in []byte) error {
26 if len(in) < 1 {
27 return errors.New("corrupt stream: too short")
28 }
29 b.in = in
30 b.off = uint(len(in))
31 // The highest bit of the last byte indicates where to start
32 v := in[len(in)-1]
33 if v == 0 {
34 return errors.New("corrupt stream, did not find end of stream")
35 }
36 b.bitsRead = 64
37 b.value = 0
David K. Bainbridgebd6b2882021-08-26 13:31:02 +000038 if len(in) >= 8 {
39 b.fillFastStart()
40 } else {
41 b.fill()
42 b.fill()
43 }
Scott Bakered4efab2020-01-13 19:12:25 -080044 b.bitsRead += 8 - uint8(highBit32(uint32(v)))
45 return nil
46}
47
Scott Bakered4efab2020-01-13 19:12:25 -080048// peekBitsFast requires that at least one bit is requested every time.
49// There are no checks if the buffer is filled.
50func (b *bitReader) peekBitsFast(n uint8) uint16 {
51 const regMask = 64 - 1
52 v := uint16((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
53 return v
54}
55
56// fillFast() will make sure at least 32 bits are available.
57// There must be at least 4 bytes available.
58func (b *bitReader) fillFast() {
59 if b.bitsRead < 32 {
60 return
61 }
David K. Bainbridgebd6b2882021-08-26 13:31:02 +000062
63 // 2 bounds checks.
Scott Bakered4efab2020-01-13 19:12:25 -080064 v := b.in[b.off-4 : b.off]
David K. Bainbridgebd6b2882021-08-26 13:31:02 +000065 v = v[:4]
Scott Bakered4efab2020-01-13 19:12:25 -080066 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
67 b.value = (b.value << 32) | uint64(low)
68 b.bitsRead -= 32
69 b.off -= 4
70}
71
David K. Bainbridgebd6b2882021-08-26 13:31:02 +000072func (b *bitReader) advance(n uint8) {
73 b.bitsRead += n
74}
75
76// fillFastStart() assumes the bitreader is empty and there is at least 8 bytes to read.
77func (b *bitReader) fillFastStart() {
78 // Do single re-slice to avoid bounds checks.
79 b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
80 b.bitsRead = 0
81 b.off -= 8
82}
83
Scott Bakered4efab2020-01-13 19:12:25 -080084// fill() will make sure at least 32 bits are available.
85func (b *bitReader) fill() {
86 if b.bitsRead < 32 {
87 return
88 }
89 if b.off > 4 {
David K. Bainbridgebd6b2882021-08-26 13:31:02 +000090 v := b.in[b.off-4:]
91 v = v[:4]
Scott Bakered4efab2020-01-13 19:12:25 -080092 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
93 b.value = (b.value << 32) | uint64(low)
94 b.bitsRead -= 32
95 b.off -= 4
96 return
97 }
98 for b.off > 0 {
99 b.value = (b.value << 8) | uint64(b.in[b.off-1])
100 b.bitsRead -= 8
101 b.off--
102 }
103}
104
105// finished returns true if all bits have been read from the bit stream.
106func (b *bitReader) finished() bool {
107 return b.off == 0 && b.bitsRead >= 64
108}
109
110// close the bitstream and returns an error if out-of-buffer reads occurred.
111func (b *bitReader) close() error {
112 // Release reference.
113 b.in = nil
114 if b.bitsRead > 64 {
115 return io.ErrUnexpectedEOF
116 }
117 return nil
118}
David K. Bainbridgebd6b2882021-08-26 13:31:02 +0000119
120// bitReader reads a bitstream in reverse.
121// The last set bit indicates the start of the stream and is used
122// for aligning the input.
123type bitReaderBytes struct {
124 in []byte
125 off uint // next byte to read is at in[off - 1]
126 value uint64
127 bitsRead uint8
128}
129
130// init initializes and resets the bit reader.
131func (b *bitReaderBytes) init(in []byte) error {
132 if len(in) < 1 {
133 return errors.New("corrupt stream: too short")
134 }
135 b.in = in
136 b.off = uint(len(in))
137 // The highest bit of the last byte indicates where to start
138 v := in[len(in)-1]
139 if v == 0 {
140 return errors.New("corrupt stream, did not find end of stream")
141 }
142 b.bitsRead = 64
143 b.value = 0
144 if len(in) >= 8 {
145 b.fillFastStart()
146 } else {
147 b.fill()
148 b.fill()
149 }
150 b.advance(8 - uint8(highBit32(uint32(v))))
151 return nil
152}
153
154// peekBitsFast requires that at least one bit is requested every time.
155// There are no checks if the buffer is filled.
156func (b *bitReaderBytes) peekByteFast() uint8 {
157 got := uint8(b.value >> 56)
158 return got
159}
160
161func (b *bitReaderBytes) advance(n uint8) {
162 b.bitsRead += n
163 b.value <<= n & 63
164}
165
166// fillFast() will make sure at least 32 bits are available.
167// There must be at least 4 bytes available.
168func (b *bitReaderBytes) fillFast() {
169 if b.bitsRead < 32 {
170 return
171 }
172
173 // 2 bounds checks.
174 v := b.in[b.off-4 : b.off]
175 v = v[:4]
176 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
177 b.value |= uint64(low) << (b.bitsRead - 32)
178 b.bitsRead -= 32
179 b.off -= 4
180}
181
182// fillFastStart() assumes the bitReaderBytes is empty and there is at least 8 bytes to read.
183func (b *bitReaderBytes) fillFastStart() {
184 // Do single re-slice to avoid bounds checks.
185 b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
186 b.bitsRead = 0
187 b.off -= 8
188}
189
190// fill() will make sure at least 32 bits are available.
191func (b *bitReaderBytes) fill() {
192 if b.bitsRead < 32 {
193 return
194 }
195 if b.off > 4 {
196 v := b.in[b.off-4:]
197 v = v[:4]
198 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
199 b.value |= uint64(low) << (b.bitsRead - 32)
200 b.bitsRead -= 32
201 b.off -= 4
202 return
203 }
204 for b.off > 0 {
205 b.value |= uint64(b.in[b.off-1]) << (b.bitsRead - 8)
206 b.bitsRead -= 8
207 b.off--
208 }
209}
210
211// finished returns true if all bits have been read from the bit stream.
212func (b *bitReaderBytes) finished() bool {
213 return b.off == 0 && b.bitsRead >= 64
214}
215
216// close the bitstream and returns an error if out-of-buffer reads occurred.
217func (b *bitReaderBytes) close() error {
218 // Release reference.
219 b.in = nil
220 if b.bitsRead > 64 {
221 return io.ErrUnexpectedEOF
222 }
223 return nil
224}
225
226// bitReaderShifted reads a bitstream in reverse.
227// The last set bit indicates the start of the stream and is used
228// for aligning the input.
229type bitReaderShifted struct {
230 in []byte
231 off uint // next byte to read is at in[off - 1]
232 value uint64
233 bitsRead uint8
234}
235
236// init initializes and resets the bit reader.
237func (b *bitReaderShifted) init(in []byte) error {
238 if len(in) < 1 {
239 return errors.New("corrupt stream: too short")
240 }
241 b.in = in
242 b.off = uint(len(in))
243 // The highest bit of the last byte indicates where to start
244 v := in[len(in)-1]
245 if v == 0 {
246 return errors.New("corrupt stream, did not find end of stream")
247 }
248 b.bitsRead = 64
249 b.value = 0
250 if len(in) >= 8 {
251 b.fillFastStart()
252 } else {
253 b.fill()
254 b.fill()
255 }
256 b.advance(8 - uint8(highBit32(uint32(v))))
257 return nil
258}
259
260// peekBitsFast requires that at least one bit is requested every time.
261// There are no checks if the buffer is filled.
262func (b *bitReaderShifted) peekBitsFast(n uint8) uint16 {
263 return uint16(b.value >> ((64 - n) & 63))
264}
265
266func (b *bitReaderShifted) advance(n uint8) {
267 b.bitsRead += n
268 b.value <<= n & 63
269}
270
271// fillFast() will make sure at least 32 bits are available.
272// There must be at least 4 bytes available.
273func (b *bitReaderShifted) fillFast() {
274 if b.bitsRead < 32 {
275 return
276 }
277
278 // 2 bounds checks.
279 v := b.in[b.off-4 : b.off]
280 v = v[:4]
281 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
282 b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
283 b.bitsRead -= 32
284 b.off -= 4
285}
286
287// fillFastStart() assumes the bitReaderShifted is empty and there is at least 8 bytes to read.
288func (b *bitReaderShifted) fillFastStart() {
289 // Do single re-slice to avoid bounds checks.
290 b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
291 b.bitsRead = 0
292 b.off -= 8
293}
294
295// fill() will make sure at least 32 bits are available.
296func (b *bitReaderShifted) fill() {
297 if b.bitsRead < 32 {
298 return
299 }
300 if b.off > 4 {
301 v := b.in[b.off-4:]
302 v = v[:4]
303 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
304 b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
305 b.bitsRead -= 32
306 b.off -= 4
307 return
308 }
309 for b.off > 0 {
310 b.value |= uint64(b.in[b.off-1]) << ((b.bitsRead - 8) & 63)
311 b.bitsRead -= 8
312 b.off--
313 }
314}
315
316// finished returns true if all bits have been read from the bit stream.
317func (b *bitReaderShifted) finished() bool {
318 return b.off == 0 && b.bitsRead >= 64
319}
320
321// close the bitstream and returns an error if out-of-buffer reads occurred.
322func (b *bitReaderShifted) close() error {
323 // Release reference.
324 b.in = nil
325 if b.bitsRead > 64 {
326 return io.ErrUnexpectedEOF
327 }
328 return nil
329}