Velocity Reviews > unsigned short addition/subtraction overflow

# unsigned short addition/subtraction overflow

Old Wolf
Guest
Posts: n/a

 12-23-2003
> If we have two "unsigned short"s, values 65535 and 3 respectively,
> and go to add them, we continue to have "case a" and "case b".
> In case (a), the sum is 65535U + 3U, which has type unsigned int
> and value 2. In case (b), the sum is 65535 + 3, which has type
> signed int and value 65538.

Just to make sure this is absolutely clear in my mind:
You are saying that the type of the expression
(unsigned short)65535 + (unsigned short)3
could be something other than "unsigned short" ?

Also, if we have
unsigned short a = 65535, b = 3;
then could the type of
(a + b)
not be "unsigned short" ?

This would be relevant to templates and/or function overloading, eg.
void f(unsigned int t) { /*...*/ }
void f(signed int t} { /*...*/ }

and you went: f((unsigned short)65535 + (unsigned short) 3)
or: f(65535u + 3u)
or, with the above declarations:
f(a+b) // might not even know till runtime

Finally, I had been taught that "65535u" means (unsigned int)65535
which is a whole different kettle of fish to (unsigned short)65535.
Is this correct?

Peter Nilsson
Guest
Posts: n/a

 12-23-2003
"Old Wolf" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> > If we have two "unsigned short"s, values 65535 and 3 respectively,
> > and go to add them, we continue to have "case a" and "case b".
> > In case (a), the sum is 65535U + 3U, which has type unsigned int
> > and value 2. In case (b), the sum is 65535 + 3, which has type
> > signed int and value 65538.

>
> Just to make sure this is absolutely clear in my mind:

You should get a good C book, or check out the Standard(s) or a draft like
N869.

> You are saying that the type of the expression
> (unsigned short)65535 + (unsigned short)3
> could be something other than "unsigned short" ?

It _has_ to be.

> Also, if we have
> unsigned short a = 65535, b = 3;
> then could the type of
> (a + b)
> not be "unsigned short" ?

The type of (a + b) will _never_ be unsigned short, since integer operands
of + are always subject to integral promotion.

Try the following program on an implementation where short and int have
different sizes:

#include <stdio.h>

int main(void)
{
unsigned short a = 65530;
unsigned short b = 3;

printf("%u\n", (unsigned) sizeof( a ));
printf("%u\n", (unsigned) sizeof( + a ));
printf("%u\n", (unsigned) sizeof( a + b ));

return 0;
}

> This would be relevant to templates and/or function overloading, eg.
> void f(unsigned int t) { /*...*/ }
> void f(signed int t} { /*...*/ }

Ask a C++ group.

> Finally, I had been taught that "65535u" means (unsigned int)65535
> which is a whole different kettle of fish to (unsigned short)65535.
> Is this correct?

Define 'kettle of fish'.

A singular u suffix means the constant (if valid) is an unsigned integral
type starting in rank from unsigned int, through the higher ranked standard
unsigned integers, then (for C99) suitable extended integer types(*). For
65535u, it's an unsigned int.

(*) It seems that constants larger than the standard integer type range need
not necessarily attain the lowest ranked eligible extended integer type.

--
Peter

Andy
Guest
Posts: n/a

 12-24-2003
"Peter Nilsson" <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
>
> > You are saying that the type of the expression
> > (unsigned short)65535 + (unsigned short)3
> > could be something other than "unsigned short" ?

>
> It _has_ to be.
>
> > Also, if we have
> > unsigned short a = 65535, b = 3;
> > then could the type of
> > (a + b)
> > not be "unsigned short" ?

>
> The type of (a + b) will _never_ be unsigned short, since integer operands
> of + are always subject to integral promotion.
>

Yes, but if you assign the result to an unsigned short variable, then
the result will be truncated and is still unsigned short and you still have
modulus 2^n (n=bit size of unsigned short) arithmetic. Am I right? eg.

unsigned short i = (unsigned short)65535 + (unsigned short)3;

result of i is 2. Correct?

Andy

pete
Guest
Posts: n/a

 12-25-2003
