1/* Copyright 2013 Google Inc. All Rights Reserved.
2
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5*/
6
7/* Bit reading helpers */
8
9#ifndef BROTLI_DEC_BIT_READER_H_
10#define BROTLI_DEC_BIT_READER_H_
11
12#include <string.h> /* memcpy */
13
14#include <brotli/types.h>
15
16#include "../common/constants.h"
17#include "../common/platform.h"
18
19#if defined(__cplusplus) || defined(c_plusplus)
20extern "C" {
21#endif
22
23#define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1)
24
25BROTLI_INTERNAL extern const uint32_t kBrotliBitMask[33];
26
27static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
28 if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
29 /* Masking with this expression turns to a single
30 "Unsigned Bit Field Extract" UBFX instruction on ARM. */
31 return ~((0xFFFFFFFFu) << n);
32 } else {
33 return kBrotliBitMask[n];
34 }
35}
36
37typedef struct {
38 brotli_reg_t val_; /* pre-fetched bits */
39 uint32_t bit_pos_; /* current bit-reading position in val_ */
40 const uint8_t* next_in; /* the byte we're reading from */
41 size_t avail_in;
42} BrotliBitReader;
43
44typedef struct {
45 brotli_reg_t val_;
46 uint32_t bit_pos_;
47 const uint8_t* next_in;
48 size_t avail_in;
49} BrotliBitReaderState;
50
51/* Initializes the BrotliBitReader fields. */
52BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);
53
54/* Ensures that accumulator is not empty.
55 May consume up to sizeof(brotli_reg_t) - 1 bytes of input.
56 Returns BROTLI_FALSE if data is required but there is no input available.
57 For !BROTLI_UNALIGNED_READ_FAST this function also prepares bit reader for
58 aligned reading. */
59BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);
60
61/* Fallback for BrotliSafeReadBits32. Extracted as noninlined method to unburden
62 the main code-path. Never called for RFC brotli streams, required only for
63 "large-window" mode and other extensions. */
64BROTLI_INTERNAL BROTLI_NOINLINE BROTLI_BOOL BrotliSafeReadBits32Slow(
65 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val);
66
67static BROTLI_INLINE void BrotliBitReaderSaveState(
68 BrotliBitReader* const from, BrotliBitReaderState* to) {
69 to->val_ = from->val_;
70 to->bit_pos_ = from->bit_pos_;
71 to->next_in = from->next_in;
72 to->avail_in = from->avail_in;
73}
74
75static BROTLI_INLINE void BrotliBitReaderRestoreState(
76 BrotliBitReader* const to, BrotliBitReaderState* from) {
77 to->val_ = from->val_;
78 to->bit_pos_ = from->bit_pos_;
79 to->next_in = from->next_in;
80 to->avail_in = from->avail_in;
81}
82
83static BROTLI_INLINE uint32_t BrotliGetAvailableBits(
84 const BrotliBitReader* br) {
85 return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;
86}
87
88/* Returns amount of unread bytes the bit reader still has buffered from the
89 BrotliInput, including whole bytes in br->val_. Result is capped with
90 maximal ring-buffer size (larger number won't be utilized anyway). */
91static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
92 static const size_t kCap = (size_t)1 << BROTLI_LARGE_MAX_WBITS;
93 if (br->avail_in > kCap) return kCap;
94 return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
95}
96
97/* Checks if there is at least |num| bytes left in the input ring-buffer
98 (excluding the bits remaining in br->val_). */
99static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(
100 BrotliBitReader* const br, size_t num) {
101 return TO_BROTLI_BOOL(br->avail_in >= num);
102}
103
104/* Guarantees that there are at least |n_bits| + 1 bits in accumulator.
105 Precondition: accumulator contains at least 1 bit.
106 |n_bits| should be in the range [1..24] for regular build. For portable
107 non-64-bit little-endian build only 16 bits are safe to request. */
108static BROTLI_INLINE void BrotliFillBitWindow(
109 BrotliBitReader* const br, uint32_t n_bits) {
110#if (BROTLI_64_BITS)
111 if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) &&
112 (n_bits <= 8)) {
113 uint32_t bit_pos = br->bit_pos_;
114 if (bit_pos >= 56) {
115 br->val_ =
116 (br->val_ >> 56) | (BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 8);
117 br->bit_pos_ =
118 bit_pos ^ 56; /* here same as -= 56 because of the if condition */
119 br->avail_in -= 7;
120 br->next_in += 7;
121 }
122 } else if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) &&
123 (n_bits <= 16)) {
124 uint32_t bit_pos = br->bit_pos_;
125 if (bit_pos >= 48) {
126 br->val_ =
127 (br->val_ >> 48) | (BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 16);
128 br->bit_pos_ =
129 bit_pos ^ 48; /* here same as -= 48 because of the if condition */
130 br->avail_in -= 6;
131 br->next_in += 6;
132 }
133 } else {
134 uint32_t bit_pos = br->bit_pos_;
135 if (bit_pos >= 32) {
136 br->val_ = (br->val_ >> 32) |
137 (((uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in)) << 32);
138 br->bit_pos_ =
139 bit_pos ^ 32; /* here same as -= 32 because of the if condition */
140 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
141 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
142 }
143 }
144#else
145 if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) &&
146 (n_bits <= 8)) {
147 uint32_t bit_pos = br->bit_pos_;
148 if (bit_pos >= 24) {
149 br->val_ =
150 (br->val_ >> 24) | (BROTLI_UNALIGNED_LOAD32LE(br->next_in) << 8);
151 br->bit_pos_ =
152 bit_pos ^ 24; /* here same as -= 24 because of the if condition */
153 br->avail_in -= 3;
154 br->next_in += 3;
155 }
156 } else {
157 uint32_t bit_pos = br->bit_pos_;
158 if (bit_pos >= 16) {
159 br->val_ = (br->val_ >> 16) |
160 (((uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in)) << 16);
161 br->bit_pos_ =
162 bit_pos ^ 16; /* here same as -= 16 because of the if condition */
163 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
164 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
165 }
166 }
167#endif
168}
169
170/* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
171 more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
172static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
173 BrotliFillBitWindow(br, 17);
174}
175
176/* Tries to pull one byte of input to accumulator.
177 Returns BROTLI_FALSE if there is no input available. */
178static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {
179 if (br->avail_in == 0) {
180 return BROTLI_FALSE;
181 }
182 br->val_ >>= 8;
183#if (BROTLI_64_BITS)
184 br->val_ |= ((uint64_t)*br->next_in) << 56;
185#else
186 br->val_ |= ((uint32_t)*br->next_in) << 24;
187#endif
188 br->bit_pos_ -= 8;
189 --br->avail_in;
190 ++br->next_in;
191 return BROTLI_TRUE;
192}
193
194/* Returns currently available bits.
195 The number of valid bits could be calculated by BrotliGetAvailableBits. */
196static BROTLI_INLINE brotli_reg_t BrotliGetBitsUnmasked(
197 BrotliBitReader* const br) {
198 return br->val_ >> br->bit_pos_;
199}
200
201/* Like BrotliGetBits, but does not mask the result.
202 The result contains at least 16 valid bits. */
203static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(
204 BrotliBitReader* const br) {
205 BrotliFillBitWindow(br, 16);
206 return (uint32_t)BrotliGetBitsUnmasked(br);
207}
208
209/* Returns the specified number of bits from |br| without advancing bit
210 position. */
211static BROTLI_INLINE uint32_t BrotliGetBits(
212 BrotliBitReader* const br, uint32_t n_bits) {
213 BrotliFillBitWindow(br, n_bits);
214 return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
215}
216
217/* Tries to peek the specified amount of bits. Returns BROTLI_FALSE, if there
218 is not enough input. */
219static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(
220 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
221 while (BrotliGetAvailableBits(br) < n_bits) {
222 if (!BrotliPullByte(br)) {
223 return BROTLI_FALSE;
224 }
225 }
226 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
227 return BROTLI_TRUE;
228}
229
230/* Advances the bit pos by |n_bits|. */
231static BROTLI_INLINE void BrotliDropBits(
232 BrotliBitReader* const br, uint32_t n_bits) {
233 br->bit_pos_ += n_bits;
234}
235
236static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
237 uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
238 uint32_t unused_bits = unused_bytes << 3;
239 br->avail_in += unused_bytes;
240 br->next_in -= unused_bytes;
241 if (unused_bits == sizeof(br->val_) << 3) {
242 br->val_ = 0;
243 } else {
244 br->val_ <<= unused_bits;
245 }
246 br->bit_pos_ += unused_bits;
247}
248
249/* Reads the specified number of bits from |br| and advances the bit pos.
250 Precondition: accumulator MUST contain at least |n_bits|. */
251static BROTLI_INLINE void BrotliTakeBits(
252 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
253 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
254 BROTLI_LOG(("[BrotliTakeBits] %d %d %d val: %6x\n",
255 (int)br->avail_in, (int)br->bit_pos_, (int)n_bits, (int)*val));
256 BrotliDropBits(br, n_bits);
257}
258
259/* Reads the specified number of bits from |br| and advances the bit pos.
260 Assumes that there is enough input to perform BrotliFillBitWindow.
261 Up to 24 bits are allowed to be requested from this method. */
262static BROTLI_INLINE uint32_t BrotliReadBits24(
263 BrotliBitReader* const br, uint32_t n_bits) {
264 BROTLI_DCHECK(n_bits <= 24);
265 if (BROTLI_64_BITS || (n_bits <= 16)) {
266 uint32_t val;
267 BrotliFillBitWindow(br, n_bits);
268 BrotliTakeBits(br, n_bits, &val);
269 return val;
270 } else {
271 uint32_t low_val;
272 uint32_t high_val;
273 BrotliFillBitWindow(br, 16);
274 BrotliTakeBits(br, 16, &low_val);
275 BrotliFillBitWindow(br, 8);
276 BrotliTakeBits(br, n_bits - 16, &high_val);
277 return low_val | (high_val << 16);
278 }
279}
280
281/* Same as BrotliReadBits24, but allows reading up to 32 bits. */
282static BROTLI_INLINE uint32_t BrotliReadBits32(
283 BrotliBitReader* const br, uint32_t n_bits) {
284 BROTLI_DCHECK(n_bits <= 32);
285 if (BROTLI_64_BITS || (n_bits <= 16)) {
286 uint32_t val;
287 BrotliFillBitWindow(br, n_bits);
288 BrotliTakeBits(br, n_bits, &val);
289 return val;
290 } else {
291 uint32_t low_val;
292 uint32_t high_val;
293 BrotliFillBitWindow(br, 16);
294 BrotliTakeBits(br, 16, &low_val);
295 BrotliFillBitWindow(br, 16);
296 BrotliTakeBits(br, n_bits - 16, &high_val);
297 return low_val | (high_val << 16);
298 }
299}
300
301/* Tries to read the specified amount of bits. Returns BROTLI_FALSE, if there
302 is not enough input. |n_bits| MUST be positive.
303 Up to 24 bits are allowed to be requested from this method. */
304static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(
305 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
306 BROTLI_DCHECK(n_bits <= 24);
307 while (BrotliGetAvailableBits(br) < n_bits) {
308 if (!BrotliPullByte(br)) {
309 return BROTLI_FALSE;
310 }
311 }
312 BrotliTakeBits(br, n_bits, val);
313 return BROTLI_TRUE;
314}
315
316/* Same as BrotliSafeReadBits, but allows reading up to 32 bits. */
317static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits32(
318 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
319 BROTLI_DCHECK(n_bits <= 32);
320 if (BROTLI_64_BITS || (n_bits <= 24)) {
321 while (BrotliGetAvailableBits(br) < n_bits) {
322 if (!BrotliPullByte(br)) {
323 return BROTLI_FALSE;
324 }
325 }
326 BrotliTakeBits(br, n_bits, val);
327 return BROTLI_TRUE;
328 } else {
329 return BrotliSafeReadBits32Slow(br, n_bits, val);
330 }
331}
332
333/* Advances the bit reader position to the next byte boundary and verifies
334 that any skipped bits are set to zero. */
335static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {
336 uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;
337 uint32_t pad_bits = 0;
338 if (pad_bits_count != 0) {
339 BrotliTakeBits(br, pad_bits_count, &pad_bits);
340 }
341 return TO_BROTLI_BOOL(pad_bits == 0);
342}
343
344static BROTLI_INLINE void BrotliDropBytes(BrotliBitReader* br, size_t num) {
345 br->avail_in -= num;
346 br->next_in += num;
347}
348
349/* Copies remaining input bytes stored in the bit reader to the output. Value
350 |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be
351 warmed up again after this. */
352static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
353 BrotliBitReader* br, size_t num) {
354 while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
355 *dest = (uint8_t)BrotliGetBitsUnmasked(br);
356 BrotliDropBits(br, 8);
357 ++dest;
358 --num;
359 }
360 if (num > 0) {
361 memcpy(dest, br->next_in, num);
362 BrotliDropBytes(br, num);
363 }
364}
365
366#if defined(__cplusplus) || defined(c_plusplus)
367} /* extern "C" */
368#endif
369
370#endif /* BROTLI_DEC_BIT_READER_H_ */
371