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 5 package zstd
6 7 import (
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.
14 type block []byte
15 16 // bitReader reads a bit stream going forward.
17 type 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.
26 func (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.
36 func (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.
50 func (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.
58 func (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.
66 func (br *bitReader) makeError(msg []byte) error {
67 return br.r.makeError(int(br.off), msg)
68 }
69 70 // reverseBitReader reads a bit stream in reverse.
71 type 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.
83 func (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.
100 func (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.
113 func (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.
128 func (rbr *reverseBitReader) makeError(msg []byte) error {
129 return rbr.r.makeError(int(rbr.off), msg)
130 }
131