How to judge overflow when adding unsigned signed

Question

I am trying to detect overflow when adding a signed offset to an unsigned position

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

How to check if the result is overflow or invalid?

I thought of the ugly, 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 is a more elegant way to do this.

Update:

What is the best solution if the offset is long?

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

Answer 1

Your test is correct. I don't see a more elegant way right now, maybe not.

Why the conditions are true: arithmetic on uint32_t is arithmetic modulo 2 ^ 32. int32_t from int32_t to uint32_t usually a reinterpretation of the bit diagram (in any case, as @caf pointed out, it restores modulo 2 ^ 32 here, so it definitely works). Calculate position and offset as arbitrary precision integers. Overflow occurs if and only if position + offset >= 2^32 . But offset < 2^31 , therefore position + offset < position + 2^31 , which is less than position + 2^32 , the next value that reduces to position modulo 2 ^ 32, since uint32_t , then position + offset < position . On the other hand, if offset > 0 and position + offset < position , an overflow has obviously occurred. Underflow occurs if and only if position + offset < 0 as mathematical integers. Since offset >= -2^31 , similar reasoning shows that underflow occurred if and only if offset < 0 && position + offset > position .

Answer 2

The following function checks for overflow / underflow when adding int32_t to uint32_t. It also contains some test cases as proof 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 suffix u must ensure that the constant 0xFFFFFFFF is of unsigned type (hexadecimal constants without suffixes can be signed or unsigned, depending on the value and how your compiler defines int, long and long) and, therefore, the expression on the left is <unsigned. It may not be necessary, but I'm a little tired to understand, right. This will not hurt for sure.

Tasks (uint32) should shut up the compiler, which might think that we are doing something stupid (comparing signed with unsigned).

UPDATE If int32 has a representation with two additions and offset = -0x80000000, the -offset expression -offset allowed to raise an implementation-defined signal or, possibly, even cause undefined behavior in C (see sections 6.3.1.3 Signed and unsigned integers and 7.20.6.1 The abs, labs and llabs functions for C99), but practically never happens, because on most platforms negation is implemented as a simple instruction (or several) that does not cause any exception / interrupt / trap / event in the CPU and has little value for generating additional code to verify this case with the edge moreover, integers are represented in 2 complement codes, and the absolute value of -0x80000000 is 0x80000000, which can be convenient (for example, for calculating absolute values). The CPU does not really care about signed integers and even uses the same instructions to add and subtract for both (this is the advantage of the 2nd addition), and it rarely cares about integer overflows, as they occur in software and are a way of life. Keep this in mind, but do not sweat.

See how they are implemented in Microsoft SafeInt for C ++ ( Code , Introduction , In MSDN , Video ) and IntSafe for C ( Intro + Code , In MSDN ).