1 //===- unittests/Support/MathExtrasTest.cpp - math utils 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/Support/MathExtras.h" 10 #include "gtest/gtest.h" 11 #include <limits> 12 13 using namespace llvm; 14 15 namespace { 16 17 TEST(MathExtras, onesMask) { 18 EXPECT_EQ(0U, maskLeadingOnes<uint8_t>(0)); 19 EXPECT_EQ(0U, maskTrailingOnes<uint8_t>(0)); 20 EXPECT_EQ(0U, maskLeadingOnes<uint16_t>(0)); 21 EXPECT_EQ(0U, maskTrailingOnes<uint16_t>(0)); 22 EXPECT_EQ(0U, maskLeadingOnes<uint32_t>(0)); 23 EXPECT_EQ(0U, maskTrailingOnes<uint32_t>(0)); 24 EXPECT_EQ(0U, maskLeadingOnes<uint64_t>(0)); 25 EXPECT_EQ(0U, maskTrailingOnes<uint64_t>(0)); 26 27 EXPECT_EQ(0x00000003U, maskTrailingOnes<uint32_t>(2U)); 28 EXPECT_EQ(0xC0000000U, maskLeadingOnes<uint32_t>(2U)); 29 30 EXPECT_EQ(0x000007FFU, maskTrailingOnes<uint32_t>(11U)); 31 EXPECT_EQ(0xFFE00000U, maskLeadingOnes<uint32_t>(11U)); 32 33 EXPECT_EQ(0xFFFFFFFFU, maskTrailingOnes<uint32_t>(32U)); 34 EXPECT_EQ(0xFFFFFFFFU, maskLeadingOnes<uint32_t>(32U)); 35 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, maskTrailingOnes<uint64_t>(64U)); 36 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, maskLeadingOnes<uint64_t>(64U)); 37 38 EXPECT_EQ(0x0000FFFFFFFFFFFFULL, maskTrailingOnes<uint64_t>(48U)); 39 EXPECT_EQ(0xFFFFFFFFFFFF0000ULL, maskLeadingOnes<uint64_t>(48U)); 40 } 41 42 TEST(MathExtras, isIntN) { 43 EXPECT_TRUE(isIntN(16, 32767)); 44 EXPECT_FALSE(isIntN(16, 32768)); 45 EXPECT_TRUE(isIntN(0, 0)); 46 EXPECT_FALSE(isIntN(0, 1)); 47 EXPECT_FALSE(isIntN(0, -1)); 48 } 49 50 TEST(MathExtras, isUIntN) { 51 EXPECT_TRUE(isUIntN(16, 65535)); 52 EXPECT_FALSE(isUIntN(16, 65536)); 53 EXPECT_TRUE(isUIntN(1, 0)); 54 EXPECT_TRUE(isUIntN(6, 63)); 55 EXPECT_TRUE(isUIntN(0, 0)); 56 EXPECT_FALSE(isUIntN(0, 1)); 57 } 58 59 TEST(MathExtras, maxIntN) { 60 EXPECT_EQ(32767, maxIntN(16)); 61 EXPECT_EQ(2147483647, maxIntN(32)); 62 EXPECT_EQ(std::numeric_limits<int32_t>::max(), maxIntN(32)); 63 EXPECT_EQ(std::numeric_limits<int64_t>::max(), maxIntN(64)); 64 EXPECT_EQ(0, maxIntN(0)); 65 } 66 67 TEST(MathExtras, minIntN) { 68 EXPECT_EQ(-32768LL, minIntN(16)); 69 EXPECT_EQ(-64LL, minIntN(7)); 70 EXPECT_EQ(std::numeric_limits<int32_t>::min(), minIntN(32)); 71 EXPECT_EQ(std::numeric_limits<int64_t>::min(), minIntN(64)); 72 EXPECT_EQ(0, minIntN(0)); 73 } 74 75 TEST(MathExtras, maxUIntN) { 76 EXPECT_EQ(0xffffULL, maxUIntN(16)); 77 EXPECT_EQ(0xffffffffULL, maxUIntN(32)); 78 EXPECT_EQ(0xffffffffffffffffULL, maxUIntN(64)); 79 EXPECT_EQ(1ULL, maxUIntN(1)); 80 EXPECT_EQ(0x0fULL, maxUIntN(4)); 81 EXPECT_EQ(0ULL, maxUIntN(0)); 82 } 83 84 TEST(MathExtras, reverseBits) { 85 uint8_t NZ8 = 42; 86 uint16_t NZ16 = 42; 87 uint32_t NZ32 = 42; 88 uint64_t NZ64 = 42; 89 EXPECT_EQ(0x54ULL, reverseBits(NZ8)); 90 EXPECT_EQ(0x5400ULL, reverseBits(NZ16)); 91 EXPECT_EQ(0x54000000ULL, reverseBits(NZ32)); 92 EXPECT_EQ(0x5400000000000000ULL, reverseBits(NZ64)); 93 } 94 95 TEST(MathExtras, isShiftedMask_32) { 96 EXPECT_FALSE(isShiftedMask_32(0x01010101)); 97 EXPECT_TRUE(isShiftedMask_32(0xf0000000)); 98 EXPECT_TRUE(isShiftedMask_32(0xffff0000)); 99 EXPECT_TRUE(isShiftedMask_32(0xff << 1)); 100 101 unsigned MaskIdx, MaskLen; 102 EXPECT_FALSE(isShiftedMask_32(0x01010101, MaskIdx, MaskLen)); 103 EXPECT_TRUE(isShiftedMask_32(0xf0000000, MaskIdx, MaskLen)); 104 EXPECT_EQ(28, (int)MaskIdx); 105 EXPECT_EQ(4, (int)MaskLen); 106 EXPECT_TRUE(isShiftedMask_32(0xffff0000, MaskIdx, MaskLen)); 107 EXPECT_EQ(16, (int)MaskIdx); 108 EXPECT_EQ(16, (int)MaskLen); 109 EXPECT_TRUE(isShiftedMask_32(0xff << 1, MaskIdx, MaskLen)); 110 EXPECT_EQ(1, (int)MaskIdx); 111 EXPECT_EQ(8, (int)MaskLen); 112 } 113 114 TEST(MathExtras, isShiftedMask_64) { 115 EXPECT_FALSE(isShiftedMask_64(0x0101010101010101ull)); 116 EXPECT_TRUE(isShiftedMask_64(0xf000000000000000ull)); 117 EXPECT_TRUE(isShiftedMask_64(0xffff000000000000ull)); 118 EXPECT_TRUE(isShiftedMask_64(0xffull << 55)); 119 120 unsigned MaskIdx, MaskLen; 121 EXPECT_FALSE(isShiftedMask_64(0x0101010101010101ull, MaskIdx, MaskLen)); 122 EXPECT_TRUE(isShiftedMask_64(0xf000000000000000ull, MaskIdx, MaskLen)); 123 EXPECT_EQ(60, (int)MaskIdx); 124 EXPECT_EQ(4, (int)MaskLen); 125 EXPECT_TRUE(isShiftedMask_64(0xffff000000000000ull, MaskIdx, MaskLen)); 126 EXPECT_EQ(48, (int)MaskIdx); 127 EXPECT_EQ(16, (int)MaskLen); 128 EXPECT_TRUE(isShiftedMask_64(0xffull << 55, MaskIdx, MaskLen)); 129 EXPECT_EQ(55, (int)MaskIdx); 130 EXPECT_EQ(8, (int)MaskLen); 131 } 132 133 TEST(MathExtras, isPowerOf2_32) { 134 EXPECT_FALSE(isPowerOf2_32(0)); 135 EXPECT_TRUE(isPowerOf2_32(1 << 6)); 136 EXPECT_TRUE(isPowerOf2_32(1 << 12)); 137 EXPECT_FALSE(isPowerOf2_32((1 << 19) + 3)); 138 EXPECT_FALSE(isPowerOf2_32(0xABCDEF0)); 139 } 140 141 TEST(MathExtras, isPowerOf2_64) { 142 EXPECT_FALSE(isPowerOf2_64(0)); 143 EXPECT_TRUE(isPowerOf2_64(1LL << 46)); 144 EXPECT_TRUE(isPowerOf2_64(1LL << 12)); 145 EXPECT_FALSE(isPowerOf2_64((1LL << 53) + 3)); 146 EXPECT_FALSE(isPowerOf2_64(0xABCDEF0ABCDEF0LL)); 147 } 148 149 TEST(MathExtras, PowerOf2Ceil) { 150 EXPECT_EQ(0U, PowerOf2Ceil(0U)); 151 EXPECT_EQ(8U, PowerOf2Ceil(8U)); 152 EXPECT_EQ(8U, PowerOf2Ceil(7U)); 153 } 154 155 TEST(MathExtras, CTLog2) { 156 EXPECT_EQ(CTLog2<1ULL << 0>(), 0U); 157 EXPECT_EQ(CTLog2<1ULL << 1>(), 1U); 158 EXPECT_EQ(CTLog2<1ULL << 2>(), 2U); 159 EXPECT_EQ(CTLog2<1ULL << 3>(), 3U); 160 EXPECT_EQ(CTLog2<1ULL << 4>(), 4U); 161 EXPECT_EQ(CTLog2<1ULL << 5>(), 5U); 162 EXPECT_EQ(CTLog2<1ULL << 6>(), 6U); 163 EXPECT_EQ(CTLog2<1ULL << 7>(), 7U); 164 EXPECT_EQ(CTLog2<1ULL << 8>(), 8U); 165 EXPECT_EQ(CTLog2<1ULL << 9>(), 9U); 166 EXPECT_EQ(CTLog2<1ULL << 10>(), 10U); 167 EXPECT_EQ(CTLog2<1ULL << 11>(), 11U); 168 EXPECT_EQ(CTLog2<1ULL << 12>(), 12U); 169 EXPECT_EQ(CTLog2<1ULL << 13>(), 13U); 170 EXPECT_EQ(CTLog2<1ULL << 14>(), 14U); 171 EXPECT_EQ(CTLog2<1ULL << 15>(), 15U); 172 } 173 174 TEST(MathExtras, MinAlign) { 175 EXPECT_EQ(1u, MinAlign(2, 3)); 176 EXPECT_EQ(2u, MinAlign(2, 4)); 177 EXPECT_EQ(1u, MinAlign(17, 64)); 178 EXPECT_EQ(256u, MinAlign(256, 512)); 179 EXPECT_EQ(2u, MinAlign(0, 2)); 180 } 181 182 TEST(MathExtras, NextPowerOf2) { 183 EXPECT_EQ(4u, NextPowerOf2(3)); 184 EXPECT_EQ(16u, NextPowerOf2(15)); 185 EXPECT_EQ(256u, NextPowerOf2(128)); 186 } 187 188 TEST(MathExtras, AlignTo) { 189 EXPECT_EQ(8u, alignTo(5, 8)); 190 EXPECT_EQ(24u, alignTo(17, 8)); 191 EXPECT_EQ(0u, alignTo(~0LL, 8)); 192 EXPECT_EQ(static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1, 193 alignTo(std::numeric_limits<uint32_t>::max(), 2)); 194 195 EXPECT_EQ(7u, alignTo(5, 8, 7)); 196 EXPECT_EQ(17u, alignTo(17, 8, 1)); 197 EXPECT_EQ(3u, alignTo(~0LL, 8, 3)); 198 EXPECT_EQ(552u, alignTo(321, 255, 42)); 199 EXPECT_EQ(std::numeric_limits<uint32_t>::max(), 200 alignTo(std::numeric_limits<uint32_t>::max(), 2, 1)); 201 } 202 203 TEST(MathExtras, AlignToPowerOf2) { 204 EXPECT_EQ(8u, alignToPowerOf2(5, 8)); 205 EXPECT_EQ(24u, alignToPowerOf2(17, 8)); 206 EXPECT_EQ(0u, alignToPowerOf2(~0LL, 8)); 207 EXPECT_EQ(static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1, 208 alignToPowerOf2(std::numeric_limits<uint32_t>::max(), 2)); 209 } 210 211 TEST(MathExtras, AlignDown) { 212 EXPECT_EQ(0u, alignDown(5, 8)); 213 EXPECT_EQ(16u, alignDown(17, 8)); 214 EXPECT_EQ(std::numeric_limits<uint32_t>::max() - 1, 215 alignDown(std::numeric_limits<uint32_t>::max(), 2)); 216 } 217 218 template <typename T> void SaturatingAddTestHelper() { 219 const T Max = std::numeric_limits<T>::max(); 220 bool ResultOverflowed; 221 222 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2))); 223 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), &ResultOverflowed)); 224 EXPECT_FALSE(ResultOverflowed); 225 226 EXPECT_EQ(Max, SaturatingAdd(Max, T(1))); 227 EXPECT_EQ(Max, SaturatingAdd(Max, T(1), &ResultOverflowed)); 228 EXPECT_TRUE(ResultOverflowed); 229 230 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1))); 231 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), &ResultOverflowed)); 232 EXPECT_FALSE(ResultOverflowed); 233 234 EXPECT_EQ(Max, SaturatingAdd(T(1), Max)); 235 EXPECT_EQ(Max, SaturatingAdd(T(1), Max, &ResultOverflowed)); 236 EXPECT_TRUE(ResultOverflowed); 237 238 EXPECT_EQ(Max, SaturatingAdd(Max, Max)); 239 EXPECT_EQ(Max, SaturatingAdd(Max, Max, &ResultOverflowed)); 240 EXPECT_TRUE(ResultOverflowed); 241 242 EXPECT_EQ(T(6), SaturatingAdd(T(1), T(2), T(3))); 243 EXPECT_EQ(T(6), SaturatingAdd(T(1), T(2), T(3), &ResultOverflowed)); 244 EXPECT_FALSE(ResultOverflowed); 245 246 EXPECT_EQ(T(10), SaturatingAdd(T(1), T(2), T(3), T(4))); 247 EXPECT_EQ(T(10), SaturatingAdd(T(1), T(2), T(3), T(4), &ResultOverflowed)); 248 EXPECT_FALSE(ResultOverflowed); 249 250 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(0))); 251 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(0), &ResultOverflowed)); 252 EXPECT_FALSE(ResultOverflowed); 253 254 EXPECT_EQ(Max, SaturatingAdd(T(0), T(0), Max)); 255 EXPECT_EQ(Max, SaturatingAdd(T(0), T(0), Max, &ResultOverflowed)); 256 EXPECT_FALSE(ResultOverflowed); 257 258 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(1))); 259 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(1), &ResultOverflowed)); 260 EXPECT_TRUE(ResultOverflowed); 261 262 EXPECT_EQ(Max, SaturatingAdd(T(0), T(1), Max)); 263 EXPECT_EQ(Max, SaturatingAdd(T(0), T(1), Max, &ResultOverflowed)); 264 EXPECT_TRUE(ResultOverflowed); 265 266 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 2), T(1))); 267 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 2), T(1), &ResultOverflowed)); 268 EXPECT_FALSE(ResultOverflowed); 269 270 EXPECT_EQ(Max, SaturatingAdd(T(1), T(1), T(Max - 2))); 271 EXPECT_EQ(Max, SaturatingAdd(T(1), T(1), T(Max - 2), &ResultOverflowed)); 272 EXPECT_FALSE(ResultOverflowed); 273 274 EXPECT_EQ(Max, SaturatingAdd(Max, Max, Max)); 275 EXPECT_EQ(Max, SaturatingAdd(Max, Max, Max, &ResultOverflowed)); 276 EXPECT_TRUE(ResultOverflowed); 277 } 278 279 TEST(MathExtras, SaturatingAdd) { 280 SaturatingAddTestHelper<uint8_t>(); 281 SaturatingAddTestHelper<uint16_t>(); 282 SaturatingAddTestHelper<uint32_t>(); 283 SaturatingAddTestHelper<uint64_t>(); 284 } 285 286 template<typename T> 287 void SaturatingMultiplyTestHelper() 288 { 289 const T Max = std::numeric_limits<T>::max(); 290 bool ResultOverflowed; 291 292 // Test basic multiplication. 293 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3))); 294 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), &ResultOverflowed)); 295 EXPECT_FALSE(ResultOverflowed); 296 297 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2))); 298 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), &ResultOverflowed)); 299 EXPECT_FALSE(ResultOverflowed); 300 301 // Test multiplication by zero. 302 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0))); 303 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), &ResultOverflowed)); 304 EXPECT_FALSE(ResultOverflowed); 305 306 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0))); 307 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), &ResultOverflowed)); 308 EXPECT_FALSE(ResultOverflowed); 309 310 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1))); 311 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), &ResultOverflowed)); 312 EXPECT_FALSE(ResultOverflowed); 313 314 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0))); 315 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), &ResultOverflowed)); 316 EXPECT_FALSE(ResultOverflowed); 317 318 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max)); 319 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, &ResultOverflowed)); 320 EXPECT_FALSE(ResultOverflowed); 321 322 // Test multiplication by maximum value. 323 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2))); 324 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), &ResultOverflowed)); 325 EXPECT_TRUE(ResultOverflowed); 326 327 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max)); 328 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, &ResultOverflowed)); 329 EXPECT_TRUE(ResultOverflowed); 330 331 EXPECT_EQ(Max, SaturatingMultiply(Max, Max)); 332 EXPECT_EQ(Max, SaturatingMultiply(Max, Max, &ResultOverflowed)); 333 EXPECT_TRUE(ResultOverflowed); 334 335 // Test interesting boundary conditions for algorithm - 336 // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1] 337 // and A + B == std::numeric_limits<T>::digits. 338 // We expect overflow iff A > B and K = 1. 339 const int Digits = std::numeric_limits<T>::digits; 340 for (int A = 1, B = Digits - 1; B >= 1; ++A, --B) { 341 for (int K = -1; K <= 1; ++K) { 342 T X = (T(1) << A) - T(1); 343 T Y = (T(1) << B) + K; 344 bool OverflowExpected = A > B && K == 1; 345 346 if(OverflowExpected) { 347 EXPECT_EQ(Max, SaturatingMultiply(X, Y)); 348 EXPECT_EQ(Max, SaturatingMultiply(X, Y, &ResultOverflowed)); 349 EXPECT_TRUE(ResultOverflowed); 350 } else { 351 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y)); 352 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, &ResultOverflowed)); 353 EXPECT_FALSE(ResultOverflowed); 354 } 355 } 356 } 357 } 358 359 TEST(MathExtras, SaturatingMultiply) { 360 SaturatingMultiplyTestHelper<uint8_t>(); 361 SaturatingMultiplyTestHelper<uint16_t>(); 362 SaturatingMultiplyTestHelper<uint32_t>(); 363 SaturatingMultiplyTestHelper<uint64_t>(); 364 } 365 366 template<typename T> 367 void SaturatingMultiplyAddTestHelper() 368 { 369 const T Max = std::numeric_limits<T>::max(); 370 bool ResultOverflowed; 371 372 // Test basic multiply-add. 373 EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10))); 374 EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10), &ResultOverflowed)); 375 EXPECT_FALSE(ResultOverflowed); 376 377 // Test multiply overflows, add doesn't overflow 378 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(0), &ResultOverflowed)); 379 EXPECT_TRUE(ResultOverflowed); 380 381 // Test multiply doesn't overflow, add overflows 382 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed)); 383 EXPECT_TRUE(ResultOverflowed); 384 385 // Test multiply-add with Max as operand 386 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed)); 387 EXPECT_TRUE(ResultOverflowed); 388 389 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), Max, T(1), &ResultOverflowed)); 390 EXPECT_TRUE(ResultOverflowed); 391 392 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(1), &ResultOverflowed)); 393 EXPECT_TRUE(ResultOverflowed); 394 395 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, Max, &ResultOverflowed)); 396 EXPECT_TRUE(ResultOverflowed); 397 398 // Test multiply-add with 0 as operand 399 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(1), T(0), &ResultOverflowed)); 400 EXPECT_FALSE(ResultOverflowed); 401 402 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(0), T(1), &ResultOverflowed)); 403 EXPECT_FALSE(ResultOverflowed); 404 405 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(0), T(0), T(1), &ResultOverflowed)); 406 EXPECT_FALSE(ResultOverflowed); 407 408 EXPECT_EQ(T(0), SaturatingMultiplyAdd(T(0), T(0), T(0), &ResultOverflowed)); 409 EXPECT_FALSE(ResultOverflowed); 410 411 } 412 413 TEST(MathExtras, SaturatingMultiplyAdd) { 414 SaturatingMultiplyAddTestHelper<uint8_t>(); 415 SaturatingMultiplyAddTestHelper<uint16_t>(); 416 SaturatingMultiplyAddTestHelper<uint32_t>(); 417 SaturatingMultiplyAddTestHelper<uint64_t>(); 418 } 419 420 TEST(MathExtras, IsShiftedUInt) { 421 EXPECT_TRUE((isShiftedUInt<1, 0>(0))); 422 EXPECT_TRUE((isShiftedUInt<1, 0>(1))); 423 EXPECT_FALSE((isShiftedUInt<1, 0>(2))); 424 EXPECT_FALSE((isShiftedUInt<1, 0>(3))); 425 EXPECT_FALSE((isShiftedUInt<1, 0>(0x8000000000000000))); 426 EXPECT_TRUE((isShiftedUInt<1, 63>(0x8000000000000000))); 427 EXPECT_TRUE((isShiftedUInt<2, 62>(0xC000000000000000))); 428 EXPECT_FALSE((isShiftedUInt<2, 62>(0xE000000000000000))); 429 430 // 0x201 is ten bits long and has a 1 in the MSB and LSB. 431 EXPECT_TRUE((isShiftedUInt<10, 5>(uint64_t(0x201) << 5))); 432 EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 4))); 433 EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 6))); 434 } 435 436 TEST(MathExtras, IsShiftedInt) { 437 EXPECT_TRUE((isShiftedInt<1, 0>(0))); 438 EXPECT_TRUE((isShiftedInt<1, 0>(-1))); 439 EXPECT_FALSE((isShiftedInt<1, 0>(2))); 440 EXPECT_FALSE((isShiftedInt<1, 0>(3))); 441 EXPECT_FALSE((isShiftedInt<1, 0>(0x8000000000000000))); 442 EXPECT_TRUE((isShiftedInt<1, 63>(0x8000000000000000))); 443 EXPECT_TRUE((isShiftedInt<2, 62>(0xC000000000000000))); 444 EXPECT_FALSE((isShiftedInt<2, 62>(0xE000000000000000))); 445 446 // 0x201 is ten bits long and has a 1 in the MSB and LSB. 447 EXPECT_TRUE((isShiftedInt<11, 5>(int64_t(0x201) << 5))); 448 EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 3))); 449 EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 6))); 450 EXPECT_TRUE((isShiftedInt<11, 5>(-(int64_t(0x201) << 5)))); 451 EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 3)))); 452 EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 6)))); 453 454 EXPECT_TRUE((isShiftedInt<6, 10>(-(int64_t(1) << 15)))); 455 EXPECT_FALSE((isShiftedInt<6, 10>(int64_t(1) << 15))); 456 } 457 458 TEST(MathExtras, DivideNearest) { 459 EXPECT_EQ(divideNearest(14, 3), 5u); 460 EXPECT_EQ(divideNearest(15, 3), 5u); 461 EXPECT_EQ(divideNearest(0, 3), 0u); 462 EXPECT_EQ(divideNearest(5, 4), 1u); 463 EXPECT_EQ(divideNearest(6, 4), 2u); 464 EXPECT_EQ(divideNearest(3, 1), 3u); 465 EXPECT_EQ(divideNearest(3, 6), 1u); 466 EXPECT_EQ(divideNearest(3, 7), 0u); 467 EXPECT_EQ(divideNearest(std::numeric_limits<uint32_t>::max(), 2), 468 std::numeric_limits<uint32_t>::max() / 2 + 1); 469 EXPECT_EQ(divideNearest(std::numeric_limits<uint64_t>::max(), 2), 470 std::numeric_limits<uint64_t>::max() / 2 + 1); 471 EXPECT_EQ(divideNearest(std::numeric_limits<uint64_t>::max(), 1), 472 std::numeric_limits<uint64_t>::max()); 473 EXPECT_EQ(divideNearest(std::numeric_limits<uint64_t>::max() - 1, 474 std::numeric_limits<uint64_t>::max()), 475 1u); 476 } 477 478 TEST(MathExtras, DivideCeil) { 479 EXPECT_EQ(divideCeil(14, 3), 5u); 480 EXPECT_EQ(divideCeil(15, 3), 5u); 481 EXPECT_EQ(divideCeil(0, 3), 0u); 482 EXPECT_EQ(divideCeil(5, 4), 2u); 483 EXPECT_EQ(divideCeil(6, 4), 2u); 484 EXPECT_EQ(divideCeil(3, 1), 3u); 485 EXPECT_EQ(divideCeil(3, 6), 1u); 486 EXPECT_EQ(divideCeil(3, 7), 1u); 487 EXPECT_EQ(divideCeil(std::numeric_limits<uint32_t>::max(), 2), 488 std::numeric_limits<uint32_t>::max() / 2 + 1); 489 EXPECT_EQ(divideCeil(std::numeric_limits<uint64_t>::max(), 2), 490 std::numeric_limits<uint64_t>::max() / 2 + 1); 491 EXPECT_EQ(divideCeil(std::numeric_limits<uint64_t>::max(), 1), 492 std::numeric_limits<uint64_t>::max()); 493 494 EXPECT_EQ(divideCeilSigned(14, 3), 5); 495 EXPECT_EQ(divideCeilSigned(15, 3), 5); 496 EXPECT_EQ(divideCeilSigned(14, -3), -4); 497 EXPECT_EQ(divideCeilSigned(-14, -3), 5); 498 EXPECT_EQ(divideCeilSigned(-14, 3), -4); 499 EXPECT_EQ(divideCeilSigned(-15, 3), -5); 500 EXPECT_EQ(divideCeilSigned(0, 3), 0); 501 EXPECT_EQ(divideCeilSigned(0, -3), 0); 502 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int32_t>::max(), 2), 503 std::numeric_limits<int32_t>::max() / 2 + 1); 504 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int64_t>::max(), 2), 505 std::numeric_limits<int64_t>::max() / 2 + 1); 506 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int32_t>::max(), -2), 507 std::numeric_limits<int32_t>::min() / 2 + 1); 508 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int64_t>::max(), -2), 509 std::numeric_limits<int64_t>::min() / 2 + 1); 510 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int64_t>::min(), 1), 511 std::numeric_limits<int64_t>::min()); 512 } 513 514 TEST(MathExtras, DivideFloorSigned) { 515 EXPECT_EQ(divideFloorSigned(14, 3), 4); 516 EXPECT_EQ(divideFloorSigned(15, 3), 5); 517 EXPECT_EQ(divideFloorSigned(14, -3), -5); 518 EXPECT_EQ(divideFloorSigned(-14, -3), 4); 519 EXPECT_EQ(divideFloorSigned(-14, 3), -5); 520 EXPECT_EQ(divideFloorSigned(-15, 3), -5); 521 EXPECT_EQ(divideFloorSigned(0, 3), 0); 522 EXPECT_EQ(divideFloorSigned(0, -3), 0); 523 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int32_t>::max(), 2), 524 std::numeric_limits<int32_t>::max() / 2); 525 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int64_t>::max(), 2), 526 std::numeric_limits<int64_t>::max() / 2); 527 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int32_t>::max(), -2), 528 std::numeric_limits<int32_t>::min() / 2); 529 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int64_t>::max(), -2), 530 std::numeric_limits<int64_t>::min() / 2); 531 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int64_t>::min(), 1), 532 std::numeric_limits<int64_t>::min()); 533 } 534 535 TEST(MathExtras, Mod) { 536 EXPECT_EQ(mod(1, 14), 1); 537 EXPECT_EQ(mod(-1, 14), 13); 538 EXPECT_EQ(mod(14, 3), 2); 539 EXPECT_EQ(mod(15, 3), 0); 540 EXPECT_EQ(mod(-14, 3), 1); 541 EXPECT_EQ(mod(-15, 3), 0); 542 EXPECT_EQ(mod(0, 3), 0); 543 } 544 545 template <typename T> class OverflowTest : public ::testing::Test {}; 546 547 using OverflowTestTypes = ::testing::Types<signed char, short, int, long, 548 long long>; 549 550 TYPED_TEST_SUITE(OverflowTest, OverflowTestTypes, ); 551 552 TYPED_TEST(OverflowTest, AddNoOverflow) { 553 TypeParam Result; 554 EXPECT_FALSE(AddOverflow<TypeParam>(1, 2, Result)); 555 EXPECT_EQ(Result, TypeParam(3)); 556 } 557 558 TYPED_TEST(OverflowTest, AddOverflowToNegative) { 559 TypeParam Result; 560 auto MaxValue = std::numeric_limits<TypeParam>::max(); 561 EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, MaxValue, Result)); 562 EXPECT_EQ(Result, TypeParam(-2)); 563 } 564 565 TYPED_TEST(OverflowTest, AddOverflowToMin) { 566 TypeParam Result; 567 auto MaxValue = std::numeric_limits<TypeParam>::max(); 568 EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, TypeParam(1), Result)); 569 EXPECT_EQ(Result, std::numeric_limits<TypeParam>::min()); 570 } 571 572 TYPED_TEST(OverflowTest, AddOverflowToZero) { 573 TypeParam Result; 574 auto MinValue = std::numeric_limits<TypeParam>::min(); 575 EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, MinValue, Result)); 576 EXPECT_EQ(Result, TypeParam(0)); 577 } 578 579 TYPED_TEST(OverflowTest, AddOverflowToMax) { 580 TypeParam Result; 581 auto MinValue = std::numeric_limits<TypeParam>::min(); 582 EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, TypeParam(-1), Result)); 583 EXPECT_EQ(Result, std::numeric_limits<TypeParam>::max()); 584 } 585 586 TYPED_TEST(OverflowTest, SubNoOverflow) { 587 TypeParam Result; 588 EXPECT_FALSE(SubOverflow<TypeParam>(1, 2, Result)); 589 EXPECT_EQ(Result, TypeParam(-1)); 590 } 591 592 TYPED_TEST(OverflowTest, SubOverflowToMax) { 593 TypeParam Result; 594 auto MinValue = std::numeric_limits<TypeParam>::min(); 595 EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result)); 596 EXPECT_EQ(Result, MinValue); 597 } 598 599 TYPED_TEST(OverflowTest, SubOverflowToMin) { 600 TypeParam Result; 601 auto MinValue = std::numeric_limits<TypeParam>::min(); 602 EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result)); 603 EXPECT_EQ(Result, MinValue); 604 } 605 606 TYPED_TEST(OverflowTest, SubOverflowToNegative) { 607 TypeParam Result; 608 auto MaxValue = std::numeric_limits<TypeParam>::max(); 609 auto MinValue = std::numeric_limits<TypeParam>::min(); 610 EXPECT_TRUE(SubOverflow<TypeParam>(MaxValue, MinValue, Result)); 611 EXPECT_EQ(Result, TypeParam(-1)); 612 } 613 614 TYPED_TEST(OverflowTest, SubOverflowToPositive) { 615 TypeParam Result; 616 auto MaxValue = std::numeric_limits<TypeParam>::max(); 617 auto MinValue = std::numeric_limits<TypeParam>::min(); 618 EXPECT_TRUE(SubOverflow<TypeParam>(MinValue, MaxValue, Result)); 619 EXPECT_EQ(Result, TypeParam(1)); 620 } 621 622 TYPED_TEST(OverflowTest, MulNoOverflow) { 623 TypeParam Result; 624 EXPECT_FALSE(MulOverflow<TypeParam>(1, 2, Result)); 625 EXPECT_EQ(Result, 2); 626 EXPECT_FALSE(MulOverflow<TypeParam>(-1, 3, Result)); 627 EXPECT_EQ(Result, -3); 628 EXPECT_FALSE(MulOverflow<TypeParam>(4, -2, Result)); 629 EXPECT_EQ(Result, -8); 630 EXPECT_FALSE(MulOverflow<TypeParam>(-6, -5, Result)); 631 EXPECT_EQ(Result, 30); 632 } 633 634 TYPED_TEST(OverflowTest, MulNoOverflowToMax) { 635 TypeParam Result; 636 auto MaxValue = std::numeric_limits<TypeParam>::max(); 637 auto MinValue = std::numeric_limits<TypeParam>::min(); 638 EXPECT_FALSE(MulOverflow<TypeParam>(MinValue + 1, -1, Result)); 639 EXPECT_EQ(Result, MaxValue); 640 } 641 642 TYPED_TEST(OverflowTest, MulOverflowToMin) { 643 TypeParam Result; 644 auto MinValue = std::numeric_limits<TypeParam>::min(); 645 EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, -1, Result)); 646 EXPECT_EQ(Result, MinValue); 647 } 648 649 TYPED_TEST(OverflowTest, MulOverflowMax) { 650 TypeParam Result; 651 auto MinValue = std::numeric_limits<TypeParam>::min(); 652 auto MaxValue = std::numeric_limits<TypeParam>::max(); 653 EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, MinValue, Result)); 654 EXPECT_EQ(Result, 0); 655 EXPECT_TRUE(MulOverflow<TypeParam>(MaxValue, MaxValue, Result)); 656 EXPECT_EQ(Result, 1); 657 } 658 659 TYPED_TEST(OverflowTest, MulResultZero) { 660 TypeParam Result; 661 EXPECT_FALSE(MulOverflow<TypeParam>(4, 0, Result)); 662 EXPECT_EQ(Result, TypeParam(0)); 663 EXPECT_FALSE(MulOverflow<TypeParam>(-5, 0, Result)); 664 EXPECT_EQ(Result, TypeParam(0)); 665 EXPECT_FALSE(MulOverflow<TypeParam>(0, 5, Result)); 666 EXPECT_EQ(Result, TypeParam(0)); 667 EXPECT_FALSE(MulOverflow<TypeParam>(0, -5, Result)); 668 EXPECT_EQ(Result, TypeParam(0)); 669 } 670 } // namespace 671