Line data Source code
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 "./port.h"
15 : #include "./types.h"
16 :
17 : #if defined(__cplusplus) || defined(c_plusplus)
18 : extern "C" {
19 : #endif
20 :
21 : #if (BROTLI_64_BITS)
22 : #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4
23 : typedef uint64_t reg_t;
24 : #else
25 : #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2
26 : typedef uint32_t reg_t;
27 : #endif
28 :
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
38 : };
39 :
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);
45 : } else {
46 0 : return kBitMask[n];
47 : }
48 : }
49 :
50 : typedef struct {
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 */
54 : size_t avail_in;
55 : } BrotliBitReader;
56 :
57 : typedef struct {
58 : reg_t val_;
59 : uint32_t bit_pos_;
60 : const uint8_t* next_in;
61 : size_t avail_in;
62 : } BrotliBitReaderState;
63 :
64 : /* Initializes the bitreader fields. */
65 : BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);
66 :
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_ALIGNED_READ this function also prepares bit reader for aligned
70 : reading. */
71 : BROTLI_INTERNAL int BrotliWarmupBitReader(BrotliBitReader* const br);
72 :
73 : static BROTLI_INLINE void BrotliBitReaderSaveState(
74 : BrotliBitReader* const from, BrotliBitReaderState* to) {
75 0 : to->val_ = from->val_;
76 0 : to->bit_pos_ = from->bit_pos_;
77 0 : to->next_in = from->next_in;
78 0 : to->avail_in = from->avail_in;
79 : }
80 :
81 : static BROTLI_INLINE void BrotliBitReaderRestoreState(
82 : BrotliBitReader* const to, BrotliBitReaderState* from) {
83 0 : to->val_ = from->val_;
84 0 : to->bit_pos_ = from->bit_pos_;
85 0 : to->next_in = from->next_in;
86 0 : to->avail_in = from->avail_in;
87 : }
88 :
89 : static BROTLI_INLINE uint32_t BrotliGetAvailableBits(
90 : const BrotliBitReader* br) {
91 0 : return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;
92 : }
93 :
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 0 : return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
98 : }
99 :
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 0 : return br->avail_in >= num;
105 : }
106 :
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);
112 : return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8));
113 : } else {
114 : return (uint16_t)(in[0] | (in[1] << 8));
115 : }
116 : }
117 :
118 : static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {
119 : if (BROTLI_LITTLE_ENDIAN) {
120 0 : return *((const uint32_t*)in);
121 : } else if (BROTLI_BIG_ENDIAN) {
122 : uint32_t value = *((const uint32_t*)in);
123 : return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |
124 : ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);
125 : } else {
126 : uint32_t value = (uint32_t)(*(in++));
127 : value |= (uint32_t)(*(in++)) << 8;
128 : value |= (uint32_t)(*(in++)) << 16;
129 : value |= (uint32_t)(*(in++)) << 24;
130 : return value;
131 : }
132 : }
133 :
134 : #if (BROTLI_64_BITS)
135 : static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {
136 : if (BROTLI_LITTLE_ENDIAN) {
137 : return *((const uint64_t*)in);
138 : } else if (BROTLI_BIG_ENDIAN) {
139 : uint64_t value = *((const uint64_t*)in);
140 : return
141 : ((value & 0xFFU) << 56) |
142 : ((value & 0xFF00U) << 40) |
143 : ((value & 0xFF0000U) << 24) |
144 : ((value & 0xFF000000U) << 8) |
145 : ((value & 0xFF00000000U) >> 8) |
146 : ((value & 0xFF0000000000U) >> 24) |
147 : ((value & 0xFF000000000000U) >> 40) |
148 : ((value & 0xFF00000000000000U) >> 56);
149 : } else {
150 : uint64_t value = (uint64_t)(*(in++));
151 : value |= (uint64_t)(*(in++)) << 8;
152 : value |= (uint64_t)(*(in++)) << 16;
153 : value |= (uint64_t)(*(in++)) << 24;
154 : value |= (uint64_t)(*(in++)) << 32;
155 : value |= (uint64_t)(*(in++)) << 40;
156 : value |= (uint64_t)(*(in++)) << 48;
157 : value |= (uint64_t)(*(in++)) << 56;
158 : return value;
159 : }
160 : }
161 : #endif
162 :
163 : /* Guarantees that there are at least n_bits + 1 bits in accumulator.
164 : Precondition: accumulator contains at least 1 bit.
165 : n_bits should be in the range [1..24] for regular build. For portable
166 : non-64-bit little endian build only 16 bits are safe to request. */
167 : static BROTLI_INLINE void BrotliFillBitWindow(
168 : BrotliBitReader* const br, uint32_t n_bits) {
169 : #if (BROTLI_64_BITS)
170 : if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
171 : if (br->bit_pos_ >= 56) {
172 : br->val_ >>= 56;
173 : br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */
174 : br->val_ |= BrotliLoad64LE(br->next_in) << 8;
175 : br->avail_in -= 7;
176 : br->next_in += 7;
177 : }
178 : } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {
179 : if (br->bit_pos_ >= 48) {
180 : br->val_ >>= 48;
181 : br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */
182 : br->val_ |= BrotliLoad64LE(br->next_in) << 16;
183 : br->avail_in -= 6;
184 : br->next_in += 6;
185 : }
186 : } else {
187 0 : if (br->bit_pos_ >= 32) {
188 0 : br->val_ >>= 32;
189 0 : br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */
190 0 : br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;
191 0 : br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
192 0 : br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
193 : }
194 : }
195 : #else
196 : if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
197 : if (br->bit_pos_ >= 24) {
198 : br->val_ >>= 24;
199 : br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */
200 : br->val_ |= BrotliLoad32LE(br->next_in) << 8;
201 : br->avail_in -= 3;
202 : br->next_in += 3;
203 : }
204 : } else {
205 : if (br->bit_pos_ >= 16) {
206 : br->val_ >>= 16;
207 : br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */
208 : br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;
209 : br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
210 : br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
211 : }
212 : }
213 : #endif
214 : }
215 :
216 : /* Mosltly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
217 : more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
218 : static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
219 : BrotliFillBitWindow(br, 17);
220 : }
221 :
222 : /* Pulls one byte of input to accumulator. */
223 : static BROTLI_INLINE int BrotliPullByte(BrotliBitReader* const br) {
224 0 : if (br->avail_in == 0) {
225 0 : return 0;
226 : }
227 0 : br->val_ >>= 8;
228 : #if (BROTLI_64_BITS)
229 0 : br->val_ |= ((uint64_t)*br->next_in) << 56;
230 : #else
231 : br->val_ |= ((uint32_t)*br->next_in) << 24;
232 : #endif
233 0 : br->bit_pos_ -= 8;
234 0 : --br->avail_in;
235 0 : ++br->next_in;
236 0 : return 1;
237 : }
238 :
239 : /* Returns currently available bits.
240 : The number of valid bits could be calclulated by BrotliGetAvailableBits. */
241 : static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {
242 0 : return br->val_ >> br->bit_pos_;
243 : }
244 :
245 : /* Like BrotliGetBits, but does not mask the result.
246 : The result contains at least 16 valid bits. */
247 : static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(
248 : BrotliBitReader* const br) {
249 : BrotliFillBitWindow(br, 16);
250 0 : return (uint32_t)BrotliGetBitsUnmasked(br);
251 : }
252 :
253 : /* Returns the specified number of bits from br without advancing bit pos. */
254 : static BROTLI_INLINE uint32_t BrotliGetBits(
255 : BrotliBitReader* const br, uint32_t n_bits) {
256 : BrotliFillBitWindow(br, n_bits);
257 0 : return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
258 : }
259 :
260 : /* Tries to peek the specified amount of bits. Returns 0, if there is not
261 : enough input. */
262 : static BROTLI_INLINE int BrotliSafeGetBits(
263 : BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
264 0 : while (BrotliGetAvailableBits(br) < n_bits) {
265 0 : if (!BrotliPullByte(br)) {
266 0 : return 0;
267 : }
268 : }
269 0 : *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
270 0 : return 1;
271 : }
272 :
273 : /* Advances the bit pos by n_bits. */
274 : static BROTLI_INLINE void BrotliDropBits(
275 : BrotliBitReader* const br, uint32_t n_bits) {
276 0 : br->bit_pos_ += n_bits;
277 : }
278 :
279 : static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
280 0 : uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
281 0 : uint32_t unused_bits = unused_bytes << 3;
282 0 : br->avail_in += unused_bytes;
283 0 : br->next_in -= unused_bytes;
284 0 : if (unused_bits == sizeof(br->val_) << 3) {
285 0 : br->val_ = 0;
286 : } else {
287 0 : br->val_ <<= unused_bits;
288 : }
289 0 : br->bit_pos_ += unused_bits;
290 : }
291 :
292 : /* Reads the specified number of bits from br and advances the bit pos.
293 : Precondition: accumulator MUST contain at least n_bits. */
294 : static BROTLI_INLINE void BrotliTakeBits(
295 : BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
296 0 : *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
297 : BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n",
298 : (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val));
299 : BrotliDropBits(br, n_bits);
300 : }
301 :
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)) {
307 : uint32_t val;
308 : BrotliFillBitWindow(br, n_bits);
309 : BrotliTakeBits(br, n_bits, &val);
310 0 : return val;
311 : } else {
312 : uint32_t low_val;
313 : uint32_t high_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);
319 : }
320 : }
321 :
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 0 : while (BrotliGetAvailableBits(br) < n_bits) {
327 0 : if (!BrotliPullByte(br)) {
328 0 : return 0;
329 : }
330 : }
331 : BrotliTakeBits(br, n_bits, val);
332 0 : return 1;
333 : }
334 :
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 0 : uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;
339 0 : uint32_t pad_bits = 0;
340 0 : if (pad_bits_count != 0) {
341 : BrotliTakeBits(br, pad_bits_count, &pad_bits);
342 : }
343 0 : return pad_bits == 0;
344 : }
345 :
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 0 : uint32_t available_bits = BrotliGetAvailableBits(br);
351 0 : size_t bytes_left = available_bits >> 3;
352 : BROTLI_DCHECK((available_bits & 7) == 0);
353 0 : if (offset < bytes_left) {
354 0 : return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;
355 : }
356 0 : offset -= bytes_left;
357 0 : if (offset < br->avail_in) {
358 0 : return br->next_in[offset];
359 : }
360 0 : return -1;
361 : }
362 :
363 : /* Copies remaining input bytes stored in the bit reader to the output. Value
364 : num may not be larger than BrotliGetRemainingBytes. The bit reader must be
365 : warmed up again after this. */
366 : static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
367 : BrotliBitReader* br, size_t num) {
368 0 : while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
369 0 : *dest = (uint8_t)BrotliGetBitsUnmasked(br);
370 : BrotliDropBits(br, 8);
371 0 : ++dest;
372 0 : --num;
373 : }
374 0 : memcpy(dest, br->next_in, num);
375 0 : br->avail_in -= num;
376 0 : br->next_in += num;
377 : }
378 :
379 : #if defined(__cplusplus) || defined(c_plusplus)
380 : } /* extern "C" */
381 : #endif
382 :
383 : #endif /* BROTLI_DEC_BIT_READER_H_ */
|
