在32位计算机上实现64位运算

Question

以下代码计算x和y的乘积,并将结果存储在内存中.数据类型ll_t被定义为等于long long.

typedef long long ll_t;
void store_prod(ll_t *dest, int x, ll_t y) {
    *dest = x*y;
}

gcc生成以下汇编代码实现计算:dest at%ebp + 8,x at%ebp + 12,y at%ebp + 16

1 movl 16(%ebp), %esi
2 movl 12(%ebp), %eax
3 movl %eax, %edx
4 sarl $31, %edx
5 movl 20(%ebp), %ecx
6 imull %eax, %ecx
7 movl %edx, %ebx
8 imull %esi, %ebx
9 addl %ebx, %ecx
10 mull %esi
11 leal (%ecx,%edx), %edx
12 movl 8(%ebp), %ecx
13 movl %eax, (%ecx)
14 movl %edx, 4(%ecx)

此代码使用三次乘法来实现在32位机器上实现64位算术所需的多精度算法.描述用于计算产品的算法,并注释汇编代码以显示它如何实现您的算法.

我不明白上面的汇编代码中的第8行和第9行.有人可以帮忙吗？

Answer 1

我把它转换成了intel语法.

mov esi, y_low
mov eax, x
mov edx, eax
sar edx, 31
mov ecx, y_high

imul ecx, eax ; ecx = y_high *{signed} x

mov ebx, edx

imul ebx, esi ; ebx = sign_extension(x) *{signed} y_low

add ecx, ebx ; ecx = y_high *{signed} x_low + x_high *{signed} y_low

mul esi ; edx:eax = x_low *{unsigned} y_low

lea edx, [ecx + edx] ; edx = high(x_low *{unsigned} y_low + y_high *{signed} x_low + x_high *{signed} y_low)

mov ecx, dest
mov [ecx], eax
mov [ecx + 4], edx

上面的代码所做的是乘以2个64位有符号整数,它们保留了产品中最不重要的64位.

其他64位被乘数来自哪里？它的x 符号扩展从32位扩展到64位.该sar指令用于将x's符号位复制到所有位edx.我将此值称为仅包含x's符号x_high.x_low是x实际传递给例程的值.

y_low并且y_high是最少的,最显著的部分y,只是喜欢x's x_low和x_high有.

从这里开始很简单:

product = y*{signed} x=
(y_high*2 ³² + y_low)*{signed}(x_high*2 ³² + x_low)=
y_high*{signed} x_high*2 ⁶⁴ +
y_high*{signed} x_low*2 ³² +
y_low*{signed} x_high*2 ³² +
y_low*{签}x_low

y_high*{signed} x_high*2 ⁶⁴未计算,因为它不会影响产品的最低64位.如果我们对完整的128位产品感兴趣(完整的96位产品用于挑剔),我们会计算它.

y_low*{signed} x_low使用无符号乘法计算.这样做是合法的,因为2的补码有符号乘法给出了与无符号乘法相同的最低有效位.示例:
-1*{signed} -1 = 1
0xFFFFFFFFFFFFFFFF*{unsigned} 0xFFFFFFFFFFFFFFFF = 0xFFFFFFFFFFFFFFFE0000000000000001(64个最低有效位相当于1)