Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #8055 > unrolled thread

Re: Arithmetic overflow checking

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-10 01:47 -0700
    Re: Arithmetic overflow checking China Blue Dolls <chine.bleu@yahoo.com> - 2011-07-10 02:47 -0700
      Re: Arithmetic overflow checking pete <pfiland@mindspring.com> - 2011-07-10 06:04 -0400
        Re: Arithmetic overflow checking China Blue Dolls <chine.bleu@yahoo.com> - 2011-07-10 03:29 -0700
          Re: Arithmetic overflow checking Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-07-10 20:52 +0300
          Re: Arithmetic overflow checking pete <pfiland@mindspring.com> - 2011-07-10 23:29 -0400
      Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-10 04:44 -0700
        Re: Arithmetic overflow checking "BartC" <bc@freeuk.com> - 2011-07-12 11:33 +0100
          Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 04:17 -0700
            Re: Arithmetic overflow checking "BartC" <bc@freeuk.com> - 2011-07-12 12:33 +0100
              Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 05:24 -0700
                Re: Arithmetic overflow checking Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-07-12 21:45 -0400
            Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-12 05:25 -0700
              Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 10:21 -0700
                Re: Arithmetic overflow checking Thomas Boell <tboell@domain.invalid> - 2011-07-12 22:39 +0200
                  Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 14:15 -0700
                    Re: Arithmetic overflow checking Keith Thompson <kst-u@mib.org> - 2011-07-12 14:18 -0700
                      Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 23:54 -0700
              Re: Arithmetic overflow checking "BartC" <bc@freeuk.com> - 2011-07-12 19:14 +0100
                Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-13 00:20 -0700
          Re: Arithmetic overflow checking markspace <-@.> - 2011-07-12 09:26 -0700
            Re: Arithmetic overflow checking Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-07-12 10:52 -0600
              Re: Arithmetic overflow checking Keith Thompson <kst-u@mib.org> - 2011-07-12 10:48 -0700
                Re: Arithmetic overflow checking Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-07-12 12:36 -0600
                  Re: Arithmetic overflow checking Keith Thompson <kst-u@mib.org> - 2011-07-12 12:16 -0700
                    Re: Arithmetic overflow checking Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-07-12 14:09 -0600
                      Re: Arithmetic overflow checking Keith Thompson <kst-u@mib.org> - 2011-07-12 14:16 -0700
                Re: Arithmetic overflow checking, not so hard after all "Greg A. Woods" <woods@robohack.org> - 2011-07-12 21:52 -0700
                  Re: Arithmetic overflow checking, not so hard after all Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-07-13 12:50 +0100
                    Re: Arithmetic overflow checking, not so hard after all "Greg A. Woods" <woods@robohack.org> - 2011-07-13 11:10 -0700
                      Re: Arithmetic overflow checking, not so hard after all Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-07-14 01:34 +0100
                        Re: Arithmetic overflow checking, not so hard after all "Greg A. Woods" <woods@robohack.org> - 2011-07-19 17:10 -0700
                          Re: Arithmetic overflow checking, not so hard after all Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-07-19 20:47 -0600
                            Re: Arithmetic overflow checking, not so hard after all Keith Thompson <kst-u@mib.org> - 2011-07-19 20:23 -0700
                              Re: Arithmetic overflow checking, not so hard after all "Greg A. Woods" <woods@robohack.org> - 2011-09-06 17:47 -0700
                            Re: Arithmetic overflow checking, not so hard after all Todd Carnes <toddcarnes@gmail.com> - 2011-07-20 03:48 +0000
                  Re: Arithmetic overflow checking, not so hard after all Keith Thompson <kst-u@mib.org> - 2011-07-13 09:27 -0700
                Re: Arithmetic overflow checking "MikeP" <mp011011@some.org> - 2011-07-14 23:55 -0500
            Re: Arithmetic overflow checking Martin Gregorie <martin@address-in-sig.invalid> - 2011-07-12 16:54 +0000
              Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-12 11:35 -0700
            Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 10:13 -0700
            Re: Arithmetic overflow checking Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-07-12 21:53 -0400
          Re: Arithmetic overflow checking "MikeP" <mp011011@some.org> - 2011-07-14 23:41 -0500
            Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-15 10:56 -0700
              Re: Arithmetic overflow checking "MikeP" <mp011011@some.org> - 2011-07-15 21:27 -0500
        Re: Arithmetic overflow checking bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-07-20 09:22 +0100
          Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-20 10:51 -0700
            Re: Arithmetic overflow checking gordonb.3urm7@burditt.org (Gordon Burditt) - 2011-07-20 15:39 -0500
            Re: Arithmetic overflow checking "BartC" <bc@freeuk.com> - 2011-07-21 12:12 +0100
      Re: Arithmetic overflow checking Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-07-10 09:28 -0400
        Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-10 06:52 -0700
          Re: Arithmetic overflow checking Keith Thompson <kst-u@mib.org> - 2011-07-10 14:47 -0700
          Re: Arithmetic overflow checking gordonb.u8vng@burditt.org (Gordon Burditt) - 2011-07-11 18:45 -0500
        Re: Arithmetic overflow checking "MikeP" <mp011011@some.org> - 2011-07-14 23:07 -0500
      Re: Arithmetic overflow checking Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-07-10 12:25 -0400
    Re: Arithmetic overflow checking Robert Wessel <robertwessel2@yahoo.com> - 2011-07-10 10:47 -0500
    Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-11 07:58 -0700
      Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-11 10:48 -0700
        Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-11 14:40 -0700
      Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-11 14:54 -0700
        Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-11 15:55 -0700
        Re: Arithmetic overflow checking Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-07-11 21:51 -0400
          Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-11 21:31 -0700
            Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-11 23:16 -0700
            Re: Arithmetic overflow checking James Kuyper <jameskuyper@verizon.net> - 2011-07-12 06:28 -0400
            Re: Arithmetic overflow checking David Thompson <dave.thompson2@verizon.net> - 2011-07-24 22:13 -0400
              Re: Arithmetic overflow checking Lew Pitcher <lpitcher@teksavvy.com> - 2011-07-25 10:24 -0400
    Re: Arithmetic overflow checking "io_x" <a@b.c.invalid> - 2011-07-12 09:05 +0200
      Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 02:22 -0700
        Re: Arithmetic overflow checking "io_x" <a@b.c.invalid> - 2011-07-12 11:34 +0200
          Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-12 03:04 -0700
            Re: Arithmetic overflow checking "Greg A. Woods" <woods@robohack.org> - 2011-07-12 19:55 -0700
              Re: Arithmetic overflow checking "Greg A. Woods" <woods@robohack.org> - 2011-07-12 21:54 -0700
              Re: Arithmetic overflow checking "MikeP" <mp011011@some.org> - 2011-07-14 23:28 -0500
                Re: Arithmetic overflow checking "Greg A. Woods" <woods@robohack.org> - 2011-07-19 17:16 -0700
          Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-12 03:33 -0700
          Re: Arithmetic overflow checking David Lamb <dalamb@cs.queensu.ca> - 2011-07-12 08:29 -0400
        Re: Arithmetic overflow checking "io_x" <a@b.c.invalid> - 2011-07-12 13:18 +0200
        Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-12 11:39 -0700
          Re: Arithmetic overflow checking Patricia Shanahan <pats@acm.org> - 2011-07-12 12:38 -0700
            Re: Arithmetic overflow checking markspace <-@.> - 2011-07-12 13:20 -0700
              Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-12 13:23 -0700
                Re: Arithmetic overflow checking Martin Gregorie <martin@address-in-sig.invalid> - 2011-07-12 21:08 +0000
                  Re: Arithmetic overflow checking lewbloch <lewbloch@gmail.com> - 2011-07-12 14:48 -0700
                    Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-12 15:24 -0700
                      Re: Arithmetic overflow checking lewbloch <lewbloch@gmail.com> - 2011-07-12 16:09 -0700
                        Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-13 10:38 -0700
                          Re: Arithmetic overflow checking Patricia Shanahan <pats@acm.org> - 2011-07-13 11:00 -0700
                          Re: Arithmetic overflow checking lewbloch <lewbloch@gmail.com> - 2011-07-13 12:16 -0700
                            Re: Arithmetic overflow checking Gene Wirchenko <genew@ocis.net> - 2011-07-13 13:10 -0700
                            Re: Arithmetic overflow checking markspace <-@.> - 2011-07-13 13:21 -0700
                              Re: Arithmetic overflow checking Keith Thompson <kst-u@mib.org> - 2011-07-13 13:41 -0700
                                Re: Arithmetic overflow checking Robert Wessel <robertwessel2@yahoo.com> - 2011-07-14 21:10 -0500
                                  Re: Arithmetic overflow checking "io_x" <a@b.c.invalid> - 2011-07-15 11:57 +0200
                                    Re: Arithmetic overflow checking Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-07-15 04:36 -0700
                        Re: Arithmetic overflow checking Niklas Holsti <niklas.holsti@tidorum.invalid> - 2011-08-13 21:54 +0300
        Re: Arithmetic overflow checking "Greg A. Woods" <woods@robohack.org> - 2011-07-12 20:03 -0700
          Re: Arithmetic overflow checking tm <thomas.mertes@gmx.at> - 2011-07-13 00:52 -0700
            Re: Arithmetic overflow checking Patricia Shanahan <pats@acm.org> - 2011-07-13 07:45 -0700
              Re: Arithmetic overflow checking "Greg A. Woods" <woods@robohack.org> - 2011-07-13 11:28 -0700
            Re: Arithmetic overflow checking "Greg A. Woods" <woods@robohack.org> - 2011-07-13 11:15 -0700
    Re: Arithmetic overflow checking Wolfgang Draxinger <wdraxinger@darkstargames.de> - 2011-09-08 21:02 +0200
      Re: Arithmetic overflow checking Wolfgang Draxinger <wdraxinger@darkstargames.de> - 2011-09-08 21:12 +0200
        Re: Arithmetic overflow checking Willem <willem@toad.stack.nl> - 2011-09-08 19:15 +0000
          Re: Arithmetic overflow checking Wolfgang Draxinger <wdraxinger@darkstargames.de> - 2011-09-08 22:24 +0200

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

