News for hackers. Stuff that matters.
Re:Fast integer overflow detection (2012) by revelation on Sunday December 14, 2014 @02:16PM (#8749209)
(This article may need a [2012])

GCC 5 has builtin, efficient overflow checks:

https://gcc.gnu.org/gcc-5/changes.html

A new set of built-in functions for arithmetics with overflow checking has been added: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow and for compatibility with clang also other variants.

Re:Fast integer overflow detection (2012) by internetisthesh on Sunday December 14, 2014 @03:16PM (#8749400)
Anyone knows if something like this is available for C++ when using Visual Studio? I just started experiencing issues with this a few days ago when porting my application to x64. Would be nice if it was possible to enable something in debug mode so that an error is triggered if an overflow occur
Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @03:51PM (#8749513)
Look at valgrind?

Although I don't know if it works with VS.

Re:Fast integer overflow detection (2012) by dezgeg on Sunday December 14, 2014 @08:57PM (#8750359)
Valgrind doesn't do integer overflow checking. In general, it's not even possible to add such checks via binary translation, as on two's complement systems most unsigned and signed operations are compiled to the same machine instruction.
Re:Fast integer overflow detection (2012) by azakai on Sunday December 14, 2014 @04:21PM (#8749612)
Valgrind doesn't work on windows.
Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @02:38PM (#8749282)
...Which only helps you if you discard compatibility, unless I'm mistaken.

The question remains of how to detect overflow on add in portable C code.

Re:Fast integer overflow detection (2012) by forrestthewoods on Sunday December 14, 2014 @04:17PM (#8749595)
Detect on add? Not sure. Detect before add? Simple!

bool int_add_safe(int a, int b) { if (a >= 0 && b >= 0) return INT_MAX - a >= b; if (a < 0 && b < 0) return INT_MIN - a <= b; return true; }

If you ever have an instance that will result in an overflow you've got some kind of bug on your hand. Or at least some kind of circumstance that requires special handling. You don't want to overflow, not perform the add, or perform the add and discard the overflow. All three sucks and sweep a bug under the rug in some instance. Computers suck sometimes. :(

Re:Fast integer overflow detection (2012) by nly on Sunday December 14, 2014 @04:51PM (#8749688)
It's possible to simplify your code.

    bool int_add_safe(int a, int b) {
        if (b < 0) {
            return (a >= INT_MIN - b);
        } else {
            return (a <= INT_MAX - b);
        }
    }
Codegen comparison: http://goo.gl/Tgj7nu (If you switch to GCC it makes a mess of your version). You're right in that all portable solutions suck, but on x86 it will certainly be faster just to do the add and check the overflow flag.
Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @05:22PM (#8749783)
Neither of those two compile down to what I imagine would be the best on x86, namely an add and then a check of the overflow flag.

Is there any portable version that compiles down to that on GCC or Clang on x86?

Re:Fast integer overflow detection (2012) by acqq on Sunday December 14, 2014 @07:39PM (#8750158)
Once you have a function consistently used in your code the portable version can be used for the targets for which you don't provide an asm implementation, and the asm (or the solution customized to the compiler) can be selected implementation otherwise, covering the most common processors of today.
Re:Fast integer overflow detection (2012) by Someone on Sunday December 14, 2014 @07:56PM (#8750201)
Alternatively, bug the compiler writers to make their compiler recognise that portable version. That way, you don't have to maintain all those special code paths.

Getting the compiler writers to help you is easier if your project is significant, or if you use a portable version that a big open source project uses.

Re:Fast integer overflow detection (2012) by acqq on Sunday December 14, 2014 @08:05PM (#8750228)
My proposal costs the implementer just a few #if lines in one file. Your alternative costs much more people much more time, and the gain is then just... the implementer saves a few #ifs.
Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @08:10PM (#8750247)
By that logic most HLLs shouldn't have been made.

Remember - write once run many times. Implementing it in GCC / etc once means that many people won't have to do it themselves - especially as it's far more likely that one implementation will be bug-free than many people writing their own.

Re:Fast integer overflow detection (2012) by acqq on Sunday December 14, 2014 @08:45PM (#8750333)
It's not the feature that anybody would use as is, when you'd use it you'd prefer to call the function. But then what's behind the function is irrelevant for the users of the function. We don't force compiler authors to put in the compiler what can be nicely put in the libraries.

It's: write one header with a few #if's once, everybody use it, whenever she needs it.

You'd just call

    is_safe_to_add_ints( s, t[i] ) 
and be sure that on the common platform it's optimal thanks to the #if's in the header, and not write

    bool bsafe = (t[i] < 0) ? s >= INT_MIN - t[i] : s <= INT_MAX - t[i];
every time you'd want to check if the addition would be safe.
Re:Fast integer overflow detection (2012) by Someone on Monday December 15, 2014 @03:23AM (#8751094)
But you want

   if( !canSafelyAdd(a,b)) return ERROR;
   c = a + b;
To compile down to an add and a check of the overflow bit. For that, you need help from the compiler.

There are many examples where compilers special-case what is in a library. For example, compilers know they do not have to call strlen every time through this loop:

    for(int i = 0; i < strlen(s); ++i)
Re:Fast integer overflow detection (2012) by acqq on Monday December 15, 2014 @04:05AM (#8751185)
The enough help you need is, in the implementation of the library function #if X86 #if GCC etc and then the assembly for each case, otherwise the slow but standard implementation. And that's one file, the code never to be directly used but by function name. It's already done this way in the current libraries for a lot processor specific stuff.
Re:Fast integer overflow detection (2012) by acqq on Sunday December 14, 2014 @09:07PM (#8750385)
Nice, with the conditional operator and a single return it's even terser:

    bool is_safe_to_add_ints( int a, int b ) {
        return b < 0 
               ? a >= INT_MIN - b 
               : a <= INT_MAX - b;
    }
Re:Fast integer overflow detection (2012) by stormbrew on Sunday December 14, 2014 @03:21PM (#8749418)
Since the nature of overflow is basically completely undefined by the C standard the idea of detecting it with portable C code strikes me as an obvious oxymoron. You will have to sacrifice some kind of portability in order to detect it.
Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @03:48PM (#8749503)
You have two fundamental misunderstandings here.

First, you misunderstand what I - and the article - mean by detecting overflow. To put it another way - you have two integer values, A and B, and you want to know if A + B is representable in a given (signed) integer type. If neither A nor B are of the longest supported type, it's easy, but if A or B are of the longest supported (signed) integer type on the system, it's much harder. That's what this article is talking about.

Say, for example, you're doing the Pythonic approach of storing integers as either an integer or a pointer to a bigint. Well, if you have two non-bigints, you need to know if the result will fit in a native word or if you're going to have to make a bigint and do the slow path.

Second, detecting if an operation would cause undefined behavior is something you can indeed do in valid portable C code, for some operations at least. Among other things, that's exactly what checked access for an array does!

Re:Fast integer overflow detection (2012) by VLM on Sunday December 14, 2014 @05:13PM (#8749757)
"or if you're going to have to make a bigint and do the slow path."

You can cheat, sort of, and run your signedint code on a 64 bit processor and pretend you're running on a 63 bit processor and hit the slow path when you hit MAXINT for a 63 bit processor, not for a 64 bit processor. You can always add 63 bit signed ints on a 64 bit signed int capable processor.

Or maybe simpler explanation is there do exist 64 bit signed ints that can't be added and represented in a 64 bit signed register. But there do not exist any 32 bit signed ints that can't be added together and fit in a 64 bit register.

Its possible to play benchmarking games to make an unrealistic result that makes this look horrific. In reality under "normal" workloads it'll work just fine and the time you save by implementing artificially low limits on a slightly larger processor will save you a lot of debugging and writing and troubleshooting time.

"Well, yeah, this is a 64 bit proc, but to make life simpler we pretend its 1 sign bit and 62 int bits and anything bigger gets promoted to some arbitrary precision software library"

Another trick is not to use signed ints or at least minimize it, which is not as crazy as it may sound. If you can eliminate a whole class of arithmetic errors by changing program style...

Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @05:28PM (#8749799)
Generally you'll be doing this anyways (as you'll be storing it with a bit to tag if it is a pointer).

However, it is... interesting... that a language that is so low-level does not have any simple construct for doing this, especially seeing how trivial it is in x86 assembly (add the numbers, then check the overflow flag).

And saying "just don't used signed arithmetic" misses the point. If a "general-purpose" programming language cannot do something that is trivial in the next layer down, and that occurs as commonly as wanting to do something if there would be an overflow, I am inclined to blame the language, not the coder.

Re:Fast integer overflow detection (2012) by RaleyField on Sunday December 14, 2014 @05:59PM (#8749901)
> especially seeing how trivial it is in x86 assembly (add the numbers, then check the overflow flag)

I'm no expert, especially not on modern x86 processors or compilers for them, but I suspect it isn't so trivial as scattering such instructions may affects branch predictor tables and indirectly degrade performance in other parts of code.

Re:Fast integer overflow detection (2012) by TheLoneWolfling on Sunday December 14, 2014 @07:06PM (#8750059)
You require one branch regardless, and the trivial version is one branch, i.e. already at the minimum amount of branches.
Re:Fast integer overflow detection (2012) by nraynaud on Sunday December 14, 2014 @03:37PM (#8749479)
no, you can check your inflating operations before executing them.

But the idea that in 2014 this integer overflow detecting in C, is still a headline is frankly scary. We are all living a very fragile life.