I have a time-critical calculation running on an ARM Cortex-M0. This is the fastest 32x32 bit -> 64 bit multiplication that I can come up with.

The following C compiles almost 1-1 to assembly instructions:

//consider each arg as two 16-bit parts.
//r0 is Aa is A<<16+a. r1 is Bb is B<<16+b
//then Aa * Bb = (A*B)<<32 + (a*B+A*b)<<16 + a*b
//     result  =  Hh<<32   +  KmM<<16      + Ll

uint64_t mul32x32(uint32_t r0, uint32_t r1)
    register uint32_t r2= r1&0xFFFF;  // b
    register uint32_t r3= r1>>16;     // B  
    register uint32_t r4= r0&0xFFFF;  // a
    r1 = r0 >> 16;                    // A
    r0 = r4;                // a
    r4 *= r2;               // Ll = a*b
    r0 *= r3;               // a*B
    r3 *= r1;               // Hh = B*A
    r2 *= r1;               // b*A
    r1 = 0;                 // K
    ADD_W_CARRY(r1,r0,r2);  // 0K.mM = a*B + b*A
    r1 <<= 16;              // K0
    r2 = r0 >> 16;          // 0m
    r0 <<=16;               // M0
    DBL_ADD_W_CARRY(r1,r0,r2,r4); // K0.M0 += 0m.Ll 
    r1 += r3;                     // Km += Hh
    return (((uint64_t)r1)<<32)|r0;  
}

It uses this bit of inline assembly, to deal with C's inability to express the carry flag:

//R.r+=x // clears x to avoid consuming another register
#define ADD_W_CARRY(R,r,x) __asm {\
        ADDS r,r,x;\
        MOVS x,0x0;\
        ADCS R,R,x;}
//pure C equiv is:  {r+=x;R+=(r<x);x=0;}

//R.r+=X.x
#define DBL_ADD_W_CARRY(R,r,X,x) __asm{\
        ADDS r,r,x;\
        ADCS R,R,X;}
//Pure C equiv is:  {r+=x;R+=X+(r<x); }

This compiles to:

PUSH     {r4}         ;// 2
LSRS     r3,r0,#16    ;// 1
UXTH     r2,r1        ;// 1       
UXTH     r0,r0        ;// 1
MOV      r4,r0        ;// 1
LSRS     r1,r1,#16    ;// 1
MULS     r4,r2,r4     ;// 1
MULS     r0,r1,r0     ;// 1
MULS     r1,r3,r1     ;// 1
MULS     r2,r3,r2     ;// 1
ADDS     r0,r0,r2     ;// 1
MOVS     r3,#0        ;// 1
MOVS     r2,#0        ;// 1
ADCS     r3,r3,r2     ;// 1
LSLS     r2,r3,#16    ;// 1
LSRS     r3,r0,#16    ;// 1
LSLS     r0,r0,#16    ;// 1
ADDS     r0,r0,r4     ;// 1
ADCS     r2,r2,r3     ;// 1
POP      {r4}         ;// 2
ADDS     r1,r2,r1     ;// 1  
BX       lr           ;// 3

                      ;== 26 cycles

Is it possible to do better?

First of all, yes, CortexM0 lacks any way to do 32x32=64 multiplication in hardware. CortexM3 and CortexM4 have the umull instruction, which lets you do 32x32=64 really easily.

And yes, since you're writing in C, one possible implementation would be

uint64_t mul32x32(uint32_t r0, uint32_t r1) { return r0*(uint64_t)r1; }

but I assume you've already tried that (with -O3 and whatever other optimization and inlining options you can turn up) and discovered that your compiler doesn't inline the multiplication, but leaves it as a call to some internal libc function.

A quick Google search turned up this previous StackOverflow question on exactly the same topic, where someone in the comments linked to GCC's implementation of 64x64=64 multiplication for CortexM0 (here), with the suggestion that you could constant-propagate "upper bits are known to be zero" through the whole thing by hand and that would give you something decent. I don't know if that's true.

Have you also benchmarked the "naive" approach of

uint64_t mul32x32(uint32_t r0, uint32_t r1)
{ 
    uint16_t r0h = r0 >> 16, r0l = r0 & 0xFFFF;
    uint16_t r1h = r1 >> 16, r1l = r1 & 0xFFFF;
    uint64_t result = (r0h * r1h);
    result <<= 16;
    result += r0h*r1l;
    result += r0l*r1h;
    result <<= 16;
    result += r0l*r1l;
    return result;
}

or equivalently

uint64_t mul32x32(uint32_t r0, uint32_t r1)
{ 
    uint16_t r0h = r0 >> 16, r0l = r0 & 0xFFFF;
    uint16_t r1h = r1 >> 16, r1l = r1 & 0xFFFF;
    return ((uint64_t)(r0h * r1h) << 32)
         + ((uint64_t)(r0h * r1l) << 16)
         + ((uint64_t)(r0l * r1h) << 16)
         + ((uint64_t)(r0l * r1l) << 0);
}

? As long as none of the arithmetic operations get turned into library function calls, this has the benefit of being portable ANSI C and being susceptible to inlining by the compiler. If you care about speed, susceptibility-to-inlining should be your #1 concern.

Since you have access to your compiler and we don't (I'm guessing Green Hills, from the __asm{ } syntax for inline assembly blocks?), you might get better answers if you posted the assembly that results from the above three C implementations.