#8176

On 7/12/2011 6:16 AM, Stefan Ram wrote:
> "BartC"<bc@freeuk.com>  writes:
>> a+b overflows, but then what?
>
>    This can only be answered given the requirements
>    specification of a specific project.


What I think he's saying is there's no way physically detect the 
overflow in a language like C which has no exceptions.  You'd have to at 
least introduce some sort of global flag.

   int c = a + b;
   if( GLOBAL_OVERFLOW_FLAG ) {
     printf( "bugger..." );
   }

[toc] | [prev] | [next] | [standalone]

#8177

markspace <-@.> writes:

> On 7/12/2011 6:16 AM, Stefan Ram wrote:
>> "BartC"<bc@freeuk.com>  writes:
>>> a+b overflows, but then what?
>>
>>    This can only be answered given the requirements
>>    specification of a specific project.
>
>
> What I think he's saying is there's no way physically detect the
> overflow in a language like C which has no exceptions.  You'd have to
> at least introduce some sort of global flag.
>
>   int c = a + b;
>   if( GLOBAL_OVERFLOW_FLAG ) {
>     printf( "bugger..." );
>   }

Well, yes there is.  For example on an addition, if both operands have
the same sign and the result is the other sign, you had an overflow.
Analogous conditions exist (which I don't remember off the top of my
head and am too lazy to look up) exist for subtraction and
multiplication.  Integer division can't overflow.

My reading of the question was "OK, you've detected an overflow.  Now
what do you do about it?" and the (correct) answer was, in essence,
"well, what do you *want* to do about it?"

[toc] | [prev] | [next] | [standalone]

#8181

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
> markspace <-@.> writes:
>> On 7/12/2011 6:16 AM, Stefan Ram wrote:
>>> "BartC"<bc@freeuk.com>  writes:
>>>> a+b overflows, but then what?
>>>
>>>    This can only be answered given the requirements
>>>    specification of a specific project.
>>
>> What I think he's saying is there's no way physically detect the
>> overflow in a language like C which has no exceptions.  You'd have to
>> at least introduce some sort of global flag.
>>
>>   int c = a + b;
>>   if( GLOBAL_OVERFLOW_FLAG ) {
>>     printf( "bugger..." );
>>   }
>
> Well, yes there is.  For example on an addition, if both operands have
> the same sign and the result is the other sign, you had an overflow.
> Analogous conditions exist (which I don't remember off the top of my
> head and am too lazy to look up) exist for subtraction and
> multiplication.  Integer division can't overflow.

