Abstract:
Branchless abs function for x86 processors.

Created by Peter Kankowski
Last changed
Filed under Low-level code optimization

Share on social sitesReddit Digg Delicious Buzz Facebook Twitter

Optimized abs function

Microsoft's algorithm

Microsoft Visual C++ 2005 generates the following code for integer abs function:

cdq           ; if eax >= 0 then edx := 0
              ;             else edx := 0xFFFFFFFF

xor eax, edx  ; if eax >= 0 then eax := eax xor 0 = eax 
              ;             else eax := eax xor 0xFFFFFFFF = not eax

sub eax, edx  ; if eax >= 0 then eax := eax xor 0 - 0 = eax 
              ;             else eax := (eax xor -1) - (-1) = not eax + 1 = -eax

The first instruction, CDQ, copies the sign bit from eax register to edx. So, if eax was negative, edx will be –1 (0xFFFFFFFF); otherwise, it will be zero.

When one operand of XOR is zero, it returns another operand. Also, XORing something with –1 is equivalent to bitwise NOT:

A ⊕ 0 = A

A ⊕ –1 = ¬A, where –1 is a register with all bits set to 1

(You can verify these formulas with the truth table for XOR).

The last instruction substracts edx from eax. If eax is positive, edx is 0, and the instruction doesn't change the number. But when eax < 0, it adds 1 to it, effectively computing –eax:

¬A + 1 = –A

This clever trick helps to avoid a conditional jump, which can cost you a dozen of cycles if it will be mispredicted. The code also demonstrates a smart choice of instructions: CDQ is fast on all processors, while the equivalent shift (SAR eax, 31) is slow on Pentium IV.

However, the author of Bit Twiddling Hacks mention that the algorithm was patented by some Russian guy working at Sun. If you a lawyer specialized in US patent law, please comment whether Microsoft's use of the abs function violates the Sun's patent.

Alternative algorithm

Here is an alternative to Microsoft's method:

cdq
add eax, edx
xor eax, edx

Or, in C language:

int my_abs(int a) {
   int mask = (a >> (sizeof(int) * CHAR_BIT - 1));
   return (a + mask) ^ mask;
}

Explaining why it works is left as an exercise to reader. Here is a hint for you:

¬(A – 1) = –A

Legal note. This wiki page does not claim that any of the algorithms is free from the power of Sun's patent. You should consult with your lawyer before using the code in compilers or code generators.

Peter Kankowski
Peter Kankowski

About the author

Peter lives in Siberia, the land of sleeping sun, beautiful mountains, and infinitely deep snow. He likes to program in C with a bit of C++, also in x86 assembly language, Python, and PHP (on Windows platform). He can be reached at kankowski@narod.ru.

11 comments

Ten recent comments are shown below. Show all comments

Bit Twiddling Hacks &laquo; Tekquestions&#8217;s Weblog,
[...] Internet Archive also has an old link to it. On January 30, 2007, Peter Kankowski shared with me an abs version he discovered that was inspired by Microsoft’s Visual C++ compiler output. It is featured [...]
jo,

OMG, you could actually patent 3 lines of code. Don't you think this violates people right to explore something and find/create/whatever it accidentally. You CAN'T patent algorithm, there is a huge distinction between method and algorithm. Sun is being silly.

Sergey,
This patent is mistake, becouse this method "optimised abs" was used many years ago in assembler programs on non IBM PC i386 platform (ZX Spectrum,Amiga). And this method was steal.
Faisal Amin,
Thats why I hate big corporations. Very soon we will have to buy air to breath.
sparrowhawk,

god thanks i live outside US, where no software pattents restrict

Sirmabus,

I don't see how it would be a valid patent, and probably easy busted if challenged.

I remember seeing this trick before 1997.

As a matter of a fact I know someone that had it as an answer on their programmers test even.

Although I don't think to many people knew it, and had to be told the answer. This was the early

90's mind you when the internet was just taking off..

Sad,

Unbelievable. I say, screw all software patents and develop your algorithms anyway you like. If you didn't copy/paste, dont worry about being sued. Like really, if this holds up in court, lose your hope for humanity and retaliate. If Sun/Microsofts lawyers showed up at my doorstep to inform me that my binary stories have used sentences in thier clients binary stories, and their clients want to sue me if I continue selling/distrbuting my stories, things would get physical... for the lawyers and for the clients. All programmers should have this mentality and if you don't..then your not a programmer, your a bitch. Its not like the users of your app give two shits about how the features are coded, I say that companies who own patents for code are scared and weak, unable to produce good applications and limit the programmers imagination. And any programmer wishing to patent a piece of code, you need a pschological evaluation and possibly a beat down.

Kent Johansen,

I think I want a patent of adding 5 to things I like, if this is still valid.

Oops,

I think there may be a typo (or two) in the comments in the first block of assembly.

For the second and third assembly instructions, I think it should be "eax :=" on the second comment line, instead of "edx :="

Besides that, the really did help me understand the use of cdq.

Peter Kankowski,
Thank you very much, I corrected the typos.
Your name:
Comment:

Please ignore this field: