1 //===- unittests/Support/MathExtrasTest.cpp - math utils tests ------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "gtest/gtest.h" 11 #include "llvm/Support/MathExtras.h" 12 13 using namespace llvm; 14 15 namespace { 16 17 TEST(MathExtras, countTrailingZeros) { 18 uint8_t Z8 = 0; 19 uint16_t Z16 = 0; 20 uint32_t Z32 = 0; 21 uint64_t Z64 = 0; 22 EXPECT_EQ(8u, countTrailingZeros(Z8)); 23 EXPECT_EQ(16u, countTrailingZeros(Z16)); 24 EXPECT_EQ(32u, countTrailingZeros(Z32)); 25 EXPECT_EQ(64u, countTrailingZeros(Z64)); 26 27 uint8_t NZ8 = 42; 28 uint16_t NZ16 = 42; 29 uint32_t NZ32 = 42; 30 uint64_t NZ64 = 42; 31 EXPECT_EQ(1u, countTrailingZeros(NZ8)); 32 EXPECT_EQ(1u, countTrailingZeros(NZ16)); 33 EXPECT_EQ(1u, countTrailingZeros(NZ32)); 34 EXPECT_EQ(1u, countTrailingZeros(NZ64)); 35 } 36 37 TEST(MathExtras, countLeadingZeros) { 38 uint8_t Z8 = 0; 39 uint16_t Z16 = 0; 40 uint32_t Z32 = 0; 41 uint64_t Z64 = 0; 42 EXPECT_EQ(8u, countLeadingZeros(Z8)); 43 EXPECT_EQ(16u, countLeadingZeros(Z16)); 44 EXPECT_EQ(32u, countLeadingZeros(Z32)); 45 EXPECT_EQ(64u, countLeadingZeros(Z64)); 46 47 uint8_t NZ8 = 42; 48 uint16_t NZ16 = 42; 49 uint32_t NZ32 = 42; 50 uint64_t NZ64 = 42; 51 EXPECT_EQ(2u, countLeadingZeros(NZ8)); 52 EXPECT_EQ(10u, countLeadingZeros(NZ16)); 53 EXPECT_EQ(26u, countLeadingZeros(NZ32)); 54 EXPECT_EQ(58u, countLeadingZeros(NZ64)); 55 56 EXPECT_EQ(8u, countLeadingZeros(0x00F000FFu)); 57 EXPECT_EQ(8u, countLeadingZeros(0x00F12345u)); 58 for (unsigned i = 0; i <= 30; ++i) { 59 EXPECT_EQ(31 - i, countLeadingZeros(1u << i)); 60 } 61 62 EXPECT_EQ(8u, countLeadingZeros(0x00F1234500F12345ULL)); 63 EXPECT_EQ(1u, countLeadingZeros(1ULL << 62)); 64 for (unsigned i = 0; i <= 62; ++i) { 65 EXPECT_EQ(63 - i, countLeadingZeros(1ULL << i)); 66 } 67 } 68 69 TEST(MathExtras, findFirstSet) { 70 uint8_t Z8 = 0; 71 uint16_t Z16 = 0; 72 uint32_t Z32 = 0; 73 uint64_t Z64 = 0; 74 EXPECT_EQ(0xFFULL, findFirstSet(Z8)); 75 EXPECT_EQ(0xFFFFULL, findFirstSet(Z16)); 76 EXPECT_EQ(0xFFFFFFFFULL, findFirstSet(Z32)); 77 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, findFirstSet(Z64)); 78 79 uint8_t NZ8 = 42; 80 uint16_t NZ16 = 42; 81 uint32_t NZ32 = 42; 82 uint64_t NZ64 = 42; 83 EXPECT_EQ(1u, findFirstSet(NZ8)); 84 EXPECT_EQ(1u, findFirstSet(NZ16)); 85 EXPECT_EQ(1u, findFirstSet(NZ32)); 86 EXPECT_EQ(1u, findFirstSet(NZ64)); 87 } 88 89 TEST(MathExtras, findLastSet) { 90 uint8_t Z8 = 0; 91 uint16_t Z16 = 0; 92 uint32_t Z32 = 0; 93 uint64_t Z64 = 0; 94 EXPECT_EQ(0xFFULL, findLastSet(Z8)); 95 EXPECT_EQ(0xFFFFULL, findLastSet(Z16)); 96 EXPECT_EQ(0xFFFFFFFFULL, findLastSet(Z32)); 97 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, findLastSet(Z64)); 98 99 uint8_t NZ8 = 42; 100 uint16_t NZ16 = 42; 101 uint32_t NZ32 = 42; 102 uint64_t NZ64 = 42; 103 EXPECT_EQ(5u, findLastSet(NZ8)); 104 EXPECT_EQ(5u, findLastSet(NZ16)); 105 EXPECT_EQ(5u, findLastSet(NZ32)); 106 EXPECT_EQ(5u, findLastSet(NZ64)); 107 } 108 109 TEST(MathExtras, reverseBits) { 110 uint8_t NZ8 = 42; 111 uint16_t NZ16 = 42; 112 uint32_t NZ32 = 42; 113 uint64_t NZ64 = 42; 114 EXPECT_EQ(0x54ULL, reverseBits(NZ8)); 115 EXPECT_EQ(0x5400ULL, reverseBits(NZ16)); 116 EXPECT_EQ(0x54000000ULL, reverseBits(NZ32)); 117 EXPECT_EQ(0x5400000000000000ULL, reverseBits(NZ64)); 118 } 119 120 TEST(MathExtras, isPowerOf2_32) { 121 EXPECT_TRUE(isPowerOf2_32(1 << 6)); 122 EXPECT_TRUE(isPowerOf2_32(1 << 12)); 123 EXPECT_FALSE(isPowerOf2_32((1 << 19) + 3)); 124 EXPECT_FALSE(isPowerOf2_32(0xABCDEF0)); 125 } 126 127 TEST(MathExtras, isPowerOf2_64) { 128 EXPECT_TRUE(isPowerOf2_64(1LL << 46)); 129 EXPECT_TRUE(isPowerOf2_64(1LL << 12)); 130 EXPECT_FALSE(isPowerOf2_64((1LL << 53) + 3)); 131 EXPECT_FALSE(isPowerOf2_64(0xABCDEF0ABCDEF0LL)); 132 } 133 134 TEST(MathExtras, ByteSwap_32) { 135 EXPECT_EQ(0x44332211u, ByteSwap_32(0x11223344)); 136 EXPECT_EQ(0xDDCCBBAAu, ByteSwap_32(0xAABBCCDD)); 137 } 138 139 TEST(MathExtras, ByteSwap_64) { 140 EXPECT_EQ(0x8877665544332211ULL, ByteSwap_64(0x1122334455667788LL)); 141 EXPECT_EQ(0x1100FFEEDDCCBBAAULL, ByteSwap_64(0xAABBCCDDEEFF0011LL)); 142 } 143 144 TEST(MathExtras, countLeadingOnes) { 145 for (int i = 30; i >= 0; --i) { 146 // Start with all ones and unset some bit. 147 EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i))); 148 } 149 for (int i = 62; i >= 0; --i) { 150 // Start with all ones and unset some bit. 151 EXPECT_EQ(63u - i, countLeadingOnes(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i))); 152 } 153 for (int i = 30; i >= 0; --i) { 154 // Start with all ones and unset some bit. 155 EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i))); 156 } 157 } 158 159 TEST(MathExtras, FloatBits) { 160 static const float kValue = 5632.34f; 161 EXPECT_FLOAT_EQ(kValue, BitsToFloat(FloatToBits(kValue))); 162 } 163 164 TEST(MathExtras, DoubleBits) { 165 static const double kValue = 87987234.983498; 166 EXPECT_FLOAT_EQ(kValue, BitsToDouble(DoubleToBits(kValue))); 167 } 168 169 TEST(MathExtras, MinAlign) { 170 EXPECT_EQ(1u, MinAlign(2, 3)); 171 EXPECT_EQ(2u, MinAlign(2, 4)); 172 EXPECT_EQ(1u, MinAlign(17, 64)); 173 EXPECT_EQ(256u, MinAlign(256, 512)); 174 } 175 176 TEST(MathExtras, NextPowerOf2) { 177 EXPECT_EQ(4u, NextPowerOf2(3)); 178 EXPECT_EQ(16u, NextPowerOf2(15)); 179 EXPECT_EQ(256u, NextPowerOf2(128)); 180 } 181 182 TEST(MathExtras, RoundUpToAlignment) { 183 EXPECT_EQ(8u, RoundUpToAlignment(5, 8)); 184 EXPECT_EQ(24u, RoundUpToAlignment(17, 8)); 185 EXPECT_EQ(0u, RoundUpToAlignment(~0LL, 8)); 186 187 EXPECT_EQ(7u, RoundUpToAlignment(5, 8, 7)); 188 EXPECT_EQ(17u, RoundUpToAlignment(17, 8, 1)); 189 EXPECT_EQ(3u, RoundUpToAlignment(~0LL, 8, 3)); 190 EXPECT_EQ(552u, RoundUpToAlignment(321, 255, 42)); 191 } 192 193 template<typename T> 194 void SaturatingAddTestHelper() 195 { 196 const T Max = std::numeric_limits<T>::max(); 197 bool ResultOverflowed; 198 199 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2))); 200 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), &ResultOverflowed)); 201 EXPECT_FALSE(ResultOverflowed); 202 203 EXPECT_EQ(Max, SaturatingAdd(Max, T(1))); 204 EXPECT_EQ(Max, SaturatingAdd(Max, T(1), &ResultOverflowed)); 205 EXPECT_TRUE(ResultOverflowed); 206 207 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1))); 208 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), &ResultOverflowed)); 209 EXPECT_FALSE(ResultOverflowed); 210 211 EXPECT_EQ(Max, SaturatingAdd(T(1), Max)); 212 EXPECT_EQ(Max, SaturatingAdd(T(1), Max, &ResultOverflowed)); 213 EXPECT_TRUE(ResultOverflowed); 214 215 EXPECT_EQ(Max, SaturatingAdd(Max, Max)); 216 EXPECT_EQ(Max, SaturatingAdd(Max, Max, &ResultOverflowed)); 217 EXPECT_TRUE(ResultOverflowed); 218 } 219 220 TEST(MathExtras, SaturatingAdd) { 221 SaturatingAddTestHelper<uint8_t>(); 222 SaturatingAddTestHelper<uint16_t>(); 223 SaturatingAddTestHelper<uint32_t>(); 224 SaturatingAddTestHelper<uint64_t>(); 225 } 226 227 template<typename T> 228 void SaturatingMultiplyTestHelper() 229 { 230 const T Max = std::numeric_limits<T>::max(); 231 bool ResultOverflowed; 232 233 // Test basic multiplication. 234 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3))); 235 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), &ResultOverflowed)); 236 EXPECT_FALSE(ResultOverflowed); 237 238 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2))); 239 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), &ResultOverflowed)); 240 EXPECT_FALSE(ResultOverflowed); 241 242 // Test multiplication by zero. 243 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0))); 244 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), &ResultOverflowed)); 245 EXPECT_FALSE(ResultOverflowed); 246 247 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0))); 248 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), &ResultOverflowed)); 249 EXPECT_FALSE(ResultOverflowed); 250 251 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1))); 252 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), &ResultOverflowed)); 253 EXPECT_FALSE(ResultOverflowed); 254 255 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0))); 256 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), &ResultOverflowed)); 257 EXPECT_FALSE(ResultOverflowed); 258 259 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max)); 260 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, &ResultOverflowed)); 261 EXPECT_FALSE(ResultOverflowed); 262 263 // Test multiplication by maximum value. 264 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2))); 265 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), &ResultOverflowed)); 266 EXPECT_TRUE(ResultOverflowed); 267 268 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max)); 269 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, &ResultOverflowed)); 270 EXPECT_TRUE(ResultOverflowed); 271 272 EXPECT_EQ(Max, SaturatingMultiply(Max, Max)); 273 EXPECT_EQ(Max, SaturatingMultiply(Max, Max, &ResultOverflowed)); 274 EXPECT_TRUE(ResultOverflowed); 275 276 // Test interesting boundary conditions for algorithm - 277 // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1] 278 // and A + B == std::numeric_limits<T>::digits. 279 // We expect overflow iff A > B and K = 1. 280 const int Digits = std::numeric_limits<T>::digits; 281 for (int A = 1, B = Digits - 1; B >= 1; ++A, --B) { 282 for (int K = -1; K <= 1; ++K) { 283 T X = (T(1) << A) - T(1); 284 T Y = (T(1) << B) + K; 285 bool OverflowExpected = A > B && K == 1; 286 287 if(OverflowExpected) { 288 EXPECT_EQ(Max, SaturatingMultiply(X, Y)); 289 EXPECT_EQ(Max, SaturatingMultiply(X, Y, &ResultOverflowed)); 290 EXPECT_TRUE(ResultOverflowed); 291 } else { 292 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y)); 293 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, &ResultOverflowed)); 294 EXPECT_FALSE(ResultOverflowed); 295 } 296 } 297 } 298 } 299 300 TEST(MathExtras, SaturatingMultiply) { 301 SaturatingMultiplyTestHelper<uint8_t>(); 302 SaturatingMultiplyTestHelper<uint16_t>(); 303 SaturatingMultiplyTestHelper<uint32_t>(); 304 SaturatingMultiplyTestHelper<uint64_t>(); 305 } 306 307 } 308