On many systems, yes, you can detect signed overflow after the fact by
examining the values of the operands and the result.  But in C, the
behavior is undefined -- and even on systems that use 2's-complement, an
optimizing compiler can take advantage of that fact and generate code
based on the assumption that overflow never occurs.  For example, this:

    int x = INT_MAX;
    if (x + 1 < x) {
        fprintf(stderr, "Overflow!\n");
    }

can be optimized away  (For example, gcc does this at -O2 and above.)

And yes, integer division can overflow; consider INT_MIN / -1.

> My reading of the question was "OK, you've detected an overflow.  Now
> what do you do about it?" and the (correct) answer was, in essence,
> "well, what do you *want* to do about it?"

But detecting the overflow in the first place can be *very* tricky.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#8184

Keith Thompson <kst-u@mib.org> writes:

> Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
>> markspace <-@.> writes:
>>> On 7/12/2011 6:16 AM, Stefan Ram wrote:
>>>> "BartC"<bc@freeuk.com>  writes:
>>>>> a+b overflows, but then what?
>>>>
>>>>    This can only be answered given the requirements
>>>>    specification of a specific project.
>>>
>>> What I think he's saying is there's no way physically detect the
>>> overflow in a language like C which has no exceptions.  You'd have to
>>> at least introduce some sort of global flag.
>>>
>>>   int c = a + b;
>>>   if( GLOBAL_OVERFLOW_FLAG ) {
>>>     printf( "bugger..." );
>>>   }
>>
>> Well, yes there is.  For example on an addition, if both operands have
>> the same sign and the result is the other sign, you had an overflow.
>> Analogous conditions exist (which I don't remember off the top of my
>> head and am too lazy to look up) exist for subtraction and
>> multiplication.  Integer division can't overflow.
>
> On many systems, yes, you can detect signed overflow after the fact by
> examining the values of the operands and the result.  But in C, the
> behavior is undefined -- and even on systems that use 2's-complement, an
> optimizing compiler can take advantage of that fact and generate code
> based on the assumption that overflow never occurs.  For example, this:
>
>     int x = INT_MAX;
>     if (x + 1 < x) {
>         fprintf(stderr, "Overflow!\n");
>     }
>
> can be optimized away  (For example, gcc does this at -O2 and above.)

True, but I was considering the likelier case of something more like

    y = x + 1;

    if ((x > 0) && (y < 0))
	printf("overflow\n");

Which strikes me as much less likely to be optimized away.

> And yes, integer division can overflow; consider INT_MIN / -1.

Drat.  I stand corrected.

>> My reading of the question was "OK, you've detected an overflow.  Now
>> what do you do about it?" and the (correct) answer was, in essence,
>> "well, what do you *want* to do about it?"
>
> But detecting the overflow in the first place can be *very* tricky.

[toc] | [prev] | [next] | [standalone]

#8186

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
> Keith Thompson <kst-u@mib.org> writes:
[...]
>> On many systems, yes, you can detect signed overflow after the fact by
>> examining the values of the operands and the result.  But in C, the
>> behavior is undefined -- and even on systems that use 2's-complement, an
>> optimizing compiler can take advantage of that fact and generate code
>> based on the assumption that overflow never occurs.  For example, this:
>>
>>     int x = INT_MAX;
>>     if (x + 1 < x) {
>>         fprintf(stderr, "Overflow!\n");
>>     }
>>
>> can be optimized away  (For example, gcc does this at -O2 and above.)
>
> True, but I was considering the likelier case of something more like
>
>     y = x + 1;
>
>     if ((x > 0) && (y < 0))
> 	printf("overflow\n");
>
> Which strikes me as much less likely to be optimized away.

Perhaps -- but optimizing compilers can be very clever, often
cleverer than you expect them to be.  (Some years ago, a co-worker
was surprised to discover that a substantial chunk of code was
eliminated entirely, and assumed it was a compiler bug.  On further
investigation, she found that it was a perfectly legitimate
sequence of optimizations; the code didn't actually do anything,
but she didn't expect the optimizer to be clever enough to notice.
And she was working on the optimizer.)

Depending on the compiler *not noticing things* is not a good way to
detect overflows.

Here's a program based on your suggestion:

#include <stdio.h>
#include <time.h>
#include <limits.h>
int main(void)
{
    int x = time(NULL) < 0 ? 42 : INT_MAX;
    int y;

    y = x + 1;

    if ((x > 0) && (y < 0)) {
        printf("overflow\n");
    }
    else {
        printf("no overflow\n");
    }
    return 0;
}

When compiled with "gcc -O1", it prints "overflow".  With "gcc -O2", it
prints "no overflow".

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#8188

You are correct, and I am surprised.  What surprises me even more is
that I'd tried almost the same test, using

int x = INT_MAX;

and saw the correct result.  After your followup, I looked at the
generated assembly code for both versions; it turned out that mine had
optimized away the 'if' and simply printed 'overflow'; yours had optimized
away the 'if' and simply printed 'no overflow'!

[toc] | [prev] | [next] | [standalone]

#8195

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
> You are correct, and I am surprised.  What surprises me even more is
> that I'd tried almost the same test, using
>
> int x = INT_MAX;
>
> and saw the correct result.  After your followup, I looked at the
> generated assembly code for both versions; it turned out that mine had
> optimized away the 'if' and simply printed 'overflow'; yours had optimized
> away the 'if' and simply printed 'no overflow'!

Undefined behavior can be like that.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#8224 — Re: Arithmetic overflow checking, not so hard after all

Keith Thompson <kst-u@mib.org> writes:
> 
> But detecting the overflow in the first place can be *very* tricky.

Assuming your code is too complex or performance sensitive to use a
compiler that can do the checking for you (e.g. maybe with Clang's
"-ftrapv" -- see my comments below), it's reasonlyb easy to reliably do
the checks yourself, assuming you understand your target platform.

