Mailman 3 OT: abs(x) with 4 assembly insns - pypy-dev

Sept. 29, 2003

      Hi friends,

today, Armin presented me a simple brain-teaser:

You have X86 assembly, you have only 4 insns,
and you don't want to use a jump.
You have a register, loaded with a value, and
you should produce its abs, in another register,
while preserving the argument register.

Hmm. 4 insns.

Here is the standard C solution for doing abs without a jump,
whioch you can find on the internet:

int int_abs(int a) {
     return a - ((a+a) & (a>>31));
}

This clearly computes the bas, quite nicely.
The resulting assembly code looks like so:

; 2    :     return a - ((a+a) & (a>>31));

   00000	8b 44 24 04	 mov	 eax, DWORD PTR _a$[esp-4]
   00004	8b c8		 mov	 ecx, eax
   00006	c1 f9 1f	 sar	 ecx, 31			; 0000001fH
   00009	8d 14 00	 lea	 edx, DWORD PTR [eax+eax]
   0000c	23 ca		 and	 ecx, edx
   0000e	2b c1		 sub	 eax, ecx

; 3    : }

This is clearly some solution. But, ignoring the first insn,
which is just moving the argument, this really takes
five instructions, one too much of course.

Actually, there is a much better solution.
X86 has the cdq insn, which does a sign extension from
32 bit signed eax to 64 bit signed edx/eax.

This in fact puts a -1 into edx, whenever the eax is negative,
or a 0, if eax is >= 0.

Now, what is taking the abs() of a value? Right, it is a two's
complement, if the argument is negative, or a do-nothing if
it is not negative.
And the name 'two's complement' comes from the fact
that you need to do two operations for the complement:
First, take the NOT of the value, then add one.

So, here comes the trick:
NOT is equivalent to XORing with -1.
ADD 1 is the same as SUB -1.

Fortunately, this can all be carried out with the result of
the CDQ sign extension, since we got the -1 from it:

Do the CDQ.
Load eax into another register
XOR it with edx   (which is either 0 or -1)
SUB edx from it   (which is either adding one or zero)

So, here the solution(TM):

int other_abs(int a) {
     __asm {
         mov eax, a;
         /* from here... */
         cdq;
         mov ebx, eax;
         xor ebx, edx;
         sub ebx, edx;
         /*... to here*/
         xchg eax, ebx;
     }
}

The meat of the program is exactly four insns, the rest
is just needed to make the C calling conventions happy.

Here the full program, you can step through it with a
debugger, to see that it really works:

int int_abs(int a) {
     return a - ((a+a) & (a>>31));
}

int other_abs(int a) {
     __asm {
         mov eax, a;                /* C: load arg */
         /* from here... */
         cdq;                       /* 1: edx has either 0 or -1 */
         mov ebx, eax;              /* 2: get a copy */
         xor ebx, edx;              /* 3: either identity, or NOT */
         sub ebx, edx;              /* 4: either add 0, or 1 */
         /* ... to here */
         xchg eax, ebx;             /* C: store result */
     }
}

int main(int argc, char **argv) {
     int a;
     a = int_abs(5);
     a = int_abs(-5);
     a = other_abs(5);
     a = other_abs(-5);
     return 0;
}

Hoping-that-everybody-trusts-me-now-that-I-can-write-a-small-OS
     -- ly y'rs - chris

-- 
Christian Tismer             :^)   <mailto:tismer@tismer.com>
Mission Impossible 5oftware  :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34  home +49 30 802 86 56  mobile +49 173 24 18 776
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/

OT: abs(x) with 4 assembly insns

Christian Tismer

Bob Ippolito

Michael Hudson

Bob Ippolito

Michael Hudson

Bob Ippolito

Michael Hudson

Robin Becker

Christian Tismer

Bob Ippolito

Bob Ippolito

Michael Hudson

Bob Ippolito

Michael Hudson

Bob Ippolito

Michael Hudson

Robin Becker

Christian Tismer

Bob Ippolito

tags

participants (4)