6 ms·
Fast integer overflow detection (2012)
- revelation 12y ago(This article may need a [2012]) GCC 5 has builtin, efficient overflow checks: https://gcc.gnu.org/gcc-5/changes.html 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.
- TheLoneWolfling 12y ago...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.
- stormbrew 12y agoSince 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.
- nraynaud 12y agono, 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.
- TheLoneWolfling 12y agoYou 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!
- VLM 12y ago"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...
- TheLoneWolfling 12y agoGenerally 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.
- RaleyField 12y ago> 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.
- forrestthewoods 12y agoDetect 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. :(
- nly 12y agoIt'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 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.
- TheLoneWolfling 12y agoNeither 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?
- acqq 12y agoOnce 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.
- Someone 12y agoAlternatively, 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.
- internetisthesh 12y agoAnyone 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
- TheLoneWolfling 12y agoLook at valgrind? Although I don't know if it works with VS.
- deleted 12y ago[deleted]
- UnoriginalGuy 12y agoIt seems like a lot of problems in C/C++ is caused by "this code might be removed duration optimisation." Makes the whole environment undefined. Why has nobody pushed for marking key sections of code with "don't optimise away" flags? In C# you have this: [MethodImplAttribute(MethodImplOptions.NoOptimization)] public static string GetCalendarName(Calendar cal) { return cal.ToString().Replace("System.Globalization.", ""). Replace("Calendar", ""); }
- TheLoneWolfling 12y ago(Most) things that are undefined behavior are so for a reason. In this case - you don't know if the system you're on even stores numbers as twos complement. And if it doesn't, it may not have the same behavior. So even the unoptimized version may fail.
- to3m 12y agoI think in most cases, people writing code to check for overflow do know whether the system they're on stores integers as twos complement, and they'll have a pretty good idea what will happen when overflow occurs. A portable approach for this sort of thing would be very useful, but in the mean time, perhaps we could settle for compilers that don't strip out reasonable code? I know, I know - I'm asking a lot. My favourite two links on the subject: http://blog.metaobject.com/2014/04/cc-osmartass.html http://blog.metaobject.com/2014/04/cc-osmartass.html, http://robertoconcerto.blogspot.co.uk/2010/10/strict-aliasing.html http://robertoconcerto.blogspot.co.uk/2010/10/strict-aliasin...
- heinrich5991 12y agoThe good thing is that this allows to optimize out in reasonable places too.
- Moral_ 12y agoIn gcc there are some pragmas you can use to to this: for instance `#pragma gcc optimize("O0")` should work. https://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/Function-Specific-Option-Pragmas.html https://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/Function-Specif... But the whole "this code might be removed during optimization" isn't exactly true. The compiler has to keep the meaning of your code the same. But once you introduce undefined behavior into the code, everything is meaningless from then on and gcc can do tons of wacky stuff.
- wfh 12y agoChromium has implmenented a safe numerics library for overflow detection - see: https://code.google.com/p/chromium/codesearch#chromium/src/base/numerics/&sq=package:chromium https://code.google.com/p/chromium/codesearch#chromium/src/b...
- danbruc 12y agoInteger overflow is really a strange problem - it is no problem at all on the assembly level but then we abstracted away the details in our higher level languages for convenience or what ever only to realize that we now regularly shoot our feet. It is nothing more than a language design mistake.
- sillysaurus3 12y agoHm? In Lisp or Python, you don't have overflow issues because ints can't overflow. It's only a problem at the assembly/low level. EDIT: The point of the parent comment is that integer overflow "isn't a problem at the assembly level, only in high level languages." But high level languages actually prevent the problem. You don't even have to worry about ints overflowing when you use Python or Lisp. You do have to worry if you're assembly or are using a lower level language like C. So the situation is actually opposite from what the parent comment describes.
- danbruc 12y agoArbitrary-precision arithmetic is probably not a general solution but it might indeed be worthwhile to consider using it more often and especially if performance is not a major concern.
- sillysaurus3 12y agoPerformance is not a major concern. Security and reliability trump performance considerations. In my experience, especially at large companies, unfounded "performance concerns" are the root of much evil. This isn't true all of the time. HFT and gamedev, for example. But gamedev only uses C++ because everyone else uses C++, and HFT often uses languages other than C/C++ from what I've heard. Though the performance-critical sections are usually transformed into C. Though as I write this, I think of Chromium and Firefox and realize that C++ was probably the correct choice for both. On the other hand, I hear Rust is making some pretty great strides in that context.
- 12y ago