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) |
20 | extern "C" { |
21 | #endif |
22 | |
23 | #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1) |
24 | |
25 | BROTLI_INTERNAL extern const uint32_t kBrotliBitMask[33]; |
26 | |
27 | static 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 | |
37 | typedef 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 | |
44 | typedef 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. */ |
52 | BROTLI_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. */ |
59 | BROTLI_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. */ |
64 | BROTLI_INTERNAL BROTLI_NOINLINE BROTLI_BOOL BrotliSafeReadBits32Slow( |
65 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val); |
66 | |
67 | static 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 | |
75 | static 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 | |
83 | static 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). */ |
91 | static 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_). */ |
99 | static 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. */ |
108 | static 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. */ |
172 | static 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. */ |
178 | static 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. */ |
196 | static 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. */ |
203 | static 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. */ |
211 | static 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. */ |
219 | static 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|. */ |
231 | static BROTLI_INLINE void BrotliDropBits( |
232 | BrotliBitReader* const br, uint32_t n_bits) { |
233 | br->bit_pos_ += n_bits; |
234 | } |
235 | |
236 | static 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|. */ |
251 | static 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. */ |
262 | static 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. */ |
282 | static 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. */ |
304 | static 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. */ |
317 | static 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. */ |
335 | static 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 | |
344 | static 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. */ |
352 | static 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 | |