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