Index: include/llvm/Support/MathExtras.h =================================================================== --- include/llvm/Support/MathExtras.h +++ include/llvm/Support/MathExtras.h @@ -655,22 +655,36 @@ /// \brief Add two unsigned integers, X and Y, of type T. /// Clamp the result to the maximum representable value of T on overflow. +/// ResultOverflowed indicates if the result is larger than the maximum +/// representable value of type T. template typename std::enable_if::value, T>::type -SaturatingAdd(T X, T Y) { +SaturatingAdd(T X, T Y, bool &ResultOverflowed) { // Hacker's Delight, p. 29 T Z = X + Y; - if (Z < X || Z < Y) + ResultOverflowed = (Z < X || Z < Y); + if (ResultOverflowed) return std::numeric_limits::max(); else return Z; } +/// \brief Add two unsigned integers, X and Y, of type T. +/// Clamp the result to the maximum representable value of T on overflow. +template +typename std::enable_if::value, T>::type +SaturatingAdd(T X, T Y) { + bool ResultOverflowed; + return SaturatingAdd(X, Y, ResultOverflowed); +} + /// \brief Multiply two unsigned integers, X and Y, of type T. /// Clamp the result to the maximum representable value of T on overflow. +/// ResultOverflowed indicates if the result is larger than the maximum +/// representable value of type T. template typename std::enable_if::value, T>::type -SaturatingMultiply(T X, T Y) { +SaturatingMultiply(T X, T Y, bool &ResultOverflowed) { // Hacker's Delight, p. 30 has a different algorithm, but we don't use that // because it fails for uint16_t (where multiplication can have undefined // behavior due to promotion to int), and requires a division in addition @@ -682,19 +696,38 @@ int Log2Z = Log2_64(X) + Log2_64(Y); const T Max = std::numeric_limits::max(); int Log2Max = Log2_64(Max); - if (Log2Z < Log2Max) + if (Log2Z < Log2Max) { + ResultOverflowed = false; return X * Y; - if (Log2Z > Log2Max) + } + if (Log2Z > Log2Max) { + ResultOverflowed = true; return Max; + } // We're going to use the top bit, and maybe overflow one // bit past it. Multiply all but the bottom bit then add // that on at the end. T Z = (X >> 1) * Y; - if (Z & ~(Max >> 1)) + if (Z & ~(Max >> 1)) { + ResultOverflowed = true; return Max; + } Z <<= 1; - return (X & 1) ? SaturatingAdd(Z, Y) : Z; + if (X & 1) + return SaturatingAdd(Z, Y, ResultOverflowed); + + ResultOverflowed = false; + return Z; +} + +/// \brief Multiply two unsigned integers, X and Y, of type T. +/// Clamp the result to the maximum representable value of T on overflow. +template +typename std::enable_if::value, T>::type +SaturatingMultiply(T X, T Y) { + bool ResultOverflowed; + return SaturatingMultiply(X, Y, ResultOverflowed); } extern const float huge_valf; Index: unittests/Support/MathExtrasTest.cpp =================================================================== --- unittests/Support/MathExtrasTest.cpp +++ unittests/Support/MathExtrasTest.cpp @@ -194,10 +194,27 @@ void SaturatingAddTestHelper() { const T Max = std::numeric_limits::max(); + bool ResultOverflowed; + EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2))); + EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(Max, SaturatingAdd(Max, T(1))); + EXPECT_EQ(Max, SaturatingAdd(Max, T(1), ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); + + EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1))); + EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(Max, SaturatingAdd(T(1), Max)); + EXPECT_EQ(Max, SaturatingAdd(T(1), Max, ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); + EXPECT_EQ(Max, SaturatingAdd(Max, Max)); + EXPECT_EQ(Max, SaturatingAdd(Max, Max, ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); } TEST(MathExtras, SaturatingAdd) { @@ -211,22 +228,50 @@ void SaturatingMultiplyTestHelper() { const T Max = std::numeric_limits::max(); + bool ResultOverflowed; // Test basic multiplication. EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3))); + EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2))); + EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); // Test multiplication by zero. EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0))); + EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0))); + EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1))); + EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0))); + EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); + EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max)); + EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); // Test multiplication by maximum value. EXPECT_EQ(Max, SaturatingMultiply(Max, T(2))); + EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); + EXPECT_EQ(Max, SaturatingMultiply(T(2),Max)); + EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); + EXPECT_EQ(Max, SaturatingMultiply(Max, Max)); + EXPECT_EQ(Max, SaturatingMultiply(Max, Max, ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); // Test interesting boundary conditions for algorithm - // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1] @@ -241,8 +286,12 @@ if(OverflowExpected) { EXPECT_EQ(Max, SaturatingMultiply(X, Y)); + EXPECT_EQ(Max, SaturatingMultiply(X, Y, ResultOverflowed)); + EXPECT_TRUE(ResultOverflowed); } else { EXPECT_EQ(X * Y, SaturatingMultiply(X, Y)); + EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, ResultOverflowed)); + EXPECT_FALSE(ResultOverflowed); } } }