Pages

October 3, 2006

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.

8 comments:

Anonymous said...

Sree, nice follow-up and clever approach. For those interested I ported the code to GNU and wrote a C version for comparison, here.

Sree Kotay said...

coolio! thanks for the discussion :)

Anonymous said...

if ((a<=c)==(unsigned long(b)>>31))

What does this exactly do ? please elaborate on that

Anonymous said...

Hi, I wrote a on how mine works. Well, how it is supposed to work :). Appreciate any comments, etc.

Sree Kotay said...

anonymous - sorry, I keep meaning to turn this into article but have NOT yet.

Basically, with :

if ((a<=c)==(unsigned long(b)>>31))

I'm testing to see if a is indeed less than or equal to c, and then, if it SHOULD be less than or equal to c.

That is, if b is negative, c (which a+b) should be less than a, otherwise, it should be greater (if b is positive)

make sense?

Anonymous said...

wow gold
world of warcraft gold
wow gold kaufen
wow geld
wow gold
world of warcraft gold
wow gold kaufen
wow geld
wow gold
world of warcraft gold
wow gold kaufen
wow geld
wow gold
world of warcraft gold
wow gold kaufen
wow geld
wow gold
world of warcraft gold
wow gold kaufen
wow geld
wow gold
world of warcraft gold
wow gold kaufen
wow geld
wow gold
world of warcraft gold
wow gold kaufen
wow geld

Anonymous said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,情人歡愉用品,情惑用品性哥,情人用品性哥,情趣用品,AIO交友愛情館,情人歡愉用品,美女視訊,情色交友,情人用品性哥,視訊交友,辣妹視訊,美女交友,性愛,嘟嘟成人網,按摩棒,震動按摩棒,微調按摩棒,情趣按摩棒,逼真按摩棒,G點,跳蛋,跳蛋,跳蛋,性感內衣,飛機杯,充氣娃娃,情趣娃娃,角色扮演,性感睡衣,後庭區,SM,潤滑液,情趣禮物,威而柔,香水,精油,芳香精油,自慰,自慰套,性感吊帶襪,情趣用品加盟,情人節禮物,情人節,吊帶襪,辣妹視訊,美女交友,情色交友,成人交友,視訊聊天室,美女視訊,視訊美女,情色視訊,免費視訊聊天,視訊交友,視訊聊天,AIO交友愛情館,嘟嘟成人網,成人貼圖,成人網站,AIO交友愛情館,情色,情色貼圖,情色文學,情色交友,色情聊天室,色情小說,七夕情人節,色情,A片,A片下載,免費A片,免費A片下載,情色視訊,情色電影,色情網站,辣妹視訊,視訊聊天室,情色視訊,免費視訊聊天,視訊聊天,美女視訊,視訊美女,美女交友,美女,情色交友,成人交友,自拍,本土自拍,情人視訊網,視訊交友90739,生日禮物,情色論壇,正妹牆,正妹,成人網站,A片,免費A片,A片下載,免費A片下載,AV女優,成人影片

Anonymous said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,按摩棒,跳蛋,充氣娃娃,免費A片,AV女優,美女視訊,情色交友,免費AV,色情網站,辣妹視訊,美女交友,色情影片,成人影片,成人網站,A片,H漫,18成人,成人圖片,成人漫畫,情色網,日本A片,免費A片下載,性愛,A片,色情,成人,做愛,情色文學,A片下載,色情遊戲,色情影片,色情聊天室,情色電影,免費視訊,免費視訊聊天,免費視訊聊天室,一葉情貼圖片區,情色,情色視訊,免費成人影片,視訊交友,視訊聊天,視訊聊天室,言情小說,愛情小說,AIO,AV片,A漫,av dvd,聊天室,自拍,情色論壇,視訊美女,AV成人網,色情A片,情趣用品,A片,免費A片,AV女優,美女視訊,情色交友,色情網站,免費AV,辣妹視訊,美女交友,色情影片,成人網站,H漫,18成人,成人圖片,成人漫畫,成人影片,情色網,sex,情趣用品,A片,免費A片,日本A片,A片下載,線上A片,成人電影,嘟嘟成人網,成人,成人貼圖,成人交友,成人圖片,18成人,成人小說,成人圖片區,微風成人區,成人文章,成人影城,情色,情色貼圖,色情聊天室,情色視訊,情色文學,色情小說,情色小說,臺灣情色網,色情,情色電影,色情遊戲,嘟嘟情人色網,麗的色遊戲,情色論壇,色情網站,一葉情貼圖片區,做愛,性愛,美女視訊,辣妹視訊,視訊聊天室,視訊交友網,免費視訊聊天,美女交友,做愛影片,情境坊歡愉用品,情趣用品,情人節禮物,情惑用品性易購,av,情趣用品,a片,成人電影,微風成人,嘟嘟成人網,成人,成人貼圖,成人交友,成人圖片,18成人,成人小說,成人圖片區,成人文章,成人影城,愛情公寓,情色,情色貼圖,色情聊天室,情色視訊,情色文學,色情小說,情色小說,色情,寄情築園小遊戲,情色電影,aio,av女優,AV,免費A片,日本a片,美女視訊,辣妹視訊,聊天室,美女交友,成人光碟