MdeModulePkg BrotliLib: Fix the regression logic issue in loop
[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / bit_reader.h
CommitLineData
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
19extern "C" {\r
20#endif\r
21\r
22#if (BROTLI_64_BITS)\r
23#define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4\r
24typedef uint64_t reg_t;\r
25#else\r
26#define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2\r
27typedef uint32_t reg_t;\r
28#endif\r
29\r
30static 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
41static 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
51typedef 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
58typedef 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
66BROTLI_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
72BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);\r
73\r
74static 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
82static 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
90static 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
97static 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
103static 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
108static 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
119static 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
136static 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
168static 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
219static 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
224static 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
242static 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
248static 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
255static 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
263static 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
275static 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
280static 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
295static 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
305static 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
325static 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
338static 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
350static 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
367static 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