• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "./port.h"
16 
17 #if defined(__cplusplus) || defined(c_plusplus)
18 extern "C" {
19 #endif
20 
21 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(reg_t) >> 1)
22 
23 static const uint32_t kBitMask[33] = { 0x0000,
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 
BitMask(uint32_t n)34 static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
35   if (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 
44 typedef struct {
45   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 
51 typedef struct {
52   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. */
59 BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);
60 
61 /* Ensures that accumulator is not empty. May consume one byte of input.
62    Returns 0 if data is required but there is no input available.
63    For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned
64    reading. */
65 BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);
66 
BrotliBitReaderSaveState(BrotliBitReader * const from,BrotliBitReaderState * to)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 
BrotliBitReaderRestoreState(BrotliBitReader * const to,BrotliBitReaderState * from)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 
BrotliGetAvailableBits(const BrotliBitReader * br)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_. */
BrotliGetRemainingBytes(BrotliBitReader * br)90 static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
91   return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
92 }
93 
94 /* Checks if there is at least |num| bytes left in the input ring-buffer
95    (excluding the bits remaining in br->val_). */
BrotliCheckInputAmount(BrotliBitReader * const br,size_t num)96 static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(
97     BrotliBitReader* const br, size_t num) {
98   return TO_BROTLI_BOOL(br->avail_in >= num);
99 }
100 
BrotliLoad16LE(const uint8_t * in)101 static BROTLI_INLINE uint16_t BrotliLoad16LE(const uint8_t* in) {
102   if (BROTLI_LITTLE_ENDIAN) {
103     return *((const uint16_t*)in);
104   } else if (BROTLI_BIG_ENDIAN) {
105     uint16_t value = *((const uint16_t*)in);
106     return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8));
107   } else {
108     return (uint16_t)(in[0] | (in[1] << 8));
109   }
110 }
111 
BrotliLoad32LE(const uint8_t * in)112 static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {
113   if (BROTLI_LITTLE_ENDIAN) {
114     return *((const uint32_t*)in);
115   } else if (BROTLI_BIG_ENDIAN) {
116     uint32_t value = *((const uint32_t*)in);
117     return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |
118         ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);
119   } else {
120     uint32_t value = (uint32_t)(*(in++));
121     value |= (uint32_t)(*(in++)) << 8;
122     value |= (uint32_t)(*(in++)) << 16;
123     value |= (uint32_t)(*(in++)) << 24;
124     return value;
125   }
126 }
127 
128 #if (BROTLI_64_BITS)
BrotliLoad64LE(const uint8_t * in)129 static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {
130   if (BROTLI_LITTLE_ENDIAN) {
131     return *((const uint64_t*)in);
132   } else if (BROTLI_BIG_ENDIAN) {
133     uint64_t value = *((const uint64_t*)in);
134     return
135         ((value & 0xFFU) << 56) |
136         ((value & 0xFF00U) << 40) |
137         ((value & 0xFF0000U) << 24) |
138         ((value & 0xFF000000U) << 8) |
139         ((value & 0xFF00000000U) >> 8) |
140         ((value & 0xFF0000000000U) >> 24) |
141         ((value & 0xFF000000000000U) >> 40) |
142         ((value & 0xFF00000000000000U) >> 56);
143   } else {
144     uint64_t value = (uint64_t)(*(in++));
145     value |= (uint64_t)(*(in++)) << 8;
146     value |= (uint64_t)(*(in++)) << 16;
147     value |= (uint64_t)(*(in++)) << 24;
148     value |= (uint64_t)(*(in++)) << 32;
149     value |= (uint64_t)(*(in++)) << 40;
150     value |= (uint64_t)(*(in++)) << 48;
151     value |= (uint64_t)(*(in++)) << 56;
152     return value;
153   }
154 }
155 #endif
156 
157 /* Guarantees that there are at least n_bits + 1 bits in accumulator.
158    Precondition: accumulator contains at least 1 bit.
159    n_bits should be in the range [1..24] for regular build. For portable
160    non-64-bit little-endian build only 16 bits are safe to request. */
BrotliFillBitWindow(BrotliBitReader * const br,uint32_t n_bits)161 static BROTLI_INLINE void BrotliFillBitWindow(
162     BrotliBitReader* const br, uint32_t n_bits) {
163 #if (BROTLI_64_BITS)
164   if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
165     if (br->bit_pos_ >= 56) {
166       br->val_ >>= 56;
167       br->bit_pos_ ^= 56;  /* here same as -= 56 because of the if condition */
168       br->val_ |= BrotliLoad64LE(br->next_in) << 8;
169       br->avail_in -= 7;
170       br->next_in += 7;
171     }
172   } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {
173     if (br->bit_pos_ >= 48) {
174       br->val_ >>= 48;
175       br->bit_pos_ ^= 48;  /* here same as -= 48 because of the if condition */
176       br->val_ |= BrotliLoad64LE(br->next_in) << 16;
177       br->avail_in -= 6;
178       br->next_in += 6;
179     }
180   } else {
181     if (br->bit_pos_ >= 32) {
182       br->val_ >>= 32;
183       br->bit_pos_ ^= 32;  /* here same as -= 32 because of the if condition */
184       br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;
185       br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
186       br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
187     }
188   }
189 #else
190   if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
191     if (br->bit_pos_ >= 24) {
192       br->val_ >>= 24;
193       br->bit_pos_ ^= 24;  /* here same as -= 24 because of the if condition */
194       br->val_ |= BrotliLoad32LE(br->next_in) << 8;
195       br->avail_in -= 3;
196       br->next_in += 3;
197     }
198   } else {
199     if (br->bit_pos_ >= 16) {
200       br->val_ >>= 16;
201       br->bit_pos_ ^= 16;  /* here same as -= 16 because of the if condition */
202       br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;
203       br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
204       br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
205     }
206   }
207 #endif
208 }
209 
210 /* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
211    more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
BrotliFillBitWindow16(BrotliBitReader * const br)212 static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
213   BrotliFillBitWindow(br, 17);
214 }
215 
216 /* Pulls one byte of input to accumulator. */
BrotliPullByte(BrotliBitReader * const br)217 static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {
218   if (br->avail_in == 0) {
219     return BROTLI_FALSE;
220   }
221   br->val_ >>= 8;
222 #if (BROTLI_64_BITS)
223   br->val_ |= ((uint64_t)*br->next_in) << 56;
224 #else
225   br->val_ |= ((uint32_t)*br->next_in) << 24;
226 #endif
227   br->bit_pos_ -= 8;
228   --br->avail_in;
229   ++br->next_in;
230   return BROTLI_TRUE;
231 }
232 
233 /* Returns currently available bits.
234    The number of valid bits could be calculated by BrotliGetAvailableBits. */
BrotliGetBitsUnmasked(BrotliBitReader * const br)235 static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {
236   return br->val_ >> br->bit_pos_;
237 }
238 
239 /* Like BrotliGetBits, but does not mask the result.
240    The result contains at least 16 valid bits. */
BrotliGet16BitsUnmasked(BrotliBitReader * const br)241 static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(
242     BrotliBitReader* const br) {
243   BrotliFillBitWindow(br, 16);
244   return (uint32_t)BrotliGetBitsUnmasked(br);
245 }
246 
247 /* Returns the specified number of bits from |br| without advancing bit pos. */
BrotliGetBits(BrotliBitReader * const br,uint32_t n_bits)248 static BROTLI_INLINE uint32_t BrotliGetBits(
249     BrotliBitReader* const br, uint32_t n_bits) {
250   BrotliFillBitWindow(br, n_bits);
251   return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
252 }
253 
254 /* Tries to peek the specified amount of bits. Returns 0, if there is not
255    enough input. */
BrotliSafeGetBits(BrotliBitReader * const br,uint32_t n_bits,uint32_t * val)256 static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(
257     BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
258   while (BrotliGetAvailableBits(br) < n_bits) {
259     if (!BrotliPullByte(br)) {
260       return BROTLI_FALSE;
261     }
262   }
263   *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
264   return BROTLI_TRUE;
265 }
266 
267 /* Advances the bit pos by n_bits. */
BrotliDropBits(BrotliBitReader * const br,uint32_t n_bits)268 static BROTLI_INLINE void BrotliDropBits(
269     BrotliBitReader* const br, uint32_t n_bits) {
270   br->bit_pos_ += n_bits;
271 }
272 
BrotliBitReaderUnload(BrotliBitReader * br)273 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
274   uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
275   uint32_t unused_bits = unused_bytes << 3;
276   br->avail_in += unused_bytes;
277   br->next_in -= unused_bytes;
278   if (unused_bits == sizeof(br->val_) << 3) {
279     br->val_ = 0;
280   } else {
281     br->val_ <<= unused_bits;
282   }
283   br->bit_pos_ += unused_bits;
284 }
285 
286 /* Reads the specified number of bits from |br| and advances the bit pos.
287    Precondition: accumulator MUST contain at least n_bits. */
BrotliTakeBits(BrotliBitReader * const br,uint32_t n_bits,uint32_t * val)288 static BROTLI_INLINE void BrotliTakeBits(
289   BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
290   *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
291   BROTLI_LOG(("[BrotliReadBits]  %d %d %d val: %6x\n",
292       (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val));
293   BrotliDropBits(br, n_bits);
294 }
295 
296 /* Reads the specified number of bits from |br| and advances the bit pos.
297    Assumes that there is enough input to perform BrotliFillBitWindow. */
BrotliReadBits(BrotliBitReader * const br,uint32_t n_bits)298 static BROTLI_INLINE uint32_t BrotliReadBits(
299     BrotliBitReader* const br, uint32_t n_bits) {
300   if (BROTLI_64_BITS || (n_bits <= 16)) {
301     uint32_t val;
302     BrotliFillBitWindow(br, n_bits);
303     BrotliTakeBits(br, n_bits, &val);
304     return val;
305   } else {
306     uint32_t low_val;
307     uint32_t high_val;
308     BrotliFillBitWindow(br, 16);
309     BrotliTakeBits(br, 16, &low_val);
310     BrotliFillBitWindow(br, 8);
311     BrotliTakeBits(br, n_bits - 16, &high_val);
312     return low_val | (high_val << 16);
313   }
314 }
315 
316 /* Tries to read the specified amount of bits. Returns 0, if there is not
317    enough input. n_bits MUST be positive. */
BrotliSafeReadBits(BrotliBitReader * const br,uint32_t n_bits,uint32_t * val)318 static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(
319     BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
320   while (BrotliGetAvailableBits(br) < n_bits) {
321     if (!BrotliPullByte(br)) {
322       return BROTLI_FALSE;
323     }
324   }
325   BrotliTakeBits(br, n_bits, val);
326   return BROTLI_TRUE;
327 }
328 
329 /* Advances the bit reader position to the next byte boundary and verifies
330    that any skipped bits are set to zero. */
BrotliJumpToByteBoundary(BrotliBitReader * br)331 static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {
332   uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;
333   uint32_t pad_bits = 0;
334   if (pad_bits_count != 0) {
335     BrotliTakeBits(br, pad_bits_count, &pad_bits);
336   }
337   return TO_BROTLI_BOOL(pad_bits == 0);
338 }
339 
340 /* Copies remaining input bytes stored in the bit reader to the output. Value
341    num may not be larger than BrotliGetRemainingBytes. The bit reader must be
342    warmed up again after this. */
BrotliCopyBytes(uint8_t * dest,BrotliBitReader * br,size_t num)343 static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
344                                           BrotliBitReader* br, size_t num) {
345   while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
346     *dest = (uint8_t)BrotliGetBitsUnmasked(br);
347     BrotliDropBits(br, 8);
348     ++dest;
349     --num;
350   }
351   memcpy(dest, br->next_in, num);
352   br->avail_in -= num;
353   br->next_in += num;
354 }
355 
356 #if defined(__cplusplus) || defined(c_plusplus)
357 }  /* extern "C" */
358 #endif
359 
360 #endif  /* BROTLI_DEC_BIT_READER_H_ */
361