Andy wrote:
>
> "Peter Nilsson" <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> >
> > > You are saying that the type of the expression
> > > (unsigned short)65535 + (unsigned short)3
> > > could be something other than "unsigned short" ?

> >
> > It _has_ to be.
> >
> > > Also, if we have
> > > unsigned short a = 65535, b = 3;
> > > then could the type of
> > > (a + b)
> > > not be "unsigned short" ?

> >
> > The type of (a + b) will _never_ be unsigned short,
> > since integer operands
> > of + are always subject to integral promotion.
> >

>
> Yes, but if you assign the result to an unsigned short variable,
> then the result will be truncated and is
> still unsigned short and you still have
> modulus 2^n (n=bit size of unsigned short) arithmetic.
> Am I right? eg.
>
> unsigned short i = (unsigned short)65535 + (unsigned short)3;
>
> result of i is 2. Correct?

The cast operates on the constants.
The results of the casts, are the operands to the addition operator.
The operands of the addition operator are promoted to either
int or unsigned.
The right operand of the assignment operator
is converted to the type of the left.

If INT_MAX is 32767
then the operands will be promoted to unsigned.
If the result of the addition is greater than UINT_MAX
then the result will be reduced to 2,
otherwise the result of the addition will be 65538.

if INT_MAX is greater than 32767
then the operands will be promoted to int.
If the result of the addition is greater than INT_MAX,
then the behavior is undefined,
otherwise the result of the addition will be 65538.

If the result of the addition is greater than USHRT_MAX,
then i will be assigned a value of 2,
otherwise, i will be asigned the value of the result of the addition,
unless the addition caused undefined behavior.

--
pete

Andy
Guest
Posts: n/a

 12-29-2003
pete <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> >

> if INT_MAX is greater than 32767
> then the operands will be promoted to int.
> If the result of the addition is greater than INT_MAX,
> then the behavior is undefined,
> otherwise the result of the addition will be 65538.
>
> If the result of the addition is greater than USHRT_MAX,
> then i will be assigned a value of 2,
> otherwise, i will be asigned the value of the result of the addition,
> unless the addition caused undefined behavior.

Can unsigned short be more than 2 bytes long? If not, then
(unsigned short)c1 + (unsigned short)c2 will never cause undefined
behavior because
1. If INT_MAX == USHRT_MAX, then c1 and c2 will be promoted
to unsigned short and unsigned short additions will never
cause undefined behaviors.
2. If INT_MAX > USHRT_MAX, then c1 and c2 will be promoted to
int, but c1+c2 is always <= 2*65535 so the addition can
never overflow because INT_MAX is >= 4 bytes.

So then is correct to say that (unsigned short)c1 + (unsigned short)c2
will never cause undefined behaviors? The reason is because in the
book "C, Traps and Pitfalls", the author states that unsigned arithmetic
shall always be done modulus 2^n manner where n is the number of bits
for the unsigned variable. But the edition I got is old (~1991) and
predates the ANSI standard. How about (unsigned long)c1 + (unsigned long)c2?

Andy

Richard Heathfield
Guest
Posts: n/a

 12-29-2003
Andy wrote:

> pete <(E-Mail Removed)> wrote in message
> news:<(E-Mail Removed)>...
>> >

>> if INT_MAX is greater than 32767
>> then the operands will be promoted to int.
>> If the result of the addition is greater than INT_MAX,
>> then the behavior is undefined,
>> otherwise the result of the addition will be 65538.
>>
>> If the result of the addition is greater than USHRT_MAX,
>> then i will be assigned a value of 2,
>> otherwise, i will be asigned the value of the result of the addition,
>> unless the addition caused undefined behavior.

>
> Can unsigned short be more than 2 bytes long?

Yes. On a Cray, for example, it might easily be eight bytes long.

<snip>

> book "C, Traps and Pitfalls", the author states that unsigned arithmetic
> shall always be done modulus 2^n manner where n is the number of bits
> for the unsigned variable. But the edition I got is old (~1991) and
> predates the ANSI standard.

The ANSI Standard dates from 1989. The author's statement is, however,
correct.

--
Richard Heathfield : http://www.velocityreviews.com/forums/(E-Mail Removed)
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

