third_party/brotli/dec/bit_reader.h

   1 /* Copyright 2013 Google Inc. All Rights Reserved.
   2
   3    Licensed under the Apache License, Version 2.0 (the "License");
   4    you may not use this file except in compliance with the License.
   5    You may obtain a copy of the License at
   6
   7    http://www.apache.org/licenses/LICENSE-2.0
   8
   9    Unless required by applicable law or agreed to in writing, software
  10    distributed under the License is distributed on an "AS IS" BASIS,
  11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    See the License for the specific language governing permissions and
  13    limitations under the License.
  14
  15    Bit reading helpers
  16 */
  17
  18 #ifndef BROTLI_DEC_BIT_READER_H_
  19 #define BROTLI_DEC_BIT_READER_H_
  20
  21 #include <string.h>
  22 #include "./streams.h"
  23 #include "./types.h"
  24
  25 #if defined(__cplusplus) || defined(c_plusplus)
  26 extern "C" {
  27 #endif
  28
  29 #define BROTLI_MAX_NUM_BIT_READ   25
  30 #define BROTLI_READ_SIZE          4096
  31 #define BROTLI_IBUF_SIZE          (2 * BROTLI_READ_SIZE + 32)
  32 #define BROTLI_IBUF_MASK          (2 * BROTLI_READ_SIZE - 1)
  33
  34 #define UNALIGNED_COPY64(dst, src) memcpy(dst, src, 8)
  35 #define UNALIGNED_MOVE64(dst, src) memmove(dst, src, 8)
  36
  37 static const uint32_t kBitMask[BROTLI_MAX_NUM_BIT_READ] = {
  38   0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
  39   65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
  40 };
  41
  42 typedef struct {
  43   /* Input byte buffer, consist of a ringbuffer and a "slack" region where */
  44   /* bytes from the start of the ringbuffer are copied. */
  45   uint8_t buf_[BROTLI_IBUF_SIZE];
  46   uint8_t*    buf_ptr_;      /* next input will write here */
  47   BrotliInput input_;        /* input callback */
  48   uint64_t    val_;          /* pre-fetched bits */
  49   uint32_t    pos_;          /* byte position in stream */
  50   uint32_t    bit_pos_;      /* current bit-reading position in val_ */
  51   uint32_t    bit_end_pos_;  /* bit-reading end position from LSB of val_ */
  52   int         eos_;          /* input stream is finished */
  53 } BrotliBitReader;
  54
  55 int BrotliInitBitReader(BrotliBitReader* const br, BrotliInput input);
  56
  57 /* Return the prefetched bits, so they can be looked up. */
  58 static BROTLI_INLINE uint32_t BrotliPrefetchBits(BrotliBitReader* const br) {
  59   return (uint32_t)(br->val_ >> br->bit_pos_);
  60 }
  61
  62 /* For jumping over a number of bits in the bit stream when accessed with */
  63 /* BrotliPrefetchBits and BrotliFillBitWindow. */
  64 static BROTLI_INLINE void BrotliSetBitPos(BrotliBitReader* const br,
  65                                           uint32_t val) {
  66 #ifdef BROTLI_DECODE_DEBUG
  67   uint32_t n_bits = val - br->bit_pos_;
  68   const uint32_t bval = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
  69   printf("[BrotliReadBits]  %010d %2d  val: %6x\n",
  70          (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, bval);
  71 #endif
  72   br->bit_pos_ = val;
  73 }
  74
  75 /* Reload up to 64 bits byte-by-byte */
  76 static BROTLI_INLINE void ShiftBytes(BrotliBitReader* const br) {
  77   while (br->bit_pos_ >= 8) {
  78     br->val_ >>= 8;
  79     br->val_ |= ((uint64_t)br->buf_[br->pos_ & BROTLI_IBUF_MASK]) << 56;
  80     ++br->pos_;
  81     br->bit_pos_ -= 8;
  82     br->bit_end_pos_ -= 8;
  83   }
  84 }
  85
  86 /* Fills up the input ringbuffer by calling the input callback.
  87
  88    Does nothing if there are at least 32 bytes present after current position.
  89
  90    Returns 0 if either:
  91     - the input callback returned an error, or
  92     - there is no more input and the position is past the end of the stream.
  93
  94    After encountering the end of the input stream, 32 additional zero bytes are
  95    copied to the ringbuffer, therefore it is safe to call this function after
  96    every 32 bytes of input is read.
  97 */
  98 static BROTLI_INLINE int BrotliReadMoreInput(BrotliBitReader* const br) {
  99   if (br->bit_end_pos_ > 256) {
 100     return 1;
 101   } else if (br->eos_) {
 102     return br->bit_pos_ <= br->bit_end_pos_;
 103   } else {
 104     uint8_t* dst = br->buf_ptr_;
 105     int bytes_read = BrotliRead(br->input_, dst, BROTLI_READ_SIZE);
 106     if (bytes_read < 0) {
 107       return 0;
 108     }
 109     if (bytes_read < BROTLI_READ_SIZE) {
 110       br->eos_ = 1;
 111       /* Store 32 bytes of zero after the stream end. */
 112 #if (defined(__x86_64__) || defined(_M_X64))
 113       *(uint64_t*)(dst + bytes_read) = 0;
 114       *(uint64_t*)(dst + bytes_read + 8) = 0;
 115       *(uint64_t*)(dst + bytes_read + 16) = 0;
 116       *(uint64_t*)(dst + bytes_read + 24) = 0;
 117 #else
 118       memset(dst + bytes_read, 0, 32);
 119 #endif
 120     }
 121     if (dst == br->buf_) {
 122       /* Copy the head of the ringbuffer to the slack region. */
 123 #if (defined(__x86_64__) || defined(_M_X64))
 124       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 32, br->buf_);
 125       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 24, br->buf_ + 8);
 126       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 16, br->buf_ + 16);
 127       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 8, br->buf_ + 24);
 128 #else
 129       memcpy(br->buf_ + (BROTLI_READ_SIZE << 1), br->buf_, 32);
 130 #endif
 131       br->buf_ptr_ = br->buf_ + BROTLI_READ_SIZE;
 132     } else {
 133       br->buf_ptr_ = br->buf_;
 134     }
 135     br->bit_end_pos_ += ((uint32_t)bytes_read << 3);
 136     return 1;
 137   }
 138 }
 139
 140 /* Advances the Read buffer by 5 bytes to make room for reading next 24 bits. */
 141 static BROTLI_INLINE void BrotliFillBitWindow(BrotliBitReader* const br) {
 142   if (br->bit_pos_ >= 40) {
 143 #if (defined(__x86_64__) || defined(_M_X64))
 144     br->val_ >>= 40;
 145     /* The expression below needs a little-endian arch to work correctly. */
 146     /* This gives a large speedup for decoding speed. */
 147     br->val_ |= *(const uint64_t*)(
 148         br->buf_ + (br->pos_ & BROTLI_IBUF_MASK)) << 24;
 149     br->pos_ += 5;
 150     br->bit_pos_ -= 40;
 151     br->bit_end_pos_ -= 40;
 152 #else
 153     ShiftBytes(br);
 154 #endif
 155   }
 156 }
 157
 158 /* Reads the specified number of bits from Read Buffer. */
 159 static BROTLI_INLINE uint32_t BrotliReadBits(
 160     BrotliBitReader* const br, int n_bits) {
 161   uint32_t val;
 162   BrotliFillBitWindow(br);
 163   val = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
 164 #ifdef BROTLI_DECODE_DEBUG
 165   printf("[BrotliReadBits]  %010d %2d  val: %6x\n",
 166          (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, val);
 167 #endif
 168   br->bit_pos_ += (uint32_t)n_bits;
 169   return val;
 170 }
 171
 172 #if defined(__cplusplus) || defined(c_plusplus)
 173 }    /* extern "C" */
 174 #endif
 175
 176 #endif  /* BROTLI_DEC_BIT_READER_H_ */