unsigned short addition/subtraction overflow

[pete]

Re: unsigned short addition/subtraction overflow

Kevin Goodsell wrote:[color=blue]
>
> pete wrote:[color=green]
> >
> > No.
> > 65536 is an allowable value for INT_MAX.[/color]
>
> I don't think so.[/color]

65535
Thank you.

--
pete

[Peter Nilsson]

Re: unsigned short addition/subtraction overflow

pete <pfiland@mindsp ring.com> wrote in message news:<3FE5ADF9. 1044@mindspring .com>...[color=blue]
> pete wrote:[/color]
....[color=blue][color=green]
> > If INT_MAX equals 65535,[/color]
>
> I meant 65536.[/color]

Why? Neither is likely, but 65536 is considerably less so. Some would
argue (myself included) that 65536 is impossible on a conforming
implementation (be that C90 or C99).

--
Peter

[pete]

Re: unsigned short addition/subtraction overflow

Peter Nilsson wrote:[color=blue]
>
> pete <pfiland@mindsp ring.com> wrote in message news:<3FE5ADF9. 1044@mindspring .com>...[color=green]
> > pete wrote:[/color]
> ...[color=green][color=darkred]
> > > If INT_MAX equals 65535,[/color]
> >
> > I meant 65536.[/color]
>
> Why? Neither is likely, but 65536 is considerably less so. Some would
> argue (myself included) that 65536 is impossible on a conforming
> implementation (be that C90 or C99).[/color]

You would be right.

--
pete

[Christopher Benson-Manica]

Re: unsigned short addition/subtraction overflow

Chris Torek <nospam@torek.n et> spoke thus:
[color=blue]
> Actually, this is potentially quite different.[/color]
[color=blue]
> If ANSI/ISO C used the *correct* rules (according to me :-) )
> it would be precisely the same, but we are stuck with quite
> bogus widening rules due to a mistaken decision in the 1980s:
> "when a narrow unsigned integer type widens, the resulting
> type is signed if all the unsigned values fit, otherwise
> it is unsigned".[/color]
[color=blue]
> etc.[/color]

Wow, what a great article! The only thing I'm unclear on now is why
such a seemingly obvious point escaped the C89 people, and why you
weren't around to dissuade them ;)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Chris Torek]

Re: unsigned short addition/subtraction overflow

>Chris Torek <nospam@torek.n et> spoke thus:[color=blue][color=green]
>> If ANSI/ISO C used the *correct* rules (according to me :-) ) ...[/color][/color]

In article <news:bs76vt$er 9$2@chessie.cir r.com>
Christopher Benson-Manica <ataru@nospam.c yberspace.org> wrote:[color=blue]
>Wow, what a great article! The only thing I'm unclear on now is why
>such a seemingly obvious point escaped the C89 people, and why you
>weren't around to dissuade them ;)[/color]

I was but a poor student at the time (making about four bucks an
hour, with a limit of 20 hrs/week, as "student staff") and could
not afford exotic vacation trips to ANSI C committee meetings. :-)
I did, however, hear from someone who did go to them that this was
actually something of a "hotly debated" topic.

The VAX PCC did it "my" way, and apparently Plauger's C compiler(s)
did it the other way. The "base document" -- i.e., K&R-1 -- did
not even allow for the possibility of "unsigned short" and "unsigned
char", and if you have "narrow unsigned always widens to unsigned"
as a rule, you need an exception for plain char if/when plain char
is unsigned (as on the IBM 370), so that EOF can be negative.

The results of the rules differ only in "questionab ly signed" cases,
which are rare enough. But the ANSI rules are so ugly to work with
that I would prefer a special exception for "plain char is unsigned
on this implementation, yet nonetheless widens to signed int". Note
that this exception would force the constraint that CHAR_MAX < INT_MAX,
even when char is unsigned, which would have the happy side effect
of making stdio "work right".
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Old Wolf]

Re: unsigned short addition/subtraction overflow

> If we have two "unsigned short"s, values 65535 and 3 respectively,[color=blue]
> 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.[/color]

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]

Re: unsigned short addition/subtraction overflow

"Old Wolf" <oldwolf@inspir e.net.nz> wrote in message
news:843a4f78.0 312230125.1dc3a 72b@posting.goo gle.com...[color=blue][color=green]
> > 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.[/color]
>
> Just to make sure this is absolutely clear in my mind:[/color]

You should get a good C book, or check out the Standard(s) or a draft like
N869.
[color=blue]
> You are saying that the type of the expression
> (unsigned short)65535 + (unsigned short)3
> could be something other than "unsigned short" ?[/color]

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

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;
}
[color=blue]
> This would be relevant to templates and/or function overloading, eg.
> void f(unsigned int t) { /*...*/ }
> void f(signed int t} { /*...*/ }[/color]

Ask a C++ group.
[color=blue]
> 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?[/color]

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]

Re: unsigned short addition/subtraction overflow

