]>
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 | 12 | //#include <string.h> /* memcpy */\r |
36ff6d80 | 13 | \r |
2730470f LG |
14 | #include "../common/platform.h"\r |
15 | #include <brotli/types.h>\r | |
36ff6d80 SB |
16 | \r |
17 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
18 | extern "C" {\r | |
19 | #endif\r | |
20 | \r | |
2730470f | 21 | #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1)\r |
36ff6d80 | 22 | \r |
2730470f | 23 | static const uint32_t kBitMask[33] = { 0x00000000,\r |
36ff6d80 SB |
24 | 0x00000001, 0x00000003, 0x00000007, 0x0000000F,\r |
25 | 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,\r | |
26 | 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,\r | |
27 | 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,\r | |
28 | 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,\r | |
29 | 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,\r | |
30 | 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,\r | |
31 | 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF\r | |
32 | };\r | |
33 | \r | |
34 | static BROTLI_INLINE uint32_t BitMask(uint32_t n) {\r | |
2730470f | 35 | if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) {\r |
36ff6d80 SB |
36 | /* Masking with this expression turns to a single\r |
37 | "Unsigned Bit Field Extract" UBFX instruction on ARM. */\r | |
2730470f | 38 | return ~((0xFFFFFFFFu) << n);\r |
36ff6d80 SB |
39 | } else {\r |
40 | return kBitMask[n];\r | |
41 | }\r | |
42 | }\r | |
43 | \r | |
44 | typedef struct {\r | |
2730470f | 45 | brotli_reg_t val_; /* pre-fetched bits */\r |
36ff6d80 SB |
46 | uint32_t bit_pos_; /* current bit-reading position in val_ */\r |
47 | const uint8_t* next_in; /* the byte we're reading from */\r | |
48 | size_t avail_in;\r | |
49 | } BrotliBitReader;\r | |
50 | \r | |
51 | typedef struct {\r | |
2730470f | 52 | brotli_reg_t val_;\r |
36ff6d80 SB |
53 | uint32_t bit_pos_;\r |
54 | const uint8_t* next_in;\r | |
55 | size_t avail_in;\r | |
56 | } BrotliBitReaderState;\r | |
57 | \r | |
2730470f | 58 | /* Initializes the BrotliBitReader fields. */\r |
36ff6d80 SB |
59 | BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);\r |
60 | \r | |
2730470f LG |
61 | /* Ensures that accumulator is not empty.\r |
62 | May consume up to sizeof(brotli_reg_t) - 1 bytes of input.\r | |
63 | Returns BROTLI_FALSE if data is required but there is no input available.\r | |
36ff6d80 SB |
64 | For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned\r |
65 | reading. */\r | |
66 | BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);\r | |
67 | \r | |
68 | static BROTLI_INLINE void BrotliBitReaderSaveState(\r | |
69 | BrotliBitReader* const from, BrotliBitReaderState* to) {\r | |
70 | to->val_ = from->val_;\r | |
71 | to->bit_pos_ = from->bit_pos_;\r | |
72 | to->next_in = from->next_in;\r | |
73 | to->avail_in = from->avail_in;\r | |
74 | }\r | |
75 | \r | |
76 | static BROTLI_INLINE void BrotliBitReaderRestoreState(\r | |
77 | BrotliBitReader* const to, BrotliBitReaderState* from) {\r | |
78 | to->val_ = from->val_;\r | |
79 | to->bit_pos_ = from->bit_pos_;\r | |
80 | to->next_in = from->next_in;\r | |
81 | to->avail_in = from->avail_in;\r | |
82 | }\r | |
83 | \r | |
84 | static BROTLI_INLINE uint32_t BrotliGetAvailableBits(\r | |
85 | const BrotliBitReader* br) {\r | |
86 | return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;\r | |
87 | }\r | |
88 | \r | |
89 | /* Returns amount of unread bytes the bit reader still has buffered from the\r | |
90 | BrotliInput, including whole bytes in br->val_. */\r | |
91 | static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {\r | |
92 | return br->avail_in + (BrotliGetAvailableBits(br) >> 3);\r | |
93 | }\r | |
94 | \r | |
2730470f LG |
95 | /* Checks if there is at least |num| bytes left in the input ring-buffer\r |
96 | (excluding the bits remaining in br->val_). */\r | |
36ff6d80 SB |
97 | static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(\r |
98 | BrotliBitReader* const br, size_t num) {\r | |
99 | return TO_BROTLI_BOOL(br->avail_in >= num);\r | |
100 | }\r | |
101 | \r | |
2730470f | 102 | /* Guarantees that there are at least |n_bits| + 1 bits in accumulator.\r |
36ff6d80 | 103 | Precondition: accumulator contains at least 1 bit.\r |
2730470f LG |
104 | |n_bits| should be in the range [1..24] for regular build. For portable\r |
105 | non-64-bit little-endian build only 16 bits are safe to request. */\r | |
36ff6d80 SB |
106 | static BROTLI_INLINE void BrotliFillBitWindow(\r |
107 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
108 | #if (BROTLI_64_BITS)\r | |
2730470f | 109 | if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) {\r |
36ff6d80 SB |
110 | if (br->bit_pos_ >= 56) {\r |
111 | br->val_ >>= 56;\r | |
112 | br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */\r | |
2730470f | 113 | br->val_ |= BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 8;\r |
36ff6d80 SB |
114 | br->avail_in -= 7;\r |
115 | br->next_in += 7;\r | |
116 | }\r | |
2730470f LG |
117 | } else if (\r |
118 | !BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 16)) {\r | |
36ff6d80 SB |
119 | if (br->bit_pos_ >= 48) {\r |
120 | br->val_ >>= 48;\r | |
121 | br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */\r | |
2730470f | 122 | br->val_ |= BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 16;\r |
36ff6d80 SB |
123 | br->avail_in -= 6;\r |
124 | br->next_in += 6;\r | |
125 | }\r | |
126 | } else {\r | |
127 | if (br->bit_pos_ >= 32) {\r | |
128 | br->val_ >>= 32;\r | |
129 | br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */\r | |
2730470f | 130 | br->val_ |= ((uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in)) << 32;\r |
36ff6d80 SB |
131 | br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r |
132 | br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r | |
133 | }\r | |
134 | }\r | |
135 | #else\r | |
2730470f | 136 | if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) {\r |
36ff6d80 SB |
137 | if (br->bit_pos_ >= 24) {\r |
138 | br->val_ >>= 24;\r | |
139 | br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */\r | |
2730470f | 140 | br->val_ |= BROTLI_UNALIGNED_LOAD32LE(br->next_in) << 8;\r |
36ff6d80 SB |
141 | br->avail_in -= 3;\r |
142 | br->next_in += 3;\r | |
143 | }\r | |
144 | } else {\r | |
145 | if (br->bit_pos_ >= 16) {\r | |
146 | br->val_ >>= 16;\r | |
147 | br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */\r | |
2730470f | 148 | br->val_ |= ((uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in)) << 16;\r |
36ff6d80 SB |
149 | br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r |
150 | br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r | |
151 | }\r | |
152 | }\r | |
153 | #endif\r | |
154 | }\r | |
155 | \r | |
2730470f | 156 | /* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no\r |
36ff6d80 SB |
157 | more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */\r |
158 | static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {\r | |
159 | BrotliFillBitWindow(br, 17);\r | |
160 | }\r | |
161 | \r | |
2730470f LG |
162 | /* Tries to pull one byte of input to accumulator.\r |
163 | Returns BROTLI_FALSE if there is no input available. */\r | |
36ff6d80 SB |
164 | static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {\r |
165 | if (br->avail_in == 0) {\r | |
166 | return BROTLI_FALSE;\r | |
167 | }\r | |
168 | br->val_ >>= 8;\r | |
169 | #if (BROTLI_64_BITS)\r | |
170 | br->val_ |= ((uint64_t)*br->next_in) << 56;\r | |
171 | #else\r | |
172 | br->val_ |= ((uint32_t)*br->next_in) << 24;\r | |
173 | #endif\r | |
174 | br->bit_pos_ -= 8;\r | |
175 | --br->avail_in;\r | |
176 | ++br->next_in;\r | |
177 | return BROTLI_TRUE;\r | |
178 | }\r | |
179 | \r | |
180 | /* Returns currently available bits.\r | |
2730470f LG |
181 | The number of valid bits could be calculated by BrotliGetAvailableBits. */\r |
182 | static BROTLI_INLINE brotli_reg_t BrotliGetBitsUnmasked(\r | |
183 | BrotliBitReader* const br) {\r | |
36ff6d80 SB |
184 | return br->val_ >> br->bit_pos_;\r |
185 | }\r | |
186 | \r | |
187 | /* Like BrotliGetBits, but does not mask the result.\r | |
188 | The result contains at least 16 valid bits. */\r | |
189 | static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(\r | |
190 | BrotliBitReader* const br) {\r | |
191 | BrotliFillBitWindow(br, 16);\r | |
192 | return (uint32_t)BrotliGetBitsUnmasked(br);\r | |
193 | }\r | |
194 | \r | |
2730470f LG |
195 | /* Returns the specified number of bits from |br| without advancing bit\r |
196 | position. */\r | |
36ff6d80 SB |
197 | static BROTLI_INLINE uint32_t BrotliGetBits(\r |
198 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
199 | BrotliFillBitWindow(br, n_bits);\r | |
200 | return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r | |
201 | }\r | |
202 | \r | |
2730470f LG |
203 | /* Tries to peek the specified amount of bits. Returns BROTLI_FALSE, if there\r |
204 | is not enough input. */\r | |
36ff6d80 SB |
205 | static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(\r |
206 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r | |
207 | while (BrotliGetAvailableBits(br) < n_bits) {\r | |
208 | if (!BrotliPullByte(br)) {\r | |
209 | return BROTLI_FALSE;\r | |
210 | }\r | |
211 | }\r | |
212 | *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r | |
213 | return BROTLI_TRUE;\r | |
214 | }\r | |
215 | \r | |
2730470f | 216 | /* Advances the bit pos by |n_bits|. */\r |
36ff6d80 SB |
217 | static BROTLI_INLINE void BrotliDropBits(\r |
218 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
219 | br->bit_pos_ += n_bits;\r | |
220 | }\r | |
221 | \r | |
222 | static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {\r | |
223 | uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;\r | |
224 | uint32_t unused_bits = unused_bytes << 3;\r | |
225 | br->avail_in += unused_bytes;\r | |
226 | br->next_in -= unused_bytes;\r | |
227 | if (unused_bits == sizeof(br->val_) << 3) {\r | |
228 | br->val_ = 0;\r | |
229 | } else {\r | |
230 | br->val_ <<= unused_bits;\r | |
231 | }\r | |
232 | br->bit_pos_ += unused_bits;\r | |
233 | }\r | |
234 | \r | |
2730470f LG |
235 | /* Reads the specified number of bits from |br| and advances the bit pos.\r |
236 | Precondition: accumulator MUST contain at least |n_bits|. */\r | |
36ff6d80 SB |
237 | static BROTLI_INLINE void BrotliTakeBits(\r |
238 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r | |
239 | *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r | |
240 | BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n",\r | |
2730470f | 241 | (int)br->avail_in, (int)br->bit_pos_, (int)n_bits, (int)*val));\r |
36ff6d80 SB |
242 | BrotliDropBits(br, n_bits);\r |
243 | }\r | |
244 | \r | |
2730470f | 245 | /* Reads the specified number of bits from |br| and advances the bit pos.\r |
36ff6d80 SB |
246 | Assumes that there is enough input to perform BrotliFillBitWindow. */\r |
247 | static BROTLI_INLINE uint32_t BrotliReadBits(\r | |
248 | BrotliBitReader* const br, uint32_t n_bits) {\r | |
249 | if (BROTLI_64_BITS || (n_bits <= 16)) {\r | |
250 | uint32_t val;\r | |
251 | BrotliFillBitWindow(br, n_bits);\r | |
252 | BrotliTakeBits(br, n_bits, &val);\r | |
253 | return val;\r | |
254 | } else {\r | |
255 | uint32_t low_val;\r | |
256 | uint32_t high_val;\r | |
257 | BrotliFillBitWindow(br, 16);\r | |
258 | BrotliTakeBits(br, 16, &low_val);\r | |
259 | BrotliFillBitWindow(br, 8);\r | |
260 | BrotliTakeBits(br, n_bits - 16, &high_val);\r | |
261 | return low_val | (high_val << 16);\r | |
262 | }\r | |
263 | }\r | |
264 | \r | |
2730470f LG |
265 | /* Tries to read the specified amount of bits. Returns BROTLI_FALSE, if there\r |
266 | is not enough input. |n_bits| MUST be positive. */\r | |
36ff6d80 SB |
267 | static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(\r |
268 | BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r | |
269 | while (BrotliGetAvailableBits(br) < n_bits) {\r | |
270 | if (!BrotliPullByte(br)) {\r | |
271 | return BROTLI_FALSE;\r | |
272 | }\r | |
273 | }\r | |
274 | BrotliTakeBits(br, n_bits, val);\r | |
275 | return BROTLI_TRUE;\r | |
276 | }\r | |
277 | \r | |
278 | /* Advances the bit reader position to the next byte boundary and verifies\r | |
279 | that any skipped bits are set to zero. */\r | |
280 | static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {\r | |
281 | uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;\r | |
282 | uint32_t pad_bits = 0;\r | |
283 | if (pad_bits_count != 0) {\r | |
284 | BrotliTakeBits(br, pad_bits_count, &pad_bits);\r | |
285 | }\r | |
286 | return TO_BROTLI_BOOL(pad_bits == 0);\r | |
287 | }\r | |
288 | \r | |
36ff6d80 | 289 | /* Copies remaining input bytes stored in the bit reader to the output. Value\r |
2730470f | 290 | |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be\r |
36ff6d80 SB |
291 | warmed up again after this. */\r |
292 | static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,\r | |
293 | BrotliBitReader* br, size_t num) {\r | |
294 | while (BrotliGetAvailableBits(br) >= 8 && num > 0) {\r | |
295 | *dest = (uint8_t)BrotliGetBitsUnmasked(br);\r | |
296 | BrotliDropBits(br, 8);\r | |
297 | ++dest;\r | |
298 | --num;\r | |
299 | }\r | |
300 | memcpy(dest, br->next_in, num);\r | |
301 | br->avail_in -= num;\r | |
302 | br->next_in += num;\r | |
303 | }\r | |
304 | \r | |
305 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
306 | } /* extern "C" */\r | |
307 | #endif\r | |
308 | \r | |
309 | #endif /* BROTLI_DEC_BIT_READER_H_ */\r |