bits_test.cc (25941B)
1 // Copyright 2020 The Abseil Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "absl/numeric/bits.h" 16 17 #include <cstdint> 18 #include <limits> 19 #include <type_traits> 20 21 #include "gmock/gmock.h" 22 #include "gtest/gtest.h" 23 #include "absl/random/random.h" 24 25 namespace absl { 26 ABSL_NAMESPACE_BEGIN 27 namespace { 28 29 template <typename IntT> 30 class IntegerTypesTest : public ::testing::Test {}; 31 32 using OneByteIntegerTypes = ::testing::Types< 33 unsigned char, 34 uint8_t 35 >; 36 37 TYPED_TEST_SUITE(IntegerTypesTest, OneByteIntegerTypes); 38 39 TYPED_TEST(IntegerTypesTest, HandlesTypes) { 40 using UIntType = TypeParam; 41 42 EXPECT_EQ(rotl(UIntType{0x12}, 0), uint8_t{0x12}); 43 EXPECT_EQ(rotr(UIntType{0x12}, -4), uint8_t{0x21}); 44 static_assert(rotl(UIntType{0x12}, 0) == uint8_t{0x12}, ""); 45 46 static_assert(rotr(UIntType{0x12}, 0) == uint8_t{0x12}, ""); 47 EXPECT_EQ(rotr(UIntType{0x12}, 0), uint8_t{0x12}); 48 49 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 50 static_assert(countl_zero(UIntType{}) == 8, ""); 51 static_assert(countl_zero(static_cast<UIntType>(-1)) == 0, ""); 52 53 static_assert(countl_one(UIntType{}) == 0, ""); 54 static_assert(countl_one(static_cast<UIntType>(-1)) == 8, ""); 55 56 static_assert(countr_zero(UIntType{}) == 8, ""); 57 static_assert(countr_zero(static_cast<UIntType>(-1)) == 0, ""); 58 59 static_assert(countr_one(UIntType{}) == 0, ""); 60 static_assert(countr_one(static_cast<UIntType>(-1)) == 8, ""); 61 62 static_assert(popcount(UIntType{}) == 0, ""); 63 static_assert(popcount(UIntType{1}) == 1, ""); 64 static_assert(popcount(static_cast<UIntType>(-1)) == 8, ""); 65 66 static_assert(bit_width(UIntType{}) == 0, ""); 67 static_assert(bit_width(UIntType{1}) == 1, ""); 68 static_assert(bit_width(UIntType{3}) == 2, ""); 69 static_assert(bit_width(static_cast<UIntType>(-1)) == 8, ""); 70 #endif 71 72 EXPECT_EQ(countl_zero(UIntType{}), 8); 73 EXPECT_EQ(countl_zero(static_cast<UIntType>(-1)), 0); 74 75 EXPECT_EQ(countl_one(UIntType{}), 0); 76 EXPECT_EQ(countl_one(static_cast<UIntType>(-1)), 8); 77 78 EXPECT_EQ(countr_zero(UIntType{}), 8); 79 EXPECT_EQ(countr_zero(static_cast<UIntType>(-1)), 0); 80 81 EXPECT_EQ(countr_one(UIntType{}), 0); 82 EXPECT_EQ(countr_one(static_cast<UIntType>(-1)), 8); 83 84 EXPECT_EQ(popcount(UIntType{}), 0); 85 EXPECT_EQ(popcount(UIntType{1}), 1); 86 87 EXPECT_FALSE(has_single_bit(UIntType{})); 88 EXPECT_FALSE(has_single_bit(static_cast<UIntType>(-1))); 89 90 EXPECT_EQ(bit_width(UIntType{}), 0); 91 EXPECT_EQ(bit_width(UIntType{1}), 1); 92 EXPECT_EQ(bit_width(UIntType{3}), 2); 93 EXPECT_EQ(bit_width(static_cast<UIntType>(-1)), 8); 94 } 95 96 TEST(Rotate, Left) { 97 static_assert(rotl(uint8_t{0x12}, 0) == uint8_t{0x12}, ""); 98 static_assert(rotl(uint16_t{0x1234}, 0) == uint16_t{0x1234}, ""); 99 static_assert(rotl(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, ""); 100 static_assert(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0) == 101 uint64_t{0x12345678ABCDEF01ULL}, 102 ""); 103 104 EXPECT_EQ(rotl(uint8_t{0x12}, 0), uint8_t{0x12}); 105 EXPECT_EQ(rotl(uint16_t{0x1234}, 0), uint16_t{0x1234}); 106 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL}); 107 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0), 108 uint64_t{0x12345678ABCDEF01ULL}); 109 110 EXPECT_EQ(rotl(uint8_t{0x12}, 8), uint8_t{0x12}); 111 EXPECT_EQ(rotl(uint16_t{0x1234}, 16), uint16_t{0x1234}); 112 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL}); 113 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 64), 114 uint64_t{0x12345678ABCDEF01ULL}); 115 116 EXPECT_EQ(rotl(uint8_t{0x12}, -8), uint8_t{0x12}); 117 EXPECT_EQ(rotl(uint16_t{0x1234}, -16), uint16_t{0x1234}); 118 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL}); 119 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -64), 120 uint64_t{0x12345678ABCDEF01ULL}); 121 122 EXPECT_EQ(rotl(uint8_t{0x12}, 4), uint8_t{0x21}); 123 EXPECT_EQ(rotl(uint16_t{0x1234}, 4), uint16_t{0x2341}); 124 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 4), uint32_t{0x23456781UL}); 125 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 4), 126 uint64_t{0x2345678ABCDEF011ULL}); 127 128 EXPECT_EQ(rotl(uint8_t{0x12}, -4), uint8_t{0x21}); 129 EXPECT_EQ(rotl(uint16_t{0x1234}, -4), uint16_t{0x4123}); 130 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -4), uint32_t{0x81234567UL}); 131 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -4), 132 uint64_t{0x112345678ABCDEF0ULL}); 133 } 134 135 TEST(Rotate, Right) { 136 static_assert(rotr(uint8_t{0x12}, 0) == uint8_t{0x12}, ""); 137 static_assert(rotr(uint16_t{0x1234}, 0) == uint16_t{0x1234}, ""); 138 static_assert(rotr(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, ""); 139 static_assert(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0) == 140 uint64_t{0x12345678ABCDEF01ULL}, 141 ""); 142 143 EXPECT_EQ(rotr(uint8_t{0x12}, 0), uint8_t{0x12}); 144 EXPECT_EQ(rotr(uint16_t{0x1234}, 0), uint16_t{0x1234}); 145 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL}); 146 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0), 147 uint64_t{0x12345678ABCDEF01ULL}); 148 149 EXPECT_EQ(rotr(uint8_t{0x12}, 8), uint8_t{0x12}); 150 EXPECT_EQ(rotr(uint16_t{0x1234}, 16), uint16_t{0x1234}); 151 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL}); 152 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 64), 153 uint64_t{0x12345678ABCDEF01ULL}); 154 155 EXPECT_EQ(rotr(uint8_t{0x12}, -8), uint8_t{0x12}); 156 EXPECT_EQ(rotr(uint16_t{0x1234}, -16), uint16_t{0x1234}); 157 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL}); 158 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -64), 159 uint64_t{0x12345678ABCDEF01ULL}); 160 161 EXPECT_EQ(rotr(uint8_t{0x12}, 4), uint8_t{0x21}); 162 EXPECT_EQ(rotr(uint16_t{0x1234}, 4), uint16_t{0x4123}); 163 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 4), uint32_t{0x81234567UL}); 164 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 4), 165 uint64_t{0x112345678ABCDEF0ULL}); 166 167 EXPECT_EQ(rotr(uint8_t{0x12}, -4), uint8_t{0x21}); 168 EXPECT_EQ(rotr(uint16_t{0x1234}, -4), uint16_t{0x2341}); 169 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -4), uint32_t{0x23456781UL}); 170 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -4), 171 uint64_t{0x2345678ABCDEF011ULL}); 172 } 173 174 TEST(Rotate, Symmetry) { 175 // rotr(x, s) is equivalent to rotl(x, -s) 176 absl::BitGen rng; 177 constexpr int kTrials = 100; 178 179 for (int i = 0; i < kTrials; ++i) { 180 uint8_t value = absl::Uniform(rng, std::numeric_limits<uint8_t>::min(), 181 std::numeric_limits<uint8_t>::max()); 182 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint8_t>::digits, 183 2 * std::numeric_limits<uint8_t>::digits); 184 185 EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); 186 } 187 188 for (int i = 0; i < kTrials; ++i) { 189 uint16_t value = absl::Uniform(rng, std::numeric_limits<uint16_t>::min(), 190 std::numeric_limits<uint16_t>::max()); 191 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint16_t>::digits, 192 2 * std::numeric_limits<uint16_t>::digits); 193 194 EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); 195 } 196 197 for (int i = 0; i < kTrials; ++i) { 198 uint32_t value = absl::Uniform(rng, std::numeric_limits<uint32_t>::min(), 199 std::numeric_limits<uint32_t>::max()); 200 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint32_t>::digits, 201 2 * std::numeric_limits<uint32_t>::digits); 202 203 EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); 204 } 205 206 for (int i = 0; i < kTrials; ++i) { 207 uint64_t value = absl::Uniform(rng, std::numeric_limits<uint64_t>::min(), 208 std::numeric_limits<uint64_t>::max()); 209 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint64_t>::digits, 210 2 * std::numeric_limits<uint64_t>::digits); 211 212 EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); 213 } 214 } 215 216 TEST(Counting, LeadingZeroes) { 217 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 218 static_assert(countl_zero(uint8_t{}) == 8, ""); 219 static_assert(countl_zero(static_cast<uint8_t>(-1)) == 0, ""); 220 static_assert(countl_zero(uint16_t{}) == 16, ""); 221 static_assert(countl_zero(static_cast<uint16_t>(-1)) == 0, ""); 222 static_assert(countl_zero(uint32_t{}) == 32, ""); 223 static_assert(countl_zero(~uint32_t{}) == 0, ""); 224 static_assert(countl_zero(uint64_t{}) == 64, ""); 225 static_assert(countl_zero(~uint64_t{}) == 0, ""); 226 #endif 227 228 EXPECT_EQ(countl_zero(uint8_t{}), 8); 229 EXPECT_EQ(countl_zero(static_cast<uint8_t>(-1)), 0); 230 EXPECT_EQ(countl_zero(uint16_t{}), 16); 231 EXPECT_EQ(countl_zero(static_cast<uint16_t>(-1)), 0); 232 EXPECT_EQ(countl_zero(uint32_t{}), 32); 233 EXPECT_EQ(countl_zero(~uint32_t{}), 0); 234 EXPECT_EQ(countl_zero(uint64_t{}), 64); 235 EXPECT_EQ(countl_zero(~uint64_t{}), 0); 236 237 for (int i = 0; i < 8; i++) { 238 EXPECT_EQ(countl_zero(static_cast<uint8_t>(1u << i)), 7 - i); 239 } 240 241 for (int i = 0; i < 16; i++) { 242 EXPECT_EQ(countl_zero(static_cast<uint16_t>(1u << i)), 15 - i); 243 } 244 245 for (int i = 0; i < 32; i++) { 246 EXPECT_EQ(countl_zero(uint32_t{1} << i), 31 - i); 247 } 248 249 for (int i = 0; i < 64; i++) { 250 EXPECT_EQ(countl_zero(uint64_t{1} << i), 63 - i); 251 } 252 } 253 254 TEST(Counting, LeadingOnes) { 255 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 256 static_assert(countl_one(uint8_t{}) == 0, ""); 257 static_assert(countl_one(static_cast<uint8_t>(-1)) == 8, ""); 258 static_assert(countl_one(uint16_t{}) == 0, ""); 259 static_assert(countl_one(static_cast<uint16_t>(-1)) == 16, ""); 260 static_assert(countl_one(uint32_t{}) == 0, ""); 261 static_assert(countl_one(~uint32_t{}) == 32, ""); 262 static_assert(countl_one(uint64_t{}) == 0, ""); 263 static_assert(countl_one(~uint64_t{}) == 64, ""); 264 #endif 265 266 EXPECT_EQ(countl_one(uint8_t{}), 0); 267 EXPECT_EQ(countl_one(static_cast<uint8_t>(-1)), 8); 268 EXPECT_EQ(countl_one(uint16_t{}), 0); 269 EXPECT_EQ(countl_one(static_cast<uint16_t>(-1)), 16); 270 EXPECT_EQ(countl_one(uint32_t{}), 0); 271 EXPECT_EQ(countl_one(~uint32_t{}), 32); 272 EXPECT_EQ(countl_one(uint64_t{}), 0); 273 EXPECT_EQ(countl_one(~uint64_t{}), 64); 274 } 275 276 TEST(Counting, TrailingZeroes) { 277 #if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 278 static_assert(countr_zero(uint8_t{}) == 8, ""); 279 static_assert(countr_zero(static_cast<uint8_t>(-1)) == 0, ""); 280 static_assert(countr_zero(uint16_t{}) == 16, ""); 281 static_assert(countr_zero(static_cast<uint16_t>(-1)) == 0, ""); 282 static_assert(countr_zero(uint32_t{}) == 32, ""); 283 static_assert(countr_zero(~uint32_t{}) == 0, ""); 284 static_assert(countr_zero(uint64_t{}) == 64, ""); 285 static_assert(countr_zero(~uint64_t{}) == 0, ""); 286 #endif 287 288 EXPECT_EQ(countr_zero(uint8_t{}), 8); 289 EXPECT_EQ(countr_zero(static_cast<uint8_t>(-1)), 0); 290 EXPECT_EQ(countr_zero(uint16_t{}), 16); 291 EXPECT_EQ(countr_zero(static_cast<uint16_t>(-1)), 0); 292 EXPECT_EQ(countr_zero(uint32_t{}), 32); 293 EXPECT_EQ(countr_zero(~uint32_t{}), 0); 294 EXPECT_EQ(countr_zero(uint64_t{}), 64); 295 EXPECT_EQ(countr_zero(~uint64_t{}), 0); 296 } 297 298 TEST(Counting, TrailingOnes) { 299 #if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 300 static_assert(countr_one(uint8_t{}) == 0, ""); 301 static_assert(countr_one(static_cast<uint8_t>(-1)) == 8, ""); 302 static_assert(countr_one(uint16_t{}) == 0, ""); 303 static_assert(countr_one(static_cast<uint16_t>(-1)) == 16, ""); 304 static_assert(countr_one(uint32_t{}) == 0, ""); 305 static_assert(countr_one(~uint32_t{}) == 32, ""); 306 static_assert(countr_one(uint64_t{}) == 0, ""); 307 static_assert(countr_one(~uint64_t{}) == 64, ""); 308 #endif 309 310 EXPECT_EQ(countr_one(uint8_t{}), 0); 311 EXPECT_EQ(countr_one(static_cast<uint8_t>(-1)), 8); 312 EXPECT_EQ(countr_one(uint16_t{}), 0); 313 EXPECT_EQ(countr_one(static_cast<uint16_t>(-1)), 16); 314 EXPECT_EQ(countr_one(uint32_t{}), 0); 315 EXPECT_EQ(countr_one(~uint32_t{}), 32); 316 EXPECT_EQ(countr_one(uint64_t{}), 0); 317 EXPECT_EQ(countr_one(~uint64_t{}), 64); 318 } 319 320 TEST(Counting, Popcount) { 321 #if ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 322 static_assert(popcount(uint8_t{}) == 0, ""); 323 static_assert(popcount(uint8_t{1}) == 1, ""); 324 static_assert(popcount(static_cast<uint8_t>(-1)) == 8, ""); 325 static_assert(popcount(uint16_t{}) == 0, ""); 326 static_assert(popcount(uint16_t{1}) == 1, ""); 327 static_assert(popcount(static_cast<uint16_t>(-1)) == 16, ""); 328 static_assert(popcount(uint32_t{}) == 0, ""); 329 static_assert(popcount(uint32_t{1}) == 1, ""); 330 static_assert(popcount(~uint32_t{}) == 32, ""); 331 static_assert(popcount(uint64_t{}) == 0, ""); 332 static_assert(popcount(uint64_t{1}) == 1, ""); 333 static_assert(popcount(~uint64_t{}) == 64, ""); 334 #endif // ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 335 336 EXPECT_EQ(popcount(uint8_t{}), 0); 337 EXPECT_EQ(popcount(uint8_t{1}), 1); 338 EXPECT_EQ(popcount(static_cast<uint8_t>(-1)), 8); 339 EXPECT_EQ(popcount(uint16_t{}), 0); 340 EXPECT_EQ(popcount(uint16_t{1}), 1); 341 EXPECT_EQ(popcount(static_cast<uint16_t>(-1)), 16); 342 EXPECT_EQ(popcount(uint32_t{}), 0); 343 EXPECT_EQ(popcount(uint32_t{1}), 1); 344 EXPECT_EQ(popcount(~uint32_t{}), 32); 345 EXPECT_EQ(popcount(uint64_t{}), 0); 346 EXPECT_EQ(popcount(uint64_t{1}), 1); 347 EXPECT_EQ(popcount(~uint64_t{}), 64); 348 349 for (int i = 0; i < 8; i++) { 350 EXPECT_EQ(popcount(static_cast<uint8_t>(uint8_t{1} << i)), 1); 351 EXPECT_EQ(popcount(static_cast<uint8_t>(static_cast<uint8_t>(-1) ^ 352 (uint8_t{1} << i))), 353 7); 354 } 355 356 for (int i = 0; i < 16; i++) { 357 EXPECT_EQ(popcount(static_cast<uint16_t>(uint16_t{1} << i)), 1); 358 EXPECT_EQ(popcount(static_cast<uint16_t>(static_cast<uint16_t>(-1) ^ 359 (uint16_t{1} << i))), 360 15); 361 } 362 363 for (int i = 0; i < 32; i++) { 364 EXPECT_EQ(popcount(uint32_t{1} << i), 1); 365 EXPECT_EQ(popcount(static_cast<uint32_t>(-1) ^ (uint32_t{1} << i)), 31); 366 } 367 368 for (int i = 0; i < 64; i++) { 369 EXPECT_EQ(popcount(uint64_t{1} << i), 1); 370 EXPECT_EQ(popcount(static_cast<uint64_t>(-1) ^ (uint64_t{1} << i)), 63); 371 } 372 } 373 374 template <typename T> 375 struct PopcountInput { 376 T value = 0; 377 int expected = 0; 378 }; 379 380 template <typename T> 381 PopcountInput<T> GeneratePopcountInput(absl::BitGen& gen) { 382 PopcountInput<T> ret; 383 for (int i = 0; i < std::numeric_limits<T>::digits; i++) { 384 bool coin = absl::Bernoulli(gen, 0.2); 385 if (coin) { 386 ret.value |= T{1} << i; 387 ret.expected++; 388 } 389 } 390 return ret; 391 } 392 393 TEST(Counting, PopcountFuzz) { 394 absl::BitGen rng; 395 constexpr int kTrials = 100; 396 397 for (int i = 0; i < kTrials; ++i) { 398 auto input = GeneratePopcountInput<uint8_t>(rng); 399 EXPECT_EQ(popcount(input.value), input.expected); 400 } 401 402 for (int i = 0; i < kTrials; ++i) { 403 auto input = GeneratePopcountInput<uint16_t>(rng); 404 EXPECT_EQ(popcount(input.value), input.expected); 405 } 406 407 for (int i = 0; i < kTrials; ++i) { 408 auto input = GeneratePopcountInput<uint32_t>(rng); 409 EXPECT_EQ(popcount(input.value), input.expected); 410 } 411 412 for (int i = 0; i < kTrials; ++i) { 413 auto input = GeneratePopcountInput<uint64_t>(rng); 414 EXPECT_EQ(popcount(input.value), input.expected); 415 } 416 } 417 418 TEST(IntegralPowersOfTwo, SingleBit) { 419 EXPECT_FALSE(has_single_bit(uint8_t{})); 420 EXPECT_FALSE(has_single_bit(static_cast<uint8_t>(-1))); 421 EXPECT_FALSE(has_single_bit(uint16_t{})); 422 EXPECT_FALSE(has_single_bit(static_cast<uint16_t>(-1))); 423 EXPECT_FALSE(has_single_bit(uint32_t{})); 424 EXPECT_FALSE(has_single_bit(~uint32_t{})); 425 EXPECT_FALSE(has_single_bit(uint64_t{})); 426 EXPECT_FALSE(has_single_bit(~uint64_t{})); 427 428 static_assert(!has_single_bit(0u), ""); 429 static_assert(has_single_bit(1u), ""); 430 static_assert(has_single_bit(2u), ""); 431 static_assert(!has_single_bit(3u), ""); 432 static_assert(has_single_bit(4u), ""); 433 static_assert(!has_single_bit(1337u), ""); 434 static_assert(has_single_bit(65536u), ""); 435 static_assert(has_single_bit(uint32_t{1} << 30), ""); 436 static_assert(has_single_bit(uint64_t{1} << 42), ""); 437 438 EXPECT_FALSE(has_single_bit(0u)); 439 EXPECT_TRUE(has_single_bit(1u)); 440 EXPECT_TRUE(has_single_bit(2u)); 441 EXPECT_FALSE(has_single_bit(3u)); 442 EXPECT_TRUE(has_single_bit(4u)); 443 EXPECT_FALSE(has_single_bit(1337u)); 444 EXPECT_TRUE(has_single_bit(65536u)); 445 EXPECT_TRUE(has_single_bit(uint32_t{1} << 30)); 446 EXPECT_TRUE(has_single_bit(uint64_t{1} << 42)); 447 448 EXPECT_TRUE(has_single_bit( 449 static_cast<uint8_t>(std::numeric_limits<uint8_t>::max() / 2 + 1))); 450 EXPECT_TRUE(has_single_bit( 451 static_cast<uint16_t>(std::numeric_limits<uint16_t>::max() / 2 + 1))); 452 EXPECT_TRUE(has_single_bit( 453 static_cast<uint32_t>(std::numeric_limits<uint32_t>::max() / 2 + 1))); 454 EXPECT_TRUE(has_single_bit( 455 static_cast<uint64_t>(std::numeric_limits<uint64_t>::max() / 2 + 1))); 456 } 457 458 template <typename T, T arg, T = bit_ceil(arg)> 459 bool IsBitCeilConstantExpression(int) { 460 return true; 461 } 462 template <typename T, T arg> 463 bool IsBitCeilConstantExpression(char) { 464 return false; 465 } 466 467 TEST(IntegralPowersOfTwo, Ceiling) { 468 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 469 static_assert(bit_ceil(0u) == 1, ""); 470 static_assert(bit_ceil(1u) == 1, ""); 471 static_assert(bit_ceil(2u) == 2, ""); 472 static_assert(bit_ceil(3u) == 4, ""); 473 static_assert(bit_ceil(4u) == 4, ""); 474 static_assert(bit_ceil(1337u) == 2048, ""); 475 static_assert(bit_ceil(65536u) == 65536, ""); 476 static_assert(bit_ceil(65536u - 1337u) == 65536, ""); 477 static_assert(bit_ceil(uint32_t{0x80000000}) == uint32_t{0x80000000}, ""); 478 static_assert(bit_ceil(uint64_t{0x40000000000}) == uint64_t{0x40000000000}, 479 ""); 480 static_assert( 481 bit_ceil(uint64_t{0x8000000000000000}) == uint64_t{0x8000000000000000}, 482 ""); 483 484 EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x0}>(0))); 485 EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x80}>(0))); 486 EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x81}>(0))); 487 EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0xff}>(0))); 488 489 EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x0}>(0))); 490 EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8000}>(0))); 491 EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8001}>(0))); 492 EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0xffff}>(0))); 493 494 EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x0}>(0))); 495 EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000000}>(0))); 496 EXPECT_FALSE( 497 (IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000001}>(0))); 498 EXPECT_FALSE( 499 (IsBitCeilConstantExpression<uint32_t, uint32_t{0xffffffff}>(0))); 500 501 EXPECT_TRUE((IsBitCeilConstantExpression<uint64_t, uint64_t{0x0}>(0))); 502 EXPECT_TRUE( 503 (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000000}>(0))); 504 EXPECT_FALSE( 505 (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000001}>(0))); 506 EXPECT_FALSE( 507 (IsBitCeilConstantExpression<uint64_t, uint64_t{0xffffffffffffffff}>(0))); 508 #endif 509 510 EXPECT_EQ(bit_ceil(0u), 1); 511 EXPECT_EQ(bit_ceil(1u), 1); 512 EXPECT_EQ(bit_ceil(2u), 2); 513 EXPECT_EQ(bit_ceil(3u), 4); 514 EXPECT_EQ(bit_ceil(4u), 4); 515 EXPECT_EQ(bit_ceil(1337u), 2048); 516 EXPECT_EQ(bit_ceil(65536u), 65536); 517 EXPECT_EQ(bit_ceil(65536u - 1337u), 65536); 518 EXPECT_EQ(bit_ceil(uint64_t{0x40000000000}), uint64_t{0x40000000000}); 519 } 520 521 TEST(IntegralPowersOfTwo, Floor) { 522 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 523 static_assert(bit_floor(0u) == 0, ""); 524 static_assert(bit_floor(1u) == 1, ""); 525 static_assert(bit_floor(2u) == 2, ""); 526 static_assert(bit_floor(3u) == 2, ""); 527 static_assert(bit_floor(4u) == 4, ""); 528 static_assert(bit_floor(1337u) == 1024, ""); 529 static_assert(bit_floor(65536u) == 65536, ""); 530 static_assert(bit_floor(65536u - 1337u) == 32768, ""); 531 static_assert(bit_floor(uint64_t{0x40000000000}) == uint64_t{0x40000000000}, 532 ""); 533 #endif 534 535 EXPECT_EQ(bit_floor(0u), 0); 536 EXPECT_EQ(bit_floor(1u), 1); 537 EXPECT_EQ(bit_floor(2u), 2); 538 EXPECT_EQ(bit_floor(3u), 2); 539 EXPECT_EQ(bit_floor(4u), 4); 540 EXPECT_EQ(bit_floor(1337u), 1024); 541 EXPECT_EQ(bit_floor(65536u), 65536); 542 EXPECT_EQ(bit_floor(65536u - 1337u), 32768); 543 EXPECT_EQ(bit_floor(uint64_t{0x40000000000}), uint64_t{0x40000000000}); 544 545 for (int i = 0; i < 8; i++) { 546 uint8_t input = uint8_t{1} << i; 547 EXPECT_EQ(bit_floor(input), input); 548 if (i > 0) { 549 EXPECT_EQ(bit_floor(static_cast<uint8_t>(input + 1)), input); 550 } 551 } 552 553 for (int i = 0; i < 16; i++) { 554 uint16_t input = uint16_t{1} << i; 555 EXPECT_EQ(bit_floor(input), input); 556 if (i > 0) { 557 EXPECT_EQ(bit_floor(static_cast<uint16_t>(input + 1)), input); 558 } 559 } 560 561 for (int i = 0; i < 32; i++) { 562 uint32_t input = uint32_t{1} << i; 563 EXPECT_EQ(bit_floor(input), input); 564 if (i > 0) { 565 EXPECT_EQ(bit_floor(input + 1), input); 566 } 567 } 568 569 for (int i = 0; i < 64; i++) { 570 uint64_t input = uint64_t{1} << i; 571 EXPECT_EQ(bit_floor(input), input); 572 if (i > 0) { 573 EXPECT_EQ(bit_floor(input + 1), input); 574 } 575 } 576 } 577 578 TEST(IntegralPowersOfTwo, Width) { 579 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 580 static_assert(bit_width(uint8_t{}) == 0, ""); 581 static_assert(bit_width(uint8_t{1}) == 1, ""); 582 static_assert(bit_width(uint8_t{3}) == 2, ""); 583 static_assert(bit_width(static_cast<uint8_t>(-1)) == 8, ""); 584 static_assert(bit_width(uint16_t{}) == 0, ""); 585 static_assert(bit_width(uint16_t{1}) == 1, ""); 586 static_assert(bit_width(uint16_t{3}) == 2, ""); 587 static_assert(bit_width(static_cast<uint16_t>(-1)) == 16, ""); 588 static_assert(bit_width(uint32_t{}) == 0, ""); 589 static_assert(bit_width(uint32_t{1}) == 1, ""); 590 static_assert(bit_width(uint32_t{3}) == 2, ""); 591 static_assert(bit_width(~uint32_t{}) == 32, ""); 592 static_assert(bit_width(uint64_t{}) == 0, ""); 593 static_assert(bit_width(uint64_t{1}) == 1, ""); 594 static_assert(bit_width(uint64_t{3}) == 2, ""); 595 static_assert(bit_width(~uint64_t{}) == 64, ""); 596 #endif 597 598 EXPECT_EQ(bit_width(uint8_t{}), 0); 599 EXPECT_EQ(bit_width(uint8_t{1}), 1); 600 EXPECT_EQ(bit_width(uint8_t{3}), 2); 601 EXPECT_EQ(bit_width(static_cast<uint8_t>(-1)), 8); 602 EXPECT_EQ(bit_width(uint16_t{}), 0); 603 EXPECT_EQ(bit_width(uint16_t{1}), 1); 604 EXPECT_EQ(bit_width(uint16_t{3}), 2); 605 EXPECT_EQ(bit_width(static_cast<uint16_t>(-1)), 16); 606 EXPECT_EQ(bit_width(uint32_t{}), 0); 607 EXPECT_EQ(bit_width(uint32_t{1}), 1); 608 EXPECT_EQ(bit_width(uint32_t{3}), 2); 609 EXPECT_EQ(bit_width(~uint32_t{}), 32); 610 EXPECT_EQ(bit_width(uint64_t{}), 0); 611 EXPECT_EQ(bit_width(uint64_t{1}), 1); 612 EXPECT_EQ(bit_width(uint64_t{3}), 2); 613 EXPECT_EQ(bit_width(~uint64_t{}), 64); 614 615 for (int i = 0; i < 8; i++) { 616 EXPECT_EQ(bit_width(static_cast<uint8_t>(uint8_t{1} << i)), i + 1); 617 } 618 619 for (int i = 0; i < 16; i++) { 620 EXPECT_EQ(bit_width(static_cast<uint16_t>(uint16_t{1} << i)), i + 1); 621 } 622 623 for (int i = 0; i < 32; i++) { 624 EXPECT_EQ(bit_width(uint32_t{1} << i), i + 1); 625 } 626 627 for (int i = 0; i < 64; i++) { 628 EXPECT_EQ(bit_width(uint64_t{1} << i), i + 1); 629 } 630 } 631 632 // On GCC and Clang, anticiapte that implementations will be constexpr 633 #if defined(__GNUC__) 634 static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT, 635 "popcount should be constexpr"); 636 static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_CLZ, "clz should be constexpr"); 637 static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_CTZ, "ctz should be constexpr"); 638 #endif 639 640 TEST(Endian, Comparison) { 641 #if defined(ABSL_IS_LITTLE_ENDIAN) 642 static_assert(absl::endian::native == absl::endian::little); 643 static_assert(absl::endian::native != absl::endian::big); 644 #endif 645 #if defined(ABSL_IS_BIG_ENDIAN) 646 static_assert(absl::endian::native != absl::endian::little); 647 static_assert(absl::endian::native == absl::endian::big); 648 #endif 649 } 650 651 TEST(Byteswap, Constexpr) { 652 static_assert(absl::byteswap<int8_t>(0x12) == 0x12); 653 static_assert(absl::byteswap<int16_t>(0x1234) == 0x3412); 654 static_assert(absl::byteswap<int32_t>(0x12345678) == 0x78563412); 655 static_assert(absl::byteswap<int64_t>(0x123456789abcdef0) == 656 static_cast<int64_t>(0xf0debc9a78563412)); 657 static_assert(absl::byteswap<uint8_t>(0x21) == 0x21); 658 static_assert(absl::byteswap<uint16_t>(0x4321) == 0x2143); 659 static_assert(absl::byteswap<uint32_t>(0x87654321) == 0x21436587); 660 static_assert(absl::byteswap<uint64_t>(0xfedcba9876543210) == 661 static_cast<uint64_t>(0x1032547698badcfe)); 662 static_assert(absl::byteswap<int32_t>(static_cast<int32_t>(0xdeadbeef)) == 663 static_cast<int32_t>(0xefbeadde)); 664 } 665 666 TEST(Byteswap, NotConstexpr) { 667 int8_t a = 0x12; 668 int16_t b = 0x1234; 669 int32_t c = 0x12345678; 670 int64_t d = 0x123456789abcdef0; 671 uint8_t e = 0x21; 672 uint16_t f = 0x4321; 673 uint32_t g = 0x87654321; 674 uint64_t h = 0xfedcba9876543210; 675 EXPECT_EQ(absl::byteswap<int8_t>(a), 0x12); 676 EXPECT_EQ(absl::byteswap<int16_t>(b), 0x3412); 677 EXPECT_EQ(absl::byteswap(c), 0x78563412); 678 EXPECT_EQ(absl::byteswap(d), 0xf0debc9a78563412); 679 EXPECT_EQ(absl::byteswap<uint8_t>(e), 0x21); 680 EXPECT_EQ(absl::byteswap<uint16_t>(f), 0x2143); 681 EXPECT_EQ(absl::byteswap(g), 0x21436587); 682 EXPECT_EQ(absl::byteswap(h), 0x1032547698badcfe); 683 EXPECT_EQ(absl::byteswap(absl::byteswap<int8_t>(a)), a); 684 EXPECT_EQ(absl::byteswap(absl::byteswap<int16_t>(b)), b); 685 EXPECT_EQ(absl::byteswap(absl::byteswap(c)), c); 686 EXPECT_EQ(absl::byteswap(absl::byteswap(d)), d); 687 EXPECT_EQ(absl::byteswap(absl::byteswap<uint8_t>(e)), e); 688 EXPECT_EQ(absl::byteswap(absl::byteswap<uint16_t>(f)), f); 689 EXPECT_EQ(absl::byteswap(absl::byteswap(g)), g); 690 EXPECT_EQ(absl::byteswap(absl::byteswap(h)), h); 691 EXPECT_EQ(absl::byteswap<uint32_t>(0xdeadbeef), 0xefbeadde); 692 EXPECT_EQ(absl::byteswap<const uint32_t>(0xdeadbeef), 0xefbeadde); 693 } 694 695 } // namespace 696 ABSL_NAMESPACE_END 697 } // namespace absl