Attached is some test code I wrote quite a long time ago for checking
compilers and such.  It uses techniques I found from various sources to
demonstrate the possibilities of reliable integer overflow and
underflow detection for addition and subtraction, respectively.

I think I've covered testing each technique for most of the corner &
edge cases you have to watch out for, but I can't be certain.

I just re-ran it with some newer versions of GCC though and I see that
'-ftrapv' doesn't seem to work at all any more.  They broke it bad, and
haven't got around to fixing it yet.  See the comments in the code below.

Half-hearted apologies to anyone stuck with an 80-column terminal.  Join
the modern age and get a wider screen!  :-)


						Greg A. Woods
						RoboHack

<woods@robohack.ca>     living on the edge      http://www.robohack.ca/

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 * NOTES about C implementations vs. integer overflow detection:
 *
 * GCC has '-ftrapv' which (in some versions) replaces integer arithmetic
 * operators with calls to libgcc wrapper functions which (assuming
 * two's-complement signed integer arithmetic implementstions) will do overflow
 * checks (usually post-condition wrap-around checks) and call abort() if
 * there's an overflow detected in the operation.
 *
 * Unfortunately using GCC-4.1.2's '-ftrapv' in combination with any
 * optimization (i.e. '-O1' or greater) then the compiler will apparently
 * generate code which will purposefuly optimize away the libgcc internal calls
 * for (at least) addition operations.  The tests below will still detect the
 * overflows at runtime, and we know these tests are never optimized away
 * because we check that they work correctly for known non-overflowing values.
 * This is a GCC bug.
 *
 * Even more recent versions of GCC suffer worse:
 *
 * '-ftrapv' has no affect on Mac OS X (10.6.8 w/ gcc 4.2.1) (not in manpage)
 *
 * '-ftrapv' has no affect on FreeBSD 8.x w/ gcc 4.2.1 either (is documented)
 *
 * And as of last check, it's still a noted, open, bug:
 *
 *	http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35412 
 *	
 * However some discussions on some GCC mailing lists suggest this is too
 * broken to fix as-is.  Back in 2008 it was suggested it be deprecated for 4.4
 * and re-implemented properly using GIMPLE, whatever that is.
 *
 * Some other work done on this issue:
 *
 *	http://repository.cmu.edu/cgi/viewcontent.cgi?article=1017&context=ece
 *
 * Clang does support '-ftrapv', and it works even with -O3.
 *
 * BTW, if you do use '-ftrapv' you could add a signal handler for SIGABRT, or
 * re-define the abort() function, and then get signalled/called for every test
 * where overflow/underflow is detected.
 *
 * Someday C may have "as-if infinitely ranging integers".....
 */

/*
 * WARNING:  when testing this kind of stuff one must be careful not to give
 * away the secret to the optimizer, else it's certain to just elide your code.
 * Here we either use a system call to make the compiler uncertain about what
 * value will be used, or (with the following #define) we enable input options
 * for the user to supply the values, giving our suggestion as a simplistic
 * automated Turing test to out-smart the compiler.
 */
#if 1
#define USE_TIME_TO_INIT	/* defined.... */
#endif

void	unsigned_int_add_ovf(unsigned int, unsigned int);
void	unsigned_int_sub_undf(unsigned int, unsigned int);
void	signed_int_add_ovf_1(signed int, signed int);
void	signed_int_add_ovf_2(signed int, signed int);
void	signed_int_add_ovf_3(signed int, signed int);
void	signed_int_add_ovf_mot(signed int, signed int);
void	signed_int_add_ovf_cert_2s(signed int, signed int);
void	signed_int_add_ovf_cert_any(signed int, signed int);
void	signed_int_sub_undf_3(signed int, signed int);
void	signed_int_sub_undf_mot(signed int, signed int);


int main(void);

int
main()
{
	unsigned int ufoo;
	unsigned int ubar;

	signed int foo;
	signed int bar;

	int high_int_bit = (1 << ((int) (sizeof(int) * CHAR_BIT) - 1));

	/*
	 * note: this entire "if" trivially gets optimized away with -O1
	 */
	if (high_int_bit != INT_MIN) {
		printf("*** high bit expression says INT_MIN is busted! (INT_MIN=0x%x)\n", INT_MIN);
	}

	printf("\nTesting unsigned integer OK....\n\n");

#ifdef USE_TIME_TO_INIT
	ufoo = 	(time((time_t) NULL) < 0) ? 42 : 1;
	ubar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter a 1: ");
	fscanf(stdin, "%u", &ufoo);
	printf("got %u\n\n", ufoo);

	printf("Enter a 1: ");
	fscanf(stdin, "%u", &ubar);
	printf("got %u\n\n", ubar);
#endif

	unsigned_int_add_ovf(ufoo, ubar); /* UINT_MAX + 1 */

#ifdef USE_TIME_TO_INIT
	ufoo = 	(time((time_t) NULL) < 0) ? 42 : (UINT_MAX - 1);
#else
	printf("Enter %d: ", (UINT_MAX - 1));
	fscanf(stdin, "%u", &ufoo);
	printf("got %u\n\n", ufoo);
#endif
	unsigned_int_add_ovf(ufoo, ubar); /* (UINT_MAX-1) + 1 */


	printf("\nTesting unsigned integer overflow detection....\n\n");


#ifdef USE_TIME_TO_INIT
	ufoo = 	(time((time_t) NULL) < 0) ? 42 : UINT_MAX;
	ubar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter %u: ", UINT_MAX);
	fscanf(stdin, "%u", &ufoo);
	printf("got %u\n\n", ufoo);

	printf("Enter a 1: ");
	fscanf(stdin, "%u", &ubar);
	printf("got %u\n\n", ubar);
#endif

	unsigned_int_add_ovf(ufoo, ubar); /* UINT_MAX + 1 */

#ifdef USE_TIME_TO_INIT
	ubar = 	(time((time_t) NULL) < 0) ? 42 : UINT_MAX;
#else
	printf("Enter %u: ", UINT_MAX);
	fscanf(stdin, "%u", &ubar);
	printf("got %u\n\n", ubar);
#endif

	unsigned_int_add_ovf(ufoo, ubar); /* UINT_MAX + UINT_MAX */

#ifdef USE_TIME_TO_INIT
	ufoo = 	(time((time_t) NULL) < 0) ? 42 : 0;
	ubar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter a 0: ");
	fscanf(stdin, "%u", &ufoo);
	printf("got %u\n\n", ufoo);

	printf("Enter a 1: ");
	fscanf(stdin, "%u", &ubar);
	printf("got %u\n\n", ubar);
#endif

	unsigned_int_sub_undf(ufoo, ubar); /* 0 - 1 */


#ifdef USE_TIME_TO_INIT
	ubar = 	(time((time_t) NULL) < 0) ? 42 : UINT_MAX;
#else
	printf("Enter %u: ", UINT_MAX);
	fscanf(stdin, "%u", &ubar);
	printf("got %u\n\n", ubar);
#endif

	unsigned_int_sub_undf(ufoo, ubar); /*  0 - UINT_MAX */


	printf("\nTesting signed integer OK....\n\n");

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : 1;
	bar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter a 1: ");
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);

	printf("Enter a 1: ");
	fscanf(stdin, "%d", &bar);
	printf("got %d\n\n", bar);
#endif

	signed_int_add_ovf_1(foo, bar); /* INT_MAX + 1 */
	signed_int_add_ovf_2(foo, bar);
	signed_int_add_ovf_3(foo, bar);
	signed_int_add_ovf_mot(foo, bar);
	signed_int_add_ovf_cert_2s(foo, bar);
	signed_int_add_ovf_cert_any(foo, bar);

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : (INT_MAX - 1);
#else
	printf("Enter %d: ", (INT_MAX - 1));
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);
#endif

	signed_int_add_ovf_1(foo, bar); /* (INT_MAX-1) + 1 */
	signed_int_add_ovf_2(foo, bar);
	signed_int_add_ovf_3(foo, bar);
	signed_int_add_ovf_mot(foo, bar);
	signed_int_add_ovf_cert_2s(foo, bar);
	signed_int_add_ovf_cert_any(foo, bar);


	printf("\nTesting signed integer addition overflow detection....\n\n");

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : INT_MAX;
	bar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter %d: ", INT_MAX);
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);

	printf("Enter a 1: ");
	fscanf(stdin, "%d", &bar);
	printf("got %d\n\n", bar);
