C/C++ unsigned integer overflow

Question

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 overﬂow,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.

That's.. misleading. It overflows. But it does so in a defined way, namely by wrapping in the way they explain. — harold, Apr 17 '13 at 09:48
@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, Apr 17 '13 at 09:57

score 44 · Accepted Answer · answered Apr 17 '13 at 09:47

44

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

answered Apr 17 '13 at 09:47

Pubby

51,882
13
139
180

I know signed overflow is undefined behavior, but wouldn't it too wrap around? – David G Apr 17 '13 at 12:16
9

@0x499602D2 On most hardware it does, although the compiler can make optimizations which won't. – Pubby Apr 17 '13 at 12:30
2

It's just like an old-style car odometer. If it only reads up to 999,999 miles, then one more mile brings it back to zero. – David Schwartz Jun 15 '17 at 08:11
Where is that defined in the C++ standard? – Thomas Weller Sep 08 '21 at 07:31
@Pubby, I think it's important to point out that in recent years compilers have become a lot more aggressive about optimizing assuming that signed integer overflow will not happen. A decade or two ago, you could leave optimizations off and kind of ignore the undefined behavior because it would work on most machines. These days, at least some compilers will actively break your code if you ignore the fact that signed integer overflow is undefined. However, the gcc option -fwrapv does make signed overflow defined, if you want it. It is non-standard so I would not recommend in general code. – cds Jan 15 '23 at 05:53

score 7 · Answer 2 · edited Aug 27 '14 at 18:17

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.

score 5 · Answer 3 · answered Apr 17 '13 at 09:50

5

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")

answered Apr 17 '13 at 09:50

Mats Petersson

126,704
14
140
227

3

Wording: "implementation defined behaviour", when a compiler shall document behaviour, and "undefined behaviour", where compilers can do what they want. edit: Oh and, "clearly defined" would be "well defined" in C++ parlance :) – Sebastian Mach Apr 17 '13 at 09:58
I think there is (at least) a third one which is something like "implementation detail", but my point was rather that I don't know which level of "it's not certain what happens here" that signed integer math ends up under - does it allow just "strange results" or "anything could happen" (e.g. what happens if the processor has an overflow trap that fires on integer overflow?) – Mats Petersson Apr 17 '13 at 10:01
"implementation detail" would be "implementation defined" in C++ parlance. Without reviewing the standard, I think overflowing signed values results in undefined behaviour. – Sebastian Mach Apr 17 '13 at 10:09
I was under the impression there is a subtle difference: "implementation defined" means that the compiler producer has to tell you what they do. "implementation detail" means "it's up to the compiler producer, and there is no need to explain that it is". Either way, "don't overflow signed integers" is the conclusion. – Mats Petersson Apr 17 '13 at 10:11
"no need to explain" would be the same as "undefined behaviour". Even though a compiler is allowed to explain how it acts on something that the standard declares undefined :) And agree on your conclusion. – Sebastian Mach Apr 17 '13 at 10:15
3

@phresnel, I understand, this was long time ago, but "no need to explain" is "unspecified behaviour", unlike "undefined" one it produces sane results, which may still differ. – sukhmel Aug 27 '14 at 18:12

SridharKritha · Answer 4 · 2022-04-20T16:17:54.107

One more example to show unsigned data type wraps around instead of overflow:

unsigned int i = std::numeric_limits<unsigned int>::max(); // (say) 4294967295

Assigning a -ve number to the unsigned is not recommended but for the illustrative purpose, I'm using it below

unsigned int j = -1; // 4294967295 wraps around(uses modulo operation)
unsigned int j = -2; // 4294967294

Visualizing the unsigned (0 to max) range with respect to the modulo of max+1 (where max = 2^n):

Range         :         0,     1,        2,.......,     max-2,   max-1,       max
.................................................................................
Last-to-First :  -(max+1),  -max, -(max-1),.......,        -3,      -2,        -1

First-to-Last :     max+1, max+2,    max+3,......., max+max-1, max+max, max+max+1

Modulo Addition Rule: (A + B) % C = (A % C + B % C) % C

[max + max + 1] % (max + 1) = [(max) + (max + 1)] % (max + 1)
                            = [(max % (max + 1)) + ((max + 1) % (max + 1))] % (max + 1)
                            = [(max % (max + 1)) + 0] % (max + 1)
                            = [max] % (max + 1) 
                            = max

C/C++ unsigned integer overflow

4 Answers4

No overflow?

Modulo?

Linked

Related