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