libwebp: update to 0.4.1

third_party/libwebp/utils/bit_reader.h

Index: third_party/libwebp/utils/bit_reader.h
diff --git a/third_party/libwebp/utils/bit_reader.h b/third_party/libwebp/utils/bit_reader.h
index 98df98a7678648c1347ba8fad564bb8fa33b2924..2c9766ebccdda0eb2d501459e4d8a9d57709a9fd 100644
--- a/third_party/libwebp/utils/bit_reader.h
+++ b/third_party/libwebp/utils/bit_reader.h
@@ -29,110 +29,62 @@ extern "C" {
 // 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.
+// brought in as LSB. To avoid reading the fresh bits one by one (slow), we
+// cache BITS of them ahead. The total of (BITS + 8) bits must fit into a
+// natural register (with type bit_t). To fetch BITS bits from bitstream we
+// use a type lbit_t.
 //
-//  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 eight 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
+#define BITS 24
 #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
+#elif defined(__mips__)                        // MIPS
 #define BITS 24
-#endif
-
-#else     // reference choices
-
-#define USE_RIGHT_JUSTIFY
-#define BITS 8
-
+#else                                          // reasonable default
+#define BITS 24  // TODO(skal): test aarch64 and find the proper BITS value.
 #endif
 
 //------------------------------------------------------------------------------
-// Derived types and constants
-
-// bit_t = natural register type
-// lbit_t = natural type for memory I/O
+// Derived types and constants:
+//   bit_t = natural register type for storing 'value_' (which is BITS+8 bits)
+//   range_t = register for 'range_' (which is 8bits only)
 
-#if (BITS > 32)
-typedef uint64_t bit_t;
-typedef uint64_t lbit_t;
-#elif (BITS == 32)
+#if (BITS > 24)
 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
+typedef uint32_t range_t;
 
 //------------------------------------------------------------------------------
 // Bitreader
 
 typedef struct VP8BitReader VP8BitReader;
 struct VP8BitReader {
+  // boolean decoder  (keep the field ordering as is!)
+  bit_t value_;               // current value
+  range_t range_;             // current range minus 1. In [127, 254] interval.
+  int bits_;                  // number of valid bits left
+  // read buffer
   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
-  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);
 
+// Update internal pointers to displace the byte buffer by the
+// relative offset 'offset'.
+void VP8RemapBitReader(VP8BitReader* const br, ptrdiff_t offset);
+
 // 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) {
@@ -142,152 +94,19 @@ static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
 // 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 range_t kVP8NewRange[128];
-
-void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
-
-static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) {
-  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;
-    const lbit_t in_bits = *(const lbit_t*)br->buf_;
-    br->buf_ += (BITS) >> 3;
-#if !defined(__BIG_ENDIAN__)
-#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__)
-    {
-      lbit_t swapped_in_bits;
-      __asm__ volatile("bswap %k0" : "=r"(swapped_in_bits) : "0"(in_bits));
-      bits = (bit_t)swapped_in_bits;   // 24b/32b -> 32b/64b zero-extension
-    }
-#elif defined(_MSC_VER)
-    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);
-#else   // BITS == 8
-    bits = (bit_t)in_bits;
-#endif
-#else    // BIG_ENDIAN
-    bits = (bit_t)in_bits;
-    if (BITS != 8 * sizeof(bit_t)) bits >>= (8 * sizeof(bit_t) - 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, range_t split) {
-  if (br->bits_ < 0) {  // Make sure we have a least BITS bits in 'value_'
-    VP8LoadNewBytes(br);
-  }
-#ifndef USE_RIGHT_JUSTIFY
-  split |= (MASK);
-  if (br->value_ > split) {
-    br->range_ -= split + 1;
-    br->value_ -= split + 1;
-    return 1;
-  } else {
-    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 bit_t idx = br->range_ >> (BITS);
-  const int shift = kVP8Log2Range[idx];
-  br->range_ = kVP8NewRange[idx];
-  br->value_ <<= 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 range_t split =
-      (range_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8);
-  const int bit = VP8BitUpdate(br, split);
-  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 range_t split = (br->range_ >> 1);
-  const int bit = VP8BitUpdate(br, split);
-  VP8Shift(br);
-  return bit ? -v : v;
-}
+// bit_reader_inl.h will implement the following methods:
+//   static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob)
+//   static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v)
+// and should be included by the .c files that actually need them.
+// This is to avoid recompiling the whole library whenever this file is touched,
+// and also allowing platform-specific ad-hoc hacks.
 
 // -----------------------------------------------------------------------------
 // Bitreader for lossless format
 
+// maximum number of bits (inclusive) the bit-reader can handle:
+#define VP8L_MAX_NUM_BIT_READ 24
+
 typedef uint64_t vp8l_val_t;  // right now, this bit-reader can only use 64bit.
 
 typedef struct {
@@ -308,9 +127,10 @@ void VP8LInitBitReader(VP8LBitReader* const br,
 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.
+// Reads the specified number of bits from read buffer.
+// Flags an error in case end_of_stream or n_bits is more than the allowed limit
+// of VP8L_MAX_NUM_BIT_READ (inclusive).
+// Flags eos_ if this read attempt is going to cross the read buffer.
 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits);
 
 // Return the prefetched bits, so they can be looked up.