bitreader.go raw
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 "errors"
10 "fmt"
11 "io"
12
13 "github.com/klauspost/compress/internal/le"
14 )
15
16 // bitReader reads a bitstream in reverse.
17 // The last set bit indicates the start of the stream and is used
18 // for aligning the input.
19 type bitReaderBytes struct {
20 in []byte
21 off uint // next byte to read is at in[off - 1]
22 value uint64
23 bitsRead uint8
24 }
25
26 // init initializes and resets the bit reader.
27 func (b *bitReaderBytes) init(in []byte) error {
28 if len(in) < 1 {
29 return errors.New("corrupt stream: too short")
30 }
31 b.in = in
32 b.off = uint(len(in))
33 // The highest bit of the last byte indicates where to start
34 v := in[len(in)-1]
35 if v == 0 {
36 return errors.New("corrupt stream, did not find end of stream")
37 }
38 b.bitsRead = 64
39 b.value = 0
40 if len(in) >= 8 {
41 b.fillFastStart()
42 } else {
43 b.fill()
44 b.fill()
45 }
46 b.advance(8 - uint8(highBit32(uint32(v))))
47 return nil
48 }
49
50 // peekByteFast requires that at least one byte is requested every time.
51 // There are no checks if the buffer is filled.
52 func (b *bitReaderBytes) peekByteFast() uint8 {
53 got := uint8(b.value >> 56)
54 return got
55 }
56
57 func (b *bitReaderBytes) advance(n uint8) {
58 b.bitsRead += n
59 b.value <<= n & 63
60 }
61
62 // fillFast() will make sure at least 32 bits are available.
63 // There must be at least 4 bytes available.
64 func (b *bitReaderBytes) fillFast() {
65 if b.bitsRead < 32 {
66 return
67 }
68
69 // 2 bounds checks.
70 low := le.Load32(b.in, b.off-4)
71 b.value |= uint64(low) << (b.bitsRead - 32)
72 b.bitsRead -= 32
73 b.off -= 4
74 }
75
76 // fillFastStart() assumes the bitReaderBytes is empty and there is at least 8 bytes to read.
77 func (b *bitReaderBytes) fillFastStart() {
78 // Do single re-slice to avoid bounds checks.
79 b.value = le.Load64(b.in, b.off-8)
80 b.bitsRead = 0
81 b.off -= 8
82 }
83
84 // fill() will make sure at least 32 bits are available.
85 func (b *bitReaderBytes) fill() {
86 if b.bitsRead < 32 {
87 return
88 }
89 if b.off >= 4 {
90 low := le.Load32(b.in, b.off-4)
91 b.value |= uint64(low) << (b.bitsRead - 32)
92 b.bitsRead -= 32
93 b.off -= 4
94 return
95 }
96 for b.off > 0 {
97 b.value |= uint64(b.in[b.off-1]) << (b.bitsRead - 8)
98 b.bitsRead -= 8
99 b.off--
100 }
101 }
102
103 // finished returns true if all bits have been read from the bit stream.
104 func (b *bitReaderBytes) finished() bool {
105 return b.off == 0 && b.bitsRead >= 64
106 }
107
108 func (b *bitReaderBytes) remaining() uint {
109 return b.off*8 + uint(64-b.bitsRead)
110 }
111
112 // close the bitstream and returns an error if out-of-buffer reads occurred.
113 func (b *bitReaderBytes) close() error {
114 // Release reference.
115 b.in = nil
116 if b.remaining() > 0 {
117 return fmt.Errorf("corrupt input: %d bits remain on stream", b.remaining())
118 }
119 if b.bitsRead > 64 {
120 return io.ErrUnexpectedEOF
121 }
122 return nil
123 }
124
125 // bitReaderShifted reads a bitstream in reverse.
126 // The last set bit indicates the start of the stream and is used
127 // for aligning the input.
128 type bitReaderShifted struct {
129 in []byte
130 off uint // next byte to read is at in[off - 1]
131 value uint64
132 bitsRead uint8
133 }
134
135 // init initializes and resets the bit reader.
136 func (b *bitReaderShifted) init(in []byte) error {
137 if len(in) < 1 {
138 return errors.New("corrupt stream: too short")
139 }
140 b.in = in
141 b.off = uint(len(in))
142 // The highest bit of the last byte indicates where to start
143 v := in[len(in)-1]
144 if v == 0 {
145 return errors.New("corrupt stream, did not find end of stream")
146 }
147 b.bitsRead = 64
148 b.value = 0
149 if len(in) >= 8 {
150 b.fillFastStart()
151 } else {
152 b.fill()
153 b.fill()
154 }
155 b.advance(8 - uint8(highBit32(uint32(v))))
156 return nil
157 }
158
159 // peekBitsFast requires that at least one bit is requested every time.
160 // There are no checks if the buffer is filled.
161 func (b *bitReaderShifted) peekBitsFast(n uint8) uint16 {
162 return uint16(b.value >> ((64 - n) & 63))
163 }
164
165 func (b *bitReaderShifted) advance(n uint8) {
166 b.bitsRead += n
167 b.value <<= n & 63
168 }
169
170 // fillFast() will make sure at least 32 bits are available.
171 // There must be at least 4 bytes available.
172 func (b *bitReaderShifted) fillFast() {
173 if b.bitsRead < 32 {
174 return
175 }
176
177 low := le.Load32(b.in, b.off-4)
178 b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
179 b.bitsRead -= 32
180 b.off -= 4
181 }
182
183 // fillFastStart() assumes the bitReaderShifted is empty and there is at least 8 bytes to read.
184 func (b *bitReaderShifted) fillFastStart() {
185 b.value = le.Load64(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.
191 func (b *bitReaderShifted) fill() {
192 if b.bitsRead < 32 {
193 return
194 }
195 if b.off > 4 {
196 low := le.Load32(b.in, b.off-4)
197 b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
198 b.bitsRead -= 32
199 b.off -= 4
200 return
201 }
202 for b.off > 0 {
203 b.value |= uint64(b.in[b.off-1]) << ((b.bitsRead - 8) & 63)
204 b.bitsRead -= 8
205 b.off--
206 }
207 }
208
209 func (b *bitReaderShifted) remaining() uint {
210 return b.off*8 + uint(64-b.bitsRead)
211 }
212
213 // close the bitstream and returns an error if out-of-buffer reads occurred.
214 func (b *bitReaderShifted) close() error {
215 // Release reference.
216 b.in = nil
217 if b.remaining() > 0 {
218 return fmt.Errorf("corrupt input: %d bits remain on stream", b.remaining())
219 }
220 if b.bitsRead > 64 {
221 return io.ErrUnexpectedEOF
222 }
223 return nil
224 }
225