Re: Arithmetic overflow checking

Discussion in 'C Programming' started by tm, Jul 10, 2011.

  1. tm

    tm Guest

    On 8 Jul., 05:04, Patricia Shanahan <> wrote:
    > On 7/7/2011 5:51 PM, Peter Duniho wrote:
    > ...
    >
    > > I would not worry about the "simple" or "efficient" criteria. IMHO, if
    > > one is deciding to apply overflow checking to every computation, one has
    > > already abandoned the hope of efficiency.

    >
    > Not necessarily. I assumed a couple of decades ago that array index
    > checking would be impossibly inefficient, but it seems to work fine in
    > Java.


    And in other languages, like Pascal, Ada and Seed7, as well.

    > I suspect that having integer range types would be a major help.
    > When I'm working out whether an int can overflow, I often think in terms
    > of the ranges of inputs to calculations. A compiler would be able to
    > tell that adding a digit to a digit always fits in the range [0,18].


    I think there are two things:

    1. range checks (like value fits in [0,18]).
    2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
    computation overflows.

    In the 1. case a compiler could generate code that does
    the computation and checks the range afterwards.
    In the 2. case a computation could result in wrong data,
    because the overflow was silently ignored. In this case
    either some checks must be done before the computation or
    the overfow condition is recognized during or after the
    computation. In an ideal world the hardware would do this.

    A CPU could (in theory) easily recognize the overflow
    and generate an interrupt. This way normal computations
    (without overflow) would have no extra cost. AFAIK
    commonly used CPUs do not have this possibility. They
    have some FLAG, which is set when an overflow occurred.
    But there is no possibility to cause an interrupt, when
    the overflow FLAG is set. So code, which checks for
    overflow, must check this flag after every computation.
    Needless to say: Normal computations (without overflow)
    are slowed down by this checks.

    Because of this slow down most compilers and virtual
    machines (AFAIK inluding the JVM) have no overflow
    checking.

    In other words: A missing hardware feature:

    Trigger interupt when overflow flag is set.

    Causes compilers and JVMs to omit overflow checks.


    Greetings Thomas Mertes

    --
    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
    tm, Jul 10, 2011
    #1
    1. Advertising

  2. tm

    tm Guest

    On 10 Jul., 11:47, China Blue Dolls <> wrote:
    > In article <>,
    >
    >  tm <> wrote:
    > > On 8 Jul., 05:04, Patricia Shanahan <> wrote:
    > > > On 7/7/2011 5:51 PM, Peter Duniho wrote:
    > > > ...

    >
    > > > > I would not worry about the "simple" or "efficient" criteria. IMHO,if
    > > > > one is deciding to apply overflow checking to every computation, one has
    > > > > already abandoned the hope of efficiency.

    >
    > > > Not necessarily. I assumed a couple of decades ago that array index
    > > > checking would be impossibly inefficient, but it seems to work fine in
    > > > Java.

    >
    > >   2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
    > >      computation overflows.

    >
    > C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
    > So the concept of overflow does not apply.
    >
    > >   Trigger interupt when overflow flag is set.

    >
    > Not all CPUs detect integer arithmetic overflow. Not all CPUs signal integer
    > arithmetic problems.


    And popular CPUs, which do detect integer overflow, do not
    trigger an interupt. This makes zero overhead overflow
    detection impossible.

    So software suffers because hardware / CPU designers want
    to save a transistor...


    Greetings Thomas Mertes

    --
    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
    tm, Jul 10, 2011
    #2
    1. Advertising

  3. tm

    Eric Sosman Guest

    On 7/10/2011 5:47 AM, China Blue Dolls wrote:
    >
    > In C the array size is not part of the type or value, so there is nothing to
    > check.


    No; the size (element count) is part of an array's type. Your
    compiler will confirm this for you by issuing a diagnostic for

    char matrix[5][7]; /* five char[7] arrays */
    char (*nine)[9]; /* pointer to char[9] */
    nine = matrix; /* point it at the first char[7] */

    > C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
    > So the concept of overflow does not apply.


    This is true only for `unsigned' integer arithmetic. Signed
    integer arithmetic is in fact vulnerable to overflow.

    --
    Eric Sosman
    d
    Eric Sosman, Jul 10, 2011
    #3
  4. On Jul 10, 4:28 pm, Eric Sosman <> wrote:
    >
    >      This is true only for `unsigned' integer arithmetic.  Signed
    > integer arithmetic is in fact vulnerable to overflow.
    >

    All arithmetic is vulnerable to overflow. The question is whether the
    system reports and error or gives wrong results. Sometimes wrong
    results are better than errors, for instance in video games, but only
    rarely.
    --
    Learn all about MPI
    Tutorial on my website: http://www.malcolmmclean.site11.com/www
    Malcolm McLean, Jul 10, 2011
    #4
  5. On 07/10/2011 05:47 AM, China Blue Dolls wrote:
    > In article<>,
    >> 2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
    >> computation overflows.

    >
    > C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
    > So the concept of overflow does not apply.


    That is only true for unsigned integers; signed integer overflow is
    undefined.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
    Joshua Cranmer, Jul 10, 2011
    #5
  6. tm

    Phil Carmody Guest

    China Blue Dolls <> writes:
    > In article <>, pete <> wrote:
    > > China Blue Dolls wrote:
    > >
    > > > In C the array size is not part of the type or value,
    > > > so there is nothing to check.

    > >
    > > In C,
    > > the size of an array is part of the type of the array.


    One might even say that array types are characterized by their
    element type and by the number of elements in the array.

    > extern char s[];


    That's not an array, that's a promise that somewhere else there's
    an array.

    Phil
    --
    "At least you know where you are with Microsoft."
    "True. I just wish I'd brought a paddle." -- Matthew Vernon
    Phil Carmody, Jul 10, 2011
    #6
  7. Malcolm McLean <> writes:
    > On Jul 10, 4:28 pm, Eric Sosman <> wrote:
    >>      This is true only for `unsigned' integer arithmetic.  Signed
    >> integer arithmetic is in fact vulnerable to overflow.
    >>

    > All arithmetic is vulnerable to overflow. The question is whether the
    > system reports and error or gives wrong results. Sometimes wrong
    > results are better than errors, for instance in video games, but only
    > rarely.


    All arithmetic that's intended to model (a subset of) the real
    numbers with the usual mathematical operations is vulnerable to
    overflow. (Even arbitrary-precision packages can run out of memory.)

    But C unsigned arithmetic, for example *doesn't* model normal real
    arithmetic; it models arithmetic modulo 2**N and is not vulnerable
    to overflow. (Wraparound is not overflow; it yields the correct
    wrapped result.)

    --
    Keith Thompson (The_Other_Keith) <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"
    Keith Thompson, Jul 10, 2011
    #7
  8. On Sun, 10 Jul 2011 01:47:25 -0700 (PDT), tm <>
    wrote:

    [snip]

    >In other words: A missing hardware feature:
    >
    > Trigger interupt when overflow flag is set.
    >
    >Causes compilers and JVMs to omit overflow checks.


    No, it does not. Coupled with the idea of speed at all costs,
    yes.

    I think the safe option should be on by default. If you really
    need the speed, then you can make the decision to override.

    Most of the time, the speed is not required. I will take
    slightly slower, correct results over fast, possibly wrong results.

    Sincerely,

    Gene Wirchenko
    Gene Wirchenko, Jul 11, 2011
    #8
  9. On Jul 11, 5:58 pm, Gene Wirchenko <> wrote:
    >
    >      Most of the time, the speed is not required.  I will take
    > slightly slower, correct results over fast, possibly wrong results.
    >

    The game keeps on changing.

    For instance modern space invaders are slowed down by the need to
    normalise their vectors for lighting. Most of the rest of the code is
    either handled by special rasterisers, or is insignificant in the
    larger scheme of things. However they used to crawl about the screen
    unless you pulled all the layers of indirection and gift-wrapping and
    bounds checking away.
    --
    Learn MPI (message passing interface).
    On my website, http://www.malcolmmclean.site11.com/www
    Malcolm McLean, Jul 11, 2011
    #9
  10. On Mon, 11 Jul 2011 10:48:47 -0700 (PDT), Malcolm McLean
    <> wrote:

    >On Jul 11, 5:58 pm, Gene Wirchenko <> wrote:
    >>
    >>      Most of the time, the speed is not required.  I will take
    >> slightly slower, correct results over fast, possibly wrong results.
    >>

    >The game keeps on changing.
    >
    >For instance modern space invaders are slowed down by the need to
    >normalise their vectors for lighting. Most of the rest of the code is
    >either handled by special rasterisers, or is insignificant in the
    >larger scheme of things. However they used to crawl about the screen
    >unless you pulled all the layers of indirection and gift-wrapping and
    >bounds checking away.


    As someone once asked on a newsgroup that I follow, "How fast do
    you want your wrong answers?"

    Sincerely,

    Gene Wirchenko
    Gene Wirchenko, Jul 11, 2011
    #10
  11. tm

    tm Guest

    On 11 Jul., 16:58, Gene Wirchenko <> wrote:
    > On Sun, 10 Jul 2011 01:47:25 -0700 (PDT), tm <>
    > wrote:
    >
    > [snip]
    >
    > >In other words: A missing hardware feature:

    >
    > >  Trigger interupt when overflow flag is set.

    >
    > >Causes compilers and JVMs to omit overflow checks.

    >
    >      No, it does not.  Coupled with the idea of speed at all costs,
    > yes.
    >
    >      I think the safe option should be on by default.  If you really
    > need the speed, then you can make the decision to override.
    >
    >      Most of the time, the speed is not required.  I will take
    > slightly slower, correct results over fast, possibly wrong results.


    It is not always necessary to pay for correct results
    with a slowdown.

    Correct results can be computed without any slowdown,
    when the CPU is able to trigger an overflow interupt.

    A slowdown would only happen when an overflow occurs.
    Computations without overflow would run at full speed.


    Greetings Thomas Mertes

    --
    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
    tm, Jul 11, 2011
    #11
  12. On Mon, 11 Jul 2011 14:54:22 -0700 (PDT), tm <>
    wrote:

    >On 11 Jul., 16:58, Gene Wirchenko <> wrote:


    [snip]

    >>      Most of the time, the speed is not required.  I will take
    >> slightly slower, correct results over fast, possibly wrong results.

    >
    >It is not always necessary to pay for correct results
    >with a slowdown.


    This is not a surprise to me. If there is a slowdown, I am often
    willing to pay that cost.

    >Correct results can be computed without any slowdown,
    >when the CPU is able to trigger an overflow interupt.


    Even if the CPU does not have this facility, I still want correct
    answers.

    >A slowdown would only happen when an overflow occurs.
    >Computations without overflow would run at full speed.


    Even more reason to not avoid such checking.

    Sincerely,

    Gene Wirchenko
    Gene Wirchenko, Jul 11, 2011
    #12
  13. tm

    Eric Sosman Guest

    On 7/11/2011 5:54 PM, tm wrote:
    >[...]
    > Correct results can be computed without any slowdown,
    > when the CPU is able to trigger an overflow interupt.
    >
    > A slowdown would only happen when an overflow occurs.
    > Computations without overflow would run at full speed.


    Well, no. At least, not in any trap-capable architecture I've
    seen. Three points:

    1) Even the non-trap isn't entirely free: There's some logic in
    the execution pipeline that decides not to raise it. The silicon
    devoted to that logic might instead have been devoted to one more
    slot in a CPU-internal cache or something, so its mere presence slows
    down the CPU even if it's never exercised.

    2) In mode-bit styles, the maintenance of the mode bit carries
    a cost. You've got to set or clear it before some computation, and
    restore it afterward, and the instructions to do so aren't free. In
    the machine I mentioned earlier, the mode bit was in a "Program Status
    Word" that was mostly off-limits to user-level code; IIRC you had to
    call an O/S service to fiddle with the bit. (It's been a long time and
    maybe I don't RC, but if there were special instructions to manipulate
    the privilege-insensitive parts of the PSW, see point (3) below.)

    3) In ISA styles (different instructions to wrap or trap), you
    double the "decode space" for the instructions of interest. That is,
    the arithmetic instructions need to devote a bit to wrap/trap, and the
    bit therefore becomes unavailable for other purposes. This means that
    some otherwise desirable instructions will be absent from the ISA, and
    that programs desiring those operations will perforce execute multiple
    instructions instead of just one.

    These effects are all small (I think). But in an environment where
    a 3.63GHz part gets bragging rights over a mere 3.59GHz, I don't think
    "full speed" is entirely accurate. It's sort of like those car ads:
    "Best highway mileage *in its class*."

    --
    Eric Sosman
    d
    Eric Sosman, Jul 12, 2011
    #13
  14. On Mon, 11 Jul 2011 21:51:28 -0400, Eric Sosman
    <> wrote:

    >On 7/11/2011 5:54 PM, tm wrote:
    >>[...]
    >> Correct results can be computed without any slowdown,
    >> when the CPU is able to trigger an overflow interupt.
    >>
    >> A slowdown would only happen when an overflow occurs.
    >> Computations without overflow would run at full speed.

    >
    > Well, no. At least, not in any trap-capable architecture I've
    >seen. Three points:


    [snipped nice explanation]

    How about an example of such an architecture? A URL would be
    fine. I believe that /370 had something like that for floating point,
    but not for integer.

    > These effects are all small (I think). But in an environment where
    >a 3.63GHz part gets bragging rights over a mere 3.59GHz, I don't think
    >"full speed" is entirely accurate. It's sort of like those car ads:
    >"Best highway mileage *in its class*."


    I never did understand that phrase. With your post, I imagine
    private, car obedience classes. Every car is the best in its class.

    Sincerely,

    Gene Wirchenko
    Gene Wirchenko, Jul 12, 2011
    #14
  15. On Jul 12, 7:31 am, Gene Wirchenko <> wrote:
    >
    > >     These effects are all small (I think).  But in an environmentwhere
    > >a 3.63GHz part gets bragging rights over a mere 3.59GHz, I don't think
    > >"full speed" is entirely accurate.  It's sort of like those car ads:
    > >"Best highway mileage *in its class*."

    >
    >      I never did understand that phrase.  With your post, I imagine
    > private, car obedience classes.  Every car is the best in its class.
    >

    A dinky little hatchback will do lots of miles per gallon. However
    it's not very practical if you regularly take four adults on long
    journeys. A saloon car might be the most efficient saloon car, so the
    best in its class, and the best choice for someone looking for good
    mileage but with other constraints.
    --
    Lots of C programming goodies on my website
    http://www.malcolmmclean.site11.com/www
    Malcolm McLean, Jul 12, 2011
    #15
  16. tm

    tm Guest

    On 12 Jul., 09:05, "io_x" <> wrote:
    > "tm" <> ha scritto nel messaggionews:...
    >
    >
    >
    > > On 8 Jul., 05:04, Patricia Shanahan <> wrote:
    > >> On 7/7/2011 5:51 PM, Peter Duniho wrote:
    > >> ...

    >
    > >> > I would not worry about the "simple" or "efficient" criteria. IMHO, if
    > >> > one is deciding to apply overflow checking to every computation, onehas
    > >> > already abandoned the hope of efficiency.

    >
    > >> Not necessarily. I assumed a couple of decades ago that array index
    > >> checking would be impossibly inefficient, but it seems to work fine in
    > >> Java.

    >
    > > And in other languages, like Pascal, Ada and Seed7, as well.

    >
    > >> I suspect that having integer range types would be a major help.
    > >> When I'm working out whether an int can overflow, I often think in terms
    > >> of the ranges of inputs to calculations. A compiler would be able to
    > >> tell that adding a digit to a digit always fits in the range [0,18].

    >
    > > I think there are two things:

    >
    > >  1. range checks (like value fits in [0,18]).
    > >  2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
    > >     computation overflows.

    >
    > the carry flag for 2^n word is ok for detect overflow


    Yes, but it must be checked after every operation.
    A hardware that triggers an interrupt, would save this
    extra checks.

    Unchecked signed integer operations are used, because of
    performance reasons. Many people don't care about correct
    results, as long as they have maximum performance. With
    hardware support there would be no performance loss. So
    there would be no excuse to accept wrong results.


    Greetings Thomas Mertes

    --
    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
    tm, Jul 12, 2011
    #16
  17. On Jul 12, 12:34 pm, "io_x" <> wrote:
    >
    > #but the checks can be done one time for all, in the input
    > #data for the function for impose arg has to be in a
    > #numeric range good for not overflow
    >

    It's too fiddly, at least in C. You can overflow check if you really
    have to, but it's not a viable strategy to insert checking code for
    every single arithmetical operation that could conceivably overflow.
    You need a different language for that.
    --
    Check out MiniBasic
    http://www.malcolmmclean.site11.com/www
    Malcolm McLean, Jul 12, 2011
    #17
  18. tm

    James Kuyper Guest

    On 07/12/2011 12:31 AM, Gene Wirchenko wrote:
    > On Mon, 11 Jul 2011 21:51:28 -0400, Eric Sosman
    > <> wrote:
    >
    >> On 7/11/2011 5:54 PM, tm wrote:
    >>> [...]
    >>> Correct results can be computed without any slowdown,
    >>> when the CPU is able to trigger an overflow interupt.
    >>>
    >>> A slowdown would only happen when an overflow occurs.
    >>> Computations without overflow would run at full speed.

    >>
    >> Well, no. At least, not in any trap-capable architecture I've
    >> seen. Three points:

    >
    > [snipped nice explanation]
    >
    > How about an example of such an architecture? A URL would be
    > fine. I believe that /370 had something like that for floating point,
    > but not for integer.
    >
    >> These effects are all small (I think). But in an environment where
    >> a 3.63GHz part gets bragging rights over a mere 3.59GHz, I don't think
    >> "full speed" is entirely accurate. It's sort of like those car ads:
    >> "Best highway mileage *in its class*."

    >
    > I never did understand that phrase. With your post, I imagine
    > private, car obedience classes. Every car is the best in its class.


    [OT]The idea is borrowed from the concept of weight classes in the
    barbaric "sport" of boxing. An SUV and a sub-compact car are designed to
    carry very different loads; if you actually need the extra
    cargo/passenger capacity of the SUV, a sub-compact with much better gas
    mileage won't do you any good. However, I don't think that's the
    complete explanation for all the single-passenger SUVs I see every day
    while driving to and from work.[/OT]
    --
    James Kuyper
    James Kuyper, Jul 12, 2011
    #18
  19. tm

    BartC Guest

    "tm" <> wrote in message
    news:...

    > And popular CPUs, which do detect integer overflow, do not
    > trigger an interupt. This makes zero overhead overflow
    > detection impossible.
    >
    > So software suffers because hardware / CPU designers want
    > to save a transistor...


    Even if zero-overhead detection was possible, it's difficult to know how to
    make use of this in C. For example:

    int a,b,c;

    c=a+b;

    The a+b overflows, but then what? You can't then magically switch over to:

    long long int a,b,c;

    Even /with/ the overhead, it's difficult to see what could follow such an
    expression:

    if (overflow(c=a+b)) ...

    In the context of C-based code for implementing auto-ranging, dynamic types
    of /another language/, this might be workable, but still difficult to see
    how it can be done with zero-overhead. But this is a limited application
    (which I wouldn't even attempt in C because it's so fiddly).

    Aborting a program is also a possibility, but this just helps in debugging,
    and overheads are less relevant.

    (There is a longer thread on this in comp.lang.misc: "Integer arithmetic"
    from around start of March 2011.)

    --
    Bartc
    BartC, Jul 12, 2011
    #19
  20. tm

    tm Guest

    On 12 Jul., 11:34, "io_x" <> wrote:
    > "tm" <> ha scritto nel messaggionews:...
    > On 12 Jul., 09:05, "io_x" <> wrote:
    >
    > > > I think there are two things:

    >
    > > > 1. range checks (like value fits in [0,18]).
    > > > 2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
    > > > computation overflows.

    >
    > > the carry flag for 2^n word is ok for detect overflow
    > >Yes, but it must be checked after every operation.
    > >A hardware that triggers an interrupt, would save this
    > >extra checks.

    >
    > #if hardware 'triggers' an interrupt all you lost the prog
    > #or lost the control of the program; and this is not good.


    Why should the control of the program be lost?
    A hardware interrupt can cause an signal or an exception.
    So the program can handle the signal or handle the exception.

    On many CPUs a division by zero triggers also an interrupt.
    Depending on the language a signal or an exception allows
    the program to stay in control. Of cause such things are
    done by the runtime library in cooperation with the OS.


    Greetings Thomas Mertes

    --
    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
    tm, Jul 12, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dlamoris
    Replies:
    0
    Views:
    881
    dlamoris
    Oct 26, 2006
  2. joshc
    Replies:
    5
    Views:
    552
    Keith Thompson
    Mar 31, 2005
  3. Fraser Ross

    arithmetic overflow with enum

    Fraser Ross, Oct 9, 2005, in forum: C++
    Replies:
    5
    Views:
    510
    Fraser Ross
    Oct 10, 2005
  4. darrel
    Replies:
    4
    Views:
    811
    darrel
    Jul 19, 2007
  5. rop rop

    Arithmetic overflow checking

    rop rop, Jul 6, 2011, in forum: Java
    Replies:
    233
    Views:
    3,496
    Wolfgang Draxinger
    Sep 8, 2011
Loading...

Share This Page