#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2009
    Posts
    10
    Rep Power
    0

    X86 Assembly multiplication of two 64 bit integers on a 32 bit processor


    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:

    void llmultiply(unsigned long long int l1, unsigned long long int l2, unsigned char *result);

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

    After:

    push ebp
    mov ebp, esp


    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
    The multiplication can be done like this:
    a * b = AH * BH * 2^64 + (AH * BL + AL * BH) * 2^32 + AL * BL.

    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:

    void llmultiply(unsigned long long int l1, unsigned long long int l2, unsigned char *result);


    So if someone could help me with that part atleast, some help on the multiplication part would also be welcome but not as important.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    I don't understand where you're stuck. Reading/Writing to an array is just "mov" with a memory location as an operand. Something like (assuming the pointer is in ESI):

    Code:
    mov [esi], ecx
    You can also use a few simple expressions inside the address so you don't need to compute the address of each element yourself.

    Code:
    mov [esi+4], ecx
    mov [esi+eax], ecx
    mov [esi+4*eax], ecx
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2009
    Posts
    10
    Rep Power
    0
    Yeah I know but I need to get the adress of the result array at [ebp + 24] and then I think I have to bit shift that address to the top of the stack or something, and then put the product from the multiplication at that address. But I'm not getting the unsigned char *result to point at what I want it to point at.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    No bit shifting involved. Just move the pointer from the stack to a register, then move the data to that memory location.

    If you're still stuck, it would be helpful to see what you're trying. Can you write & post code to zero to first couple elements of result.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2009
    Posts
    10
    Rep Power
    0
    I tried this, no multiplication here just trying to put something in the array:

    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
    
    	MOV EAX, [EBP + AL_OFF]	
    	MOV EBX, [EBP + AH_OFF]
    	MOV ECX, [EBP + BL_OFF]
    	MOV EDX, [EBP + BH_OFF]
    
    	MOV [EBP + RES_OFF], EAX
    	MOV [EBP + RES_OFF + 4], EBX
    	MOV [EBP + RES_OFF + 8], ECX
    	MOV [EBP + RES_OFF + 12], EDX	
    
    	POP EBP
    	RET
    I put low bits of l1 inte EAX, high bits of l1 into EBX, low bits of l2 into ECX and high bits of l2 into EDX. This works fine. Then I tried putting that into the array adresses but *result points to something else.

    void llmultiply(unsigned long long int l1, unsigned long long int l2, unsigned char *result);
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    [EBP+RES_OFF] is the pointer result, not an element of the result array (similarly, [EBP+RES_OFF+4] is [EBP+28] which is somewhere in the calling routines local variables, not anything to do with result).

    What you want to do is get the [EBP+RES_OFF] (i.e. the pointer "result"), store it in a register and then use that register for a memory access (giving you *result).
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2009
    Posts
    10
    Rep Power
    0
    Thanks. Solved this problem by doing this:

    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
    
    	MOV EAX, [EBP + AL_OFF]	
    	MOV EBX, [EBP + AH_OFF]
    	MOV ECX, [EBP + BL_OFF]
    
    	MOV EDX, [EBP + RES_OFF]
    	MOV [EDX], EAX
    	MOV [EDX + 4], EBX
    	MOV [EDX + 8], ECX
    
    	MOV EAX, [EBP + BH_OFF]
            MOV [EDX + 12], EAX
    
    	POP EBP
    	RET
    Still wondering about that thing about bitshifting the result array though. This guy did the same thing I'm trying to do, why is he using SHL on the array addresses?

    http://www.gidforums.com/t-18041.html
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    Bizarre, it looks like he's loading the address byte by byte rather than a single DWORD move. I'm surprised it works at all without an explicit BYTE PTR on those add instructions.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2009
    Posts
    10
    Rep Power
    0
    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
    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.

IMN logo majestic logo threadwatch logo seochat tools logo