mp_mul.c

   1 #include "tommath_private.h"
   2 #ifdef MP_MUL_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* high level multiplication (handles sign) */
   7 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
   8 {
   9    mp_err err;
  10    int min = MP_MIN(a->used, b->used),
  11        max = MP_MAX(a->used, b->used),
  12        digs = a->used + b->used + 1;
  13    bool neg = (a->sign != b->sign);
  14
  15    if ((a == b) &&
  16        MP_HAS(S_MP_SQR_TOOM) && /* use Toom-Cook? */
  17        (a->used >= MP_SQR_TOOM_CUTOFF)) {
  18       err = s_mp_sqr_toom(a, c);
  19    } else if ((a == b) &&
  20               MP_HAS(S_MP_SQR_KARATSUBA) &&  /* Karatsuba? */
  21               (a->used >= MP_SQR_KARATSUBA_CUTOFF)) {
  22       err = s_mp_sqr_karatsuba(a, c);
  23    } else if ((a == b) &&
  24               MP_HAS(S_MP_SQR_COMBA) && /* can we use the fast comba multiplier? */
  25               (((a->used * 2) + 1) < MP_WARRAY) &&
  26               (a->used <= MP_MAX_COMBA)) {
  27       err = s_mp_sqr_comba(a, c);
  28    } else if ((a == b) &&
  29               MP_HAS(S_MP_SQR)) {
  30       err = s_mp_sqr(a, c);
  31    } else if (MP_HAS(S_MP_MUL_BALANCE) &&
  32               /* Check sizes. The smaller one needs to be larger than the Karatsuba cut-off.
  33                * The bigger one needs to be at least about one MP_MUL_KARATSUBA_CUTOFF bigger
  34                * to make some sense, but it depends on architecture, OS, position of the
  35                * stars... so YMMV.
  36                * Using it to cut the input into slices small enough for s_mp_mul_comba
  37                * was actually slower on the author's machine, but YMMV.
  38                */
  39               (min >= MP_MUL_KARATSUBA_CUTOFF) &&
  40               ((max / 2) >= MP_MUL_KARATSUBA_CUTOFF) &&
  41               /* Not much effect was observed below a ratio of 1:2, but again: YMMV. */
  42               (max >= (2 * min))) {
  43       err = s_mp_mul_balance(a,b,c);
  44    } else if (MP_HAS(S_MP_MUL_TOOM) &&
  45               (min >= MP_MUL_TOOM_CUTOFF)) {
  46       err = s_mp_mul_toom(a, b, c);
  47    } else if (MP_HAS(S_MP_MUL_KARATSUBA) &&
  48               (min >= MP_MUL_KARATSUBA_CUTOFF)) {
  49       err = s_mp_mul_karatsuba(a, b, c);
  50    } else if (MP_HAS(S_MP_MUL_COMBA) &&
  51               /* can we use the fast multiplier?
  52                *
  53                * The fast multiplier can be used if the output will
  54                * have less than MP_WARRAY digits and the number of
  55                * digits won't affect carry propagation
  56                */
  57               (digs < MP_WARRAY) &&
  58               (min <= MP_MAX_COMBA)) {
  59       err = s_mp_mul_comba(a, b, c, digs);
  60    } else if (MP_HAS(S_MP_MUL)) {
  61       err = s_mp_mul(a, b, c, digs);
  62    } else {
  63       err = MP_VAL;
  64    }
  65    c->sign = ((c->used > 0) && neg) ? MP_NEG : MP_ZPOS;
  66    return err;
  67 }
  68 #endif