unsigned short addition/subtraction overflow

[Andy]

Hi,
Are 1 through 4 defined behaviors in C?

unsigned short i;
unsigned long li; /* 32-bit wide */

1. i = 65535 + 3;
2. i = 1 - 3;
3. li = (unsigned long)0xFFFFFFFF + 3;
4. li = 1 - 3;

TIA
Andy

[James Hu]

Re: unsigned short addition/subtraction overflow

On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:[color=blue]
> Are 1 through 4 defined behaviors in C?
>
> unsigned short i;
> unsigned long li; /* 32-bit wide */
>
> 1. i = 65535 + 3;
> 2. i = 1 - 3;
> 3. li = (unsigned long)0xFFFFFFFF + 3;
> 4. li = 1 - 3;[/color]

Yes.

-- James

[pete]

Re: unsigned short addition/subtraction overflow

James Hu wrote:[color=blue]
>
> On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:[color=green]
> > Are 1 through 4 defined behaviors in C?
> >
> > unsigned short i;
> > unsigned long li; /* 32-bit wide */
> >
> > 1. i = 65535 + 3;
> > 2. i = 1 - 3;
> > 3. li = (unsigned long)0xFFFFFFFF + 3;
> > 4. li = 1 - 3;[/color]
>
> Yes.[/color]

No.
65536 is an allowable value for INT_MAX.
(65535 + 3) would be integer overflow
and undefined behavior in that case.

--
pete

[Robert Stankowic]

Re: unsigned short addition/subtraction overflow


"pete" <pfiland@mindsp ring.com> schrieb im Newsbeitrag
news:3FE5809B.2 575@mindspring. com...[color=blue]
> James Hu wrote:[color=green]
> >
> > On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:[color=darkred]
> > > Are 1 through 4 defined behaviors in C?
> > >
> > > unsigned short i;
> > > unsigned long li; /* 32-bit wide */
> > >
> > > 1. i = 65535 + 3;
> > > 2. i = 1 - 3;
> > > 3. li = (unsigned long)0xFFFFFFFF + 3;
> > > 4. li = 1 - 3;[/color]
> >
> > Yes.[/color]
>
> No.
> 65536 is an allowable value for INT_MAX.
> (65535 + 3) would be integer overflow
> and undefined behavior in that case.[/color]

From N869: 6.2.5
9 The range of nonnegative values of a signed integer type is a subrange of
the
corresponding unsigned integer type, and the representation of the same
value in each
type is the same.28) 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 type.

However, I am not sure about
i = 1 - 3;
and
li = 1 - 3;
but I think it is defined as far as I understand the integer promotion
rules.

cheers
Robert

[CBFalconer]

Re: unsigned short addition/subtraction overflow

pete wrote:[color=blue]
> James Hu wrote:[color=green]
> > On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:
> >[color=darkred]
> > > Are 1 through 4 defined behaviors in C?
> > >
> > > unsigned short i;
> > > unsigned long li; /* 32-bit wide */
> > >
> > > 1. i = 65535 + 3;
> > > 2. i = 1 - 3;
> > > 3. li = (unsigned long)0xFFFFFFFF + 3;
> > > 4. li = 1 - 3;[/color]
> >
> > Yes.[/color]
>
> No.
> 65536 is an allowable value for INT_MAX.
> (65535 + 3) would be integer overflow
> and undefined behavior in that case.[/color]

Good catch. However, change "would" to "could".

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[pete]

Re: unsigned short addition/subtraction overflow

Robert Stankowic wrote:[color=blue]
>
> "pete" <pfiland@mindsp ring.com> schrieb im Newsbeitrag
> news:3FE5809B.2 575@mindspring. com...[color=green]
> > James Hu wrote:[color=darkred]
> > >
> > > On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:
> > > > Are 1 through 4 defined behaviors in C?
> > > >
> > > > unsigned short i;
> > > > unsigned long li; /* 32-bit wide */
> > > >
> > > > 1. i = 65535 + 3;
> > > > 2. i = 1 - 3;
> > > > 3. li = (unsigned long)0xFFFFFFFF + 3;
> > > > 4. li = 1 - 3;
> > >
> > > Yes.[/color]
> >
> > No.
> > 65536 is an allowable value for INT_MAX.
> > (65535 + 3) would be integer overflow
> > and undefined behavior in that case.[/color]
>
> From N869: 6.2.5
> 9 The range of nonnegative values of a
> signed integer type is a subrange of
> the corresponding unsigned integer type,
> and the representation of the same value in each
> type is the same.28)
> 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 type.[/color]

