1 //===- llvm/unittests/ADT/BitTest.cpp - <bit> tests ---===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/ADT/bit.h" 10 #include "gtest/gtest.h" 11 #include <cstdint> 12 #include <cstdlib> 13 14 using namespace llvm; 15 16 namespace { 17 18 TEST(BitTest, BitCast) { 19 static const uint8_t kValueU8 = 0x80; 20 EXPECT_TRUE(llvm::bit_cast<int8_t>(kValueU8) < 0); 21 22 static const uint16_t kValueU16 = 0x8000; 23 EXPECT_TRUE(llvm::bit_cast<int16_t>(kValueU16) < 0); 24 25 static const float kValueF32 = 5632.34f; 26 EXPECT_FLOAT_EQ(kValueF32, 27 llvm::bit_cast<float>(llvm::bit_cast<uint32_t>(kValueF32))); 28 29 static const double kValueF64 = 87987234.983498; 30 EXPECT_DOUBLE_EQ(kValueF64, 31 llvm::bit_cast<double>(llvm::bit_cast<uint64_t>(kValueF64))); 32 } 33 34 TEST(BitTest, HasSingleBit) { 35 EXPECT_FALSE(llvm::has_single_bit(0U)); 36 EXPECT_FALSE(llvm::has_single_bit(0ULL)); 37 38 EXPECT_FALSE(llvm::has_single_bit(~0U)); 39 EXPECT_FALSE(llvm::has_single_bit(~0ULL)); 40 41 EXPECT_TRUE(llvm::has_single_bit(1U)); 42 EXPECT_TRUE(llvm::has_single_bit(1ULL)); 43 44 static const int8_t kValueS8 = -128; 45 EXPECT_TRUE(llvm::has_single_bit(static_cast<uint8_t>(kValueS8))); 46 47 static const int16_t kValueS16 = -32768; 48 EXPECT_TRUE(llvm::has_single_bit(static_cast<uint16_t>(kValueS16))); 49 } 50 51 TEST(BitTest, BitFloor) { 52 EXPECT_EQ(0u, llvm::bit_floor(uint8_t(0))); 53 EXPECT_EQ(0u, llvm::bit_floor(uint16_t(0))); 54 EXPECT_EQ(0u, llvm::bit_floor(uint32_t(0))); 55 EXPECT_EQ(0u, llvm::bit_floor(uint64_t(0))); 56 57 EXPECT_EQ(1u, llvm::bit_floor(uint8_t(1))); 58 EXPECT_EQ(1u, llvm::bit_floor(uint16_t(1))); 59 EXPECT_EQ(1u, llvm::bit_floor(uint32_t(1))); 60 EXPECT_EQ(1u, llvm::bit_floor(uint64_t(1))); 61 62 EXPECT_EQ(2u, llvm::bit_floor(uint8_t(2))); 63 EXPECT_EQ(2u, llvm::bit_floor(uint16_t(2))); 64 EXPECT_EQ(2u, llvm::bit_floor(uint32_t(2))); 65 EXPECT_EQ(2u, llvm::bit_floor(uint64_t(2))); 66 67 EXPECT_EQ(2u, llvm::bit_floor(uint8_t(3))); 68 EXPECT_EQ(2u, llvm::bit_floor(uint16_t(3))); 69 EXPECT_EQ(2u, llvm::bit_floor(uint32_t(3))); 70 EXPECT_EQ(2u, llvm::bit_floor(uint64_t(3))); 71 72 EXPECT_EQ(4u, llvm::bit_floor(uint8_t(4))); 73 EXPECT_EQ(4u, llvm::bit_floor(uint16_t(4))); 74 EXPECT_EQ(4u, llvm::bit_floor(uint32_t(4))); 75 EXPECT_EQ(4u, llvm::bit_floor(uint64_t(4))); 76 77 EXPECT_EQ(0x40u, llvm::bit_floor(uint8_t(0x7f))); 78 EXPECT_EQ(0x4000u, llvm::bit_floor(uint16_t(0x7fff))); 79 EXPECT_EQ(0x40000000u, llvm::bit_floor(uint32_t(0x7fffffffu))); 80 EXPECT_EQ(0x4000000000000000ull, 81 llvm::bit_floor(uint64_t(0x7fffffffffffffffull))); 82 83 EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0x80))); 84 EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0x8000))); 85 EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0x80000000u))); 86 EXPECT_EQ(0x8000000000000000ull, 87 llvm::bit_floor(uint64_t(0x8000000000000000ull))); 88 89 EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0xff))); 90 EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0xffff))); 91 EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0xffffffffu))); 92 EXPECT_EQ(0x8000000000000000ull, 93 llvm::bit_floor(uint64_t(0xffffffffffffffffull))); 94 } 95 96 TEST(BitTest, BitCeil) { 97 EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(0))); 98 EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(0))); 99 EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(0))); 100 EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(0))); 101 102 EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(1))); 103 EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(1))); 104 EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(1))); 105 EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(1))); 106 107 EXPECT_EQ(2u, llvm::bit_ceil(uint8_t(2))); 108 EXPECT_EQ(2u, llvm::bit_ceil(uint16_t(2))); 109 EXPECT_EQ(2u, llvm::bit_ceil(uint32_t(2))); 110 EXPECT_EQ(2u, llvm::bit_ceil(uint64_t(2))); 111 112 EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(3))); 113 EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(3))); 114 EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(3))); 115 EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(3))); 116 117 EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(4))); 118 EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(4))); 119 EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(4))); 120 EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(4))); 121 122 // The result is the largest representable value for each type. 123 EXPECT_EQ(0x80u, llvm::bit_ceil(uint8_t(0x7f))); 124 EXPECT_EQ(0x8000u, llvm::bit_ceil(uint16_t(0x7fff))); 125 EXPECT_EQ(0x80000000u, llvm::bit_ceil(uint32_t(0x7fffffffu))); 126 EXPECT_EQ(0x8000000000000000ull, 127 llvm::bit_ceil(uint64_t(0x7fffffffffffffffull))); 128 } 129 130 TEST(BitTest, BitWidth) { 131 EXPECT_EQ(0, llvm::bit_width(uint8_t(0))); 132 EXPECT_EQ(0, llvm::bit_width(uint16_t(0))); 133 EXPECT_EQ(0, llvm::bit_width(uint32_t(0))); 134 EXPECT_EQ(0, llvm::bit_width(uint64_t(0))); 135 136 EXPECT_EQ(1, llvm::bit_width(uint8_t(1))); 137 EXPECT_EQ(1, llvm::bit_width(uint16_t(1))); 138 EXPECT_EQ(1, llvm::bit_width(uint32_t(1))); 139 EXPECT_EQ(1, llvm::bit_width(uint64_t(1))); 140 141 EXPECT_EQ(2, llvm::bit_width(uint8_t(2))); 142 EXPECT_EQ(2, llvm::bit_width(uint16_t(2))); 143 EXPECT_EQ(2, llvm::bit_width(uint32_t(2))); 144 EXPECT_EQ(2, llvm::bit_width(uint64_t(2))); 145 146 EXPECT_EQ(2, llvm::bit_width(uint8_t(3))); 147 EXPECT_EQ(2, llvm::bit_width(uint16_t(3))); 148 EXPECT_EQ(2, llvm::bit_width(uint32_t(3))); 149 EXPECT_EQ(2, llvm::bit_width(uint64_t(3))); 150 151 EXPECT_EQ(3, llvm::bit_width(uint8_t(4))); 152 EXPECT_EQ(3, llvm::bit_width(uint16_t(4))); 153 EXPECT_EQ(3, llvm::bit_width(uint32_t(4))); 154 EXPECT_EQ(3, llvm::bit_width(uint64_t(4))); 155 156 EXPECT_EQ(7, llvm::bit_width(uint8_t(0x7f))); 157 EXPECT_EQ(15, llvm::bit_width(uint16_t(0x7fff))); 158 EXPECT_EQ(31, llvm::bit_width(uint32_t(0x7fffffffu))); 159 EXPECT_EQ(63, llvm::bit_width(uint64_t(0x7fffffffffffffffull))); 160 161 EXPECT_EQ(8, llvm::bit_width(uint8_t(0x80))); 162 EXPECT_EQ(16, llvm::bit_width(uint16_t(0x8000))); 163 EXPECT_EQ(32, llvm::bit_width(uint32_t(0x80000000u))); 164 EXPECT_EQ(64, llvm::bit_width(uint64_t(0x8000000000000000ull))); 165 166 EXPECT_EQ(8, llvm::bit_width(uint8_t(0xff))); 167 EXPECT_EQ(16, llvm::bit_width(uint16_t(0xffff))); 168 EXPECT_EQ(32, llvm::bit_width(uint32_t(0xffffffffu))); 169 EXPECT_EQ(64, llvm::bit_width(uint64_t(0xffffffffffffffffull))); 170 } 171 172 TEST(BitTest, CountlZero) { 173 uint8_t Z8 = 0; 174 uint16_t Z16 = 0; 175 uint32_t Z32 = 0; 176 uint64_t Z64 = 0; 177 EXPECT_EQ(8, llvm::countl_zero(Z8)); 178 EXPECT_EQ(16, llvm::countl_zero(Z16)); 179 EXPECT_EQ(32, llvm::countl_zero(Z32)); 180 EXPECT_EQ(64, llvm::countl_zero(Z64)); 181 182 uint8_t NZ8 = 42; 183 uint16_t NZ16 = 42; 184 uint32_t NZ32 = 42; 185 uint64_t NZ64 = 42; 186 EXPECT_EQ(2, llvm::countl_zero(NZ8)); 187 EXPECT_EQ(10, llvm::countl_zero(NZ16)); 188 EXPECT_EQ(26, llvm::countl_zero(NZ32)); 189 EXPECT_EQ(58, llvm::countl_zero(NZ64)); 190 191 EXPECT_EQ(8, llvm::countl_zero(0x00F000FFu)); 192 EXPECT_EQ(8, llvm::countl_zero(0x00F12345u)); 193 for (unsigned i = 0; i <= 30; ++i) { 194 EXPECT_EQ(int(31 - i), llvm::countl_zero(1u << i)); 195 } 196 197 EXPECT_EQ(8, llvm::countl_zero(0x00F1234500F12345ULL)); 198 EXPECT_EQ(1, llvm::countl_zero(1ULL << 62)); 199 for (unsigned i = 0; i <= 62; ++i) { 200 EXPECT_EQ(int(63 - i), llvm::countl_zero(1ULL << i)); 201 } 202 } 203 204 TEST(BitTest, CountrZero) { 205 uint8_t Z8 = 0; 206 uint16_t Z16 = 0; 207 uint32_t Z32 = 0; 208 uint64_t Z64 = 0; 209 EXPECT_EQ(8, llvm::countr_zero(Z8)); 210 EXPECT_EQ(16, llvm::countr_zero(Z16)); 211 EXPECT_EQ(32, llvm::countr_zero(Z32)); 212 EXPECT_EQ(64, llvm::countr_zero(Z64)); 213 214 uint8_t NZ8 = 42; 215 uint16_t NZ16 = 42; 216 uint32_t NZ32 = 42; 217 uint64_t NZ64 = 42; 218 EXPECT_EQ(1, llvm::countr_zero(NZ8)); 219 EXPECT_EQ(1, llvm::countr_zero(NZ16)); 220 EXPECT_EQ(1, llvm::countr_zero(NZ32)); 221 EXPECT_EQ(1, llvm::countr_zero(NZ64)); 222 } 223 224 TEST(BitTest, CountlOne) { 225 for (int i = 30; i >= 0; --i) { 226 // Start with all ones and unset some bit. 227 EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i))); 228 } 229 for (int i = 62; i >= 0; --i) { 230 // Start with all ones and unset some bit. 231 EXPECT_EQ(63 - i, llvm::countl_one(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i))); 232 } 233 for (int i = 30; i >= 0; --i) { 234 // Start with all ones and unset some bit. 235 EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i))); 236 } 237 } 238 239 TEST(BitTest, CountrOne) { 240 uint8_t AllOnes8 = ~(uint8_t)0; 241 uint16_t AllOnes16 = ~(uint16_t)0; 242 uint32_t AllOnes32 = ~(uint32_t)0; 243 uint64_t AllOnes64 = ~(uint64_t)0; 244 EXPECT_EQ(8, llvm::countr_one(AllOnes8)); 245 EXPECT_EQ(16, llvm::countr_one(AllOnes16)); 246 EXPECT_EQ(32, llvm::countr_one(AllOnes32)); 247 EXPECT_EQ(64, llvm::countr_one(AllOnes64)); 248 249 uint8_t X8 = 6; 250 uint16_t X16 = 6; 251 uint32_t X32 = 6; 252 uint64_t X64 = 6; 253 EXPECT_EQ(0, llvm::countr_one(X8)); 254 EXPECT_EQ(0, llvm::countr_one(X16)); 255 EXPECT_EQ(0, llvm::countr_one(X32)); 256 EXPECT_EQ(0, llvm::countr_one(X64)); 257 258 uint8_t Y8 = 23; 259 uint16_t Y16 = 23; 260 uint32_t Y32 = 23; 261 uint64_t Y64 = 23; 262 EXPECT_EQ(3, llvm::countr_one(Y8)); 263 EXPECT_EQ(3, llvm::countr_one(Y16)); 264 EXPECT_EQ(3, llvm::countr_one(Y32)); 265 EXPECT_EQ(3, llvm::countr_one(Y64)); 266 } 267 268 TEST(BitTest, PopCount) { 269 EXPECT_EQ(0, llvm::popcount(0U)); 270 EXPECT_EQ(0, llvm::popcount(0ULL)); 271 272 EXPECT_EQ(32, llvm::popcount(~0U)); 273 EXPECT_EQ(64, llvm::popcount(~0ULL)); 274 275 for (int I = 0; I != 32; ++I) 276 EXPECT_EQ(1, llvm::popcount(1U << I)); 277 } 278 279 } // anonymous namespace 280