Problems with Integer Overflow Math and Detection, pt 3:Easy overflow arithmetic, no assembly required.

Updated: Some nice profile results on GCC from Eric O'Laughlen. Full optimizations on I think is the important case.

Continued from Part 2. Inspired by this post from Google.

I think I'll do a full article on this shortly - covering the full range of mathematical operations, because this is fairly simple but important (for example). Oddly, most of the default answers seem to be 64-bit math (Microsoft and Linus/Linux) or assembly (everybody else). I'm not sure why - perhaps I'm missing something? But first, some performance results:

--------- Testing Addition
--------- Math requiring no overflow detection, but still testing for it
-------------------- This is for speed (overhead)
Test Simple........... total: 100000001 Time = 651.314 ms (1)
Test ASM Safe......... total: 100000001 Time = 1799.14 ms (2)
Test MS Safe.......... total: 100000001 Time = 1205.74 ms (3)
Test ASM SETTO Safe... total: 100000001 Time = 706.609 ms (4)
Test Sree C Safe...... total: 100000001 Time = 694.44 ms (5)

Key:
(1) is a+b, just for a baseline
(2) is the common Assembly solution I've seen a few places on the web
(3) is the Microsoft SafeInt class
(4) is the assembly recommended by Eric, following Mike
(5) is my C version (below)

The basic idea is really simple, and pretty obvious for the unsigned integer case, as everyone points out. If you add two positive numbers, and the result is smaller than either number, your addition overflowed.

It gets a little more complicated for the signed case, but not really THAT much more complicated. Basically, if you want to test if the result of an addition is supposed to be greater or less than a specific number, you only have to look at the sign of the OTHER number. That is, if you're testing if "a+b" overflowed, the unsigned test is "a is greater than c" and the signed test is "(a greater than c)!=(b less than zero)" (we can optimize that "b is less than zero" test, such that this becomes two compares and one jump).

So the code for my fast C version - you can plug it into the benchmark source I posted yourself:

__forceinline long __sreeSafeadd(long a, long b)
{
long c = a + b;
if ((a<=c)==(unsigned long(b)>>31))
SafeIntOnOverflow();

return c;
}

Its not what I might call "maximally" portable, in that it presumes two's-complement and basic processor oveflow arithmetic, but its basically as good as it gets (IMHO). It also uses one of my favored "mini-patterns" - using comparison as a computation value, as opposed to just as just a branch variable. This pattern extends fairly well to all the common overflow arithmetic math operations, amongst other things, though being a graphics guy, I really just want the stuff to clamp - I'm not sure that people are prepared to deal with integer overflow exceptions. I only used that in these examples because that's how the MS stuff worked that I started with as a benchmark for performance - I think exceptions are generally bad for most programmers and should not be used.

But what suprised me about all this, was (a) lack of "first order" information online, with real benchmarks, and, relatedly, (b) the assumptions folks tended to make about performance (particularly the "its Assembly so its faster"). This is a pretty basic simple (but important) thing, but the error propagation of information on the web was quite high - seems like people have just pushed around the same code and ideas from site to site, as opposed to actually investigating from first principles.

This assumption driven "error propagation" seems like a common problem that I'd hope at least technologists would be more immune from - not so much. I wish I saw more stuff like this for developers.