What's your point ?
If INT_MAX equals 65535,
then there are no unsigned operands in (65535 + 3), just two ints.
[color=blue]
> However, I am not sure about
> i = 1 - 3;
> and
> li = 1 - 3;
> but I think it is defined as far as I
> understand the integer promotion rules.[/color]

The standard defines what happens when any integer
is the right operand of the assignment operator,
and the left operand is an unsigned type.

--
pete

[pete]

Re: unsigned short addition/subtraction overflow

CBFalconer wrote:[color=blue]
>
> pete wrote:[color=green]
> > James Hu wrote:[color=darkred]
> > > On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:
> > >
> > > > Are 1 through 4 defined behaviors in C?
> > > >
> > > > unsigned short i;
> > > > unsigned long li; /* 32-bit wide */
> > > >
> > > > 1. i = 65535 + 3;
> > > > 2. i = 1 - 3;
> > > > 3. li = (unsigned long)0xFFFFFFFF + 3;
> > > > 4. li = 1 - 3;
> > >
> > > Yes.[/color]
> >
> > No.
> > 65536 is an allowable value for INT_MAX.
> > (65535 + 3) would be integer overflow
> > and undefined behavior in that case.[/color]
>
> Good catch. However, change "would" to "could".[/color]

I think I got that right.
"in that case" meaning the case when 65536 was equal to INT_MAX,
then (65535 + 3) most definitely would overflow,
and definitely be undefined behavior.
The particular form of the manifestation of the undefined behavior,
would be different matter, if that's what you mean.

--
pete

[pete]

Re: unsigned short addition/subtraction overflow

pete wrote:[color=blue]
>
> Robert Stankowic wrote:[color=green]
> >
> > "pete" <pfiland@mindsp ring.com> schrieb im Newsbeitrag
> > news:3FE5809B.2 575@mindspring. com...[color=darkred]
> > > James Hu wrote:
> > > >
> > > > On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:
> > > > > Are 1 through 4 defined behaviors in C?
> > > > >
> > > > > unsigned short i;
> > > > > unsigned long li; /* 32-bit wide */
> > > > >
> > > > > 1. i = 65535 + 3;
> > > > > 2. i = 1 - 3;
> > > > > 3. li = (unsigned long)0xFFFFFFFF + 3;
> > > > > 4. li = 1 - 3;
> > > >
> > > > Yes.
> > >
> > > No.
> > > 65536 is an allowable value for INT_MAX.
> > > (65535 + 3) would be integer overflow
> > > and undefined behavior in that case.[/color]
> >
> > From N869: 6.2.5
> > 9 The range of nonnegative values of a
> > signed integer type is a subrange of
> > the corresponding unsigned integer type,
> > and the representation of the same value in each
> > type is the same.28)
> > 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 type.[/color]
>
> What's your point ?
> If INT_MAX equals 65535,[/color]

I meant 65536.
[color=blue]
> then there are no unsigned operands in (65535 + 3), just two ints.
>[color=green]
> > However, I am not sure about
> > i = 1 - 3;
> > and
> > li = 1 - 3;
> > but I think it is defined as far as I
> > understand the integer promotion rules.[/color]
>
> The standard defines what happens when any integer
> is the right operand of the assignment operator,
> and the left operand is an unsigned type.[/color]

--
pete

[Andy]

Re: unsigned short addition/subtraction overflow

bikejog@hotmail .com (Andy) wrote in message news:<aed59298. 0312202231.78bb 5fae@posting.go ogle.com>...[color=blue]
> Hi,
> Are 1 through 4 defined behaviors in C?
>
> unsigned short i;
> unsigned long li; /* 32-bit wide */
>
> 1. i = 65535 + 3;
> 2. i = 1 - 3;
> 3. li = (unsigned long)0xFFFFFFFF + 3;
> 4. li = 1 - 3;
>
> TIA
> Andy[/color]

Actually what I really meant is for unsigned operations.
This is what I want to know. Are the following defined in
C and always guaranteed warped around values?

unsigned short i;
unsigned long li; /* 32-bit wide */

1. i = (unsigned short)65535 + (unsigned short)3;
2. i = (unsigned short)1 - (unsigned short)3;
3. li = (unsigned long)0xFFFFFFFF + (unsigned long)3;
4. li = (unsigned long)1 - (unsigned long)3;

TIA
Andy

[Robert Stankowic]

Re: unsigned short addition/subtraction overflow


