1// Copyright 2023 The Go Authors. 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
5package zstd
6
7import (
8	"math/bits"
9)
10
11// block is the data for a single compressed block.
12// The data starts immediately after the 3 byte block header,
13// and is Block_Size bytes long.
14type block []byte
15
16// bitReader reads a bit stream going forward.
17type bitReader struct {
18	r    *Reader // for error reporting
19	data block   // the bits to read
20	off  uint32  // current offset into data
21	bits uint32  // bits ready to be returned
22	cnt  uint32  // number of valid bits in the bits field
23}
24
25// makeBitReader makes a bit reader starting at off.
26func (r *Reader) makeBitReader(data block, off int) bitReader {
27	return bitReader{
28		r:    r,
29		data: data,
30		off:  uint32(off),
31	}
32}
33
34// moreBits is called to read more bits.
35// This ensures that at least 16 bits are available.
36func (br *bitReader) moreBits() error {
37	for br.cnt < 16 {
38		if br.off >= uint32(len(br.data)) {
39			return br.r.makeEOFError(int(br.off))
40		}
41		c := br.data[br.off]
42		br.off++
43		br.bits |= uint32(c) << br.cnt
44		br.cnt += 8
45	}
46	return nil
47}
48
49// val is called to fetch a value of b bits.
50func (br *bitReader) val(b uint8) uint32 {
51	r := br.bits & ((1 << b) - 1)
52	br.bits >>= b
53	br.cnt -= uint32(b)
54	return r
55}
56
57// backup steps back to the last byte we used.
58func (br *bitReader) backup() {
59	for br.cnt >= 8 {
60		br.off--
61		br.cnt -= 8
62	}
63}
64
65// makeError returns an error at the current offset wrapping a string.
66func (br *bitReader) makeError(msg string) error {
67	return br.r.makeError(int(br.off), msg)
68}
69
70// reverseBitReader reads a bit stream in reverse.
71type reverseBitReader struct {
72	r     *Reader // for error reporting
73	data  block   // the bits to read
74	off   uint32  // current offset into data
75	start uint32  // start in data; we read backward to start
76	bits  uint32  // bits ready to be returned
77	cnt   uint32  // number of valid bits in bits field
78}
79
80// makeReverseBitReader makes a reverseBitReader reading backward
81// from off to start. The bitstream starts with a 1 bit in the last
82// byte, at off.
83func (r *Reader) makeReverseBitReader(data block, off, start int) (reverseBitReader, error) {
84	streamStart := data[off]
85	if streamStart == 0 {
86		return reverseBitReader{}, r.makeError(off, "zero byte at reverse bit stream start")
87	}
88	rbr := reverseBitReader{
89		r:     r,
90		data:  data,
91		off:   uint32(off),
92		start: uint32(start),
93		bits:  uint32(streamStart),
94		cnt:   uint32(7 - bits.LeadingZeros8(streamStart)),
95	}
96	return rbr, nil
97}
98
99// val is called to fetch a value of b bits.
100func (rbr *reverseBitReader) val(b uint8) (uint32, error) {
101	if !rbr.fetch(b) {
102		return 0, rbr.r.makeEOFError(int(rbr.off))
103	}
104
105	rbr.cnt -= uint32(b)
106	v := (rbr.bits >> rbr.cnt) & ((1 << b) - 1)
107	return v, nil
108}
109
110// fetch is called to ensure that at least b bits are available.
111// It reports false if this can't be done,
112// in which case only rbr.cnt bits are available.
113func (rbr *reverseBitReader) fetch(b uint8) bool {
114	for rbr.cnt < uint32(b) {
115		if rbr.off <= rbr.start {
116			return false
117		}
118		rbr.off--
119		c := rbr.data[rbr.off]
120		rbr.bits <<= 8
121		rbr.bits |= uint32(c)
122		rbr.cnt += 8
123	}
124	return true
125}
126
127// makeError returns an error at the current offset wrapping a string.
128func (rbr *reverseBitReader) makeError(msg string) error {
129	return rbr.r.makeError(int(rbr.off), msg)
130}
131