5

以下代码计算 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 行。任何人都可以帮忙吗?

4

3 回答 3

5

我已将其转换为 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 位被乘数从何而来?它从 32 位x 符号扩展为 64 位。该sar指令用于将x's符号位复制到edx. 我称这个值仅由x's符号组成x_highx_lowx实际传递到例程中的值。

y_lowy_high是 的最不重要和最重要的部分y,就像x's x_lowx_high是一样。

从这里开始很容易:

乘积 = y*{signed} x=
( y_high* 2 32 + y_low) *{signed} ( x_high* 2 32 + x_low) =
y_high*{signed} x_high* 2 64 +
y_high*{signed} x_low* 2 32 +
y_low*{signed} x_high* 2 32 +
y_low*{签}x_low

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

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

于 2012-07-27T03:54:30.997 回答
2

考虑第 8 行和第 9 行的上下文。

此时,ESI包含 的下半部分yEBX包含sgn(x)。所以第 8 行只是计算sgn(x) * (y % 2^32)并将其存储在EBX.

第 9 行利用了该结果。到第 9 行发生时,ECX包含乘法的部分上半部分,即有x * (y >> 32)符号。所以EBX+ECX最终是我们在最后一步计算的加上我们在前一行找到的部分上半部分。

完整的算法本身非常简洁;)

编辑:回应下面的评论......

第 4 行:考虑SAR EDX, 31(或者如果你喜欢,sar $31, %edx)真正的含义。由于EDX是 32 位寄存器,因此您最终会得到两个值之一。哪两个?考虑它们在有符号算术上下文中的含义。

第 7 行:EDX此时包含对以下操作非常有用的内容。我只是把它移到它需要去的地方。

于 2012-07-27T03:12:10.897 回答
0

imul 所做的是将 eax 的内容与 ecx 相乘,并将低 32 位保存在 eax 中,将高 32 位保存在 edx 中。

addl 据我记得添加了两个寄存器并将其保存在第一个寄存器中,因此在本例中为 ebx。(我不确定它是否还有其他作用,addl 之后的 l 代表很长时间)

于 2012-07-27T02:57:43.060 回答