Commit | Line | Data |
---|---|---|
f9995f31 MG |
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 <stdio.h> | |
13 | #include <string.h> | |
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 | 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 | 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_BUILD_PORTABLE this function also prepares bit reader for aligned | |
70 | reading. */ | |
71 | int BrotliWarmupBitReader(BrotliBitReader* const br); | |
72 | ||
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; | |
79 | } | |
80 | ||
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; | |
87 | } | |
88 | ||
89 | static BROTLI_INLINE uint32_t BrotliGetAvailableBits( | |
90 | const BrotliBitReader* br) { | |
91 | 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 | 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 | 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)( | |
113 | ((value & 0xFFU) << 8) | | |
114 | ((value & 0xFF00U) >> 8)); | |
115 | } else { | |
116 | return (uint16_t)(in[0] | (in[1] << 8)); | |
117 | } | |
118 | } | |
119 | ||
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); | |
127 | } else { | |
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; | |
132 | return value; | |
133 | } | |
134 | } | |
135 | ||
136 | #if (BROTLI_64_BITS) | |
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); | |
142 | return | |
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); | |
151 | } else { | |
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; | |
160 | return value; | |
161 | } | |
162 | } | |
163 | #endif | |
164 | ||
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) { | |
171 | #if (BROTLI_64_BITS) | |
172 | if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) { | |
173 | if (br->bit_pos_ >= 56) { | |
174 | br->val_ >>= 56; | |
175 | br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */ | |
176 | br->val_ |= BrotliLoad64LE(br->next_in) << 8; | |
177 | br->avail_in -= 7; | |
178 | br->next_in += 7; | |
179 | } | |
180 | } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) { | |
181 | if (br->bit_pos_ >= 48) { | |
182 | br->val_ >>= 48; | |
183 | br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */ | |
184 | br->val_ |= BrotliLoad64LE(br->next_in) << 16; | |
185 | br->avail_in -= 6; | |
186 | br->next_in += 6; | |
187 | } | |
188 | } else { | |
189 | if (br->bit_pos_ >= 32) { | |
190 | br->val_ >>= 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; | |
195 | } | |
196 | } | |
197 | #else | |
198 | if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) { | |
199 | if (br->bit_pos_ >= 24) { | |
200 | br->val_ >>= 24; | |
201 | br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */ | |
202 | br->val_ |= BrotliLoad32LE(br->next_in) << 8; | |
203 | br->avail_in -= 3; | |
204 | br->next_in += 3; | |
205 | } | |
206 | } else { | |
207 | if (br->bit_pos_ >= 16) { | |
208 | br->val_ >>= 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; | |
213 | } | |
214 | } | |
215 | #endif | |
216 | } | |
217 | ||
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); | |
222 | } | |
223 | ||
224 | /* Pulls one byte of input to accumulator. */ | |
225 | static BROTLI_INLINE int BrotliPullByte(BrotliBitReader* const br) { | |
226 | if (br->avail_in == 0) { | |
227 | return 0; | |
228 | } | |
229 | br->val_ >>= 8; | |
230 | #if (BROTLI_64_BITS) | |
231 | br->val_ |= ((uint64_t)*br->next_in) << 56; | |
232 | #else | |
233 | br->val_ |= ((uint32_t)*br->next_in) << 24; | |
234 | #endif | |
235 | br->bit_pos_ -= 8; | |
236 | --br->avail_in; | |
237 | ++br->next_in; | |
238 | return 1; | |
239 | } | |
240 | ||
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_; | |
245 | } | |
246 | ||
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); | |
253 | } | |
254 | ||
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); | |
260 | } | |
261 | ||
262 | /* Tries to peek the specified amount of bits. Returns 0, if there is not | |
263 | enough input. */ | |
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)) { | |
268 | return 0; | |
269 | } | |
270 | } | |
271 | *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); | |
272 | return 1; | |
273 | } | |
274 | ||
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; | |
279 | } | |
280 | ||
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; | |
288 | } | |
289 | ||
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); | |
298 | #endif | |
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 | 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 | while (BrotliGetAvailableBits(br) < n_bits) { | |
327 | if (!BrotliPullByte(br)) { | |
328 | return 0; | |
329 | } | |
330 | } | |
331 | BrotliTakeBits(br, n_bits, val); | |
332 | 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 | 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); | |
342 | } | |
343 | 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 | uint32_t available_bits = BrotliGetAvailableBits(br); | |
351 | size_t bytes_left = available_bits >> 3; | |
352 | if (available_bits & 7) { | |
353 | return -1; | |
354 | } | |
355 | if (offset < bytes_left) { | |
356 | return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF; | |
357 | } | |
358 | offset -= bytes_left; | |
359 | if (offset < br->avail_in) { | |
360 | return br->next_in[offset]; | |
361 | } | |
362 | return -1; | |
363 | } | |
364 | ||
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); | |
373 | ++dest; | |
374 | --num; | |
375 | } | |
376 | memcpy(dest, br->next_in, num); | |
377 | br->avail_in -= num; | |
378 | br->next_in += num; | |
379 | } | |
380 | ||
381 | #if defined(__cplusplus) || defined(c_plusplus) | |
382 | } /* extern "C" */ | |
383 | #endif | |
384 | ||
385 | #endif /* BROTLI_DEC_BIT_READER_H_ */ |