어셈블리 : 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 비트 곱셈 (128 비트 결과를 얻기 위해 한 쌍의 64 비트 수 곱하기)이 아닙니다. 이것은 32 비트 곱셈입니다 (한 쌍의 32 비트 수를 곱하여 64 비트 결과를 얻습니다).

32 비트 80X86 단일 명령에 32 비트 승산을 지원한다. 기본적으로 MUL 명령어는 부호없는 32 비트 숫자 쌍을 곱하여 EDX에서 부호없는 64 비트 결과를 생성합니다. EAX; IMUL 명령어 ("one operand"버전)는 EDX : EAX에서 부호있는 64 비트 결과를 생성하기 위해 부호있는 32 비트 숫자 쌍을 곱합니다.

참고 IMUL의 "하나의 피연산자"버전은 제 묵시적 피연산자 EAX의 값을 사용한다.

기본적; 값 중 하나를 EAX에로드해야하고 IMUL (피연산자가 두 번째 값인 경우)을 사용하고 결과를 저장해야합니다.