在32位计算机上实现64位运算
以下代码计算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行。 有人可以帮忙吗?
我把它转换成了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 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
* {signed} 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)
考虑第8行和第9行的上下文。
此时, ESI
包含y
的下半部分, EBX
包含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
包含对以下操作非常有用的东西。 我只是把它移到需要去的地方。
imul所做的是将eax的内容与ecx相乘,并将ex中的低32位和edx中的高32位保存。
addl据我记得添加两个寄存器并将其保存在第一个寄存器上,所以在本例中为ebx。 (我不确定它是否会做任何其他事情并且在addl代表之后l)