Update third_party/base/bits.h.

Pick up https://crrev.com/515947 and https://crrev.com/542972

Change-Id: Idccd388ee2f9cc71ace7ed5f598c820754e87b6e
Reviewed-on: https://pdfium-review.googlesource.com/32631
Commit-Queue: Ryan Harrison <rharrison@chromium.org>
Reviewed-by: Ryan Harrison <rharrison@chromium.org>

1 files changed, 107 insertions, 49 deletions

diff --git a/third_party/base/bits.h b/third_party/base/bits.h
index 220be4b73c..ac40dc6ce4 100644
--- a/third_party/base/bits.h
+++ b/third_party/base/bits.h
@@ -21,91 +21,149 @@ namespace pdfium {
 namespace base {
 namespace bits {
 
-// Returns the integer i such as 2^i <= n < 2^(i+1)
-inline int Log2Floor(uint32_t n) {
-  if (n == 0)
-    return -1;
-  int log = 0;
-  uint32_t value = n;
-  for (int i = 4; i >= 0; --i) {
-    int shift = (1 << i);
-    uint32_t x = value >> shift;
-    if (x != 0) {
-      value = x;
-      log += shift;
-    }
-  }
-  DCHECK_EQ(value, 1u);
-  return log;
-}
-
-// Returns the integer i such as 2^(i-1) < n <= 2^i
-inline int Log2Ceiling(uint32_t n) {
-  if (n == 0) {
-    return -1;
-  } else {
-    // Log2Floor returns -1 for 0, so the following works correctly for n=1.
-    return 1 + Log2Floor(n - 1);
-  }
-}
-
 // Round up |size| to a multiple of alignment, which must be a power of two.
 inline size_t Align(size_t size, size_t alignment) {
   DCHECK_EQ(alignment & (alignment - 1), 0u);
   return (size + alignment - 1) & ~(alignment - 1);
 }
 
-// These functions count the number of leading zeros in a binary value, starting
-// with the most significant bit. C does not have an operator to do this, but
-// fortunately the various compilers have built-ins that map to fast underlying
-// processor instructions.
+// CountLeadingZeroBits(value) returns the number of zero bits following the
+// most significant 1 bit in |value| if |value| is non-zero, otherwise it
+// returns {sizeof(T) * 8}.
+// Example: 00100010 -> 2
+//
+// CountTrailingZeroBits(value) returns the number of zero bits preceding the
+// least significant 1 bit in |value| if |value| is non-zero, otherwise it
+// returns {sizeof(T) * 8}.
+// Example: 00100010 -> 1
+//
+// C does not have an operator to do this, but fortunately the various
+// compilers have built-ins that map to fast underlying processor instructions.
 #if defined(COMPILER_MSVC)
 
-ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
+template <typename T, unsigned bits = sizeof(T) * 8>
+ALWAYS_INLINE
+    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4,
+                            unsigned>::type
+    CountLeadingZeroBits(T x) {
+  static_assert(bits > 0, "invalid instantiation");
   unsigned long index;
-  return LIKELY(_BitScanReverse(&index, x)) ? (31 - index) : 32;
+  return LIKELY(_BitScanReverse(&index, static_cast<uint32_t>(x)))
+             ? (31 - index - (32 - bits))
+             : bits;
+}
+
+template <typename T, unsigned bits = sizeof(T) * 8>
+ALWAYS_INLINE
+    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8,
+                            unsigned>::type
+    CountLeadingZeroBits(T x) {
+  static_assert(bits > 0, "invalid instantiation");
+  unsigned long index;
+  return LIKELY(_BitScanReverse64(&index, static_cast<uint64_t>(x)))
+             ? (63 - index)
+             : 64;
+}
+
+template <typename T, unsigned bits = sizeof(T) * 8>
+ALWAYS_INLINE
+    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4,
+                            unsigned>::type
+    CountTrailingZeroBits(T x) {
+  static_assert(bits > 0, "invalid instantiation");
+  unsigned long index;
+  return LIKELY(_BitScanForward(&index, static_cast<uint32_t>(x))) ? index
+                                                                   : bits;
+}
+
+template <typename T, unsigned bits = sizeof(T) * 8>
+ALWAYS_INLINE
+    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8,
+                            unsigned>::type
+    CountTrailingZeroBits(T x) {
+  static_assert(bits > 0, "invalid instantiation");
+  unsigned long index;
+  return LIKELY(_BitScanForward64(&index, static_cast<uint64_t>(x))) ? index
+                                                                     : 64;
+}
+
+ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
+  return CountLeadingZeroBits(x);
 }
 
 #if defined(ARCH_CPU_64_BITS)
 
 // MSVC only supplies _BitScanForward64 when building for a 64-bit target.
 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
-  unsigned long index;
-  return LIKELY(_BitScanReverse64(&index, x)) ? (63 - index) : 64;
+  return CountLeadingZeroBits(x);
 }
 
 #endif
 
 #elif defined(COMPILER_GCC)
 
-// This is very annoying. __builtin_clz has undefined behaviour for an input of
-// 0, even though there's clearly a return value that makes sense, and even
-// though some processor clz instructions have defined behaviour for 0. We could
-// drop to raw __asm__ to do better, but we'll avoid doing that unless we see
-// proof that we need to.
+// __builtin_clz has undefined behaviour for an input of 0, even though there's
+// clearly a return value that makes sense, and even though some processor clz
+// instructions have defined behaviour for 0. We could drop to raw __asm__ to
+// do better, but we'll avoid doing that unless we see proof that we need to.
+template <typename T, unsigned bits = sizeof(T) * 8>
+ALWAYS_INLINE
+    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
+                            unsigned>::type
+    CountLeadingZeroBits(T value) {
+  static_assert(bits > 0, "invalid instantiation");
+  return LIKELY(value)
+             ? bits == 64
+                   ? __builtin_clzll(static_cast<uint64_t>(value))
+                   : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits)
+             : bits;
+}
+
+template <typename T, unsigned bits = sizeof(T) * 8>
+ALWAYS_INLINE
+    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
+                            unsigned>::type
+    CountTrailingZeroBits(T value) {
+  return LIKELY(value) ? bits == 64
+                             ? __builtin_ctzll(static_cast<uint64_t>(value))
+                             : __builtin_ctz(static_cast<uint32_t>(value))
+                       : bits;
+}
+
 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
