libwebp: update snapshot to v0.3.0-rc6

third_party/libwebp/utils/bit_reader.h

 // Copyright 2010 Google Inc. All Rights Reserved.
 //
 // This code is licensed under the same terms as WebM:
 //  Software License Agreement:  http://www.webmproject.org/license/software/
 //  Additional IP Rights Grant:  http://www.webmproject.org/license/additional/
 // -----------------------------------------------------------------------------
 //
 // Boolean decoder
 //
 // Author: Skal (pascal.massimino@gmail.com)
 //         Vikas Arora (vikaas.arora@gmail.com)
 
 #ifndef WEBP_UTILS_BIT_READER_H_
 #define WEBP_UTILS_BIT_READER_H_
 
 #include <assert.h>
 #ifdef _MSC_VER
 #include <stdlib.h>  // _byteswap_ulong
 #endif
 #include <string.h>  // For memcpy
 #include "../webp/types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
-#define BITS 32     // can be 32, 16 or 8
-#define MASK ((((bit_t)1) << (BITS)) - 1)
-#if (BITS == 32)
-typedef uint64_t bit_t;   // natural register type
-typedef uint32_t lbit_t;  // natural type for memory I/O
+// The Boolean decoder needs to maintain infinite precision on the value_ field.
+// However, since range_ is only 8bit, we only need an active window of 8 bits
+// for value_. Left bits (MSB) gets zeroed and shifted away when value_ falls
+// below 128, range_ is updated, and fresh bits read from the bitstream are
+// brought in as LSB.
+// To avoid reading the fresh bits one by one (slow), we cache a few of them
+// ahead (actually, we cache BITS of them ahead. See below). There's two
+// strategies regarding how to shift these looked-ahead fresh bits into the
+// 8bit window of value_: either we shift them in, while keeping the position of
+// the window fixed. Or we slide the window to the right while keeping the cache
+// bits at a fixed, right-justified, position.
+//
+//  Example, for BITS=16: here is the content of value_ for both strategies:
+//
+//          !USE_RIGHT_JUSTIFY            ||        USE_RIGHT_JUSTIFY
+//                                        ||
+//   <- 8b -><- 8b -><- BITS bits  ->     ||  <- 8b+3b -><- 8b -><- 13 bits ->
+//   [unused][value_][cached bits][0]     ||  [unused...][value_][cached bits]
+//  [........00vvvvvvBBBBBBBBBBBBB000]LSB || [...........00vvvvvvBBBBBBBBBBBBB]
+//                                        ||
+// After calling VP8Shift(), where we need to shift away two zeros:
+//  [........vvvvvvvvBBBBBBBBBBB00000]LSB || [.............vvvvvvvvBBBBBBBBBBB]
+//                                        ||
+// Just before we need to call VP8LoadNewBytes(), the situation is:
+//  [........vvvvvv000000000000000000]LSB || [..........................vvvvvv]
+//                                        ||
+// And just after calling VP8LoadNewBytes():
+//  [........vvvvvvvvBBBBBBBBBBBBBBBB]LSB || [........vvvvvvvvBBBBBBBBBBBBBBBB]
+//
+// -> we're back to height active 'value_' bits (marked 'v') and BITS cached
+// bits (marked 'B')
+//
+// The right-justify strategy tends to use less shifts and is often faster.
+
+//------------------------------------------------------------------------------
+// BITS can be any multiple of 8 from 8 to 56 (inclusive).
+// Pick values that fit natural register size.
+
+#if !defined(WEBP_REFERENCE_IMPLEMENTATION)
+
+#define USE_RIGHT_JUSTIFY
+
+#if defined(__i386__) || defined(_M_IX86)      // x86 32bit
+#define BITS 16
+#elif defined(__x86_64__) || defined(_M_X64)   // x86 64bit
+#define BITS 56
+#elif defined(__arm__) || defined(_M_ARM)      // ARM
+#define BITS 24
+#else                      // reasonable default
+#define BITS 24
+#endif
+
+#else     // reference choices
+
+#define USE_RIGHT_JUSTIFY
+#define BITS 8
+
+#endif
+
+//------------------------------------------------------------------------------
+// Derived types and constants
+
+// bit_t = natural register type
+// lbit_t = natural type for memory I/O
+
+#if (BITS > 32)
+typedef uint64_t bit_t;
+typedef uint64_t lbit_t;
+#elif (BITS == 32)
+typedef uint64_t bit_t;
+typedef uint32_t lbit_t;
+#elif (BITS == 24)
+typedef uint32_t bit_t;
+typedef uint32_t lbit_t;
 #elif (BITS == 16)
 typedef uint32_t bit_t;
 typedef uint16_t lbit_t;
 #else
 typedef uint32_t bit_t;
 typedef uint8_t lbit_t;
 #endif
 
+#ifndef USE_RIGHT_JUSTIFY
+typedef bit_t range_t;     // type for storing range_
+#define MASK ((((bit_t)1) << (BITS)) - 1)
+#else
+typedef uint32_t range_t;  // range_ only uses 8bits here. No need for bit_t.
+#endif
+
 //------------------------------------------------------------------------------