pete
Guest
Posts: n/a

 12-29-2003
Andy wrote:
>
> pete <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> > >

> > if INT_MAX is greater than 32767
> > then the operands will be promoted to int.
> > If the result of the addition is greater than INT_MAX,
> > then the behavior is undefined,
> > otherwise the result of the addition will be 65538.
> >
> > If the result of the addition is greater than USHRT_MAX,
> > then i will be assigned a value of 2,
> > otherwise,
> > i will be asigned the value of the result of the addition,
> > unless the addition caused undefined behavior.

>
> Can unsigned short be more than 2 bytes long? If not, then
> (unsigned short)c1 + (unsigned short)c2 will never cause undefined
> behavior because
> 1. If INT_MAX == USHRT_MAX, then c1 and c2 will be promoted
> to unsigned short and unsigned short additions will never
> cause undefined behaviors.

Nothing ever gets promoted to unsigned short.
"the integer promotions" are either to int or to unsigned int.

N869
6.3.1 Arithmetic operands
6.3.1.1 Boolean, characters, and integers
[#2]
If an int can represent all values of the original type, the
value is converted to an int; otherwise, it is converted to
an unsigned int. These are called the integer
promotions.

> 2. If INT_MAX > USHRT_MAX, then c1 and c2 will be promoted to
> int, but c1+c2 is always <= 2*65535 so the addition can
> never overflow because INT_MAX is >= 4 bytes.
>
> So then is correct to say that
> (unsigned short)c1 + (unsigned short)c2
> will never cause undefined behaviors?

No.

> The reason is because in the
> book "C, Traps and Pitfalls",
> the author states that unsigned arithmetic
> shall always be done modulus 2^n manner where n is the number of bits
> for the unsigned variable. But the edition I got is old (~1991) and
> predates the ANSI standard.

The problem is that you don't know
if the operands to the addition operator above, are unsigned.

> How about (unsigned long)c1 + (unsigned long)c2?

The operands of the addition operator above, are unsigned types
which are not subject to the integer promotions,
so it's OK.

--
pete

Peter Nilsson
Guest
Posts: n/a

 12-29-2003
"Andy" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
....
> Can unsigned short be more than 2 bytes long?

Yes. The only _size_ criteria is that sizeof(short) >= 1. Of course, it has
to satisfy the minimum range requirement [0..65535], so the size of a short
(and therefore unsigned short) must be at least 16 bits. But since CHAR_BIT
may be anything >= 8, like 16 or 32 (e.g. DSP chipsets often have
implementations where CHAR_BIT is 32), it is possible for sizeof(short) to
be 1.

Theoretically, sizeof(short) > sizeof(long) is allowed in a conforming

Basically, the byte size of unsigned short is totally irrelevent to the
issue. The semantics of C integer expressions are defined by type and value,
not by the size of the representations.

You would do well to avoid forming preconceptions about the size of various
integer types. Not because there are theoretical possibilities, but because
there are very real practical problems that can result as a consequence.
E.g., when the world went from 16 to 32-bit home computers an awful lot of
poor code had to be painstakingly rewritten. Now that we sit on the edge of
64-bit machines becoming the 'norm', you should appreciate that making
assumptions about integer sizes may cost you (or the people who have to
maintain your code) in a few years time.

> If not, then
> (unsigned short)c1 + (unsigned short)c2 will never cause undefined
> behavior because
> 1. If INT_MAX == USHRT_MAX, then c1 and c2 will be promoted
> to unsigned short and unsigned short additions will never
> cause undefined behaviors.

INT_MAX == USHRT_MAX is extremely unlikely[*], but in such a case, the
operands of + will both be promoted to int since all the values of unsigned
short _are_ representable as an int. The promotion to int applies to the
operands, which in this case are...

(unsigned short) c1 and (unsigned short) c2

A cast will not _override_ integral promotion.

> 2. If INT_MAX > USHRT_MAX, then c1 and c2 will be promoted to
> int, but c1+c2 is always <= 2*65535

Strictly speaking, in this case, the sum of two unsigned short values is
always less than or equal to 2*USHRT_MAX+1.

> so the addition can
> never overflow because INT_MAX is >= 4 bytes.

There is nothing in the standards that state that an int must be twice the
size of an unsigned short. There are plenty of implementations where short
and int have the same properties except for their 'rank'.

> So then is correct to say that (unsigned short)c1 + (unsigned short)c2
> will never cause undefined behaviors? The reason is because in the
> book "C, Traps and Pitfalls", the author states that unsigned arithmetic
> shall always be done modulus 2^n manner where n is the number of bits
> for the unsigned variable.

Yes, but you have to be careful to assertain whether the arithmetic is
indeed being performed on unsigned operands. In the case of adding two
unsigned short values, that isn't a given.

> But the edition I got is old (~1991) and
> predates the ANSI standard.

I've never read the book, but what it says is true. What the author may not
have known at the time of original writing was whether unsigned short would
possibly promote to int, instead of always promoting to unsigned int. [This
was apparently contested by the C committee.]

> How about (unsigned long)c1 + (unsigned long)c2?

The two operands have type unsigned long and are therefore not subject to
integral promotion, nor indeed any other promotion. So the result is an
unsigned long calculated modulo ULONG_MAX+1.
[*] C90 apparently has no concept of padded integers or integer trap
representations, so you're not likely to find a conforming C implementation
where INT_MAX == USHRT_MAX any time soon. It's possible in C99, but I doubt
anyone will ever actually build such an implementation. [It would be
possible on a machine which used floating point instructions to mimic
integer calculations, but such a machine would probably have a hard time
implementing unsigned integer types as a whole, so the compiler writers
would probably give it up as a bad job. ]

--
Peter

Peter Nilsson
Guest
Posts: n/a

 12-29-2003
"Andy" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> "Peter Nilsson" <(E-Mail Removed)> wrote in message

news:<(E-Mail Removed)>...
> >
> > > You are saying that the type of the expression
> > > (unsigned short)65535 + (unsigned short)3
> > > could be something other than "unsigned short" ?

> >
> > It _has_ to be.
> >
> > > Also, if we have
> > > unsigned short a = 65535, b = 3;
> > > then could the type of
> > > (a + b)
> > > not be "unsigned short" ?

> >
> > The type of (a + b) will _never_ be unsigned short, since integer

operands
> > of + are always subject to integral promotion.

>
> Yes, but if you assign the result to an unsigned short variable, then
> the result will be truncated and is still unsigned short and you still

have
> modulus 2^n (n=bit size of unsigned short) arithmetic. Am I right?

Yes, but only assuming the value to be assigned can itself be computed
without undefined behaviour.

> eg.
>
> unsigned short i = (unsigned short)65535 + (unsigned short)3;
>
> result of i is 2. Correct?

Not necessarily. Even after casting, the operands of + are _still_ subject
to integral promotion. So, the expression is effectively...

#if USHRT_MAX <= INT_MAX

unsigned short i = (int) (unsigned short) 65535 + (int) (unsigned short)
3;

#else

unsigned short i = (unsigned) (unsigned short) 65535 + (unsigned)
(unsigned short) 3;

#endif

It's highly unlikely, but it is possible for INT_MAX to equal USHRT_MAX, in
which case, the addition may overflow an int, invoking undefined behaviour.

--
Peter

Andy
Guest
Posts: n/a

 12-31-2003
"Peter Nilsson" <(E-Mail Removed)> wrote in message news:<3ff01772\$(E-Mail Removed)>...
>
> #if USHRT_MAX <= INT_MAX
>
> unsigned short i = (int) (unsigned short) 65535 + (int) (unsigned short)
> 3;
>
> #else
>
> unsigned short i = (unsigned) (unsigned short) 65535 + (unsigned)
> (unsigned short) 3;
>
> #endif
>
> It's highly unlikely, but it is possible for INT_MAX to equal USHRT_MAX, in
> which case, the addition may overflow an int, invoking undefined behaviour.

Yes. I got it now. Thanks for clearing things up with the <=
point. I guess, then I can say that unsigned short
addition/subtraction on a machine where sizeof(unsigned short) ==
sizeof(int) will always yield valid modulus 2^n results. Correct?

Thanks
Andy