blob: b9db204f59d6bde459a287baf0f421cd42f63ce0 [file] [log] [blame]
Dinesh Belwalkare63f7f92019-11-22 23:11:16 +00001// 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 "errors"
10 "io"
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
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) uint16 {
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) uint16 {
54 const regMask = 64 - 1
55 v := uint16((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
56 b.bitsRead += n
57 return 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// close the bitstream and returns an error if out-of-buffer reads occurred.
100func (b *bitReader) close() error {
101 // Release reference.
102 b.in = nil
103 if b.bitsRead > 64 {
104 return io.ErrUnexpectedEOF
105 }
106 return nil
107}