大會：與32位寄存器的64位乘法

Question

我有一個關於在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) 

Answer 1

下面是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) 

而且你還可以檢查此implement 64-bit arithmetic on a 32-bit machine

Answer 2

這不是64位乘法（乘以一對64位數以獲得128位結果）。這是32位乘法（將一對32位數乘以得到64位結果）。

32位80x86支持32位乘法和單一指令。基本上，MUL指令將一對無符號的32位數乘以在EDX：EAX中產生無符號的64位結果;和IMUL指令的（「一個操作數」版本）乘以一對帶符號的32位數字，以在EDX：EAX中產生帶符號的64位結果。

注意：IMUL的「一個操作數」版本使用EAX中的值作爲隱含的第二個操作數。

基本上;您需要將其中一個值加載到EAX中，使用IMUL一次（操作數是第二個值），然後存儲結果。