Integer Overflow

Discussion in 'C Programming' started by arnuld, Dec 28, 2010.

  1. arnuld

    arnuld Guest

    WANTED: How to handle integer overflows (and overflows in general)

    #include <stdio.h>
    #include <limits.h>
    #include <errno.h>


    int main(void)
    {
    int i, j, k;

    errno = 0;
    j = k = INT_MAX;
    i = j + k;

    printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    return 0;
    }
    ===================== OUTPUT ============================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
    [arnuld@dune programs]$ ./a.out
    i = -2, errno = 0, ERANGE = 34
    [arnuld@dune programs]$



    It overflows of course, (OT) gcc does not give any error even when all
    flags are on (/OT). errno does not work, its value is still zero after
    that overflow. In this case how to check for overflow ? I have checked
    FAQs and 20.6b gives a technique to handle this which I have applied down
    here, it works fine but I am not sure it will still work if I change line
    j = k = INT_MAX to j = k = INT_MIN



    int main(void)
    {
    int i, j, k;

    errno = 0;
    j = k = INT_MAX;

    if(INT_MAX - j < k)
    {
    printf("Overflow error\n");
    i = INT_MAX;
    }
    else
    {
    i = j + k;
    }


    printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    return 0;
    }




    NOTE: Came to think of this exercise because of this article that claims
    "Nearly all binary searches and mergesorts are broken". Author talsk
    about line 6 but I think line 3 will overflow issue if written in C, if
    a.length comes out to be greater than INT_MAX.

    http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-
    nearly.html




    --
    http://www.lispmachine.wordpress.com
    arnuld, Dec 28, 2010
    #1
    1. Advertising

  2. arnuld

    Ike Naar Guest

    On 2010-12-28, arnuld <> wrote:
    > I have checked
    > FAQs and 20.6b gives a technique to handle this which I have applied down
    > here, it works fine but I am not sure it will still work if I change line
    > j = k = INT_MAX to j = k = INT_MIN


    For reference, the FAQ says:

    if(INT_MAX - b < a) {
    fputs("int overflow\n", stderr);
    return INT_MAX;
    }
    return a + b;

    To check for underflow as well, you'll have to make a
    slightly more elaborate test, something like:

    if (0 < a && INT_MAX - a < b)
    {
    return INT_MAX; /* overflow */
    }
    else if (a < 0 && b < INT_MIN - a)
    {
    return INT_MIN; /* underflow */
    }
    else
    {
    return a + b; /* okay */
    }
    Ike Naar, Dec 28, 2010
    #2
    1. Advertising

  3. arnuld

    jacob navia Guest

    Le 28/12/10 11:13, arnuld a écrit :
    >
    > WANTED: How to handle integer overflows (and overflows in general)
    >
    > #include<stdio.h>
    > #include<limits.h>
    > #include<errno.h>
    >
    >
    > int main(void)
    > {
    > int i, j, k;
    >
    > errno = 0;
    > j = k = INT_MAX;
    > i = j + k;
    >
    > printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    > return 0;
    > }
    > ===================== OUTPUT ============================
    > [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
    > [arnuld@dune programs]$ ./a.out
    > i = -2, errno = 0, ERANGE = 34
    > [arnuld@dune programs]$
    >
    >
    >
    > It overflows of course, (OT) gcc does not give any error even when all
    > flags are on (/OT). errno does not work, its value is still zero after
    > that overflow. In this case how to check for overflow ? I have checked
    > FAQs and 20.6b gives a technique to handle this which I have applied down
    > here, it works fine but I am not sure it will still work if I change line
    > j = k = INT_MAX to j = k = INT_MIN
    >
    >
    >
    > int main(void)
    > {
    > int i, j, k;
    >
    > errno = 0;
    > j = k = INT_MAX;
    >
    > if(INT_MAX - j< k)
    > {
    > printf("Overflow error\n");
    > i = INT_MAX;
    > }
    > else
    > {
    > i = j + k;
    > }
    >
    >
    > printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    > return 0;
    > }
    >
    >
    >
    >
    > NOTE: Came to think of this exercise because of this article that claims
    > "Nearly all binary searches and mergesorts are broken". Author talsk
    > about line 6 but I think line 3 will overflow issue if written in C, if
    > a.length comes out to be greater than INT_MAX.
    >
    > http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-
    > nearly.html
    >
    >
    >
    >


    The lcc-win compiler allows you to check for overflow in all signed
    integer operations. I have proposed that this be incorporated into
    the C language as a standard but people in comp.std.c seem to prefer
    wrong results than "wasting" some cycles in checking overflow.

    Note that many other languages based on C (for instance Eiffel) have the
    same problem.

    You can download the lcc-win compiler at no cost from:

    http://www.q-software-solutions.de
    or
    http://www.cs.virginia.edu/~lcc-win32

    jacob
    jacob navia, Dec 28, 2010
    #3
  4. On Dec 28, 10:13 am, arnuld <> wrote:
    > WANTED: How to handle integer overflows (and overflows in general)
    >
    > NOTE: Came to think of this exercise because of this article that claims
    > "Nearly all binary searches and mergesorts are broken".
    >

    Normally it's inappropriate for general-purpose logic code to have to
    worry about overflow.

    The real answer is to join the campaign for 64 bit ints. Searchable
    arrays of real data aren't going to go above 64 bits any time soon, so
    the problem is eliminated.
    Malcolm McLean, Dec 28, 2010
    #4
  5. arnuld

    Eric Sosman Guest

    On 12/28/2010 5:13 AM, arnuld wrote:
    >
    > WANTED: How to handle integer overflows (and overflows in general)


    Avoid them. If a conversion or (sub-)expression overflows,
    the behavior is undefined -- meaning, among other things, that
    it's already too late to "handle" something.

    --
    Eric Sosman
    lid
    Eric Sosman, Dec 28, 2010
    #5
  6. arnuld wrote:
    > #include<stdio.h>
    > #include<limits.h>
    > #include<errno.h>
    >
    >
    > int main(void)
    > {
    > int i, j, k;
    >
    > errno = 0;
    > j = k = INT_MAX;
    > i = j + k;
    >
    > printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    > return 0;
    > }
    > ===================== OUTPUT ============================
    > [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
    > [arnuld@dune programs]$ ./a.out
    > i = -2, errno = 0, ERANGE = 34
    > [arnuld@dune programs]$


    $ gcc -ansi -pedantic -Wall -Wextra -m32 -ftrapv test.c
    $ ./a.out
    Aborted
    $

    As this example illustrates, the compiler is allowed to make signed
    overflows cause an exception (in this case, a signal is raised).
    --
    Marcin Grzegorczyk
    Marcin Grzegorczyk, Dec 28, 2010
    #6
  7. arnuld

    BGB Guest

    On 12/28/2010 4:15 AM, jacob navia wrote:
    > Le 28/12/10 11:13, arnuld a écrit :
    >>
    >> WANTED: How to handle integer overflows (and overflows in general)
    >>
    >> #include<stdio.h>
    >> #include<limits.h>
    >> #include<errno.h>
    >>
    >>
    >> int main(void)
    >> {
    >> int i, j, k;
    >>
    >> errno = 0;
    >> j = k = INT_MAX;
    >> i = j + k;
    >>
    >> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    >> return 0;
    >> }
    >> ===================== OUTPUT ============================
    >> [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
    >> [arnuld@dune programs]$ ./a.out
    >> i = -2, errno = 0, ERANGE = 34
    >> [arnuld@dune programs]$
    >>
    >>
    >>
    >> It overflows of course, (OT) gcc does not give any error even when all
    >> flags are on (/OT). errno does not work, its value is still zero after
    >> that overflow. In this case how to check for overflow ? I have checked
    >> FAQs and 20.6b gives a technique to handle this which I have applied down
    >> here, it works fine but I am not sure it will still work if I change line
    >> j = k = INT_MAX to j = k = INT_MIN
    >>
    >>
    >>
    >> int main(void)
    >> {
    >> int i, j, k;
    >>
    >> errno = 0;
    >> j = k = INT_MAX;
    >>
    >> if(INT_MAX - j< k)
    >> {
    >> printf("Overflow error\n");
    >> i = INT_MAX;
    >> }
    >> else
    >> {
    >> i = j + k;
    >> }
    >>
    >>
    >> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
    >> return 0;
    >> }
    >>
    >>
    >>
    >>
    >> NOTE: Came to think of this exercise because of this article that claims
    >> "Nearly all binary searches and mergesorts are broken". Author talsk
    >> about line 6 but I think line 3 will overflow issue if written in C, if
    >> a.length comes out to be greater than INT_MAX.
    >>
    >> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-
    >> nearly.html
    >>
    >>
    >>
    >>

    >
    > The lcc-win compiler allows you to check for overflow in all signed
    > integer operations. I have proposed that this be incorporated into
    > the C language as a standard but people in comp.std.c seem to prefer
    > wrong results than "wasting" some cycles in checking overflow.
    >
    > Note that many other languages based on C (for instance Eiffel) have the
    > same problem.
    >
    > You can download the lcc-win compiler at no cost from:
    >
    > http://www.q-software-solutions.de
    > or
    > http://www.cs.virginia.edu/~lcc-win32
    >


    well, one could always do arithmetic via API calls if they wanted
    overflow-detecting calls.

    for example, hypothetical API calls:
    k=suAddInt32(i, j);
    if(suStatusOvfP())
    ...

    then, these could be implemented via ordinary calls (C or ASM), or via
    macros and compiler intrinsics...


    this would also avoid breaking any code which depends on the typical
    integer overflow semantics or causing an overhead for operations where
    overflow is not of particular interest, and also allows for a pure C
    implementation if needed.

    or such...
    BGB, Dec 28, 2010
    #7
  8. On 2010-12-28 12:00, Ike Naar wrote:
    > To check for underflow as well,

    [...]

    You mean negative overflow.

    /August

    --
    The competent programmer is fully aware of the limited size of his own
    skull. He therefore approaches his task with full humility, and avoids
    clever tricks like the plague. --Edsger Dijkstra
    August Karlstrom, Dec 28, 2010
    #8
  9. BGB <> writes:
    [...]
    > well, one could always do arithmetic via API calls if they wanted
    > overflow-detecting calls.
    >
    > for example, hypothetical API calls:
    > k=suAddInt32(i, j);
    > if(suStatusOvfP())
    > ...
    >
    > then, these could be implemented via ordinary calls (C or ASM), or via
    > macros and compiler intrinsics...


    One problem with that particular interface is that the linkage
    between the call and the status is IMHO too loose. The C standard's
    use of errno suffers from similar problems. For example, in the
    presence of threading the implementation has to play tricks to avoid
    getting status results from a different thread. In effect, the error
    status is a global variable, with all the problems that can cause.

    Unfortunately, C doesn't provide a good clean way of doing this.
    You might have something like this:

    err = suAddInt32(&sum, i, j);
    if (err == 0) {
    /* ok, sum contains the result */
    }
    else {
    /* something went wrong, err tells you what */
    }

    Or it could return the sum and store the error code via a pointer
    argument.

    I'm almost tempted to suggest that adding exception handling to
    the language might not be a completely horrible idea.

    --
    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, Dec 28, 2010
    #9
  10. arnuld

    BGB Guest

    On 12/28/2010 2:46 PM, Keith Thompson wrote:
    > BGB<> writes:
    > [...]
    >> well, one could always do arithmetic via API calls if they wanted
    >> overflow-detecting calls.
    >>
    >> for example, hypothetical API calls:
    >> k=suAddInt32(i, j);
    >> if(suStatusOvfP())
    >> ...
    >>
    >> then, these could be implemented via ordinary calls (C or ASM), or via
    >> macros and compiler intrinsics...

    >
    > One problem with that particular interface is that the linkage
    > between the call and the status is IMHO too loose. The C standard's
    > use of errno suffers from similar problems. For example, in the
    > presence of threading the implementation has to play tricks to avoid
    > getting status results from a different thread. In effect, the error
    > status is a global variable, with all the problems that can cause.
    >
    > Unfortunately, C doesn't provide a good clean way of doing this.
    > You might have something like this:
    >
    > err = suAddInt32(&sum, i, j);
    > if (err == 0) {
    > /* ok, sum contains the result */
    > }
    > else {
    > /* something went wrong, err tells you what */
    > }
    >
    > Or it could return the sum and store the error code via a pointer
    > argument.
    >
    > I'm almost tempted to suggest that adding exception handling to
    > the language might not be a completely horrible idea.
    >


    one could use thread-local storage for this...

    AFAIK pretty much all (common?) OS's with threads also provide for TLS
    and similar...

    if errno was accessed via a function call, little would stop putting
    this in TLS as well (however, as-is, doing so requires using compiler
    specific extensions, such as the "__thread" modifier or similar for
    MSVC, ...).


    this way, one doesn't need to bother with providing a convoluted API to
    manage status, ....

    for example, AFAIK, OpenGL contexts are often handled via TLS, ...

    or such...
    BGB, Dec 29, 2010
    #10
  11. arnuld

    BGB Guest

    On 12/28/2010 10:41 PM, BGB wrote:
    > On 12/28/2010 2:46 PM, Keith Thompson wrote:
    >> BGB<> writes:
    >> [...]
    >>> well, one could always do arithmetic via API calls if they wanted
    >>> overflow-detecting calls.
    >>>
    >>> for example, hypothetical API calls:
    >>> k=suAddInt32(i, j);
    >>> if(suStatusOvfP())
    >>> ...
    >>>
    >>> then, these could be implemented via ordinary calls (C or ASM), or via
    >>> macros and compiler intrinsics...

    >>
    >> One problem with that particular interface is that the linkage
    >> between the call and the status is IMHO too loose. The C standard's
    >> use of errno suffers from similar problems. For example, in the
    >> presence of threading the implementation has to play tricks to avoid
    >> getting status results from a different thread. In effect, the error
    >> status is a global variable, with all the problems that can cause.
    >>
    >> Unfortunately, C doesn't provide a good clean way of doing this.
    >> You might have something like this:
    >>
    >> err = suAddInt32(&sum, i, j);
    >> if (err == 0) {
    >> /* ok, sum contains the result */
    >> }
    >> else {
    >> /* something went wrong, err tells you what */
    >> }
    >>
    >> Or it could return the sum and store the error code via a pointer
    >> argument.
    >>
    >> I'm almost tempted to suggest that adding exception handling to
    >> the language might not be a completely horrible idea.
    >>

    >
    > one could use thread-local storage for this...
    >
    > AFAIK pretty much all (common?) OS's with threads also provide for TLS
    > and similar...
    >
    > if errno was accessed via a function call, little would stop putting
    > this in TLS as well (however, as-is, doing so requires using compiler
    > specific extensions, such as the "__thread" modifier or similar for
    > MSVC, ...).
    >


    correction (brain dump...):
    __thread is for GCC for, __declspec(thread) is for MSVC, grr...
    typically, I wrap stuff like this in macros anyways though...
    BGB, Dec 29, 2010
    #11
  12. arnuld

    jacob navia Guest

    Le 28/12/10 22:46, Keith Thompson a écrit :
    > BGB<> writes:
    > [...]
    >> well, one could always do arithmetic via API calls if they wanted
    >> overflow-detecting calls.
    >>
    >> for example, hypothetical API calls:
    >> k=suAddInt32(i, j);
    >> if(suStatusOvfP())
    >> ...
    >>
    >> then, these could be implemented via ordinary calls (C or ASM), or via
    >> macros and compiler intrinsics...

    >
    > One problem with that particular interface is that the linkage
    > between the call and the status is IMHO too loose. The C standard's
    > use of errno suffers from similar problems. For example, in the
    > presence of threading the implementation has to play tricks to avoid
    > getting status results from a different thread. In effect, the error
    > status is a global variable, with all the problems that can cause.
    >
    > Unfortunately, C doesn't provide a good clean way of doing this.
    > You might have something like this:
    >
    > err = suAddInt32(&sum, i, j);
    > if (err == 0) {
    > /* ok, sum contains the result */
    > }
    > else {
    > /* something went wrong, err tells you what */
    > }
    >
    > Or it could return the sum and store the error code via a pointer
    > argument.
    >
    > I'm almost tempted to suggest that adding exception handling to
    > the language might not be a completely horrible idea.
    >

    lcc-win proposes:

    int a,b,c;
    // ...
    c = a+b;
    if (_overflow()) {
    }

    What's wrong with that?

    In i386asm:
    addl %eax,%ecx
    jo _overflowhandler
    jacob navia, Dec 29, 2010
    #12
  13. arnuld

    BGB Guest

    On 12/28/2010 11:31 PM, jacob navia wrote:
    > Le 28/12/10 22:46, Keith Thompson a écrit :
    >> BGB<> writes:
    >> [...]
    >>> well, one could always do arithmetic via API calls if they wanted
    >>> overflow-detecting calls.
    >>>
    >>> for example, hypothetical API calls:
    >>> k=suAddInt32(i, j);
    >>> if(suStatusOvfP())
    >>> ...
    >>>
    >>> then, these could be implemented via ordinary calls (C or ASM), or via
    >>> macros and compiler intrinsics...

    >>
    >> One problem with that particular interface is that the linkage
    >> between the call and the status is IMHO too loose. The C standard's
    >> use of errno suffers from similar problems. For example, in the
    >> presence of threading the implementation has to play tricks to avoid
    >> getting status results from a different thread. In effect, the error
    >> status is a global variable, with all the problems that can cause.
    >>
    >> Unfortunately, C doesn't provide a good clean way of doing this.
    >> You might have something like this:
    >>
    >> err = suAddInt32(&sum, i, j);
    >> if (err == 0) {
    >> /* ok, sum contains the result */
    >> }
    >> else {
    >> /* something went wrong, err tells you what */
    >> }
    >>
    >> Or it could return the sum and store the error code via a pointer
    >> argument.
    >>
    >> I'm almost tempted to suggest that adding exception handling to
    >> the language might not be a completely horrible idea.
    >>

    > lcc-win proposes:
    >
    > int a,b,c;
    > // ...
    > c = a+b;
    > if (_overflow()) {
    > }
    >
    > What's wrong with that?
    >
    > In i386asm:
    > addl %eax,%ecx
    > jo _overflowhandler


    issues:
    no pure C implementation is possible (while still preserving semantics);
    it may carry costs on architectures which do not provide this by default
    (arithmetic isn't safe unless the optimizer notes that one doesn't
    capture the state);
    since these status codes can only apply to a single operation at a time,
    little is gained by using a raw operator;
    ....

    providing a special intrinsic to wrap the addition allows similar to be
    done without requiring this.


    in my case, early on I had also added additional semantics to C to add a
    new feature: geometric vector math.

    however, after realizing the costs of using the feature in this form, I
    switched to using intrinsics instead, since they could provide an API
    which would work on existing compilers with only a modest increase in
    typing.


    more so, defining something like, say:
    #define suAddInt32(a, b) ((a)+(b))
    #define suStatusOvfP() _overflow()

    would be... trivial...


    similarly, I also use a standard-C-friendly interface for dynamic types
    and OO facilities as well, since again this avoids compiler-specific
    features...

    it is really no different from wrapping any compiler specific keywords
    or annotations in macros so that they may be stripped out in standard C.

    for example, I could have stuff in my code like:

    typedef struct FooObj_s *FooObj __declspec(dytname("_foo_obj_t"));
    typedef __variant_this FooObj FooThis;
    ....

    or, also valid:
    typedef [dytname("_foo_obj_t") this] struct FooObj_s *FooObj;


    but, I found it preferable to wrap a lot of this in generic macros, say:

    typedef struct FooObj_s *FooObj dytname("_foo_obj_t");
    typedef dycThisT(FooObj) FooThis;

    which allow the preprocessor to strip a lot out, and without necessarily
    exposing standard C compilers to a lot of my extensions and IDL and
    reflection-related metadata...


    much like a few simple macros allow me to both make use of
    __declspec(dllimport) and __declspec(dllexport) without compromising my
    ability to build my code on Linux and via both MSVC and GCC in addition
    to using my own tools, ...


    I hope the reasoning for this is understood...
    BGB, Dec 29, 2010
    #13
  14. arnuld

    jacob navia Guest

    Le 29/12/10 09:18, BGB a écrit :
    > On 12/28/2010 11:31 PM, jacob navia wrote:


    >> lcc-win proposes:
    >>
    >> int a,b,c;
    >> // ...
    >> c = a+b;
    >> if (_overflow()) {
    >> }
    >>
    >> What's wrong with that?
    >>
    >> In i386asm:
    >> addl %eax,%ecx
    >> jo _overflowhandler

    >
    > issues:
    > no pure C implementation is possible (while still preserving semantics);


    Yes.
    But for the implementing a+b there is no pure c implementation either.
    It is clear that at *some* level C must meet assembly.

    > it may carry costs on architectures which do not provide this by default
    > (arithmetic isn't safe unless the optimizer notes that one doesn't
    > capture the state);


    There is no processor that hasn't an overflow flag. And if
    you happen to run in a weird processor without it, you can always
    write it in C...

    > since these status codes can only apply to a single operation at a time,
    > little is gained by using a raw operator;


    Yes, you have to split your statements to figure out which operation
    overflowed, if you are interested in that.

    > ...
    >
    > providing a special intrinsic to wrap the addition allows similar to be
    > done without requiring this.
    >


    That's the same actually:

    #define myProtectedAddition(result,op1,op2) result=op1+op2,_overflow()

    >
    > in my case, early on I had also added additional semantics to C to add a
    > new feature: geometric vector math.
    >
    > however, after realizing the costs of using the feature in this form, I
    > switched to using intrinsics instead, since they could provide an API
    > which would work on existing compilers with only a modest increase in
    > typing.
    >


    That's what I propose: _overflow() is an intrinsic.
    >
    > more so, defining something like, say:
    > #define suAddInt32(a, b) ((a)+(b))
    > #define suStatusOvfP() _overflow()
    >
    > would be... trivial...
    >

    Yes

    [snip]

    >
    > I hope the reasoning for this is understood...
    >


    Yes, but that is not about checking for overflow. Now tell me:

    How does your compiler handle it then?
    jacob navia, Dec 29, 2010
    #14
  15. arnuld

    BartC Guest

    "arnuld" <> wrote in message
    news:4d19b83a$0$23763$...

    > NOTE: Came to think of this exercise because of this article that claims
    > "Nearly all binary searches and mergesorts are broken". Author talsk
    > about line 6 but I think line 3 will overflow issue if written in C, if
    > a.length comes out to be greater than INT_MAX.
    >
    > http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-
    > nearly.html


    That exercise will fail on the (high+low)/2 expression when high+low is
    likely to exceed around two billion.

    As the articles says, this was unlikely when the code was created (and even
    now, would only apply to an int-array size of 4MB or more).

    The answer is simply to use a more appropriate int-size, as trying to mess
    about with overflow detection in code like this is a waste of time. (Suppose
    you *do* detect that high+low overflows, then what, try and reinvent some
    way of doing 33-bit arithmetic?

    And what would happen if high and low were unsigned; in that case the
    results would go wrong when high+low exceeded about four billion, but this
    time that would be well-defined!)

    If no wider arithmetic was available, then it would simplest (in this
    example), to just impose an upper limit on how big an array can be searched.

    I think overflow detection (ie. detecting it after the event) is more useful
    when implementing some higher arithmetic routines, rather than for general
    use.

    --
    Bartc
    BartC, Dec 29, 2010
    #15
  16. arnuld

    BartC Guest

    "pete" <> wrote in message
    news:...
    > BartC wrote:
    >> "arnuld" <> wrote in message


    >>> nearly.html

    >>
    >> That exercise will fail on the (high+low)/2 expression when high+low is
    >> likely to exceed around two billion.
    >>


    >> If no wider arithmetic was available, then it would simplest

    >
    > No it wouldn't.
    >
    >> (in this example),

    >
    > This is simpler: (high - low) / 2 + low


    >> to just impose an upper limit on how big an array can be searched.


    > A bit of analysis, is worth a byte of program.


    Well, it would be simpler than rewriting code (that has been proved correct,
    apparently). Especially if the routine is inside someone else's binary
    library.

    Although even with that fix, it might still not be possible to search the
    maximum possible array size, depending on the type of a.length, so limits
    could still be advisable (but at a more reasonable two billion elements
    rather than one).

    And specifying a range of inputs to a routine, over which it is guaranteed
    to work properly, might still be a useful thing to do.

    --
    Bartc
    BartC, Dec 29, 2010
    #16
  17. arnuld

    jacob navia Guest

    Le 29/12/10 15:34, christian.bau a écrit :
    > On Dec 29, 6:31 am, jacob navia<> wrote:
    >
    >> lcc-win proposes:
    >>
    >> int a,b,c;
    >> // ...
    >> c = a+b;
    >> if (_overflow()) {
    >>
    >> }
    >>
    >> What's wrong with that?

    >
    > So what about this:
    >
    > c = a + b + c;
    > if (_overflow()) {
    > }
    >


    This is invalid since you do not know where the
    overflow happened. The correct way is:
    c = c+b;
    if (_overflow()) goto error;
    c += a;
    if (_overflow()) goto error;

    This becomes quickly tedious. That is whty lcc win allows you to
    specify
    #pragma overflowcheck on/off

    > How is that going to work? Or c = f () + g () ?
    >

    c = f();
    tmp = g();
    if (c+= tmp,_overflow()) goto error;

    > What _precisely_ is the semantics of the "_overflow" function?


    It returns 1 if the last operation overflowed, zero if not.
    Concerned operations: signed +,-,*, and /.


    What
    > about this one:
    >
    > c = a + b;
    > error = (_overflow() | (c + 3 == x));

    if a+b overflowed or c+3 is equal to x error is 1, otherwise is zero
    what else you expect?
    >
    > Keep in mind that I wrote | and not ||.
    >


    If the right hand is evaluated before the intrinsic the new operation
    will overwrite any overflow flag from the last one.

    All this problems can be avoided if you use the #pragma overflowcheck
    form.

    What bothers me is that you seem so upset that I offer a SOLUTION
    instead of just allowing UB. Maybe you can offer a BETTER solution?

    I am all ears.

    jacob
    jacob navia, Dec 29, 2010
    #17
  18. arnuld

    jacob navia Guest

    Some people here aren't aware of the problems overflow can produce. Just
    remember the calloc example

    Many implementations of calloc(count size) just multiply count*size
    ignoring overflow with catastrophic results. We had a discussion about
    that in comp.lang.c

    jacob
    jacob navia, Dec 29, 2010
    #18
  19. arnuld

    BGB Guest

    On 12/29/2010 10:44 AM, jacob navia wrote:
    > Some people here aren't aware of the problems overflow can produce. Just
    > remember the calloc example
    >
    > Many implementations of calloc(count size) just multiply count*size
    > ignoring overflow with catastrophic results. We had a discussion about
    > that in comp.lang.c
    >


    if one has an overflow here, then one already has much greater problems
    than having an overflow here...

    > jacob
    BGB, Dec 29, 2010
    #19
  20. arnuld

    Jorgen Grahn Guest

    On Tue, 2010-12-28, Keith Thompson wrote:
    > BGB <> writes:
    > [...]
    >> well, one could always do arithmetic via API calls if they wanted
    >> overflow-detecting calls.
    >>
    >> for example, hypothetical API calls:
    >> k=suAddInt32(i, j);
    >> if(suStatusOvfP())
    >> ...
    >>
    >> then, these could be implemented via ordinary calls (C or ASM), or via
    >> macros and compiler intrinsics...

    >
    > One problem with that particular interface is that the linkage
    > between the call and the status is IMHO too loose. The C standard's
    > use of errno suffers from similar problems. For example, in the
    > presence of threading the implementation has to play tricks to avoid
    > getting status results from a different thread. In effect, the error
    > status is a global variable, with all the problems that can cause.
    >
    > Unfortunately, C doesn't provide a good clean way of doing this.
    > You might have something like this:
    >
    > err = suAddInt32(&sum, i, j);
    > if (err == 0) {
    > /* ok, sum contains the result */
    > }
    > else {
    > /* something went wrong, err tells you what */
    > }
    >
    > Or it could return the sum and store the error code via a pointer
    > argument.
    >
    > I'm almost tempted to suggest that adding exception handling to
    > the language might not be a completely horrible idea.


    I'd suggest simply moving to C++ for the situations where you need to
    fail explicitly rather than suffer the silent overflow. The mechanism
    is there already -- and so is operator overloading, to make it
    readable.

    This was after all one of the reasons C++ got created in the first
    place.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Dec 29, 2010
    #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. bartek
    Replies:
    3
    Views:
    3,079
    bartek
    Feb 6, 2004
  2. John Black
    Replies:
    1
    Views:
    4,489
    John Harrison
    Apr 15, 2004
  3. deancoo

    integer or long overflow...

    deancoo, Mar 5, 2005, in forum: C++
    Replies:
    11
    Views:
    750
    Pete Becker
    Mar 5, 2005
  4. Enrico 'Trippo' Porreca

    Integer overflow

    Enrico 'Trippo' Porreca, Aug 21, 2003, in forum: C Programming
    Replies:
    9
    Views:
    400
  5. Ashutosh Iddya

    integer overflow

    Ashutosh Iddya, Apr 16, 2004, in forum: C Programming
    Replies:
    25
    Views:
    908
    RoSsIaCrIiLoIA
    Apr 24, 2004
Loading...

Share This Page