blob: f65eb3909cf4a59255e0302a96d7e7d3ab21fd29 [file] [log] [blame]
khenaidoo7d3c5582021-08-11 18:09:44 -04001// 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 fse
7
8import (
9 "encoding/binary"
10 "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
38 if len(in) >= 8 {
39 b.fillFastStart()
40 } else {
41 b.fill()
42 b.fill()
43 }
44 b.bitsRead += 8 - uint8(highBits(uint32(v)))
45 return nil
46}
47
48// getBits will return n bits. n can be 0.
49func (b *bitReader) getBits(n uint8) uint16 {
50 if n == 0 || b.bitsRead >= 64 {
51 return 0
52 }
53 return b.getBitsFast(n)
54}
55
56// getBitsFast requires that at least one bit is requested every time.
57// There are no checks if the buffer is filled.
58func (b *bitReader) getBitsFast(n uint8) uint16 {
59 const regMask = 64 - 1
60 v := uint16((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
61 b.bitsRead += n
62 return v
63}
64
65// fillFast() will make sure at least 32 bits are available.
66// There must be at least 4 bytes available.
67func (b *bitReader) fillFast() {
68 if b.bitsRead < 32 {
69 return
70 }
71 // 2 bounds checks.
72 v := b.in[b.off-4:]
73 v = v[:4]
74 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
75 b.value = (b.value << 32) | uint64(low)
76 b.bitsRead -= 32
77 b.off -= 4
78}
79
80// fill() will make sure at least 32 bits are available.
81func (b *bitReader) fill() {
82 if b.bitsRead < 32 {
83 return
84 }
85 if b.off > 4 {
86 v := b.in[b.off-4:]
87 v = v[:4]
88 low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
89 b.value = (b.value << 32) | uint64(low)
90 b.bitsRead -= 32
91 b.off -= 4
92 return
93 }
94 for b.off > 0 {
95 b.value = (b.value << 8) | uint64(b.in[b.off-1])
96 b.bitsRead -= 8
97 b.off--
98 }
99}
100
101// fillFastStart() assumes the bitreader is empty and there is at least 8 bytes to read.
102func (b *bitReader) fillFastStart() {
103 // Do single re-slice to avoid bounds checks.
104 b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
105 b.bitsRead = 0
106 b.off -= 8
107}
108
109// finished returns true if all bits have been read from the bit stream.
110func (b *bitReader) finished() bool {
111 return b.bitsRead >= 64 && b.off == 0
112}
113
114// close the bitstream and returns an error if out-of-buffer reads occurred.
115func (b *bitReader) close() error {
116 // Release reference.
117 b.in = nil
118 if b.bitsRead > 64 {
119 return io.ErrUnexpectedEOF
120 }
121 return nil
122}