Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Multiplication of two 64 bit integers on 32 bit processor

jakethecakejakethecake Member Posts: 2
Hi I want to write an x86 assembler function that multiplicates two 64 bit integers on a 32 bit processor. It has the following C signature:

[B]void llmultiply(unsigned long long int l1, unsigned long long int l2, unsigned char *result);[/B]

The result of l1 * l2 are to be but in an array pointed to by *result.

After:

[B]push ebp
mov ebp, esp[/B]

the stack looks like this:

[CODE]
| least significant byte of ebp | 0x3fffffe4 <---- ebp and stack pointer point here
| byte 1 of ebp | 0x3fffffe5
| byte 2 of ebp | 0x3fffffe6
| most significant byte of ebp | 0x3fffffe7
| least significant byte of return address (byte 0) | 0x3fffffe8 <--- the stack pointer points here after entering the function
| byte 1 of return address | 0x3fffffe9
| byte 2 of return address | 0x3fffffea
| most significant byte of return address (byte 3) | 0x3fffffeb
| least significant byte of parameter 1 (byte 0 of l1) | 0x3fffffec ---
| byte 1 of l1 | 0x3fffffed | here is A low
| byte 2 of l1 | 0x3fffffee |
| byte 3 of l1 | 0x3fffffef ---
| byte 4 of l1 | 0x3ffffff0 ---
| byte 5 of l1 | 0x3ffffff1 | here is A high
| byte 6 of l1 | 0x3ffffff2 |
| most significant byte of parameter 1 (byte 7 of l1) | 0x3ffffff3 ---
| least significant byte of parameter 2 (byte 0 of l2) | 0x3ffffff4 ---
| byte 1 of l2 | 0x3ffffff5 | here is B low
| byte 2 of l2 | 0x3ffffff6 |
| byte 3 of l2 | 0x3ffffff7 ---
| byte 4 of l2 | 0x3ffffff8 --- <---- [ebp + 20] points here
| byte 5 of l2 | 0x3ffffff9 | here is B high
| byte 6 of l2 | 0x3ffffffa |
| most significant byte of parameter 2 (byte 7 of l2) | 0x3ffffffb ---
| least significant byte of the address of the result array | 0x3ffffffc
| byte 1 of the address of the result array | 0x3ffffffd
| byte 2 of the address of the result array | 0x3ffffffe
| most significant byte of the address of the result array | 0x3fffffff <--- stack bottom
[/CODE]

The multiplication can be done like this:
[B]a * b = AH * BH * 2^64 + (AH * BL + AL * BH) * 2^32 + AL * BL.[/B]

Where H and L stands for high and low bits of a and b. The multiplication part is however not my biggest problem, I could solve that myself. What I'm having trouble with is putting the product in the result array so that it will be pointed to by the result pointer in:
[B]
void llmultiply(unsigned long long int l1, unsigned long long int l2, unsigned char *result);[/B]

So if someone could help me with that part atleast, some help on the multiplication part would also be welcome but not as important.

Comments

  • jakethecakejakethecake Member Posts: 2
    So this is what I've got now:

    [CODE]
    SECTION .data

    SECTION .text
    ALIGN 16
    BITS 32

    AL_OFF EQU 8 ; Offset from EBP to low bits of a (AL)
    AH_OFF EQU 12 ; Offset from EBP to high bits of a (AH)
    BL_OFF EQU 16 ; Offset from EBP to low bits of b (BL)
    BH_OFF EQU 20 ; Offset from EBP to high bits of b (BH)
    RES_OFF EQU 24 ; Offset from EBP to result array pointer

    GLOBAL llmultiply

    llmultiply:
    PUSH EBP
    MOV EBP, ESP

    PUSH EAX
    PUSH EBX
    PUSH ECX
    PUSH EDX
    PUSH EDI
    PUSH ESI

    MOV EAX, [EBP + AL_OFF]
    MOV EDX, [EBP + BL_OFF]
    MUL EDX ; AL * BL, EAX = low(AL * BL), EDX = high(AL * BL)

    MOV EDI, EAX ; Save low(AL * BL) in EDI
    MOV ESI, EDX ; Save high(AL * BL) in ESI

    MOV EAX, [EBP + AH_OFF]
    MOV EDX, [EBP + BL_OFF]
    MUL EDX ; AH * BL, EAX = low(AH * BL), EDX = high(AH * BL)

    ADD ESI, EAX ; Add low(AH * BL) to high(AL * BL)
    ADC ECX, EDX ; Add carry from the previous addition to high(AH * BL) and save in ECX

    MOV EAX, [EBP + AL_OFF]
    MOV EDX, [EBP + BH_OFF]
    MUL EDX ; AL * BH, EAX = low(AL * BH), EDX = high(AL * BH)

    ADD ESI, EAX ; Add low(AL * BH) to high(AL * BL) and low(AH * BL)
    ADC ECX, EDX ; Add carry from the previous addition and high(AL * BH) to high(AH * BL) and earlier carry, save in ECX

    MOV EAX, [EBP + AH_OFF]
    MOV EDX, [EBP + BH_OFF]
    MUL EDX ; AH * BH, EAX = low(AH * BH), EDX = high(AH * BH)

    ADD EAX, ECX ; Add high(AL * BH), high(AH * BL) and carry to low(AH * BH)
    ADC EDX, 0 ; Add carry from the previous addition to high(AH * BH)

    MOV EBX, [EBP + RES_OFF]
    MOV [EBX], EDI ; Put low 32 bit of result in array
    MOV [EBX + 4], ESI ; Put next 32 bit of result in array
    MOV [EBX + 8], EAX ; Put next 32 bit of result in array
    MOV [EBX + 12], EDX ; Put high 32 bit of result in array

    POP ESI
    POP EDI
    POP EDX
    POP ECX
    POP EBX
    POP EAX

    POP EBP ; restore EBP reg
    RET ; return
    [/CODE]

    It's almost working but there's a carry missing somewhere, for an example:

    FFFEFFFFFFFFFFFF * FFFF0001FFFFFFFF should be: FFFE0002FFFDFFFE0001FFFE00000001

    but I get:
    FFFE0001FFFDFFFE0001FFFE00000001

    So there should be another carry added to EDX.
Sign In or Register to comment.