Size/perf optimisation for mbedtls_mpi_core_clz
Signed-off-by: Dave Rodgman <dave.rodgman@arm.com>
diff --git a/library/bignum_core.c b/library/bignum_core.c
index c6d92fb..9b6c414 100644
--- a/library/bignum_core.c
+++ b/library/bignum_core.c
@@ -35,6 +35,36 @@
size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a)
{
+#if defined(__has_builtin)
+#if __has_builtin(__builtin_clz)
+ if (sizeof(mbedtls_mpi_uint) == sizeof(unsigned int)) {
+ // __builtin_clz is undefined if a == 0
+ if (a == 0) {
+ return sizeof(mbedtls_mpi_uint) * 8;
+ } else {
+ return (size_t) __builtin_clz(a);
+ }
+ }
+#endif
+#if __has_builtin(__builtin_clzl)
+ if (sizeof(mbedtls_mpi_uint) == sizeof(unsigned long)) {
+ if (a == 0) {
+ return sizeof(mbedtls_mpi_uint) * 8;
+ } else {
+ return (size_t) __builtin_clzl(a);
+ }
+ }
+#endif
+#if __has_builtin(__builtin_clzll)
+ if (sizeof(mbedtls_mpi_uint) == sizeof(unsigned long long)) {
+ if (a == 0) {
+ return sizeof(mbedtls_mpi_uint) * 8;
+ } else {
+ return (size_t) __builtin_clzll(a);
+ }
+ }
+#endif
+#endif
size_t j;
mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
diff --git a/tests/suites/test_suite_bignum_core.function b/tests/suites/test_suite_bignum_core.function
index e084b83..d80054c 100644
--- a/tests/suites/test_suite_bignum_core.function
+++ b/tests/suites/test_suite_bignum_core.function
@@ -309,6 +309,43 @@
}
/* END_CASE */
+
+/* BEGIN_CASE */
+void mpi_core_clz(int lz, int tz)
+{
+ if ((size_t) (lz + tz) >= (sizeof(mbedtls_mpi_uint) * 8)) {
+ // can't fit required number of leading and trailing zeros - skip test
+ goto exit;
+ }
+
+ mbedtls_mpi_uint x;
+ size_t expected;
+
+ // generate x with lz leading zeros and tz trailing zeros, all other bits set.
+ if (lz == -1) {
+ // special case: all zero
+ x = 0;
+ expected = sizeof(mbedtls_mpi_uint) * 8;
+ } else {
+ expected = lz;
+ if ((lz + tz) > 0) {
+ // some zero bits
+ uint32_t s = (sizeof(mbedtls_mpi_uint) * 8 - lz - tz);
+ x = ((1ULL << s) - 1) << tz;
+ } else {
+ // all bits set
+ x = ~0ULL;
+ }
+ }
+
+ size_t n = mbedtls_mpi_core_clz(x);
+ TEST_EQUAL(n, expected);
+exit:
+ ;
+}
+/* END_CASE */
+
+
/* BEGIN_CASE */
void mpi_core_lt_ct(char *input_X, char *input_Y, int exp_ret)
{
diff --git a/tests/suites/test_suite_bignum_core.misc.data b/tests/suites/test_suite_bignum_core.misc.data
index b61d708..c245b02 100644
--- a/tests/suites/test_suite_bignum_core.misc.data
+++ b/tests/suites/test_suite_bignum_core.misc.data
@@ -491,3 +491,38 @@
Fill random core: 42 bytes, 5 missing limbs
mpi_core_fill_random:42:0:-5:0:MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+CLZ: 0 0: all ones
+mpi_core_clz:0:0
+
+CLZ: -1 -1: all zeros
+mpi_core_clz:-1:-1
+
+CLZ: 1 0
+mpi_core_clz:1:0
+
+CLZ: 1 1
+mpi_core_clz:1:1
+
+CLZ: 4 5
+mpi_core_clz:4:5
+
+CLZ: 8 16
+mpi_core_clz:8:16
+
+CLZ: 31 0
+mpi_core_clz:31:0
+
+CLZ: 32 0
+mpi_core_clz:32:0
+
+CLZ: 33 0
+mpi_core_clz:33:0
+
+CLZ: 63 0
+mpi_core_clz:63:0
+
+CLZ: 64 0
+mpi_core_clz:64:0
+
+CLZ: 100000 0: skip overly long input
+mpi_core_clz:100000:0