"pete" <pfiland@mindsp ring.com> schrieb im Newsbeitrag
news:3FE5ADF9.1 044@mindspring. com...[color=blue]
> pete wrote:[color=green]
> >
> > Robert Stankowic wrote:[color=darkred]
> > >
> > > "pete" <pfiland@mindsp ring.com> schrieb im Newsbeitrag[/color][/color][/color]
[....]
[color=blue][color=green]
> > What's your point ?
> > If INT_MAX equals 65535,[/color]
>
> I meant 65536.
>[color=green]
> > then there are no unsigned operands in (65535 + 3), just two ints.[/color][/color]

I see your point.
Thanks
Robert

[Kevin Goodsell]

Re: unsigned short addition/subtraction overflow

pete wrote:[color=blue]
>
> No.
> 65536 is an allowable value for INT_MAX.[/color]

I don't think so. INT_MAX pretty much has to be an odd number, I think.
In fact, to satisfy the requirement that the non-negative integer values
have the same representation as the same values for the corresponding
unsigned type, and the requirement that unsigned types use a pure binary
representation, I think it's safe to say that INT_MAX must be (2^N)-1
for some integer N, which must be 15 or greater.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Kevin Goodsell]

Re: unsigned short addition/subtraction overflow

Andy wrote:
[color=blue]
>
> Actually what I really meant is for unsigned operations.
> This is what I want to know. Are the following defined in
> C and always guaranteed warped around values?
>
> unsigned short i;
> unsigned long li; /* 32-bit wide */
>
> 1. i = (unsigned short)65535 + (unsigned short)3;[/color]

You could write these easer this way:

i = 65535u + 3u;
[color=blue]
> 2. i = (unsigned short)1 - (unsigned short)3;
> 3. li = (unsigned long)0xFFFFFFFF + (unsigned long)3;
> 4. li = (unsigned long)1 - (unsigned long)3;
>[/color]

It's difficult to produce undefined behavior with unsigned values.
(Unless you divide by zero, maybe. I don't actually know what the
standard says about that, which surprises me.) Overflow doesn't occur
with unsigned types, but it's possible for unsigned types that are
narrower than int to be promoted to (signed) int, which may allow
overflow (and undefined behavior) to occur.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[James Hu]

Re: unsigned short addition/subtraction overflow

On 2003-12-21, pete <pfiland@mindsp ring.com> wrote:[color=blue]
> James Hu wrote:[color=green]
>>
>> On 2003-12-21, Andy <bikejog@hotmai l.com> wrote:[color=darkred]
>> > Are 1 through 4 defined behaviors in C?
>> >
>> > unsigned short i;
>> > unsigned long li; /* 32-bit wide */
>> >
>> > 1. i = 65535 + 3;
>> > 2. i = 1 - 3;
>> > 3. li = (unsigned long)0xFFFFFFFF + 3;
>> > 4. li = 1 - 3;[/color]
>>
>> Yes.[/color]
>
> No.
> 65536 is an allowable value for INT_MAX.
> (65535 + 3) would be integer overflow
> and undefined behavior in that case.[/color]

Good catch. I did consider overflow, but I assumed that (65535+3) was
identical to writing (65538) because of computation at translation
time versus computation at run time.

-- James

[Chris Torek]

Re: unsigned short addition/subtraction overflow

>Andy wrote:[color=blue][color=green]
>> Actually what I really meant is for unsigned operations.
>> This is what I want to know. Are the following defined in
>> C and always guaranteed warped around values?
>>
>> unsigned short i;
>> unsigned long li; /* 32-bit wide */[/color][/color]

All C guarantees here is "at least" 32 bits, but here it does
not really matter.
[color=blue][color=green]
>> 1. i = (unsigned short)65535 + (unsigned short)3;[/color][/color]

In article <vCmFb.340$lo3. 163@newsread2.n ews.pas.earthli nk.net>
Kevin Goodsell <usenet1.spamfr ee.fusion@never box.com> writes:[color=blue]
>You could write these easer this way:
>
>i = 65535u + 3u;[/color]

Actually, this is potentially quite different.

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

In this particular case, unsigned short widens to either
unsigned int or signed int. Which one we get depends on the
properties of the implementation. This is a really dumb idea,
made in an attempt to be "less surprising" than the "right"
way ("narrow unsigned widens to unsigned"), that actually
turns out to be *more* surprising. But again we are stuck
with the wrong decision -- so let me define it.

What you must do is look in <limits.h> (perhaps by writing a
small C program, since the header may not exist) and compare
the values of USHRT_MAX and INT_MAX. One of the following two
cases will necessarily hold:

a) USHRT_MAX > INT_MAX.

This occurs on, e.g., the 16-bit PDP-11 and old 16-bit
MS-DOS C compilers. Here USHRT_MAX is 65535 while INT_MAX
is 32767.

b) USHRT_MAX <= INT_MAX.

