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 <stdio.h>
  13 #include <string.h>
  14 #include "./port.h"
  15 #include "./types.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 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_BUILD_PORTABLE this function also prepares bit reader for aligned
  70    reading. */
  71 int 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 int BrotliCheckInputAmount(
 103     BrotliBitReader* const br, size_t num) {
 104   return 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)(
 113         ((value & 0xFFU) << 8) |
 114         ((value & 0xFF00U) >> 8));
 115   } else {
 116     return (uint16_t)(in[0] | (in[1] << 8));
 117   }
 118 }
 119
 120 static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {
 121   if (BROTLI_LITTLE_ENDIAN) {
 122     return *((const uint32_t*)in);
 123   } else if (BROTLI_BIG_ENDIAN) {
 124     uint32_t value = *((const uint32_t*)in);
 125     return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |
 126         ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);
 127   } else {
 128     uint32_t value = (uint32_t)(*(in++));
 129     value |= (uint32_t)(*(in++)) << 8;
 130     value |= (uint32_t)(*(in++)) << 16;
 131     value |= (uint32_t)(*(in++)) << 24;
 132     return value;
 133   }
 134 }
 135
 136 #if (BROTLI_64_BITS)
 137 static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {
 138   if (BROTLI_LITTLE_ENDIAN) {
 139     return *((const uint64_t*)in);
 140   } else if (BROTLI_BIG_ENDIAN) {
 141     uint64_t value = *((const uint64_t*)in);
 142     return
 143         ((value & 0xFFU) << 56) |
 144         ((value & 0xFF00U) << 40) |
 145         ((value & 0xFF0000U) << 24) |
 146         ((value & 0xFF000000U) << 8) |
 147         ((value & 0xFF00000000U) >> 8) |
 148         ((value & 0xFF0000000000U) >> 24) |
 149         ((value & 0xFF000000000000U) >> 40) |
 150         ((value & 0xFF00000000000000U) >> 56);
 151   } else {
 152     uint64_t value = (uint64_t)(*(in++));
 153     value |= (uint64_t)(*(in++)) << 8;
 154     value |= (uint64_t)(*(in++)) << 16;
 155     value |= (uint64_t)(*(in++)) << 24;
 156     value |= (uint64_t)(*(in++)) << 32;
 157     value |= (uint64_t)(*(in++)) << 40;
 158     value |= (uint64_t)(*(in++)) << 48;
 159     value |= (uint64_t)(*(in++)) << 56;
 160     return value;
 161   }
 162 }
 163 #endif
 164
 165 /* Guarantees that there are at least n_bits + 1 bits in accumulator.
 166    Precondition: accumulator contains at least 1 bit.
 167    n_bits should be in the range [1..24] for regular build. For portable
 168    non-64-bit little endian build only 16 bits are safe to request. */
 169 static BROTLI_INLINE void BrotliFillBitWindow(
 170     BrotliBitReader* const br, uint32_t n_bits) {
 171 #if (BROTLI_64_BITS)
 172   if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
 173     if (br->bit_pos_ >= 56) {
 174       br->val_ >>= 56;
 175       br->bit_pos_ ^= 56;  /* here same as -= 56 because of the if condition */
 176       br->val_ |= BrotliLoad64LE(br->next_in) << 8;
 177       br->avail_in -= 7;
 178       br->next_in += 7;
 179     }
 180   } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {
 181     if (br->bit_pos_ >= 48) {
 182       br->val_ >>= 48;
 183       br->bit_pos_ ^= 48;  /* here same as -= 48 because of the if condition */
 184       br->val_ |= BrotliLoad64LE(br->next_in) << 16;
 185       br->avail_in -= 6;
 186       br->next_in += 6;
 187     }
 188   } else {
 189     if (br->bit_pos_ >= 32) {
 190       br->val_ >>= 32;
 191       br->bit_pos_ ^= 32;  /* here same as -= 32 because of the if condition */
 192       br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;
 193       br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 194       br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 195     }
 196   }
 197 #else
 198   if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
 199     if (br->bit_pos_ >= 24) {
 200       br->val_ >>= 24;
 201       br->bit_pos_ ^= 24;  /* here same as -= 24 because of the if condition */
 202       br->val_ |= BrotliLoad32LE(br->next_in) << 8;
 203       br->avail_in -= 3;
 204       br->next_in += 3;
 205     }
 206   } else {
 207     if (br->bit_pos_ >= 16) {
 208       br->val_ >>= 16;
 209       br->bit_pos_ ^= 16;  /* here same as -= 16 because of the if condition */
 210       br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;
 211       br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 212       br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
 213     }
 214   }
 215 #endif
 216 }
 217
 218 /* Mosltly like BrotliFillBitWindow, but guarantees only 16 bits and reads no
 219    more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */
 220 static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) {
 221   BrotliFillBitWindow(br, 17);
 222 }
 223
 224 /* Pulls one byte of input to accumulator. */
 225 static BROTLI_INLINE int BrotliPullByte(BrotliBitReader* const br) {
 226   if (br->avail_in == 0) {
 227     return 0;
 228   }
 229   br->val_ >>= 8;
 230 #if (BROTLI_64_BITS)
 231     br->val_ |= ((uint64_t)*br->next_in) << 56;
 232 #else
 233     br->val_ |= ((uint32_t)*br->next_in) << 24;
 234 #endif
 235   br->bit_pos_ -= 8;
 236   --br->avail_in;
 237   ++br->next_in;
 238   return 1;
 239 }
 240
 241 /* Returns currently available bits.
 242    The number of valid bits could be calclulated by BrotliGetAvailableBits. */
 243 static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {
 244   return br->val_ >> br->bit_pos_;
 245 }
 246
 247 /* Like BrotliGetBits, but does not mask the result.
 248    The result contains at least 16 valid bits. */
 249 static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked(
 250     BrotliBitReader* const br) {
 251   BrotliFillBitWindow(br, 16);
 252   return (uint32_t)BrotliGetBitsUnmasked(br);
 253 }
 254
 255 /* Returns the specified number of bits from br without advancing bit pos. */
 256 static BROTLI_INLINE uint32_t BrotliGetBits(
 257     BrotliBitReader* const br, uint32_t n_bits) {
 258   BrotliFillBitWindow(br, n_bits);
 259   return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
 260 }
 261
 262 /* Tries to peek the specified amount of bits. Returns 0, if there is not
 263    enough input. */
 264 static BROTLI_INLINE int BrotliSafeGetBits(
 265   BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
 266   while (BrotliGetAvailableBits(br) < n_bits) {
 267     if (!BrotliPullByte(br)) {
 268       return 0;
 269     }
 270   }
 271   *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
 272   return 1;
 273 }
 274
 275 /* Advances the bit pos by n_bits. */
 276 static BROTLI_INLINE void BrotliDropBits(
 277     BrotliBitReader* const br, uint32_t n_bits) {
 278   br->bit_pos_ += n_bits;
 279 }
 280
 281 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) {
 282   uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3;
 283   uint32_t unused_bits = unused_bytes << 3;
 284   br->avail_in += unused_bytes;
 285   br->next_in -= unused_bytes;
 286   br->val_ <<= unused_bits;
 287   br->bit_pos_ += unused_bits;
 288 }
 289
 290 /* Reads the specified number of bits from br and advances the bit pos.
 291    Precondition: accumulator MUST contain at least n_bits. */
 292 static BROTLI_INLINE void BrotliTakeBits(
 293   BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
 294   *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
 295 #ifdef BROTLI_DECODE_DEBUG
 296   printf("[BrotliReadBits]  %d %d %d val: %6x\n",
 297          (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val);
 298 #endif
 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 int BrotliSafeReadBits(
 325   BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
 326   while (BrotliGetAvailableBits(br) < n_bits) {
 327     if (!BrotliPullByte(br)) {
 328       return 0;
 329     }
 330   }
 331   BrotliTakeBits(br, n_bits, val);
 332   return 1;
 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 int 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 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   if (available_bits & 7) {
 353     return -1;
 354   }
 355   if (offset < bytes_left) {
 356     return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;
 357   }
 358   offset -= bytes_left;
 359   if (offset < br->avail_in) {
 360     return br->next_in[offset];
 361   }
 362   return -1;
 363 }
 364
 365 /* Copies remaining input bytes stored in the bit reader to the output. Value
 366    num may not be larger than BrotliGetRemainingBytes. The bit reader must be
 367    warmed up again after this. */
 368 static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
 369                                           BrotliBitReader* br, size_t num) {
 370   while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
 371     *dest = (uint8_t)BrotliGetBitsUnmasked(br);
 372     BrotliDropBits(br, 8);
 373     ++dest;
 374     --num;
 375   }
 376   memcpy(dest, br->next_in, num);
 377   br->avail_in -= num;
 378   br->next_in += num;
 379 }
 380
 381 #if defined(__cplusplus) || defined(c_plusplus)
 382 }    /* extern "C" */
 383 #endif
 384
 385 #endif  /* BROTLI_DEC_BIT_READER_H_ */