#endif

	signed_int_add_ovf_1(foo, bar);
	signed_int_add_ovf_2(foo, bar);
	signed_int_add_ovf_3(foo, bar);
	signed_int_add_ovf_mot(foo, bar);
	signed_int_add_ovf_cert_2s(foo, bar);
	signed_int_add_ovf_cert_any(foo, bar);

#ifdef USE_TIME_TO_INIT
	bar = 	(time((time_t) NULL) < 0) ? 42 : INT_MAX;
#else
	printf("Enter %d: ", INT_MAX);
	fscanf(stdin, "%d", &bar);
	printf("got %d\n\n", bar);
#endif

	signed_int_add_ovf_1(foo, bar);
	signed_int_add_ovf_2(foo, bar);
	signed_int_add_ovf_3(foo, bar);
	signed_int_add_ovf_mot(foo, bar);
	signed_int_add_ovf_cert_2s(foo, bar);
	signed_int_add_ovf_cert_any(foo, bar);

	printf("\nTesting signed integer subtraction OK....\n\n");

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : 1;
	bar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter a 1: ");
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);

	printf("Enter a 1: ");
	fscanf(stdin, "%d", &bar);
	printf("got %d\n\n", bar);
#endif
	signed_int_sub_undf_3(foo, bar);
	signed_int_sub_undf_mot(foo, bar);

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : 0;
#else
	printf("Enter a 0: ");
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);
#endif
	signed_int_sub_undf_3(foo, bar);
	signed_int_sub_undf_mot(foo, bar);

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : (INT_MIN + 1);
#else
	printf("Enter %d: ", (INT_MIN + 1));
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);
#endif
	signed_int_sub_undf_3(foo, bar);
	signed_int_sub_undf_mot(foo, bar);

	printf("\nTesting signed integer subtraction underflow detection....\n\n");

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : INT_MIN;
	bar = 	(time((time_t) NULL) < 0) ? 42 : 1;
#else
	printf("Enter %d: ", INT_MIN);
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);

	printf("Enter a 1: ");
	fscanf(stdin, "%d", &bar);
	printf("got %d\n\n", bar);
#endif
	signed_int_sub_undf_3(foo, bar);
	signed_int_sub_undf_mot(foo, bar);

#ifdef USE_TIME_TO_INIT
	foo = 	(time((time_t) NULL) < 0) ? 42 : INT_MIN;
	bar = 	(time((time_t) NULL) < 0) ? 42 : INT_MAX;
#else
	printf("Enter %d: ", INT_MIN);
	fscanf(stdin, "%d", &foo);
	printf("got %d\n\n", foo);

	printf("Enter %d: ", INT_MAX);
	fscanf(stdin, "%d", &bar);
	printf("got %d\n\n", bar);
#endif

	signed_int_sub_undf_3(foo, bar);
	signed_int_sub_undf_mot(foo, bar);

	exit(0);
}

void
unsigned_int_add_ovf(ufoo, ubar)
	unsigned int ufoo;		/* = UINT_MAX */
	unsigned int ubar;		/* = 1 */
{
	unsigned int usum;

	/*
	 * the simplest (and most portable) case is for addition of unsigned
	 * integers -- just check that the result is not less than either of
	 * the operands:
	 *
	 * (you should be using unsigned ints for array subscripts anyway!) 
	 */
	usum = ufoo + ubar;
	if (usum < ufoo || usum < ubar) {
		printf("*** unsigned integer addition overflow: %u + %u = %u!\n", ufoo, ubar, usum);
	} else {
		printf("unsigned integer addition OK: %u + %u = %u\n", ufoo, ubar, usum);
	}
}

