c0f6d1bf6efb71a8a7bdaea8134bd4f037e73cf6
[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / bit_reader.h
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 "../common/types.h"
15 #include "./port.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 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 BROTLI_BOOL 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 BROTLI_BOOL BrotliCheckInputAmount(
103 BrotliBitReader* const br, size_t num) {
104 return TO_BROTLI_BOOL(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 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 if (br->bit_pos_ >= 32) {
188 br->val_ >>= 32;
189 br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */
190 br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;
191 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
192 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 BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {
224 if (br->avail_in == 0) {
225 return BROTLI_FALSE;
226 }
227 br->val_ >>= 8;
228 #if (BROTLI_64_BITS)
229 br->val_ |= ((uint64_t)*br->next_in) << 56;
230 #else
231 br->val_ |= ((uint32_t)*br->next_in) << 24;
232 #endif
233 br->bit_pos_ -= 8;
234 --br->avail_in;
235 ++br->next_in;
236 return BROTLI_TRUE;
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 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 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 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 BROTLI_BOOL BrotliSafeGetBits(
263 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
264 while (BrotliGetAvailableBits(br) < n_bits) {
265 if (!BrotliPullByte(br)) {
266 return BROTLI_FALSE;
267 }
268 }
269 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
270 return BROTLI_TRUE;
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 br->bit_pos_ += n_bits;
277 }
278
279 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
280 uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
281 uint32_t unused_bits = unused_bytes << 3;
282 br->avail_in += unused_bytes;
283 br->next_in -= unused_bytes;
284 if (unused_bits == sizeof(br->val_) << 3) {
285 br->val_ = 0;
286 } else {
287 br->val_ <<= unused_bits;
288 }
289 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 *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 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 BROTLI_BOOL BrotliSafeReadBits(
325 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
326 while (BrotliGetAvailableBits(br) < n_bits) {
327 if (!BrotliPullByte(br)) {
328 return BROTLI_FALSE;
329 }
330 }
331 BrotliTakeBits(br, n_bits, val);
332 return BROTLI_TRUE;
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 BROTLI_BOOL 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 TO_BROTLI_BOOL(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 BROTLI_DCHECK((available_bits & 7) == 0);
353 if (offset < bytes_left) {
354 return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;
355 }
356 offset -= bytes_left;
357 if (offset < br->avail_in) {
358 return br->next_in[offset];
359 }
360 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 while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
369 *dest = (uint8_t)BrotliGetBitsUnmasked(br);
370 BrotliDropBits(br, 8);
371 ++dest;
372 --num;
373 }
374 memcpy(dest, br->next_in, num);
375 br->avail_in -= num;
376 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_ */