s_mp_mul.c

   1 #include "tommath_private.h"
   2 #ifdef S_MP_MUL_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* multiplies |a| * |b| and only computes upto digs digits of result
   7  * HAC pp. 595, Algorithm 14.12  Modified so you can control how
   8  * many digits of output are created.
   9  */
  10 mp_err s_mp_mul(const mp_int *a, const mp_int *b, mp_int *c, int digs)
  11 {
  12    mp_int  t;
  13    mp_err  err;
  14    int     pa, ix;
  15
  16    if (digs < 0) {
  17       return MP_VAL;
  18    }
  19
  20    /* can we use the fast multiplier? */
  21    if ((digs < MP_WARRAY) &&
  22        (MP_MIN(a->used, b->used) < MP_MAX_COMBA)) {
  23       return s_mp_mul_comba(a, b, c, digs);
  24    }
  25
  26    if ((err = mp_init_size(&t, digs)) != MP_OKAY) {
  27       return err;
  28    }
  29    t.used = digs;
  30
  31    /* compute the digits of the product directly */
  32    pa = a->used;
  33    for (ix = 0; ix < pa; ix++) {
  34       int iy, pb;
  35       mp_digit u = 0;
  36
  37       /* limit ourselves to making digs digits of output */
  38       pb = MP_MIN(b->used, digs - ix);
  39
  40       /* compute the columns of the output and propagate the carry */
  41       for (iy = 0; iy < pb; iy++) {
  42          /* compute the column as a mp_word */
  43          mp_word r = (mp_word)t.dp[ix + iy] +
  44                      ((mp_word)a->dp[ix] * (mp_word)b->dp[iy]) +
  45                      (mp_word)u;
  46
  47          /* the new column is the lower part of the result */
  48          t.dp[ix + iy] = (mp_digit)(r & (mp_word)MP_MASK);
  49
  50          /* get the carry word from the result */
  51          u       = (mp_digit)(r >> (mp_word)MP_DIGIT_BIT);
  52       }
  53       /* set carry if it is placed below digs */
  54       if ((ix + iy) < digs) {
  55          t.dp[ix + pb] = u;
  56       }
  57    }
  58
  59    mp_clamp(&t);
  60    mp_exch(&t, c);
  61
  62    mp_clear(&t);
  63    return MP_OKAY;
  64 }
  65 #endif