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
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}
108