Where does the C standard describe overflow of signed integers?

Where does the C standard describe overflow of signed integers?

[Nicholas Nethercote]

Hi,

There was recently a very long thread about the overflow behaviour of 
signed integers in C.  Apparently this is undefined according to the C 
standard.  I searched the standard on this matter, and while I did find 
some paragraphs that described how unsigned integers must wrap around upon 
overflow, I couldn't find anything explicit about signed integers.  Can 
someone point me to the relevant part(s) of the standard?

Also, does anyone know what the required behaviour for Fortran integers is 
on overflow?

(I realise this isn't exactly on-topic for this list, but I thought it 
reasonable to ask since this topic was discussed so enthusiastically 
recently :)

Thanks very much.

Nick

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Nicholas Nethercote
>Sent: 11 July 2005 15:59

> Hi,
> 
> There was recently a very long thread about the overflow behaviour of
> signed integers in C.  Apparently this is undefined according to the C
> standard.  I searched the standard on this matter, and while I did find
> some paragraphs that described how unsigned integers must wrap around upon
> overflow, I couldn't find anything explicit about signed integers.

  Anything not defined is undefined, by definition!

>  Can someone point me to the relevant part(s) of the standard?

  :) I can only point you at the whole thing, where it doesn't define it
anywhere.

  See also 3.4.3/3, and H.2.2.

    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

RE: Where does the C standard describe overflow of signed integers?

[Nicholas Nethercote]

On Mon, 11 Jul 2005, Dave Korn wrote:

>> There was recently a very long thread about the overflow behaviour of
>> signed integers in C.  Apparently this is undefined according to the C
>> standard.  I searched the standard on this matter, and while I did find
>> some paragraphs that described how unsigned integers must wrap around upon
>> overflow, I couldn't find anything explicit about signed integers.

Dave, Nathan and Paul:  thanks for the quick replies.

The difference between signed and unsigned integer overflow is a little 
unclearly expressed, I think.

3.4.3/3 says:

   "EXAMPLE  An example of undefined behavior is the behavior on integer
    overflow"

6.5/5 says:

   "If an _exceptional condition_ 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."

These two paragraphs would seem to indicate that overflow is undefined for 
both signed and unsigned integers.

But then 6.2.5 para 9, sentence 2 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 type."