Finally, note that CortexM0's MULS instruction takes either 1 cycle or 32 cycles, depending on the processor. If you're on one of those 32-cycle processors, doing four MULS instructions in a row is probably one of the worst things you can do. If MULS only takes 1 cycle, then you're probably okay; I don't think there's any need to space out those MULS instructions the way one might on a machine where they took multiple cycles (software pipelining).

  • Thanks. The compiler is the one with Keil's uVision. The processor has 1 cycle multiply. If I let the compiler do uint64_t multiplies, it generates calls to a library routine ` __ARM_common_ll_muluu` which takes 35 cycles. I'll test some of the other ideas soon. – AShelly Dec 21 '15 at 4:22
  • The GCC implementation looks to be the same 35 cycle routine. – AShelly Dec 21 '15 at 4:27
  • @AShelly Have you looked at this version? You can eliminate 3+ instructions from this version because this one is a 64x64 multiply, so the first few instructions that operate on the high bits are unneeded. – JS1 Dec 21 '15 at 6:18
  • The "naive" version compiles to 39 cycles, the "equivalent" to 38. See Revision 4 for details. @JS1's is 28 - maybe that can be trimmed as suggested. – AShelly Feb 4 '16 at 4:31
  • @AShelly Since this is a 64x64 multiply, you can pretend that r1 and r3 start out as zero. This allows you to remove lines 48-50 and line 55. Then change the two r3 on lines 52 and 54 to be r1 to make the registers correct. This saves 4 instructions. However, this assumes that your inputs are in r3:r2 and r1:r0. In a 32 bit multiply, your inputs are in r1 and r0. You will need to use one extra instruction to copy r1 to r2, because the code clobbers r1 during the computation because r1 will be one of the outputs. So in summary, it should be 28 - 4 + 1 = 25 cycles. – JS1 Feb 4 '16 at 5:27

Attempt 1

To expand on my rather long comment above, I took the 64x64 multiply from this library implementation on github, and I modified it to be a 32x32 multiply. I'm not sure how you are counting the cycles, but this may be equivalent to your 26 cycle implementation because I count 19 "1-cycle" instructions which is the same as in the original post. I don't know how many cycles the push and pop take.

@ long long mul32(long r1, long r0)
@
@ Multiply r1 and r0 and return the product in r1:r0
@
    .thumb_func
        .global mul32
mul32:

    push    {r4, lr}
    mov     r2, r1

    lsrs    r1, r0, #16
    lsrs    r4, r2, #16
    muls    r1, r4

    lsrs    r3, r0, #16
    uxth    r0, r0
    uxth    r2, r2
    muls    r3, r2
    muls    r4, r0
    muls    r0, r2

    movs    r2, #0
    adds    r3, r4
    adcs    r2, r2
    lsls    r2, #16
    adds    r1, r2

    lsls    r2, r3, #16
    lsrs    r3, #16
    adds    r0, r2
    adcs    r1, r3
    pop {r4, pc}

Attempt 2

Actually, I just transformed the above to this, which should be faster than the original post (it now has 1 fewer instructions than the previous version). Perhaps you could test it to make sure I didn't do something wrong because I transformed the code in my head:

@ long long mul32(long r1, long r0)
@
@ Multiply r1 and r0 and return the product in r1:r0
@
    .thumb_func
        .global mul32
mul32:

    push    {r4, lr}

    uxth    r2, r1
    lsrs    r3, r0, #16
    lsrs    r1, r1, #16
    mov     r4, r1
    muls    r1, r3

    uxth    r0, r0
    muls    r3, r2
    muls    r4, r0
    muls    r0, r2

    movs    r2, #0
    adds    r3, r4
    adcs    r2, r2
    lsls    r2, #16
    adds    r1, r2

    lsls    r2, r3, #16
    lsrs    r3, #16
    adds    r0, r2
    adcs    r1, r3
    pop {r4, pc}
  • Thanks. push and pop take 1 + count(registers) cycles, so 3 in these two instances. In attempt 2, you seem to be missing a mov r4,r1 right before the muls r1,r3, to prevent using an uninitialized register. With that addition, it is 24 cycles. It is performing the same set of operations, except I had an extra mov r3,#0 that this one avoids. The other difference is the return to caller method: push {r4,lr}...pop {r4,pc} is 6 cycles vspush {r4}...pop{r4};bx lr which is 7. – AShelly Feb 4 '16 at 20:43
  • @AShelly You're right. I fixed up attempt #2 to add in the missing mov r4, r1 that you spotted. – JS1 Feb 4 '16 at 21:15

In some conditions your code returns incorrect output....check attempt 2 for following inputs : -1 and -1

r1:r0 should return 0x00000000,0x00000001

Given that some implementations of the M0 core take 32 cycles to perform a multiply, using the minimal number of MULS is important. Now, the bottom 32 bits are correctly calculated by 1 MULS so only 3 MULS are strictly necessary. If only r0-r3 are used, that is another 4 cycles (stack unstack) and seeing as a multiply will be the bottom subroutine, lr (r14) only needs to be stacked if your code intends to use it. If you are THAT short of registers and can prevent interrupts, you can use store sp (r13) as well.

The problem lies with the fact that only the Z & N flags are updated by MULS. I'm stumbling with the way to detect an overflow in an elegant manner. Can someone more able than I devise an elegant solution?

  • Can you please sketch how to produce the correct 64 bit result using just the 3 MULS [] strictly necessary – greybeard May 15 at 5:45
  • youtube.com/watch?v=JCbZayFr9RE 1-if you often read from a table (<256 entries), place at bottom of ROM i.e. from $00000000. Doing this made my 14-16 cycle CLZ (count leading zeros) to 12-14 cycles. Address is an immediate! 2-interrupts swap the register file in the CPU of M0/M0+/M1 so feel free to push the LR & store SP in RAM. SP has powerful instructions and addressing modes. Base all code on SP addressing. 3-Ask ARM community. They are great. If you work out why the LSxx instructions use bits 0-7 rather 0-4 of register is unknown by ARM so if you work it out, post. – Sean Oct 15 at 14:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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