Summary: Adds the ability for callers to detect when saturation occurred on the result of saturating addition/multiplication.
Reviewers: davidxl, silvas, rsmith
Subscribers: llvm-commits
Differential Revision: http://reviews.llvm.org/D14931
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253921
91177308-0d34-0410-b5e6-
96231b3b80d8
/// \brief Add two unsigned integers, X and Y, of type T.
/// Clamp the result to the maximum representable value of T on overflow.
/// \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 T>
typename std::enable_if<std::is_unsigned<T>::value, T>::type
template <typename T>
typename std::enable_if<std::is_unsigned<T>::value, T>::type
-SaturatingAdd(T X, T Y) {
+SaturatingAdd(T X, T Y, bool &ResultOverflowed) {
// Hacker's Delight, p. 29
T Z = X + Y;
// Hacker's Delight, p. 29
T Z = X + Y;
+ ResultOverflowed = (Z < X || Z < Y);
+ if (ResultOverflowed)
return std::numeric_limits<T>::max();
else
return Z;
}
return std::numeric_limits<T>::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 T>
+typename std::enable_if<std::is_unsigned<T>::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.
/// \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 T>
typename std::enable_if<std::is_unsigned<T>::value, T>::type
template <typename T>
typename std::enable_if<std::is_unsigned<T>::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
// to the multiplication.
// 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
// to the multiplication.
+ ResultOverflowed = false;
+
// Log2(Z) would be either Log2Z or Log2Z + 1.
// Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
// will necessarily be less than Log2Max as desired.
int Log2Z = Log2_64(X) + Log2_64(Y);
const T Max = std::numeric_limits<T>::max();
int Log2Max = Log2_64(Max);
// Log2(Z) would be either Log2Z or Log2Z + 1.
// Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
// will necessarily be less than Log2Max as desired.
int Log2Z = Log2_64(X) + Log2_64(Y);
const T Max = std::numeric_limits<T>::max();
int Log2Max = Log2_64(Max);
+ }
+ if (Log2Z > Log2Max) {
+ ResultOverflowed = true;
// 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;
// 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)) {
+ ResultOverflowed = true;
- return (X & 1) ? SaturatingAdd(Z, Y) : Z;
+ if (X & 1)
+ return SaturatingAdd(Z, Y, ResultOverflowed);
+
+ 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 T>
+typename std::enable_if<std::is_unsigned<T>::value, T>::type
+SaturatingMultiply(T X, T Y) {
+ bool ResultOverflowed;
+ return SaturatingMultiply(X, Y, ResultOverflowed);
}
extern const float huge_valf;
}
extern const float huge_valf;
void SaturatingAddTestHelper()
{
const T Max = std::numeric_limits<T>::max();
void SaturatingAddTestHelper()
{
const T Max = std::numeric_limits<T>::max();
+ bool ResultOverflowed;
+
EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2)));
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)));
+ 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));
+ EXPECT_EQ(Max, SaturatingAdd(T(1), Max, ResultOverflowed));
+ EXPECT_TRUE(ResultOverflowed);
+
EXPECT_EQ(Max, SaturatingAdd(Max, Max));
EXPECT_EQ(Max, SaturatingAdd(Max, Max));
+ EXPECT_EQ(Max, SaturatingAdd(Max, Max, ResultOverflowed));
+ EXPECT_TRUE(ResultOverflowed);
}
TEST(MathExtras, SaturatingAdd) {
}
TEST(MathExtras, SaturatingAdd) {
void SaturatingMultiplyTestHelper()
{
const T Max = std::numeric_limits<T>::max();
void SaturatingMultiplyTestHelper()
{
const T Max = std::numeric_limits<T>::max();
// Test basic multiplication.
EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3)));
// 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)));
+ 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)));
// 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)));
+ 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)));
+ 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)));
+ 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));
+ EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, ResultOverflowed));
+ EXPECT_FALSE(ResultOverflowed);
// Test multiplication by maximum value.
EXPECT_EQ(Max, SaturatingMultiply(Max, T(2)));
// Test multiplication by maximum value.
EXPECT_EQ(Max, SaturatingMultiply(Max, T(2)));
- EXPECT_EQ(Max, SaturatingMultiply(T(2),Max));
+ 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));
+ 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]
// Test interesting boundary conditions for algorithm -
// ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1]
if(OverflowExpected) {
EXPECT_EQ(Max, SaturatingMultiply(X, Y));
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));
} else {
EXPECT_EQ(X * Y, SaturatingMultiply(X, Y));
+ EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, ResultOverflowed));
+ EXPECT_FALSE(ResultOverflowed);