Which requires that unsigned ints must wrap on overflow.  (Actually, I 
guess it defines "overflow" such that unsigned ints never "overflow", so 
3.4.3/3 and 6.5/5 don't apply!)

But I think the paragraphs together are good enough to communicate that: 
unsigned ints must wrap on overflow, signed ints need not.  Thanks again 
for your help.

N

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Nicholas Nethercote
>Sent: 11 July 2005 17:08

> On Mon, 11 Jul 2005, Dave Korn wrote:
> 
>>> There was recently a very long thread about the overflow behaviour of
>>> signed integers in C.  Apparently this is undefined according to the C
>>> standard.  I searched the standard on this matter, and while I did find
>>> some paragraphs that described how unsigned integers must wrap around
>>> upon overflow, I couldn't find anything explicit about signed integers.

  Mangled attribution there, I didn't say that, you did!  There's no reason
to leave in the "So-and-so wrote" line if you haven't quoted a single word
of what so-and-so actually wrote....

> The difference between signed and unsigned integer overflow is a little
> unclearly expressed, I think.
> 
> 3.4.3/3 says:
> 
>    "EXAMPLE  An example of undefined behavior is the behavior on integer
>     overflow"
> 
> 6.5/5 says:
> 
>    "If an _exceptional condition_ 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."
> 
> These two paragraphs would seem to indicate that overflow is undefined for
> both signed and unsigned integers.

  Not quite; you have to read all the implications at once.  3.4.3/3 says
that the behaviour "on integer overflow" is undefined, but because it
elsewhere says that unsigned ints don't overflow, that para only applies to
signed ints.  Likewise, because unsigned ints are defined to use modulo
arithmetic, no "exception condition" occurs, because the result _is_ defined
and the modulo rule keeps it within the "range of representable values for
its type".

> But then 6.2.5 para 9, sentence 2 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 type."
> 
> Which requires that unsigned ints must wrap on overflow.  (Actually, I
> guess it defines "overflow" such that unsigned ints never "overflow", so
> 3.4.3/3 and 6.5/5 don't apply!)
> 
> But I think the paragraphs together are good enough to communicate that:
> unsigned ints must wrap on overflow, signed ints need not.  Thanks again
> for your help.

  Ah, I see you've already worked out for yourself what I wrote above.  Yes,
the language in these standards is very hard to read, because you can't
consider any individual point by itself; they don't all explicitly itemise
the other points that might interact with or modify them, as you've seen, so
it requires a good familiarity with the standard to know if some other part
of it might make a difference to the interpretation of the bit you're
examining on any given occasion.


    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: Where does the C standard describe overflow of signed integers?

[Nathan Sidwell]

Nicholas Nethercote wrote:
> Hi,
> 
> There was recently a very long thread about the overflow behaviour of 
> signed integers in C.  Apparently this is undefined according to the C 
> standard.  I searched the standard on this matter, and while I did find 
> some paragraphs that described how unsigned integers must wrap around 
> upon overflow, I couldn't find anything explicit about signed integers.  
> Can someone point me to the relevant part(s) of the standard?

c99 6.5 para 5 (overflow is undefined) & 6.3.1.3 (conversions to unsigned type 
obey modulo laws)

c++ 5 para 5 (overflow is undefined, unless otherwise stated) & 3.9.1 para 4 
(unsigned types obey modulo laws)

I cannot find, in c99, a statement that all unsigned arithmetic obeys modulo 
laws -- only that integral conversions to them do.

nathan

-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Nathan Sidwell
>Sent: 11 July 2005 16:15

> c99 6.5 para 5 (overflow is undefined) 

  Have I got an old draft or something, or is that the paragraph that begins
"If an _exceptional_ _condition_ occurs ..." ?

> I cannot find, in c99, a statement that all unsigned arithmetic obeys
> modulo laws -- only that integral conversions to them do.

  Like I say, I'm not sure exactly what draft/version/spec I have here in
front of me, except that it says "ISO/IEC 9899:1999 (E)" at the top of each
page, but I've got a para 9 in 6.2.5 that 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 type."

    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: Overflow in Fortran (was: Where does the C standard describe overflow of signed integers?)

[Paul Brook]

On Monday 11 July 2005 15:58, Nicholas Nethercote wrote:
> Also, does anyone know what the required behaviour for Fortran integers is
> on overflow?

Section 7.1.7 "Evaluation of operation"

"The evaluation of any numeric operation whose result is not defined by the 
arithmetic used by the processor[1] is prohibited"

Section 13.7.1 "Models for integer and real data"

The model set for integer i is defined by:
[sign + magnitude]


ie. overflow is not defined, and we can do whatever the hell we want.

Paul

[1] In this context "processor" means language processor, ie. a combination 
the compiler, OS and target hardware.

Re: Where does the C standard describe overflow of signed integers?

[Michael Meissner]

On Mon, Jul 11, 2005 at 09:58:36AM -0500, Nicholas Nethercote wrote:
> Hi,
> 
> There was recently a very long thread about the overflow behaviour of 
> signed integers in C.  Apparently this is undefined according to the C 
> standard.  I searched the standard on this matter, and while I did find 
> some paragraphs that described how unsigned integers must wrap around upon 
> overflow, I couldn't find anything explicit about signed integers.  Can 
> someone point me to the relevant part(s) of the standard?

I don't have time to dig out all of the relevant sections, but I was on the
ANSI X3J11 committee that defined the C standard from its beginning through the
release of the C90 international standard (and some of the C99 work, though I
left the committee before a lot of the changes were made).  It did come up for
discussion, but the committee did decide to leave it undefined, since there
were C compilers for some different machines that did not just silently
truncate.

From memory, there was one vendor with a machine that had signed magnitude
integers.

There was a vendor with a machine that had one's complement integers.

I suspect at least one vendor used instructions that caused an overflow trap
for signed arithmetic.

-- 
Michael Meissner
email: gnu@the-meissners.org
http://www.the-meissners.org