"Peter Nilsson" <airia@acay.com .au> wrote in message news:<3fe8317c@ news.rivernet.c om.au>...[color=blue]
>[color=green]
> > You are saying that the type of the expression
> > (unsigned short)65535 + (unsigned short)3
> > could be something other than "unsigned short" ?[/color]
>
> It _has_ to be.
>[color=green]
> > Also, if we have
> > unsigned short a = 65535, b = 3;
> > then could the type of
> > (a + b)
> > not be "unsigned short" ?[/color]
>
> The type of (a + b) will _never_ be unsigned short, since integer operands
> of + are always subject to integral promotion.
>[/color]

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]

Re: unsigned short addition/subtraction overflow

Andy wrote:[color=blue]
>
> "Peter Nilsson" <airia@acay.com .au> wrote in message news:<3fe8317c@ news.rivernet.c om.au>...[color=green]
> >[color=darkred]
> > > You are saying that the type of the expression
> > > (unsigned short)65535 + (unsigned short)3
> > > could be something other than "unsigned short" ?[/color]
> >
> > It _has_ to be.
> >[color=darkred]
> > > Also, if we have
> > > unsigned short a = 65535, b = 3;
> > > then could the type of
> > > (a + b)
> > > not be "unsigned short" ?[/color]
> >
> > The type of (a + b) will _never_ be unsigned short,
> > since integer operands
> > of + are always subject to integral promotion.
> >[/color]
>
> 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?[/color]

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]

Re: unsigned short addition/subtraction overflow

pete <pfiland@mindsp ring.com> wrote in message news:<3FEA33B6. 7DD1@mindspring .com>...[color=blue][color=green]
> >[/color]
> 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.[/color]

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]

Re: unsigned short addition/subtraction overflow

Andy wrote:
[color=blue]
> pete <pfiland@mindsp ring.com> wrote in message
> news:<3FEA33B6. 7DD1@mindspring .com>...[color=green][color=darkred]
>> >[/color]
>> 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.[/color]
>
> Can unsigned short be more than 2 bytes long?[/color]

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

<snip>
[color=blue]
> 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.[/color]

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

--
Richard Heathfield : binary@eton.pow ernet.co.uk
"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]

Re: unsigned short addition/subtraction overflow

Andy wrote:[color=blue]
>
> pete <pfiland@mindsp ring.com> wrote in message news:<3FEA33B6. 7DD1@mindspring .com>...[color=green][color=darkred]
> > >[/color]
> > 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.[/color]
>
> 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.[/color]

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.
[color=blue]
> 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?[/color]

No.
[color=blue]
> 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.[/color]

The problem is that you don't know
if the operands to the addition operator above, are unsigned.
[color=blue]
> How about (unsigned long)c1 + (unsigned long)c2?[/color]

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]

Re: unsigned short addition/subtraction overflow

"Andy" <bikejog@hotmai l.com> wrote in message
news:aed59298.0 312282002.44e70 ebc@posting.goo gle.com...
....[color=blue]
> Can unsigned short be more than 2 bytes long?[/color]

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
implementation without contradiction.

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.
[color=blue]
> 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.[/color]

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.
[color=blue]
> 2. If INT_MAX > USHRT_MAX, then c1 and c2 will be promoted to
> int, but c1+c2 is always <= 2*65535[/color]

Strictly speaking, in this case, the sum of two unsigned short values is
always less than or equal to 2*USHRT_MAX+1.
[color=blue]
> so the addition can
> never overflow because INT_MAX is >= 4 bytes.[/color]

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'.
[color=blue]
> 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.[/color]

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.
[color=blue]
> But the edition I got is old (~1991) and
> predates the ANSI standard.[/color]

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.]
[color=blue]
> How about (unsigned long)c1 + (unsigned long)c2?[/color]

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]

Re: unsigned short addition/subtraction overflow

"Andy" <bikejog@hotmai l.com> wrote in message
news:aed59298.0 312241428.408db 4bb@posting.goo gle.com...[color=blue]
> "Peter Nilsson" <airia@acay.com .au> wrote in message[/color]
news:<3fe8317c@ news.rivernet.c om.au>...[color=blue][color=green]
> >[color=darkred]
> > > You are saying that the type of the expression
> > > (unsigned short)65535 + (unsigned short)3
> > > could be something other than "unsigned short" ?[/color]
> >
> > It _has_ to be.
> >[color=darkred]
> > > Also, if we have
> > > unsigned short a = 65535, b = 3;
> > > then could the type of
> > > (a + b)
> > > not be "unsigned short" ?[/color]
> >
> > The type of (a + b) will _never_ be unsigned short, since integer[/color][/color]
operands[color=blue][color=green]
> > of + are always subject to integral promotion.[/color]
>
> 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[/color]
have[color=blue]
> modulus 2^n (n=bit size of unsigned short) arithmetic. Am I right?[/color]

Yes, but only assuming the value to be assigned can itself be computed
without undefined behaviour.
[color=blue]
> eg.
>
> unsigned short i = (unsigned short)65535 + (unsigned short)3;
>
> result of i is 2. Correct?[/color]

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]

Re: unsigned short addition/subtraction overflow

"Peter Nilsson" <airia@acay.com .au> wrote in message news:<3ff01772$ 1@news.rivernet .com.au>...[color=blue]
>
> #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.[/color]

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