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. :(
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.Is there any portable version that compiles down to that on GCC or Clang on x86?
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.
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.
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. 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) bool is_safe_to_add_ints( int a, int b ) {
return b < 0
? a >= INT_MIN - b
: a <= INT_MAX - b;
}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!
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...
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.
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.
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.
The question remains of how to detect overflow on add in portable C code.