-// Bitreader and code-tree reader
+// Bitreader
 
 typedef struct VP8BitReader VP8BitReader;
 struct VP8BitReader {
   const uint8_t* buf_;        // next byte to be read
   const uint8_t* buf_end_;    // end of read buffer
   int eof_;                   // true if input is exhausted
 
   // boolean decoder
-  bit_t range_;            // current range minus 1. In [127, 254] interval.
-  bit_t value_;            // current value
-  int missing_;            // number of missing bits in value_ (8bit)
+  range_t range_;            // current range minus 1. In [127, 254] interval.
+  bit_t value_;              // current value
+  int bits_;                 // number of valid bits left
 };
 
 // Initialize the bit reader and the boolean decoder.
 void VP8InitBitReader(VP8BitReader* const br,
                       const uint8_t* const start, const uint8_t* const end);
 
 // return the next value made of 'num_bits' bits
 uint32_t VP8GetValue(VP8BitReader* const br, int num_bits);
 static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
   return VP8GetValue(br, 1);
 }
 
 // return the next value with sign-extension.
 int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits);
 
 // Read a bit with proba 'prob'. Speed-critical function!
 extern const uint8_t kVP8Log2Range[128];
-extern const bit_t kVP8NewRange[128];
+extern const range_t kVP8NewRange[128];
 
 void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
 
 static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) {
-  assert(br && br->buf_);
+  assert(br != NULL && br->buf_ != NULL);
   // Read 'BITS' bits at a time if possible.
   if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) {
     // convert memory type to register type (with some zero'ing!)
     bit_t bits;
     lbit_t in_bits = *(lbit_t*)br->buf_;
     br->buf_ += (BITS) >> 3;
 #if !defined(__BIG_ENDIAN__)
-#if (BITS == 32)
+#if (BITS > 32)
+// gcc 4.3 has builtin functions for swap32/swap64
+#if defined(__GNUC__) && \
+           (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3))
+    bits = (bit_t)__builtin_bswap64(in_bits);
+#elif defined(_MSC_VER)
+    bits = (bit_t)_byteswap_uint64(in_bits);
+#elif defined(__x86_64__)
+    __asm__ volatile("bswapq %0" : "=r"(bits) : "0"(in_bits));
+#else  // generic code for swapping 64-bit values (suggested by bdb@)
+    bits = (bit_t)in_bits;
+    bits = ((bits & 0xffffffff00000000ull) >> 32) |
+           ((bits & 0x00000000ffffffffull) << 32);
+    bits = ((bits & 0xffff0000ffff0000ull) >> 16) |
+           ((bits & 0x0000ffff0000ffffull) << 16);
+    bits = ((bits & 0xff00ff00ff00ff00ull) >> 8) |
+           ((bits & 0x00ff00ff00ff00ffull) << 8);
+#endif
+    bits >>= 64 - BITS;
+#elif (BITS >= 24)
 #if defined(__i386__) || defined(__x86_64__)
     __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits));
-    bits = (bit_t)in_bits;   // 32b -> 64b zero-extension
+    bits = (bit_t)in_bits;   // 24b/32b -> 32b/64b zero-extension
 #elif defined(_MSC_VER)
-    bits = _byteswap_ulong(in_bits);
+    bits = (bit_t)_byteswap_ulong(in_bits);
 #else
     bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00)
          | ((in_bits << 8) & 0xff0000)  | (in_bits << 24);
 #endif  // x86
+    bits >>= (32 - BITS);
 #elif (BITS == 16)
     // gcc will recognize a 'rorw $8, ...' here:
     bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8);
-#endif
-#else    // LITTLE_ENDIAN
+#else   // BITS == 8
     bits = (bit_t)in_bits;
 #endif
-    br->value_ |= bits << br->missing_;
-    br->missing_ -= (BITS);
+#else    // BIG_ENDIAN
+    bits = (bit_t)in_bits;
+#endif
+#ifndef USE_RIGHT_JUSTIFY
+    br->value_ |= bits << (-br->bits_);
+#else
+    br->value_ = bits | (br->value_ << (BITS));
+#endif
+    br->bits_ += (BITS);
   } else {
     VP8LoadFinalBytes(br);    // no need to be inlined
   }
 }
 
