Thread: reliably checking for overflow before addition?

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229

    reliably checking for overflow before addition?

    Is there a reliable way to check for overflow before addition, without casting to a bigger type, or go into assembly to check the carry flag?

    If I understand it correctly, the classic way -
    Code:
    u32 a;
    if ((a+10) < 10) //overflow
    is not reliable since overflow is not defined, and the compiler can and do optimize the check away.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    The overflow of unsigned numbers is defined. They use modulo arithmetic.

    For signed numbers, there is no portable way.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Why not something like this?
    Code:
    #include <climits>
    
    int addition_will_overflow(int x, int y) {
        if(INT_MAX - x >= y) return 0;
    
        // the addition will overflow
        return 1;
    }
    That only works for positive numbers, but I'm sure you could figure something out for negative ones too . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Close dwks. There are two circumstances when computing x+y (both ints) will overflow:

    1) When both are positive, and INT_MAX - x < y; OR

    2) When both are negative, and INT_MIN - x < y

    I'll leave it as an exercise to work out if adding a positive to a negative value overflows, if adding zero overflows, what happens when computing INT_MAX - x (x positive), or what happens when computing INT_MIN - x (for x negative).

    Incidentally, INT_MAX and INT_MIN are represented as std::numeric_limits<int>::max() and std::numeric_limits<int>::min() respectively in C++.

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    The overflow of unsigned numbers is defined. They use modulo arithmetic.

    For signed numbers, there is no portable way.
    Thanks. Nice to know.

    I'll leave it as an exercise to work out if adding a positive to a negative value overflows, if adding zero overflows, what happens when computing INT_MAX - x (x positive), or what happens when computing INT_MIN - x (for x negative).
    The answer is they all don't overflow?

    From dwks's code and grumpy's hint -
    Code:
    bool addition_will_overflow(int a, int b) {
    	if (a > 0 && b > 0) {
    		return (INT_MAX - a) < b;
    	} else if (a < 0 && b < 0) {
    		return (INT_MIN - a) > b;
    	}
    	return false;
    }
    Is that it?
    Last edited by cyberfish; 06-21-2008 at 02:45 AM.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by grumpy View Post
    Incidentally, INT_MAX and INT_MIN are represented as std::numeric_limits<int>::max() and std::numeric_limits<int>::min() respectively in C++.
    And I still don't understand why they made them runtime functions.
    You could alternatively use boost::integer_traits<int>::const_max or boost::integer_traits<int>::const_min.
    They're constant, so that's far better than std's implementation.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Elysia View Post
    And I still don't understand why they made them runtime functions.
    There is no requirement they be runtine functions.

    std::numeric_limits<int>::min() and max() return implementation defined values, with nothing preventing them being inlined at compile time. In practice, it is not difficult for compilers to inline such functions (they are simply a getter) and the return value is usually substituted directly in place of the "function call" at compile time.

    In other words, there is nothing in the standard that requires these functions to be evaluated at runtime and, in practice, they usually are not.
    Quote Originally Posted by Elysia View Post
    You could alternatively use boost::integer_traits<int>::const_max or boost::integer_traits<int>::const_min.
    They're constant, so that's far better than std's implementation.
    Just a different way of achieving the same thing.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by grumpy View Post
    There is no requirement they be runtine functions.

    std::numeric_limits<int>::min() and max() return implementation defined values, with nothing preventing them being inlined at compile time. In practice, it is not difficult for compilers to inline such functions (they are simply a getter) and the return value is usually substituted directly in place of the "function call" at compile time.

    In other words, there is nothing in the standard that requires these functions to be evaluated at runtime and, in practice, they usually are not.
    Perhaps. But then again, perhaps not.
    Do they return constant values?
    If not, that's a major oversight on their part, because it severely hinders what can be done at compile time, especially with meta-programming.

    Just a different way of achieving the same thing.
    But it has its advantages.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Elysia View Post
    Perhaps. But then again, perhaps not.
    Do they return constant values?
    std::numeric_limits<T>::min() and max() return the minimum and maximum finite value of the type respectively - and those values are implementation defined constants (ie in the case of int they are INT_MIN and INT_MAX respectively).
    Quote Originally Posted by Elysia View Post
    If not, that's a major oversight on their part, because it severely hinders what can be done at compile time, especially with meta-programming.
    That is not true: C++ templates are specified as a compile-time, Turing-complete, meta-language ie the process of template expansion can be implemented completely and optimised at compile time. There is a pile of information freely available on such things; look up the topic of "Compile-time code optimization" - interestingly inlining of functions is one of the simplest metaprogramming techniques.
    But it has its advantages.
    Other than convenience of syntax, I'd be curious to know what you consider those to be. (I exclude syntax, because the notion of "best" or "advantageous" is highly subjective when it comes to elements of syntax -- we could debate different ideas about syntax for months, and both be completely correct at the same time by some measure).
    Last edited by grumpy; 06-21-2008 at 07:22 AM.

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Well, maybe I am underestimating what the compiler can do, but I would still like to prefer boost's syntax, at least.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    OK, let's see. The return values of numeric_limits::min() and max() are not compile-time constants from the language point of view, for the simple reason that function return values never are. This is not a performance problem, since these functions will most definitely be inlined by any even halfway decent compiler, but it matters because compile-time constants are required in some circumstances. In particular, you can't use min() and max() as array bounds or as non-type template parameters.

    There are some very good reasons to make them functions. Peculiarly enough, one of those reasons is performance. Consider:
    Code:
    // This is <limits>
    
    template <>
    struct numeric_limits<float>
    {
      static float min() { return <minimal floating point value>; }
    };
    This is what a specialization of numeric_limits looks like in the standard. The compiler, seeing a call of min(), would simply inline the function and find out that it's dealing with a simple literal, opening up a lot of new optimization opportunities.

    Let's examine the possibilities if it's a static constant variable.
    Code:
    // This is <limits>
    
    template <>
    struct numeric_limits<float>
    {
      static const float min = <minimal floating point value>;
    };
    Nope, that's an error. Inline initialization is only allowed for integral static constants.

    Code:
    // This is <limits>
    
    template <>
    struct numeric_limits<float>
    {
      static const float min;
    };
    
    template <>
    const float numeric_limits<float>::min = <minimal floating point value>;
    Nope, that's another error. Specifically, you'll get linker errors from this symbol.

    How about this then?
    Code:
    // This is <limits>
    
    template <>
    struct numeric_limits<float>
    {
      static const float min;
    };
    
    // This is limits.cpp, a file linked into the compiler's precompiled standard library.
    
    template <>
    const float numeric_limits<float>::min = <minimal floating point value>;
    Ah yes, that works. Only, now the constant value is no longer accessible to the compiler for further optimization. Oops.

    OK, so a compiler that does cross-module optimization might be able to optimize this. If, that is, you're linking against a static version of the runtime. Definitely not if you're linking against a dynamic version.

    So by converting the function to a static constant, in the belief that perhaps this is faster, you've actually made it slower.



    Here's the good news: C++0x introduces the constexpr keyword, which forces the compiler to evaluate simple functions at compile time if possible. Thus, the result becomes a proper compiler-time constant expression, and you get the best of both worlds.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by grumpy View Post
    C++ templates are specified as a compile-time, Turing-complete, meta-language ie the process of template expansion can be implemented completely and optimised at compile time. There is a pile of information freely available on such things; look up the topic of "Compile-time code optimization" - interestingly inlining of functions is one of the simplest metaprogramming techniques.
    As CornedBee says, return results are not constants. You can't use the return result as the size to declare an array, or as a value assigned to an enum etc. As such, I'd say Elysia was correct in that they really aren't useful in Template meta-programming. It's not an oversight though, as demonstrated, there just isn't a better way.

    It's not about what it could optimise, it's about what is or isn't legal C++. "Inlining of functions" in template meta-programming isn't about inlining a normal function, it's about writing a template meta-program to replace what would otherwise be a function call, to the point that there is no function call at all, both in the syntax of the entire meta-program itself and where it's used.
    E.g:
    Code:
    template <unsigned n, unsigned b>
    struct ceilLogb {
    	enum { ret = ceilLogb<(n+b-1)/b, b>::ret + 1 };
    }; 
    template <unsigned b>
    struct ceilLogb<1, b> {
      enum { ret = 0 };
    };
    
    int digits[ceilLogb<MYMAXVAL, 10>::ret];
    instead of the following, which of course cannot compile:
    Code:
    int digits[ceil(log10(MYMAXVAL))];
    constexpr sounds really cool, as it seems that it will finally enable actual function calling in template meta-programming, and presumably allow things like that second piece of code to compile!
    Last edited by iMalc; 06-21-2008 at 03:31 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    To a point. The restrictions on constexpr functions are pretty heavy. They must consist of a single return statement. They may not call themselves recursively.
    The latter really is trouble.

    However, constexpr has other uses too. For example, if you make a constructor constexpr, you can have a compile-time constant instance of the class. If you further make the getters of this class constexpr, the result will stilll be compile-time constant.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The first I can understand (maybe), but the second...? Why the heavy restrictions? To make it easier for compilers?
    So long as the function contains code that can be determined at compile time, it shouldn't be a problem, even if calls it recursively or return multiple things.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I think it was because they wanted a useful subset of full functionality that can be specified with sane language. If you have the feature of limited evaluation at compile time, then you have to specify in the standard how much "limited" is. If you don't, the feature is useless, because compilers will have different support, meaning that it's very hard to write portable code.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  2. Overflow and range checking for mul/div
    By Elysia in forum C++ Programming
    Replies: 28
    Last Post: 06-06-2008, 02:09 PM
  3. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  4. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  5. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM