Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_S_MP_MUL_HIGH_DIGS_FAST_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* this is a modified version of fast_s_mul_digs that only produces
       7             :  * output digits *above* digs.  See the comments for fast_s_mul_digs
       8             :  * to see how it works.
       9             :  *
      10             :  * This is used in the Barrett reduction since for one of the multiplications
      11             :  * only the higher digits were needed.  This essentially halves the work.
      12             :  *
      13             :  * Based on Algorithm 14.12 on pp.595 of HAC.
      14             :  */
      15           0 : mp_err s_mp_mul_high_digs_fast(const mp_int *a, const mp_int *b, mp_int *c, int digs)
      16             : {
      17             :    int     olduse, pa, ix, iz;
      18             :    mp_err   err;
      19             :    mp_digit W[MP_WARRAY];
      20             :    mp_word  _W;
      21             : 
      22             :    /* grow the destination as required */
      23           0 :    pa = a->used + b->used;
      24           0 :    if (c->alloc < pa) {
      25           0 :       if ((err = mp_grow(c, pa)) != MP_OKAY) {
      26           0 :          return err;
      27             :       }
      28             :    }
      29             : 
      30             :    /* number of output digits to produce */
      31           0 :    pa = a->used + b->used;
      32           0 :    _W = 0;
      33           0 :    for (ix = digs; ix < pa; ix++) {
      34             :       int      tx, ty, iy;
      35             :       mp_digit *tmpx, *tmpy;
      36             : 
      37             :       /* get offsets into the two bignums */
      38           0 :       ty = MP_MIN(b->used-1, ix);
      39           0 :       tx = ix - ty;
      40             : 
      41             :       /* setup temp aliases */
      42           0 :       tmpx = a->dp + tx;
      43           0 :       tmpy = b->dp + ty;
      44             : 
      45             :       /* this is the number of times the loop will iterrate, essentially its
      46             :          while (tx++ < a->used && ty-- >= 0) { ... }
      47             :        */
      48           0 :       iy = MP_MIN(a->used-tx, ty+1);
      49             : 
      50             :       /* execute loop */
      51           0 :       for (iz = 0; iz < iy; iz++) {
      52           0 :          _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
      53             :       }
      54             : 
      55             :       /* store term */
      56           0 :       W[ix] = (mp_digit)_W & MP_MASK;
      57             : 
      58             :       /* make next carry */
      59           0 :       _W = _W >> (mp_word)MP_DIGIT_BIT;
      60             :    }
      61             : 
      62             :    /* setup dest */
      63           0 :    olduse  = c->used;
      64           0 :    c->used = pa;
      65             : 
      66             :    {
      67             :       mp_digit *tmpc;
      68             : 
      69           0 :       tmpc = c->dp + digs;
      70           0 :       for (ix = digs; ix < pa; ix++) {
      71             :          /* now extract the previous digit [below the carry] */
      72           0 :          *tmpc++ = W[ix];
      73             :       }
      74             : 
      75             :       /* clear unused digits [that existed in the old copy of c] */
      76           0 :       MP_ZERO_DIGITS(tmpc, olduse - ix);
      77             :    }
      78           0 :    mp_clamp(c);
      79           0 :    return MP_OKAY;
      80             : }
      81             : #endif