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(8u, alignTo(5ULL, 8ULL)); 193 194 EXPECT_EQ(8u, alignTo<8>(5)); 195 EXPECT_EQ(24u, alignTo<8>(17)); 196 EXPECT_EQ(0u, alignTo<8>(~0LL)); 197 EXPECT_EQ(254u, 198 alignTo<static_cast<uint8_t>(127)>(static_cast<uint8_t>(200))); 199 200 EXPECT_EQ(7u, alignTo(5, 8, 7)); 201 EXPECT_EQ(17u, alignTo(17, 8, 1)); 202 EXPECT_EQ(3u, alignTo(~0LL, 8, 3)); 203 EXPECT_EQ(552u, alignTo(321, 255, 42)); 204 EXPECT_EQ(std::numeric_limits<uint32_t>::max(), 205 alignTo(std::numeric_limits<uint32_t>::max(), 2, 1)); 206 207 // Overflow. 208 EXPECT_EQ(0u, alignTo(static_cast<uint8_t>(200), static_cast<uint8_t>(128))); 209 EXPECT_EQ(0u, alignTo<static_cast<uint8_t>(128)>(static_cast<uint8_t>(200))); 210 EXPECT_EQ(0u, alignTo(static_cast<uint8_t>(200), static_cast<uint8_t>(128), 211 static_cast<uint8_t>(0))); 212 EXPECT_EQ(0u, alignTo(std::numeric_limits<uint32_t>::max(), 2)); 213 } 214 215 TEST(MathExtras, AlignToPowerOf2) { 216 EXPECT_EQ(0u, alignToPowerOf2(0u, 8)); 217 EXPECT_EQ(8u, alignToPowerOf2(5, 8)); 218 EXPECT_EQ(24u, alignToPowerOf2(17, 8)); 219 EXPECT_EQ(0u, alignToPowerOf2(~0LL, 8)); 220 EXPECT_EQ(240u, alignToPowerOf2(240, 16)); 221 222 // Overflow. 223 EXPECT_EQ(0u, alignToPowerOf2(static_cast<uint8_t>(200), 224 static_cast<uint8_t>(128))); 225 EXPECT_EQ(0u, alignToPowerOf2(std::numeric_limits<uint32_t>::max(), 2)); 226 } 227 228 TEST(MathExtras, AlignDown) { 229 EXPECT_EQ(0u, alignDown(5, 8)); 230 EXPECT_EQ(16u, alignDown(17, 8)); 231 EXPECT_EQ(std::numeric_limits<uint32_t>::max() - 1, 232 alignDown(std::numeric_limits<uint32_t>::max(), 2)); 233 } 234 235 template <typename T> void SaturatingAddTestHelper() { 236 const T Max = std::numeric_limits<T>::max(); 237 bool ResultOverflowed; 238 239 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2))); 240 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), &ResultOverflowed)); 241 EXPECT_FALSE(ResultOverflowed); 242 243 EXPECT_EQ(Max, SaturatingAdd(Max, T(1))); 244 EXPECT_EQ(Max, SaturatingAdd(Max, T(1), &ResultOverflowed)); 245 EXPECT_TRUE(ResultOverflowed); 246 247 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1))); 248 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), &ResultOverflowed)); 249 EXPECT_FALSE(ResultOverflowed); 250 251 EXPECT_EQ(Max, SaturatingAdd(T(1), Max)); 252 EXPECT_EQ(Max, SaturatingAdd(T(1), Max, &ResultOverflowed)); 253 EXPECT_TRUE(ResultOverflowed); 254 255 EXPECT_EQ(Max, SaturatingAdd(Max, Max)); 256 EXPECT_EQ(Max, SaturatingAdd(Max, Max, &ResultOverflowed)); 257 EXPECT_TRUE(ResultOverflowed); 258 259 EXPECT_EQ(T(6), SaturatingAdd(T(1), T(2), T(3))); 260 EXPECT_EQ(T(6), SaturatingAdd(T(1), T(2), T(3), &ResultOverflowed)); 261 EXPECT_FALSE(ResultOverflowed); 262 263 EXPECT_EQ(T(10), SaturatingAdd(T(1), T(2), T(3), T(4))); 264 EXPECT_EQ(T(10), SaturatingAdd(T(1), T(2), T(3), T(4), &ResultOverflowed)); 265 EXPECT_FALSE(ResultOverflowed); 266 267 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(0))); 268 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(0), &ResultOverflowed)); 269 EXPECT_FALSE(ResultOverflowed); 270 271 EXPECT_EQ(Max, SaturatingAdd(T(0), T(0), Max)); 272 EXPECT_EQ(Max, SaturatingAdd(T(0), T(0), Max, &ResultOverflowed)); 273 EXPECT_FALSE(ResultOverflowed); 274 275 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(1))); 276 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(1), &ResultOverflowed)); 277 EXPECT_TRUE(ResultOverflowed); 278 279 EXPECT_EQ(Max, SaturatingAdd(T(0), T(1), Max)); 280 EXPECT_EQ(Max, SaturatingAdd(T(0), T(1), Max, &ResultOverflowed)); 281 EXPECT_TRUE(ResultOverflowed); 282 283 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 2), T(1))); 284 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 2), T(1), &ResultOverflowed)); 285 EXPECT_FALSE(ResultOverflowed); 286 287 EXPECT_EQ(Max, SaturatingAdd(T(1), T(1), T(Max - 2))); 288 EXPECT_EQ(Max, SaturatingAdd(T(1), T(1), T(Max - 2), &ResultOverflowed)); 289 EXPECT_FALSE(ResultOverflowed); 290 291 EXPECT_EQ(Max, SaturatingAdd(Max, Max, Max)); 292 EXPECT_EQ(Max, SaturatingAdd(Max, Max, Max, &ResultOverflowed)); 293 EXPECT_TRUE(ResultOverflowed); 294 } 295 296 TEST(MathExtras, SaturatingAdd) { 297 SaturatingAddTestHelper<uint8_t>(); 298 SaturatingAddTestHelper<uint16_t>(); 299 SaturatingAddTestHelper<uint32_t>(); 300 SaturatingAddTestHelper<uint64_t>(); 301 } 302 303 template<typename T> 304 void SaturatingMultiplyTestHelper() 305 { 306 const T Max = std::numeric_limits<T>::max(); 307 bool ResultOverflowed; 308 309 // Test basic multiplication. 310 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3))); 311 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), &ResultOverflowed)); 312 EXPECT_FALSE(ResultOverflowed); 313 314 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2))); 315 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), &ResultOverflowed)); 316 EXPECT_FALSE(ResultOverflowed); 317 318 // Test multiplication by zero. 319 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0))); 320 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), &ResultOverflowed)); 321 EXPECT_FALSE(ResultOverflowed); 322 323 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0))); 324 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), &ResultOverflowed)); 325 EXPECT_FALSE(ResultOverflowed); 326 327 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1))); 328 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), &ResultOverflowed)); 329 EXPECT_FALSE(ResultOverflowed); 330 331 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0))); 332 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), &ResultOverflowed)); 333 EXPECT_FALSE(ResultOverflowed); 334 335 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max)); 336 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, &ResultOverflowed)); 337 EXPECT_FALSE(ResultOverflowed); 338 339 // Test multiplication by maximum value. 340 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2))); 341 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), &ResultOverflowed)); 342 EXPECT_TRUE(ResultOverflowed); 343 344 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max)); 345 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, &ResultOverflowed)); 346 EXPECT_TRUE(ResultOverflowed); 347 348 EXPECT_EQ(Max, SaturatingMultiply(Max, Max)); 349 EXPECT_EQ(Max, SaturatingMultiply(Max, Max, &ResultOverflowed)); 350 EXPECT_TRUE(ResultOverflowed); 351 352 // Test interesting boundary conditions for algorithm - 353 // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1] 354 // and A + B == std::numeric_limits<T>::digits. 355 // We expect overflow iff A > B and K = 1. 356 const int Digits = std::numeric_limits<T>::digits; 357 for (int A = 1, B = Digits - 1; B >= 1; ++A, --B) { 358 for (int K = -1; K <= 1; ++K) { 359 T X = (T(1) << A) - T(1); 360 T Y = (T(1) << B) + K; 361 bool OverflowExpected = A > B && K == 1; 362 363 if(OverflowExpected) { 364 EXPECT_EQ(Max, SaturatingMultiply(X, Y)); 365 EXPECT_EQ(Max, SaturatingMultiply(X, Y, &ResultOverflowed)); 366 EXPECT_TRUE(ResultOverflowed); 367 } else { 368 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y)); 369 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, &ResultOverflowed)); 370 EXPECT_FALSE(ResultOverflowed); 371 } 372 } 373 } 374 } 375 376 TEST(MathExtras, SaturatingMultiply) { 377 SaturatingMultiplyTestHelper<uint8_t>(); 378 SaturatingMultiplyTestHelper<uint16_t>(); 379 SaturatingMultiplyTestHelper<uint32_t>(); 380 SaturatingMultiplyTestHelper<uint64_t>(); 381 } 382 383 template<typename T> 384 void SaturatingMultiplyAddTestHelper() 385 { 386 const T Max = std::numeric_limits<T>::max(); 387 bool ResultOverflowed; 388 389 // Test basic multiply-add. 390 EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10))); 391 EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10), &ResultOverflowed)); 392 EXPECT_FALSE(ResultOverflowed); 393 394 // Test multiply overflows, add doesn't overflow 395 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(0), &ResultOverflowed)); 396 EXPECT_TRUE(ResultOverflowed); 397 398 // Test multiply doesn't overflow, add overflows 399 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed)); 400 EXPECT_TRUE(ResultOverflowed); 401 402 // Test multiply-add with Max as operand 403 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed)); 404 EXPECT_TRUE(ResultOverflowed); 405 406 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), Max, T(1), &ResultOverflowed)); 407 EXPECT_TRUE(ResultOverflowed); 408 409 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(1), &ResultOverflowed)); 410 EXPECT_TRUE(ResultOverflowed); 411 412 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, Max, &ResultOverflowed)); 413 EXPECT_TRUE(ResultOverflowed); 414 415 // Test multiply-add with 0 as operand 416 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(1), T(0), &ResultOverflowed)); 417 EXPECT_FALSE(ResultOverflowed); 418 419 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(0), T(1), &ResultOverflowed)); 420 EXPECT_FALSE(ResultOverflowed); 421 422 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(0), T(0), T(1), &ResultOverflowed)); 423 EXPECT_FALSE(ResultOverflowed); 424 425 EXPECT_EQ(T(0), SaturatingMultiplyAdd(T(0), T(0), T(0), &ResultOverflowed)); 426 EXPECT_FALSE(ResultOverflowed); 427 428 } 429 430 TEST(MathExtras, SaturatingMultiplyAdd) { 431 SaturatingMultiplyAddTestHelper<uint8_t>(); 432 SaturatingMultiplyAddTestHelper<uint16_t>(); 433 SaturatingMultiplyAddTestHelper<uint32_t>(); 434 SaturatingMultiplyAddTestHelper<uint64_t>(); 435 } 436 437 TEST(MathExtras, IsShiftedUInt) { 438 EXPECT_TRUE((isShiftedUInt<1, 0>(0))); 439 EXPECT_TRUE((isShiftedUInt<1, 0>(1))); 440 EXPECT_FALSE((isShiftedUInt<1, 0>(2))); 441 EXPECT_FALSE((isShiftedUInt<1, 0>(3))); 442 EXPECT_FALSE((isShiftedUInt<1, 0>(0x8000000000000000))); 443 EXPECT_TRUE((isShiftedUInt<1, 63>(0x8000000000000000))); 444 EXPECT_TRUE((isShiftedUInt<2, 62>(0xC000000000000000))); 445 EXPECT_FALSE((isShiftedUInt<2, 62>(0xE000000000000000))); 446 447 // 0x201 is ten bits long and has a 1 in the MSB and LSB. 448 EXPECT_TRUE((isShiftedUInt<10, 5>(uint64_t(0x201) << 5))); 449 EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 4))); 450 EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 6))); 451 } 452 453 TEST(MathExtras, IsShiftedInt) { 454 EXPECT_TRUE((isShiftedInt<1, 0>(0))); 455 EXPECT_TRUE((isShiftedInt<1, 0>(-1))); 456 EXPECT_FALSE((isShiftedInt<1, 0>(2))); 457 EXPECT_FALSE((isShiftedInt<1, 0>(3))); 458 EXPECT_FALSE((isShiftedInt<1, 0>(0x8000000000000000))); 459 EXPECT_TRUE((isShiftedInt<1, 63>(0x8000000000000000))); 460 EXPECT_TRUE((isShiftedInt<2, 62>(0xC000000000000000))); 461 EXPECT_FALSE((isShiftedInt<2, 62>(0xE000000000000000))); 462 463 // 0x201 is ten bits long and has a 1 in the MSB and LSB. 464 EXPECT_TRUE((isShiftedInt<11, 5>(int64_t(0x201) << 5))); 465 EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 3))); 466 EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 6))); 467 EXPECT_TRUE((isShiftedInt<11, 5>(-(int64_t(0x201) << 5)))); 468 EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 3)))); 469 EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 6)))); 470 471 EXPECT_TRUE((isShiftedInt<6, 10>(-(int64_t(1) << 15)))); 472 EXPECT_FALSE((isShiftedInt<6, 10>(int64_t(1) << 15))); 473 } 474 475 TEST(MathExtras, DivideNearest) { 476 EXPECT_EQ(divideNearest(14, 3), 5u); 477 EXPECT_EQ(divideNearest(15, 3), 5u); 478 EXPECT_EQ(divideNearest(0, 3), 0u); 479 EXPECT_EQ(divideNearest(5, 4), 1u); 480 EXPECT_EQ(divideNearest(6, 4), 2u); 481 EXPECT_EQ(divideNearest(3, 1), 3u); 482 EXPECT_EQ(divideNearest(3, 6), 1u); 483 EXPECT_EQ(divideNearest(3, 7), 0u); 484 EXPECT_EQ(divideNearest(std::numeric_limits<uint32_t>::max(), 2), 485 std::numeric_limits<uint32_t>::max() / 2 + 1); 486 EXPECT_EQ(divideNearest(std::numeric_limits<uint64_t>::max(), 2), 487 std::numeric_limits<uint64_t>::max() / 2 + 1); 488 EXPECT_EQ(divideNearest(std::numeric_limits<uint64_t>::max(), 1), 489 std::numeric_limits<uint64_t>::max()); 490 EXPECT_EQ(divideNearest(std::numeric_limits<uint64_t>::max() - 1, 491 std::numeric_limits<uint64_t>::max()), 492 1u); 493 } 494 495 TEST(MathExtras, DivideCeil) { 496 EXPECT_EQ(divideCeil(14, 3), 5u); 497 EXPECT_EQ(divideCeil(15, 3), 5u); 498 EXPECT_EQ(divideCeil(0, 3), 0u); 499 EXPECT_EQ(divideCeil(5, 4), 2u); 500 EXPECT_EQ(divideCeil(6, 4), 2u); 501 EXPECT_EQ(divideCeil(3, 1), 3u); 502 EXPECT_EQ(divideCeil(3, 6), 1u); 503 EXPECT_EQ(divideCeil(3, 7), 1u); 504 EXPECT_EQ(divideCeil(std::numeric_limits<uint32_t>::max(), 2), 505 std::numeric_limits<uint32_t>::max() / 2 + 1); 506 EXPECT_EQ(divideCeil(std::numeric_limits<uint64_t>::max(), 2), 507 std::numeric_limits<uint64_t>::max() / 2 + 1); 508 EXPECT_EQ(divideCeil(std::numeric_limits<uint64_t>::max(), 1), 509 std::numeric_limits<uint64_t>::max()); 510 511 EXPECT_EQ(divideCeilSigned(14, 3), 5); 512 EXPECT_EQ(divideCeilSigned(15, 3), 5); 513 EXPECT_EQ(divideCeilSigned(14, -3), -4); 514 EXPECT_EQ(divideCeilSigned(-14, -3), 5); 515 EXPECT_EQ(divideCeilSigned(-14, 3), -4); 516 EXPECT_EQ(divideCeilSigned(-15, 3), -5); 517 EXPECT_EQ(divideCeilSigned(0, 3), 0); 518 EXPECT_EQ(divideCeilSigned(0, -3), 0); 519 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int32_t>::max(), 2), 520 std::numeric_limits<int32_t>::max() / 2 + 1); 521 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int64_t>::max(), 2), 522 std::numeric_limits<int64_t>::max() / 2 + 1); 523 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int32_t>::max(), -2), 524 std::numeric_limits<int32_t>::min() / 2 + 1); 525 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int64_t>::max(), -2), 526 std::numeric_limits<int64_t>::min() / 2 + 1); 527 EXPECT_EQ(divideCeilSigned(std::numeric_limits<int64_t>::min(), 1), 528 std::numeric_limits<int64_t>::min()); 529 530 // Overflow. 531 EXPECT_TRUE( 532 divideSignedWouldOverflow(std::numeric_limits<int8_t>::min(), -1)); 533 EXPECT_TRUE( 534 divideSignedWouldOverflow(std::numeric_limits<int64_t>::min(), -1)); 535 } 536 537 TEST(MathExtras, DivideFloorSigned) { 538 EXPECT_EQ(divideFloorSigned(14, 3), 4); 539 EXPECT_EQ(divideFloorSigned(15, 3), 5); 540 EXPECT_EQ(divideFloorSigned(14, -3), -5); 541 EXPECT_EQ(divideFloorSigned(-14, -3), 4); 542 EXPECT_EQ(divideFloorSigned(-14, 3), -5); 543 EXPECT_EQ(divideFloorSigned(-15, 3), -5); 544 EXPECT_EQ(divideFloorSigned(0, 3), 0); 545 EXPECT_EQ(divideFloorSigned(0, -3), 0); 546 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int32_t>::max(), 2), 547 std::numeric_limits<int32_t>::max() / 2); 548 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int64_t>::max(), 2), 549 std::numeric_limits<int64_t>::max() / 2); 550 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int32_t>::max(), -2), 551 std::numeric_limits<int32_t>::min() / 2); 552 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int64_t>::max(), -2), 553 std::numeric_limits<int64_t>::min() / 2); 554 EXPECT_EQ(divideFloorSigned(std::numeric_limits<int64_t>::min(), 1), 555 std::numeric_limits<int64_t>::min()); 556 557 // Same overflow condition, divideSignedWouldOverflow, applies. 558 } 559 560 TEST(MathExtras, Mod) { 561 EXPECT_EQ(mod(1, 14), 1); 562 EXPECT_EQ(mod(-1, 14), 13); 563 EXPECT_EQ(mod(14, 3), 2); 564 EXPECT_EQ(mod(15, 3), 0); 565 EXPECT_EQ(mod(-14, 3), 1); 566 EXPECT_EQ(mod(-15, 3), 0); 567 EXPECT_EQ(mod(0, 3), 0); 568 } 569 570 template <typename T> class OverflowTest : public ::testing::Test {}; 571 572 using OverflowTestTypes = ::testing::Types<signed char, short, int, long, 573 long long>; 574 575 TYPED_TEST_SUITE(OverflowTest, OverflowTestTypes, ); 576 577 TYPED_TEST(OverflowTest, AddNoOverflow) { 578 TypeParam Result; 579 EXPECT_FALSE(AddOverflow<TypeParam>(1, 2, Result)); 580 EXPECT_EQ(Result, TypeParam(3)); 581 } 582 583 TYPED_TEST(OverflowTest, AddOverflowToNegative) { 584 TypeParam Result; 585 auto MaxValue = std::numeric_limits<TypeParam>::max(); 586 EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, MaxValue, Result)); 587 EXPECT_EQ(Result, TypeParam(-2)); 588 } 589 590 TYPED_TEST(OverflowTest, AddOverflowToMin) { 591 TypeParam Result; 592 auto MaxValue = std::numeric_limits<TypeParam>::max(); 593 EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, TypeParam(1), Result)); 594 EXPECT_EQ(Result, std::numeric_limits<TypeParam>::min()); 595 } 596 597 TYPED_TEST(OverflowTest, AddOverflowToZero) { 598 TypeParam Result; 599 auto MinValue = std::numeric_limits<TypeParam>::min(); 600 EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, MinValue, Result)); 601 EXPECT_EQ(Result, TypeParam(0)); 602 } 603 604 TYPED_TEST(OverflowTest, AddOverflowToMax) { 605 TypeParam Result; 606 auto MinValue = std::numeric_limits<TypeParam>::min(); 607 EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, TypeParam(-1), Result)); 608 EXPECT_EQ(Result, std::numeric_limits<TypeParam>::max()); 609 } 610 611 TYPED_TEST(OverflowTest, SubNoOverflow) { 612 TypeParam Result; 613 EXPECT_FALSE(SubOverflow<TypeParam>(1, 2, Result)); 614 EXPECT_EQ(Result, TypeParam(-1)); 615 } 616 617 TYPED_TEST(OverflowTest, SubOverflowToMax) { 618 TypeParam Result; 619 auto MinValue = std::numeric_limits<TypeParam>::min(); 620 EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result)); 621 EXPECT_EQ(Result, MinValue); 622 } 623 624 TYPED_TEST(OverflowTest, SubOverflowToMin) { 625 TypeParam Result; 626 auto MinValue = std::numeric_limits<TypeParam>::min(); 627 EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result)); 628 EXPECT_EQ(Result, MinValue); 629 } 630 631 TYPED_TEST(OverflowTest, SubOverflowToNegative) { 632 TypeParam Result; 633 auto MaxValue = std::numeric_limits<TypeParam>::max(); 634 auto MinValue = std::numeric_limits<TypeParam>::min(); 635 EXPECT_TRUE(SubOverflow<TypeParam>(MaxValue, MinValue, Result)); 636 EXPECT_EQ(Result, TypeParam(-1)); 637 } 638 639 TYPED_TEST(OverflowTest, SubOverflowToPositive) { 640 TypeParam Result; 641 auto MaxValue = std::numeric_limits<TypeParam>::max(); 642 auto MinValue = std::numeric_limits<TypeParam>::min(); 643 EXPECT_TRUE(SubOverflow<TypeParam>(MinValue, MaxValue, Result)); 644 EXPECT_EQ(Result, TypeParam(1)); 645 } 646 647 TYPED_TEST(OverflowTest, MulNoOverflow) { 648 TypeParam Result; 649 EXPECT_FALSE(MulOverflow<TypeParam>(1, 2, Result)); 650 EXPECT_EQ(Result, 2); 651 EXPECT_FALSE(MulOverflow<TypeParam>(-1, 3, Result)); 652 EXPECT_EQ(Result, -3); 653 EXPECT_FALSE(MulOverflow<TypeParam>(4, -2, Result)); 654 EXPECT_EQ(Result, -8); 655 EXPECT_FALSE(MulOverflow<TypeParam>(-6, -5, Result)); 656 EXPECT_EQ(Result, 30); 657 } 658 659 TYPED_TEST(OverflowTest, MulNoOverflowToMax) { 660 TypeParam Result; 661 auto MaxValue = std::numeric_limits<TypeParam>::max(); 662 auto MinValue = std::numeric_limits<TypeParam>::min(); 663 EXPECT_FALSE(MulOverflow<TypeParam>(MinValue + 1, -1, Result)); 664 EXPECT_EQ(Result, MaxValue); 665 } 666 667 TYPED_TEST(OverflowTest, MulOverflowToMin) { 668 TypeParam Result; 669 auto MinValue = std::numeric_limits<TypeParam>::min(); 670 EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, -1, Result)); 671 EXPECT_EQ(Result, MinValue); 672 } 673 674 TYPED_TEST(OverflowTest, MulOverflowMax) { 675 TypeParam Result; 676 auto MinValue = std::numeric_limits<TypeParam>::min(); 677 auto MaxValue = std::numeric_limits<TypeParam>::max(); 678 EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, MinValue, Result)); 679 EXPECT_EQ(Result, 0); 680 EXPECT_TRUE(MulOverflow<TypeParam>(MaxValue, MaxValue, Result)); 681 EXPECT_EQ(Result, 1); 682 } 683 684 TYPED_TEST(OverflowTest, MulResultZero) { 685 TypeParam Result; 686 EXPECT_FALSE(MulOverflow<TypeParam>(4, 0, Result)); 687 EXPECT_EQ(Result, TypeParam(0)); 688 EXPECT_FALSE(MulOverflow<TypeParam>(-5, 0, Result)); 689 EXPECT_EQ(Result, TypeParam(0)); 690 EXPECT_FALSE(MulOverflow<TypeParam>(0, 5, Result)); 691 EXPECT_EQ(Result, TypeParam(0)); 692 EXPECT_FALSE(MulOverflow<TypeParam>(0, -5, Result)); 693 EXPECT_EQ(Result, TypeParam(0)); 694 } 695 } // namespace 696