实现一个32位计算机上的64位运算 [英] implement 64-bit arithmetic on a 32-bit machine
问题描述
以下code计算x和y的乘积,并将结果存储在存储器中。数据
类型ll_t被定义为等同于很长很长。
The following code computes the product of x and y and stores the result in memory. Data type ll_t is defined to be equivalent to long long.
typedef long long ll_t;
void store_prod(ll_t *dest, int x, ll_t y) {
*dest = x*y;
}
GCC生成以下组装code实现的计算:
DEST在的%ebp + 8,X在的%ebp + 12,Y处的%ebp + 16
gcc generates the following assembly code implementing the computation: 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)
这code使用三个乘法来实现多precision算术
实现的32位机器上的64位算术必需的。描述
算法用于计算产品和注释组装code,显示
它是如何实现你的算法。
This code uses three multiplications to implement the multiprecision arithmetic required to implement 64-bit arithmetic on a 32-bit machine. Describe the algorithm used to compute the product, and annotate the assembly code to show how it realizes your algorithm.
我不明白,在组装$ C $上面C线8和9号线。谁能帮助?的
I don't understand line 8 and line 9 in assembly code above. Can anyone help?
推荐答案
我已经转换它为Intel语法。
I've converted it to intel syntax.
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
在什么上面的code确实是2的64位有符号整数乘法,保持产品的最低显著64位。
What the above code does is multiplication of 2 64-bit signed integers that keeps the least-significant 64 bits of the product.
在哪里其他64位的被乘数从何而来?这是 X
的符号扩展的从32位到64 特区
指令用于复制 X的
符号位为 EDX
的所有位。我把这个值只包含了 X的
标志 x_high
。 x_low
是 X
实际传递到程序。
Where does the other 64-bit multiplicand come from? It's x
sign-extended from 32 bits to 64. The sar
instruction is used to replicate x's
sign bit into all bits of edx
. I call this value consisting only of the x's
sign x_high
. x_low
is the value of x
actually passed into the routine.
y_low
和 y_high
是 y的最小,最显著的部分
,就像 X的
x_low
和 x_high
是。
从这里,它是pretty容易:
From here it's pretty easy:
产品= 是
* {}签署 X
=结果
( y_high
* 2 32 + y_low
)* {签署}( x_high
* 2 32 + x_low
)=结果 y_high
* {}签署 x_high
* 2 64 +结果 y_high
* {}签署 x_low
* 2 32 +结果 y_low
* {}签署 x_high
* 2 32 +结果 y_low
* {}签署 x_low
product = y
*{signed} x
=
(y_high
* 232 + y_low
) *{signed} (x_high
* 232 + x_low
) =
y_high
*{signed} x_high
* 264 +
y_high
*{signed} x_low
* 232 +
y_low
*{signed} x_high
* 232 +
y_low
*{signed} x_low
y_high
* {}签署 x_high
* 2 64 不计算,因为它无助于产品的至少显著64位。我们会计算它,如果我们有兴趣在全128位的产品(对于挑剔的全96位产品)。
y_high
*{signed} x_high
* 264 isn't calculated because it doesn't contribute to the least significant 64 bits of the product. We'd calculate it if we were interested in the full 128-bit product (full 96-bit product for the picky).
y_low
* {}签署 x_low
使用无符号乘法计算。这是合法的,这样做是因为2的补符号乘法给出了相同的至少显著位作为无符号乘法。例如:结果
-1 * {}签署-1 = 1结果
0xFFFFFFFFFFFFFFFF * {无符号} 0xFFFFFFFFFFFFFFFF = 0xFFFFFFFFFFFFFFFE0000000000000001(64至少显著位是相当于1)
y_low
*{signed} x_low
is calculated using unsigned multiplication. It's legal to do so because 2's complement signed multiplication gives the same least significant bits as unsigned multiplication. Example:
-1 *{signed} -1 = 1
0xFFFFFFFFFFFFFFFF *{unsigned} 0xFFFFFFFFFFFFFFFF = 0xFFFFFFFFFFFFFFFE0000000000000001 (64 least significant bits are equivalent to 1)
这篇关于实现一个32位计算机上的64位运算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!