MdeModulePkg: Copy Brotli algorithm 3rd party source code for library

[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / bit_reader.h

/* Copyright 2013 Google Inc. All Rights Reserved.\r
\r
   Distributed under MIT license.\r
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
*/\r
\r
/* Bit reading helpers */\r
\r
#ifndef BROTLI_DEC_BIT_READER_H_\r
#define BROTLI_DEC_BIT_READER_H_\r
\r
#include <string.h>  /* memcpy */\r
\r
#include "../common/types.h"\r
#include "./port.h"\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
extern "C" {\r
#endif\r
\r
#if (BROTLI_64_BITS)\r
#define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4\r
typedef uint64_t reg_t;\r
#else\r
#define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2\r
typedef uint32_t reg_t;\r
#endif\r
\r
static const uint32_t kBitMask[33] = { 0x0000,\r
    0x00000001, 0x00000003, 0x00000007, 0x0000000F,\r
    0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,\r
    0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,\r
    0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,\r
    0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,\r
    0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,\r
    0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,\r
    0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF\r
};\r
\r
static BROTLI_INLINE uint32_t BitMask(uint32_t n) {\r
  if (IS_CONSTANT(n) || BROTLI_HAS_UBFX) {\r
    /* Masking with this expression turns to a single\r
       "Unsigned Bit Field Extract" UBFX instruction on ARM. */\r
    return ~((0xffffffffU) << n);\r
  } else {\r
    return kBitMask[n];\r
  }\r
}\r
\r
typedef struct {\r
  reg_t val_;              /* pre-fetched bits */\r
  uint32_t bit_pos_;       /* current bit-reading position in val_ */\r
  const uint8_t* next_in;  /* the byte we're reading from */\r
  size_t avail_in;\r
} BrotliBitReader;\r
\r
typedef struct {\r
  reg_t val_;\r
  uint32_t bit_pos_;\r
  const uint8_t* next_in;\r
  size_t avail_in;\r
} BrotliBitReaderState;\r
\r
/* Initializes the bitreader fields. */\r
BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);\r
\r
/* Ensures that accumulator is not empty. May consume one byte of input.\r
   Returns 0 if data is required but there is no input available.\r
   For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned\r
   reading. */\r
BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br);\r
\r
static BROTLI_INLINE void BrotliBitReaderSaveState(\r
    BrotliBitReader* const from, BrotliBitReaderState* to) {\r
  to->val_ = from->val_;\r
  to->bit_pos_ = from->bit_pos_;\r
  to->next_in = from->next_in;\r
  to->avail_in = from->avail_in;\r
}\r
\r
static BROTLI_INLINE void BrotliBitReaderRestoreState(\r
    BrotliBitReader* const to, BrotliBitReaderState* from) {\r
  to->val_ = from->val_;\r
  to->bit_pos_ = from->bit_pos_;\r
  to->next_in = from->next_in;\r
  to->avail_in = from->avail_in;\r
}\r
\r
static BROTLI_INLINE uint32_t BrotliGetAvailableBits(\r
    const BrotliBitReader* br) {\r
  return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_;\r
}\r
\r
/* Returns amount of unread bytes the bit reader still has buffered from the\r
   BrotliInput, including whole bytes in br->val_. */\r
static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {\r
  return br->avail_in + (BrotliGetAvailableBits(br) >> 3);\r
}\r
\r
/* Checks if there is at least num bytes left in the input ringbuffer (excluding\r
   the bits remaining in br->val_). */\r
