1package brotli
2
3import "encoding/binary"
4
5/* Copyright 2013 Google Inc. All Rights Reserved.
6
7   Distributed under MIT license.
8   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
9*/
10
11/* Bit reading helpers */
12
13const shortFillBitWindowRead = (8 >> 1)
14
15var kBitMask = [33]uint32{
16	0x00000000,
17	0x00000001,
18	0x00000003,
19	0x00000007,
20	0x0000000F,
21	0x0000001F,
22	0x0000003F,
23	0x0000007F,
24	0x000000FF,
25	0x000001FF,
26	0x000003FF,
27	0x000007FF,
28	0x00000FFF,
29	0x00001FFF,
30	0x00003FFF,
31	0x00007FFF,
32	0x0000FFFF,
33	0x0001FFFF,
34	0x0003FFFF,
35	0x0007FFFF,
36	0x000FFFFF,
37	0x001FFFFF,
38	0x003FFFFF,
39	0x007FFFFF,
40	0x00FFFFFF,
41	0x01FFFFFF,
42	0x03FFFFFF,
43	0x07FFFFFF,
44	0x0FFFFFFF,
45	0x1FFFFFFF,
46	0x3FFFFFFF,
47	0x7FFFFFFF,
48	0xFFFFFFFF,
49}
50
51func bitMask(n uint32) uint32 {
52	return kBitMask[n]
53}
54
55type bitReader struct {
56	val_      uint64
57	bit_pos_  uint32
58	input     []byte
59	input_len uint
60	byte_pos  uint
61}
62
63type bitReaderState struct {
64	val_      uint64
65	bit_pos_  uint32
66	input     []byte
67	input_len uint
68	byte_pos  uint
69}
70
71/* Initializes the BrotliBitReader fields. */
72
73/* Ensures that accumulator is not empty.
74   May consume up to sizeof(brotli_reg_t) - 1 bytes of input.
75   Returns false if data is required but there is no input available.
76   For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned
77   reading. */
78func bitReaderSaveState(from *bitReader, to *bitReaderState) {
79	to.val_ = from.val_
80	to.bit_pos_ = from.bit_pos_
81	to.input = from.input
82	to.input_len = from.input_len
83	to.byte_pos = from.byte_pos
84}
85
86func bitReaderRestoreState(to *bitReader, from *bitReaderState) {
87	to.val_ = from.val_
88	to.bit_pos_ = from.bit_pos_
89	to.input = from.input
90	to.input_len = from.input_len
91	to.byte_pos = from.byte_pos
92}
93
94func getAvailableBits(br *bitReader) uint32 {
95	return 64 - br.bit_pos_
96}
97
98/* Returns amount of unread bytes the bit reader still has buffered from the
99   BrotliInput, including whole bytes in br->val_. */
100func getRemainingBytes(br *bitReader) uint {
101	return uint(uint32(br.input_len-br.byte_pos) + (getAvailableBits(br) >> 3))
102}
103
104/* Checks if there is at least |num| bytes left in the input ring-buffer
105   (excluding the bits remaining in br->val_). */
106func checkInputAmount(br *bitReader, num uint) bool {
107	return br.input_len-br.byte_pos >= num
108}
109
110/* Guarantees that there are at least |n_bits| + 1 bits in accumulator.
111   Precondition: accumulator contains at least 1 bit.
112   |n_bits| should be in the range [1..24] for regular build. For portable
113   non-64-bit little-endian build only 16 bits are safe to request. */
114func fillBitWindow(br *bitReader, n_bits uint32) {
115	if br.bit_pos_ >= 32 {
116		br.val_ >>= 32
117		br.bit_pos_ ^= 32 /* here same as -= 32 because of the if condition */
118		br.val_ |= (uint64(binary.LittleEndian.Uint32(br.input[br.byte_pos:]))) << 32
119		br.byte_pos += 4
120	}
121}
122
123/* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
124   more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
125func fillBitWindow16(br *bitReader) {
126	fillBitWindow(br, 17)
127}
128
129/* Tries to pull one byte of input to accumulator.
130   Returns false if there is no input available. */
131func pullByte(br *bitReader) bool {
132	if br.byte_pos == br.input_len {
133		return false
134	}
135
136	br.val_ >>= 8
137	br.val_ |= (uint64(br.input[br.byte_pos])) << 56
138	br.bit_pos_ -= 8
139	br.byte_pos++
140	return true
141}
142
143/* Returns currently available bits.
144   The number of valid bits could be calculated by BrotliGetAvailableBits. */
145func getBitsUnmasked(br *bitReader) uint64 {
146	return br.val_ >> br.bit_pos_
147}
148
149/* Like BrotliGetBits, but does not mask the result.
150   The result contains at least 16 valid bits. */
151func get16BitsUnmasked(br *bitReader) uint32 {
152	fillBitWindow(br, 16)
153	return uint32(getBitsUnmasked(br))
154}
155
156/* Returns the specified number of bits from |br| without advancing bit
157   position. */
158func getBits(br *bitReader, n_bits uint32) uint32 {
159	fillBitWindow(br, n_bits)
160	return uint32(getBitsUnmasked(br)) & bitMask(n_bits)
161}
162
163/* Tries to peek the specified amount of bits. Returns false, if there
164   is not enough input. */
165func safeGetBits(br *bitReader, n_bits uint32, val *uint32) bool {
166	for getAvailableBits(br) < n_bits {
167		if !pullByte(br) {
168			return false
169		}
170	}
171
172	*val = uint32(getBitsUnmasked(br)) & bitMask(n_bits)
173	return true
174}
175
176/* Advances the bit pos by |n_bits|. */
177func dropBits(br *bitReader, n_bits uint32) {
178	br.bit_pos_ += n_bits
179}
180
181func bitReaderUnload(br *bitReader) {
182	var unused_bytes uint32 = getAvailableBits(br) >> 3
183	var unused_bits uint32 = unused_bytes << 3
184	br.byte_pos -= uint(unused_bytes)
185	if unused_bits == 64 {
186		br.val_ = 0
187	} else {
188		br.val_ <<= unused_bits
189	}
190
191	br.bit_pos_ += unused_bits
192}
193
194/* Reads the specified number of bits from |br| and advances the bit pos.
195   Precondition: accumulator MUST contain at least |n_bits|. */
196func takeBits(br *bitReader, n_bits uint32, val *uint32) {
197	*val = uint32(getBitsUnmasked(br)) & bitMask(n_bits)
198	dropBits(br, n_bits)
199}
200
201/* Reads the specified number of bits from |br| and advances the bit pos.
202   Assumes that there is enough input to perform BrotliFillBitWindow. */
203func readBits(br *bitReader, n_bits uint32) uint32 {
204	var val uint32
205	fillBitWindow(br, n_bits)
206	takeBits(br, n_bits, &val)
207	return val
208}
209
210/* Tries to read the specified amount of bits. Returns false, if there
211   is not enough input. |n_bits| MUST be positive. */
212func safeReadBits(br *bitReader, n_bits uint32, val *uint32) bool {
213	for getAvailableBits(br) < n_bits {
214		if !pullByte(br) {
215			return false
216		}
217	}
218
219	takeBits(br, n_bits, val)
220	return true
221}
222
223/* Advances the bit reader position to the next byte boundary and verifies
224   that any skipped bits are set to zero. */
225func bitReaderJumpToByteBoundary(br *bitReader) bool {
226	var pad_bits_count uint32 = getAvailableBits(br) & 0x7
227	var pad_bits uint32 = 0
228	if pad_bits_count != 0 {
229		takeBits(br, pad_bits_count, &pad_bits)
230	}
231
232	return pad_bits == 0
233}
234
235/* Copies remaining input bytes stored in the bit reader to the output. Value
236   |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be
237   warmed up again after this. */
238func copyBytes(dest []byte, br *bitReader, num uint) {
239	for getAvailableBits(br) >= 8 && num > 0 {
240		dest[0] = byte(getBitsUnmasked(br))
241		dropBits(br, 8)
242		dest = dest[1:]
243		num--
244	}
245
246	copy(dest, br.input[br.byte_pos:][:num])
247	br.byte_pos += num
248}
249
250func initBitReader(br *bitReader) {
251	br.val_ = 0
252	br.bit_pos_ = 64
253}
254
255func warmupBitReader(br *bitReader) bool {
256	/* Fixing alignment after unaligned BrotliFillWindow would result accumulator
257	   overflow. If unalignment is caused by BrotliSafeReadBits, then there is
258	   enough space in accumulator to fix alignment. */
259	if getAvailableBits(br) == 0 {
260		if !pullByte(br) {
261			return false
262		}
263	}
264
265	return true
266}
267