This occurs on, e.g., today's 16-bit-short 32-bit-int C
compilers. Here USHRT_MAX is 65535 while INT_MAX is
2147483647.

In case (a), an unsigned short expression -- no matter what its
actual value is -- that appears in an arithmetic expression is
widened to unsigned int. Thus (unsigned short)65535 is
identical to (unsigned int)65535 or 65535U.

In case (b), howver, an unsigned short -- no matter what its actual
value is -- is widened to a *signed* int. Thus (unsigned short)65535
is identical to (int)65535 or 65535.

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.

In either case, when storing the final values back into an unsigned
short, it is reduced mod (USHRT_MAX+1), so that i becomes 2. The
place where this becomes a problem is not when we stuff the result
back into an unsigned variable, but rather when we compare it in
what the original 1989 C rationale called a "questionab ly signed"
expression.

Suppose we have the following code fragment:

unsigned short us = 65535;
int i = -1;

if (us > i)
printf("65535 > -1\n");
else
printf("65535 <= -1\n");

According to ANSI C's ridiculous rules (which we must obey anyway),
we decide whether this comparison uses "unsigned int" or "signed
int" based on whether USHRT_MAX exceeds INT_MAX. Once again, we
have the two cases:

case (a), USHRT_MAX > INT_MAX (PDP-11): "us" widens to an
unsigned int, value 65535U; i widens to an unsigned int,
value 65535U. 65535U > 65535U is false and we print
"65535 <= -1". This is, supposedly, "surprising " -- but
it happens!

case (b), USHRT_MAX < INT_MAX (VAX etc): "us" widens to
a signed int, value 65535; i remains signed int, value
-1. 65535 > -1 is true and we print "65535 > -1". This
is supposedly "not surprising" (which is probably true),
but in fact it is only SOMETIMES true.

As far as I am concerned, it is *much* better to be "predictabl y
surprising" than "unpredicta bly surprising based on the relative
values of USHRT_MAX and INT_MAX". The reason is that, while C
programmers do get surprised, they get surprised *once*, the *first*
time they mix signed and unsigned this way. This gives them the
opportunity to learn that the results are surprising; from then
on, they have no excuse to be surprised. Moreover, the logic
is trivial to follow: "unsigned widens to unsigned" means "put
an unsigned into an expression and it takes over."

Instead, we have a language where the code "works as expected" --
until it is moved to a machine where case (a) holds instead of case
(b). Programmers learn that mixing signed and unsigned is harmless
and "never surprises", only to find someday that, no, the language
is considerably more perverse than that. The logic is difficult
as well: "unsigned takes over except when it doesn't, based on the
relative values of the corresponding MAXes."
[color=blue][color=green]
>> 2. i = (unsigned short)1 - (unsigned short)3;
>> 3. li = (unsigned long)0xFFFFFFFF + (unsigned long)3;
>> 4. li = (unsigned long)1 - (unsigned long)3;[/color][/color]
[color=blue]
>It's difficult to produce undefined behavior with unsigned values.[/color]

As long as you stick with unsigned int or unsigned long, anyway,
so that the broken widening rules do not trick you into accidentally
using signed values.
[color=blue]
>(Unless you divide by zero, maybe. I don't actually know what the
>standard says about that, which surprises me.)[/color]

Division by zero produces undefined behavior, even for 1U / 0U and
the like.
[color=blue]
>Overflow doesn't occur
>with unsigned types, but it's possible for unsigned types that are
>narrower than int to be promoted to (signed) int, which may allow
>overflow (and undefined behavior) to occur.[/color]

Yes. I claim that this rule is a terrible one; but I note that we
are stuck with it. The best approach is to avoid it -- make sure
you explicitly widen your narrow unsigned types to wider unsigned
types if the result (overflow or result of "questionab ly signed"
comparison) can matter. This kind of code is undeniably ugly, but
then, working around broken portions of any language (not just C)
is usually ugly.
--
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.

[Kevin Goodsell]

Re: unsigned short addition/subtraction overflow

Chris Torek wrote:
[color=blue]
> In article <vCmFb.340$lo3. 163@newsread2.n ews.pas.earthli nk.net>
> Kevin Goodsell <usenet1.spamfr ee.fusion@never box.com> writes:
>[color=green]
>>You could write these easer this way:
>>
>>i = 65535u + 3u;[/color]
>
>
> Actually, this is potentially quite different.[/color]

Yes, obviously. Not sure what I was thinking there. I think I suffer
from "short blindness" - I either miss the word 'short' or
sub-consciously translate it to 'int'. This wasn't the first time.

Thanks for pointing out the error.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.