# Fast 32x32 bit multiply on ARM M0

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
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
MOVS x,0x0;\
//pure C equiv is:  {r+=x;R+=(r<x);x=0;}

//R.r+=X.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
MOVS     r3,#0        ;// 1
MOVS     r2,#0        ;// 1
LSLS     r2,r3,#16    ;// 1
LSRS     r3,r0,#16    ;// 1
LSLS     r0,r0,#16    ;// 1
POP      {r4}         ;// 2
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. Dec 21, 2015 at 4:22
• The GCC implementation looks to be the same 35 cycle routine. Dec 21, 2015 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, 2015 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. Feb 4, 2016 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, 2016 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
lsls    r2, #16

lsls    r2, r3, #16
lsrs    r3, #16
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
lsls    r2, #16

lsls    r2, r3, #16
lsrs    r3, #16
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. Feb 4, 2016 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, 2016 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

• You are multiplying 0xFFFF,FFFF and 0xFFFF,FFFF. Now check again. Groetjes Albert Mar 5, 2021 at 19:15
• Is this a review of the code in the question, or is a comment on JS1's answer which introduces "attempt 2"? May 28, 2021 at 10:03
• The inputs are uint32_t, so -1 isn't possible (except as the bit-pattern for UINT_MAX). Squaring it doesn't produce 1, it produces 0xfffffffe : 0x00000001. Jun 28, 2021 at 19:53

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 May 15, 2018 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, 2018 at 14:15