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_ */