blob: 15d79d439fa92ed8abedf06225b1c2cd6d84fdef [file] [log] [blame]
Pragya Arya324337e2020-02-20 14:35:08 +05301// 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
5package zstd
6
7import (
8 "errors"
9 "io"
10 "math/bits"
11)
12
13// bitReader reads a bitstream in reverse.
14// The last set bit indicates the start of the stream and is used
15// for aligning the input.
16type bitReader struct {
17 in []byte
18 off uint // next byte to read is at in[off - 1]
19 value uint64 // Maybe use [16]byte, but shifting is awkward.
20 bitsRead uint8
21}
22
23// init initializes and resets the bit reader.
24func (b *bitReader) init(in []byte) error {
25 if len(in) < 1 {
26 return errors.New("corrupt stream: too short")
27 }
28 b.in = in
29 b.off = uint(len(in))
30 // The highest bit of the last byte indicates where to start
31 v := in[len(in)-1]
32 if v == 0 {
33 return errors.New("corrupt stream, did not find end of stream")
34 }
35 b.bitsRead = 64
36 b.value = 0
37 b.fill()
38 b.fill()
39 b.bitsRead += 8 - uint8(highBits(uint32(v)))
40 return nil
41}
42
43// getBits will return n bits. n can be 0.
44func (b *bitReader) getBits(n uint8) int {
45 if n == 0 /*|| b.bitsRead >= 64 */ {
46 return 0
47 }
48 return b.getBitsFast(n)
49}
50
51// getBitsFast requires that at least one bit is requested every time.
52// There are no checks if the buffer is filled.
53func (b *bitReader) getBitsFast(n uint8) int {
54 const regMask = 64 - 1
55 v := uint32((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
56 b.bitsRead += n
57 return int(v)
58}
59
60// fillFast() will make sure at least 32 bits are available.
61// There must be at least 4 bytes available.
62func (b *bitReader) fillFast() {
63 if b.bitsRead < 32 {
64 return
65 }
66 // Do single re-slice to avoid bounds checks.
67 v := b.in[b.off-4 : b.off]
68 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
69 b.value = (b.value << 32) | uint64(low)
70 b.bitsRead -= 32
71 b.off -= 4
72}
73
74// fill() will make sure at least 32 bits are available.
75func (b *bitReader) fill() {
76 if b.bitsRead < 32 {
77 return
78 }
79 if b.off >= 4 {
80 v := b.in[b.off-4 : b.off]
81 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
82 b.value = (b.value << 32) | uint64(low)
83 b.bitsRead -= 32
84 b.off -= 4
85 return
86 }
87 for b.off > 0 {
88 b.value = (b.value << 8) | uint64(b.in[b.off-1])
89 b.bitsRead -= 8
90 b.off--
91 }
92}
93
94// finished returns true if all bits have been read from the bit stream.
95func (b *bitReader) finished() bool {
96 return b.off == 0 && b.bitsRead >= 64
97}
98
99// overread returns true if more bits have been requested than is on the stream.
100func (b *bitReader) overread() bool {
101 return b.bitsRead > 64
102}
103
104// remain returns the number of bits remaining.
105func (b *bitReader) remain() uint {
106 return b.off*8 + 64 - uint(b.bitsRead)
107}
108
109// close the bitstream and returns an error if out-of-buffer reads occurred.
110func (b *bitReader) close() error {
111 // Release reference.
112 b.in = nil
113 if b.bitsRead > 64 {
114 return io.ErrUnexpectedEOF
115 }
116 return nil
117}
118
119func highBits(val uint32) (n uint32) {
120 return uint32(bits.Len32(val) - 1)
121}