2

I have a question regarding an implementation in x86 assembly of 64 bit multiplication. I've posted the code with as far as I was able to get in understanding it. I'm at a loss as to what the rest does (and it's possible I have made errors in what I've already done). Any direction would be appreciated.

dest at %ebp+8
x    at %ebp+12
y    at %ebp+16

movl        16(%ebp), %esi      //Move y into %esi
movl        12(%ebp), %eax      //Move x into %eax
movl        %eax, %edx          //Move x into %edx
sarl        $31, %edx            //Shift x right 31 bits (only sign bit remains)
movl        20(%ebp), %ecx      //Move the low order bits of y into %ecx
imull       %eax, %ecx          //Multiply the contents of %ecx (low order bits of y) by x
movl        %edx, %ebx          //Copy sign bit of x to ebx
imull       %esi, %ebx          //Multiply sign bit of x in ebx by high order bits of y
addl        %ebx, %ecx          //Add the signed upper order bits of y to the lower order bits (What happens when this overflows?)
mull        %esi                //Multiply the contents of eax (x) by y
leal        (%ecx,%edx), %edx           
movl        8(%ebp), %ecx
movl        %eax, (%ecx)
movl        %edx, 4(%ecx)
Taylor Hill
  • 1,053
  • 1
  • 14
  • 24
  • Multiplying 2 32-bit values doesn't really count as 64-bit multiplication. And how does moving the long at 20(%ebp) move any bits of y, unless y is a 64-bit value, but then you don't have a 64-bit location for the result (dest is only 32 bits), unless its supposed to overwrite x... – Scott Hunter Oct 26 '13 at 01:41
  • 1
    This multiplies a signed 32-bit integer with a signed 64-bit integer, producing a signed 64-big result. Just work it out on paper in base 2^32. – Raymond Chen Oct 26 '13 at 02:38
  • BTW, *unsigned* 32x64 multiplication only needs `imul` + `mul` and 2 adds (https://godbolt.org/g/VC6i9T): the upper half of the 32-bit input is zero, not 0 or -1, so the `x_h * y_h` term disappears. (And BTW, gcc could have done a better job here, with cmov / sub instead of actually multiplying by the upper half of x. And it could have generated it with `cdq`.) Actual 64x64 multiplication takes fewer instructions (no sign-extending the upper half). – Peter Cordes Jun 13 '18 at 07:15

2 Answers2

2

Below is the algorithm of 64-bit multiplication:

x, y: 64-bit integer
x_h/x_l: higher/lower 32 bits of x
y_h/y_l: higher/lower 32 bits of y

x*y  = ((x_h*2^32 + x_l)*(y_h*2^32 + y_l)) mod 2^64
     = (x_h*y_h*2^64 + x_l*y_l + x_h*y_l*2^32 + x_l*y_h*2^32) mod 2^64
     = x_l*y_l + (x_h*y_l + x_l*y_h)*2^32

Now from the equation you can see that only 3(not 4) multiplication needed.

 movl 16(%ebp), %esi    ; get y_l
 movl 12(%ebp), %eax    ; get x_l
 movl %eax, %edx
 sarl $31, %edx         ; get x_h, (x >>a 31), higher 32 bits of sign-extension of x
 movl 20(%ebp), %ecx    ; get y_h
 imull %eax, %ecx       ; compute s: x_l*y_h
 movl %edx, %ebx
 imull %esi, %ebx       ; compute t: x_h*y_l
 addl %ebx, %ecx        ; compute s + t
 mull %esi              ; compute u: x_l*y_l
 leal (%ecx,%edx), %edx ; u_h += (s + t), result is u
 movl 8(%ebp), %ecx
 movl %eax, (%ecx)
 movl %edx, 4(%ecx)

And you can also check this implement 64-bit arithmetic on a 32-bit machine

Community
  • 1
  • 1
WilhelmJung
  • 56
  • 6
  • `movl %eax, %edx ; sarl $31, %edx` does the same thing as `cltd` (aka Intel-syntax `cdq`), sign-extending EAX into EDX:EAX. But your code then copies it to EBX, never using the value in EDX, so you might as well have just sign-extended into EBX:EAX in the first palce. – Peter Cordes Jun 05 '23 at 20:15
  • Also note, this is producing a 64-bit product, not a full 64x64 => 128-bit widening multiply. (In that case you do need all four multiplies, and the cross products need to be widening. And that means doing `unsigned low x signed high` somehow, since there isn't an instruction for that. The high half of a widening multiply does depend on the interpretation of the MSB as `+2^(n-1)` or `-2^(n-1)`. One strategy might be to take absolute values of inputs beforehand, then apply the sign, like neg/sbb/sbb/sbb if the input signs differ (if `x_h^y_h` sets SF). – Peter Cordes Jun 05 '23 at 20:21
1

This is not 64-bit multiplication (multiplying a pair of 64-bit numbers to get a 128-bit result). This is 32-bit multiplication (multiplying a pair of 32-bit numbers to get a 64-bit result).

32-bit 80x86 supports 32-bit multiplication with a single instruction. Basically, the MUL instruction multiplies a pair of unsigned 32-bit numbers to produce an unsigned 64-bit result in EDX:EAX; and (the "one operand" version of) the IMUL instruction multiplies a pair of signed 32-bit numbers to produce a signed 64-bit result in EDX:EAX.

Note: The "one operand" version of IMUL uses the value in EAX as an implied second operand.

Basically; you need to load one of the values into EAX, use IMUL once (where the operand is the second value), then store the result.

Brendan
  • 35,656
  • 2
  • 39
  • 66
  • 1
    This is 32x64, not 32x32. If it were 32x32 there would be only one multiplication instruction, but this sequence has three. – Raymond Chen Oct 26 '13 at 06:28