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 #include <BrotliDecompressLibInternal.h>
  14
  15 #include "../common/types.h"
  16 #include "./port.h"
  17
  18 #if defined(__cplusplus) || defined(c_plusplus)
  19 extern "C" {
  20 #endif
  21
  22 #if (BROTLI_64_BITS)
  23 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4
  24 typedef uint64_t reg_t;
  25 #else
  26 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2
  27 typedef uint32_t reg_t;
  28 #endif
  29
  30 static const uint32_t kBitMask[33] = { 0x0000,
  31     0x00000001, 0x00000003, 0x00000007, 0x0000000F,
  32     0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
  33     0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
  34     0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
  35     0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
  36     0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
  37     0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
  38     0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
  39 };
  40
  41 static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
  42   if (IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
  43     /* Masking with this expression turns to a single
  44        "Unsigned Bit Field Extract" UBFX instruction on ARM. */
  45     return ~((0xffffffffU) << n);
  46   } else {
  47     return kBitMask[n];
  48   }
  49 }
  50
  51 typedef struct {
  52   reg_t val_;              /* pre-fetched bits */
  53   uint32_t bit_pos_;       /* current bit-reading position in val_ */
  54   const uint8_t* next_in;  /* the byte we're reading from */
  55   size_t avail_in;
  56 } BrotliBitReader;
  57
  58 typedef struct {
  59   reg_t val_;
  60   uint32_t bit_pos_;
  61   const uint8_t* next_in;
  62   size_t avail_in;
  63 } BrotliBitReaderState;
  64
  65 /* Initializes the bitreader fields. */
  66 BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);
  67
  68 /* Ensures that accumulator is not empty. May consume one byte of input.
  69    Returns 0 if data is required but there is no input available.
  70    For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned
  71    reading. */
  72 BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);
  73
  74 static BROTLI_INLINE void BrotliBitReaderSaveState(
  75     BrotliBitReader* const from, BrotliBitReaderState* to) {
  76   to->val_ = from->val_;
  77   to->bit_pos_ = from->bit_pos_;
  78   to->next_in = from->next_in;
  79   to->avail_in = from->avail_in;
  80 }
  81
  82 static BROTLI_INLINE void BrotliBitReaderRestoreState(
  83     BrotliBitReader* const to, BrotliBitReaderState* from) {
  84   to->val_ = from->val_;
  85   to->bit_pos_ = from->bit_pos_;
  86   to->next_in = from->next_in;
  87   to->avail_in = from->avail_in;
  88 }
  89
  90 static BROTLI_INLINE uint32_t BrotliGetAvailableBits(
  91     const BrotliBitReader* br) {
  92   return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;
  93 }
  94
  95 /* Returns amount of unread bytes the bit reader still has buffered from the
  96    BrotliInput, including whole bytes in br->val_. */
  97 static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
  98   return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
  99 }
 100
 101 /* Checks if there is at least num bytes left in the input ringbuffer (excluding
 102    the bits remaining in br->val_). */
 103 static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(
 104     BrotliBitReader* const br, size_t num) {
 105   return TO_BROTLI_BOOL(br->avail_in >= num);
 106 }
 107
 108 static BROTLI_INLINE uint16_t BrotliLoad16LE(const uint8_t* in) {
 109   if (BROTLI_LITTLE_ENDIAN) {
 110     return *((const uint16_t*)in);
 111   } else if (BROTLI_BIG_ENDIAN) {
 112     uint16_t value = *((const uint16_t*)in);
 113     return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8));
 114   } else {
 115     return (uint16_t)(in[0] | (in[1] << 8));
 116   }
 117 }
 118
 119 static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {
 120   if (BROTLI_LITTLE_ENDIAN) {
 121     return *((const uint32_t*)in);
 122   } else if (BROTLI_BIG_ENDIAN) {
 123     uint32_t value = *((const uint32_t*)in);
 124     return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |
 125         ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);
 126   } else {
 127     uint32_t value = (uint32_t)(*(in++));
 128     value |= (uint32_t)(*(in++)) << 8;
 129     value |= (uint32_t)(*(in++)) << 16;
 130     value |= (uint32_t)(*(in++)) << 24;
 131     return value;
 132   }
 133 }
 134
 135 #if (BROTLI_64_BITS)
 136 static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {
 137   if (BROTLI_LITTLE_ENDIAN) {
 138     return *((const uint64_t*)in);
 139   } else if (BROTLI_BIG_ENDIAN) {
 140     uint64_t value = *((const uint64_t*)in);
 141     return
 142         ((value & 0xFFU) << 56) |
 143         ((value & 0xFF00U) << 40) |
 144         ((value & 0xFF0000U) << 24) |
 145         ((value & 0xFF000000U) << 8) |
 146         ((value & 0xFF00000000U) >> 8) |
 147         ((value & 0xFF0000000000U) >> 24) |
 148         ((value & 0xFF000000000000U) >> 40) |
 149         ((value & 0xFF00000000000000U) >> 56);
 150   } else {
 151     uint64_t value = (uint64_t)(*(in++));
 152     value |= (uint64_t)(*(in++)) << 8;
 153     value |= (uint64_t)(*(in++)) << 16;
 154     value |= (uint64_t)(*(in++)) << 24;
 155     value |= (uint64_t)(*(in++)) << 32;
 156     value |= (uint64_t)(*(in++)) << 40;
 157     value |= (uint64_t)(*(in++)) << 48;
 158     value |= (uint64_t)(*(in++)) << 56;
 159     return value;
 160   }
 161 }
 162 #endif
 163
 164 /* Guarantees that there are at least n_bits + 1 bits in accumulator.
 165    Precondition: accumulator contains at least 1 bit.
 166    n_bits should be in the range [1..24] for regular build. For portable
 167    non-64-bit little endian build only 16 bits are safe to request. */
 168 static BROTLI_INLINE void BrotliFillBitWindow(
 169     BrotliBitReader* const br, uint32_t n_bits) {
 170 #if (BROTLI_64_BITS)
 171   if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
 172     if (br->bit_pos_ >= 56) {
 173       br->val_ >>= 56;
 174       br->bit_pos_ ^= 56;  /* here same as -= 56 because of the if condition */
 175       br->val_ |= BrotliLoad64LE(br->next_in) << 8;
 176       br->avail_in -= 7;
 177       br->next_in += 7;
 178     }
 179   } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {
 180     if (br->bit_pos_ >= 48) {
 181       br->val_ >>= 48;
 182       br->bit_pos_ ^= 48;  /* here same as -= 48 because of the if condition */
 183       br->val_ |= BrotliLoad64LE(br->next_in) << 16;
 184       br->avail_in -= 6;
 185       br->next_in += 6;
 186     }
 187   } else {
 188     if (br->bit_pos_ >= 32) {
 189       br->val_ >>= 32;
 190       br->bit_pos_ ^= 32;  /* here same as -= 32 because of the if condition */
 191       br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;
 192       br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 193       br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 194     }
 195   }
 196 #else
 197   if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
 198     if (br->bit_pos_ >= 24) {
 199       br->val_ >>= 24;
 200       br->bit_pos_ ^= 24;  /* here same as -= 24 because of the if condition */
 201       br->val_ |= BrotliLoad32LE(br->next_in) << 8;
 202       br->avail_in -= 3;
 203       br->next_in += 3;
 204     }
 205   } else {
 206     if (br->bit_pos_ >= 16) {
 207       br->val_ >>= 16;
 208       br->bit_pos_ ^= 16;  /* here same as -= 16 because of the if condition */
 209       br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;
 210       br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 211       br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 212     }
 213   }
 214 #endif
 215 }
 216
 217 /* Mosltly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
 218    more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
 219 static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
 220   BrotliFillBitWindow(br, 17);
 221 }
 222
 223 /* Pulls one byte of input to accumulator. */
 224 static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {
 225   if (br->avail_in == 0) {
 226     return BROTLI_FALSE;
 227   }
 228   br->val_ >>= 8;
 229 #if (BROTLI_64_BITS)
 230   br->val_ |= ((uint64_t)*br->next_in) << 56;
 231 #else
 232   br->val_ |= ((uint32_t)*br->next_in) << 24;
 233 #endif
 234   br->bit_pos_ -= 8;
 235   --br->avail_in;
 236   ++br->next_in;
 237   return BROTLI_TRUE;
 238 }
 239
 240 /* Returns currently available bits.
 241    The number of valid bits could be calclulated by BrotliGetAvailableBits. */
 242 static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {
 243   return br->val_ >> br->bit_pos_;
 244 }
 245
 246 /* Like BrotliGetBits, but does not mask the result.
 247    The result contains at least 16 valid bits. */
 248 static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(
 249     BrotliBitReader* const br) {
 250   BrotliFillBitWindow(br, 16);
 251   return (uint32_t)BrotliGetBitsUnmasked(br);
 252 }
 253
 254 /* Returns the specified number of bits from br without advancing bit pos. */
 255 static BROTLI_INLINE uint32_t BrotliGetBits(
 256     BrotliBitReader* const br, uint32_t n_bits) {
 257   BrotliFillBitWindow(br, n_bits);
 258   return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
 259 }
 260
 261 /* Tries to peek the specified amount of bits. Returns 0, if there is not
 262    enough input. */
 263 static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(
 264     BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
 265   while (BrotliGetAvailableBits(br) < n_bits) {
 266     if (!BrotliPullByte(br)) {
 267       return BROTLI_FALSE;
 268     }
 269   }
 270   *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
 271   return BROTLI_TRUE;
 272 }
 273
 274 /* Advances the bit pos by n_bits. */
 275 static BROTLI_INLINE void BrotliDropBits(
 276     BrotliBitReader* const br, uint32_t n_bits) {
 277   br->bit_pos_ += n_bits;
 278 }
 279
 280 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
 281   uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
 282   uint32_t unused_bits = unused_bytes << 3;
 283   br->avail_in += unused_bytes;
 284   br->next_in -= unused_bytes;
 285   if (unused_bits == sizeof(br->val_) << 3) {
 286     br->val_ = 0;
 287   } else {
 288     br->val_ <<= unused_bits;
 289   }
 290   br->bit_pos_ += unused_bits;
 291 }
 292
 293 /* Reads the specified number of bits from br and advances the bit pos.
 294    Precondition: accumulator MUST contain at least n_bits. */
 295 static BROTLI_INLINE void BrotliTakeBits(
 296   BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
 297   *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
 298   BROTLI_LOG(("[BrotliReadBits]  %d %d %d val: %6x\n",
 299       (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val));
 300   BrotliDropBits(br, n_bits);
 301 }
 302
 303 /* Reads the specified number of bits from br and advances the bit pos.
 304    Assumes that there is enough input to perform BrotliFillBitWindow. */
 305 static BROTLI_INLINE uint32_t BrotliReadBits(
 306     BrotliBitReader* const br, uint32_t n_bits) {
 307   if (BROTLI_64_BITS || (n_bits <= 16)) {
 308     uint32_t val;
 309     BrotliFillBitWindow(br, n_bits);
 310     BrotliTakeBits(br, n_bits, &val);
 311     return val;
 312   } else {
 313     uint32_t low_val;
 314     uint32_t high_val;
 315     BrotliFillBitWindow(br, 16);
 316     BrotliTakeBits(br, 16, &low_val);
 317     BrotliFillBitWindow(br, 8);
 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 0, if there is not
 324    enough input. n_bits MUST be positive. */
 325 static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(
 326     BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
 327   while (BrotliGetAvailableBits(br) < n_bits) {
 328     if (!BrotliPullByte(br)) {
 329       return BROTLI_FALSE;
 330     }
 331   }
 332   BrotliTakeBits(br, n_bits, val);
 333   return BROTLI_TRUE;
 334 }
 335
 336 /* Advances the bit reader position to the next byte boundary and verifies
 337    that any skipped bits are set to zero. */
 338 static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {
 339   uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;
 340   uint32_t pad_bits = 0;
 341   if (pad_bits_count != 0) {
 342     BrotliTakeBits(br, pad_bits_count, &pad_bits);
 343   }
 344   return TO_BROTLI_BOOL(pad_bits == 0);
 345 }
 346
 347 /* Peeks a byte at specified offset.
 348    Precondition: bit reader is parked to a byte boundary.
 349    Returns -1 if operation is not feasible. */
 350 static BROTLI_INLINE int BrotliPeekByte(BrotliBitReader* br, size_t offset) {
 351   uint32_t available_bits = BrotliGetAvailableBits(br);
 352   size_t bytes_left = available_bits >> 3;
 353   BROTLI_DCHECK((available_bits & 7) == 0);
 354   if (offset < bytes_left) {
 355     return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;
 356   }
 357   offset -= bytes_left;
 358   if (offset < br->avail_in) {
 359     return br->next_in[offset];
 360   }
 361   return -1;
 362 }
 363
 364 /* Copies remaining input bytes stored in the bit reader to the output. Value
 365    num may not be larger than BrotliGetRemainingBytes. The bit reader must be
 366    warmed up again after this. */
 367 static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
 368                                           BrotliBitReader* br, size_t num) {
 369   while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
 370     *dest = (uint8_t)BrotliGetBitsUnmasked(br);
 371     BrotliDropBits(br, 8);
 372     ++dest;
 373     --num;
 374   }
 375   memcpy(dest, br->next_in, num);
 376   br->avail_in -= num;
 377   br->next_in += num;
 378 }
 379
 380 #if defined(__cplusplus) || defined(c_plusplus)
 381 }  /* extern "C" */
 382 #endif
 383
 384 #endif  /* BROTLI_DEC_BIT_READER_H_ */