diff options
Diffstat (limited to 'libtommath/bn_mp_mul.c')
| -rw-r--r-- | libtommath/bn_mp_mul.c | 105 |
1 files changed, 45 insertions, 60 deletions
diff --git a/libtommath/bn_mp_mul.c b/libtommath/bn_mp_mul.c index cc3b9c8..561913a 100644 --- a/libtommath/bn_mp_mul.c +++ b/libtommath/bn_mp_mul.c @@ -1,67 +1,52 @@ -#include <tommath_private.h> +#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. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tstdenis82@gmail.com, http://libtom.org - */ +/* LibTomMath, multiple-precision integer library -- Tom St Denis */ +/* SPDX-License-Identifier: Unlicense */ /* high level multiplication (handles sign) */ -int mp_mul (mp_int * a, 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 < MP_WARRAY) && - (MIN(a->used, b->used) <= - (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * 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 - } - } - c->sign = (c->used > 0) ? neg : MP_ZPOS; - return res; + 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 err; } #endif - -/* ref: $Format:%D$ */ -/* git commit: $Format:%H$ */ -/* commit time: $Format:%ai$ */ |