-  return LIKELY(x) ? __builtin_clz(x) : 32;
+  return CountLeadingZeroBits(x);
 }
 
+#if defined(ARCH_CPU_64_BITS)
+
 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
-  return LIKELY(x) ? __builtin_clzll(x) : 64;
+  return CountLeadingZeroBits(x);
 }
 
 #endif
 
-#if defined(ARCH_CPU_64_BITS)
+#endif
 
 ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) {
-  return CountLeadingZeroBits64(x);
+  return CountLeadingZeroBits(x);
 }
 
-#else
+ALWAYS_INLINE size_t CountTrailingZeroBitsSizeT(size_t x) {
+  return CountTrailingZeroBits(x);
+}
 
-ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) {
-  return CountLeadingZeroBits32(x);
+// Returns the integer i such as 2^i <= n < 2^(i+1)
+inline int Log2Floor(uint32_t n) {
+  return 31 - CountLeadingZeroBits(n);
 }
 
-#endif
+// Returns the integer i such as 2^(i-1) < n <= 2^i
+inline int Log2Ceiling(uint32_t n) {
+  // When n == 0, we want the function to return -1.
+  // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
+  // why the statement below starts with (n ? 32 : -1).
+  return (n ? 32 : -1) - CountLeadingZeroBits(n - 1);
+}
 
 }  // namespace bits
 }  // namespace base