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
  16 /* Bit reading helpers */
  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 #if (defined(__x86_64__) || defined(_M_X64))
  30 /* This should be set to 1 only on little-endian machines. */
  31 #define BROTLI_USE_64_BITS 1
  32 #else
  33 #define BROTLI_USE_64_BITS 0
  34 #endif
  35 #define BROTLI_MAX_NUM_BIT_READ   25
  36 #define BROTLI_READ_SIZE          4096
  37 #define BROTLI_IBUF_SIZE          (2 * BROTLI_READ_SIZE + 32)
  38 #define BROTLI_IBUF_MASK          (2 * BROTLI_READ_SIZE - 1)
  39
  40 #define UNALIGNED_COPY64(dst, src) memcpy(dst, src, 8)
  41 #define UNALIGNED_MOVE64(dst, src) memmove(dst, src, 8)
  42
  43 static const uint32_t kBitMask[BROTLI_MAX_NUM_BIT_READ] = {
  44   0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
  45   65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
  46 };
  47
  48 typedef struct {
  49   /* Input byte buffer, consist of a ringbuffer and a "slack" region where */
  50   /* bytes from the start of the ringbuffer are copied. */
  51   uint8_t buf_[BROTLI_IBUF_SIZE];
  52   uint8_t*    buf_ptr_;      /* next input will write here */
  53   BrotliInput input_;        /* input callback */
  54 #if (BROTLI_USE_64_BITS)
  55   uint64_t    val_;          /* pre-fetched bits */
  56 #else
  57   uint32_t    val_;          /* pre-fetched bits */
  58 #endif
  59   uint32_t    pos_;          /* byte position in stream */
  60   uint32_t    bit_pos_;      /* current bit-reading position in val_ */
  61   uint32_t    bit_end_pos_;  /* bit-reading end position from LSB of val_ */
  62   int         eos_;          /* input stream is finished */
  63
  64   /* Set to 0 to support partial data streaming. Set to 1 to expect full data or
  65      for the last chunk of partial data. */
  66   int         finish_;
  67   /* indicates how much bytes already read when reading partial data */
  68   int         tmp_bytes_read_;
  69 } BrotliBitReader;
  70
  71 /* Initializes the bitreader fields. After this, BrotliWarmupBitReader must
  72    be used. */
  73 void BrotliInitBitReader(BrotliBitReader* const br,
  74                          BrotliInput input, int finish);
  75
  76 /* Fetches data to fill up internal buffers. Returns 0 if there wasn't enough */
  77 /* data to read. It then buffers the read data and can be called again with */
  78 /* more data. If br->finish_ is 1, never fails. */
  79 int BrotliWarmupBitReader(BrotliBitReader* const br);
  80
  81 /* Return the prefetched bits, so they can be looked up. */
  82 static BROTLI_INLINE uint32_t BrotliPrefetchBits(BrotliBitReader* const br) {
  83   return (uint32_t)(br->val_ >> br->bit_pos_);
  84 }
  85
  86 /* For jumping over a number of bits in the bit stream when accessed with */
  87 /* BrotliPrefetchBits and BrotliFillBitWindow. */
  88 static BROTLI_INLINE void BrotliSetBitPos(BrotliBitReader* const br,
  89                                           uint32_t val) {
  90 #ifdef BROTLI_DECODE_DEBUG
  91   uint32_t n_bits = val - br->bit_pos_;
  92   const uint32_t bval = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
  93   printf("[BrotliReadBits]  %010d %2d  val: %6x\n",
  94          (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, bval);
  95 #endif
  96   br->bit_pos_ = val;
  97 }
  98
  99 /*
 100  * Reload up to 32 bits byte-by-byte.
 101  * This function works on both little and big endian.
 102  */
 103 static BROTLI_INLINE void ShiftBytes32(BrotliBitReader* const br) {
 104   while (br->bit_pos_ >= 8) {
 105     br->val_ >>= 8;
 106     br->val_ |= ((uint32_t)br->buf_[br->pos_ & BROTLI_IBUF_MASK]) << 24;
 107     ++br->pos_;
 108     br->bit_pos_ -= 8;
 109     br->bit_end_pos_ -= 8;
 110   }
 111 }
 112
 113 /* Fills up the input ringbuffer by calling the input callback.
 114
 115    Does nothing if there are at least 32 bytes present after current position.
 116
 117    Returns 0 if one of:
 118     - the input callback returned an error, or
 119     - there is no more input and the position is past the end of the stream.
 120     - finish is false and less than BROTLI_READ_SIZE are available - a next call
 121       when more data is available makes it continue including the partially read
 122       data
 123
 124    After encountering the end of the input stream, 32 additional zero bytes are
 125    copied to the ringbuffer, therefore it is safe to call this function after
 126    every 32 bytes of input is read.
 127 */
 128 static BROTLI_INLINE int BrotliReadMoreInput(BrotliBitReader* const br) {
 129   if (br->bit_end_pos_ > 256) {
 130     return 1;
 131   } else if (br->eos_) {
 132     return br->bit_pos_ <= br->bit_end_pos_;
 133   } else {
 134     uint8_t* dst = br->buf_ptr_;
 135     int bytes_read = BrotliRead(br->input_, dst + br->tmp_bytes_read_,
 136         (size_t) (BROTLI_READ_SIZE - br->tmp_bytes_read_));
 137     if (bytes_read < 0) {
 138       return 0;
 139     }
 140     bytes_read += br->tmp_bytes_read_;
 141     br->tmp_bytes_read_ = 0;
 142     if (bytes_read < BROTLI_READ_SIZE) {
 143       if (!br->finish_) {
 144         br->tmp_bytes_read_ = bytes_read;
 145         return 0;
 146       }
 147       br->eos_ = 1;
 148       /* Store 32 bytes of zero after the stream end. */
 149 #if (BROTLI_USE_64_BITS)
 150       *(uint64_t*)(dst + bytes_read) = 0;
 151       *(uint64_t*)(dst + bytes_read + 8) = 0;
 152       *(uint64_t*)(dst + bytes_read + 16) = 0;
 153       *(uint64_t*)(dst + bytes_read + 24) = 0;
 154 #else
 155       memset(dst + bytes_read, 0, 32);
 156 #endif
 157     }
 158     if (dst == br->buf_) {
 159       /* Copy the head of the ringbuffer to the slack region. */
 160 #if (BROTLI_USE_64_BITS)
 161       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 32, br->buf_);
 162       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 24, br->buf_ + 8);
 163       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 16, br->buf_ + 16);
 164       UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 8, br->buf_ + 24);
 165 #else
 166       memcpy(br->buf_ + (BROTLI_READ_SIZE << 1), br->buf_, 32);
 167 #endif
 168       br->buf_ptr_ = br->buf_ + BROTLI_READ_SIZE;
 169     } else {
 170       br->buf_ptr_ = br->buf_;
 171     }
 172     br->bit_end_pos_ += ((uint32_t)bytes_read << 3);
 173     return 1;
 174   }
 175 }
 176
 177 /* Guarantees that there are at least 24 bits in the buffer. */
 178 static BROTLI_INLINE void BrotliFillBitWindow(BrotliBitReader* const br) {
 179 #if (BROTLI_USE_64_BITS)
 180   if (br->bit_pos_ >= 40) {
 181     /*
 182      * Advances the Read buffer by 5 bytes to make room for reading next
 183      * 24 bits.
 184      * The expression below needs a little-endian arch to work correctly.
 185      * This gives a large speedup for decoding speed.
 186      */
 187     br->val_ >>= 40;
 188     br->val_ |= *(const uint64_t*)(
 189         br->buf_ + (br->pos_ & BROTLI_IBUF_MASK)) << 24;
 190     br->pos_ += 5;
 191     br->bit_pos_ -= 40;
 192     br->bit_end_pos_ -= 40;
 193   }
 194 #else
 195   ShiftBytes32(br);
 196 #endif
 197 }
 198
 199 /* Reads the specified number of bits from Read Buffer. */
 200 static BROTLI_INLINE uint32_t BrotliReadBits(
 201     BrotliBitReader* const br, int n_bits) {
 202   uint32_t val;
 203 #if (BROTLI_USE_64_BITS)
 204   BrotliFillBitWindow(br);
 205   val = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
 206 #else
 207   /*
 208    * The if statement gives 2-4% speed boost on Canterbury data set with
 209    * asm.js/firefox/x86-64.
 210    */
 211   if ((32 - br->bit_pos_) < ((uint32_t) n_bits)) {
 212     BrotliFillBitWindow(br);
 213   }
 214   val = (br->val_ >> br->bit_pos_) & kBitMask[n_bits];
 215 #endif
 216 #ifdef BROTLI_DECODE_DEBUG
 217   printf("[BrotliReadBits]  %010d %2d  val: %6x\n",
 218          (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, val);
 219 #endif
 220   br->bit_pos_ += (uint32_t)n_bits;
 221   return val;
 222 }
 223
 224 #if defined(__cplusplus) || defined(c_plusplus)
 225 }    /* extern "C" */
 226 #endif
 227
 228 #endif  /* BROTLI_DEC_BIT_READER_H_ */