Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_S_MP_MUL_DIGS_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           0 : mp_err s_mp_mul_digs(const mp_int *a, const mp_int *b, mp_int *c, int digs)
      11             : {
      12           0 :    mp_int  t;
      13           0 :    mp_err  err;
      14           0 :    int     pa, pb, ix, iy;
      15           0 :    mp_digit u;
      16           0 :    mp_word r;
      17           0 :    mp_digit tmpx, *tmpt, *tmpy;
      18             : 
      19             :    /* can we use the fast multiplier? */
      20           0 :    if ((digs < MP_WARRAY) &&
      21           0 :        (MP_MIN(a->used, b->used) < MP_MAXFAST)) {
      22           0 :       return s_mp_mul_digs_fast(a, b, c, digs);
      23             :    }
      24             : 
      25           0 :    if ((err = mp_init_size(&t, digs)) != MP_OKAY) {
      26           0 :       return err;
      27             :    }
      28           0 :    t.used = digs;
      29             : 
      30             :    /* compute the digits of the product directly */
      31           0 :    pa = a->used;
      32           0 :    for (ix = 0; ix < pa; ix++) {
      33             :       /* set the carry to zero */
      34           0 :       u = 0;
      35             : 
      36             :       /* limit ourselves to making digs digits of output */
      37           0 :       pb = MP_MIN(b->used, digs - ix);
      38             : 
      39             :       /* setup some aliases */
      40             :       /* copy of the digit from a used within the nested loop */
      41           0 :       tmpx = a->dp[ix];
      42             : 
      43             :       /* an alias for the destination shifted ix places */
      44           0 :       tmpt = t.dp + ix;
      45             : 
      46             :       /* an alias for the digits of b */
      47           0 :       tmpy = b->dp;
      48             : 
      49             :       /* compute the columns of the output and propagate the carry */
      50           0 :       for (iy = 0; iy < pb; iy++) {
      51             :          /* compute the column as a mp_word */
      52           0 :          r       = (mp_word)*tmpt +
      53           0 :                    ((mp_word)tmpx * (mp_word)*tmpy++) +
      54           0 :                    (mp_word)u;
      55             : 
      56             :          /* the new column is the lower part of the result */
      57           0 :          *tmpt++ = (mp_digit)(r & (mp_word)MP_MASK);
      58             : 
      59             :          /* get the carry word from the result */
      60           0 :          u       = (mp_digit)(r >> (mp_word)MP_DIGIT_BIT);
      61             :       }
      62             :       /* set carry if it is placed below digs */
      63           0 :       if ((ix + iy) < digs) {
      64           0 :          *tmpt = u;
      65             :       }
      66             :    }
      67             : 
      68           0 :    mp_clamp(&t);
      69           0 :    mp_exch(&t, c);
      70             : 
      71           0 :    mp_clear(&t);
      72           0 :    return MP_OKAY;
      73             : }
      74             : #endif