I'm implementing a cryptographic library, which has optimized assembly for ARM Cortex M-0 architecture, including several units using multiply-accumulate macro, which uses 32x32->32 bit multiplications.
I'm using M-33 which supports 32x32-->64 multiplication. So I first optimized the algorithms by replacing the 32-bit multiplications (and some additions) with 64-bit variant (UMULL), which worked correctly. However, the Cortex M33 also supports single instruction for 64-bit MAC (UMLAL). When I used this instruction, the results was correct except 2 bits : 0xe5c528fb, 0xc5abc3fc (11th and 12th values).
The wrong result by using UMLAL:
umlal_result =
{0xb45deb28, 0xeb23a781, 0xec09b357, 0xe561f5f5, 0x1e3fa5d2, 0x828ad2db,
0x60c67a8a, 0xd2850733, 0xad1de690, 0x6e1ceba1, 0xe5c528fb, 0xc5abc3fc,
0x2f648d3b, 0xe13039aa, 0x58cc1ff4, 0x1d7521f1}
The right one (UMULL):
umull_result =
{0xb45deb28, 0xeb23a781, 0xec09b357, 0xe561f5f5, 0x1e3fa5d2, 0x828ad2db,
0x60c67a8a, 0xd2850733, 0xad1de690, 0x6e1ceba1, 0xe5c528fc, 0xc5abc3fb,
0x2f648d3b, 0xe13039aa, 0x58cc1ff4, 0x1d7521f1}
I tried to debug through the problem, but couldn't find the reason. So my question is, what could be the problem? In my opinion, the two samples above are equivalent, affecting the same flags.. Apparently that is not the case. My guess would be that all the modifications would need to locate in mulacc macro, as it simply takes 2*32 bit inputs and outputs 64 bits as the result of MAC, and of course, updates the required flags. All the numbers I'm using are unsigned.
Any advice will be appreciated.
EDIT2: A test-code containing all the necessary: .S files for both umlal, umull versions and a main function for calling them.
The karatsuba_umull.S file:
.macro mulacc
@fixed: 64-bit multiply for Cortex M-33
umull r6, r0, r1, r2
mov r7, #0
add r5, r5, r6
adc r4, r4, r0
adc r3, r3, r7
.endm
.macro loadAndAdd reg, idx
.if \reg == sp || \reg == r0
ldr r6, [\reg, #\idx*4]
.else
mov r0, \reg
ldr r6, [r0, #\idx*4]
.endif
add r5, r5, r6
adc r4, r4, r7
.endm
.macro loadAndSub reg, idx
.if \reg == sp || \reg == r0
ldr r6, [\reg, #\idx*4]
.else
mov r0, \reg
ldr r6, [r0, #\idx*4]
.endif
sub r5, r5, r6
sbc r4, r4, r7
.endm
.macro loadAndAddIfCarry carryReg, opReg, idx
ldr r0, [\opReg, #\idx*4]
mov r1, \carryReg
and r0, r0, r1
add r5, r5, r0 @ tässä pitäisi olla 1? umuls mid kohta 7
adc r4, r4, r7
.endm
.macro loadMultiply regA, regB, idxA, idxB
.if \regA == sp
ldr r1, [sp, #\idxA*4]
.else
mov r1, \regA
ldr r1, [r1, #\idxA*4]
.endif
.if \regB == sp
ldr r2, [sp, #\idxB*4]
.else
mov r2, \regB
ldr r2, [r2, #\idxB*4]
.endif
mulacc
.endm
.macro storeAndShiftAcc regDst, idx
.if \regDst == sp || \regDst == r0
str r5, [\regDst, #\idx*4]
.else
mov r6, \regDst
str r5, [r6, #\idx*4]
.endif
mov r5, r4
mov r4, r3
asr r3, r4, #32
.endm
.macro storeRemAcc regDst, idx1, idx2
.if \regDst == sp
str r5, [sp, #\idx1*4]
str r4, [sp, #\idx2*4]
.else
mov r6, \regDst
str r5, [r6, #\idx1*4]
str r4, [r6, #\idx2*4]
.endif
.endm
.macro resetAccumulator
ldr r3, =0
mov r4, r3
mov r5, r3
.endm
.macro multiplyLow
loadMultiply r8,r9,0,0
storeAndShiftAcc r10, 0
loadMultiply r9,r8,1,0
loadMultiply r9,r8,0,1
storeAndShiftAcc r10, 1
loadMultiply r8,r9,2,0
loadMultiply r8,r9,1,1
loadMultiply r8,r9,0,2
storeAndShiftAcc r10, 2
loadMultiply r9,r8,3,0
loadMultiply r8,r9,1,2
loadMultiply r8,r9,2,1
loadMultiply r8,r9,3,0
storeAndShiftAcc r10, 3
loadMultiply r9,r8,1,3
loadMultiply r9,r8,2,2
loadMultiply r9,r8,3,1
storeAndShiftAcc sp, 8
loadMultiply r8,r9,2,3
loadMultiply r8,r9,3,2
storeAndShiftAcc sp, 9
loadMultiply r9,r8,3,3
storeRemAcc sp, 10, 11
.endm
.macro multiplyHigh
loadMultiply r8,r9,4,4
storeAndShiftAcc r10, 8
loadMultiply r9,r8,5,4
loadMultiply r9,r8,4,5
storeAndShiftAcc r10, 9
loadMultiply r8,r9,6,4
loadMultiply r8,r9,5,5
loadMultiply r8,r9,4,6
storeAndShiftAcc r10, 10
loadMultiply r9,r8,7,4
loadMultiply r8,r9,5,6
loadMultiply r8,r9,6,5
loadMultiply r8,r9,7,4
storeAndShiftAcc r10, 11
loadMultiply r9,r8,5,7
loadMultiply r9,r8,6,6
loadMultiply r9,r8,7,5
storeAndShiftAcc r10, 12
loadMultiply r8,r9,6,7
loadMultiply r8,r9,7,6
storeAndShiftAcc r10, 13
loadMultiply r9,r8,7,7
storeRemAcc r10, 14, 15
.endm
.macro multiplyMiddle
mov r7, #0
mov r0, r10
loadAndAdd sp, 8
loadAndSub r0,8
loadAndSub r0,0
asr r3, r4, #32
loadMultiply sp,sp,0,4
storeAndShiftAcc r10,4
mov r0, r10
loadAndAdd sp, 9
loadAndSub r0,9
loadAndSub r0,1
asr r3, r4, #32
loadMultiply sp,sp,1,4
loadMultiply sp,sp,0,5
storeAndShiftAcc r10,5
mov r0, r10
loadAndAdd sp, 10
loadAndSub r0,10
loadAndSub r0,2
asr r3, r4, #32
loadMultiply sp,sp,2,4
loadMultiply sp,sp,1,5
loadMultiply sp,sp,0,6
storeAndShiftAcc r10,6
mov r0, r10
loadAndAdd sp, 11
loadAndSub r0,11
loadAndSub r0,3
asr r3, r4, #32
loadMultiply sp,sp,3,4
loadMultiply sp,sp,2,5
loadMultiply sp,sp,1,6
loadMultiply sp,sp,0,7
storeAndShiftAcc r10,7
loadAndAddIfCarry r11, sp, 4
loadAndAddIfCarry r12, sp, 0
mov r0, r10
loadAndAdd r0,8
loadAndSub r0,12
loadAndSub sp,8
asr r3, r4, #32
loadMultiply sp,sp,3,5
loadMultiply sp,sp,2,6
loadMultiply sp,sp,1,7
storeAndShiftAcc r10,8
loadAndAddIfCarry r11, sp, 5
loadAndAddIfCarry r12, sp, 1
mov r0, r10
loadAndAdd r0,9
loadAndSub r0,13
loadAndSub sp,9
asr r3, r4, #32
loadMultiply sp,sp,3,6
loadMultiply sp,sp,2,7
storeAndShiftAcc r10,9
loadAndAddIfCarry r11, sp, 6
loadAndAddIfCarry r12, sp, 2 @ r4 = 1 with umuls
mov r0, r10
loadAndAdd r0,10
loadAndSub r0,14
loadAndSub sp,10
asr r3, r4, #32
loadMultiply sp,sp,3,7
storeAndShiftAcc r10,10
loadAndAddIfCarry r11, sp, 7
loadAndAddIfCarry r12, sp, 3
mov r0, r10
loadAndAdd r0,11
loadAndSub r0,15
loadAndSub sp,11
asr r3, r4, #32
storeAndShiftAcc r0,11
addCarries
loadRegAndAdd r1,12
str r5, [r1, #12*4]
mov r5, r4
loadRegAndAddNoAcc r1,13
str r5, [r1, #13*4]
loadRegAndAddCarry r1,14
str r5, [r1, #14*4]
loadRegAndAddCarry r1,15
str r5, [r1, #15*4]
.endm
.macro loadRegAndAddCarry baseReg, idx
ldr r5, [\baseReg, #\idx*4]
adc r5, r5, r7
.endm
.macro loadRegAndAddNoAcc baseReg, idx
ldr r6, [\baseReg, #\idx*4]
add r5, r5, r6
.endm
.macro loadRegAndAdd baseReg, idx
ldr r6, [\baseReg, #\idx*4]
add r5, r5, r6
adc r4, r4, r7
.endm
.macro addCarries
mov r6, r11
mov r0, r12
and r6, r6, r0
neg r6, r6
add r5, r5, r6
adc r4, r4, r7
mov r1, r10
.endm
.macro sumA
@ to use: r3, r4, r5, r6, r7
ldm r1, {r0, r1, r2, r3, r4, r5, r6, r7}
add r4, r4, r0
adc r5, r5, r1
adc r6, r6, r2
adc r7, r7, r3
sbc r3, r3, r3
mvn r3, r3
mov r11, r3
mov r1, sp
stm r1, {r4, r5, r6, r7}
.endm
.macro sumB
@ to use: r3, r4, r5, r6, r7
mov r1, r9
ldm r1, {r0, r1, r2, r3, r4, r5, r6, r7}
add r4, r4, r0
adc r5, r5, r1
adc r6, r6, r2
adc r7, r7, r3
sbc r3, r3, r3
mvn r3, r3
mov r12, r3
add r1, sp, #16
stm r1, {r4, r5, r6, r7}
.endm
.global bi_multiply_cm0_umull
.type bi_multiply_cm0_umull, function
.text 1
.thumb
@ res: r0
@ operand a: r1
@ operand b: r2
bi_multiply_cm0_umull:
push {r4, r5, r6, r7, lr}
mov r4, r8
mov r5, r9
mov r6, r10
mov r7, r11
push {r4, r5, r6, r7}
mov r4, r12
push {r4}
sub sp, sp, #64
mov r8, r1
mov r9, r2
mov r10, r0
sumA
sumB
resetAccumulator
multiplyLow
resetAccumulator
multiplyHigh
resetAccumulator
multiplyMiddle
add sp, sp, #64
pop {r4}
mov r12, r4
pop {r4, r5, r6, r7}
mov r8, r4
mov r9, r5
mov r10, r6
mov r11, r7
pop {r4, r5, r6, r7, pc}
karatsuba_umlal.S file
.macro mulacc
@ fixed: 64-bit multiply for Cortex M-33
umlal r5, r4, r1, r2
mov r7, #0
adc r3, r3, r7
.endm
.macro loadAndAdd reg, idx
.if \reg == sp || \reg == r0
ldr r6, [\reg, #\idx*4]
.else
mov r0, \reg
ldr r6, [r0, #\idx*4]
.endif
add r5, r5, r6
adc r4, r4, r7
.endm
.macro loadAndSub reg, idx
.if \reg == sp || \reg == r0
ldr r6, [\reg, #\idx*4]
.else
mov r0, \reg
ldr r6, [r0, #\idx*4]
.endif
sub r5, r5, r6
sbc r4, r4, r7
.endm
.macro loadAndAddIfCarry carryReg, opReg, idx
ldr r0, [\opReg, #\idx*4]
mov r1, \carryReg
and r0, r0, r1
add r5, r5, r0 @ tässä pitäisi olla 1? umuls mid kohta 7
adc r4, r4, r7
.endm
.macro loadMultiply regA, regB, idxA, idxB
.if \regA == sp
ldr r1, [sp, #\idxA*4]
.else
mov r1, \regA
ldr r1, [r1, #\idxA*4]
.endif
.if \regB == sp
ldr r2, [sp, #\idxB*4]
.else
mov r2, \regB
ldr r2, [r2, #\idxB*4]
.endif
mulacc
.endm
.macro storeAndShiftAcc regDst, idx
.if \regDst == sp || \regDst == r0
str r5, [\regDst, #\idx*4]
.else
mov r6, \regDst
str r5, [r6, #\idx*4]
.endif
mov r5, r4
mov r4, r3
asr r3, r4, #32
.endm
.macro storeRemAcc regDst, idx1, idx2
.if \regDst == sp
str r5, [sp, #\idx1*4]
str r4, [sp, #\idx2*4]
.else
mov r6, \regDst
str r5, [r6, #\idx1*4]
str r4, [r6, #\idx2*4]
.endif
.endm
.macro resetAccumulator
ldr r3, =0
mov r4, r3
mov r5, r3
.endm
.macro multiplyLow
loadMultiply r8,r9,0,0
storeAndShiftAcc r10, 0
loadMultiply r9,r8,1,0
loadMultiply r9,r8,0,1
storeAndShiftAcc r10, 1
loadMultiply r8,r9,2,0
loadMultiply r8,r9,1,1
loadMultiply r8,r9,0,2
storeAndShiftAcc r10, 2
loadMultiply r9,r8,3,0
loadMultiply r8,r9,1,2
loadMultiply r8,r9,2,1
loadMultiply r8,r9,3,0
storeAndShiftAcc r10, 3
loadMultiply r9,r8,1,3
loadMultiply r9,r8,2,2
loadMultiply r9,r8,3,1
storeAndShiftAcc sp, 8
loadMultiply r8,r9,2,3
loadMultiply r8,r9,3,2
storeAndShiftAcc sp, 9
loadMultiply r9,r8,3,3
storeRemAcc sp, 10, 11
.endm
.macro multiplyHigh
loadMultiply r8,r9,4,4
storeAndShiftAcc r10, 8
loadMultiply r9,r8,5,4
loadMultiply r9,r8,4,5
storeAndShiftAcc r10, 9
loadMultiply r8,r9,6,4
loadMultiply r8,r9,5,5
loadMultiply r8,r9,4,6
storeAndShiftAcc r10, 10
loadMultiply r9,r8,7,4
loadMultiply r8,r9,5,6
loadMultiply r8,r9,6,5
loadMultiply r8,r9,7,4
storeAndShiftAcc r10, 11
loadMultiply r9,r8,5,7
loadMultiply r9,r8,6,6
loadMultiply r9,r8,7,5
storeAndShiftAcc r10, 12
loadMultiply r8,r9,6,7
loadMultiply r8,r9,7,6
storeAndShiftAcc r10, 13
loadMultiply r9,r8,7,7
storeRemAcc r10, 14, 15
.endm
.macro multiplyMiddle
mov r7, #0
mov r0, r10
loadAndAdd sp, 8
loadAndSub r0,8
loadAndSub r0,0
asr r3, r4, #32
loadMultiply sp,sp,0,4
storeAndShiftAcc r10,4
mov r0, r10
loadAndAdd sp, 9
loadAndSub r0,9
loadAndSub r0,1
asr r3, r4, #32
loadMultiply sp,sp,1,4
loadMultiply sp,sp,0,5
storeAndShiftAcc r10,5
mov r0, r10
loadAndAdd sp, 10
loadAndSub r0,10
loadAndSub r0,2
asr r3, r4, #32
loadMultiply sp,sp,2,4
loadMultiply sp,sp,1,5
loadMultiply sp,sp,0,6
storeAndShiftAcc r10,6
mov r0, r10
loadAndAdd sp, 11
loadAndSub r0,11
loadAndSub r0,3
asr r3, r4, #32
loadMultiply sp,sp,3,4
loadMultiply sp,sp,2,5
loadMultiply sp,sp,1,6
loadMultiply sp,sp,0,7
storeAndShiftAcc r10,7
loadAndAddIfCarry r11, sp, 4
loadAndAddIfCarry r12, sp, 0
mov r0, r10
loadAndAdd r0,8
loadAndSub r0,12
loadAndSub sp,8
asr r3, r4, #32
loadMultiply sp,sp,3,5
loadMultiply sp,sp,2,6
loadMultiply sp,sp,1,7
storeAndShiftAcc r10,8
loadAndAddIfCarry r11, sp, 5
loadAndAddIfCarry r12, sp, 1
mov r0, r10
loadAndAdd r0,9
loadAndSub r0,13
loadAndSub sp,9
asr r3, r4, #32
loadMultiply sp,sp,3,6
loadMultiply sp,sp,2,7
storeAndShiftAcc r10,9
loadAndAddIfCarry r11, sp, 6
loadAndAddIfCarry r12, sp, 2 @ r4 = 1 with umuls
mov r0, r10
loadAndAdd r0,10
loadAndSub r0,14
loadAndSub sp,10
asr r3, r4, #32
loadMultiply sp,sp,3,7
storeAndShiftAcc r10,10
loadAndAddIfCarry r11, sp, 7
loadAndAddIfCarry r12, sp, 3
mov r0, r10
loadAndAdd r0,11
loadAndSub r0,15
loadAndSub sp,11
asr r3, r4, #32
storeAndShiftAcc r0,11
addCarries
loadRegAndAdd r1,12
str r5, [r1, #12*4]
mov r5, r4
loadRegAndAddNoAcc r1,13
str r5, [r1, #13*4]
loadRegAndAddCarry r1,14
str r5, [r1, #14*4]
loadRegAndAddCarry r1,15
str r5, [r1, #15*4]
.endm
.macro loadRegAndAddCarry baseReg, idx
ldr r5, [\baseReg, #\idx*4]
adc r5, r5, r7
.endm
.macro loadRegAndAddNoAcc baseReg, idx
ldr r6, [\baseReg, #\idx*4]
add r5, r5, r6
.endm
.macro loadRegAndAdd baseReg, idx
ldr r6, [\baseReg, #\idx*4]
add r5, r5, r6
adc r4, r4, r7
.endm
.macro addCarries
mov r6, r11
mov r0, r12
and r6, r6, r0
neg r6, r6
add r5, r5, r6
adc r4, r4, r7
mov r1, r10
.endm
.macro sumA
@ to use: r3, r4, r5, r6, r7
ldm r1, {r0, r1, r2, r3, r4, r5, r6, r7}
add r4, r4, r0
adc r5, r5, r1
adc r6, r6, r2
adc r7, r7, r3
sbc r3, r3, r3
mvn r3, r3
mov r11, r3
mov r1, sp
stm r1, {r4, r5, r6, r7}
.endm
.macro sumB
@ to use: r3, r4, r5, r6, r7
mov r1, r9
ldm r1, {r0, r1, r2, r3, r4, r5, r6, r7}
add r4, r4, r0
adc r5, r5, r1
adc r6, r6, r2
adc r7, r7, r3
sbc r3, r3, r3
mvn r3, r3
mov r12, r3
add r1, sp, #16
stm r1, {r4, r5, r6, r7}
.endm
.global bi_multiply_cm0_umlal
.type bi_multiply_cm0_umlal, function
.text 1
.thumb
@ res: r0
@ operand a: r1
@ operand b: r2
bi_multiply_cm0_umlal:
push {r4, r5, r6, r7, lr}
mov r4, r8
mov r5, r9
mov r6, r10
mov r7, r11
push {r4, r5, r6, r7}
mov r4, r12
push {r4}
sub sp, sp, #64
mov r8, r1
mov r9, r2
mov r10, r0
sumA
sumB
resetAccumulator
multiplyLow
resetAccumulator
multiplyHigh
resetAccumulator
multiplyMiddle
add sp, sp, #64
pop {r4}
mov r12, r4
pop {r4, r5, r6, r7}
mov r8, r4
mov r9, r5
mov r10, r6
mov r11, r7
pop {r4, r5, r6, r7, pc}
Minimal test function (mainfunc.c) for calling:
#include <stdio.h>
#include <inttypes.h>
#define FP_WORDS 8
typedef uint32_t word_t;
typedef word_t bigint_t[FP_WORDS];
static const bigint_t var_a = { 0x52766F6A, 0xACBDC62E, 0x32D23576,
0x600D522F, 0x19049F3B, 0xC4B0D05E, 0xC0FE0998, 0xB70E64D5 };
static const bigint_t var_b = { 0x8FE44968, 0xDEF5AF3C, 0x3D568ABD,
0x09372473, 0x9AF4FFC7, 0x3A822C26, 0x522D6E14, 0x2DAAB214 };
void bi_multiply_cm0_umull(word_t res[2*FP_WORDS], bigint_t a, bigint_t b);
void bi_multiply_cm0_umlal(word_t res[2*FP_WORDS], bigint_t a, bigint_t b);
int main()
{
word_t res_umull[2*FP_WORDS], res_umlal[2*FP_WORDS];
bi_multiply_cm0_umull(res_umull, var_a, var_b);
bi_multiply_cm0_umlal(res_umlal, var_a, var_b);
return 0;
}