How can I correctly check that integer underflow and overflow will not happen before subtraction?

2

I'm currently working on a safe integer library for C++. I've come across some issues when implementing subtraction.

Here's what I start with:

#include <limits>
#include <stdexcept>

template<typename I>
class safe_int
{
    I val;

public:
    typedef I value_type;
    static constexpr I max = std::numeric_limits<I>::max();
    static constexpr I min = std::numeric_limits<I>::min();

    safe_int(I i) : val { i } { };

    safe_int &operator+=(I rhs)
    {
        if( val > 0 && rhs > max - val )
            throw std::overflow_error("");
        else if( val < 0 && rhs < min - val )
            throw std::underflow_error("");

        val += rhs;
        return *this;
    }
};

I first attempted to write operator-= like this:

safe_int &operator-=(I rhs)
{
    return operator+=(-rhs);
}

but obviously this will fail with input of -0x80000000 on a two's complement system.

I then attempted to do it like this:

safe_int &operator-=(I rhs)
{
    if(rhs < -max)
        throw std::overflow_error("");

    return operator+=(-rhs);
}

But this doesn't work for anything less than 0 (e.x. -1 - -0x80000000 should be 0x7fffffff but instead reports overflow).

I then tried this:

safe_int &operator-=(I rhs)
{
    if( rhs < -max && val > 0 )
        throw std::overflow_error("");

    return operator+=(-rhs);
}

But now even though it correctly catches a case where overflow would occur, it itself causes overflow in a valid case (e.x. -1 - -0x80000000, where - -0x80000000 overflows).

At this point I believe that there's no way to reuse code from the addition while catching all of the corner cases. Therefore, I should probably write different code for the subtraction.

How can I correctly check that integer overflow will not happen before subtraction?

Here's a little test program:

int main(void)
{
    safe_int<int> i = -1;

    i -= -2147483648;

    return 0;
}

Assume no particular size of integer. Do not rely on undefined behavior.

c++
integer
subtraction
integer-overflow
asked on Stack Overflow Jan 29, 2020 by S.S. Anne • edited Jan 29, 2020 by S.S. Anne

2 Answers

1
template<class I>
bool valid_add( I lhs, I rhs ) {
  static constexpr I max = std::numeric_limits<I>::max();
  static constexpr I min = std::numeric_limits<I>::min();

  if( rhs > 0 && lhs > max - rhs ) return false;
  if( rhs < 0 && lhs < min - rhs ) return false;

  return true;
}
template<class I>
bool valid_subtract( I lhs, I rhs ) {
  static constexpr I max = std::numeric_limits<I>::max();
  static constexpr I min = std::numeric_limits<I>::min();

  if ((rhs < 0) && (lhs > max + rhs)) return false;
  if ((rhs > 0) && (lhs < min + rhs)) return false;

  return true;
}

note that the two functions are basically asking the same question. First we ask "what direction will rhs move our result from lhs". Then we check if lhs is "far enough away" from the min or max in that direction.

In your code simply inject:

if (!valid_add(val, rhs))
   throw "whatever";

and

if (!valid_subtract(val, rhs))
   throw "whatever";

you'll need to change this code if not using it on integral types. On floating point types, there are more complications.

After you check that the operation is valid, simply do it. Don't call another function.

0

I'd like to add that there's an additional check needed for val >= 0 && rhs < -max. Here's what I ended up going with:

safe_int &operator-=(I rhs)
{
    if( val >= 0 && rhs < -max )
        throw std::overflow_error("");

    if( val < 0 && rhs > max + val )
        throw std::overflow_error("");
    else if( val > 0 && rhs < min + val )
        throw std::underflow_error("");

    val -= rhs;
    return *this;
}
answered on Stack Overflow Jan 29, 2020 by S.S. Anne • edited Jan 29, 2020 by S.S. Anne

User contributions licensed under CC BY-SA 3.0