void
unsigned_int_sub_undf(ufoo, ubar)
	unsigned int ufoo;		/* = 0 */
	unsigned int ubar;		/* = UINT_MAX || 1 */
{
	unsigned int udiff;

	/*
	 * similarly for subtraction -- just check that the result is not
	 * greater than either of the operands:
	 */
	udiff = ufoo - ubar;
	if (udiff > ufoo || udiff > ubar) {
		printf("*** unsigned integer subtraction underflow: %u - %u = %u!\n", ufoo, ubar, udiff);
	} else {
		printf("unsigned integer subtraction OK: %u - %u = %u\n", ufoo, ubar, udiff);
	}
}

void
signed_int_add_ovf_1(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int sum;

	/*
	 * For signed integers on two's-compliment systems:
	 * 
	 * When using operators such as '+' and '-', in which both operands
	 * have like signs, a change of sign in the result indicates an
	 * overflow condition.
	 *
	 * Note that if the signs of the operands are different then of course
	 * an overflow or underflow is impossible.
	 */
	sum = foo + bar;
	if ((foo >= 0 && bar <= 0) ||
	    (foo <= 0 && bar >= 0)) {
		printf("signed 2's-compliment integer addition 1 OK: %d + %d = %d\n", foo, bar, sum);
	} else if ((foo > 0 && sum < 0) ||
		   (foo < 0 && sum > 0)) {
		printf("*** signed 2's-compliment integer addition overflow 1: %d + %d = %d!\n", foo, bar, sum);
	} else {
		printf("signed 2's-compliment integer addition 1 OK: %d + %d = %d\n", foo, bar, sum);
	}
}

void
signed_int_add_ovf_2(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int sum;

	/*
	 * perhaps even simpler than the sign-change check though for
	 * 2's-complement systems is this simple magnitude check of one operand
	 * against the result based on whether the other operand is positive or
	 * not (from GCC's "-ftrapv" runtime):
	 *
	 * NOTE:  This is probably the least expensive post-condition check!
	 */
	sum = foo + bar;
	if ((foo >= 0) ? (sum < bar) : (sum > bar)) {
		printf("*** signed 2's-complement integer addition overflow 2: %d + %d = %d!\n", foo, bar, sum);
	} else {
		printf("signed 2's-complement integer addition 2 OK: %d + %d = %d\n", foo, bar, sum);
	}
}

void
signed_int_add_ovf_3(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int sum;

	/*
	 * from Autoconf's manual, a tranformed variant of the above expression
	 */
	sum = foo + bar;
	if ((sum < bar) != (foo < 0)) {
		printf("*** signed 2's-complement integer addition overflow 3: %d + %d = %d!\n", foo, bar, sum);
	} else {
		printf("signed 2's-complement integer addition 3 OK: %d + %d = %d\n", foo, bar, sum);
	}
}

void
signed_int_add_ovf_mot(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int sum;

	/*
	 * without regard to the sign of the operands we can also use the
	 * following on two's-complement systems (Apparently from Motorola's
	 * documented scheme for setting the overflow bit in MC68k family).
	 */
	sum = foo + bar;
	if (((foo & bar & ~sum) | (~foo & ~bar & sum)) < 0) {
		printf("*** safe & simple signed 2's-complement integer addition overflow: %d + %d = %d!\n", foo, bar, sum);
	} else {
		printf("safe & simple signed signed 2's-complement integer addition OK: %d + %d = %d\n", foo, bar, sum);
	}
}

void
signed_int_add_ovf_cert_2s(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int sum;

	/*
	 * The CERT secure coding page shows an even more complex version (I've
	 * replaced a complex static expression with INT_MIN) of this still
	 * very complex and much more expensive (especially on RISC CPUs)
	 * solution for testing for potential integer overflow when adding two
	 * integer values when the host uses a two's-complement representation
	 * for integers:
	 */
	if (((foo^bar) | (((foo^(~(foo^bar) & INT_MIN)) + bar)^bar)) >= 0) {
		sum = foo + bar;
		printf("*** expensive pre-condition signed 2's-complement integer addition overflow: %d + %d = %d!\n", foo, bar, sum);
	} else {
		sum = foo + bar;
		printf("expensive pre-condition signed 2's-complement integer addition OK: %d + %d = %d\n", foo, bar, sum);
	}
}

void
signed_int_add_ovf_cert_any(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int sum;

	/*
	 * The CERT secure coding page goes on to show another equally (or even
	 * more) expensive solution for testing for potential integer overflow
	 * when adding two integer values regardless of what binary
	 * representation the host uses for integers:
	 */
	if ((foo > 0 && bar > 0 && foo > (INT_MAX - bar)) ||
	    (foo < 0 && bar < 0 && foo < (INT_MIN - bar))) {
		sum = foo + bar;
		printf("*** expensive pre-conditioned signed integer addition overflow: %d + %d = %d!\n", foo, bar, sum);
	} else {
		sum = foo + bar;
		printf("expensive pre-condition signed integer addition OK: %d + %d = %d\n", foo, bar, sum);
	}
}

void
signed_int_sub_undf_3(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int diff;

	/*
	 * again from libgcc:
	 *
	 * NOTE:  This is probably the least expensive post-condition check!
	 */
	diff = foo - bar;
	if ((bar >= 0) ? (diff > foo) : (diff < foo)) {
		printf("*** signed 2's-complement integer subtraction underflow 3: %d - %d = %d!\n", foo, bar, diff);
	} else {
		printf("signed 2's-complement integer subtraction OK 3: %d - %d = %d\n", foo, bar, diff);
	}
}

void
signed_int_sub_undf_mot(foo, bar)
	signed int foo;
	signed int bar;
{
	signed int diff;

	/*
	 * again from Motorola:
	 */
	diff = foo - bar;
	if (((foo & ~bar & ~diff) | (~foo & bar & diff)) < 0) {
		printf("*** safe & simple signed 2's-complement integer subtraction overflow: %d - %d = %d!\n", foo, bar, diff);
	} else {
		printf("safe & simple signed signed 2's-complement integer subtraction OK: %d - %d = %d\n", foo, bar, diff);
	}
}

[toc] | [prev] | [next] | [standalone]

#8231 — Re: Arithmetic overflow checking, not so hard after all

"Greg A. Woods" <woods@robohack.org> writes:

