unittests/Support/ScaledNumberTest.cpp

   1 //===- llvm/unittest/Support/ScaledNumberTest.cpp - ScaledPair 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/ScaledNumber.h"
  10 #include "llvm/Support/DataTypes.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14 using namespace llvm::ScaledNumbers;
  15
  16 namespace {
  17
  18 template <class UIntT> struct ScaledPair {
  19   UIntT D;
  20   int S;
  21   ScaledPair(const std::pair<UIntT, int16_t> &F) : D(F.first), S(F.second) {}
  22   ScaledPair(UIntT D, int S) : D(D), S(S) {}
  23
  24   bool operator==(const ScaledPair<UIntT> &X) const {
  25     return D == X.D && S == X.S;
  26   }
  27 };
  28 template <class UIntT>
  29 bool operator==(const std::pair<UIntT, int16_t> &L,
  30                 const ScaledPair<UIntT> &R) {
  31   return ScaledPair<UIntT>(L) == R;
  32 }
  33 template <class UIntT>
  34 void PrintTo(const ScaledPair<UIntT> &F, ::std::ostream *os) {
  35   *os << F.D << "*2^" << F.S;
  36 }
  37
  38 typedef ScaledPair<uint32_t> SP32;
  39 typedef ScaledPair<uint64_t> SP64;
  40
  41 TEST(ScaledNumberHelpersTest, getRounded) {
  42   EXPECT_EQ(getRounded32(0, 0, false), SP32(0, 0));
  43   EXPECT_EQ(getRounded32(0, 0, true), SP32(1, 0));
  44   EXPECT_EQ(getRounded32(20, 21, true), SP32(21, 21));
  45   EXPECT_EQ(getRounded32(UINT32_MAX, 0, false), SP32(UINT32_MAX, 0));
  46   EXPECT_EQ(getRounded32(UINT32_MAX, 0, true), SP32(1 << 31, 1));
  47
  48   EXPECT_EQ(getRounded64(0, 0, false), SP64(0, 0));
  49   EXPECT_EQ(getRounded64(0, 0, true), SP64(1, 0));
  50   EXPECT_EQ(getRounded64(20, 21, true), SP64(21, 21));
  51   EXPECT_EQ(getRounded64(UINT32_MAX, 0, false), SP64(UINT32_MAX, 0));
  52   EXPECT_EQ(getRounded64(UINT32_MAX, 0, true), SP64(UINT64_C(1) << 32, 0));
  53   EXPECT_EQ(getRounded64(UINT64_MAX, 0, false), SP64(UINT64_MAX, 0));
  54   EXPECT_EQ(getRounded64(UINT64_MAX, 0, true), SP64(UINT64_C(1) << 63, 1));
  55 }
  56
  57 TEST(ScaledNumberHelpersTest, getAdjusted) {
  58   const uint64_t Max32In64 = UINT32_MAX;
  59   EXPECT_EQ(getAdjusted32(0), SP32(0, 0));
  60   EXPECT_EQ(getAdjusted32(0, 5), SP32(0, 5));
  61   EXPECT_EQ(getAdjusted32(UINT32_MAX), SP32(UINT32_MAX, 0));
  62   EXPECT_EQ(getAdjusted32(Max32In64 << 1), SP32(UINT32_MAX, 1));
  63   EXPECT_EQ(getAdjusted32(Max32In64 << 1, 1), SP32(UINT32_MAX, 2));
  64   EXPECT_EQ(getAdjusted32(Max32In64 << 31), SP32(UINT32_MAX, 31));
  65   EXPECT_EQ(getAdjusted32(Max32In64 << 32), SP32(UINT32_MAX, 32));
  66   EXPECT_EQ(getAdjusted32(Max32In64 + 1), SP32(1u << 31, 1));
  67   EXPECT_EQ(getAdjusted32(UINT64_MAX), SP32(1u << 31, 33));
  68
  69   EXPECT_EQ(getAdjusted64(0), SP64(0, 0));
  70   EXPECT_EQ(getAdjusted64(0, 5), SP64(0, 5));
  71   EXPECT_EQ(getAdjusted64(UINT32_MAX), SP64(UINT32_MAX, 0));
  72   EXPECT_EQ(getAdjusted64(Max32In64 << 1), SP64(Max32In64 << 1, 0));
  73   EXPECT_EQ(getAdjusted64(Max32In64 << 1, 1), SP64(Max32In64 << 1, 1));
  74   EXPECT_EQ(getAdjusted64(Max32In64 << 31), SP64(Max32In64 << 31, 0));
  75   EXPECT_EQ(getAdjusted64(Max32In64 << 32), SP64(Max32In64 << 32, 0));
  76   EXPECT_EQ(getAdjusted64(Max32In64 + 1), SP64(Max32In64 + 1, 0));
  77   EXPECT_EQ(getAdjusted64(UINT64_MAX), SP64(UINT64_MAX, 0));
  78 }
  79
  80 TEST(ScaledNumberHelpersTest, getProduct) {
  81   // Zero.
  82   EXPECT_EQ(SP32(0, 0), getProduct32(0, 0));
  83   EXPECT_EQ(SP32(0, 0), getProduct32(0, 1));
  84   EXPECT_EQ(SP32(0, 0), getProduct32(0, 33));
  85
  86   // Basic.
  87   EXPECT_EQ(SP32(6, 0), getProduct32(2, 3));
  88   EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0),
  89             getProduct32(UINT16_MAX / 3, UINT16_MAX / 5 * 2));
  90
  91   // Overflow, no loss of precision.
  92   // ==> 0xf00010 * 0x1001
  93   // ==> 0xf00f00000 + 0x10010
  94   // ==> 0xf00f10010
  95   // ==> 0xf00f1001 * 2^4
  96   EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0xf00010, 0x1001));
  97
  98   // Overflow, loss of precision, rounds down.
  99   // ==> 0xf000070 * 0x1001
 100   // ==> 0xf00f000000 + 0x70070
 101   // ==> 0xf00f070070
 102   // ==> 0xf00f0700 * 2^8
 103   EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0xf000070, 0x1001));
 104
 105   // Overflow, loss of precision, rounds up.
 106   // ==> 0xf000080 * 0x1001
 107   // ==> 0xf00f000000 + 0x80080
 108   // ==> 0xf00f080080
 109   // ==> 0xf00f0801 * 2^8
 110   EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0xf000080, 0x1001));
 111
 112   // Reverse operand order.
 113   EXPECT_EQ(SP32(0, 0), getProduct32(1, 0));
 114   EXPECT_EQ(SP32(0, 0), getProduct32(33, 0));
 115   EXPECT_EQ(SP32(6, 0), getProduct32(3, 2));
 116   EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0),
 117             getProduct32(UINT16_MAX / 5 * 2, UINT16_MAX / 3));
 118   EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0x1001, 0xf00010));
 119   EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0x1001, 0xf000070));
 120   EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0x1001, 0xf000080));
 121
 122   // Round to overflow.
 123   EXPECT_EQ(SP64(UINT64_C(1) << 63, 64),
 124             getProduct64(UINT64_C(10376293541461622786),
 125                          UINT64_C(16397105843297379211)));
 126
 127   // Big number with rounding.
 128   EXPECT_EQ(SP64(UINT64_C(9223372036854775810), 64),
 129             getProduct64(UINT64_C(18446744073709551556),
 130                          UINT64_C(9223372036854775840)));
 131 }
 132
 133 TEST(ScaledNumberHelpersTest, getQuotient) {
 134   // Zero.
 135   EXPECT_EQ(SP32(0, 0), getQuotient32(0, 0));
 136   EXPECT_EQ(SP32(0, 0), getQuotient32(0, 1));
 137   EXPECT_EQ(SP32(0, 0), getQuotient32(0, 73));
 138   EXPECT_EQ(SP32(UINT32_MAX, MaxScale), getQuotient32(1, 0));
 139   EXPECT_EQ(SP32(UINT32_MAX, MaxScale), getQuotient32(6, 0));
 140
 141   // Powers of two.
 142   EXPECT_EQ(SP32(1u << 31, -31), getQuotient32(1, 1));
 143   EXPECT_EQ(SP32(1u << 31, -30), getQuotient32(2, 1));
 144   EXPECT_EQ(SP32(1u << 31, -33), getQuotient32(4, 16));
 145   EXPECT_EQ(SP32(7u << 29, -29), getQuotient32(7, 1));
 146   EXPECT_EQ(SP32(7u << 29, -30), getQuotient32(7, 2));
 147   EXPECT_EQ(SP32(7u << 29, -33), getQuotient32(7, 16));
 148
 149   // Divide evenly.
 150   EXPECT_EQ(SP32(3u << 30, -30), getQuotient32(9, 3));
 151   EXPECT_EQ(SP32(9u << 28, -28), getQuotient32(63, 7));
 152
 153   // Divide unevenly.
 154   EXPECT_EQ(SP32(0xaaaaaaab, -33), getQuotient32(1, 3));
 155   EXPECT_EQ(SP32(0xd5555555, -31), getQuotient32(5, 3));
 156
 157   // 64-bit division is hard to test, since divide64 doesn't canonicalize its
 158   // output.  However, this is the algorithm the implementation uses:
 159   //
 160   // - Shift divisor right.
 161   // - If we have 1 (power of 2), return early -- not canonicalized.
 162   // - Shift dividend left.
 163   // - 64-bit integer divide.
 164   // - If there's a remainder, continue with long division.
 165   //
 166   // TODO: require less knowledge about the implementation in the test.
 167
 168   // Zero.
 169   EXPECT_EQ(SP64(0, 0), getQuotient64(0, 0));
 170   EXPECT_EQ(SP64(0, 0), getQuotient64(0, 1));
 171   EXPECT_EQ(SP64(0, 0), getQuotient64(0, 73));
 172   EXPECT_EQ(SP64(UINT64_MAX, MaxScale), getQuotient64(1, 0));
 173   EXPECT_EQ(SP64(UINT64_MAX, MaxScale), getQuotient64(6, 0));
 174
 175   // Powers of two.
 176   EXPECT_EQ(SP64(1, 0), getQuotient64(1, 1));
 177   EXPECT_EQ(SP64(2, 0), getQuotient64(2, 1));
 178   EXPECT_EQ(SP64(4, -4), getQuotient64(4, 16));
 179   EXPECT_EQ(SP64(7, 0), getQuotient64(7, 1));
 180   EXPECT_EQ(SP64(7, -1), getQuotient64(7, 2));
 181   EXPECT_EQ(SP64(7, -4), getQuotient64(7, 16));
 182
 183   // Divide evenly.
 184   EXPECT_EQ(SP64(UINT64_C(3) << 60, -60), getQuotient64(9, 3));
 185   EXPECT_EQ(SP64(UINT64_C(9) << 58, -58), getQuotient64(63, 7));
 186
 187   // Divide unevenly.
 188   EXPECT_EQ(SP64(0xaaaaaaaaaaaaaaab, -65), getQuotient64(1, 3));
 189   EXPECT_EQ(SP64(0xd555555555555555, -63), getQuotient64(5, 3));
 190 }
 191
 192 TEST(ScaledNumberHelpersTest, getLg) {
 193   EXPECT_EQ(0, getLg(UINT32_C(1), 0));
 194   EXPECT_EQ(1, getLg(UINT32_C(1), 1));
 195   EXPECT_EQ(1, getLg(UINT32_C(2), 0));
 196   EXPECT_EQ(3, getLg(UINT32_C(1), 3));
 197   EXPECT_EQ(3, getLg(UINT32_C(7), 0));
 198   EXPECT_EQ(3, getLg(UINT32_C(8), 0));
 199   EXPECT_EQ(3, getLg(UINT32_C(9), 0));
 200   EXPECT_EQ(3, getLg(UINT32_C(64), -3));
 201   EXPECT_EQ(31, getLg((UINT32_MAX >> 1) + 2, 0));
 202   EXPECT_EQ(32, getLg(UINT32_MAX, 0));
 203   EXPECT_EQ(-1, getLg(UINT32_C(1), -1));
 204   EXPECT_EQ(-1, getLg(UINT32_C(2), -2));
 205   EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), -1));
 206   EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 0));
 207   EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 1));
 208
 209   EXPECT_EQ(0, getLg(UINT64_C(1), 0));
 210   EXPECT_EQ(1, getLg(UINT64_C(1), 1));
 211   EXPECT_EQ(1, getLg(UINT64_C(2), 0));
 212   EXPECT_EQ(3, getLg(UINT64_C(1), 3));
 213   EXPECT_EQ(3, getLg(UINT64_C(7), 0));
 214   EXPECT_EQ(3, getLg(UINT64_C(8), 0));
 215   EXPECT_EQ(3, getLg(UINT64_C(9), 0));
 216   EXPECT_EQ(3, getLg(UINT64_C(64), -3));
 217   EXPECT_EQ(63, getLg((UINT64_MAX >> 1) + 2, 0));
 218   EXPECT_EQ(64, getLg(UINT64_MAX, 0));
 219   EXPECT_EQ(-1, getLg(UINT64_C(1), -1));
 220   EXPECT_EQ(-1, getLg(UINT64_C(2), -2));
 221   EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), -1));
 222   EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 0));
 223   EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 1));
 224 }
 225
 226 TEST(ScaledNumberHelpersTest, getLgFloor) {
 227   EXPECT_EQ(0, getLgFloor(UINT32_C(1), 0));
 228   EXPECT_EQ(1, getLgFloor(UINT32_C(1), 1));
 229   EXPECT_EQ(1, getLgFloor(UINT32_C(2), 0));
 230   EXPECT_EQ(2, getLgFloor(UINT32_C(7), 0));
 231   EXPECT_EQ(3, getLgFloor(UINT32_C(1), 3));
 232   EXPECT_EQ(3, getLgFloor(UINT32_C(8), 0));
 233   EXPECT_EQ(3, getLgFloor(UINT32_C(9), 0));
 234   EXPECT_EQ(3, getLgFloor(UINT32_C(64), -3));
 235   EXPECT_EQ(31, getLgFloor((UINT32_MAX >> 1) + 2, 0));
 236   EXPECT_EQ(31, getLgFloor(UINT32_MAX, 0));
 237   EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), -1));
 238   EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 0));
 239   EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 1));
 240
 241   EXPECT_EQ(0, getLgFloor(UINT64_C(1), 0));
 242   EXPECT_EQ(1, getLgFloor(UINT64_C(1), 1));
 243   EXPECT_EQ(1, getLgFloor(UINT64_C(2), 0));
 244   EXPECT_EQ(2, getLgFloor(UINT64_C(7), 0));
 245   EXPECT_EQ(3, getLgFloor(UINT64_C(1), 3));
 246   EXPECT_EQ(3, getLgFloor(UINT64_C(8), 0));
 247   EXPECT_EQ(3, getLgFloor(UINT64_C(9), 0));
 248   EXPECT_EQ(3, getLgFloor(UINT64_C(64), -3));
 249   EXPECT_EQ(63, getLgFloor((UINT64_MAX >> 1) + 2, 0));
 250   EXPECT_EQ(63, getLgFloor(UINT64_MAX, 0));
 251   EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), -1));
 252   EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 0));
 253   EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 1));
 254 }
 255
 256 TEST(ScaledNumberHelpersTest, getLgCeiling) {
 257   EXPECT_EQ(0, getLgCeiling(UINT32_C(1), 0));
 258   EXPECT_EQ(1, getLgCeiling(UINT32_C(1), 1));
 259   EXPECT_EQ(1, getLgCeiling(UINT32_C(2), 0));
 260   EXPECT_EQ(3, getLgCeiling(UINT32_C(1), 3));
 261   EXPECT_EQ(3, getLgCeiling(UINT32_C(7), 0));
 262   EXPECT_EQ(3, getLgCeiling(UINT32_C(8), 0));
 263   EXPECT_EQ(3, getLgCeiling(UINT32_C(64), -3));
 264   EXPECT_EQ(4, getLgCeiling(UINT32_C(9), 0));
 265   EXPECT_EQ(32, getLgCeiling(UINT32_MAX, 0));
 266   EXPECT_EQ(32, getLgCeiling((UINT32_MAX >> 1) + 2, 0));
 267   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), -1));
 268   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 0));
 269   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 1));
 270
 271   EXPECT_EQ(0, getLgCeiling(UINT64_C(1), 0));
 272   EXPECT_EQ(1, getLgCeiling(UINT64_C(1), 1));
 273   EXPECT_EQ(1, getLgCeiling(UINT64_C(2), 0));
 274   EXPECT_EQ(3, getLgCeiling(UINT64_C(1), 3));
 275   EXPECT_EQ(3, getLgCeiling(UINT64_C(7), 0));
 276   EXPECT_EQ(3, getLgCeiling(UINT64_C(8), 0));
 277   EXPECT_EQ(3, getLgCeiling(UINT64_C(64), -3));
 278   EXPECT_EQ(4, getLgCeiling(UINT64_C(9), 0));
 279   EXPECT_EQ(64, getLgCeiling((UINT64_MAX >> 1) + 2, 0));
 280   EXPECT_EQ(64, getLgCeiling(UINT64_MAX, 0));
 281   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), -1));
 282   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 0));
 283   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 1));
 284 }
 285
 286 TEST(ScaledNumberHelpersTest, compare) {
 287   EXPECT_EQ(0, compare(UINT32_C(0), 0, UINT32_C(0), 1));
 288   EXPECT_EQ(0, compare(UINT32_C(0), 0, UINT32_C(0), -10));
 289   EXPECT_EQ(0, compare(UINT32_C(0), 0, UINT32_C(0), 20));
 290   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(64), -3));
 291   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(32), -2));
 292   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(16), -1));
 293   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(8), 0));
 294   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(4), 1));
 295   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(2), 2));
 296   EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(1), 3));
 297   EXPECT_EQ(-1, compare(UINT32_C(0), 0, UINT32_C(1), 3));
 298   EXPECT_EQ(-1, compare(UINT32_C(7), 0, UINT32_C(1), 3));
 299   EXPECT_EQ(-1, compare(UINT32_C(7), 0, UINT32_C(64), -3));
 300   EXPECT_EQ(1, compare(UINT32_C(9), 0, UINT32_C(1), 3));
 301   EXPECT_EQ(1, compare(UINT32_C(9), 0, UINT32_C(64), -3));
 302   EXPECT_EQ(1, compare(UINT32_C(9), 0, UINT32_C(0), 0));
 303
 304   EXPECT_EQ(0, compare(UINT64_C(0), 0, UINT64_C(0), 1));
 305   EXPECT_EQ(0, compare(UINT64_C(0), 0, UINT64_C(0), -10));
 306   EXPECT_EQ(0, compare(UINT64_C(0), 0, UINT64_C(0), 20));
 307   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(64), -3));
 308   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(32), -2));
 309   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(16), -1));
 310   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(8), 0));
 311   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(4), 1));
 312   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(2), 2));
 313   EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(1), 3));
 314   EXPECT_EQ(-1, compare(UINT64_C(0), 0, UINT64_C(1), 3));
 315   EXPECT_EQ(-1, compare(UINT64_C(7), 0, UINT64_C(1), 3));
 316   EXPECT_EQ(-1, compare(UINT64_C(7), 0, UINT64_C(64), -3));
 317   EXPECT_EQ(1, compare(UINT64_C(9), 0, UINT64_C(1), 3));
 318   EXPECT_EQ(1, compare(UINT64_C(9), 0, UINT64_C(64), -3));
 319   EXPECT_EQ(1, compare(UINT64_C(9), 0, UINT64_C(0), 0));
 320   EXPECT_EQ(-1, compare(UINT64_MAX, 0, UINT64_C(1), 64));
 321 }
 322
 323 TEST(ScaledNumberHelpersTest, matchScales) {
 324 #define MATCH_SCALES(T, LDIn, LSIn, RDIn, RSIn, LDOut, RDOut, SOut)            \
 325   do {                                                                         \
 326     T LDx = LDIn;                                                              \
 327     T RDx = RDIn;                                                              \
 328     T LDy = LDOut;                                                             \
 329     T RDy = RDOut;                                                             \
 330     int16_t LSx = LSIn;                                                        \
 331     int16_t RSx = RSIn;                                                        \
 332     int16_t Sy = SOut;                                                         \
 333                                                                                \
 334     EXPECT_EQ(SOut, matchScales(LDx, LSx, RDx, RSx));                          \
 335     EXPECT_EQ(LDy, LDx);                                                       \
 336     EXPECT_EQ(RDy, RDx);                                                       \
 337     if (LDy) {                                                                 \
 338       EXPECT_EQ(Sy, LSx);                                                      \
 339     }                                                                          \
 340     if (RDy) {                                                                 \
 341       EXPECT_EQ(Sy, RSx);                                                      \
 342     }                                                                          \
 343   } while (false)
 344
 345   MATCH_SCALES(uint32_t, 0, 0, 0, 0, 0, 0, 0);
 346   MATCH_SCALES(uint32_t, 0, 50, 7, 1, 0, 7, 1);
 347   MATCH_SCALES(uint32_t, UINT32_C(1) << 31, 1, 9, 0, UINT32_C(1) << 31, 4, 1);
 348   MATCH_SCALES(uint32_t, UINT32_C(1) << 31, 2, 9, 0, UINT32_C(1) << 31, 2, 2);
 349   MATCH_SCALES(uint32_t, UINT32_C(1) << 31, 3, 9, 0, UINT32_C(1) << 31, 1, 3);
 350   MATCH_SCALES(uint32_t, UINT32_C(1) << 31, 4, 9, 0, UINT32_C(1) << 31, 0, 4);
 351   MATCH_SCALES(uint32_t, UINT32_C(1) << 30, 4, 9, 0, UINT32_C(1) << 31, 1, 3);
 352   MATCH_SCALES(uint32_t, UINT32_C(1) << 29, 4, 9, 0, UINT32_C(1) << 31, 2, 2);
 353   MATCH_SCALES(uint32_t, UINT32_C(1) << 28, 4, 9, 0, UINT32_C(1) << 31, 4, 1);
 354   MATCH_SCALES(uint32_t, UINT32_C(1) << 27, 4, 9, 0, UINT32_C(1) << 31, 9, 0);
 355   MATCH_SCALES(uint32_t, 7, 1, 0, 50, 7, 0, 1);
 356   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 31, 1, 4, UINT32_C(1) << 31, 1);
 357   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 31, 2, 2, UINT32_C(1) << 31, 2);
 358   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 31, 3, 1, UINT32_C(1) << 31, 3);
 359   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 31, 4, 0, UINT32_C(1) << 31, 4);
 360   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 30, 4, 1, UINT32_C(1) << 31, 3);
 361   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 29, 4, 2, UINT32_C(1) << 31, 2);
 362   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 28, 4, 4, UINT32_C(1) << 31, 1);
 363   MATCH_SCALES(uint32_t, 9, 0, UINT32_C(1) << 27, 4, 9, UINT32_C(1) << 31, 0);
 364
 365   MATCH_SCALES(uint64_t, 0, 0, 0, 0, 0, 0, 0);
 366   MATCH_SCALES(uint64_t, 0, 100, 7, 1, 0, 7, 1);
 367   MATCH_SCALES(uint64_t, UINT64_C(1) << 63, 1, 9, 0, UINT64_C(1) << 63, 4, 1);
 368   MATCH_SCALES(uint64_t, UINT64_C(1) << 63, 2, 9, 0, UINT64_C(1) << 63, 2, 2);
 369   MATCH_SCALES(uint64_t, UINT64_C(1) << 63, 3, 9, 0, UINT64_C(1) << 63, 1, 3);
 370   MATCH_SCALES(uint64_t, UINT64_C(1) << 63, 4, 9, 0, UINT64_C(1) << 63, 0, 4);
 371   MATCH_SCALES(uint64_t, UINT64_C(1) << 62, 4, 9, 0, UINT64_C(1) << 63, 1, 3);
 372   MATCH_SCALES(uint64_t, UINT64_C(1) << 61, 4, 9, 0, UINT64_C(1) << 63, 2, 2);
 373   MATCH_SCALES(uint64_t, UINT64_C(1) << 60, 4, 9, 0, UINT64_C(1) << 63, 4, 1);
 374   MATCH_SCALES(uint64_t, UINT64_C(1) << 59, 4, 9, 0, UINT64_C(1) << 63, 9, 0);
 375   MATCH_SCALES(uint64_t, 7, 1, 0, 100, 7, 0, 1);
 376   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 63, 1, 4, UINT64_C(1) << 63, 1);
 377   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 63, 2, 2, UINT64_C(1) << 63, 2);
 378   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 63, 3, 1, UINT64_C(1) << 63, 3);
 379   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 63, 4, 0, UINT64_C(1) << 63, 4);
 380   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 62, 4, 1, UINT64_C(1) << 63, 3);
 381   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 61, 4, 2, UINT64_C(1) << 63, 2);
 382   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 60, 4, 4, UINT64_C(1) << 63, 1);
 383   MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 59, 4, 9, UINT64_C(1) << 63, 0);
 384 }
 385
 386 TEST(ScaledNumberHelpersTest, getSum) {
 387   // Zero.
 388   EXPECT_EQ(SP32(1, 0), getSum32(0, 0, 1, 0));
 389   EXPECT_EQ(SP32(8, -3), getSum32(0, 0, 8, -3));
 390   EXPECT_EQ(SP32(UINT32_MAX, 0), getSum32(0, 0, UINT32_MAX, 0));
 391
 392   // Basic.
 393   EXPECT_EQ(SP32(2, 0), getSum32(1, 0, 1, 0));
 394   EXPECT_EQ(SP32(3, 0), getSum32(1, 0, 2, 0));
 395   EXPECT_EQ(SP32(67, 0), getSum32(7, 0, 60, 0));
 396
 397   // Different scales.
 398   EXPECT_EQ(SP32(3, 0), getSum32(1, 0, 1, 1));
 399   EXPECT_EQ(SP32(4, 0), getSum32(2, 0, 1, 1));
 400
 401   // Loss of precision.
 402   EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(1, 32, 1, 0));
 403   EXPECT_EQ(SP32(UINT32_C(1) << 31, -31), getSum32(1, -32, 1, 0));
 404
 405   // Not quite loss of precision.
 406   EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, 1), getSum32(1, 32, 1, 1));
 407   EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, -32), getSum32(1, -32, 1, -1));
 408
 409   // Overflow.
 410   EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(1, 0, UINT32_MAX, 0));
 411
 412   // Reverse operand order.
 413   EXPECT_EQ(SP32(1, 0), getSum32(1, 0, 0, 0));
 414   EXPECT_EQ(SP32(8, -3), getSum32(8, -3, 0, 0));
 415   EXPECT_EQ(SP32(UINT32_MAX, 0), getSum32(UINT32_MAX, 0, 0, 0));
 416   EXPECT_EQ(SP32(3, 0), getSum32(2, 0, 1, 0));
 417   EXPECT_EQ(SP32(67, 0), getSum32(60, 0, 7, 0));
 418   EXPECT_EQ(SP32(3, 0), getSum32(1, 1, 1, 0));
 419   EXPECT_EQ(SP32(4, 0), getSum32(1, 1, 2, 0));
 420   EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(1, 0, 1, 32));
 421   EXPECT_EQ(SP32(UINT32_C(1) << 31, -31), getSum32(1, 0, 1, -32));
 422   EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, 1), getSum32(1, 1, 1, 32));
 423   EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, -32), getSum32(1, -1, 1, -32));
 424   EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(UINT32_MAX, 0, 1, 0));
 425
 426   // Zero.
 427   EXPECT_EQ(SP64(1, 0), getSum64(0, 0, 1, 0));
 428   EXPECT_EQ(SP64(8, -3), getSum64(0, 0, 8, -3));
 429   EXPECT_EQ(SP64(UINT64_MAX, 0), getSum64(0, 0, UINT64_MAX, 0));
 430
 431   // Basic.
 432   EXPECT_EQ(SP64(2, 0), getSum64(1, 0, 1, 0));
 433   EXPECT_EQ(SP64(3, 0), getSum64(1, 0, 2, 0));
 434   EXPECT_EQ(SP64(67, 0), getSum64(7, 0, 60, 0));
 435
 436   // Different scales.
 437   EXPECT_EQ(SP64(3, 0), getSum64(1, 0, 1, 1));
 438   EXPECT_EQ(SP64(4, 0), getSum64(2, 0, 1, 1));
 439
 440   // Loss of precision.
 441   EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(1, 64, 1, 0));
 442   EXPECT_EQ(SP64(UINT64_C(1) << 63, -63), getSum64(1, -64, 1, 0));
 443
 444   // Not quite loss of precision.
 445   EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, 1), getSum64(1, 64, 1, 1));
 446   EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, -64), getSum64(1, -64, 1, -1));
 447
 448   // Overflow.
 449   EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(1, 0, UINT64_MAX, 0));
 450
 451   // Reverse operand order.
 452   EXPECT_EQ(SP64(1, 0), getSum64(1, 0, 0, 0));
 453   EXPECT_EQ(SP64(8, -3), getSum64(8, -3, 0, 0));
 454   EXPECT_EQ(SP64(UINT64_MAX, 0), getSum64(UINT64_MAX, 0, 0, 0));
 455   EXPECT_EQ(SP64(3, 0), getSum64(2, 0, 1, 0));
 456   EXPECT_EQ(SP64(67, 0), getSum64(60, 0, 7, 0));
 457   EXPECT_EQ(SP64(3, 0), getSum64(1, 1, 1, 0));
 458   EXPECT_EQ(SP64(4, 0), getSum64(1, 1, 2, 0));
 459   EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(1, 0, 1, 64));
 460   EXPECT_EQ(SP64(UINT64_C(1) << 63, -63), getSum64(1, 0, 1, -64));
 461   EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, 1), getSum64(1, 1, 1, 64));
 462   EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, -64), getSum64(1, -1, 1, -64));
 463   EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(UINT64_MAX, 0, 1, 0));
 464 }
 465
 466 TEST(ScaledNumberHelpersTest, getDifference) {
 467   // Basic.
 468   EXPECT_EQ(SP32(0, 0), getDifference32(1, 0, 1, 0));
 469   EXPECT_EQ(SP32(1, 0), getDifference32(2, 0, 1, 0));
 470   EXPECT_EQ(SP32(53, 0), getDifference32(60, 0, 7, 0));
 471
 472   // Equals "0", different scales.
 473   EXPECT_EQ(SP32(0, 0), getDifference32(2, 0, 1, 1));
 474
 475   // Subtract "0".
 476   EXPECT_EQ(SP32(1, 0), getDifference32(1, 0, 0, 0));
 477   EXPECT_EQ(SP32(8, -3), getDifference32(8, -3, 0, 0));
 478   EXPECT_EQ(SP32(UINT32_MAX, 0), getDifference32(UINT32_MAX, 0, 0, 0));
 479
 480   // Loss of precision.
 481   EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, 1),
 482             getDifference32((UINT32_C(1) << 31) + 1, 1, 1, 0));
 483   EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, -31),
 484             getDifference32((UINT32_C(1) << 31) + 1, -31, 1, -32));
 485
 486   // Not quite loss of precision.
 487   EXPECT_EQ(SP32(UINT32_MAX, 0), getDifference32(1, 32, 1, 0));
 488   EXPECT_EQ(SP32(UINT32_MAX, -32), getDifference32(1, 0, 1, -32));
 489
 490   // Saturate to "0".
 491   EXPECT_EQ(SP32(0, 0), getDifference32(0, 0, 1, 0));
 492   EXPECT_EQ(SP32(0, 0), getDifference32(0, 0, 8, -3));
 493   EXPECT_EQ(SP32(0, 0), getDifference32(0, 0, UINT32_MAX, 0));
 494   EXPECT_EQ(SP32(0, 0), getDifference32(7, 0, 60, 0));
 495   EXPECT_EQ(SP32(0, 0), getDifference32(1, 0, 1, 1));
 496   EXPECT_EQ(SP32(0, 0), getDifference32(1, -32, 1, 0));
 497   EXPECT_EQ(SP32(0, 0), getDifference32(1, -32, 1, -1));
 498
 499   // Regression tests for cases that failed during bringup.
 500   EXPECT_EQ(SP32(UINT32_C(1) << 26, -31),
 501             getDifference32(1, 0, UINT32_C(31) << 27, -32));
 502
 503   // Basic.
 504   EXPECT_EQ(SP64(0, 0), getDifference64(1, 0, 1, 0));
 505   EXPECT_EQ(SP64(1, 0), getDifference64(2, 0, 1, 0));
 506   EXPECT_EQ(SP64(53, 0), getDifference64(60, 0, 7, 0));
 507
 508   // Equals "0", different scales.
 509   EXPECT_EQ(SP64(0, 0), getDifference64(2, 0, 1, 1));
 510
 511   // Subtract "0".
 512   EXPECT_EQ(SP64(1, 0), getDifference64(1, 0, 0, 0));
 513   EXPECT_EQ(SP64(8, -3), getDifference64(8, -3, 0, 0));
 514   EXPECT_EQ(SP64(UINT64_MAX, 0), getDifference64(UINT64_MAX, 0, 0, 0));
 515
 516   // Loss of precision.
 517   EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, 1),
 518             getDifference64((UINT64_C(1) << 63) + 1, 1, 1, 0));
 519   EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, -63),
 520             getDifference64((UINT64_C(1) << 63) + 1, -63, 1, -64));
 521
 522   // Not quite loss of precision.
 523   EXPECT_EQ(SP64(UINT64_MAX, 0), getDifference64(1, 64, 1, 0));
 524   EXPECT_EQ(SP64(UINT64_MAX, -64), getDifference64(1, 0, 1, -64));
 525
 526   // Saturate to "0".
 527   EXPECT_EQ(SP64(0, 0), getDifference64(0, 0, 1, 0));
 528   EXPECT_EQ(SP64(0, 0), getDifference64(0, 0, 8, -3));
 529   EXPECT_EQ(SP64(0, 0), getDifference64(0, 0, UINT64_MAX, 0));
 530   EXPECT_EQ(SP64(0, 0), getDifference64(7, 0, 60, 0));
 531   EXPECT_EQ(SP64(0, 0), getDifference64(1, 0, 1, 1));
 532   EXPECT_EQ(SP64(0, 0), getDifference64(1, -64, 1, 0));
 533   EXPECT_EQ(SP64(0, 0), getDifference64(1, -64, 1, -1));
 534 }
 535
 536 TEST(ScaledNumberHelpersTest, arithmeticOperators) {
 537   EXPECT_EQ(ScaledNumber<uint32_t>(10, 0),
 538             ScaledNumber<uint32_t>(1, 3) + ScaledNumber<uint32_t>(1, 1));
 539   EXPECT_EQ(ScaledNumber<uint32_t>(6, 0),
 540             ScaledNumber<uint32_t>(1, 3) - ScaledNumber<uint32_t>(1, 1));
 541   EXPECT_EQ(ScaledNumber<uint32_t>(2, 3),
 542             ScaledNumber<uint32_t>(1, 3) * ScaledNumber<uint32_t>(1, 1));
 543   EXPECT_EQ(ScaledNumber<uint32_t>(1, 2),
 544             ScaledNumber<uint32_t>(1, 3) / ScaledNumber<uint32_t>(1, 1));
 545   EXPECT_EQ(ScaledNumber<uint32_t>(1, 2), ScaledNumber<uint32_t>(1, 3) >> 1);
 546   EXPECT_EQ(ScaledNumber<uint32_t>(1, 4), ScaledNumber<uint32_t>(1, 3) << 1);
 547
 548   EXPECT_EQ(ScaledNumber<uint64_t>(10, 0),
 549             ScaledNumber<uint64_t>(1, 3) + ScaledNumber<uint64_t>(1, 1));
 550   EXPECT_EQ(ScaledNumber<uint64_t>(6, 0),
 551             ScaledNumber<uint64_t>(1, 3) - ScaledNumber<uint64_t>(1, 1));
 552   EXPECT_EQ(ScaledNumber<uint64_t>(2, 3),
 553             ScaledNumber<uint64_t>(1, 3) * ScaledNumber<uint64_t>(1, 1));
 554   EXPECT_EQ(ScaledNumber<uint64_t>(1, 2),
 555             ScaledNumber<uint64_t>(1, 3) / ScaledNumber<uint64_t>(1, 1));
 556   EXPECT_EQ(ScaledNumber<uint64_t>(1, 2), ScaledNumber<uint64_t>(1, 3) >> 1);
 557   EXPECT_EQ(ScaledNumber<uint64_t>(1, 4), ScaledNumber<uint64_t>(1, 3) << 1);
 558 }
 559
 560 TEST(ScaledNumberHelpersTest, toIntBug) {
 561   ScaledNumber<uint32_t> n(1, 0);
 562   EXPECT_EQ(1u, (n * n).toInt<uint32_t>());
 563 }
 564
 565 static_assert(is_trivially_copyable<ScaledNumber<uint32_t>>::value,
 566               "trivially copyable");
 567
 568 } // end namespace