source4/heimdal/lib/hcrypto/libtommath/bn_mp_mul.c

   1 #include "tommath_private.h"
   2 #ifdef BN_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_len = MP_MIN(a->used, b->used),
  11        max_len = MP_MAX(a->used, b->used),
  12        digs = a->used + b->used + 1;
  13    mp_sign neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
  14
  15    if (MP_HAS(S_MP_BALANCE_MUL) &&
  16        /* Check sizes. The smaller one needs to be larger than the Karatsuba cut-off.
  17         * The bigger one needs to be at least about one MP_KARATSUBA_MUL_CUTOFF bigger
  18         * to make some sense, but it depends on architecture, OS, position of the
  19         * stars... so YMMV.
  20         * Using it to cut the input into slices small enough for fast_s_mp_mul_digs
  21         * was actually slower on the author's machine, but YMMV.
  22         */
  23        (min_len >= MP_KARATSUBA_MUL_CUTOFF) &&
  24        ((max_len / 2) >= MP_KARATSUBA_MUL_CUTOFF) &&
  25        /* Not much effect was observed below a ratio of 1:2, but again: YMMV. */
  26        (max_len >= (2 * min_len))) {
  27       err = s_mp_balance_mul(a,b,c);
  28    } else if (MP_HAS(S_MP_TOOM_MUL) &&
  29               (min_len >= MP_TOOM_MUL_CUTOFF)) {
  30       err = s_mp_toom_mul(a, b, c);
  31    } else if (MP_HAS(S_MP_KARATSUBA_MUL) &&
  32               (min_len >= MP_KARATSUBA_MUL_CUTOFF)) {
  33       err = s_mp_karatsuba_mul(a, b, c);
  34    } else if (MP_HAS(S_MP_MUL_DIGS_FAST) &&
  35               /* can we use the fast multiplier?
  36                *
  37                * The fast multiplier can be used if the output will
  38                * have less than MP_WARRAY digits and the number of
  39                * digits won't affect carry propagation
  40                */
  41               (digs < MP_WARRAY) &&
  42               (min_len <= MP_MAXFAST)) {
  43       err = s_mp_mul_digs_fast(a, b, c, digs);
  44    } else if (MP_HAS(S_MP_MUL_DIGS)) {
  45       err = s_mp_mul_digs(a, b, c, digs);
  46    } else {
  47       err = MP_VAL;
  48    }
  49    c->sign = (c->used > 0) ? neg : MP_ZPOS;
  50    return err;
  51 }
  52 #endif