2

我有一个关于 64 位乘法的 x86 汇编中的实现的问题。据我所知，我已经发布了代码。我不知道其余的做了什么（我可能在我已经做过的事情上犯了错误）。任何方向将不胜感激。

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)
4

2 回答 2

2

下面是64位乘法的算法：

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)

你也可以在 32 位机器上检查这个实现 64 位算术

于 2014-06-16T07:50:18.300 回答
1

这不是 64 位乘法（将一对 64 位数字相乘得到 128 位结果）。这是 32 位乘法（将一对 32 位数字相乘得到 64 位结果）。

32 位 80x86 支持单条指令的 32 位乘法。基本上，该MUL指令将一对无符号 32 位数字相乘以在 EDX:EAX 中生成无符号 64 位结果；并且（“一个操作数”版本）该IMUL指令将一对带符号的 32 位数字相乘以在 EDX:EAX 中生成带符号的 64 位结果。

注意：“一个操作数”版本IMUL使用 EAX 中的值作为隐含的第二个操作数。

基本上; 您需要将其中一个值加载到 EAX 中，使用IMUL一次（其中操作数是第二个值），然后存储结果。

于 2013-10-26T03:06:42.813 回答