SERVER-375 Implement multiplication for SafeNum

4 files changed, 251 insertions, 2 deletions

diff --git a/src/mongo/util/safe_num-inl.h b/src/mongo/util/safe_num-inl.h
index 18d6a1f641e..6679619643b 100644
--- a/src/mongo/util/safe_num-inl.h
+++ b/src/mongo/util/safe_num-inl.h
@@ -60,6 +60,14 @@ namespace mongo {
         return *this = addInternal(*this, rhs);
     }
 
+    inline SafeNum SafeNum::operator*(const SafeNum& rhs) const {
+        return mulInternal(*this, rhs);
+    }
+
+    inline SafeNum& SafeNum::operator*=(const SafeNum& rhs) {
+        return *this = mulInternal(*this, rhs);
+    }
+
     inline SafeNum SafeNum::bitAnd(const SafeNum& rhs) const {
         return andInternal(*this, rhs);
     }
diff --git a/src/mongo/util/safe_num.cpp b/src/mongo/util/safe_num.cpp
index 98864cdb550..4b26ca4f3e4 100644
--- a/src/mongo/util/safe_num.cpp
+++ b/src/mongo/util/safe_num.cpp
@@ -193,6 +193,70 @@ namespace mongo {
             return SafeNum(sum);
         }
 