> Keith Thompson <kst-u@mib.org> writes:
>> 
>> But detecting the overflow in the first place can be *very* tricky.
>
> Assuming your code is too complex or performance sensitive to use a
> compiler that can do the checking for you (e.g. maybe with Clang's
> "-ftrapv" -- see my comments below), it's reasonlyb easy to reliably do
> the checks yourself, assuming you understand your target platform.
>
> Attached is some test code I wrote quite a long time ago for checking
> compilers and such.  It uses techniques I found from various sources to
> demonstrate the possibilities of reliable integer overflow and
> underflow detection for addition and subtraction, respectively.

I am not sure what you mean by "reliable".  For example, the code
produces different results with different gcc optimisations turned on.
It's been said before (I think) but it is worth noting that any test
that does the arithmetic first has already entered the world of
undefined behaviour and that's not the best place to be for reliable
tests.

> I think I've covered testing each technique for most of the corner &
> edge cases you have to watch out for, but I can't be certain.
>
> I just re-ran it with some newer versions of GCC though and I see that
> '-ftrapv' doesn't seem to work at all any more.  They broke it bad, and
> haven't got around to fixing it yet.  See the comments in the code below.
>
> Half-hearted apologies to anyone stuck with an 80-column terminal.  Join
> the modern age and get a wider screen!  :-)

I have one now, but the last time I edited K&R style functions I didn't!

<snip code>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8241 — Re: Arithmetic overflow checking, not so hard after all

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
> "Greg A. Woods" <woods@robohack.org> writes:
> >
> > Attached is some test code I wrote quite a long time ago for checking
> > compilers and such.  It uses techniques I found from various sources to
> > demonstrate the possibilities of reliable integer overflow and
> > underflow detection for addition and subtraction, respectively.
>
> I am not sure what you mean by "reliable".  For example, the code
> produces different results with different gcc optimisations turned on.

Are you sure?  I can't get any different behaviour no matter how much
optimisation I use, and I've tried many versions of GCC, as well as
Clang now on OS X.

The only option which (sometimes) makes a difference is '-ftrapv'.  :-)

-- 
						Greg A. Woods
						RoboHack

<woods@robohack.ca>     living on the edge      http://www.robohack.ca/

[toc] | [prev] | [next] | [standalone]

#8273 — Re: Arithmetic overflow checking, not so hard after all

"Greg A. Woods" <woods@robohack.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> 
>> "Greg A. Woods" <woods@robohack.org> writes:
>> >
>> > Attached is some test code I wrote quite a long time ago for checking
>> > compilers and such.  It uses techniques I found from various sources to
>> > demonstrate the possibilities of reliable integer overflow and
>> > underflow detection for addition and subtraction, respectively.
>>
>> I am not sure what you mean by "reliable".  For example, the code
>> produces different results with different gcc optimisations turned on.
>
> Are you sure?  I can't get any different behaviour no matter how much
> optimisation I use, and I've tried many versions of GCC, as well as
> Clang now on OS X.

Maybe I'm misunderstanding the program but I get this:

$ gcc -std=c99 -pedantic -O2 ovf.c -o ovf
$ ./ovf >o2
$ gcc -std=c99 -pedantic -O3 ovf.c -o ovf
$ ./ovf >o3
$ diff o2 o3
31,33c31,33
< *** signed 2's-compliment integer addition overflow 1: 2147483647 + 1 = -2147483648!
< *** signed 2's-complement integer addition overflow 2: 2147483647 + 1 = -2147483648!
< *** signed 2's-complement integer addition overflow 3: 2147483647 + 1 = -2147483648!
---
> signed 2's-compliment integer addition 1 OK: 2147483647 + 1 = -2147483648
> signed 2's-complement integer addition 2 OK: 2147483647 + 1 = -2147483648
> signed 2's-complement integer addition 3 OK: 2147483647 + 1 = -2147483648
37c37
< *** signed 2's-compliment integer addition overflow 1: 2147483647 + 2147483647 = -2!
---
> signed 2's-compliment integer addition 1 OK: 2147483647 + 2147483647 = -2
$ gcc --version
gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8519 — Re: Arithmetic overflow checking, not so hard after all

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> $ gcc --version
> gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3

Good to know -- I don't have access to any GCC that new.

-- 
						Greg A. Woods
						RoboHack

<woods@robohack.ca>     living on the edge      http://www.robohack.ca/

[toc] | [prev] | [next] | [standalone]

#8523 — Re: Arithmetic overflow checking, not so hard after all

"Greg A. Woods" <woods@robohack.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> $ gcc --version
>> gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
>
> Good to know -- I don't have access to any GCC that new.

Spend $300 for a netbook and install Ubuntu?

[toc] | [prev] | [next] | [standalone]

#8524 — Re: Arithmetic overflow checking, not so hard after all

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
> "Greg A. Woods" <woods@robohack.org> writes:
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>> $ gcc --version
>>> gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
>>
>> Good to know -- I don't have access to any GCC that new.
>
> Spend $300 for a netbook and install Ubuntu?

Spend $0 for VirtualBox and install Ubuntu?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#9975 — Re: Arithmetic overflow checking, not so hard after all

Keith Thompson <kst-u@mib.org> writes:

> Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
>> "Greg A. Woods" <woods@robohack.org> writes:
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>> $ gcc --version
>>>> gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
>>>
>>> Good to know -- I don't have access to any GCC that new.
>>
>> Spend $300 for a netbook and install Ubuntu?
>
> Spend $0 for VirtualBox and install Ubuntu?

You've both _got_ to be kidding!  Do you have nothing else to do?

I definitely don't have time to mess with another instance of even a
system I do use, let alone a whole other kind of system than the kinds I
already use, virtual or otherwise, just to get a different version of a
portable compiler to use.  That's *insanity*.  I sure as heck don't want
to spend good money on more hardware just for this kind of thing.

(maybe such suggestions are not as insane as suggesting I purchase
another machine and also purchase and run Windoze on it too, but they're
still pretty insane ideas to me)

It's enough of a time waster using additional machines (virtual and
real) just to test stuff I have to test, let alone adding more machines
just to test software that will already run on an existing machine.

Maybe if I had a personal sysadmin assistant (and a spare bag of
cash)....  Anyone want to volunteer to be my "slave" for such tasks?

