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&lt;&lt;16+a. r1 is Bb is B&lt;&lt;16+b
//then Aa * Bb = (A*B)&lt;&lt;32 + (a*B+A*b)&lt;&lt;16 + a*b
//     result  =  Hh&lt;&lt;32   +  KmM&lt;&lt;16      + Ll

uint64_t mul32x32(uint32_t r0, uint32_t r1)
    register uint32_t r2= r1&amp;0xFFFF;  // b
    register uint32_t r3= r1&gt;&gt;16;     // B  
    register uint32_t r4= r0&amp;0xFFFF;  // a
    r1 = r0 &gt;&gt; 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 &lt;&lt;= 16;              // K0
    r2 = r0 &gt;&gt; 16;          // 0m
    r0 &lt;&lt;=16;               // M0
    DBL_ADD_W_CARRY(r1,r0,r2,r4); // K0.M0 += 0m.Ll 
    r1 += r3;                     // Km += Hh
    return (((uint64_t)r1)&lt;&lt;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&lt;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&lt;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 &gt;&gt; 16, r0l = r0 &amp; 0xFFFF;
    uint16_t r1h = r1 &gt;&gt; 16, r1l = r1 &amp; 0xFFFF;
    uint64_t result = (r0h * r1h);
    result &lt;&lt;= 16;
    result += r0h*r1l;
    result += r0l*r1h;
    result &lt;&lt;= 16;
    result += r0l*r1l;
    return result;
}


or equivalently

uint64_t mul32x32(uint32_t r0, uint32_t r1)
{ 
    uint16_t r0h = r0 &gt;&gt; 16, r0l = r0 &amp; 0xFFFF;
    uint16_t r1h = r1 &gt;&gt; 16, r1l = r1 &amp; 0xFFFF;
    return ((uint64_t)(r0h * r1h) &lt;&lt; 32)
         + ((uint64_t)(r0h * r1l) &lt;&lt; 16)
         + ((uint64_t)(r0l * r1h) &lt;&lt; 16)
         + ((uint64_t)(r0l * r1l) &lt;&lt; 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).