summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--third_party/base/bits.h156
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