C/C++ unsigned integer overflow

21
votes

i'm reading an article about integer security . here's the link: http://ptgmedia.pearsoncmg.com/images/0321335724/samplechapter/seacord_ch05.pdf

In page 166,there is said:

A computation involving unsigned operands can never overflow,because a result that cannot be represented by the resulting unsigned integer type is reduced modulo to the number that is one greater than the largest value that can be represented by the resulting type.

What does it mean? appreciate for reply.

3
c++c
That's.. misleading. It overflows. But it does so in a defined way, namely by wrapping in the way they explain. - harold
@harold: That's a matter of semantics. For example, the authors of the C++ standard say that it doesn't overflow, because modular arithmetic keeps the result within range; they only use the term to describe signed overflow, which is an error giving undefined behaviour. - Mike Seymour
@harold It is from n1570 standard §6.2.5/9 - Suraj Jain

3 Answers

35
votes

It means the value "wraps around".

UINT_MAX + 1 == 0
UINT_MAX + 2 == 1
UINT_MAX + 3 == 2

.. and so on

As the link says, this is like the modulo operator: http://en.wikipedia.org/wiki/Modulo_operation

5
votes

No overflow?

"Overflow" here means "producing a value that doesn't fit the operand". Because arithmetic modulo is applied, the value always fits the operand, therefore, no overflow.

In other words, before overflow can actually happen, C++ will already have truncated the value.

Modulo?

Taking a value modulo some other value means to apply a division, and taking the remainder.

For example:

0 % 3 = 0  (0 / 3 = 0, remainder 0)
1 % 3 = 1  (1 / 3 = 0, remainder 1) 
2 % 3 = 2  (2 / 3 = 0, remainder 2)
3 % 3 = 0  (3 / 3 = 1, remainder 0)
4 % 3 = 1  (4 / 3 = 1, remainder 1)
5 % 3 = 2  (5 / 3 = 1, remainder 2)
6 % 3 = 0  (6 / 3 = 2, remainder 0)
...

This modulo is applied to results of unsigned-only computations, with the divisor being the maximum value the type can hold. E.g., if the maximum is 2^16=32768, then 32760 + 9 = (32760 + 9) % (32768+1) = 0.

4
votes

It means that you can't alter the sign of a unsigned calculation, but it can still produce unexpected results. Say we have an 8-bit unsigned value:

 uint8_t a = 42;

and we add 240 to that:

 a += 240;

it will not fit, so you get 26.

Unsigned math is clearly defined in C and C++, where signed math is technically either undefined or implementation dependent or some other "things that you wouldn't expect may happen" wording (I don't know the exact wording, but the conclusion is that "you shouldn't rely on the behaviour of overflow in signed integer values")