Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/brotli/c/dec/bit_reader.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 <brotli/types.h>
15
16 #include "../common/constants.h"
17 #include "../common/platform.h"
18
19 #if defined(__cplusplus) || defined(c_plusplus)
20 extern "C" {
21 #endif
22
23 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1)
24
25 /* 162 bits + 7 bytes */
26 #define BROTLI_FAST_INPUT_SLACK 28
27
28 BROTLI_INTERNAL extern const brotli_reg_t kBrotliBitMask[33];
29
30 static BROTLI_INLINE brotli_reg_t BitMask(brotli_reg_t n) {
31 if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
32 /* Masking with this expression turns to a single
33 "Unsigned Bit Field Extract" UBFX instruction on ARM. */
34 return ~(~((brotli_reg_t)0) << n);
35 } else {
36 return kBrotliBitMask[n];
37 }
38 }
39
40 typedef struct {
41 brotli_reg_t val_; /* pre-fetched bits */
42 brotli_reg_t bit_pos_; /* current bit-reading position in val_ */
43 const uint8_t* next_in; /* the byte we're reading from */
44 const uint8_t* guard_in; /* position from which "fast-path" is prohibited */
45 const uint8_t* last_in; /* == next_in + avail_in */
46 } BrotliBitReader;
47
48 typedef struct {
49 brotli_reg_t val_;
50 brotli_reg_t bit_pos_;
51 const uint8_t* next_in;
52 size_t avail_in;
53 } BrotliBitReaderState;
54
55 /* Initializes the BrotliBitReader fields. */
56 BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* br);
57
58 /* Ensures that accumulator is not empty.
59 May consume up to sizeof(brotli_reg_t) - 1 bytes of input.
60 Returns BROTLI_FALSE if data is required but there is no input available.
61 For !BROTLI_UNALIGNED_READ_FAST this function also prepares bit reader for
62 aligned reading. */
63 BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* br);
64
65 /* Fallback for BrotliSafeReadBits32. Extracted as noninlined method to unburden
66 the main code-path. Never called for RFC brotli streams, required only for
67 "large-window" mode and other extensions. */
68 BROTLI_INTERNAL BROTLI_NOINLINE BROTLI_BOOL BrotliSafeReadBits32Slow(
69 BrotliBitReader* br, brotli_reg_t n_bits, brotli_reg_t* val);
70
71 static BROTLI_INLINE size_t
72 BrotliBitReaderGetAvailIn(BrotliBitReader* const br) {
73 return (size_t)(br->last_in - br->next_in);
74 }
75
76 static BROTLI_INLINE void BrotliBitReaderSaveState(
77 BrotliBitReader* const from, BrotliBitReaderState* to) {
78 to->val_ = from->val_;
79 to->bit_pos_ = from->bit_pos_;
80 to->next_in = from->next_in;
81 to->avail_in = BrotliBitReaderGetAvailIn(from);
82 }
83
84 static BROTLI_INLINE void BrotliBitReaderSetInput(
85 BrotliBitReader* const br, const uint8_t* next_in, size_t avail_in) {
86 br->next_in = next_in;
87 br->last_in = (avail_in == 0) ? next_in : (next_in + avail_in);
88 if (avail_in + 1 > BROTLI_FAST_INPUT_SLACK) {
89 br->guard_in = next_in + (avail_in + 1 - BROTLI_FAST_INPUT_SLACK);
90 } else {
91 br->guard_in = next_in;
92 }
93 }
94
95 static BROTLI_INLINE void BrotliBitReaderRestoreState(
96 BrotliBitReader* const to, BrotliBitReaderState* from) {
97 to->val_ = from->val_;
98 to->bit_pos_ = from->bit_pos_;
99 to->next_in = from->next_in;
100 BrotliBitReaderSetInput(to, from->next_in, from->avail_in);
101 }
102
103 static BROTLI_INLINE brotli_reg_t BrotliGetAvailableBits(
104 const BrotliBitReader* br) {
105 return br->bit_pos_;
106 }
107
108 /* Returns amount of unread bytes the bit reader still has buffered from the
109 BrotliInput, including whole bytes in br->val_. Result is capped with
110 maximal ring-buffer size (larger number won't be utilized anyway). */
111 static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
112 static const size_t kCap = (size_t)1 << BROTLI_LARGE_MAX_WBITS;
113 size_t avail_in = BrotliBitReaderGetAvailIn(br);
114 if (avail_in > kCap) return kCap;
115 return avail_in + (BrotliGetAvailableBits(br) >> 3);
116 }
117
118 /* Checks if there is at least |num| bytes left in the input ring-buffer
119 (excluding the bits remaining in br->val_). */
120 static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(
121 BrotliBitReader* const br) {
122 return TO_BROTLI_BOOL(br->next_in < br->guard_in);
123 }
124
125 /* Load more bits into accumulator. */
126 static BROTLI_INLINE brotli_reg_t BrotliBitReaderLoadBits(brotli_reg_t val,
127 brotli_reg_t new_bits,
128 brotli_reg_t count,
129 brotli_reg_t offset) {
130 BROTLI_DCHECK(
131 !((val >> offset) & ~new_bits & ~(~((brotli_reg_t)0) << count)));
132 (void)count;
133 return val | (new_bits << offset);
134 }
135
136 /* Guarantees that there are at least |n_bits| + 1 bits in accumulator.
137 Precondition: accumulator contains at least 1 bit.
138 |n_bits| should be in the range [1..24] for regular build. For portable
139 non-64-bit little-endian build only 16 bits are safe to request. */
140 static BROTLI_INLINE void BrotliFillBitWindow(
141 BrotliBitReader* const br, brotli_reg_t n_bits) {
142 #if (BROTLI_64_BITS)
143 if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) &&
144 (n_bits <= 8)) {
145 brotli_reg_t bit_pos = br->bit_pos_;
146 if (bit_pos <= 8) {
147 br->val_ = BrotliBitReaderLoadBits(br->val_,
148 BROTLI_UNALIGNED_LOAD64LE(br->next_in), 56, bit_pos);
149 br->bit_pos_ = bit_pos + 56;
150 br->next_in += 7;
151 }
152 } else if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) &&
153 (n_bits <= 16)) {
154 brotli_reg_t bit_pos = br->bit_pos_;
155 if (bit_pos <= 16) {
156 br->val_ = BrotliBitReaderLoadBits(br->val_,
157 BROTLI_UNALIGNED_LOAD64LE(br->next_in), 48, bit_pos);
158 br->bit_pos_ = bit_pos + 48;
159 br->next_in += 6;
160 }
161 } else {
162 brotli_reg_t bit_pos = br->bit_pos_;
163 if (bit_pos <= 32) {
164 br->val_ = BrotliBitReaderLoadBits(br->val_,
165 (uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in), 32, bit_pos);
166 br->bit_pos_ = bit_pos + 32;
167 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
168 }
169 }
170 #else
171 if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) &&
172 (n_bits <= 8)) {
173 brotli_reg_t bit_pos = br->bit_pos_;
174 if (bit_pos <= 8) {
175 br->val_ = BrotliBitReaderLoadBits(br->val_,
176 BROTLI_UNALIGNED_LOAD32LE(br->next_in), 24, bit_pos);
177 br->bit_pos_ = bit_pos + 24;
178 br->next_in += 3;
179 }
180 } else {
181 brotli_reg_t bit_pos = br->bit_pos_;
182 if (bit_pos <= 16) {
183 br->val_ = BrotliBitReaderLoadBits(br->val_,
184 (uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in), 16, bit_pos);
185 br->bit_pos_ = bit_pos + 16;
186 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
187 }
188 }
189 #endif
190 }
191
192 /* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
193 more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
194 static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
195 BrotliFillBitWindow(br, 17);
196 }
197
198 /* Tries to pull one byte of input to accumulator.
199 Returns BROTLI_FALSE if there is no input available. */
200 static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {
201 if (br->next_in == br->last_in) {
202 return BROTLI_FALSE;
203 }
204 br->val_ = BrotliBitReaderLoadBits(br->val_,
205 (brotli_reg_t)*br->next_in, 8, br->bit_pos_);
206 br->bit_pos_ += 8;
207 ++br->next_in;
208 return BROTLI_TRUE;
209 }
210
211 /* Returns currently available bits.
212 The number of valid bits could be calculated by BrotliGetAvailableBits. */
213 static BROTLI_INLINE brotli_reg_t BrotliGetBitsUnmasked(
214 BrotliBitReader* const br) {
215 return br->val_;
216 }
217
218 /* Like BrotliGetBits, but does not mask the result.
219 The result contains at least 16 valid bits. */
220 static BROTLI_INLINE brotli_reg_t BrotliGet16BitsUnmasked(
221 BrotliBitReader* const br) {
222 BrotliFillBitWindow(br, 16);
223 return (brotli_reg_t)BrotliGetBitsUnmasked(br);
224 }
225
226 /* Returns the specified number of bits from |br| without advancing bit
227 position. */
228 static BROTLI_INLINE brotli_reg_t BrotliGetBits(
229 BrotliBitReader* const br, brotli_reg_t n_bits) {
230 BrotliFillBitWindow(br, n_bits);
231 return BrotliGetBitsUnmasked(br) & BitMask(n_bits);
232 }
233
234 /* Tries to peek the specified amount of bits. Returns BROTLI_FALSE, if there
235 is not enough input. */
236 static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(
237 BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) {
238 while (BrotliGetAvailableBits(br) < n_bits) {
239 if (!BrotliPullByte(br)) {
240 return BROTLI_FALSE;
241 }
242 }
243 *val = BrotliGetBitsUnmasked(br) & BitMask(n_bits);
244 return BROTLI_TRUE;
245 }
246
247 /* Advances the bit pos by |n_bits|. */
248 static BROTLI_INLINE void BrotliDropBits(
249 BrotliBitReader* const br, brotli_reg_t n_bits) {
250 br->bit_pos_ -= n_bits;
251 br->val_ >>= n_bits;
252 }
253
254 /* Make sure that there are no spectre bits in accumulator.
255 This is important for the cases when some bytes are skipped
256 (i.e. never placed into accumulator). */
257 static BROTLI_INLINE void BrotliBitReaderNormalize(BrotliBitReader* br) {
258 /* Actually, it is enough to normalize when br->bit_pos_ == 0 */
259 if (br->bit_pos_ < (sizeof(brotli_reg_t) << 3u)) {
260 br->val_ &= (((brotli_reg_t)1) << br->bit_pos_) - 1;
261 }
262 }
263
264 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
265 brotli_reg_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
266 brotli_reg_t unused_bits = unused_bytes << 3;
267 br->next_in =
268 (unused_bytes == 0) ? br->next_in : (br->next_in - unused_bytes);
269 br->bit_pos_ -= unused_bits;
270 BrotliBitReaderNormalize(br);
271 }
272
273 /* Reads the specified number of bits from |br| and advances the bit pos.
274 Precondition: accumulator MUST contain at least |n_bits|. */
275 static BROTLI_INLINE void BrotliTakeBits(BrotliBitReader* const br,
276 brotli_reg_t n_bits,
277 brotli_reg_t* val) {
278 *val = BrotliGetBitsUnmasked(br) & BitMask(n_bits);
279 BROTLI_LOG(("[BrotliTakeBits] %d %d %d val: %6x\n",
280 (int)BrotliBitReaderGetAvailIn(br), (int)br->bit_pos_,
281 (int)n_bits, (int)*val));
282 BrotliDropBits(br, n_bits);
283 }
284
285 /* Reads the specified number of bits from |br| and advances the bit pos.
286 Assumes that there is enough input to perform BrotliFillBitWindow.
287 Up to 24 bits are allowed to be requested from this method. */
288 static BROTLI_INLINE brotli_reg_t BrotliReadBits24(
289 BrotliBitReader* const br, brotli_reg_t n_bits) {
290 BROTLI_DCHECK(n_bits <= 24);
291 if (BROTLI_64_BITS || (n_bits <= 16)) {
292 brotli_reg_t val;
293 BrotliFillBitWindow(br, n_bits);
294 BrotliTakeBits(br, n_bits, &val);
295 return val;
296 } else {
297 brotli_reg_t low_val;
298 brotli_reg_t high_val;
299 BrotliFillBitWindow(br, 16);
300 BrotliTakeBits(br, 16, &low_val);
301 BrotliFillBitWindow(br, 8);
302 BrotliTakeBits(br, n_bits - 16, &high_val);
303 return low_val | (high_val << 16);
304 }
305 }
306
307 /* Same as BrotliReadBits24, but allows reading up to 32 bits. */
308 static BROTLI_INLINE brotli_reg_t BrotliReadBits32(
309 BrotliBitReader* const br, brotli_reg_t n_bits) {
310 BROTLI_DCHECK(n_bits <= 32);
311 if (BROTLI_64_BITS || (n_bits <= 16)) {
312 brotli_reg_t val;
313 BrotliFillBitWindow(br, n_bits);
314 BrotliTakeBits(br, n_bits, &val);
315 return val;
316 } else {
317 brotli_reg_t low_val;
318 brotli_reg_t high_val;
319 BrotliFillBitWindow(br, 16);
320 BrotliTakeBits(br, 16, &low_val);
321 BrotliFillBitWindow(br, 16);
322 BrotliTakeBits(br, n_bits - 16, &high_val);
323 return low_val | (high_val << 16);
324 }
325 }
326
327 /* Tries to read the specified amount of bits. Returns BROTLI_FALSE, if there
328 is not enough input. |n_bits| MUST be positive.
329 Up to 24 bits are allowed to be requested from this method. */
330 static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(
331 BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) {
332 BROTLI_DCHECK(n_bits <= 24);
333 while (BrotliGetAvailableBits(br) < n_bits) {
334 if (!BrotliPullByte(br)) {
335 return BROTLI_FALSE;
336 }
337 }
338 BrotliTakeBits(br, n_bits, val);
339 return BROTLI_TRUE;
340 }
341
342 /* Same as BrotliSafeReadBits, but allows reading up to 32 bits. */
343 static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits32(
344 BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) {
345 BROTLI_DCHECK(n_bits <= 32);
346 if (BROTLI_64_BITS || (n_bits <= 24)) {
347 while (BrotliGetAvailableBits(br) < n_bits) {
348 if (!BrotliPullByte(br)) {
349 return BROTLI_FALSE;
350 }
351 }
352 BrotliTakeBits(br, n_bits, val);
353 return BROTLI_TRUE;
354 } else {
355 return BrotliSafeReadBits32Slow(br, n_bits, val);
356 }
357 }
358
359 /* Advances the bit reader position to the next byte boundary and verifies
360 that any skipped bits are set to zero. */
361 static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {
362 brotli_reg_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;
363 brotli_reg_t pad_bits = 0;
364 if (pad_bits_count != 0) {
365 BrotliTakeBits(br, pad_bits_count, &pad_bits);
366 }
367 BrotliBitReaderNormalize(br);
368 return TO_BROTLI_BOOL(pad_bits == 0);
369 }
370
371 static BROTLI_INLINE void BrotliDropBytes(BrotliBitReader* br, size_t num) {
372 /* Check detour is legal: accumulator must to be empty. */
373 BROTLI_DCHECK(br->bit_pos_ == 0);
374 BROTLI_DCHECK(br->val_ == 0);
375 br->next_in += num;
376 }
377
378 /* Copies remaining input bytes stored in the bit reader to the output. Value
379 |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be
380 warmed up again after this. */
381 static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
382 BrotliBitReader* br, size_t num) {
383 while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
384 *dest = (uint8_t)BrotliGetBitsUnmasked(br);
385 BrotliDropBits(br, 8);
386 ++dest;
387 --num;
388 }
389 BrotliBitReaderNormalize(br);
390 if (num > 0) {
391 memcpy(dest, br->next_in, num);
392 BrotliDropBytes(br, num);
393 }
394 }
395
396 BROTLI_UNUSED_FUNCTION void BrotliBitReaderSuppressUnusedFunctions(void) {
397 BROTLI_UNUSED(&BrotliBitReaderSuppressUnusedFunctions);
398
399 BROTLI_UNUSED(&BrotliBitReaderGetAvailIn);
400 BROTLI_UNUSED(&BrotliBitReaderLoadBits);
401 BROTLI_UNUSED(&BrotliBitReaderRestoreState);
402 BROTLI_UNUSED(&BrotliBitReaderSaveState);
403 BROTLI_UNUSED(&BrotliBitReaderSetInput);
404 BROTLI_UNUSED(&BrotliBitReaderUnload);
405 BROTLI_UNUSED(&BrotliCheckInputAmount);
406 BROTLI_UNUSED(&BrotliCopyBytes);
407 BROTLI_UNUSED(&BrotliFillBitWindow16);
408 BROTLI_UNUSED(&BrotliGet16BitsUnmasked);
409 BROTLI_UNUSED(&BrotliGetBits);
410 BROTLI_UNUSED(&BrotliGetRemainingBytes);
411 BROTLI_UNUSED(&BrotliJumpToByteBoundary);
412 BROTLI_UNUSED(&BrotliReadBits24);
413 BROTLI_UNUSED(&BrotliReadBits32);
414 BROTLI_UNUSED(&BrotliSafeGetBits);
415 BROTLI_UNUSED(&BrotliSafeReadBits);
416 BROTLI_UNUSED(&BrotliSafeReadBits32);
417 }
418
419 #if defined(__cplusplus) || defined(c_plusplus)
420 } /* extern "C" */
421 #endif
422
423 #endif /* BROTLI_DEC_BIT_READER_H_ */