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 // In these first two tests all of the original_uintx values are truncated 35 // except for 64. We could avoid this, but there's really no point. 36 37 TEST(BitTest, ByteSwapUnsignedRoundTrip) { 38 // The point of the bit twiddling of magic is to test with and without bits 39 // in every byte. 40 uint64_t value = 1; 41 for (std::size_t i = 0; i <= sizeof(value); ++i) { 42 uint8_t original_uint8 = static_cast<uint8_t>(value); 43 EXPECT_EQ(original_uint8, llvm::byteswap(llvm::byteswap(original_uint8))); 44 45 uint16_t original_uint16 = static_cast<uint16_t>(value); 46 EXPECT_EQ(original_uint16, llvm::byteswap(llvm::byteswap(original_uint16))); 47 48 uint32_t original_uint32 = static_cast<uint32_t>(value); 49 EXPECT_EQ(original_uint32, llvm::byteswap(llvm::byteswap(original_uint32))); 50 51 uint64_t original_uint64 = static_cast<uint64_t>(value); 52 EXPECT_EQ(original_uint64, llvm::byteswap(llvm::byteswap(original_uint64))); 53 54 value = (value << 8) | 0x55; // binary 0101 0101. 55 } 56 } 57 58 TEST(BitTest, ByteSwapSignedRoundTrip) { 59 // The point of the bit twiddling of magic is to test with and without bits 60 // in every byte. 61 uint64_t value = 1; 62 for (std::size_t i = 0; i <= sizeof(value); ++i) { 63 int8_t original_int8 = static_cast<int8_t>(value); 64 EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8))); 65 66 int16_t original_int16 = static_cast<int16_t>(value); 67 EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16))); 68 69 int32_t original_int32 = static_cast<int32_t>(value); 70 EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32))); 71 72 int64_t original_int64 = static_cast<int64_t>(value); 73 EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64))); 74 75 // Test other sign. 76 value *= -1; 77 78 original_int8 = static_cast<int8_t>(value); 79 EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8))); 80 81 original_int16 = static_cast<int16_t>(value); 82 EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16))); 83 84 original_int32 = static_cast<int32_t>(value); 85 EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32))); 86 87 original_int64 = static_cast<int64_t>(value); 88 EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64))); 89 90 // Return to normal sign and twiddle. 91 value *= -1; 92 value = (value << 8) | 0x55; // binary 0101 0101. 93 } 94 } 95 96 TEST(BitTest, ByteSwap) { 97 // Unsigned types. 98 EXPECT_EQ(uint8_t(0x11), llvm::byteswap(uint8_t(0x11))); 99 EXPECT_EQ(uint16_t(0x1122), llvm::byteswap(uint16_t(0x2211))); 100 EXPECT_EQ(uint32_t(0x11223344), llvm::byteswap(uint32_t(0x44332211))); 101 EXPECT_EQ(uint64_t(0x1122334455667788ULL), 102 llvm::byteswap(uint64_t(0x8877665544332211ULL))); 103 104 // Signed types. 105 EXPECT_EQ(int8_t(0x11), llvm::byteswap(int8_t(0x11))); 106 EXPECT_EQ(int16_t(0x1122), llvm::byteswap(int16_t(0x2211))); 107 EXPECT_EQ(int32_t(0x11223344), llvm::byteswap(int32_t(0x44332211))); 108 EXPECT_EQ(int64_t(0x1122334455667788LL), 109 llvm::byteswap(int64_t(0x8877665544332211LL))); 110 } 111 112 TEST(BitTest, HasSingleBit) { 113 EXPECT_FALSE(llvm::has_single_bit(0U)); 114 EXPECT_FALSE(llvm::has_single_bit(0ULL)); 115 116 EXPECT_FALSE(llvm::has_single_bit(~0U)); 117 EXPECT_FALSE(llvm::has_single_bit(~0ULL)); 118 119 EXPECT_TRUE(llvm::has_single_bit(1U)); 120 EXPECT_TRUE(llvm::has_single_bit(1ULL)); 121 122 static const int8_t kValueS8 = -128; 123 EXPECT_TRUE(llvm::has_single_bit(static_cast<uint8_t>(kValueS8))); 124 125 static const int16_t kValueS16 = -32768; 126 EXPECT_TRUE(llvm::has_single_bit(static_cast<uint16_t>(kValueS16))); 127 } 128 129 TEST(BitTest, BitFloor) { 130 EXPECT_EQ(0u, llvm::bit_floor(uint8_t(0))); 131 EXPECT_EQ(0u, llvm::bit_floor(uint16_t(0))); 132 EXPECT_EQ(0u, llvm::bit_floor(uint32_t(0))); 133 EXPECT_EQ(0u, llvm::bit_floor(uint64_t(0))); 134 135 EXPECT_EQ(1u, llvm::bit_floor(uint8_t(1))); 136 EXPECT_EQ(1u, llvm::bit_floor(uint16_t(1))); 137 EXPECT_EQ(1u, llvm::bit_floor(uint32_t(1))); 138 EXPECT_EQ(1u, llvm::bit_floor(uint64_t(1))); 139 140 EXPECT_EQ(2u, llvm::bit_floor(uint8_t(2))); 141 EXPECT_EQ(2u, llvm::bit_floor(uint16_t(2))); 142 EXPECT_EQ(2u, llvm::bit_floor(uint32_t(2))); 143 EXPECT_EQ(2u, llvm::bit_floor(uint64_t(2))); 144 145 EXPECT_EQ(2u, llvm::bit_floor(uint8_t(3))); 146 EXPECT_EQ(2u, llvm::bit_floor(uint16_t(3))); 147 EXPECT_EQ(2u, llvm::bit_floor(uint32_t(3))); 148 EXPECT_EQ(2u, llvm::bit_floor(uint64_t(3))); 149 150 EXPECT_EQ(4u, llvm::bit_floor(uint8_t(4))); 151 EXPECT_EQ(4u, llvm::bit_floor(uint16_t(4))); 152 EXPECT_EQ(4u, llvm::bit_floor(uint32_t(4))); 153 EXPECT_EQ(4u, llvm::bit_floor(uint64_t(4))); 154 155 EXPECT_EQ(0x40u, llvm::bit_floor(uint8_t(0x7f))); 156 EXPECT_EQ(0x4000u, llvm::bit_floor(uint16_t(0x7fff))); 157 EXPECT_EQ(0x40000000u, llvm::bit_floor(uint32_t(0x7fffffffu))); 158 EXPECT_EQ(0x4000000000000000ull, 159 llvm::bit_floor(uint64_t(0x7fffffffffffffffull))); 160 161 EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0x80))); 162 EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0x8000))); 163 EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0x80000000u))); 164 EXPECT_EQ(0x8000000000000000ull, 165 llvm::bit_floor(uint64_t(0x8000000000000000ull))); 166 167 EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0xff))); 168 EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0xffff))); 169 EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0xffffffffu))); 170 EXPECT_EQ(0x8000000000000000ull, 171 llvm::bit_floor(uint64_t(0xffffffffffffffffull))); 172 } 173 174 TEST(BitTest, BitCeil) { 175 EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(0))); 176 EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(0))); 177 EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(0))); 178 EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(0))); 179 180 EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(1))); 181 EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(1))); 182 EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(1))); 183 EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(1))); 184 185 EXPECT_EQ(2u, llvm::bit_ceil(uint8_t(2))); 186 EXPECT_EQ(2u, llvm::bit_ceil(uint16_t(2))); 187 EXPECT_EQ(2u, llvm::bit_ceil(uint32_t(2))); 188 EXPECT_EQ(2u, llvm::bit_ceil(uint64_t(2))); 189 190 EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(3))); 191 EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(3))); 192 EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(3))); 193 EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(3))); 194 195 EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(4))); 196 EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(4))); 197 EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(4))); 198 EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(4))); 199 200 // The result is the largest representable value for each type. 201 EXPECT_EQ(0x80u, llvm::bit_ceil(uint8_t(0x7f))); 202 EXPECT_EQ(0x8000u, llvm::bit_ceil(uint16_t(0x7fff))); 203 EXPECT_EQ(0x80000000u, llvm::bit_ceil(uint32_t(0x7fffffffu))); 204 EXPECT_EQ(0x8000000000000000ull, 205 llvm::bit_ceil(uint64_t(0x7fffffffffffffffull))); 206 } 207 208 TEST(BitTest, BitWidth) { 209 EXPECT_EQ(0, llvm::bit_width(uint8_t(0))); 210 EXPECT_EQ(0, llvm::bit_width(uint16_t(0))); 211 EXPECT_EQ(0, llvm::bit_width(uint32_t(0))); 212 EXPECT_EQ(0, llvm::bit_width(uint64_t(0))); 213 214 EXPECT_EQ(1, llvm::bit_width(uint8_t(1))); 215 EXPECT_EQ(1, llvm::bit_width(uint16_t(1))); 216 EXPECT_EQ(1, llvm::bit_width(uint32_t(1))); 217 EXPECT_EQ(1, llvm::bit_width(uint64_t(1))); 218 219 EXPECT_EQ(2, llvm::bit_width(uint8_t(2))); 220 EXPECT_EQ(2, llvm::bit_width(uint16_t(2))); 221 EXPECT_EQ(2, llvm::bit_width(uint32_t(2))); 222 EXPECT_EQ(2, llvm::bit_width(uint64_t(2))); 223 224 EXPECT_EQ(2, llvm::bit_width(uint8_t(3))); 225 EXPECT_EQ(2, llvm::bit_width(uint16_t(3))); 226 EXPECT_EQ(2, llvm::bit_width(uint32_t(3))); 227 EXPECT_EQ(2, llvm::bit_width(uint64_t(3))); 228 229 EXPECT_EQ(3, llvm::bit_width(uint8_t(4))); 230 EXPECT_EQ(3, llvm::bit_width(uint16_t(4))); 231 EXPECT_EQ(3, llvm::bit_width(uint32_t(4))); 232 EXPECT_EQ(3, llvm::bit_width(uint64_t(4))); 233 234 EXPECT_EQ(7, llvm::bit_width(uint8_t(0x7f))); 235 EXPECT_EQ(15, llvm::bit_width(uint16_t(0x7fff))); 236 EXPECT_EQ(31, llvm::bit_width(uint32_t(0x7fffffffu))); 237 EXPECT_EQ(63, llvm::bit_width(uint64_t(0x7fffffffffffffffull))); 238 239 EXPECT_EQ(8, llvm::bit_width(uint8_t(0x80))); 240 EXPECT_EQ(16, llvm::bit_width(uint16_t(0x8000))); 241 EXPECT_EQ(32, llvm::bit_width(uint32_t(0x80000000u))); 242 EXPECT_EQ(64, llvm::bit_width(uint64_t(0x8000000000000000ull))); 243 244 EXPECT_EQ(8, llvm::bit_width(uint8_t(0xff))); 245 EXPECT_EQ(16, llvm::bit_width(uint16_t(0xffff))); 246 EXPECT_EQ(32, llvm::bit_width(uint32_t(0xffffffffu))); 247 EXPECT_EQ(64, llvm::bit_width(uint64_t(0xffffffffffffffffull))); 248 } 249 250 TEST(BitTest, CountlZero) { 251 uint8_t Z8 = 0; 252 uint16_t Z16 = 0; 253 uint32_t Z32 = 0; 254 uint64_t Z64 = 0; 255 EXPECT_EQ(8, llvm::countl_zero(Z8)); 256 EXPECT_EQ(16, llvm::countl_zero(Z16)); 257 EXPECT_EQ(32, llvm::countl_zero(Z32)); 258 EXPECT_EQ(64, llvm::countl_zero(Z64)); 259 260 uint8_t NZ8 = 42; 261 uint16_t NZ16 = 42; 262 uint32_t NZ32 = 42; 263 uint64_t NZ64 = 42; 264 EXPECT_EQ(2, llvm::countl_zero(NZ8)); 265 EXPECT_EQ(10, llvm::countl_zero(NZ16)); 266 EXPECT_EQ(26, llvm::countl_zero(NZ32)); 267 EXPECT_EQ(58, llvm::countl_zero(NZ64)); 268 269 EXPECT_EQ(8, llvm::countl_zero(0x00F000FFu)); 270 EXPECT_EQ(8, llvm::countl_zero(0x00F12345u)); 271 for (unsigned i = 0; i <= 30; ++i) { 272 EXPECT_EQ(int(31 - i), llvm::countl_zero(1u << i)); 273 } 274 275 EXPECT_EQ(8, llvm::countl_zero(0x00F1234500F12345ULL)); 276 EXPECT_EQ(1, llvm::countl_zero(1ULL << 62)); 277 for (unsigned i = 0; i <= 62; ++i) { 278 EXPECT_EQ(int(63 - i), llvm::countl_zero(1ULL << i)); 279 } 280 } 281 282 TEST(BitTest, CountrZero) { 283 uint8_t Z8 = 0; 284 uint16_t Z16 = 0; 285 uint32_t Z32 = 0; 286 uint64_t Z64 = 0; 287 EXPECT_EQ(8, llvm::countr_zero(Z8)); 288 EXPECT_EQ(16, llvm::countr_zero(Z16)); 289 EXPECT_EQ(32, llvm::countr_zero(Z32)); 290 EXPECT_EQ(64, llvm::countr_zero(Z64)); 291 292 uint8_t NZ8 = 42; 293 uint16_t NZ16 = 42; 294 uint32_t NZ32 = 42; 295 uint64_t NZ64 = 42; 296 EXPECT_EQ(1, llvm::countr_zero(NZ8)); 297 EXPECT_EQ(1, llvm::countr_zero(NZ16)); 298 EXPECT_EQ(1, llvm::countr_zero(NZ32)); 299 EXPECT_EQ(1, llvm::countr_zero(NZ64)); 300 } 301 302 TEST(BitTest, CountlOne) { 303 for (int i = 30; i >= 0; --i) { 304 // Start with all ones and unset some bit. 305 EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i))); 306 } 307 for (int i = 62; i >= 0; --i) { 308 // Start with all ones and unset some bit. 309 EXPECT_EQ(63 - i, llvm::countl_one(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i))); 310 } 311 for (int i = 30; i >= 0; --i) { 312 // Start with all ones and unset some bit. 313 EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i))); 314 } 315 } 316 317 TEST(BitTest, CountrOne) { 318 uint8_t AllOnes8 = ~(uint8_t)0; 319 uint16_t AllOnes16 = ~(uint16_t)0; 320 uint32_t AllOnes32 = ~(uint32_t)0; 321 uint64_t AllOnes64 = ~(uint64_t)0; 322 EXPECT_EQ(8, llvm::countr_one(AllOnes8)); 323 EXPECT_EQ(16, llvm::countr_one(AllOnes16)); 324 EXPECT_EQ(32, llvm::countr_one(AllOnes32)); 325 EXPECT_EQ(64, llvm::countr_one(AllOnes64)); 326 327 uint8_t X8 = 6; 328 uint16_t X16 = 6; 329 uint32_t X32 = 6; 330 uint64_t X64 = 6; 331 EXPECT_EQ(0, llvm::countr_one(X8)); 332 EXPECT_EQ(0, llvm::countr_one(X16)); 333 EXPECT_EQ(0, llvm::countr_one(X32)); 334 EXPECT_EQ(0, llvm::countr_one(X64)); 335 336 uint8_t Y8 = 23; 337 uint16_t Y16 = 23; 338 uint32_t Y32 = 23; 339 uint64_t Y64 = 23; 340 EXPECT_EQ(3, llvm::countr_one(Y8)); 341 EXPECT_EQ(3, llvm::countr_one(Y16)); 342 EXPECT_EQ(3, llvm::countr_one(Y32)); 343 EXPECT_EQ(3, llvm::countr_one(Y64)); 344 } 345 346 TEST(BitTest, PopCount) { 347 EXPECT_EQ(0, llvm::popcount(0U)); 348 EXPECT_EQ(0, llvm::popcount(0ULL)); 349 350 EXPECT_EQ(32, llvm::popcount(~0U)); 351 EXPECT_EQ(64, llvm::popcount(~0ULL)); 352 353 for (int I = 0; I != 32; ++I) 354 EXPECT_EQ(1, llvm::popcount(1U << I)); 355 } 356 357 } // anonymous namespace 358