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