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 "../common/platform.h"
15#include <brotli/types.h>
16
17#if defined(__cplusplus) || defined(c_plusplus)
18extern "C" {
19#endif
20
21#define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1)
22
23static const uint32_t kBitMask[33] = { 0x00000000,
24 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
25 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
26 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
27 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
28 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
29 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
30 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
31 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
32};
33
34static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
35 if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
36 /* Masking with this expression turns to a single
37 "Unsigned Bit Field Extract" UBFX instruction on ARM. */
38 return ~((0xFFFFFFFFu) << n);
39 } else {
40 return kBitMask[n];
41 }
42}
43
44typedef struct {
45 brotli_reg_t val_; /* pre-fetched bits */
46 uint32_t bit_pos_; /* current bit-reading position in val_ */
47 const uint8_t* next_in; /* the byte we're reading from */
48 size_t avail_in;
49} BrotliBitReader;
50
51typedef struct {
52 brotli_reg_t val_;
53 uint32_t bit_pos_;
54 const uint8_t* next_in;
55 size_t avail_in;
56} BrotliBitReaderState;
57
58/* Initializes the BrotliBitReader fields. */
59BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);
60
61/* Ensures that accumulator is not empty.
62 May consume up to sizeof(brotli_reg_t) - 1 bytes of input.
63 Returns BROTLI_FALSE if data is required but there is no input available.
64 For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned
65 reading. */
66BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);
67
68static BROTLI_INLINE void BrotliBitReaderSaveState(
69 BrotliBitReader* const from, BrotliBitReaderState* to) {
70 to->val_ = from->val_;
71 to->bit_pos_ = from->bit_pos_;
72 to->next_in = from->next_in;
73 to->avail_in = from->avail_in;
74}
75
76static BROTLI_INLINE void BrotliBitReaderRestoreState(
77 BrotliBitReader* const to, BrotliBitReaderState* from) {
78 to->val_ = from->val_;
79 to->bit_pos_ = from->bit_pos_;
80 to->next_in = from->next_in;
81 to->avail_in = from->avail_in;
82}
83
84static BROTLI_INLINE uint32_t BrotliGetAvailableBits(
85 const BrotliBitReader* br) {
86 return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;
87}
88
89/* Returns amount of unread bytes the bit reader still has buffered from the
90 BrotliInput, including whole bytes in br->val_. */
91static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
92 return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
93}
94
95/* Checks if there is at least |num| bytes left in the input ring-buffer
96 (excluding the bits remaining in br->val_). */
97static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(
98 BrotliBitReader* const br, size_t num) {
99 return TO_BROTLI_BOOL(br->avail_in >= num);
100}
101
102/* Guarantees that there are at least |n_bits| + 1 bits in accumulator.
103 Precondition: accumulator contains at least 1 bit.
104 |n_bits| should be in the range [1..24] for regular build. For portable
105 non-64-bit little-endian build only 16 bits are safe to request. */
106static BROTLI_INLINE void BrotliFillBitWindow(
107 BrotliBitReader* const br, uint32_t n_bits) {
108#if (BROTLI_64_BITS)
109 if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) {
110 if (br->bit_pos_ >= 56) {
111 br->val_ >>= 56;
112 br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */
113 br->val_ |= BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 8;
114 br->avail_in -= 7;
115 br->next_in += 7;
116 }
117 } else if (
118 !BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 16)) {
119 if (br->bit_pos_ >= 48) {
120 br->val_ >>= 48;
121 br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */
122 br->val_ |= BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 16;
123 br->avail_in -= 6;
124 br->next_in += 6;
125 }
126 } else {
127 if (br->bit_pos_ >= 32) {
128 br->val_ >>= 32;
129 br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */
130 br->val_ |= ((uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in)) << 32;
131 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
132 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
133 }
134 }
135#else
136 if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) {
137 if (br->bit_pos_ >= 24) {
138 br->val_ >>= 24;
139 br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */
140 br->val_ |= BROTLI_UNALIGNED_LOAD32LE(br->next_in) << 8;
141 br->avail_in -= 3;
142 br->next_in += 3;
143 }
144 } else {
145 if (br->bit_pos_ >= 16) {
146 br->val_ >>= 16;
147 br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */
148 br->val_ |= ((uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in)) << 16;
149 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
150 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
151 }
152 }
153#endif
154}
155
156/* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
157 more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
158static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
159 BrotliFillBitWindow(br, 17);
160}
161
162/* Tries to pull one byte of input to accumulator.
163 Returns BROTLI_FALSE if there is no input available. */
164static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {
165 if (br->avail_in == 0) {
166 return BROTLI_FALSE;
167 }
168 br->val_ >>= 8;
169#if (BROTLI_64_BITS)
170 br->val_ |= ((uint64_t)*br->next_in) << 56;
171#else
172 br->val_ |= ((uint32_t)*br->next_in) << 24;
173#endif
174 br->bit_pos_ -= 8;
175 --br->avail_in;
176 ++br->next_in;
177 return BROTLI_TRUE;
178}
179
180/* Returns currently available bits.
181 The number of valid bits could be calculated by BrotliGetAvailableBits. */
182static BROTLI_INLINE brotli_reg_t BrotliGetBitsUnmasked(
183 BrotliBitReader* const br) {
184 return br->val_ >> br->bit_pos_;
185}
186
187/* Like BrotliGetBits, but does not mask the result.
188 The result contains at least 16 valid bits. */
189static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(
190 BrotliBitReader* const br) {
191 BrotliFillBitWindow(br, 16);
192 return (uint32_t)BrotliGetBitsUnmasked(br);
193}
194
195/* Returns the specified number of bits from |br| without advancing bit
196 position. */
197static BROTLI_INLINE uint32_t BrotliGetBits(
198 BrotliBitReader* const br, uint32_t n_bits) {
199 BrotliFillBitWindow(br, n_bits);
200 return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
201}
202
203/* Tries to peek the specified amount of bits. Returns BROTLI_FALSE, if there
204 is not enough input. */
205static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(
206 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
207 while (BrotliGetAvailableBits(br) < n_bits) {
208 if (!BrotliPullByte(br)) {
209 return BROTLI_FALSE;
210 }
211 }
212 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
213 return BROTLI_TRUE;
214}
215
216/* Advances the bit pos by |n_bits|. */
217static BROTLI_INLINE void BrotliDropBits(
218 BrotliBitReader* const br, uint32_t n_bits) {
219 br->bit_pos_ += n_bits;
220}
221
222static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
223 uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
224 uint32_t unused_bits = unused_bytes << 3;
225 br->avail_in += unused_bytes;
226 br->next_in -= unused_bytes;
227 if (unused_bits == sizeof(br->val_) << 3) {
228 br->val_ = 0;
229 } else {
230 br->val_ <<= unused_bits;
231 }
232 br->bit_pos_ += unused_bits;
233}
234
235/* Reads the specified number of bits from |br| and advances the bit pos.
236 Precondition: accumulator MUST contain at least |n_bits|. */
237static BROTLI_INLINE void BrotliTakeBits(
238 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
239 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
240 BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n",
241 (int)br->avail_in, (int)br->bit_pos_, (int)n_bits, (int)*val));
242 BrotliDropBits(br, n_bits);
243}
244
245/* Reads the specified number of bits from |br| and advances the bit pos.
246 Assumes that there is enough input to perform BrotliFillBitWindow. */
247static BROTLI_INLINE uint32_t BrotliReadBits(
248 BrotliBitReader* const br, uint32_t n_bits) {
249 if (BROTLI_64_BITS || (n_bits <= 16)) {
250 uint32_t val;
251 BrotliFillBitWindow(br, n_bits);
252 BrotliTakeBits(br, n_bits, &val);
253 return val;
254 } else {
255 uint32_t low_val;
256 uint32_t high_val;
257 BrotliFillBitWindow(br, 16);
258 BrotliTakeBits(br, 16, &low_val);
259 BrotliFillBitWindow(br, 8);
260 BrotliTakeBits(br, n_bits - 16, &high_val);
261 return low_val | (high_val << 16);
262 }
263}
264
265/* Tries to read the specified amount of bits. Returns BROTLI_FALSE, if there
266 is not enough input. |n_bits| MUST be positive. */
267static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(
268 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
269 while (BrotliGetAvailableBits(br) < n_bits) {
270 if (!BrotliPullByte(br)) {
271 return BROTLI_FALSE;
272 }
273 }
274 BrotliTakeBits(br, n_bits, val);
275 return BROTLI_TRUE;
276}
277
278/* Advances the bit reader position to the next byte boundary and verifies
279 that any skipped bits are set to zero. */
280static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {
281 uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;
282 uint32_t pad_bits = 0;
283 if (pad_bits_count != 0) {
284 BrotliTakeBits(br, pad_bits_count, &pad_bits);
285 }
286 return TO_BROTLI_BOOL(pad_bits == 0);
287}
288
289/* Copies remaining input bytes stored in the bit reader to the output. Value
290 |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be
291 warmed up again after this. */
292static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
293 BrotliBitReader* br, size_t num) {
294 while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
295 *dest = (uint8_t)BrotliGetBitsUnmasked(br);
296 BrotliDropBits(br, 8);
297 ++dest;
298 --num;
299 }
300 memcpy(dest, br->next_in, num);
301 br->avail_in -= num;
302 br->next_in += num;
303}
304
305#if defined(__cplusplus) || defined(c_plusplus)
306} /* extern "C" */
307#endif
308
309#endif /* BROTLI_DEC_BIT_READER_H_ */
310