I may soon be able to trivially install different versions of GCC
simultaneously which are that new, or even newer, on an existing system
I use.  The trick here is not also wasting time trying to build
something from scratch that I would only do a one-off test with.  If my
already-in-use packaging system adds the newer GCC versions which won't
interfere with the production version I need, then I can trivially
install newer GCC packages just for these kinds of tests.

-- 
						Greg A. Woods
						RoboHack

<woods@robohack.ca>     living on the edge      http://www.robohack.ca/

[toc] | [prev] | [next] | [standalone]

#8525 — Re: Arithmetic overflow checking, not so hard after all

On Tue, 19 Jul 2011 20:47:45 -0600, Joe Pfeiffer wrote:

[snip]
 
> Spend $300 for a netbook and install Ubuntu?

Yes, that's what I did and I've never regretted it for a minute.

Todd

[toc] | [prev] | [next] | [standalone]

#8237 — Re: Arithmetic overflow checking, not so hard after all

"Greg A. Woods" <woods@robohack.org> writes:
> Keith Thompson <kst-u@mib.org> writes:
>> But detecting the overflow in the first place can be *very* tricky.
>
> Assuming your code is too complex or performance sensitive to use a
> compiler that can do the checking for you (e.g. maybe with Clang's
> "-ftrapv" -- see my comments below), it's reasonlyb easy to reliably do
> the checks yourself, assuming you understand your target platform.
                       --------------------------------------------

Which means you can't do it portably.

> Attached is some test code I wrote quite a long time ago for checking
> compilers and such.  It uses techniques I found from various sources to
> demonstrate the possibilities of reliable integer overflow and
> underflow detection for addition and subtraction, respectively.
[...]

> #ifdef USE_TIME_TO_INIT
> 	ufoo = 	(time((time_t) NULL) < 0) ? 42 : 1;
> 	ubar = 	(time((time_t) NULL) < 0) ? 42 : 1;
> #else
[...]
> #endif
[...]

Interesting, I used almost exactly the same trick just yesterday in this
very thread:

    int x = time(NULL) < 0 ? 42 : INT_MAX;

Great minds think alik.  And so do ours.  8-)}

BTW, the cast is unnecesary; since you have a #include <time.h>,
the compiler knows that time() takes a time_t* argument, and will
generate an implicit conversion.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#8299

Keith Thompson wrote:
> Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
>> markspace <-@.> writes:
>>> On 7/12/2011 6:16 AM, Stefan Ram wrote:
>>>> "BartC"<bc@freeuk.com>  writes:
>>>>> a+b overflows, but then what?
>>>>
>>>>    This can only be answered given the requirements
>>>>    specification of a specific project.
>>>
>>> What I think he's saying is there's no way physically detect the
>>> overflow in a language like C which has no exceptions.  You'd have
>>> to at least introduce some sort of global flag.
>>>
>>>   int c = a + b;
>>>   if( GLOBAL_OVERFLOW_FLAG ) {
>>>     printf( "bugger..." );
>>>   }
>>
>> Well, yes there is.  For example on an addition, if both operands
>> have the same sign and the result is the other sign, you had an
>> overflow. Analogous conditions exist (which I don't remember off the
>> top of my head and am too lazy to look up) exist for subtraction and
>> multiplication.  Integer division can't overflow.
>
> On many systems, yes, you can detect signed overflow after the fact by
> examining the values of the operands and the result.

That is post-condition checking. Pre-condition techniques are possible 
also.

>But in C, the
> behavior is undefined

So post-condition checking is not an option for signed arithmetic in C 
(not portably, anyway).

> -- and even on systems that use 2's-complement,
> an optimizing compiler can take advantage of that fact and generate
> code based on the assumption that overflow never occurs.  For
> example, this:
>
>    int x = INT_MAX;
>    if (x + 1 < x) {
>        fprintf(stderr, "Overflow!\n");
>    }
>
> can be optimized away  (For example, gcc does this at -O2 and above.)

A recognized issue. I forgot what the solution to that was. Oh yeah: 
don't optimize!

>
> And yes, integer division can overflow; consider INT_MIN / -1.
>
>> My reading of the question was "OK, you've detected an overflow.  Now
>> what do you do about it?" and the (correct) answer was, in essence,
>> "well, what do you *want* to do about it?"
>
> But detecting the overflow in the first place can be *very* tricky.

Do you mean at the programmer level or at the compiler level? 

[toc] | [prev] | [next] | [standalone]

#8178

On Tue, 12 Jul 2011 09:26:49 -0700, markspace wrote:

> On 7/12/2011 6:16 AM, Stefan Ram wrote:
>> "BartC"<bc@freeuk.com>  writes:
>>> a+b overflows, but then what?
>>
>>    This can only be answered given the requirements specification of a
>>    specific project.
> 
> 
> What I think he's saying is there's no way physically detect the
> overflow in a language like C which has no exceptions.  You'd have to at
> least introduce some sort of global flag.
> 
>    int c = a + b;
>    if( GLOBAL_OVERFLOW_FLAG ) {
>      printf( "bugger..." );
>    }

Interestingly, the much maligned COBOL has a built-in mitigation for 
overflow and a way of trapping it:

Mitigation: since you can specify the number of digits in a numeric data 
item (integer or fixed decimal), it follows that the programmer can 
control whether overflow can occur and, as the maximum size of a numeric 
field is 18 digits, the result field can almost alrays be made long 
enough.

Trapping: all computational verbs will accept the ON SIZE ERROR clause 
which, despite its name, traps almost all possible calculation errors 
including overflow, divide by zero, etc.:

ADD TRANSACTION-VALUE TO TOTAL-VALUE 
    ON SIZE ERROR PERFORM REPORT-CALCULATION-ERROR.

...and yeah, whoever it was who said Java was verbose has clearly never 
written COBOL!


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#8183

On Tue, 12 Jul 2011 16:54:36 +0000 (UTC), Martin Gregorie
<martin@address-in-sig.invalid> wrote:

[snip]

>...and yeah, whoever it was who said Java was verbose has clearly never 
>written COBOL!

     I did, and I have.  Java repeats stuff.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

Back to top | Article view | comp.lang.c

csiph-web