12

Edit: Changed the value for USHRT_MAX as it was not conformant as shown by comments.

Imagine you have a fancy compiler where its integer type limits, as defined in limits.h are:

#define INT_MAX   2147483647   /* Typical 32-bit system value */
#define USHRT_MAX 2147483647   /* ***Edited***, original question had 2000000000 */

And in my application I have the following code:

unsigned short a = 1500000000;
unsigned short b = 1500000000;
unsigned short c;
c = a + b;

As far as I know, what will happen in the last instruction will be:

  1. Integral promotion on a. As int can take all values of unsigned short, a gets promoted to int.
  2. For the same reasons, b gets promoted to int.
  3. Addition happens on int types.
  4. The result is not representable in int. Undefined Behavior due to paragraph 6.5/5.

Is my reasoning correct? Does this really invoke undefined behavior, or where did I go wrong? Note that my code only works with unsigned types, and a result applying the modulus for unsigned integers could be expected due to legal overflow on unsigned types.

If the answer to the previous question is "yes, undefined behavior", this happened for a legal conformant compiler. So, can you say that the application code I posted is incorrect? Do all non-explicitly-casted small unsigned integer additions potentially invoke undefined behavior?

atturri
  • 1,133
  • 7
  • 13
  • 4
    The easiest way this is possible is if `sizeof(unsigned short) == sizeof(int)`, and `unsigned short` has a padding-bit, while `int` doesn't. In that case, yes, adding two `unsigned short`s can invoke undefined behavior. – EOF May 27 '16 at 15:55
  • 2
    `USHRT_MAX 2000000000` is not possible in C. The maximum values of unsigned integers must be powers of two minus one. See 6.2.6.2.p1 – 2501 May 27 '16 at 15:56
  • @EOF In that unusual case than `sizeof(unsigned short) == sizeof(unsigned)`. So `int` overflow?, hmmm OTOH, maybe I am not taking into account padding. – chux - Reinstate Monica May 27 '16 at 15:56
  • 1
    Why would the addition between two rvalues of *equal type* require promotion? –  May 27 '16 at 15:57
  • 1
    @chux The important part is that it is entirely possible for `INT_MAX == USHORT_MAX`. – EOF May 27 '16 at 15:57
  • 1
    As per [this](http://port70.net/~nsz/c/c11/n1570.html#6.3.1.3) (case 3) the result is implementation defined. – Eugene Sh. May 27 '16 at 15:58
  • 8
    @Rhymoid In C, all types narrower than `int` are promoted before operations like `+`. – chux - Reinstate Monica May 27 '16 at 15:59
  • @EugeneSh. `int` will have higher rank than `unsigned short`, so case 4 applies if `INT_MAX >= USHORT_MAX`. – EOF May 27 '16 at 16:01
  • @EOF, even with `INT_MAX, USHORT_MAX, UINT_MAX` all same I see than `a + b` is `int` addition and therefore potential overflow and thus UB. simple use `0u + a + b` to avoid. – chux - Reinstate Monica May 27 '16 at 16:01
  • @chux: Sure, you can avoid the undefined behavior by casting to `unsigned`, because `unsigned` won't be converted to `int`. But the question boild down to whether the cast is required to ensure the operation is never undefined. – EOF May 27 '16 at 16:04
  • "Do all non-explicitly-casted small unsigned integer additions potentially invoke undefined behavior?" With unbounded narrow unsigned integers --> yes. – chux - Reinstate Monica May 28 '16 at 00:29
  • Possible duplicate of [Can unsigned integer incrementation lead to undefined defined behavior?](http://stackoverflow.com/questions/27004694/can-unsigned-integer-incrementation-lead-to-undefined-defined-behavior) – Vilhelm Gray Jul 01 '16 at 19:50

2 Answers2

7

It is not possible for USHRT_MAX to be defined as 2000000000. The maximum values of unsigned integers must be in the form: 2^n-1:

6.2.6.2 Integer types

  1. For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2 N−1 , so that objects of that type shall be capable of representing values from 0 to 2 N − 1 using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.

Let's say USHRT_MAX is 2^31-1 and INT_MAX is 2^31-1.

In this case the variables a and b will be promoted to type int, due to integer promotions, and the result of the signed addition will overflow.

gcc is smart enough to treat the addition of two unsigned short variables as unsigned when they are assigned to an unsigned short.

Nevertheless, for full portability the code should be:

c = a + 0u + b;
Community
  • 1
  • 1
2501
  • 25,460
  • 4
  • 47
  • 87
  • 3
    @chux: It'll still be *a* power-of-two minus one, just not the power of two that corresponds to `sizeof(type)*CHAR_BIT`. – EOF May 27 '16 at 16:20
  • 1
    @chux It must be 2^n-1, even with padding bits, since padding bits don't contribute to the value. A bit is either a value bit, or not at all. – 2501 May 27 '16 at 16:21
  • 1
    @chux `If there are N value bits, each bit shall represent a different power of 2 between 1 and 2 N−1 , so that objects of that type shall be capable of representing values from 0 to 2 N − 1 using a pure binary representation;` – 2501 May 27 '16 at 16:25
  • I now agree with your comments, The phrase "values of any padding bits are unspecified" threw me off, yet " padding bits don't contribute to the value" takes care of that. – chux - Reinstate Monica May 27 '16 at 16:26
  • 1
    @chux: Footnote 53: "Some combinations of padding bits might generate trap representations... **All other combinations of padding bits are alternative object representations of the value specified by the value bits.**" The part you quote isn't saying that padding bit X might represent adding 5 to the number; it's saying that it's unspecified whether the padding bits are set or unset. Note that the language used makes a distinction between the *value* of a bit and the power of two the bit *represents*. – user2357112 May 27 '16 at 16:28
  • @user2357112 Agree See [comment](http://stackoverflow.com/questions/37487730/can-an-unsigned-integer-addition-invoke-undefined-behavior/37488002#comment62472929_37487993) – chux - Reinstate Monica May 27 '16 at 16:29
  • Quite scary when you consider that predefined types like uint_least32_t might overflow and cause undefined behavior on multiplication, when you expected they will wrap. (Can happen if sizeof(int) > 4 and INT_MAX is > 2^32-1 ) – 2501 May 27 '16 at 16:35
  • 1
    @2501 Agree about scary. At least I do not see this would happen with `uint32_t` and `a+b` as `int` overflow not possible. Yet `a*b` could overflow on a 64-bit `int` machine. – chux - Reinstate Monica May 27 '16 at 16:42
  • 1
    @chux: On this topic, see my related question: http://stackoverflow.com/questions/4559251/would-making-plain-int-64-bit-break-a-lot-of-reasonable-code – R.. GitHub STOP HELPING ICE May 27 '16 at 17:02
  • Incidentally, on platforms with 32-bit "int", gcc will sometimes yield bogus behavior when assigning the product of two unsigned short values into an unsigned int, even though the authors of the rationale for C89 noted that one of the reasons they made unsigned short values promote to int was that the majority of then-current compilers would treat such multiplications as unsigned in cases where a result was between INT_MAX+1u and UINT_MAX but was not used in certain specific ways. – supercat Jul 28 '16 at 16:12
6

Can an unsigned integer addition invoke undefined behaviour?

This depends.

If

  • the rank of an int is greater then the two operands in question (unsigned short ints here, so in this case this is true) and
  • the values of the two operands in question would fit into an int (important corner case if not*1) and
  • the arithmetic operation (addition here) would overflow

then yes, this will invoke UB.

Reasons:

  1. The operands in question (unsigned short ints here) get promoted to int on arithmetic operations (they won't in case of *1).
  2. Overflowing arithmetic operations on ints invoke UB.

*1: If the operand does not fit into an int it gets promoted to unsigned int and with this any arithmetic operation as per 2. above would not invoke UB.

alk
  • 69,737
  • 10
  • 105
  • 255
  • That seems correct, it is possible for unsigned short to not fit into an int however strange that seems. (I already upvoted.) – 2501 May 27 '16 at 17:00
  • @2501: As per the Standard, `int` and `short int` may have the same range. Under this conditions an `unsigned short int` might not fit into an `int`. – alk May 27 '16 at 17:05