From 6cd014b2658f2a709f22b16d06982ff5444cd6db Mon Sep 17 00:00:00 2001 From: Nicolas Boichat Date: Fri, 3 Mar 2017 10:12:07 -0800 Subject: rsa: Optimization of multiplications for Cortex-M0 We multiply 2 32-bit numbers (and not 64-bit numbers), and then add another 32-bit number, which makes it possible to optimize the assembly and save a few instructions. With -O3, 3072-bit exponent, lower verification time from 122 ms to 104 ms on STM32F072 @48Mhz. Optimized mac function from Dmitry Grinberg . BRANCH=poppy BUG=b:35647963 BUG=b:77608104 TEST=On staff, flash, verification successful TEST=make test-rsa, make test-rsa3 TEST=Flash test-utils and test-rsa to hammer => pass Change-Id: I584c54c631a3f59f691849a279b308e8d4b4b22d Signed-off-by: Nicolas Boichat Reviewed-on: https://chromium-review.googlesource.com/449024 Reviewed-by: Vincent Palatin Reviewed-on: https://chromium-review.googlesource.com/1080583 --- common/rsa.c | 12 ++++++------ core/cortex-m0/build.mk | 2 +- core/cortex-m0/config_core.h | 2 ++ core/cortex-m0/mula.S | 46 ++++++++++++++++++++++++++++++++++++++++++++ include/config.h | 7 +++++++ include/util.h | 18 +++++++++++++++++ test/utils.c | 27 ++++++++++++++++++++++++++ 7 files changed, 107 insertions(+), 7 deletions(-) create mode 100644 core/cortex-m0/mula.S diff --git a/common/rsa.c b/common/rsa.c index e4e85c3374..3d8518e9ef 100644 --- a/common/rsa.c +++ b/common/rsa.c @@ -50,14 +50,14 @@ static void mont_mul_add(const struct rsa_public_key *key, const uint32_t a, const uint32_t *b) { - uint64_t A = (uint64_t)a * b[0] + c[0]; + uint64_t A = mula32(a, b[0], c[0]); uint32_t d0 = (uint32_t)A * key->n0inv; - uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; + uint64_t B = mula32(d0, key->n[0], A); uint32_t i; for (i = 1; i < RSANUMWORDS; ++i) { - A = (A >> 32) + (uint64_t)a * b[i] + c[i]; - B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; + A = (A >> 32) + mula32(a, b[i], c[i]); + B = (B >> 32) + mula32(d0, key->n[i], A); c[i - 1] = (uint32_t)B; } @@ -78,11 +78,11 @@ static void mont_mul_add_0(const struct rsa_public_key *key, const uint32_t *b) { uint32_t d0 = c[0] * key->n0inv; - uint64_t B = (uint64_t)d0 * key->n[0] + c[0]; + uint64_t B = mula32(d0, key->n[0], c[0]); uint32_t i; for (i = 1; i < RSANUMWORDS; ++i) { - B = (B >> 32) + (uint64_t)d0 * key->n[i] + c[i]; + B = (B >> 32) + mula32(d0, key->n[i], c[i]); c[i - 1] = (uint32_t)B; } diff --git a/core/cortex-m0/build.mk b/core/cortex-m0/build.mk index 6a0f44b367..2023bd9607 100644 --- a/core/cortex-m0/build.mk +++ b/core/cortex-m0/build.mk @@ -18,7 +18,7 @@ CFLAGS_CPU+=-flto LDFLAGS_EXTRA+=-flto endif -core-y=cpu.o init.o thumb_case.o div.o lmul.o ldivmod.o uldivmod.o +core-y=cpu.o init.o thumb_case.o div.o lmul.o ldivmod.o mula.o uldivmod.o core-$(CONFIG_COMMON_PANIC_OUTPUT)+=panic.o core-$(CONFIG_COMMON_RUNTIME)+=switch.o task.o diff --git a/core/cortex-m0/config_core.h b/core/cortex-m0/config_core.h index 389ed8edec..19a22bc333 100644 --- a/core/cortex-m0/config_core.h +++ b/core/cortex-m0/config_core.h @@ -15,4 +15,6 @@ #define CONFIG_SOFTWARE_CTZ #define CONFIG_SOFTWARE_PANIC +#define CONFIG_ASSEMBLY_MULA32 + #endif /* __CROS_EC_CONFIG_CORE_H */ diff --git a/core/cortex-m0/mula.S b/core/cortex-m0/mula.S new file mode 100644 index 0000000000..fc0a6f3ee0 --- /dev/null +++ b/core/cortex-m0/mula.S @@ -0,0 +1,46 @@ +/* Copyright 2018 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + * + * Cortex-M0 multiply-accumulate functions + */ + + .syntax unified + .text + .thumb + +@ uint64_t mula32(uint32_t a, uint32_t b, uint32_t c) +@ +@ Multiply a (r0) and b (r1), add c (r2) and return the product in r1:r0 +@ + .thumb_func + .section .text.mula32 + .global mula32 +mula32: + + push {r4, r5} + uxth r4, r0 /* r4 = a.lo16 */ + uxth r5, r1 /* r5 = b.lo16 */ + uxth r3, r2 /* r3 = c.lo16 */ + muls r4, r5 /* r4 = a.lo16 * b.lo16 */ + adds r4, r3 /* r4 = a.lo16 * b.lo16 + c.lo16 == r.lo32 */ + lsrs r3, r0, 16 /* r3 = a.hi16 */ + lsrs r2, r2, 16 /* r2 = c.hi16 */ + muls r5, r3 /* r5 = a.hi16 * b.lo16 */ + adds r5, r2 /* r5 = a.hi16 * b.lo16 + c.hi16 == r.mid32.1 */ + uxth r2, r0 /* r2 = a.lo16 */ + lsrs r1, r1, 16 /* r1 = b.hi16 */ + muls r2, r1 /* r2 = a.lo16 * b.hi16 == r.mid32.2 */ + muls r1, r3 /* r1 = b.hi16 * a.hi16 == r.hi32 */ + movs r3, 0 /* r3 = 0 */ + adds r5, r2 /* r5 = (r.mid32.1 + r.mid32.2).lo32 == r.mid.lo32 */ + adcs r3, r3 /* r3 = (r.mid32.1 + r.mid32.2).hi32 == r.mid.hi32 */ + lsls r0, r5, 16 /* r0 = r.mid.lo32.lo16 << 16 == r.mid.inpos.lo32 */ + lsrs r5, r5, 16 /* r5 = r.mid.lo32.hi16 >> 16 */ + lsls r3, r3, 16 /* r3 = r.mid.hi.lo16 << 16 */ + adds r3, r5 /* r3 = r5 + r3 = r.mid.inpos.hi32 */ + adds r0, r4 /* r0 = r.lo32 */ + adcs r1, r3 /* r1 = r.hi32 */ + pop {r4, r5} + bx lr + diff --git a/include/config.h b/include/config.h index 8c12e53715..5bf4f302bc 100644 --- a/include/config.h +++ b/include/config.h @@ -197,6 +197,13 @@ */ #undef CONFIG_ARMV7M_CACHE +/* + * Defined if core/ code provides assembly optimized implementation of + * multiply-accumulate operations (32-bit operands, 64-bit result), for the + * cores that lack native instructions. + */ +#undef CONFIG_ASSEMBLY_MULA32 + /* Allow proprietary communication protocols' extensions. */ #undef CONFIG_EXTENSION_COMMAND diff --git a/include/util.h b/include/util.h index 453ff8c739..2670d4e5ad 100644 --- a/include/util.h +++ b/include/util.h @@ -182,4 +182,22 @@ static inline int cond_went_true(cond_t *c) { return cond_went(c, 1); } int parse_offset_size(int argc, char **argv, int shift, int *offset, int *size); +#ifdef CONFIG_ASSEMBLY_MULA32 +/* + * Compute (a*b)+c, where a, b, c are 32-bit integers, and the result is + * 64-bit long. + */ +uint64_t mula32(uint32_t a, uint32_t b, uint32_t c); +#else +static inline uint64_t mula32(uint32_t a, uint32_t b, uint32_t c) +{ + uint64_t ret = a; + + ret *= b; + ret += c; + + return ret; +} +#endif + #endif /* __CROS_EC_UTIL_H */ diff --git a/test/utils.c b/test/utils.c index c382a46828..a5a53a5eb9 100644 --- a/test/utils.c +++ b/test/utils.c @@ -12,6 +12,7 @@ #include "test_util.h" #include "timer.h" #include "util.h" +#include "watchdog.h" static int test_memmove(void) { @@ -356,6 +357,31 @@ static int test_cond_t(void) return EC_SUCCESS; } +static int test_mula32(void) +{ + uint64_t r = 0x0; + uint32_t b = 0x1; + uint32_t c = 0x1; + uint32_t i; + timestamp_t t0, t1; + + t0 = get_time(); + for (i = 0; i < 5000000; i++) { + r = mula32(b, c, r + (r >> 32)); + b = (b << 13) ^ (b >> 2) ^ i; + c = (c << 16) ^ (c >> 7) ^ i; + watchdog_reload(); + } + t1 = get_time(); + + ccprintf("After %d iterations, r=%08x%08x (time: %d)\n", i, + (uint32_t)(r >> 32), (uint32_t)r, t1.le.lo-t0.le.lo); + TEST_ASSERT(r == 0x9df59b9fb0ab9d96L); + + /* well okay then */ + return EC_SUCCESS; +} + void run_test(void) { test_reset(); @@ -371,6 +397,7 @@ void run_test(void) RUN_TEST(test_shared_mem); RUN_TEST(test_scratchpad); RUN_TEST(test_cond_t); + RUN_TEST(test_mula32); test_print_result(); } -- cgit v1.2.1