]>
Commit | Line | Data |
---|---|---|
36ff6d80 SB |
1 | /* Copyright 2013 Google Inc. All Rights Reserved.\r |
2 | \r | |
3 | Distributed under MIT license.\r | |
4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r | |
5 | */\r | |
6 | \r | |
7 | /* Bit reading helpers */\r | |
8 | \r | |
9 | #ifndef BROTLI_DEC_BIT_READER_H_\r | |
10 | #define BROTLI_DEC_BIT_READER_H_\r | |
11 | \r | |
841b2590 SB |
12 | //#include <string.h> /* memcpy */\r |
13 | #include <BrotliDecompressLibInternal.h>\r | |
36ff6d80 SB |
14 | \r |
15 | #include "../common/types.h"\r | |
16 | #include "./port.h"\r | |
17 | \r | |
18 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
19 | extern "C" {\r | |
20 | #endif\r | |
21 | \r | |
22 | #if (BROTLI_64_BITS)\r | |
23 | #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4\r | |
24 | typedef uint64_t reg_t;\r | |
25 | #else\r | |
26 | #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2\r | |
27 | typedef uint32_t reg_t;\r | |
28 | #endif\r | |
29 | \r | |
30 | static const uint32_t kBitMask[33] = { 0x0000,\r | |
31 | 0x00000001, 0x00000003, 0x00000007, 0x0000000F,\r | |
32 | 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,\r | |
33 | 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,\r | |
34 | 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,\r | |
35 | 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,\r | |
36 | 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,\r | |
37 | 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,\r | |
38 | 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF\r | |
39 | };\r | |
40 | \r | |
41 | static BROTLI_INLINE uint32_t BitMask(uint32_t n) {\r | |
42 | if (IS_CONSTANT(n) || BROTLI_HAS_UBFX) {\r | |
43 | /* Masking with this expression turns to a single\r | |
44 | "Unsigned Bit Field Extract" UBFX instruction on ARM. */\r | |
45 | return ~((0xffffffffU) << n);\r | |
46 | } else {\r | |
47 | return kBitMask[n];\r | |
48 | }\r | |
49 | }\r | |
50 | \r | |
51 | typedef struct {\r | |
52 | reg_t val_; /* pre-fetched bits */\r | |
53 | uint32_t bit_pos_; /* current bit-reading position in val_ */\r | |
54 | const uint8_t* next_in; /* the byte we're reading from */\r | |
55 | size_t avail_in;\r | |
56 | } BrotliBitReader;\r | |
57 | \r | |
58 | typedef struct {\r | |
59 | reg_t val_;\r | |
60 | uint32_t bit_pos_;\r | |
61 | const uint8_t* next_in;\r | |
62 | size_t avail_in;\r | |
63 | } BrotliBitReaderState;\r | |
64 | \r | |
65 | /* Initializes the bitreader fields. */\r | |
66 | BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);\r | |
67 | \r | |
68 | /* Ensures that accumulator is not empty. May consume one byte of input.\r | |
69 | Returns 0 if data is required but there is no input available.\r | |
70 | For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned\r | |
71 | reading. */\r | |
72 | BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);\r | |
73 | \r | |
74 | static BROTLI_INLINE void BrotliBitReaderSaveState(\r | |
75 | BrotliBitReader* const from, BrotliBitReaderState* to) {\r | |
76 | to->val_ = from->val_;\r | |
77 | to->bit_pos_ = from->bit_pos_;\r | |
78 | to->next_in = from->next_in;\r | |
79 | to->avail_in = from->avail_in;\r | |
80 | }\r | |
81 | \r | |
82 | static BROTLI_INLINE void BrotliBitReaderRestoreState(\r | |
83 | BrotliBitReader* const to, BrotliBitReaderState* from) {\r | |
84 | to->val_ = from->val_;\r | |
85 | to->bit_pos_ = from->bit_pos_;\r | |
86 | to->next_in = from->next_in;\r | |
87 | to->avail_in = from->avail_in;\r | |
88 | }\r | |
89 | \r | |
90 | static BROTLI_INLINE uint32_t BrotliGetAvailableBits(\r | |
91 | const BrotliBitReader* br) {\r | |
92 | return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;\r | |
93 | }\r | |
94 | \r | |
95 | /* Returns amount of unread bytes the bit reader still has buffered from the\r | |
96 | BrotliInput, including whole bytes in br->val_. */\r | |
97 | static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {\r | |
98 | return br->avail_in + (BrotliGetAvailableBits(br) >> 3);\r | |
99 | }\r | |
100 | \r | |
101 | /* Checks if there is at least num bytes left in the input ringbuffer (excluding\r | |
102 | the bits remaining in br->val_). */\r | |
103 | static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(\r | |
104 | BrotliBitReader* const br, size_t num) {\r | |
105 | return TO_BROTLI_BOOL(br->avail_in >= num);\r | |
106 | }\r | |
107 | \r | |
108 | static BROTLI_INLINE uint16_t BrotliLoad16LE(const uint8_t* in) {\r | |
109 | if (BROTLI_LITTLE_ENDIAN) {\r | |
110 | return *((const uint16_t*)in);\r | |
111 | } else if (BROTLI_BIG_ENDIAN) {\r | |
112 | uint16_t value = *((const uint16_t*)in);\r | |
113 | return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8));\r | |
114 | } else {\r | |
115 | return (uint16_t)(in[0] | (in[1] << 8));\r | |
116 | }\r | |
117 | }\r | |
118 | \r | |
119 | static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {\r | |
120 | if (BROTLI_LITTLE_ENDIAN) {\r | |
121 | return *((const uint32_t*)in);\r | |
122 | } else if (BROTLI_BIG_ENDIAN) {\r | |
123 | uint32_t value = *((const uint32_t*)in);\r | |
124 | return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |\r | |
125 | ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);\r | |
126 | } else {\r | |
127 | uint32_t value = (uint32_t)(*(in++));\r | |
128 | value |= (uint32_t)(*(in++)) << 8;\r | |
129 | value |= (uint32_t)(*(in++)) << 16;\r | |
130 | value |= (uint32_t)(*(in++)) << 24;\r | |
131 | return value;\r | |
132 | }\r | |
133 | }\r | |
134 | \r | |
135 | #if (BROTLI_64_BITS)\r | |
136 | static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {\r | |
137 | if (BROTLI_LITTLE_ENDIAN) {\r | |
138 | return *((const uint64_t*)in);\r | |
139 | } else if (BROTLI_BIG_ENDIAN) {\r | |
140 | uint64_t value = *((const uint64_t*)in);\r | |
141 | return\r | |
142 | ((value & 0xFFU) << 56) |\r | |
143 | ((value & 0xFF00U) << 40) |\r | |
144 | ((value & 0xFF0000U) << 24) |\r | |
145 | ((value & 0xFF000000U) << 8) |\r | |
146 | ((value & 0xFF00000000U) >> 8) |\r | |
147 | ((value & 0xFF0000000000U) >> 24) |\r | |
148 | ((value & 0xFF000000000000U) >> 40) |\r | |
149 | ((value & 0xFF00000000000000U) >> 56);\r | |
150 | } else {\r | |
151 | uint64_t value = (uint64_t)(*(in++));\r | |
152 | value |= (uint64_t)(*(in++)) << 8;\r | |
153 | value |= (uint64_t)(*(in++)) << 16;\r | |
154 | value |= (uint64_t)(*(in++)) << 24;\r | |
155 | value |= (uint64_t)(*(in++)) << 32;\r | |
156 | value |= (uint64_t)(*(in++)) << 40;\r | |
157 | value |= (uint64_t)(*(in++)) << 48;\r | |
158 | value |= (uint64_t)(*(in++)) << 56;\r | |
159 | return value;\r | |
160 | }\r | |
161 | }\r | |
162 | #endif\r | |
163 | \r | |
164 | /* Guarantees that there are at least n_bits + 1 bits in accumulator.\r | |
165 | Precondition: accumulator contains at least 1 bit.\r | |
166 | n_bits should be in the range [1..24] for regular build. For portable\r | |
167 | non-64-bit little endian build only 16 bits are safe to request. */\r | |
168 | static BROTLI_INLINE void BrotliFillBitWindow(\r | |
169 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
170 | #if (BROTLI_64_BITS)\r | |
171 | if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {\r | |
172 | if (br->bit_pos_ >= 56) {\r | |
173 | br->val_ >>= 56;\r | |
174 | br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */\r | |
175 | br->val_ |= BrotliLoad64LE(br->next_in) << 8;\r | |
176 | br->avail_in -= 7;\r | |
177 | br->next_in += 7;\r | |
178 | }\r | |
179 | } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {\r | |
180 | if (br->bit_pos_ >= 48) {\r | |
181 | br->val_ >>= 48;\r | |
182 | br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */\r | |
183 | br->val_ |= BrotliLoad64LE(br->next_in) << 16;\r | |
184 | br->avail_in -= 6;\r | |
185 | br->next_in += 6;\r | |
186 | }\r | |
187 | } else {\r | |
188 | if (br->bit_pos_ >= 32) {\r | |
189 | br->val_ >>= 32;\r | |
190 | br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */\r | |
191 | br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;\r | |
192 | br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r | |
193 | br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r | |
194 | }\r | |
195 | }\r | |
196 | #else\r | |
197 | if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {\r | |
198 | if (br->bit_pos_ >= 24) {\r | |
199 | br->val_ >>= 24;\r | |
200 | br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */\r | |
201 | br->val_ |= BrotliLoad32LE(br->next_in) << 8;\r | |
202 | br->avail_in -= 3;\r | |
203 | br->next_in += 3;\r | |
204 | }\r | |
205 | } else {\r | |
206 | if (br->bit_pos_ >= 16) {\r | |
207 | br->val_ >>= 16;\r | |
208 | br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */\r | |
209 | br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;\r | |
210 | br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r | |
211 | br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r | |
212 | }\r | |
213 | }\r | |
214 | #endif\r | |
215 | }\r | |
216 | \r | |
217 | /* Mosltly like BrotliFillBitWindow, but guarantees only 16 bits and reads no\r | |
218 | more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */\r | |
219 | static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {\r | |
220 | BrotliFillBitWindow(br, 17);\r | |
221 | }\r | |
222 | \r | |
223 | /* Pulls one byte of input to accumulator. */\r | |
224 | static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {\r | |
225 | if (br->avail_in == 0) {\r | |
226 | return BROTLI_FALSE;\r | |
227 | }\r | |
228 | br->val_ >>= 8;\r | |
229 | #if (BROTLI_64_BITS)\r | |
230 | br->val_ |= ((uint64_t)*br->next_in) << 56;\r | |
231 | #else\r | |
232 | br->val_ |= ((uint32_t)*br->next_in) << 24;\r | |
233 | #endif\r | |
234 | br->bit_pos_ -= 8;\r | |
235 | --br->avail_in;\r | |
236 | ++br->next_in;\r | |
237 | return BROTLI_TRUE;\r | |
238 | }\r | |
239 | \r | |
240 | /* Returns currently available bits.\r | |
241 | The number of valid bits could be calclulated by BrotliGetAvailableBits. */\r | |
242 | static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {\r | |
243 | return br->val_ >> br->bit_pos_;\r | |
244 | }\r | |
245 | \r | |
246 | /* Like BrotliGetBits, but does not mask the result.\r | |
247 | The result contains at least 16 valid bits. */\r | |
248 | static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(\r | |
249 | BrotliBitReader* const br) {\r | |
250 | BrotliFillBitWindow(br, 16);\r | |
251 | return (uint32_t)BrotliGetBitsUnmasked(br);\r | |
252 | }\r | |
253 | \r | |
254 | /* Returns the specified number of bits from br without advancing bit pos. */\r | |
255 | static BROTLI_INLINE uint32_t BrotliGetBits(\r | |
256 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
257 | BrotliFillBitWindow(br, n_bits);\r | |
258 | return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r | |
259 | }\r | |
260 | \r | |
261 | /* Tries to peek the specified amount of bits. Returns 0, if there is not\r | |
262 | enough input. */\r | |
263 | static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(\r | |
264 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r | |
265 | while (BrotliGetAvailableBits(br) < n_bits) {\r | |
266 | if (!BrotliPullByte(br)) {\r | |
267 | return BROTLI_FALSE;\r | |
268 | }\r | |
269 | }\r | |
270 | *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r | |
271 | return BROTLI_TRUE;\r | |
272 | }\r | |
273 | \r | |
274 | /* Advances the bit pos by n_bits. */\r | |
275 | static BROTLI_INLINE void BrotliDropBits(\r | |
276 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
277 | br->bit_pos_ += n_bits;\r | |
278 | }\r | |
279 | \r | |
280 | static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {\r | |
281 | uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;\r | |
282 | uint32_t unused_bits = unused_bytes << 3;\r | |
283 | br->avail_in += unused_bytes;\r | |
284 | br->next_in -= unused_bytes;\r | |
285 | if (unused_bits == sizeof(br->val_) << 3) {\r | |
286 | br->val_ = 0;\r | |
287 | } else {\r | |
288 | br->val_ <<= unused_bits;\r | |
289 | }\r | |
290 | br->bit_pos_ += unused_bits;\r | |
291 | }\r | |
292 | \r | |
293 | /* Reads the specified number of bits from br and advances the bit pos.\r | |
294 | Precondition: accumulator MUST contain at least n_bits. */\r | |
295 | static BROTLI_INLINE void BrotliTakeBits(\r | |
296 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r | |
297 | *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r | |
298 | BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n",\r | |
299 | (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val));\r | |
300 | BrotliDropBits(br, n_bits);\r | |
301 | }\r | |
302 | \r | |
303 | /* Reads the specified number of bits from br and advances the bit pos.\r | |
304 | Assumes that there is enough input to perform BrotliFillBitWindow. */\r | |
305 | static BROTLI_INLINE uint32_t BrotliReadBits(\r | |
306 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
307 | if (BROTLI_64_BITS || (n_bits <= 16)) {\r | |
308 | uint32_t val;\r | |
309 | BrotliFillBitWindow(br, n_bits);\r | |
310 | BrotliTakeBits(br, n_bits, &val);\r | |
311 | return val;\r | |
312 | } else {\r | |
313 | uint32_t low_val;\r | |
314 | uint32_t high_val;\r | |
315 | BrotliFillBitWindow(br, 16);\r | |
316 | BrotliTakeBits(br, 16, &low_val);\r | |
317 | BrotliFillBitWindow(br, 8);\r | |
318 | BrotliTakeBits(br, n_bits - 16, &high_val);\r | |
319 | return low_val | (high_val << 16);\r | |
320 | }\r | |
321 | }\r | |
322 | \r | |
323 | /* Tries to read the specified amount of bits. Returns 0, if there is not\r | |
324 | enough input. n_bits MUST be positive. */\r | |
325 | static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(\r | |
326 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r | |
327 | while (BrotliGetAvailableBits(br) < n_bits) {\r | |
328 | if (!BrotliPullByte(br)) {\r | |
329 | return BROTLI_FALSE;\r | |
330 | }\r | |
331 | }\r | |
332 | BrotliTakeBits(br, n_bits, val);\r | |
333 | return BROTLI_TRUE;\r | |
334 | }\r | |
335 | \r | |
336 | /* Advances the bit reader position to the next byte boundary and verifies\r | |
337 | that any skipped bits are set to zero. */\r | |
338 | static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {\r | |
339 | uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;\r | |
340 | uint32_t pad_bits = 0;\r | |
341 | if (pad_bits_count != 0) {\r | |
342 | BrotliTakeBits(br, pad_bits_count, &pad_bits);\r | |
343 | }\r | |
344 | return TO_BROTLI_BOOL(pad_bits == 0);\r | |
345 | }\r | |
346 | \r | |
347 | /* Peeks a byte at specified offset.\r | |
348 | Precondition: bit reader is parked to a byte boundary.\r | |
349 | Returns -1 if operation is not feasible. */\r | |
350 | static BROTLI_INLINE int BrotliPeekByte(BrotliBitReader* br, size_t offset) {\r | |
351 | uint32_t available_bits = BrotliGetAvailableBits(br);\r | |
352 | size_t bytes_left = available_bits >> 3;\r | |
353 | BROTLI_DCHECK((available_bits & 7) == 0);\r | |
354 | if (offset < bytes_left) {\r | |
355 | return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;\r | |
356 | }\r | |
357 | offset -= bytes_left;\r | |
358 | if (offset < br->avail_in) {\r | |
359 | return br->next_in[offset];\r | |
360 | }\r | |
361 | return -1;\r | |
362 | }\r | |
363 | \r | |
364 | /* Copies remaining input bytes stored in the bit reader to the output. Value\r | |
365 | num may not be larger than BrotliGetRemainingBytes. The bit reader must be\r | |
366 | warmed up again after this. */\r | |
367 | static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,\r | |
368 | BrotliBitReader* br, size_t num) {\r | |
369 | while (BrotliGetAvailableBits(br) >= 8 && num > 0) {\r | |
370 | *dest = (uint8_t)BrotliGetBitsUnmasked(br);\r | |
371 | BrotliDropBits(br, 8);\r | |
372 | ++dest;\r | |
373 | --num;\r | |
374 | }\r | |
375 | memcpy(dest, br->next_in, num);\r | |
376 | br->avail_in -= num;\r | |
377 | br->next_in += num;\r | |
378 | }\r | |
379 | \r | |
380 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
381 | } /* extern "C" */\r | |
382 | #endif\r | |
383 | \r | |
384 | #endif /* BROTLI_DEC_BIT_READER_H_ */\r |