static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount(\r
    BrotliBitReader* const br, size_t num) {\r
  return TO_BROTLI_BOOL(br->avail_in >= num);\r
}\r
\r
static BROTLI_INLINE uint16_t BrotliLoad16LE(const uint8_t* in) {\r
  if (BROTLI_LITTLE_ENDIAN) {\r
    return *((const uint16_t*)in);\r
  } else if (BROTLI_BIG_ENDIAN) {\r
    uint16_t value = *((const uint16_t*)in);\r
    return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8));\r
  } else {\r
    return (uint16_t)(in[0] | (in[1] << 8));\r
  }\r
}\r
\r
static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {\r
  if (BROTLI_LITTLE_ENDIAN) {\r
    return *((const uint32_t*)in);\r
  } else if (BROTLI_BIG_ENDIAN) {\r
    uint32_t value = *((const uint32_t*)in);\r
    return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |\r
        ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);\r
  } else {\r
    uint32_t value = (uint32_t)(*(in++));\r
    value |= (uint32_t)(*(in++)) << 8;\r
    value |= (uint32_t)(*(in++)) << 16;\r
    value |= (uint32_t)(*(in++)) << 24;\r
    return value;\r
  }\r
}\r
\r
#if (BROTLI_64_BITS)\r
static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {\r
  if (BROTLI_LITTLE_ENDIAN) {\r
    return *((const uint64_t*)in);\r
  } else if (BROTLI_BIG_ENDIAN) {\r
    uint64_t value = *((const uint64_t*)in);\r
    return\r
        ((value & 0xFFU) << 56) |\r
        ((value & 0xFF00U) << 40) |\r
        ((value & 0xFF0000U) << 24) |\r
        ((value & 0xFF000000U) << 8) |\r
        ((value & 0xFF00000000U) >> 8) |\r
        ((value & 0xFF0000000000U) >> 24) |\r
        ((value & 0xFF000000000000U) >> 40) |\r
        ((value & 0xFF00000000000000U) >> 56);\r
  } else {\r
    uint64_t value = (uint64_t)(*(in++));\r
    value |= (uint64_t)(*(in++)) << 8;\r
    value |= (uint64_t)(*(in++)) << 16;\r
    value |= (uint64_t)(*(in++)) << 24;\r
    value |= (uint64_t)(*(in++)) << 32;\r
    value |= (uint64_t)(*(in++)) << 40;\r
    value |= (uint64_t)(*(in++)) << 48;\r
    value |= (uint64_t)(*(in++)) << 56;\r
    return value;\r
  }\r
}\r
#endif\r
\r
/* Guarantees that there are at least n_bits + 1 bits in accumulator.\r
   Precondition: accumulator contains at least 1 bit.\r
   n_bits should be in the range [1..24] for regular build. For portable\r
   non-64-bit little endian build only 16 bits are safe to request. */\r
static BROTLI_INLINE void BrotliFillBitWindow(\r
    BrotliBitReader* const br, uint32_t n_bits) {\r
#if (BROTLI_64_BITS)\r
  if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {\r
    if (br->bit_pos_ >= 56) {\r
      br->val_ >>= 56;\r
      br->bit_pos_ ^= 56;  /* here same as -= 56 because of the if condition */\r
      br->val_ |= BrotliLoad64LE(br->next_in) << 8;\r
      br->avail_in -= 7;\r
      br->next_in += 7;\r
    }\r
  } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {\r
    if (br->bit_pos_ >= 48) {\r
      br->val_ >>= 48;\r
      br->bit_pos_ ^= 48;  /* here same as -= 48 because of the if condition */\r
      br->val_ |= BrotliLoad64LE(br->next_in) << 16;\r
      br->avail_in -= 6;\r
      br->next_in += 6;\r
    }\r
  } else {\r
    if (br->bit_pos_ >= 32) {\r
      br->val_ >>= 32;\r
      br->bit_pos_ ^= 32;  /* here same as -= 32 because of the if condition */\r
      br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;\r
      br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r
      br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r
    }\r
  }\r
#else\r
  if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {\r
    if (br->bit_pos_ >= 24) {\r
      br->val_ >>= 24;\r
      br->bit_pos_ ^= 24;  /* here same as -= 24 because of the if condition */\r
      br->val_ |= BrotliLoad32LE(br->next_in) << 8;\r
      br->avail_in -= 3;\r
      br->next_in += 3;\r
    }\r
  } else {\r
    if (br->bit_pos_ >= 16) {\r
      br->val_ >>= 16;\r
      br->bit_pos_ ^= 16;  /* here same as -= 16 because of the if condition */\r
      br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;\r
      br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r
      br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;\r
    }\r
  }\r
#endif\r
}\r
\r
/* Mosltly like BrotliFillBitWindow, but guarantees only 16 bits and reads no\r
   more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */\r
static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {\r
  BrotliFillBitWindow(br, 17);\r
}\r
\r
/* Pulls one byte of input to accumulator. */\r
static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) {\r
  if (br->avail_in == 0) {\r
    return BROTLI_FALSE;\r
  }\r
  br->val_ >>= 8;\r
#if (BROTLI_64_BITS)\r
  br->val_ |= ((uint64_t)*br->next_in) << 56;\r
#else\r
  br->val_ |= ((uint32_t)*br->next_in) << 24;\r
#endif\r
  br->bit_pos_ -= 8;\r
  --br->avail_in;\r
  ++br->next_in;\r
  return BROTLI_TRUE;\r
}\r
\r
/* Returns currently available bits.\r
   The number of valid bits could be calclulated by BrotliGetAvailableBits. */\r
static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {\r
  return br->val_ >> br->bit_pos_;\r
}\r
\r
/* Like BrotliGetBits, but does not mask the result.\r
   The result contains at least 16 valid bits. */\r
static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(\r
    BrotliBitReader* const br) {\r
  BrotliFillBitWindow(br, 16);\r
  return (uint32_t)BrotliGetBitsUnmasked(br);\r
}\r
\r
/* Returns the specified number of bits from br without advancing bit pos. */\r
static BROTLI_INLINE uint32_t BrotliGetBits(\r
    BrotliBitReader* const br, uint32_t n_bits) {\r
  BrotliFillBitWindow(br, n_bits);\r
  return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r
}\r
\r
/* Tries to peek the specified amount of bits. Returns 0, if there is not\r
   enough input. */\r
