third_party/libwebp/utils/bit_reader.h

   1 // Copyright 2010 Google Inc. All Rights Reserved.
   2 //
   3 // Use of this source code is governed by a BSD-style license
   4 // that can be found in the COPYING file in the root of the source
   5 // tree. An additional intellectual property rights grant can be found
   6 // in the file PATENTS. All contributing project authors may
   7 // be found in the AUTHORS file in the root of the source tree.
   8 // -----------------------------------------------------------------------------
   9 //
  10 // Boolean decoder
  11 //
  12 // Author: Skal (pascal.massimino@gmail.com)
  13 //         Vikas Arora (vikaas.arora@gmail.com)
  14
  15 #ifndef WEBP_UTILS_BIT_READER_H_
  16 #define WEBP_UTILS_BIT_READER_H_
  17
  18 #include <assert.h>
  19 #ifdef _MSC_VER
  20 #include <stdlib.h>  // _byteswap_ulong
  21 #endif
  22 #include <string.h>  // For memcpy
  23 #include "../webp/types.h"
  24
  25 #if defined(__cplusplus) || defined(c_plusplus)
  26 extern "C" {
  27 #endif
  28
  29 // The Boolean decoder needs to maintain infinite precision on the value_ field.
  30 // However, since range_ is only 8bit, we only need an active window of 8 bits
  31 // for value_. Left bits (MSB) gets zeroed and shifted away when value_ falls
  32 // below 128, range_ is updated, and fresh bits read from the bitstream are
  33 // brought in as LSB.
  34 // To avoid reading the fresh bits one by one (slow), we cache a few of them
  35 // ahead (actually, we cache BITS of them ahead. See below). There's two
  36 // strategies regarding how to shift these looked-ahead fresh bits into the
  37 // 8bit window of value_: either we shift them in, while keeping the position of
  38 // the window fixed. Or we slide the window to the right while keeping the cache
  39 // bits at a fixed, right-justified, position.
  40 //
  41 //  Example, for BITS=16: here is the content of value_ for both strategies:
  42 //
  43 //          !USE_RIGHT_JUSTIFY            ||        USE_RIGHT_JUSTIFY
  44 //                                        ||
  45 //   <- 8b -><- 8b -><- BITS bits  ->     ||  <- 8b+3b -><- 8b -><- 13 bits ->
  46 //   [unused][value_][cached bits][0]     ||  [unused...][value_][cached bits]
  47 //  [........00vvvvvvBBBBBBBBBBBBB000]LSB || [...........00vvvvvvBBBBBBBBBBBBB]
  48 //                                        ||
  49 // After calling VP8Shift(), where we need to shift away two zeros:
  50 //  [........vvvvvvvvBBBBBBBBBBB00000]LSB || [.............vvvvvvvvBBBBBBBBBBB]
  51 //                                        ||
  52 // Just before we need to call VP8LoadNewBytes(), the situation is:
  53 //  [........vvvvvv000000000000000000]LSB || [..........................vvvvvv]
  54 //                                        ||
  55 // And just after calling VP8LoadNewBytes():
  56 //  [........vvvvvvvvBBBBBBBBBBBBBBBB]LSB || [........vvvvvvvvBBBBBBBBBBBBBBBB]
  57 //
  58 // -> we're back to height active 'value_' bits (marked 'v') and BITS cached
  59 // bits (marked 'B')
  60 //
  61 // The right-justify strategy tends to use less shifts and is often faster.
  62
  63 //------------------------------------------------------------------------------
  64 // BITS can be any multiple of 8 from 8 to 56 (inclusive).
  65 // Pick values that fit natural register size.
  66
  67 #if !defined(WEBP_REFERENCE_IMPLEMENTATION)
  68
  69 #define USE_RIGHT_JUSTIFY
  70
  71 #if defined(__i386__) || defined(_M_IX86)      // x86 32bit
  72 #define BITS 16
  73 #elif defined(__x86_64__) || defined(_M_X64)   // x86 64bit
  74 #define BITS 56
  75 #elif defined(__arm__) || defined(_M_ARM)      // ARM
  76 #define BITS 24
  77 #else                      // reasonable default
  78 #define BITS 24
  79 #endif
  80
  81 #else     // reference choices
  82
  83 #define USE_RIGHT_JUSTIFY
  84 #define BITS 8
  85
  86 #endif
  87
  88 //------------------------------------------------------------------------------
  89 // Derived types and constants
  90
  91 // bit_t = natural register type
  92 // lbit_t = natural type for memory I/O
  93
  94 #if (BITS > 32)
  95 typedef uint64_t bit_t;
  96 typedef uint64_t lbit_t;
  97 #elif (BITS == 32)
  98 typedef uint64_t bit_t;
  99 typedef uint32_t lbit_t;
 100 #elif (BITS == 24)
 101 typedef uint32_t bit_t;
 102 typedef uint32_t lbit_t;
 103 #elif (BITS == 16)
 104 typedef uint32_t bit_t;
 105 typedef uint16_t lbit_t;
 106 #else
 107 typedef uint32_t bit_t;
 108 typedef uint8_t lbit_t;
 109 #endif
 110
 111 #ifndef USE_RIGHT_JUSTIFY
 112 typedef bit_t range_t;     // type for storing range_
 113 #define MASK ((((bit_t)1) << (BITS)) - 1)
 114 #else
 115 typedef uint32_t range_t;  // range_ only uses 8bits here. No need for bit_t.
 116 #endif
 117
 118 //------------------------------------------------------------------------------
 119 // Bitreader
 120
 121 typedef struct VP8BitReader VP8BitReader;
 122 struct VP8BitReader {
 123   const uint8_t* buf_;        // next byte to be read
 124   const uint8_t* buf_end_;    // end of read buffer
 125   int eof_;                   // true if input is exhausted
 126
 127   // boolean decoder
 128   range_t range_;            // current range minus 1. In [127, 254] interval.
 129   bit_t value_;              // current value
 130   int bits_;                 // number of valid bits left
 131 };
 132
 133 // Initialize the bit reader and the boolean decoder.
 134 void VP8InitBitReader(VP8BitReader* const br,
 135                       const uint8_t* const start, const uint8_t* const end);
 136
 137 // return the next value made of 'num_bits' bits
 138 uint32_t VP8GetValue(VP8BitReader* const br, int num_bits);
 139 static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
 140   return VP8GetValue(br, 1);
 141 }
 142
 143 // return the next value with sign-extension.
 144 int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits);
 145
 146 // Read a bit with proba 'prob'. Speed-critical function!
 147 extern const uint8_t kVP8Log2Range[128];
 148 extern const range_t kVP8NewRange[128];
 149
 150 void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
 151
 152 static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) {
 153   assert(br != NULL && br->buf_ != NULL);
 154   // Read 'BITS' bits at a time if possible.
 155   if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) {
 156     // convert memory type to register type (with some zero'ing!)
 157     bit_t bits;
 158     lbit_t in_bits = *(lbit_t*)br->buf_;
 159     br->buf_ += (BITS) >> 3;
 160 #if !defined(__BIG_ENDIAN__)
 161 #if (BITS > 32)
 162 // gcc 4.3 has builtin functions for swap32/swap64
 163 #if defined(__GNUC__) && \
 164            (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3))
 165     bits = (bit_t)__builtin_bswap64(in_bits);
 166 #elif defined(_MSC_VER)
 167     bits = (bit_t)_byteswap_uint64(in_bits);
 168 #elif defined(__x86_64__)
 169     __asm__ volatile("bswapq %0" : "=r"(bits) : "0"(in_bits));
 170 #else  // generic code for swapping 64-bit values (suggested by bdb@)
 171     bits = (bit_t)in_bits;
 172     bits = ((bits & 0xffffffff00000000ull) >> 32) |
 173            ((bits & 0x00000000ffffffffull) << 32);
 174     bits = ((bits & 0xffff0000ffff0000ull) >> 16) |
 175            ((bits & 0x0000ffff0000ffffull) << 16);
 176     bits = ((bits & 0xff00ff00ff00ff00ull) >> 8) |
 177            ((bits & 0x00ff00ff00ff00ffull) << 8);
 178 #endif
 179     bits >>= 64 - BITS;
 180 #elif (BITS >= 24)
 181 #if defined(__i386__) || defined(__x86_64__)
 182     __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits));
 183     bits = (bit_t)in_bits;   // 24b/32b -> 32b/64b zero-extension
 184 #elif defined(_MSC_VER)
 185     bits = (bit_t)_byteswap_ulong(in_bits);
 186 #else
 187     bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00)
 188          | ((in_bits << 8) & 0xff0000)  | (in_bits << 24);
 189 #endif  // x86
 190     bits >>= (32 - BITS);
 191 #elif (BITS == 16)
 192     // gcc will recognize a 'rorw $8, ...' here:
 193     bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8);
 194 #else   // BITS == 8
 195     bits = (bit_t)in_bits;
 196 #endif
 197 #else    // BIG_ENDIAN
 198     bits = (bit_t)in_bits;
 199     if (BITS != 8 * sizeof(bit_t)) bits >>= (8 * sizeof(bit_t) - BITS);
 200 #endif
 201 #ifndef USE_RIGHT_JUSTIFY
 202     br->value_ |= bits << (-br->bits_);
 203 #else
 204     br->value_ = bits | (br->value_ << (BITS));
 205 #endif
 206     br->bits_ += (BITS);
 207   } else {
 208     VP8LoadFinalBytes(br);    // no need to be inlined
 209   }
 210 }
 211
 212 static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, range_t split) {
 213   if (br->bits_ < 0) {  // Make sure we have a least BITS bits in 'value_'
 214     VP8LoadNewBytes(br);
 215   }
 216 #ifndef USE_RIGHT_JUSTIFY
 217   split |= (MASK);
 218   if (br->value_ > split) {
 219     br->range_ -= split + 1;
 220     br->value_ -= split + 1;
 221     return 1;
 222   } else {
 223     br->range_ = split;
 224     return 0;
 225   }
 226 #else
 227   {
 228     const int pos = br->bits_;
 229     const range_t value = (range_t)(br->value_ >> pos);
 230     if (value > split) {
 231       br->range_ -= split + 1;
 232       br->value_ -= (bit_t)(split + 1) << pos;
 233       return 1;
 234     } else {
 235       br->range_ = split;
 236       return 0;
 237     }
 238   }
 239 #endif
 240 }
 241
 242 static WEBP_INLINE void VP8Shift(VP8BitReader* const br) {
 243 #ifndef USE_RIGHT_JUSTIFY
 244   // range_ is in [0..127] interval here.
 245   const bit_t idx = br->range_ >> (BITS);
 246   const int shift = kVP8Log2Range[idx];
 247   br->range_ = kVP8NewRange[idx];
 248   br->value_ <<= shift;
 249   br->bits_ -= shift;
 250 #else
 251   const int shift = kVP8Log2Range[br->range_];
 252   assert(br->range_ < (range_t)128);
 253   br->range_ = kVP8NewRange[br->range_];
 254   br->bits_ -= shift;
 255 #endif
 256 }
 257 static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) {
 258 #ifndef USE_RIGHT_JUSTIFY
 259   // It's important to avoid generating a 64bit x 64bit multiply here.
 260   // We just need an 8b x 8b after all.
 261   const range_t split =
 262       (range_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8);
 263   const int bit = VP8BitUpdate(br, split);
 264   if (br->range_ <= (((range_t)0x7e << (BITS)) | (MASK))) {
 265     VP8Shift(br);
 266   }
 267   return bit;
 268 #else
 269   const range_t split = (br->range_ * prob) >> 8;
 270   const int bit = VP8BitUpdate(br, split);
 271   if (br->range_ <= (range_t)0x7e) {
 272     VP8Shift(br);
 273   }
 274   return bit;
 275 #endif
 276 }
 277
 278 static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) {
 279   const range_t split = (br->range_ >> 1);
 280   const int bit = VP8BitUpdate(br, split);
 281   VP8Shift(br);
 282   return bit ? -v : v;
 283 }
 284
 285
 286 // -----------------------------------------------------------------------------
 287 // Bitreader for lossless format
 288
 289 typedef uint64_t vp8l_val_t;  // right now, this bit-reader can only use 64bit.
 290
 291 typedef struct {
 292   vp8l_val_t     val_;        // pre-fetched bits
 293   const uint8_t* buf_;        // input byte buffer
 294   size_t         len_;        // buffer length
 295   size_t         pos_;        // byte position in buf_
 296   int            bit_pos_;    // current bit-reading position in val_
 297   int            eos_;        // bitstream is finished
 298   int            error_;      // an error occurred (buffer overflow attempt...)
 299 } VP8LBitReader;
 300
 301 void VP8LInitBitReader(VP8LBitReader* const br,
 302                        const uint8_t* const start,
 303                        size_t length);
 304
 305 //  Sets a new data buffer.
 306 void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
 307                             const uint8_t* const buffer, size_t length);
 308
 309 // Reads the specified number of bits from Read Buffer.
 310 // Flags an error in case end_of_stream or n_bits is more than allowed limit.
 311 // Flags eos if this read attempt is going to cross the read buffer.
 312 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits);
 313
 314 // Return the prefetched bits, so they can be looked up.
 315 static WEBP_INLINE uint32_t VP8LPrefetchBits(VP8LBitReader* const br) {
 316   return (uint32_t)(br->val_ >> br->bit_pos_);
 317 }
 318
 319 // Discard 'num_bits' bits from the cache.
 320 static WEBP_INLINE void VP8LDiscardBits(VP8LBitReader* const br, int num_bits) {
 321   br->bit_pos_ += num_bits;
 322 }
 323
 324 // Advances the Read buffer by 4 bytes to make room for reading next 32 bits.
 325 void VP8LFillBitWindow(VP8LBitReader* const br);
 326
 327 #if defined(__cplusplus) || defined(c_plusplus)
 328 }    // extern "C"
 329 #endif
 330
 331 #endif  /* WEBP_UTILS_BIT_READER_H_ */