diff libtommath/bn_mp_mul.c @ 1692:1051e4eea25a

Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
line wrap: on
line diff
--- a/libtommath/bn_mp_mul.c	Tue May 26 23:27:26 2020 +0800
+++ b/libtommath/bn_mp_mul.c	Tue May 26 17:36:47 2020 +0200
@@ -1,64 +1,52 @@
 #include "tommath_private.h"
 #ifdef BN_MP_MUL_C
-/* LibTomMath, multiple-precision integer library -- Tom St Denis
- *
- * LibTomMath is a library that provides multiple-precision
- * integer arithmetic as well as number theoretic functionality.
- *
- * The library was designed directly after the MPI library by
- * Michael Fromberger but has been written from scratch with
- * additional optimizations in place.
- *
- * SPDX-License-Identifier: Unlicense
- */
+/* LibTomMath, multiple-precision integer library -- Tom St Denis */
+/* SPDX-License-Identifier: Unlicense */
 
 /* high level multiplication (handles sign) */
-int mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
+mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
 {
-   int     res, neg;
-   neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
+   mp_err err;
+   int min_len = MP_MIN(a->used, b->used),
+       max_len = MP_MAX(a->used, b->used),
+       digs = a->used + b->used + 1;
+   mp_sign neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
 
-   /* use Toom-Cook? */
-#ifdef BN_MP_TOOM_MUL_C
-   if (MIN(a->used, b->used) >= TOOM_MUL_CUTOFF) {
-      res = mp_toom_mul(a, b, c);
-   } else
-#endif
-#ifdef BN_MP_KARATSUBA_MUL_C
-      /* use Karatsuba? */
-      if (MIN(a->used, b->used) >= KARATSUBA_MUL_CUTOFF) {
-         res = mp_karatsuba_mul(a, b, c);
-      } else
-#endif
-      {
-         /* can we use the fast multiplier?
-          *
-          * The fast multiplier can be used if the output will
-          * have less than MP_WARRAY digits and the number of
-          * digits won't affect carry propagation
-          */
-         int     digs = a->used + b->used + 1;
-
-#ifdef BN_FAST_S_MP_MUL_DIGS_C
-         if ((digs < (int)MP_WARRAY) &&
-             (MIN(a->used, b->used) <=
-              (int)(1u << (((size_t)CHAR_BIT * sizeof(mp_word)) - (2u * (size_t)DIGIT_BIT))))) {
-            res = fast_s_mp_mul_digs(a, b, c, digs);
-         } else
-#endif
-         {
-#ifdef BN_S_MP_MUL_DIGS_C
-            res = s_mp_mul(a, b, c); /* uses s_mp_mul_digs */
-#else
-            res = MP_VAL;
-#endif
-         }
-      }
+   if (MP_HAS(S_MP_BALANCE_MUL) &&
+       /* Check sizes. The smaller one needs to be larger than the Karatsuba cut-off.
+        * The bigger one needs to be at least about one MP_KARATSUBA_MUL_CUTOFF bigger
+        * to make some sense, but it depends on architecture, OS, position of the
+        * stars... so YMMV.
+        * Using it to cut the input into slices small enough for fast_s_mp_mul_digs
+        * was actually slower on the author's machine, but YMMV.
+        */
+       (min_len >= MP_KARATSUBA_MUL_CUTOFF) &&
+       ((max_len / 2) >= MP_KARATSUBA_MUL_CUTOFF) &&
+       /* Not much effect was observed below a ratio of 1:2, but again: YMMV. */
+       (max_len >= (2 * min_len))) {
+      err = s_mp_balance_mul(a,b,c);
+   } else if (MP_HAS(S_MP_TOOM_MUL) &&
+              (min_len >= MP_TOOM_MUL_CUTOFF)) {
+      err = s_mp_toom_mul(a, b, c);
+   } else if (MP_HAS(S_MP_KARATSUBA_MUL) &&
+              (min_len >= MP_KARATSUBA_MUL_CUTOFF)) {
+      err = s_mp_karatsuba_mul(a, b, c);
+   } else if (MP_HAS(S_MP_MUL_DIGS_FAST) &&
+              /* can we use the fast multiplier?
+               *
+               * The fast multiplier can be used if the output will
+               * have less than MP_WARRAY digits and the number of
+               * digits won't affect carry propagation
+               */
+              (digs < MP_WARRAY) &&
+              (min_len <= MP_MAXFAST)) {
+      err = s_mp_mul_digs_fast(a, b, c, digs);
+   } else if (MP_HAS(S_MP_MUL_DIGS)) {
+      err = s_mp_mul_digs(a, b, c, digs);
+   } else {
+      err = MP_VAL;
+   }
    c->sign = (c->used > 0) ? neg : MP_ZPOS;
-   return res;
+   return err;
 }
 #endif
-
-/* ref:         HEAD -> master, tag: v1.1.0 */
-/* git commit:  08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
-/* commit time: 2019-01-28 20:32:32 +0100 */