-static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, bit_t split) {
-  const bit_t value_split = split | (MASK);
-  if (br->missing_ > 0) {  // Make sure we have a least BITS bits in 'value_'
+static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, range_t split) {
+  if (br->bits_ < 0) {  // Make sure we have a least BITS bits in 'value_'
     VP8LoadNewBytes(br);
   }
-  if (br->value_ > value_split) {
-    br->range_ -= value_split + 1;
-    br->value_ -= value_split + 1;
+#ifndef USE_RIGHT_JUSTIFY
+  split |= (MASK);
+  if (br->value_ > split) {
+    br->range_ -= split + 1;
+    br->value_ -= split + 1;
     return 1;
   } else {
-    br->range_ = value_split;
+    br->range_ = split;
     return 0;
   }
+#else
+  {
+    const int pos = br->bits_;
+    const range_t value = (range_t)(br->value_ >> pos);
+    if (value > split) {
+      br->range_ -= split + 1;
+      br->value_ -= (bit_t)(split + 1) << pos;
+      return 1;
+    } else {
+      br->range_ = split;
+      return 0;
+    }
+  }
+#endif
 }
 
 static WEBP_INLINE void VP8Shift(VP8BitReader* const br) {
+#ifndef USE_RIGHT_JUSTIFY
   // range_ is in [0..127] interval here.
-  const int idx = br->range_ >> (BITS);
+  const bit_t idx = br->range_ >> (BITS);
   const int shift = kVP8Log2Range[idx];
   br->range_ = kVP8NewRange[idx];
   br->value_ <<= shift;
-  br->missing_ += shift;
+  br->bits_ -= shift;
+#else
+  const int shift = kVP8Log2Range[br->range_];
+  assert(br->range_ < (range_t)128);
+  br->range_ = kVP8NewRange[br->range_];
+  br->bits_ -= shift;
+#endif
 }
-
 static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) {
+#ifndef USE_RIGHT_JUSTIFY
   // It's important to avoid generating a 64bit x 64bit multiply here.
   // We just need an 8b x 8b after all.
-  const bit_t split =
-      (bit_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8);
+  const range_t split =
+      (range_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8);
   const int bit = VP8BitUpdate(br, split);
-  if (br->range_ <= (((bit_t)0x7e << (BITS)) | (MASK))) {
+  if (br->range_ <= (((range_t)0x7e << (BITS)) | (MASK))) {
     VP8Shift(br);
   }
   return bit;
+#else
+  const range_t split = (br->range_ * prob) >> 8;
+  const int bit = VP8BitUpdate(br, split);
+  if (br->range_ <= (range_t)0x7e) {
+    VP8Shift(br);
+  }
+  return bit;
+#endif
 }
 
 static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) {
-  const bit_t split = (br->range_ >> 1);
+  const range_t split = (br->range_ >> 1);
   const int bit = VP8BitUpdate(br, split);
   VP8Shift(br);
   return bit ? -v : v;
 }
 
 
 // -----------------------------------------------------------------------------
-// Bitreader
+// Bitreader for lossless format
+
+typedef uint64_t vp8l_val_t;  // right now, this bit-reader can only use 64bit.
 
 typedef struct {
-  uint64_t       val_;
-  const uint8_t* buf_;
-  size_t         len_;
-  size_t         pos_;
-  int            bit_pos_;
-  int            eos_;
-  int            error_;
+  vp8l_val_t     val_;        // pre-fetched bits
+  const uint8_t* buf_;        // input byte buffer
+  size_t         len_;        // buffer length
+  size_t         pos_;        // byte position in buf_
+  int            bit_pos_;    // current bit-reading position in val_
+  int            eos_;        // bitstream is finished
+  int            error_;      // an error occurred (buffer overflow attempt...)
 } VP8LBitReader;
 
 void VP8LInitBitReader(VP8LBitReader* const br,
                        const uint8_t* const start,
                        size_t length);
 
 //  Sets a new data buffer.
 void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
                             const uint8_t* const buffer, size_t length);
 
 // Reads the specified number of bits from Read Buffer.
 // Flags an error in case end_of_stream or n_bits is more than allowed limit.
 // Flags eos if this read attempt is going to cross the read buffer.
 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits);
 
-// Reads one bit from Read Buffer. Flags an error in case end_of_stream.
-// Flags eos after reading last bit from the buffer.
-uint32_t VP8LReadOneBit(VP8LBitReader* const br);
+// Return the prefetched bits, so they can be looked up.
+static WEBP_INLINE uint32_t VP8LPrefetchBits(VP8LBitReader* const br) {
+  return (uint32_t)(br->val_ >> br->bit_pos_);
+}
 
-// VP8LReadOneBitUnsafe is faster than VP8LReadOneBit, but it can be called only
-// 32 times after the last VP8LFillBitWindow. Any subsequent calls
-// (without VP8LFillBitWindow) will return invalid data.
-static WEBP_INLINE uint32_t VP8LReadOneBitUnsafe(VP8LBitReader* const br) {
-  const uint32_t val = (br->val_ >> br->bit_pos_) & 1;
-  ++br->bit_pos_;
-  return val;
+// Discard 'num_bits' bits from the cache.
+static WEBP_INLINE void VP8LDiscardBits(VP8LBitReader* const br, int num_bits) {
+  br->bit_pos_ += num_bits;
 }
 
 // Advances the Read buffer by 4 bytes to make room for reading next 32 bits.
 void VP8LFillBitWindow(VP8LBitReader* const br);
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    // extern "C"
 #endif
 
 #endif  /* WEBP_UTILS_BIT_READER_H_ */