src/SDL2/external/libwebp-0.3.0/src/utils/bit_reader.h

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