cubefs

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 fse
7

8
import (
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.
17
type 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.
25
func (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.
49
func (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.
58
func (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.
67
func (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.
81
func (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.
102
func (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.
110
func (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.
115
func (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
}
123