Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

unsigned integer addition and undefined behavior in C90

Solved!

The relevant passage can be found in C90 ISO 9899:1990 6.1.2.5 Types:

"[..] A computation involving unsigned operands can never overflow, because [...]"

Therefore 9899:1990 6.3 can not apply and can therefore not be undefined behavior.

  • C90: see the full answer below.
  • C99: see the answer for "Is unsigned integer subtraction defined behavior?"

Thanks to Keith Thompson for helping me read. :-)

[2014-03-14] Apparently unsigned short integer can overflow resulting in undefined behavior depending on the target environment. This can happen if short unsigned integer become arithmetically promoted to int. Details see updated answer and the comments of supercat. Thanks to both. :-)

Original Question:

First of all, sorry for my bad English... I try my best. This is my first question and I think a quite stupid one.

For some sad reasons, my company got stuck to still ANSI C90 (ANSI/ISO 9899:1990) and so I have an old copy of this standard in my hands, but still missing the Corrections and ademnends.

I have an really easy question, and had known the answer perfectly well in times of my studies - till I try to read it up in the standard.

What happens if I have an unsigned integer overflow on an addition. Please see this piece of code:

uint32_t a,b,c;
b = UINT_MAX;
c = UINT_MAX;
a = b + c; /* Overflow here - undefined behavior? */

All I ever know about that is, that unsigned integer just wraps around as long as needed and everything is fine, while not always intended.

Now I was looking for the corresponding parts in the standard.

There is of course ISO 9899:1990 6.2.1.2 which describe the wrap around for unsigned integers, whenever it is converted. And there is a little bit of 6.2.1.5 "usual arithmetic conversions", which describe how the types are become wider, mostly that both operands of an expression have the same type.

Now there is 6.3 "Expressions" which is concerning me. I cite:

"[...] If an exception occurs during the evaluation of an expression (that is, if the result is not mathematically defined or NOT IN THE RANGE OF REPRESENTABLE VALUES FOR ITS TYPE) the behavior is UNDEFINED. [...]"

And the chapter 6.3.6 about additive operators says:

  • usual arithmetic conversions on operands, which does not apply as everything is uint32_t.
  • and the result is the sum of both, which clearly does not fit into uint32_t.
  • FINE

Nothing is said, that the resulting value is converted to the result type - so 6.2.1.2 does not apply. But the value then clearly overflows, where 6.3 steps in.

As far as I can see - this is undefined behavior according to ISO 9899:1990. What did I miss? Is there something in the Corrigendae? Have I miss a line or word in the standard?

I am really confused now. :-)

With regards, Mark

Question Update

[2014-03-03] Solved

[2014-03-03] So thanks to Acme I now have a clear and complete answer for ANSI C99 (see answer to: "Is unsigned integer subtraction defined behavior": It is clear defined behavior as expected. And though I expect this for ANSI C90 also, I still can't read it out of the text of ISO 9899:1990, given the text passages above. So I consider my question still unanswered for the moment.

Edit: Just Typos | Edit2: add C90 & standards tags | Edit3: add Question Update | Edit4: add solved section | Edit5: add answer links :-) | Edit6: Update short unsigned integer overflows | Edit7: some typos

like image 913
Mark A. Avatar asked Feb 28 '14 13:02

Mark A.


People also ask

What is undefined Behaviour in C?

So, in C/C++ programming, undefined behavior means when the program fails to compile, or it may execute incorrectly, either crashes or generates incorrect results, or when it may fortuitously do exactly what the programmer intended.

How can we use unsigned integer in Java?

When comparing numbers as unsigned values, the left-most bit is considered the most significant bit instead of the sign bit. Thus, the result is different, with positive being smaller than negative: int unsignedComparison = Integer. compareUnsigned(positive, negative); assertEquals(-1, unsignedComparison);

What happens when you subtract two unsigned integers?

Subtracting two unsigned values of the same size will result in an unsigned value. If the first operand is less than the second the result will be arithmetically in correct.

Can Int be unsigned?

Unsigned integers are integers that can only hold non-negative whole numbers. A 1-byte unsigned integer has a range of 0 to 255. Compare this to the 1-byte signed integer range of -128 to 127.


1 Answers

There has been no significant change in this area from C90 to C99, or from C99 to C11.

C90 6.1.2.5 (there are no paragraph numbers, but it's the first paragraph on page 23 of the PDF) says:

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

Nearly the same wording (with the phrase "resulting unsigned integer type" changed to "resulting type" appears in 6.2.5 paragraph 9 in the C99 and C11 standards.

The only significant change (that I'm aware of) is an addition in C99 regarding signed conversion. In C90, if a signed or unsigned value is converted to a signed integer type, and the result cannot be represented in the target type, the result is implementation-defined. In C99 and C11, either the result is implementation-defined or an implementation-defined signal is raised. (I don't know of any compiler that takes advantage of the permission to raise a signal.)

As supercat points out in a comment, multiplication of two unsigned short values can overflow. Suppose short is 16 bits, int is 32 bits, and integer representations are typical (2's-complement for signed types, no padding bits). Then given:

unsigned short US = USHRT_MAX; // 65536

both operands in the expression

us * us

are promoted from unsigned short to int (because int can hold all possible values of type unsigned short) -- but the product, which is nearly 232, cannot fit in a 32-bit signed int.

(During the C standardization process in the late 1980s, the committee had to choose between "value-preserving" and "unsigned-preserving" integer promotions. They chose the former. With unsigned-preserving semantics, the unsigned short operands would be promoted to unsigned int, and this problem would not occur.)

like image 150
Keith Thompson Avatar answered Sep 21 '22 05:09

Keith Thompson