How to judge an overflow when adding signed to unsigned

Question

I'm trying to detect the overflow when adding a signed offset to an unsigned position

uint32 position;
int32 offset;  // it could be negative
uint32 position = position+offset;

How can I check whether the result is overflow or underflow?

I have thought of an ugly way but not sure of its correctness.

• underflow: offset < 0 && position + offset >= position
• overflow: offset > 0 && position + offset <= position

And I'm also wondering if there's a more elegant way to do it.

Update:

What's the best solution if offset is long?

uint32 position;
long offset;  // it could be negative
uint32 position = position+offset;

Answer 1

Your test(s) is (are) correct. I don't see a more elegant way right now, perhaps there isn't.

Why the conditions are correct: arithmetic on uint32_t is arithmetic modulo 2^32. Conversion from int32_t to uint32_t is normally the reinterpretation of the bit-pattern (in any case, as @caf pointed out, it's reduction modulo 2^32 here, so it definitely works). Regard position and offset as arbitrary precision integers. Overflow happens if and only if
position + offset >= 2^32. But offset < 2^31, so position + offset < position + 2^31, which is less than position + 2^32, the next value that reduces to position modulo 2^32, so as uint32_t, then position + offset < position. On the other hand, if offset > 0 and position + offset < position, evidently overflow has occurred. Underflow happens if and only if position + offset < 0 as mathematical integers. Since offset >= -2^31, similar reasoning shows that underflow has occurred if and only if offset < 0 && position + offset > position.

Answer 2

The following function check for overflow/underflow when adding an int32_t to an uint32_t. It also contains some test cases as evidence of correctness.

#include <stdint.h>
#include <assert.h>

int is_overflow (uint32_t position, int32_t offset)
{
    if (offset > 0 && offset > UINT32_MAX - position) {
        // really we checked (offset + position > UINT32_MAX)
        // overflow
        return 1;
    }
    else if (offset < 0 && (uint32_t)offset <= UINT32_MAX - position) {
        // really we checked  (position + (uint32_t)offset <= UINT32_MAX)
        // the (uint32_t)offset maps negative offset to [2^31, UINT32_MAX]
        // underflow
        return -1;
    }

    // no over/underflow
    return 0;
}

uint32_t abs_of_negative_int32 (int32_t offset)
{
    assert(offset < 0);

    return ((UINT32_MAX - (uint32_t)offset) + 1);
}

int main (int argc, char *argv[])
{
    int r;

    r = is_overflow(0, 0);
    assert(r == 0);

    r = is_overflow(0, 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX - 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX);
    assert(r == 0);

    r = is_overflow(0, -1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN + 1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN);
    assert(r == -1);

    r = is_overflow(UINT32_MAX, 0);
    assert(r == 0);

    r = is_overflow(UINT32_MAX, 1);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, 1);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - 1, 2);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - INT32_MAX, INT32_MAX);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - INT32_MAX + 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(abs_of_negative_int32(INT32_MIN), INT32_MIN);
    assert(r == 0);

    r = is_overflow(abs_of_negative_int32(INT32_MIN) - 1, INT32_MIN);
    assert(r == -1);

    return 0;
}

Answer 3

Here's how you can do it:

uint32 addui(uint32 position, int32 offset, int* overflow)
{
  *overflow = (((offset >= 0) && (0xFFFFFFFFu - position < (uint32)offset)) ||
               ((offset < 0) && (position < (uint32)-offset)));
  return position + offset;
}

The u suffix is to ensure that the 0xFFFFFFFF constant is of unsigned type (hex constants without suffixes can be signed or unsigned, depending on value and how your compiler defines int, long and long long) and therefore the expression to the left of < is unsigned. It might not be needed, but I'm a bit tired to figure out if it's not. It won't hurt for sure.

The (uint32) casts are to shut up the compiler that may think we're doing something stupid (comparing signed with unsigned).

UPDATE: If int32 has a 2's complement representation and offset = -0x80000000, the expression -offset is allowed to raise an implementation-defined signal or maybe even cause undefined behavior per the C standard (see sections 6.3.1.3 Signed and unsigned integers and 7.20.6.1 The abs, labs and llabs functions of C99), but practically this never occurs because on most platforms negation is implemented as a simple instruction (or a few) that doesn't raise any exception/interrupt/trap/event in the CPU and there's little value in generating extra code to check for this edge case, especially since integers are represented in 2's complement code and the absolute value of -0x80000000 is 0x80000000 anyway, which may be handy (e.g. for absolute value calculations). The CPU doesn't care much about signed integers and even uses the same addition and subtraction instructions for both (this is the benefit of the 2's complement) and it rarely cares about integer overflows, because they occur routinely in software and are a way of life. Be aware of it, but don't sweat it.

Please see how these are implemented in Microsoft's SafeInt for C++ (Code, Intro, On MSDN, Video) and IntSafe for C (Intro + Code, On MSDN).