diff options
author | Andrew Morrow <acm@10gen.com> | 2013-08-19 16:54:09 -0400 |
---|---|---|
committer | Andrew Morrow <acm@10gen.com> | 2013-08-20 11:48:46 -0400 |
commit | 95f78edec079e130c58bed831cfe341f45250784 (patch) | |
tree | 90b17d6e3d67740e39532ad5b47f46f7d2f204df | |
parent | fce3b4ce8fe848c332657f3accf596e6b087bce9 (diff) | |
download | mongo-95f78edec079e130c58bed831cfe341f45250784.tar.gz |
SERVER-375 Implement multiplication for SafeNum
-rw-r--r-- | src/mongo/util/safe_num-inl.h | 8 | ||||
-rw-r--r-- | src/mongo/util/safe_num.cpp | 92 | ||||
-rw-r--r-- | src/mongo/util/safe_num.h | 17 | ||||
-rw-r--r-- | src/mongo/util/safe_num_test.cpp | 136 |
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 |