12

How would I go about...

  • multiplying two 64-bit numbers

  • multiplying two 16-digit hexadecimal numbers

...using Assembly Language.

I'm only allowed to use registers %eax, %ebx, %ecx, %edx, and the stack.

EDIT: Oh, I'm using ATT Syntax on the x86
EDIT2: Not allowed to decompile into assembly...

4

11 Answers 11

16

Use what should probably be your course textbook, Randall Hyde's "The Art of Assembly Language".

See 4.2.4 - Extended Precision Multiplication

Although an 8x8, 16x16, or 32x32 multiply is usually sufficient, there are times when you may want to multiply larger values together. You will use the x86 single operand MUL and IMUL instructions for extended precision multiplication ..

Probably the most important thing to remember when performing an extended precision multiplication is that you must also perform a multiple precision addition at the same time. Adding up all the partial products requires several additions that will produce the result. The following listing demonstrates the proper way to multiply two 64 bit values on a 32 bit processor ..

(See the link for full assembly listing and illustrations.)

0
4

If this was 64x86,

function(x, y, *lower, *higher)
movq %rx,%rax     #Store x into %rax
mulq %y           #multiplies %y to %rax
#mulq stores high and low values into rax and rdx.
movq %rax,(%r8)   #Move low into &lower
movq %rdx,(%r9)   #Move high answer into &higher
1
  • the question is about x86, not x86-64 which is obviously too easy since nothing special needs to be done
    – phuclv
    Mar 23, 2019 at 17:11
3

Since you're on x86 you need 4 mull instructions. Split the 64bit quantities into two 32bit words and multiply the low words to the lowest and 2nd lowest word of the result, then both pairs of low and high word from different numbers (they go to the 2nd and 3rd lowest word of the result) and finally both high words into the 2 highest words of the result. Add them all together not forgetting to deal with carry. You didn't specify the memory layout of the inputs and outputs so it's impossible to write sample code.

2
  • 2
    I think the high*high part is unneeded as it overflows no matter what
    – BCS
    Sep 17, 2008 at 21:33
  • 1
    @BCS: Correct, the high x high part is only needed if you want a 64x64 => 128-bit full multiply (example with SSE2). The two halves of h x h line up with the top two chunks of the 128-bit full product, fully outside the input-width result. godbolt.org/z/GWT86f78c shows GCC -O3 -m32 output for a non-widening uint64_t product on 32-bit x86, using two non-widening 32-bit imul for the cross products, and one widening mul for the low x low, with no adc needed. Jun 25, 2021 at 4:47
2

This code assumes you want x86 (not x64 code), that you probably only want a 64 bit product, and that you don't care about overflow or signed numbers. (A signed version is similar).

MUL64_MEMORY:
     mov edi, val1high
     mov esi, val1low
     mov ecx, val2high
     mov ebx, val2low
MUL64_EDIESI_ECXEBX:
     mov eax, edi
     mul ebx
     xch eax, ebx  ; partial product top 32 bits
     mul esi
     xch esi, eax ; partial product lower 32 bits
     add ebx, edx
     mul ecx
     add ebx, eax  ; final upper 32 bits
; answer here in EBX:ESI

This doesn't honor the exact register constraints of OP, but the result fits entirely in the registers offered by the x86. (This code is untested, but I think it's right).

[Note: I transferred (my) this answer from another question that got closed, because NONE of the other "answers" here directly answered the question].

6
  • @PeterCordes: Are you sure? The "carry" from the lower 32 bits is the 32 bits in edx at the "add ebx edx" instruction.
    – Ira Baxter
    Mar 9, 2018 at 0:12
  • Oh right, we're only doing 64x64 => 64 bits, and the low 32 bits of the result is fully determined by the low half of lo1 * lo2 => 64 bits, with no addition that can carry into the high half result of lo1 * hi2 => 32 bits and lo2 * hi1 => 32 bits. So those last 2 could be done with 2-operand imul ecx, esi / imul edi, ebx instead of xchg and mul, because you only want a 64-bit result, not 96 or 128. Mar 9, 2018 at 3:39
  • I dont understand how this works. You ignore 2 sets of edx results. That's my main problem. You also didn't use add carry instruction. Now I am sure that part is an error. Dec 31, 2023 at 9:33
  • 1
    @user13947194: 64x64 multiply can technically produce a 128 bit result. That's useful to almost nobody, so we limit our code to producing a 64 bit result, and we ignore the case where you would get more than 64 bits of answer. Then you can ignore the EDX upper products because they are only useful for the more than 64 bits case. Re-read Cordes's comment carefully. Its important to pay attention to the specification (I provide in the first sentence) in order to understand the answer and why it works.
    – Ira Baxter
    Dec 31, 2023 at 18:59
  • 1
    By writing that comment and the formula, I actually began working out the code in head; with help of a diagram I already drew. Imagine a 2 bit processor. We try to emulate on it 4 bit multiplication. Which gives us a 8 bit number. My problem is a drew a line through the 4 bit products and began to think of the high 2 bits of the low 4 bit as being simultaneously the high bits to discard AND the high bits of the result to keep. Long story short, the line I drew in the diagram confused me and lead to irrational thinking. Dec 31, 2023 at 20:04
