Geek asks and answers

Implement 64-bit arithmetic on a 32-bit machine

The following code calculates the product of x and y and stores the result in memory. Data Type ll_t is defined as equivalent to long debt.

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

gcc generates the following assembly code that implements the calculation: dest with% ebp + 8, x at% ebp + 12, y with% 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)

This code uses three multiplications to implement multi-point arithmetic required to implement 64-bit arithmetic on a 32-bit machine. Describe the algorithm used to calculate the product and annotate the assembly code to show how it implements your algorithm.

I do not understand line 8 and line 9 in assembler above. Can anyone help?

+5
source share
3 answers

I 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

, , - 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)

+4

8 9.

ESI y EBX sgn(x). , 8 sgn(x) * (y % 2^32) EBX.

9 . 9, ECX , x * (y >> 32), . , EBX+ECX , , , .

;)

EDIT: ...

4: , SAR EDX, 31 (, , sar $31, %edx). EDX - 32- , . ? , .

7: EDX - . , .

+2

What imul does is multiply the contents of eax with ecx and store the lower 32 bits in eax and above 32 bits in edx.

addl, as far as I remember, adds two registers and saves them on the first, therefore in this case ebx. (I'm not sure if he is doing anything else, but l after adding a long time)

0
source

More articles:


All Articles