llvm/unittests/Support/MathExtrasTest.cpp

   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