0

It depends what language you are using. From what I remember from learning MIPS assembly, there is a Move From High command and a Move From Lo command, or mflo and mfhi. mfhi stores the top 64bits while mflo stores the lower 64bits of the total number.

1
  • The OP said it's x86, not MIPS
    – phuclv
    Mar 23, 2019 at 17:10
0

ah assembly, been awhile since i've used it. so i'm assuming the real problem here is that the microcontroller (what i used to write code for in assembly anyways) you're working on doesn't have 64 bit registers? if that's the case, you're going to have the break the numbers you're working with apart and perform multiple multiplications with the pieces.

this sounds like it's a homework assignment from the way you've worded it, so i'm not gonna spell it out much further :P

0

Just do normal long multiplication, as if you were multiplying a pair of 2-digit numbers, except each "digit" is really a 32-bit integer. If you're multiplying two numbers at addresses X and Y and storing the result in Z, then what you want to do (in pseudocode) is:

Z[0..3] = X[0..3] * Y[0..3]
Z[4..7] = X[0..3] * Y[4..7] + X[4..7] * Y[0..3]

Note that we're discarding the upper 64 bits of the result (since a 64-bit number times a 64-bit number is a 128-bit number). Also note that this is assuming little-endian. Also, be careful about a signed versus an unsigned multiply.

2
  • 1
    That's missing the high bits from the first part
    – BCS
    Sep 17, 2008 at 21:31
  • Wait, you've confused me-- You've said to go ahead and get rid of the upper 64 bits of the result? Why would that be... well, rational...?
    – Kawarazu
    Sep 17, 2008 at 21:33
0

Find a C compiler that supports 64bit (GCC does IIRC) compile a program that does just that, then get the disassembly. GCC can spit it out on it's own and you can get it out of object file with the right tools.

OTOH their is a 32bX32b = 64b op on x86

a:b * c:d = e:f
// goes to
e:f = b*d;
x:y = a*d;  e += x;
x:y = b*c;  e += x;

everything else overflows

(untested)

Edit Unsigned only

0
-1

I'm betting you're a student, so see if you can make this work: Do it word by word, and use bit shifts. Think up the most efficient solution. Beware of the sign bit.

1
  • 1
    In the end, bit shifts won't be more efficient than the multiplication instructions - at least not on the x86 and not with 32-bit values. To learn the basics of what the processor does to perform a multiplication it's a good exercise though. Feb 9, 2011 at 8:06
-2

If you want 128bit multiplication then this should work this is in AT&T format.

__uint128_t FASTMUL128(const __uint128_t TA,const __uint128_t TB)
{
    union
    {
        __uint128_t WHOLE;
        struct
        {
            unsigned long long int LWORDS[2];
        } SPLIT;
    } KEY;
    register unsigned long long int __RAX,__RDX,__RSI,__RDI;
    __uint128_t RESULT;

KEY.WHOLE=TA;
__RAX=KEY.SPLIT.LWORDS[0];
__RDX=KEY.SPLIT.LWORDS[1];
KEY.WHOLE=TB;
__RSI=KEY.SPLIT.LWORDS[0];
__RDI=KEY.SPLIT.LWORDS[1];
__asm__ __volatile__(
    "movq           %0,                             %%rax                   \n\t"
    "movq           %1,                             %%rdx                   \n\t"
    "movq           %2,                             %%rsi                   \n\t"
    "movq           %3,                             %%rdi                   \n\t"
    "movq           %%rsi,                          %%rbx                   \n\t"
    "movq           %%rdi,                          %%rcx                   \n\t"
    "movq           %%rax,                          %%rsi                   \n\t"
    "movq           %%rdx,                          %%rdi                   \n\t"
    "xorq           %%rax,                          %%rax                   \n\t"
    "xorq           %%rdx,                          %%rdx                   \n\t"
    "movq           %%rdi,                          %%rax                   \n\t"
    "mulq           %%rbx                                                   \n\t"
    "xchgq          %%rbx,                          %%rax                   \n\t"
    "mulq           %%rsi                                                   \n\t"
    "xchgq          %%rax,                          %%rsi                   \n\t"
    "addq           %%rdx,                          %%rbx                   \n\t"
    "mulq           %%rcx                                                   \n\t"
    "addq           %%rax,                          %%rbx                   \n\t"
    "movq           %%rsi,                          %%rax                   \n\t"
    "movq           %%rbx,                          %%rdx                   \n\t"
    "movq           %%rax,                          %0                      \n\t"
    "movq           %%rdx,                          %1                      \n\t"
    "movq           %%rsi,                          %2                      \n\t"
    "movq           %%rdi,                          %3                      \n\t"
    : "=m"(__RAX),"=m"(__RDX),"=m"(__RSI),"=m"(__RDI)
    :  "m"(__RAX), "m"(__RDX), "m"(__RSI), "m"(__RDI)
    : "rax","rbx","ecx","rdx","rsi","rdi"
);
KEY.SPLIT.LWORDS[0]=__RAX;
KEY.SPLIT.LWORDS[1]=__RDX;
RESULT=KEY.WHOLE;
return RESULT;
}
1
-3

