Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_S_MP_MUL_DIGS_FAST_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* Fast (comba) multiplier
       7             :  *
       8             :  * This is the fast column-array [comba] multiplier.  It is
       9             :  * designed to compute the columns of the product first
      10             :  * then handle the carries afterwards.  This has the effect
      11             :  * of making the nested loops that compute the columns very
      12             :  * simple and schedulable on super-scalar processors.
      13             :  *
      14             :  * This has been modified to produce a variable number of
      15             :  * digits of output so if say only a half-product is required
      16             :  * you don't have to compute the upper half (a feature
      17             :  * required for fast Barrett reduction).
      18             :  *
      19             :  * Based on Algorithm 14.12 on pp.595 of HAC.
      20             :  *
      21             :  */
      22      119377 : mp_err s_mp_mul_digs_fast(const mp_int *a, const mp_int *b, mp_int *c, int digs)
      23             : {
      24        5280 :    int      olduse, pa, ix, iz;
      25        5280 :    mp_err   err;
      26        5280 :    mp_digit W[MP_WARRAY];
      27        5280 :    mp_word  _W;
      28             : 
      29             :    /* grow the destination as required */
      30      119377 :    if (c->alloc < digs) {
      31       27312 :       if ((err = mp_grow(c, digs)) != MP_OKAY) {
      32           0 :          return err;
      33             :       }
      34             :    }
      35             : 
      36             :    /* number of output digits to produce */
      37      119377 :    pa = MP_MIN(digs, a->used + b->used);
      38             : 
      39             :    /* clear the carry */
      40      119377 :    _W = 0;
      41     7241999 :    for (ix = 0; ix < pa; ix++) {
      42      377183 :       int      tx, ty;
      43      377183 :       int      iy;
      44      377183 :       mp_digit *tmpx, *tmpy;
      45             : 
      46             :       /* get offsets into the two bignums */
      47     7122622 :       ty = MP_MIN(b->used-1, ix);
      48     7122622 :       tx = ix - ty;
      49             : 
      50             :       /* setup temp aliases */
      51     7122622 :       tmpx = a->dp + tx;
      52     7122622 :       tmpy = b->dp + ty;
      53             : 
      54             :       /* this is the number of times the loop will iterrate, essentially
      55             :          while (tx++ < a->used && ty-- >= 0) { ... }
      56             :        */
      57     7122622 :       iy = MP_MIN(a->used-tx, ty+1);
      58             : 
      59             :       /* execute loop */
      60   127452998 :       for (iz = 0; iz < iy; ++iz) {
      61   120330376 :          _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
      62             : 
      63             :       }
      64             : 
      65             :       /* store term */
      66     7122622 :       W[ix] = (mp_digit)_W & MP_MASK;
      67             : 
      68             :       /* make next carry */
      69     7122622 :       _W = _W >> (mp_word)MP_DIGIT_BIT;
      70             :    }
      71             : 
      72             :    /* setup dest */
      73      119377 :    olduse  = c->used;
      74      119377 :    c->used = pa;
      75             : 
      76             :    {
      77        5280 :       mp_digit *tmpc;
      78      119377 :       tmpc = c->dp;
      79     7241999 :       for (ix = 0; ix < pa; ix++) {
      80             :          /* now extract the previous digit [below the carry] */
      81     7122622 :          *tmpc++ = W[ix];
      82             :       }
      83             : 
      84             :       /* clear unused digits [that existed in the old copy of c] */
      85      119377 :       MP_ZERO_DIGITS(tmpc, olduse - ix);
      86             :    }
      87      119377 :    mp_clamp(c);
      88      119377 :    return MP_OKAY;
      89             : }
      90             : #endif