llvm/unittests/ADT/BitTest.cpp

   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 TEST(BitTest, Rotl) {
 358   EXPECT_EQ(0x53U, llvm::rotl<uint8_t>(0x53, 0));
 359   EXPECT_EQ(0x4dU, llvm::rotl<uint8_t>(0x53, 2));
 360   EXPECT_EQ(0xa6U, llvm::rotl<uint8_t>(0x53, 9));
 361   EXPECT_EQ(0x9aU, llvm::rotl<uint8_t>(0x53, -5));
 362
 363   EXPECT_EQ(0xabcdU, llvm::rotl<uint16_t>(0xabcd, 0));
 364   EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, 6));
 365   EXPECT_EQ(0xaf36U, llvm::rotl<uint16_t>(0xabcd, 18));
 366   EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, -10));
 367
 368   EXPECT_EQ(0xdeadbeefU, llvm::rotl<uint32_t>(0xdeadbeef, 0));
 369   EXPECT_EQ(0x7ddfbd5bU, llvm::rotl<uint32_t>(0xdeadbeef, 17));
 370   EXPECT_EQ(0x5b7ddfbdU, llvm::rotl<uint32_t>(0xdeadbeef, 41));
 371   EXPECT_EQ(0xb6fbbf7aU, llvm::rotl<uint32_t>(0xdeadbeef, -22));
 372
 373   EXPECT_EQ(0x12345678deadbeefULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 0));
 374   EXPECT_EQ(0xf56df77891a2b3c6ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 35));
 375   EXPECT_EQ(0x8d159e37ab6fbbc4ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 70));
 376   EXPECT_EQ(0xb7dde2468acf1bd5ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, -19));
 377 }
 378
 379 TEST(BitTest, Rotr) {
 380   EXPECT_EQ(0x53U, llvm::rotr<uint8_t>(0x53, 0));
 381   EXPECT_EQ(0xd4U, llvm::rotr<uint8_t>(0x53, 2));
 382   EXPECT_EQ(0xa9U, llvm::rotr<uint8_t>(0x53, 9));
 383   EXPECT_EQ(0x6aU, llvm::rotr<uint8_t>(0x53, -5));
 384
 385   EXPECT_EQ(0xabcdU, llvm::rotr<uint16_t>(0xabcd, 0));
 386   EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, 6));
 387   EXPECT_EQ(0x6af3U, llvm::rotr<uint16_t>(0xabcd, 18));
 388   EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, -10));
 389
 390   EXPECT_EQ(0xdeadbeefU, llvm::rotr<uint32_t>(0xdeadbeef, 0));
 391   EXPECT_EQ(0xdf77ef56U, llvm::rotr<uint32_t>(0xdeadbeef, 17));
 392   EXPECT_EQ(0x77ef56dfU, llvm::rotr<uint32_t>(0xdeadbeef, 41));
 393   EXPECT_EQ(0xbbf7ab6fU, llvm::rotr<uint32_t>(0xdeadbeef, -22));
 394
 395   EXPECT_EQ(0x12345678deadbeefULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 0));
 396   EXPECT_EQ(0x1bd5b7dde2468acfULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 35));
 397   EXPECT_EQ(0xbc48d159e37ab6fbULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 70));
 398   EXPECT_EQ(0xb3c6f56df77891a2ULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, -19));
 399 }
 400
 401 } // anonymous namespace