If you want 128 mode try this...

__uint128_t AES::XMULTX(__uint128_t TA,__uint128_t TB)
{
    union
    {
        __uint128_t WHOLE;
        struct
        {
            unsigned long long int LWORDS[2];
        } SPLIT;
    } KEY;
    register unsigned long long int __XRBX,__XRCX,__XRSI,__XRDI;
    __uint128_t RESULT;

    KEY.WHOLE=TA;
    __XRSI=KEY.SPLIT.LWORDS[0];
    __XRDI=KEY.SPLIT.LWORDS[1];
    KEY.WHOLE=TB;
    __XRBX=KEY.SPLIT.LWORDS[0];
    __XRCX=KEY.SPLIT.LWORDS[1];
    __asm__ __volatile__(
                 "movq          %0,             %%rsi           \n\t"       
                 "movq          %1,             %%rdi           \n\t"
                 "movq          %2,             %%rbx           \n\t"
                 "movq          %3,             %%rcx           \n\t"
                 "movq          %%rdi,          %%rax           \n\t"
                 "mulq          %%rbx                           \n\t"
                 "xchgq         %%rbx,          %%rax           \n\t"
                 "mulq          %%rsi                           \n\t"
                 "xchgq         %%rax,          %%rsi           \n\t"
                 "addq          %%rdx,          %%rbx           \n\t"
                 "mulq          %%rcx                           \n\t"
                 "addq          %%rax,          %%rbx           \n\t"
                 "movq          %%rsi,          %0              \n\t"
                 "movq          %%rbx,          %1              \n\t"
                 : "=m" (__XRSI), "=m" (__XRBX)
                 : "m" (__XRSI),  "m" (__XRDI), "m" (__XRBX), "m" (__XRCX)
                 : "rax","rbx","rcx","rdx","rsi","rdi"
                 );
    KEY.SPLIT.LWORDS[0]=__XRSI;
    KEY.SPLIT.LWORDS[1]=__XRBX;
    RESULT=KEY.WHOLE;
    return RESULT;
}
4
  • 2
    Why would you require the inputs and outputs to be in memory, instead of just letting gcc load them if necessary? You'd get better asm from just using __uint128_t and letting gcc do it. Also, this pretty much just copies Ira Baxter's answer. If it was good inline asm, it might be a useful addition, but it's not. Using a lot of fixed registers, and requiring memory operands is nowhere near optimal. You should just let gcc handle everything except the 64x64 -> 128 mul instructions, using two separate asm statements with 2 inputs and 2 outputs. And this shouldn't be volatile Mar 5, 2016 at 10:54
  • Because I am interfacing C into Assembler and I don't have the source code for the libs that GCC use and I don't want to use displacements as that would screw up the answer that I am looking for and I also wanted to speed up a piece of code that raises n^p mod n OK.
    – user80998
    Mar 6, 2016 at 21:09
  • You should be using code like asm ("mulq %[src]" : "=a"(lo64_result), "=d"(hi64_result) : "a"(KEY.SPLIT.LWORDS[1]), [src] "rm" (KEY.SPLIT.LWORDS[0])); And then a second similar asm statement for the second multiply. gcc will do all the mov instructions. You just tell it where things need to be, and where the results will appear. Source for gcc library code has nothing to do with anything, and neither do memory displacements. See the x86 tag wiki for links about how to write inline asm that isn't terrible. That compiles: goo.gl/izSfMi Mar 7, 2016 at 3:06
  • I actually extracted this from Borland Turbo C++ so I am not copying using debug86.exe
    – user80998
    Aug 19, 2016 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.