1 //===-- Unittests for Bit -------------------------------------------------===// 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 "src/__support/CPP/bit.h" 10 #include "src/__support/big_int.h" 11 #include "src/__support/macros/config.h" 12 #include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128 13 #include "test/UnitTest/Test.h" 14 15 #include <stdint.h> 16 17 namespace LIBC_NAMESPACE_DECL { 18 namespace cpp { 19 20 using UnsignedTypes = testing::TypeList< 21 #if defined(LIBC_TYPES_HAS_INT128) 22 __uint128_t, 23 #endif // LIBC_TYPES_HAS_INT128 24 unsigned char, unsigned short, unsigned int, unsigned long, 25 unsigned long long, UInt<128>>; 26 27 TYPED_TEST(LlvmLibcBitTest, HasSingleBit, UnsignedTypes) { 28 constexpr auto ZERO = T(0); 29 constexpr auto ALL_ONES = T(~ZERO); 30 EXPECT_FALSE(has_single_bit<T>(ZERO)); 31 EXPECT_FALSE(has_single_bit<T>(ALL_ONES)); 32 33 for (T value = 1; value; value <<= 1) 34 EXPECT_TRUE(has_single_bit<T>(value)); 35 36 // We test that if two bits are set has_single_bit returns false. 37 // We do this by setting the highest or lowest bit depending or where the 38 // current bit is. This is a bit convoluted but it helps catch a bug on BigInt 39 // where we have to work on an element-by-element basis. 40 constexpr auto MIDPOINT = T(ALL_ONES / 2); 41 constexpr auto LSB = T(1); 42 constexpr auto MSB = T(~(ALL_ONES >> 1)); 43 for (T value = 1; value; value <<= 1) { 44 auto two_bits_value = value | ((value <= MIDPOINT) ? MSB : LSB); 45 EXPECT_FALSE(has_single_bit<T>(two_bits_value)); 46 } 47 } 48 49 TYPED_TEST(LlvmLibcBitTest, CountLZero, UnsignedTypes) { 50 EXPECT_EQ(countl_zero<T>(T(0)), cpp::numeric_limits<T>::digits); 51 int expected = 0; 52 for (T value = ~T(0); value; value >>= 1, ++expected) 53 EXPECT_EQ(countl_zero<T>(value), expected); 54 } 55 56 TYPED_TEST(LlvmLibcBitTest, CountRZero, UnsignedTypes) { 57 EXPECT_EQ(countr_zero<T>(T(0)), cpp::numeric_limits<T>::digits); 58 int expected = 0; 59 for (T value = ~T(0); value; value <<= 1, ++expected) 60 EXPECT_EQ(countr_zero<T>(value), expected); 61 } 62 63 TYPED_TEST(LlvmLibcBitTest, CountLOne, UnsignedTypes) { 64 EXPECT_EQ(countl_one<T>(T(0)), 0); 65 int expected = cpp::numeric_limits<T>::digits; 66 for (T value = ~T(0); value; value <<= 1, --expected) 67 EXPECT_EQ(countl_one<T>(value), expected); 68 } 69 70 TYPED_TEST(LlvmLibcBitTest, CountROne, UnsignedTypes) { 71 EXPECT_EQ(countr_one<T>(T(0)), 0); 72 int expected = cpp::numeric_limits<T>::digits; 73 for (T value = ~T(0); value; value >>= 1, --expected) 74 EXPECT_EQ(countr_one<T>(value), expected); 75 } 76 77 TYPED_TEST(LlvmLibcBitTest, BitWidth, UnsignedTypes) { 78 EXPECT_EQ(bit_width<T>(T(0)), 0); 79 int one_index = 0; 80 for (T value = 1; value; value <<= 1, ++one_index) 81 EXPECT_EQ(bit_width<T>(value), one_index + 1); 82 } 83 84 TEST(LlvmLibcBitTest, BitCeil) { 85 EXPECT_EQ(uint8_t(1), bit_ceil(uint8_t(0))); 86 EXPECT_EQ(uint16_t(1), bit_ceil(uint16_t(0))); 87 EXPECT_EQ(uint32_t(1), bit_ceil(uint32_t(0))); 88 EXPECT_EQ(uint64_t(1), bit_ceil(uint64_t(0))); 89 90 EXPECT_EQ(uint8_t(1), bit_ceil(uint8_t(1))); 91 EXPECT_EQ(uint16_t(1), bit_ceil(uint16_t(1))); 92 EXPECT_EQ(uint32_t(1), bit_ceil(uint32_t(1))); 93 EXPECT_EQ(uint64_t(1), bit_ceil(uint64_t(1))); 94 95 EXPECT_EQ(uint8_t(2), bit_ceil(uint8_t(2))); 96 EXPECT_EQ(uint16_t(2), bit_ceil(uint16_t(2))); 97 EXPECT_EQ(uint32_t(2), bit_ceil(uint32_t(2))); 98 EXPECT_EQ(uint64_t(2), bit_ceil(uint64_t(2))); 99 100 EXPECT_EQ(uint8_t(4), bit_ceil(uint8_t(3))); 101 EXPECT_EQ(uint16_t(4), bit_ceil(uint16_t(3))); 102 EXPECT_EQ(uint32_t(4), bit_ceil(uint32_t(3))); 103 EXPECT_EQ(uint64_t(4), bit_ceil(uint64_t(3))); 104 105 EXPECT_EQ(uint8_t(4), bit_ceil(uint8_t(4))); 106 EXPECT_EQ(uint16_t(4), bit_ceil(uint16_t(4))); 107 EXPECT_EQ(uint32_t(4), bit_ceil(uint32_t(4))); 108 EXPECT_EQ(uint64_t(4), bit_ceil(uint64_t(4))); 109 110 // The result is the representable power of 2 for each type. 111 EXPECT_EQ(uint8_t(0x80), bit_ceil(uint8_t(0x7f))); 112 EXPECT_EQ(uint16_t(0x8000), bit_ceil(uint16_t(0x7fff))); 113 EXPECT_EQ(uint32_t(0x80000000), bit_ceil(uint32_t(0x7fffffff))); 114 EXPECT_EQ(uint64_t(0x8000000000000000), 115 bit_ceil(uint64_t(0x7fffffffffffffff))); 116 } 117 118 TEST(LlvmLibcBitTest, BitFloor) { 119 EXPECT_EQ(uint8_t(0), bit_floor(uint8_t(0))); 120 EXPECT_EQ(uint16_t(0), bit_floor(uint16_t(0))); 121 EXPECT_EQ(uint32_t(0), bit_floor(uint32_t(0))); 122 EXPECT_EQ(uint64_t(0), bit_floor(uint64_t(0))); 123 124 EXPECT_EQ(uint8_t(1), bit_floor(uint8_t(1))); 125 EXPECT_EQ(uint16_t(1), bit_floor(uint16_t(1))); 126 EXPECT_EQ(uint32_t(1), bit_floor(uint32_t(1))); 127 EXPECT_EQ(uint64_t(1), bit_floor(uint64_t(1))); 128 129 EXPECT_EQ(uint8_t(2), bit_floor(uint8_t(2))); 130 EXPECT_EQ(uint16_t(2), bit_floor(uint16_t(2))); 131 EXPECT_EQ(uint32_t(2), bit_floor(uint32_t(2))); 132 EXPECT_EQ(uint64_t(2), bit_floor(uint64_t(2))); 133 134 EXPECT_EQ(uint8_t(2), bit_floor(uint8_t(3))); 135 EXPECT_EQ(uint16_t(2), bit_floor(uint16_t(3))); 136 EXPECT_EQ(uint32_t(2), bit_floor(uint32_t(3))); 137 EXPECT_EQ(uint64_t(2), bit_floor(uint64_t(3))); 138 139 EXPECT_EQ(uint8_t(4), bit_floor(uint8_t(4))); 140 EXPECT_EQ(uint16_t(4), bit_floor(uint16_t(4))); 141 EXPECT_EQ(uint32_t(4), bit_floor(uint32_t(4))); 142 EXPECT_EQ(uint64_t(4), bit_floor(uint64_t(4))); 143 144 EXPECT_EQ(uint8_t(0x40), bit_floor(uint8_t(0x7f))); 145 EXPECT_EQ(uint16_t(0x4000), bit_floor(uint16_t(0x7fff))); 146 EXPECT_EQ(uint32_t(0x40000000), bit_floor(uint32_t(0x7fffffff))); 147 EXPECT_EQ(uint64_t(0x4000000000000000), 148 bit_floor(uint64_t(0x7fffffffffffffffull))); 149 150 EXPECT_EQ(uint8_t(0x80), bit_floor(uint8_t(0x80))); 151 EXPECT_EQ(uint16_t(0x8000), bit_floor(uint16_t(0x8000))); 152 EXPECT_EQ(uint32_t(0x80000000), bit_floor(uint32_t(0x80000000))); 153 EXPECT_EQ(uint64_t(0x8000000000000000), 154 bit_floor(uint64_t(0x8000000000000000))); 155 156 EXPECT_EQ(uint8_t(0x80), bit_floor(uint8_t(0xff))); 157 EXPECT_EQ(uint16_t(0x8000), bit_floor(uint16_t(0xffff))); 158 EXPECT_EQ(uint32_t(0x80000000), bit_floor(uint32_t(0xffffffff))); 159 EXPECT_EQ(uint64_t(0x8000000000000000), 160 bit_floor(uint64_t(0xffffffffffffffff))); 161 } 162 163 TYPED_TEST(LlvmLibcBitTest, RotateIsInvariantForZeroAndOne, UnsignedTypes) { 164 constexpr T all_zeros = T(0); 165 constexpr T all_ones = ~T(0); 166 for (int i = 0; i < cpp::numeric_limits<T>::digits; ++i) { 167 EXPECT_EQ(rotl<T>(all_zeros, i), all_zeros); 168 EXPECT_EQ(rotl<T>(all_ones, i), all_ones); 169 EXPECT_EQ(rotr<T>(all_zeros, i), all_zeros); 170 EXPECT_EQ(rotr<T>(all_ones, i), all_ones); 171 } 172 } 173 174 TEST(LlvmLibcBitTest, Rotl) { 175 EXPECT_EQ(uint8_t(0x53U), rotl<uint8_t>(0x53, 0)); 176 EXPECT_EQ(uint8_t(0x4dU), rotl<uint8_t>(0x53, 2)); 177 EXPECT_EQ(uint8_t(0xa6U), rotl<uint8_t>(0x53, 9)); 178 EXPECT_EQ(uint8_t(0x9aU), rotl<uint8_t>(0x53, -5)); 179 180 EXPECT_EQ(uint16_t(0xabcdU), rotl<uint16_t>(0xabcd, 0)); 181 EXPECT_EQ(uint16_t(0xf36aU), rotl<uint16_t>(0xabcd, 6)); 182 EXPECT_EQ(uint16_t(0xaf36U), rotl<uint16_t>(0xabcd, 18)); 183 EXPECT_EQ(uint16_t(0xf36aU), rotl<uint16_t>(0xabcd, -10)); 184 185 EXPECT_EQ(uint32_t(0xdeadbeefU), rotl<uint32_t>(0xdeadbeef, 0)); 186 EXPECT_EQ(uint32_t(0x7ddfbd5bU), rotl<uint32_t>(0xdeadbeef, 17)); 187 EXPECT_EQ(uint32_t(0x5b7ddfbdU), rotl<uint32_t>(0xdeadbeef, 41)); 188 EXPECT_EQ(uint32_t(0xb6fbbf7aU), rotl<uint32_t>(0xdeadbeef, -22)); 189 190 EXPECT_EQ(uint64_t(0x12345678deadbeefULL), 191 rotl<uint64_t>(0x12345678deadbeefULL, 0)); 192 EXPECT_EQ(uint64_t(0xf56df77891a2b3c6ULL), 193 rotl<uint64_t>(0x12345678deadbeefULL, 35)); 194 EXPECT_EQ(uint64_t(0x8d159e37ab6fbbc4ULL), 195 rotl<uint64_t>(0x12345678deadbeefULL, 70)); 196 EXPECT_EQ(uint64_t(0xb7dde2468acf1bd5ULL), 197 rotl<uint64_t>(0x12345678deadbeefULL, -19)); 198 } 199 200 TEST(LlvmLibcBitTest, Rotr) { 201 EXPECT_EQ(uint8_t(0x53U), rotr<uint8_t>(0x53, 0)); 202 EXPECT_EQ(uint8_t(0xd4U), rotr<uint8_t>(0x53, 2)); 203 EXPECT_EQ(uint8_t(0xa9U), rotr<uint8_t>(0x53, 9)); 204 EXPECT_EQ(uint8_t(0x6aU), rotr<uint8_t>(0x53, -5)); 205 206 EXPECT_EQ(uint16_t(0xabcdU), rotr<uint16_t>(0xabcd, 0)); 207 EXPECT_EQ(uint16_t(0x36afU), rotr<uint16_t>(0xabcd, 6)); 208 EXPECT_EQ(uint16_t(0x6af3U), rotr<uint16_t>(0xabcd, 18)); 209 EXPECT_EQ(uint16_t(0x36afU), rotr<uint16_t>(0xabcd, -10)); 210 211 EXPECT_EQ(uint32_t(0xdeadbeefU), rotr<uint32_t>(0xdeadbeef, 0)); 212 EXPECT_EQ(uint32_t(0xdf77ef56U), rotr<uint32_t>(0xdeadbeef, 17)); 213 EXPECT_EQ(uint32_t(0x77ef56dfU), rotr<uint32_t>(0xdeadbeef, 41)); 214 EXPECT_EQ(uint32_t(0xbbf7ab6fU), rotr<uint32_t>(0xdeadbeef, -22)); 215 216 EXPECT_EQ(uint64_t(0x12345678deadbeefULL), 217 rotr<uint64_t>(0x12345678deadbeefULL, 0)); 218 EXPECT_EQ(uint64_t(0x1bd5b7dde2468acfULL), 219 rotr<uint64_t>(0x12345678deadbeefULL, 35)); 220 EXPECT_EQ(uint64_t(0xbc48d159e37ab6fbULL), 221 rotr<uint64_t>(0x12345678deadbeefULL, 70)); 222 EXPECT_EQ(uint64_t(0xb3c6f56df77891a2ULL), 223 rotr<uint64_t>(0x12345678deadbeefULL, -19)); 224 } 225 226 TYPED_TEST(LlvmLibcBitTest, CountOnes, UnsignedTypes) { 227 EXPECT_EQ(popcount(T(0)), 0); 228 for (int i = 0; i != cpp::numeric_limits<T>::digits; ++i) 229 EXPECT_EQ(popcount<T>(cpp::numeric_limits<T>::max() >> i), 230 cpp::numeric_limits<T>::digits - i); 231 } 232 233 } // namespace cpp 234 } // namespace LIBC_NAMESPACE_DECL 235