1 /* Copyright 2013 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 /* Bit reading helpers */
9 #ifndef BROTLI_DEC_BIT_READER_H_
10 #define BROTLI_DEC_BIT_READER_H_
17 #if defined(__cplusplus) || defined(c_plusplus)
22 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4
23 typedef uint64_t reg_t
;
25 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2
26 typedef uint32_t reg_t
;
29 static const uint32_t kBitMask
[33] = { 0x0000,
30 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
31 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
32 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
33 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
34 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
35 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
36 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
37 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
40 static BROTLI_INLINE
uint32_t BitMask(uint32_t n
) {
41 if (IS_CONSTANT(n
) || BROTLI_HAS_UBFX
) {
42 /* Masking with this expression turns to a single
43 "Unsigned Bit Field Extract" UBFX instruction on ARM. */
44 return ~((0xffffffffU
) << n
);
51 reg_t val_
; /* pre-fetched bits */
52 uint32_t bit_pos_
; /* current bit-reading position in val_ */
53 const uint8_t* next_in
; /* the byte we're reading from */
60 const uint8_t* next_in
;
62 } BrotliBitReaderState
;
64 /* Initializes the bitreader fields. */
65 void BrotliInitBitReader(BrotliBitReader
* const br
);
67 /* Ensures that accumulator is not empty. May consume one byte of input.
68 Returns 0 if data is required but there is no input available.
69 For BROTLI_BUILD_PORTABLE this function also prepares bit reader for aligned
71 int BrotliWarmupBitReader(BrotliBitReader
* const br
);
73 static BROTLI_INLINE
void BrotliBitReaderSaveState(
74 BrotliBitReader
* const from
, BrotliBitReaderState
* to
) {
75 to
->val_
= from
->val_
;
76 to
->bit_pos_
= from
->bit_pos_
;
77 to
->next_in
= from
->next_in
;
78 to
->avail_in
= from
->avail_in
;
81 static BROTLI_INLINE
void BrotliBitReaderRestoreState(
82 BrotliBitReader
* const to
, BrotliBitReaderState
* from
) {
83 to
->val_
= from
->val_
;
84 to
->bit_pos_
= from
->bit_pos_
;
85 to
->next_in
= from
->next_in
;
86 to
->avail_in
= from
->avail_in
;
89 static BROTLI_INLINE
uint32_t BrotliGetAvailableBits(
90 const BrotliBitReader
* br
) {
91 return (BROTLI_64_BITS
? 64 : 32) - br
->bit_pos_
;
94 /* Returns amount of unread bytes the bit reader still has buffered from the
95 BrotliInput, including whole bytes in br->val_. */
96 static BROTLI_INLINE
size_t BrotliGetRemainingBytes(BrotliBitReader
* br
) {
97 return br
->avail_in
+ (BrotliGetAvailableBits(br
) >> 3);
100 /* Checks if there is at least num bytes left in the input ringbuffer (excluding
101 the bits remaining in br->val_). */
102 static BROTLI_INLINE
int BrotliCheckInputAmount(
103 BrotliBitReader
* const br
, size_t num
) {
104 return br
->avail_in
>= num
;
107 static BROTLI_INLINE
uint16_t BrotliLoad16LE(const uint8_t* in
) {
108 if (BROTLI_LITTLE_ENDIAN
) {
109 return *((const uint16_t*)in
);
110 } else if (BROTLI_BIG_ENDIAN
) {
111 uint16_t value
= *((const uint16_t*)in
);
113 ((value
& 0xFFU
) << 8) |
114 ((value
& 0xFF00U
) >> 8));
116 return (uint16_t)(in
[0] | (in
[1] << 8));
120 static BROTLI_INLINE
uint32_t BrotliLoad32LE(const uint8_t* in
) {
121 if (BROTLI_LITTLE_ENDIAN
) {
122 return *((const uint32_t*)in
);
123 } else if (BROTLI_BIG_ENDIAN
) {
124 uint32_t value
= *((const uint32_t*)in
);
125 return ((value
& 0xFFU
) << 24) | ((value
& 0xFF00U
) << 8) |
126 ((value
& 0xFF0000U
) >> 8) | ((value
& 0xFF000000U
) >> 24);
128 uint32_t value
= (uint32_t)(*(in
++));
129 value
|= (uint32_t)(*(in
++)) << 8;
130 value
|= (uint32_t)(*(in
++)) << 16;
131 value
|= (uint32_t)(*(in
++)) << 24;
137 static BROTLI_INLINE
uint64_t BrotliLoad64LE(const uint8_t* in
) {
138 if (BROTLI_LITTLE_ENDIAN
) {
139 return *((const uint64_t*)in
);
140 } else if (BROTLI_BIG_ENDIAN
) {
141 uint64_t value
= *((const uint64_t*)in
);
143 ((value
& 0xFFU
) << 56) |
144 ((value
& 0xFF00U
) << 40) |
145 ((value
& 0xFF0000U
) << 24) |
146 ((value
& 0xFF000000U
) << 8) |
147 ((value
& 0xFF00000000U
) >> 8) |
148 ((value
& 0xFF0000000000U
) >> 24) |
149 ((value
& 0xFF000000000000U
) >> 40) |
150 ((value
& 0xFF00000000000000U
) >> 56);
152 uint64_t value
= (uint64_t)(*(in
++));
153 value
|= (uint64_t)(*(in
++)) << 8;
154 value
|= (uint64_t)(*(in
++)) << 16;
155 value
|= (uint64_t)(*(in
++)) << 24;
156 value
|= (uint64_t)(*(in
++)) << 32;
157 value
|= (uint64_t)(*(in
++)) << 40;
158 value
|= (uint64_t)(*(in
++)) << 48;
159 value
|= (uint64_t)(*(in
++)) << 56;
165 /* Guarantees that there are at least n_bits + 1 bits in accumulator.
166 Precondition: accumulator contains at least 1 bit.
167 n_bits should be in the range [1..24] for regular build. For portable
168 non-64-bit little endian build only 16 bits are safe to request. */
169 static BROTLI_INLINE
void BrotliFillBitWindow(
170 BrotliBitReader
* const br
, uint32_t n_bits
) {
172 if (!BROTLI_ALIGNED_READ
&& IS_CONSTANT(n_bits
) && (n_bits
<= 8)) {
173 if (br
->bit_pos_
>= 56) {
175 br
->bit_pos_
^= 56; /* here same as -= 56 because of the if condition */
176 br
->val_
|= BrotliLoad64LE(br
->next_in
) << 8;
180 } else if (!BROTLI_ALIGNED_READ
&& IS_CONSTANT(n_bits
) && (n_bits
<= 16)) {
181 if (br
->bit_pos_
>= 48) {
183 br
->bit_pos_
^= 48; /* here same as -= 48 because of the if condition */
184 br
->val_
|= BrotliLoad64LE(br
->next_in
) << 16;
189 if (br
->bit_pos_
>= 32) {
191 br
->bit_pos_
^= 32; /* here same as -= 32 because of the if condition */
192 br
->val_
|= ((uint64_t)BrotliLoad32LE(br
->next_in
)) << 32;
193 br
->avail_in
-= BROTLI_SHORT_FILL_BIT_WINDOW_READ
;
194 br
->next_in
+= BROTLI_SHORT_FILL_BIT_WINDOW_READ
;
198 if (!BROTLI_ALIGNED_READ
&& IS_CONSTANT(n_bits
) && (n_bits
<= 8)) {
199 if (br
->bit_pos_
>= 24) {
201 br
->bit_pos_
^= 24; /* here same as -= 24 because of the if condition */
202 br
->val_
|= BrotliLoad32LE(br
->next_in
) << 8;
207 if (br
->bit_pos_
>= 16) {
209 br
->bit_pos_
^= 16; /* here same as -= 16 because of the if condition */
210 br
->val_
|= ((uint32_t)BrotliLoad16LE(br
->next_in
)) << 16;
211 br
->avail_in
-= BROTLI_SHORT_FILL_BIT_WINDOW_READ
;
212 br
->next_in
+= BROTLI_SHORT_FILL_BIT_WINDOW_READ
;
218 /* Mosltly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
219 more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
220 static BROTLI_INLINE
void BrotliFillBitWindow16(BrotliBitReader
* const br
) {
221 BrotliFillBitWindow(br
, 17);
224 /* Pulls one byte of input to accumulator. */
225 static BROTLI_INLINE
int BrotliPullByte(BrotliBitReader
* const br
) {
226 if (br
->avail_in
== 0) {
231 br
->val_
|= ((uint64_t)*br
->next_in
) << 56;
233 br
->val_
|= ((uint32_t)*br
->next_in
) << 24;
241 /* Returns currently available bits.
242 The number of valid bits could be calclulated by BrotliGetAvailableBits. */
243 static BROTLI_INLINE reg_t
BrotliGetBitsUnmasked(BrotliBitReader
* const br
) {
244 return br
->val_
>> br
->bit_pos_
;
247 /* Like BrotliGetBits, but does not mask the result.
248 The result contains at least 16 valid bits. */
249 static BROTLI_INLINE
uint32_t BrotliGet16BitsUnmasked(
250 BrotliBitReader
* const br
) {
251 BrotliFillBitWindow(br
, 16);
252 return (uint32_t)BrotliGetBitsUnmasked(br
);
255 /* Returns the specified number of bits from br without advancing bit pos. */
256 static BROTLI_INLINE
uint32_t BrotliGetBits(
257 BrotliBitReader
* const br
, uint32_t n_bits
) {
258 BrotliFillBitWindow(br
, n_bits
);
259 return (uint32_t)BrotliGetBitsUnmasked(br
) & BitMask(n_bits
);
262 /* Tries to peek the specified amount of bits. Returns 0, if there is not
264 static BROTLI_INLINE
int BrotliSafeGetBits(
265 BrotliBitReader
* const br
, uint32_t n_bits
, uint32_t* val
) {
266 while (BrotliGetAvailableBits(br
) < n_bits
) {
267 if (!BrotliPullByte(br
)) {
271 *val
= (uint32_t)BrotliGetBitsUnmasked(br
) & BitMask(n_bits
);
275 /* Advances the bit pos by n_bits. */
276 static BROTLI_INLINE
void BrotliDropBits(
277 BrotliBitReader
* const br
, uint32_t n_bits
) {
278 br
->bit_pos_
+= n_bits
;
281 static BROTLI_INLINE
void BrotliBitReaderUnload(BrotliBitReader
* br
) {
282 uint32_t unused_bytes
= BrotliGetAvailableBits(br
) >> 3;
283 uint32_t unused_bits
= unused_bytes
<< 3;
284 br
->avail_in
+= unused_bytes
;
285 br
->next_in
-= unused_bytes
;
286 br
->val_
<<= unused_bits
;
287 br
->bit_pos_
+= unused_bits
;
290 /* Reads the specified number of bits from br and advances the bit pos.
291 Precondition: accumulator MUST contain at least n_bits. */
292 static BROTLI_INLINE
void BrotliTakeBits(
293 BrotliBitReader
* const br
, uint32_t n_bits
, uint32_t* val
) {
294 *val
= (uint32_t)BrotliGetBitsUnmasked(br
) & BitMask(n_bits
);
295 #ifdef BROTLI_DECODE_DEBUG
296 printf("[BrotliReadBits] %d %d %d val: %6x\n",
297 (int)br
->avail_in
, (int)br
->bit_pos_
, n_bits
, (int)*val
);
299 BrotliDropBits(br
, n_bits
);
302 /* Reads the specified number of bits from br and advances the bit pos.
303 Assumes that there is enough input to perform BrotliFillBitWindow. */
304 static BROTLI_INLINE
uint32_t BrotliReadBits(
305 BrotliBitReader
* const br
, uint32_t n_bits
) {
306 if (BROTLI_64_BITS
|| (n_bits
<= 16)) {
308 BrotliFillBitWindow(br
, n_bits
);
309 BrotliTakeBits(br
, n_bits
, &val
);
314 BrotliFillBitWindow(br
, 16);
315 BrotliTakeBits(br
, 16, &low_val
);
316 BrotliFillBitWindow(br
, 8);
317 BrotliTakeBits(br
, n_bits
- 16, &high_val
);
318 return low_val
| (high_val
<< 16);
322 /* Tries to read the specified amount of bits. Returns 0, if there is not
323 enough input. n_bits MUST be positive. */
324 static BROTLI_INLINE
int BrotliSafeReadBits(
325 BrotliBitReader
* const br
, uint32_t n_bits
, uint32_t* val
) {
326 while (BrotliGetAvailableBits(br
) < n_bits
) {
327 if (!BrotliPullByte(br
)) {
331 BrotliTakeBits(br
, n_bits
, val
);
335 /* Advances the bit reader position to the next byte boundary and verifies
336 that any skipped bits are set to zero. */
337 static BROTLI_INLINE
int BrotliJumpToByteBoundary(BrotliBitReader
* br
) {
338 uint32_t pad_bits_count
= BrotliGetAvailableBits(br
) & 0x7;
339 uint32_t pad_bits
= 0;
340 if (pad_bits_count
!= 0) {
341 BrotliTakeBits(br
, pad_bits_count
, &pad_bits
);
343 return pad_bits
== 0;
346 /* Peeks a byte at specified offset.
347 Precondition: bit reader is parked to a byte boundary.
348 Returns -1 if operation is not feasible. */
349 static BROTLI_INLINE
int BrotliPeekByte(BrotliBitReader
* br
, size_t offset
) {
350 uint32_t available_bits
= BrotliGetAvailableBits(br
);
351 size_t bytes_left
= available_bits
>> 3;
352 if (available_bits
& 7) {
355 if (offset
< bytes_left
) {
356 return (BrotliGetBitsUnmasked(br
) >> (unsigned)(offset
<< 3)) & 0xFF;
358 offset
-= bytes_left
;
359 if (offset
< br
->avail_in
) {
360 return br
->next_in
[offset
];
365 /* Copies remaining input bytes stored in the bit reader to the output. Value
366 num may not be larger than BrotliGetRemainingBytes. The bit reader must be
367 warmed up again after this. */
368 static BROTLI_INLINE
void BrotliCopyBytes(uint8_t* dest
,
369 BrotliBitReader
* br
, size_t num
) {
370 while (BrotliGetAvailableBits(br
) >= 8 && num
> 0) {
371 *dest
= (uint8_t)BrotliGetBitsUnmasked(br
);
372 BrotliDropBits(br
, 8);
376 memcpy(dest
, br
->next_in
, num
);
381 #if defined(__cplusplus) || defined(c_plusplus)
385 #endif /* BROTLI_DEC_BIT_READER_H_ */