+        SafeNum mulInt32Int32(int lInt32, int rInt32) {
+            // NOTE: Please see "Secure Coding in C and C++", Second Edition, page 264-265 for
+            // details on this algorithm (for an alternative resources, see
+            //
+            // https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false).
+            //
+            // We are using the "Downcast from a larger type" algorithm here. We always perform
+            // the arithmetic in 64-bit mode, which can never overflow for 32-bit
+            // integers. Then, if we fall within the allowable range of int, we downcast,
+            // otherwise, we retain the 64-bit result.
+
+            const long long int result =
+                static_cast<long long int>(lInt32) *
+                static_cast<long long int>(rInt32);
+
+            if (result <= std::numeric_limits<int>::max() &&
+                result >= std::numeric_limits<int>::min()) {
+                return SafeNum(static_cast<int>(result));
+            }
+
+            return SafeNum(result);
+        }
+
+        SafeNum mulInt64Int64(long long lInt64, long long rInt64) {
+            // NOTE: Please see notes in mulInt32Int32 above for references. In this case,
+            // since we have no larger integer size, if our precondition test detects overflow
+            // we must return an invalid SafeNum. Otherwise, the operation is safely performed
+            // by standard arithmetic.
+
+            if (lInt64 > 0) {
+                if (rInt64 > 0) {
+                    if (lInt64 > (std::numeric_limits<long long>::max() / rInt64)) {
+                        return SafeNum();
+                    }
+                }
+                else {
+                    if (rInt64 < (std::numeric_limits<long long>::min() / lInt64)) {
+                        return SafeNum();
+                    }
+                }
+            }
+            else {
+                if (rInt64 > 0) {
+                    if (lInt64 < (std::numeric_limits<long long>::min() / rInt64)) {
+                        return SafeNum();
+                    }
+                }
+                else {
+                    if ( (lInt64 != 0) &&
+                         (rInt64 < (std::numeric_limits<long long>::max() / lInt64))) {
+                        return SafeNum();
+                    }
+                }
+            }
+
+            const long long result = lInt64 * rInt64;
+            return SafeNum(result);
+        }
+
+        SafeNum mulFloats(double lDouble, double rDouble) {
+            const double product = lDouble * rDouble;
+            return SafeNum(product);
+        }
+
     } // namespace
 
     SafeNum SafeNum::addInternal(const SafeNum& lhs, const SafeNum& rhs) {
@@ -223,6 +287,34 @@ namespace mongo {
         return SafeNum();
     }
 
+    SafeNum SafeNum::mulInternal(const SafeNum& lhs, const SafeNum& rhs) {
+        BSONType lType = lhs._type;
+        BSONType rType = rhs._type;
+
+        if (lType == NumberInt && rType == NumberInt) {
+            return mulInt32Int32(lhs._value.int32Val, rhs._value.int32Val);
+        }
+
+        if (lType == NumberInt && rType == NumberLong) {
+            return mulInt64Int64(lhs._value.int32Val, rhs._value.int64Val);
+        }
+
+        if (lType == NumberLong && rType == NumberInt) {
+            return mulInt64Int64(lhs._value.int64Val, rhs._value.int32Val);
+        }
+
+        if (lType == NumberLong && rType == NumberLong) {
+            return mulInt64Int64(lhs._value.int64Val, rhs._value.int64Val);
+        }
+
+        if ((lType == NumberInt || lType == NumberLong || lType == NumberDouble) &&
+            (rType == NumberInt || rType == NumberLong || rType == NumberDouble)) {
+            return mulFloats(getDouble(lhs), getDouble(rhs));
+        }
+
+        return SafeNum();
+    }
+
     SafeNum SafeNum::andInternal(const SafeNum& lhs, const SafeNum& rhs) {
         const BSONType lType = lhs._type;
         const BSONType rType = rhs._type;
diff --git a/src/mongo/util/safe_num.h b/src/mongo/util/safe_num.h
index fd75a23053a..467d0a4dca0 100644
--- a/src/mongo/util/safe_num.h
+++ b/src/mongo/util/safe_num.h
@@ -99,11 +99,17 @@ namespace mutablebson {
 
         /**
          * Sums the 'rhs' -- right-hand side -- safe num with this, taking care of
-         * upconvertions and overflow (see class header).
+         * upconversions and overflow (see class header).
          */
         SafeNum operator+(const SafeNum& rhs) const;
         SafeNum& operator+=(const SafeNum& rhs);
-        // TODO other operations than sum
+
+        /**
+         * Multiplies the 'rhs' -- right-hand side -- safe num with this, taking care of
+         * upconversions and overflow (see class header).
+         */
+        SafeNum operator*(const SafeNum& rhs) const;
+        SafeNum& operator*=(const SafeNum& rhs);
 
         //
         // logical operation support. Note that these operations are only supported for
@@ -170,6 +176,13 @@ namespace mutablebson {
          */
         static SafeNum addInternal(const SafeNum& lhs, const SafeNum& rhs);
 
+        /**
+         * Returns the product of 'lhs' and 'rhs', taking into consideration their types. The
+         * type of the result would upcast, if necessary and permitted. Otherwise, returns an
+         * EOO-type instance.
+         */
+        static SafeNum mulInternal(const SafeNum& lhs, const SafeNum& rhs);
+
         /** Returns the bitwise 'and' of lhs and rhs, taking into consideration their types. If
          *  the operation is invalid for the underlying types, returns an EOO instance.
          */
diff --git a/src/mongo/util/safe_num_test.cpp b/src/mongo/util/safe_num_test.cpp
index e805d4ac293..a0f7ac28752 100644
--- a/src/mongo/util/safe_num_test.cpp
+++ b/src/mongo/util/safe_num_test.cpp
@@ -308,4 +308,140 @@ namespace {
         ASSERT_TRUE(expected.isIdentical(result_b_s));
     }
 
+    TEST(Multiplication, Zero) {
+        const SafeNum zero(0);
+        ASSERT_EQUALS(zero * 0, zero);
+        ASSERT_EQUALS(zero * zero, zero);
+    }
+
+    TEST(Multiplication, LongZero) {
+        const SafeNum zero(0LL);
+        ASSERT_EQUALS(zero * 0LL, zero);
+        ASSERT_EQUALS(zero * zero, zero);
+    }
+
+    TEST(Multiplication, DoubleZero) {
+        const SafeNum zero(0.0);
+        ASSERT_EQUALS(zero * 0.0, zero);
+        ASSERT_EQUALS(zero * zero, zero);
+    }
+
+    TEST(Multiplication, One) {
+        const SafeNum plusOne(1);
+        ASSERT_EQUALS(plusOne * 1, plusOne);
+        ASSERT_EQUALS(plusOne * plusOne, plusOne);
+    }
+
+    TEST(Multiplication, LongOne) {
+        const SafeNum plusOne(1LL);
+        ASSERT_EQUALS(plusOne * 1LL, plusOne);
+        ASSERT_EQUALS(plusOne * plusOne, plusOne);
+    }
+
+    TEST(Multiplication, DoubleOne) {
+        const SafeNum plusOne(1.0);
+        ASSERT_EQUALS(plusOne * 1.0, plusOne);
+        ASSERT_EQUALS(plusOne * plusOne, plusOne);
+    }
+
+    TEST(Multiplication, UpConvertion) {
+        const SafeNum zeroInt32(0);
+        const SafeNum zeroInt64(0LL);
+        const SafeNum zeroDouble(0.0);
+        ASSERT_EQUALS((zeroInt32 * zeroInt64).type(), mongo::NumberLong);
+        ASSERT_EQUALS((zeroInt64 * zeroInt32).type(), mongo::NumberLong);
+        ASSERT_EQUALS((zeroInt32 * zeroDouble).type(), mongo::NumberDouble);
+        ASSERT_EQUALS((zeroInt64 * zeroDouble).type(), mongo::NumberDouble);
+        ASSERT_EQUALS((zeroDouble * zeroInt32).type(), mongo::NumberDouble);
+        ASSERT_EQUALS((zeroDouble * zeroInt64).type(), mongo::NumberDouble);
+
+        const SafeNum stillInt32(zeroInt32 * zeroInt32);
+        const SafeNum stillInt64(zeroInt64 * zeroInt64);
+        const SafeNum stillDouble(zeroDouble * zeroDouble);
+        ASSERT_EQUALS(stillInt32.type(), mongo::NumberInt);
+        ASSERT_EQUALS(stillInt64.type(), mongo::NumberLong);
+        ASSERT_EQUALS(stillDouble.type(), mongo::NumberDouble);
+    }
+
+    TEST(Multiplication, Overflow32to64) {
+        const SafeNum maxInt32(std::numeric_limits<int>::max());
+        ASSERT_EQUALS(maxInt32.type(), mongo::NumberInt);
+
+        const SafeNum int32TimesOne(maxInt32 * 1);
+        ASSERT_EQUALS(int32TimesOne.type(), mongo::NumberInt);
+
+        const SafeNum int32TimesTwo(maxInt32 * 2);
+        ASSERT_EQUALS(int32TimesTwo.type(), mongo::NumberLong);
+    }
+
+    TEST(Multiplication, Overflow64toDouble) {
+        const SafeNum maxInt64(std::numeric_limits<long long>::max());
+        ASSERT_EQUALS(maxInt64.type(), mongo::NumberLong);
+
+        // We don't overflow int64 to double.
+        const SafeNum int64TimesTwo(maxInt64 * 2);
+        ASSERT_EQUALS(int64TimesTwo.type(), mongo::EOO);
+
+        const SafeNum doubleResult(std::numeric_limits<long long>::max()*static_cast<double>(2));
+        ASSERT_EQUALS(doubleResult.type(), mongo::NumberDouble);
+        ASSERT_NOT_EQUALS(int64TimesTwo, doubleResult);
+    }
+
+    TEST(Multiplication, OverflowDouble) {
+        const SafeNum maxDouble(std::numeric_limits<double>::max());
+        ASSERT_EQUALS(maxDouble.type(), mongo::NumberDouble);
+
+        const SafeNum doublePlusMax(maxDouble * maxDouble);
+        ASSERT_EQUALS(doublePlusMax.type(), mongo::NumberDouble);
+
+        const SafeNum infinity(std::numeric_limits<double>::infinity());
+        ASSERT_EQUALS(doublePlusMax, infinity);
+    }
+
+    TEST(Multiplication, Negative32to64) {
+        const SafeNum minInt32(std::numeric_limits<int>::min());
+        ASSERT_EQUALS(minInt32.type(), mongo::NumberInt);
+
+        const SafeNum int32TimesOne(minInt32 * 1);
+        ASSERT_EQUALS(int32TimesOne.type(), mongo::NumberInt);
+
+        const SafeNum int32TimesTwo(minInt32 * 2);
+        ASSERT_EQUALS(int32TimesTwo.type(), mongo::NumberLong);
+    }
+
+    TEST(Multiplication, Negative64toDouble) {
+        const SafeNum minInt64(std::numeric_limits<long long>::min());
+        ASSERT_EQUALS(minInt64.type(), mongo::NumberLong);
+
+        // We don't overflow int64 to double.
+        const SafeNum int64TimesTwo(minInt64 * 2);
+        ASSERT_EQUALS(int64TimesTwo.type(), mongo::EOO);
+
+        const SafeNum int64TimesOne(minInt64 * 1);
+        ASSERT_EQUALS(int64TimesOne.type(), mongo::NumberLong);
+
+        const SafeNum doubleResult(std::numeric_limits<long long>::min()*static_cast<double>(2));
+        ASSERT_EQUALS(doubleResult.type(), mongo::NumberDouble);
+        ASSERT_NOT_EQUALS(int64TimesTwo, doubleResult);
+    }
+
+    TEST(Multiplication, 64OverflowsFourWays) {
+        const SafeNum maxInt64(std::numeric_limits<long long>::max());
+        const SafeNum minInt64(std::numeric_limits<long long>::min());
+        ASSERT_EQUALS(mongo::EOO, (maxInt64 * maxInt64).type());
+        ASSERT_EQUALS(mongo::EOO, (maxInt64 * minInt64).type());
+        ASSERT_EQUALS(mongo::EOO, (minInt64 * maxInt64).type());
+        ASSERT_EQUALS(mongo::EOO, (minInt64 * minInt64).type());
+    }
+
+    TEST(Multiplication, BoundsWithNegativeOne) {
+        const SafeNum maxInt64(std::numeric_limits<long long>::max());
+        const SafeNum minInt64(std::numeric_limits<long long>::min());
+        const SafeNum minusOneInt64(-1LL);
+        ASSERT_NOT_EQUALS(mongo::EOO, (maxInt64 * minusOneInt64).type());
+        ASSERT_NOT_EQUALS(mongo::EOO, (minusOneInt64 * maxInt64).type());
+        ASSERT_EQUALS(mongo::EOO, (minInt64 * minusOneInt64).type());
+        ASSERT_EQUALS(mongo::EOO, (minusOneInt64 * minInt64).type());
+    }
+
 } // unnamed namespace