static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits(\r
    BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r
  while (BrotliGetAvailableBits(br) < n_bits) {\r
    if (!BrotliPullByte(br)) {\r
      return BROTLI_FALSE;\r
    }\r
  }\r
  *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r
  return BROTLI_TRUE;\r
}\r
\r
/* Advances the bit pos by n_bits. */\r
static BROTLI_INLINE void BrotliDropBits(\r
    BrotliBitReader* const br, uint32_t n_bits) {\r
  br->bit_pos_ += n_bits;\r
}\r
\r
static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {\r
  uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;\r
  uint32_t unused_bits = unused_bytes << 3;\r
  br->avail_in += unused_bytes;\r
  br->next_in -= unused_bytes;\r
  if (unused_bits == sizeof(br->val_) << 3) {\r
    br->val_ = 0;\r
  } else {\r
    br->val_ <<= unused_bits;\r
  }\r
  br->bit_pos_ += unused_bits;\r
}\r
\r
/* Reads the specified number of bits from br and advances the bit pos.\r
   Precondition: accumulator MUST contain at least n_bits. */\r
static BROTLI_INLINE void BrotliTakeBits(\r
  BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r
  *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);\r
  BROTLI_LOG(("[BrotliReadBits]  %d %d %d val: %6x\n",\r
      (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val));\r
  BrotliDropBits(br, n_bits);\r
}\r
\r
/* Reads the specified number of bits from br and advances the bit pos.\r
   Assumes that there is enough input to perform BrotliFillBitWindow. */\r
static BROTLI_INLINE uint32_t BrotliReadBits(\r
    BrotliBitReader* const br, uint32_t n_bits) {\r
  if (BROTLI_64_BITS || (n_bits <= 16)) {\r
    uint32_t val;\r
    BrotliFillBitWindow(br, n_bits);\r
    BrotliTakeBits(br, n_bits, &val);\r
    return val;\r
  } else {\r
    uint32_t low_val;\r
    uint32_t high_val;\r
    BrotliFillBitWindow(br, 16);\r
    BrotliTakeBits(br, 16, &low_val);\r
    BrotliFillBitWindow(br, 8);\r
    BrotliTakeBits(br, n_bits - 16, &high_val);\r
    return low_val | (high_val << 16);\r
  }\r
}\r
\r
/* Tries to read the specified amount of bits. Returns 0, if there is not\r
   enough input. n_bits MUST be positive. */\r
static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits(\r
    BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r
  while (BrotliGetAvailableBits(br) < n_bits) {\r
    if (!BrotliPullByte(br)) {\r
      return BROTLI_FALSE;\r
    }\r
  }\r
  BrotliTakeBits(br, n_bits, val);\r
  return BROTLI_TRUE;\r
}\r
\r
/* Advances the bit reader position to the next byte boundary and verifies\r
   that any skipped bits are set to zero. */\r
static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) {\r
  uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7;\r
  uint32_t pad_bits = 0;\r
  if (pad_bits_count != 0) {\r
    BrotliTakeBits(br, pad_bits_count, &pad_bits);\r
  }\r
  return TO_BROTLI_BOOL(pad_bits == 0);\r
}\r
\r
/* Peeks a byte at specified offset.\r
   Precondition: bit reader is parked to a byte boundary.\r
   Returns -1 if operation is not feasible. */\r
static BROTLI_INLINE int BrotliPeekByte(BrotliBitReader* br, size_t offset) {\r
  uint32_t available_bits = BrotliGetAvailableBits(br);\r
  size_t bytes_left = available_bits >> 3;\r
  BROTLI_DCHECK((available_bits & 7) == 0);\r
  if (offset < bytes_left) {\r
    return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;\r
  }\r
  offset -= bytes_left;\r
  if (offset < br->avail_in) {\r
    return br->next_in[offset];\r
  }\r
  return -1;\r
}\r
\r
/* Copies remaining input bytes stored in the bit reader to the output. Value\r
   num may not be larger than BrotliGetRemainingBytes. The bit reader must be\r
   warmed up again after this. */\r
static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,\r
                                          BrotliBitReader* br, size_t num) {\r
  while (BrotliGetAvailableBits(br) >= 8 && num > 0) {\r
    *dest = (uint8_t)BrotliGetBitsUnmasked(br);\r
    BrotliDropBits(br, 8);\r
    ++dest;\r
    --num;\r
  }\r
  memcpy(dest, br->next_in, num);\r
  br->avail_in -= num;\r
  br->next_in += num;\r
}\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
}  /* extern "C" */\r
#endif\r
\r
#endif  /* BROTLI_DEC_BIT_READER_H_ */\r