commit e5fbd93eaf96581144ce41233b2bcdb1822ea42f
author Dave Rodgman <dave.rodgman@arm.com> Thu Aug 10 10:58:13 2023 +0100
committer GitHub <noreply@github.com> Thu Aug 10 10:58:13 2023 +0100
tree 2e5ad74a9b4d5fcb180618828ff81ae7bd0a2388
parent 2f12a29cdd51dce4584020b0be2888686b310d40
parent 960eca997d07ad83843fa5dcdb61642614fabe1f

Merge pull request #8049 from daverodgman/bignum_codesize_misc

Bignum codesize misc

library/bignum.c

diff --git a/library/bignum.c b/library/bignum.c
index f2a8641..f02b1ac 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -258,6 +258,10 @@
     return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
 }
 
+/* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
+ * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
+#define TO_SIGN(x) ((((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
+
 /*
  * Set value from integer
  */
@@ -270,7 +274,7 @@
     memset(X->p, 0, X->n * ciL);
 
     X->p[0] = mpi_sint_abs(z);
-    X->s    = (z < 0) ? -1 : 1;
+    X->s    = TO_SIGN(z);
 
 cleanup:
 
@@ -326,16 +330,35 @@
  */
 size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
 {
-    size_t i, j, count = 0;
+    size_t i;
     MBEDTLS_INTERNAL_VALIDATE_RET(X != NULL, 0);
 
+#if defined(__has_builtin)
+#if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
+    #define mbedtls_mpi_uint_ctz __builtin_ctz
+#elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
+    #define mbedtls_mpi_uint_ctz __builtin_ctzl
+#elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
+    #define mbedtls_mpi_uint_ctz __builtin_ctzll
+#endif
+#endif
+
+#if defined(mbedtls_mpi_uint_ctz)
     for (i = 0; i < X->n; i++) {
-        for (j = 0; j < biL; j++, count++) {
+        if (X->p[i] != 0) {
+            return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
+        }
+    }
+#else
+    size_t count = 0;
+    for (i = 0; i < X->n; i++) {
+        for (size_t j = 0; j < biL; j++, count++) {
             if (((X->p[i] >> j) & 1) != 0) {
                 return count;
             }
         }
     }
+#endif
 
     return 0;
 }
@@ -796,9 +819,8 @@
         }
     }
 
-    if (i == 0 && j == 0) {
-        return 0;
-    }
+    /* If i == j == 0, i.e. abs(X) == abs(Y),
+     * we end up returning 0 at the end of the function. */
 
     if (i > j) {
         return 1;
@@ -880,7 +902,7 @@
     MPI_VALIDATE_RET(X != NULL);
 
     *p  = mpi_sint_abs(z);
-    Y.s = (z < 0) ? -1 : 1;
+    Y.s = TO_SIGN(z);
     Y.n = 1;
     Y.p = p;
 
@@ -1068,7 +1090,7 @@
     MPI_VALIDATE_RET(A != NULL);
 
     p[0] = mpi_sint_abs(b);
-    B.s = (b < 0) ? -1 : 1;
+    B.s = TO_SIGN(b);
     B.n = 1;
     B.p = p;
 
@@ -1086,7 +1108,7 @@
     MPI_VALIDATE_RET(A != NULL);
 
     p[0] = mpi_sint_abs(b);
-    B.s = (b < 0) ? -1 : 1;
+    B.s = TO_SIGN(b);
     B.n = 1;
     B.p = p;
 
@@ -1436,7 +1458,7 @@
     MPI_VALIDATE_RET(A != NULL);
 
     p[0] = mpi_sint_abs(b);
-    B.s = (b < 0) ? -1 : 1;
+    B.s = TO_SIGN(b);
     B.n = 1;
     B.p = p;
 

library/bignum_core.c

diff --git a/library/bignum_core.c b/library/bignum_core.c
index 8bf819c..ae0b94a 100644
--- a/library/bignum_core.c
+++ b/library/bignum_core.c
@@ -686,16 +686,16 @@
 
 static size_t exp_mod_get_window_size(size_t Ebits)
 {
-    size_t wsize = (Ebits > 671) ? 6 : (Ebits > 239) ? 5 :
-                   (Ebits >  79) ? 4 : 1;
-
-#if (MBEDTLS_MPI_WINDOW_SIZE < 6)
-    if (wsize > MBEDTLS_MPI_WINDOW_SIZE) {
-        wsize = MBEDTLS_MPI_WINDOW_SIZE;
-    }
+#if MBEDTLS_MPI_WINDOW_SIZE >= 6
+    return (Ebits > 671) ? 6 : (Ebits > 239) ? 5 : (Ebits >  79) ? 4 : 1;
+#elif MBEDTLS_MPI_WINDOW_SIZE == 5
+    return (Ebits > 239) ? 5 : (Ebits >  79) ? 4 : 1;
+#elif MBEDTLS_MPI_WINDOW_SIZE > 1
+    return (Ebits >  79) ? MBEDTLS_MPI_WINDOW_SIZE : 1;
+#else
+    (void) Ebits;
+    return 1;
 #endif
-
-    return wsize;
 }
 
 size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs)