From 36fe3f2b5651882b12e24b49dc7818ebb1a5d79f Mon Sep 17 00:00:00 2001 From: "Michael J. Spencer" Date: Fri, 24 May 2013 20:29:47 +0000 Subject: [PATCH] [Support] Add type generic bit utilities to MathExtras.h git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182667 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/MathExtras.h | 212 +++++++++++++++++++++++++++ unittests/Support/MathExtrasTest.cpp | 91 ++++++++++++ 2 files changed, 303 insertions(+) diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index d6ae58dc457..d77a1cb7e74 100644 --- a/include/llvm/Support/MathExtras.h +++ b/include/llvm/Support/MathExtras.h @@ -15,12 +15,224 @@ #define LLVM_SUPPORT_MATHEXTRAS_H #include "llvm/Support/SwapByteOrder.h" +#include "llvm/Support/type_traits.h" + +#include #ifdef _MSC_VER # include #endif namespace llvm { +/// \brief The behavior an operation has on an input of 0. +enum ZeroBehavior { + /// \brief The returned value is undefined. + ZB_Undefined, + /// \brief The returned value is numeric_limits::max() + ZB_Max, + /// \brief The returned value is numeric_limits::digits + ZB_Width +}; + +/// \brief Count number of 0's from the least significant bit to the most +/// stopping at the first 1. +/// +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are +/// valid arguments. +template +typename enable_if_c::is_integer && + !std::numeric_limits::is_signed, std::size_t>::type +countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { + if (!Val) + return std::numeric_limits::digits; + if (Val & 0x1) + return 0; + + // Bisection method. + std::size_t ZeroBits = 0; + T Shift = std::numeric_limits::digits >> 1; + T Mask = std::numeric_limits::max() >> Shift; + while (Shift) { + if ((Val & Mask) == 0) { + Val >>= Shift; + ZeroBits |= Shift; + } + Shift >>= 1; + Mask >>= Shift; + } + return ZeroBits; +} + +// Disable signed. +template +typename enable_if_c::is_integer && + std::numeric_limits::is_signed, std::size_t>::type +countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION; + +#if __GNUC__ >= 4 || _MSC_VER +template <> +inline std::size_t countTrailingZeros(uint32_t Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 32; + +#if __GNUC__ >= 4 + return __builtin_ctz(Val); +#elif _MSC_VER + unsigned long Index; + _BitScanForward(&Index, Val); + return Index; +#endif +} + +template <> +inline std::size_t countTrailingZeros(uint64_t Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 64; + +#if __GNUC__ >= 4 + return __builtin_ctzll(Val); +#elif _MSC_VER + unsigned long Index; + _BitScanForward64(&Index, Val); + return Index; +#endif +} +#endif + +/// \brief Count number of 0's from the most significant bit to the least +/// stopping at the first 1. +/// +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are +/// valid arguments. +template +typename enable_if_c::is_integer && + !std::numeric_limits::is_signed, std::size_t>::type +countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { + if (!Val) + return std::numeric_limits::digits; + + // Bisection method. + std::size_t ZeroBits = 0; + for (T Shift = std::numeric_limits::digits >> 1; Shift; Shift >>= 1) { + T Tmp = Val >> Shift; + if (Tmp) + Val = Tmp; + else + ZeroBits |= Shift; + } + return ZeroBits; +} + +// Disable signed. +template +typename enable_if_c::is_integer && + std::numeric_limits::is_signed, std::size_t>::type +countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION; + +#if __GNUC__ >= 4 || _MSC_VER +template <> +inline std::size_t countLeadingZeros(uint32_t Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 32; + +#if __GNUC__ >= 4 + return __builtin_clz(Val); +#elif _MSC_VER + unsigned long Index; + _BitScanReverse(&Index, Val); + return Index ^ 31; +#endif +} + +template <> +inline std::size_t countLeadingZeros(uint64_t Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 64; + +#if __GNUC__ >= 4 + return __builtin_clzll(Val); +#elif _MSC_VER + unsigned long Index; + _BitScanReverse64(&Index, Val); + return Index ^ 63; +#endif +} +#endif + +/// \brief Get the index of the first set bit starting from the least +/// significant bit. +/// +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are +/// valid arguments. +template +typename enable_if_c::is_integer && + !std::numeric_limits::is_signed, std::size_t>::type +findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { + if (ZB == ZB_Max && Val == 0) + return std::numeric_limits::max(); + + return countTrailingZeros(Val, ZB_Undefined); +} + +// Disable signed. +template +typename enable_if_c::is_integer && + std::numeric_limits::is_signed, std::size_t>::type +findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION; + +/// \brief Get the index of the last set bit starting from the least +/// significant bit. +/// +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are +/// valid arguments. +template +typename enable_if_c::is_integer && + !std::numeric_limits::is_signed, std::size_t>::type +findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { + if (ZB == ZB_Max && Val == 0) + return std::numeric_limits::max(); + + // Use ^ instead of - because both gcc and llvm can remove the associated ^ + // in the __builtin_clz intrinsic on x86. + return countLeadingZeros(Val, ZB_Undefined) ^ + (std::numeric_limits::digits - 1); +} + +// Disable signed. +template +typename enable_if_c::is_integer && + std::numeric_limits::is_signed, std::size_t>::type +findLastSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION; + +/// \brief Macro compressed bit reversal table for 256 bits. +/// +/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable +static const unsigned char BitReverseTable256[256] = { +#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 +#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) +#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) + R6(0), R6(2), R6(1), R6(3) +}; + +/// \brief Reverse the bits in \p Val. +template +T reverseBits(T Val) { + unsigned char in[sizeof(Val)]; + unsigned char out[sizeof(Val)]; + std::memcpy(in, &Val, sizeof(Val)); + for (unsigned i = 0; i < sizeof(Val); ++i) + out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]]; + std::memcpy(&Val, out, sizeof(Val)); + return Val; +} // NOTE: The following support functions use the _32/_64 extensions instead of // type overloading so that signed and unsigned integers can be used without diff --git a/unittests/Support/MathExtrasTest.cpp b/unittests/Support/MathExtrasTest.cpp index 0a6724c7e70..5fd638f5f33 100644 --- a/unittests/Support/MathExtrasTest.cpp +++ b/unittests/Support/MathExtrasTest.cpp @@ -14,6 +14,97 @@ using namespace llvm; namespace { +TEST(MathExtras, countTrailingZeros) { + uint8_t Z8 = 0; + uint16_t Z16 = 0; + uint32_t Z32 = 0; + uint64_t Z64 = 0; + EXPECT_EQ(8, countTrailingZeros(Z8)); + EXPECT_EQ(16, countTrailingZeros(Z16)); + EXPECT_EQ(32, countTrailingZeros(Z32)); + EXPECT_EQ(64, countTrailingZeros(Z64)); + + uint8_t NZ8 = 42; + uint16_t NZ16 = 42; + uint32_t NZ32 = 42; + uint64_t NZ64 = 42; + EXPECT_EQ(1, countTrailingZeros(NZ8)); + EXPECT_EQ(1, countTrailingZeros(NZ16)); + EXPECT_EQ(1, countTrailingZeros(NZ32)); + EXPECT_EQ(1, countTrailingZeros(NZ64)); +} + +TEST(MathExtras, countLeadingZeros) { + uint8_t Z8 = 0; + uint16_t Z16 = 0; + uint32_t Z32 = 0; + uint64_t Z64 = 0; + EXPECT_EQ(8, countLeadingZeros(Z8)); + EXPECT_EQ(16, countLeadingZeros(Z16)); + EXPECT_EQ(32, countLeadingZeros(Z32)); + EXPECT_EQ(64, countLeadingZeros(Z64)); + + uint8_t NZ8 = 42; + uint16_t NZ16 = 42; + uint32_t NZ32 = 42; + uint64_t NZ64 = 42; + EXPECT_EQ(2, countLeadingZeros(NZ8)); + EXPECT_EQ(10, countLeadingZeros(NZ16)); + EXPECT_EQ(26, countLeadingZeros(NZ32)); + EXPECT_EQ(58, countLeadingZeros(NZ64)); +} + +TEST(MathExtras, findFirstSet) { + uint8_t Z8 = 0; + uint16_t Z16 = 0; + uint32_t Z32 = 0; + uint64_t Z64 = 0; + EXPECT_EQ(0xFF, findFirstSet(Z8)); + EXPECT_EQ(0xFFFF, findFirstSet(Z16)); + EXPECT_EQ(0xFFFFFFFF, findFirstSet(Z32)); + EXPECT_EQ(0xFFFFFFFFFFFFFFFF, findFirstSet(Z64)); + + uint8_t NZ8 = 42; + uint16_t NZ16 = 42; + uint32_t NZ32 = 42; + uint64_t NZ64 = 42; + EXPECT_EQ(1, findFirstSet(NZ8)); + EXPECT_EQ(1, findFirstSet(NZ16)); + EXPECT_EQ(1, findFirstSet(NZ32)); + EXPECT_EQ(1, findFirstSet(NZ64)); +} + +TEST(MathExtras, findLastSet) { + uint8_t Z8 = 0; + uint16_t Z16 = 0; + uint32_t Z32 = 0; + uint64_t Z64 = 0; + EXPECT_EQ(0xFF, findLastSet(Z8)); + EXPECT_EQ(0xFFFF, findLastSet(Z16)); + EXPECT_EQ(0xFFFFFFFF, findLastSet(Z32)); + EXPECT_EQ(0xFFFFFFFFFFFFFFFF, findLastSet(Z64)); + + uint8_t NZ8 = 42; + uint16_t NZ16 = 42; + uint32_t NZ32 = 42; + uint64_t NZ64 = 42; + EXPECT_EQ(5, findLastSet(NZ8)); + EXPECT_EQ(5, findLastSet(NZ16)); + EXPECT_EQ(5, findLastSet(NZ32)); + EXPECT_EQ(5, findLastSet(NZ64)); +} + +TEST(MathExtras, reverseBits) { + uint8_t NZ8 = 42; + uint16_t NZ16 = 42; + uint32_t NZ32 = 42; + uint64_t NZ64 = 42; + EXPECT_EQ(0x54, reverseBits(NZ8)); + EXPECT_EQ(0x5400, reverseBits(NZ16)); + EXPECT_EQ(0x54000000, reverseBits(NZ32)); + EXPECT_EQ(0x5400000000000000, reverseBits(NZ64)); +} + TEST(MathExtras, isPowerOf2_32) { EXPECT_TRUE(isPowerOf2_32(1 << 6)); EXPECT_TRUE(isPowerOf2_32(1 << 12)); -- 2.34.1