summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNicolas Boichat <drinkcat@google.com>2017-03-03 10:12:07 -0800
committerChromeOS Commit Bot <chromeos-commit-bot@chromium.org>2018-06-01 06:22:06 +0000
commit6cd014b2658f2a709f22b16d06982ff5444cd6db (patch)
treea45f5e1cc9ef917f426b82a4ba6fcbb881fec879
parent29db6c1226288ea3eca333503a0d4a70c2729388 (diff)
downloadchrome-ec-6cd014b2658f2a709f22b16d06982ff5444cd6db.tar.gz
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 <dmitrygr@google.com>. 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 <drinkcat@chromium.org> Reviewed-on: https://chromium-review.googlesource.com/449024 Reviewed-by: Vincent Palatin <vpalatin@chromium.org> Reviewed-on: https://chromium-review.googlesource.com/1080583
-rw-r--r--common/rsa.c12
-rw-r--r--core/cortex-m0/build.mk2
-rw-r--r--core/cortex-m0/config_core.h2
-rw-r--r--core/cortex-m0/mula.S46
-rw-r--r--include/config.h7
-rw-r--r--include/util.h18
-rw-r--r--test/utils.c27
7 files changed, 107 insertions, 7 deletions
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();
}