| //===- llvm/unittests/ADT/BitTest.cpp - <bit> tests ---===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/ADT/bit.h" |
| #include "gtest/gtest.h" |
| #include <cstdint> |
| #include <cstdlib> |
| |
| using namespace llvm; |
| |
| namespace { |
| |
| TEST(BitTest, BitCast) { |
| static const uint8_t kValueU8 = 0x80; |
| EXPECT_TRUE(llvm::bit_cast<int8_t>(kValueU8) < 0); |
| |
| static const uint16_t kValueU16 = 0x8000; |
| EXPECT_TRUE(llvm::bit_cast<int16_t>(kValueU16) < 0); |
| |
| static const float kValueF32 = 5632.34f; |
| EXPECT_FLOAT_EQ(kValueF32, |
| llvm::bit_cast<float>(llvm::bit_cast<uint32_t>(kValueF32))); |
| |
| static const double kValueF64 = 87987234.983498; |
| EXPECT_DOUBLE_EQ(kValueF64, |
| llvm::bit_cast<double>(llvm::bit_cast<uint64_t>(kValueF64))); |
| } |
| |
| // In these first two tests all of the original_uintx values are truncated |
| // except for 64. We could avoid this, but there's really no point. |
| |
| TEST(BitTest, ByteSwapUnsignedRoundTrip) { |
| // The point of the bit twiddling of magic is to test with and without bits |
| // in every byte. |
| uint64_t value = 1; |
| for (std::size_t i = 0; i <= sizeof(value); ++i) { |
| uint8_t original_uint8 = static_cast<uint8_t>(value); |
| EXPECT_EQ(original_uint8, llvm::byteswap(llvm::byteswap(original_uint8))); |
| |
| uint16_t original_uint16 = static_cast<uint16_t>(value); |
| EXPECT_EQ(original_uint16, llvm::byteswap(llvm::byteswap(original_uint16))); |
| |
| uint32_t original_uint32 = static_cast<uint32_t>(value); |
| EXPECT_EQ(original_uint32, llvm::byteswap(llvm::byteswap(original_uint32))); |
| |
| uint64_t original_uint64 = static_cast<uint64_t>(value); |
| EXPECT_EQ(original_uint64, llvm::byteswap(llvm::byteswap(original_uint64))); |
| |
| value = (value << 8) | 0x55; // binary 0101 0101. |
| } |
| } |
| |
| TEST(BitTest, ByteSwapSignedRoundTrip) { |
| // The point of the bit twiddling of magic is to test with and without bits |
| // in every byte. |
| uint64_t value = 1; |
| for (std::size_t i = 0; i <= sizeof(value); ++i) { |
| int8_t original_int8 = static_cast<int8_t>(value); |
| EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8))); |
| |
| int16_t original_int16 = static_cast<int16_t>(value); |
| EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16))); |
| |
| int32_t original_int32 = static_cast<int32_t>(value); |
| EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32))); |
| |
| int64_t original_int64 = static_cast<int64_t>(value); |
| EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64))); |
| |
| // Test other sign. |
| value *= -1; |
| |
| original_int8 = static_cast<int8_t>(value); |
| EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8))); |
| |
| original_int16 = static_cast<int16_t>(value); |
| EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16))); |
| |
| original_int32 = static_cast<int32_t>(value); |
| EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32))); |
| |
| original_int64 = static_cast<int64_t>(value); |
| EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64))); |
| |
| // Return to normal sign and twiddle. |
| value *= -1; |
| value = (value << 8) | 0x55; // binary 0101 0101. |
| } |
| } |
| |
| TEST(BitTest, ByteSwap) { |
| // Unsigned types. |
| EXPECT_EQ(uint8_t(0x11), llvm::byteswap(uint8_t(0x11))); |
| EXPECT_EQ(uint16_t(0x1122), llvm::byteswap(uint16_t(0x2211))); |
| EXPECT_EQ(uint32_t(0x11223344), llvm::byteswap(uint32_t(0x44332211))); |
| EXPECT_EQ(uint64_t(0x1122334455667788ULL), |
| llvm::byteswap(uint64_t(0x8877665544332211ULL))); |
| |
| // Signed types. |
| EXPECT_EQ(int8_t(0x11), llvm::byteswap(int8_t(0x11))); |
| EXPECT_EQ(int16_t(0x1122), llvm::byteswap(int16_t(0x2211))); |
| EXPECT_EQ(int32_t(0x11223344), llvm::byteswap(int32_t(0x44332211))); |
| EXPECT_EQ(int64_t(0x1122334455667788LL), |
| llvm::byteswap(int64_t(0x8877665544332211LL))); |
| } |
| |
| TEST(BitTest, HasSingleBit) { |
| EXPECT_FALSE(llvm::has_single_bit(0U)); |
| EXPECT_FALSE(llvm::has_single_bit(0ULL)); |
| |
| EXPECT_FALSE(llvm::has_single_bit(~0U)); |
| EXPECT_FALSE(llvm::has_single_bit(~0ULL)); |
| |
| EXPECT_TRUE(llvm::has_single_bit(1U)); |
| EXPECT_TRUE(llvm::has_single_bit(1ULL)); |
| |
| static const int8_t kValueS8 = -128; |
| EXPECT_TRUE(llvm::has_single_bit(static_cast<uint8_t>(kValueS8))); |
| |
| static const int16_t kValueS16 = -32768; |
| EXPECT_TRUE(llvm::has_single_bit(static_cast<uint16_t>(kValueS16))); |
| } |
| |
| TEST(BitTest, BitFloor) { |
| EXPECT_EQ(0u, llvm::bit_floor(uint8_t(0))); |
| EXPECT_EQ(0u, llvm::bit_floor(uint16_t(0))); |
| EXPECT_EQ(0u, llvm::bit_floor(uint32_t(0))); |
| EXPECT_EQ(0u, llvm::bit_floor(uint64_t(0))); |
| |
| EXPECT_EQ(1u, llvm::bit_floor(uint8_t(1))); |
| EXPECT_EQ(1u, llvm::bit_floor(uint16_t(1))); |
| EXPECT_EQ(1u, llvm::bit_floor(uint32_t(1))); |
| EXPECT_EQ(1u, llvm::bit_floor(uint64_t(1))); |
| |
| EXPECT_EQ(2u, llvm::bit_floor(uint8_t(2))); |
| EXPECT_EQ(2u, llvm::bit_floor(uint16_t(2))); |
| EXPECT_EQ(2u, llvm::bit_floor(uint32_t(2))); |
| EXPECT_EQ(2u, llvm::bit_floor(uint64_t(2))); |
| |
| EXPECT_EQ(2u, llvm::bit_floor(uint8_t(3))); |
| EXPECT_EQ(2u, llvm::bit_floor(uint16_t(3))); |
| EXPECT_EQ(2u, llvm::bit_floor(uint32_t(3))); |
| EXPECT_EQ(2u, llvm::bit_floor(uint64_t(3))); |
| |
| EXPECT_EQ(4u, llvm::bit_floor(uint8_t(4))); |
| EXPECT_EQ(4u, llvm::bit_floor(uint16_t(4))); |
| EXPECT_EQ(4u, llvm::bit_floor(uint32_t(4))); |
| EXPECT_EQ(4u, llvm::bit_floor(uint64_t(4))); |
| |
| EXPECT_EQ(0x40u, llvm::bit_floor(uint8_t(0x7f))); |
| EXPECT_EQ(0x4000u, llvm::bit_floor(uint16_t(0x7fff))); |
| EXPECT_EQ(0x40000000u, llvm::bit_floor(uint32_t(0x7fffffffu))); |
| EXPECT_EQ(0x4000000000000000ull, |
| llvm::bit_floor(uint64_t(0x7fffffffffffffffull))); |
| |
| EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0x80))); |
| EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0x8000))); |
| EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0x80000000u))); |
| EXPECT_EQ(0x8000000000000000ull, |
| llvm::bit_floor(uint64_t(0x8000000000000000ull))); |
| |
| EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0xff))); |
| EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0xffff))); |
| EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0xffffffffu))); |
| EXPECT_EQ(0x8000000000000000ull, |
| llvm::bit_floor(uint64_t(0xffffffffffffffffull))); |
| } |
| |
| TEST(BitTest, BitCeil) { |
| EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(0))); |
| EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(0))); |
| EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(0))); |
| EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(0))); |
| |
| EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(1))); |
| EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(1))); |
| EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(1))); |
| EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(1))); |
| |
| EXPECT_EQ(2u, llvm::bit_ceil(uint8_t(2))); |
| EXPECT_EQ(2u, llvm::bit_ceil(uint16_t(2))); |
| EXPECT_EQ(2u, llvm::bit_ceil(uint32_t(2))); |
| EXPECT_EQ(2u, llvm::bit_ceil(uint64_t(2))); |
| |
| EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(3))); |
| EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(3))); |
| EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(3))); |
| EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(3))); |
| |
| EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(4))); |
| EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(4))); |
| EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(4))); |
| EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(4))); |
| |
| // The result is the largest representable value for each type. |
| EXPECT_EQ(0x80u, llvm::bit_ceil(uint8_t(0x7f))); |
| EXPECT_EQ(0x8000u, llvm::bit_ceil(uint16_t(0x7fff))); |
| EXPECT_EQ(0x80000000u, llvm::bit_ceil(uint32_t(0x7fffffffu))); |
| EXPECT_EQ(0x8000000000000000ull, |
| llvm::bit_ceil(uint64_t(0x7fffffffffffffffull))); |
| } |
| |
| TEST(BitTest, BitWidth) { |
| EXPECT_EQ(0, llvm::bit_width(uint8_t(0))); |
| EXPECT_EQ(0, llvm::bit_width(uint16_t(0))); |
| EXPECT_EQ(0, llvm::bit_width(uint32_t(0))); |
| EXPECT_EQ(0, llvm::bit_width(uint64_t(0))); |
| |
| EXPECT_EQ(1, llvm::bit_width(uint8_t(1))); |
| EXPECT_EQ(1, llvm::bit_width(uint16_t(1))); |
| EXPECT_EQ(1, llvm::bit_width(uint32_t(1))); |
| EXPECT_EQ(1, llvm::bit_width(uint64_t(1))); |
| |
| EXPECT_EQ(2, llvm::bit_width(uint8_t(2))); |
| EXPECT_EQ(2, llvm::bit_width(uint16_t(2))); |
| EXPECT_EQ(2, llvm::bit_width(uint32_t(2))); |
| EXPECT_EQ(2, llvm::bit_width(uint64_t(2))); |
| |
| EXPECT_EQ(2, llvm::bit_width(uint8_t(3))); |
| EXPECT_EQ(2, llvm::bit_width(uint16_t(3))); |
| EXPECT_EQ(2, llvm::bit_width(uint32_t(3))); |
| EXPECT_EQ(2, llvm::bit_width(uint64_t(3))); |
| |
| EXPECT_EQ(3, llvm::bit_width(uint8_t(4))); |
| EXPECT_EQ(3, llvm::bit_width(uint16_t(4))); |
| EXPECT_EQ(3, llvm::bit_width(uint32_t(4))); |
| EXPECT_EQ(3, llvm::bit_width(uint64_t(4))); |
| |
| EXPECT_EQ(7, llvm::bit_width(uint8_t(0x7f))); |
| EXPECT_EQ(15, llvm::bit_width(uint16_t(0x7fff))); |
| EXPECT_EQ(31, llvm::bit_width(uint32_t(0x7fffffffu))); |
| EXPECT_EQ(63, llvm::bit_width(uint64_t(0x7fffffffffffffffull))); |
| |
| EXPECT_EQ(8, llvm::bit_width(uint8_t(0x80))); |
| EXPECT_EQ(16, llvm::bit_width(uint16_t(0x8000))); |
| EXPECT_EQ(32, llvm::bit_width(uint32_t(0x80000000u))); |
| EXPECT_EQ(64, llvm::bit_width(uint64_t(0x8000000000000000ull))); |
| |
| EXPECT_EQ(8, llvm::bit_width(uint8_t(0xff))); |
| EXPECT_EQ(16, llvm::bit_width(uint16_t(0xffff))); |
| EXPECT_EQ(32, llvm::bit_width(uint32_t(0xffffffffu))); |
| EXPECT_EQ(64, llvm::bit_width(uint64_t(0xffffffffffffffffull))); |
| } |
| |
| TEST(BitTest, CountlZero) { |
| uint8_t Z8 = 0; |
| uint16_t Z16 = 0; |
| uint32_t Z32 = 0; |
| uint64_t Z64 = 0; |
| EXPECT_EQ(8, llvm::countl_zero(Z8)); |
| EXPECT_EQ(16, llvm::countl_zero(Z16)); |
| EXPECT_EQ(32, llvm::countl_zero(Z32)); |
| EXPECT_EQ(64, llvm::countl_zero(Z64)); |
| |
| uint8_t NZ8 = 42; |
| uint16_t NZ16 = 42; |
| uint32_t NZ32 = 42; |
| uint64_t NZ64 = 42; |
| EXPECT_EQ(2, llvm::countl_zero(NZ8)); |
| EXPECT_EQ(10, llvm::countl_zero(NZ16)); |
| EXPECT_EQ(26, llvm::countl_zero(NZ32)); |
| EXPECT_EQ(58, llvm::countl_zero(NZ64)); |
| |
| EXPECT_EQ(8, llvm::countl_zero(0x00F000FFu)); |
| EXPECT_EQ(8, llvm::countl_zero(0x00F12345u)); |
| for (unsigned i = 0; i <= 30; ++i) { |
| EXPECT_EQ(int(31 - i), llvm::countl_zero(1u << i)); |
| } |
| |
| EXPECT_EQ(8, llvm::countl_zero(0x00F1234500F12345ULL)); |
| EXPECT_EQ(1, llvm::countl_zero(1ULL << 62)); |
| for (unsigned i = 0; i <= 62; ++i) { |
| EXPECT_EQ(int(63 - i), llvm::countl_zero(1ULL << i)); |
| } |
| } |
| |
| TEST(BitTest, CountrZero) { |
| uint8_t Z8 = 0; |
| uint16_t Z16 = 0; |
| uint32_t Z32 = 0; |
| uint64_t Z64 = 0; |
| EXPECT_EQ(8, llvm::countr_zero(Z8)); |
| EXPECT_EQ(16, llvm::countr_zero(Z16)); |
| EXPECT_EQ(32, llvm::countr_zero(Z32)); |
| EXPECT_EQ(64, llvm::countr_zero(Z64)); |
| |
| uint8_t NZ8 = 42; |
| uint16_t NZ16 = 42; |
| uint32_t NZ32 = 42; |
| uint64_t NZ64 = 42; |
| EXPECT_EQ(1, llvm::countr_zero(NZ8)); |
| EXPECT_EQ(1, llvm::countr_zero(NZ16)); |
| EXPECT_EQ(1, llvm::countr_zero(NZ32)); |
| EXPECT_EQ(1, llvm::countr_zero(NZ64)); |
| } |
| |
| TEST(BitTest, CountlOne) { |
| for (int i = 30; i >= 0; --i) { |
| // Start with all ones and unset some bit. |
| EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i))); |
| } |
| for (int i = 62; i >= 0; --i) { |
| // Start with all ones and unset some bit. |
| EXPECT_EQ(63 - i, llvm::countl_one(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i))); |
| } |
| for (int i = 30; i >= 0; --i) { |
| // Start with all ones and unset some bit. |
| EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i))); |
| } |
| } |
| |
| TEST(BitTest, CountrOne) { |
| uint8_t AllOnes8 = ~(uint8_t)0; |
| uint16_t AllOnes16 = ~(uint16_t)0; |
| uint32_t AllOnes32 = ~(uint32_t)0; |
| uint64_t AllOnes64 = ~(uint64_t)0; |
| EXPECT_EQ(8, llvm::countr_one(AllOnes8)); |
| EXPECT_EQ(16, llvm::countr_one(AllOnes16)); |
| EXPECT_EQ(32, llvm::countr_one(AllOnes32)); |
| EXPECT_EQ(64, llvm::countr_one(AllOnes64)); |
| |
| uint8_t X8 = 6; |
| uint16_t X16 = 6; |
| uint32_t X32 = 6; |
| uint64_t X64 = 6; |
| EXPECT_EQ(0, llvm::countr_one(X8)); |
| EXPECT_EQ(0, llvm::countr_one(X16)); |
| EXPECT_EQ(0, llvm::countr_one(X32)); |
| EXPECT_EQ(0, llvm::countr_one(X64)); |
| |
| uint8_t Y8 = 23; |
| uint16_t Y16 = 23; |
| uint32_t Y32 = 23; |
| uint64_t Y64 = 23; |
| EXPECT_EQ(3, llvm::countr_one(Y8)); |
| EXPECT_EQ(3, llvm::countr_one(Y16)); |
| EXPECT_EQ(3, llvm::countr_one(Y32)); |
| EXPECT_EQ(3, llvm::countr_one(Y64)); |
| } |
| |
| TEST(BitTest, PopCount) { |
| EXPECT_EQ(0, llvm::popcount(0U)); |
| EXPECT_EQ(0, llvm::popcount(0ULL)); |
| |
| EXPECT_EQ(32, llvm::popcount(~0U)); |
| EXPECT_EQ(64, llvm::popcount(~0ULL)); |
| |
| for (int I = 0; I != 32; ++I) |
| EXPECT_EQ(1, llvm::popcount(1U << I)); |
| } |
| |
| TEST(BitTest, Rotl) { |
| EXPECT_EQ(0x53U, llvm::rotl<uint8_t>(0x53, 0)); |
| EXPECT_EQ(0x4dU, llvm::rotl<uint8_t>(0x53, 2)); |
| EXPECT_EQ(0xa6U, llvm::rotl<uint8_t>(0x53, 9)); |
| EXPECT_EQ(0x9aU, llvm::rotl<uint8_t>(0x53, -5)); |
| |
| EXPECT_EQ(0xabcdU, llvm::rotl<uint16_t>(0xabcd, 0)); |
| EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, 6)); |
| EXPECT_EQ(0xaf36U, llvm::rotl<uint16_t>(0xabcd, 18)); |
| EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, -10)); |
| |
| EXPECT_EQ(0xdeadbeefU, llvm::rotl<uint32_t>(0xdeadbeef, 0)); |
| EXPECT_EQ(0x7ddfbd5bU, llvm::rotl<uint32_t>(0xdeadbeef, 17)); |
| EXPECT_EQ(0x5b7ddfbdU, llvm::rotl<uint32_t>(0xdeadbeef, 41)); |
| EXPECT_EQ(0xb6fbbf7aU, llvm::rotl<uint32_t>(0xdeadbeef, -22)); |
| |
| EXPECT_EQ(0x12345678deadbeefULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 0)); |
| EXPECT_EQ(0xf56df77891a2b3c6ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 35)); |
| EXPECT_EQ(0x8d159e37ab6fbbc4ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 70)); |
| EXPECT_EQ(0xb7dde2468acf1bd5ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, -19)); |
| } |
| |
| TEST(BitTest, Rotr) { |
| EXPECT_EQ(0x53U, llvm::rotr<uint8_t>(0x53, 0)); |
| EXPECT_EQ(0xd4U, llvm::rotr<uint8_t>(0x53, 2)); |
| EXPECT_EQ(0xa9U, llvm::rotr<uint8_t>(0x53, 9)); |
| EXPECT_EQ(0x6aU, llvm::rotr<uint8_t>(0x53, -5)); |
| |
| EXPECT_EQ(0xabcdU, llvm::rotr<uint16_t>(0xabcd, 0)); |
| EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, 6)); |
| EXPECT_EQ(0x6af3U, llvm::rotr<uint16_t>(0xabcd, 18)); |
| EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, -10)); |
| |
| EXPECT_EQ(0xdeadbeefU, llvm::rotr<uint32_t>(0xdeadbeef, 0)); |
| EXPECT_EQ(0xdf77ef56U, llvm::rotr<uint32_t>(0xdeadbeef, 17)); |
| EXPECT_EQ(0x77ef56dfU, llvm::rotr<uint32_t>(0xdeadbeef, 41)); |
| EXPECT_EQ(0xbbf7ab6fU, llvm::rotr<uint32_t>(0xdeadbeef, -22)); |
| |
| EXPECT_EQ(0x12345678deadbeefULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 0)); |
| EXPECT_EQ(0x1bd5b7dde2468acfULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 35)); |
| EXPECT_EQ(0xbc48d159e37ab6fbULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 70)); |
| EXPECT_EQ(0xb3c6f56df77891a2ULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, -19)); |
| } |
| |
| } // anonymous namespace |