kc3-lang/libtommath/s_mp_mul_high_digs_fast.c

• Show log

  Commit

• Hash : 7a68f128
  Author :
  Date : 2019-10-19T16:24:39
  

  Execute move.sh - Rename files from bn_* to match the function names. * git blame <renamed-file> is not affected * git log --follow <renamed-file> can be used to show log across renames

Download

• s_mp_mul_high_digs_fast.c

• #include "tommath_private.h"
  #ifdef S_MP_MUL_HIGH_DIGS_FAST_C
  /* LibTomMath, multiple-precision integer library -- Tom St Denis */
  /* SPDX-License-Identifier: Unlicense */
  
  /* this is a modified version of fast_s_mul_digs that only produces
   * output digits *above* digs.  See the comments for fast_s_mul_digs
   * to see how it works.
   *
   * This is used in the Barrett reduction since for one of the multiplications
   * only the higher digits were needed.  This essentially halves the work.
   *
   * Based on Algorithm 14.12 on pp.595 of HAC.
   */
  mp_err s_mp_mul_high_digs_fast(const mp_int *a, const mp_int *b, mp_int *c, int digs)
  {
     int     olduse, pa, ix, iz;
     mp_err   err;
     mp_digit W[MP_WARRAY];
     mp_word  _W;
  
     /* grow the destination as required */
     pa = a->used + b->used;
     if (c->alloc < pa) {
        if ((err = mp_grow(c, pa)) != MP_OKAY) {
           return err;
        }
     }
  
     /* number of output digits to produce */
     pa = a->used + b->used;
     _W = 0;
     for (ix = digs; ix < pa; ix++) {
        int      tx, ty, iy;
        mp_digit *tmpx, *tmpy;
  
        /* get offsets into the two bignums */
        ty = MP_MIN(b->used-1, ix);
        tx = ix - ty;
  
        /* setup temp aliases */
        tmpx = a->dp + tx;
        tmpy = b->dp + ty;
  
        /* this is the number of times the loop will iterrate, essentially its
           while (tx++ < a->used && ty-- >= 0) { ... }
         */
        iy = MP_MIN(a->used-tx, ty+1);
  
        /* execute loop */
        for (iz = 0; iz < iy; iz++) {
           _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
        }
  
        /* store term */
        W[ix] = (mp_digit)_W & MP_MASK;
  
        /* make next carry */
        _W = _W >> (mp_word)MP_DIGIT_BIT;
     }
  
     /* setup dest */
     olduse  = c->used;
     c->used = pa;
  
     {
        mp_digit *tmpc;
  
        tmpc = c->dp + digs;
        for (ix = digs; ix < pa; ix++) {
           /* now extract the previous digit [below the carry] */
           *tmpc++ = W[ix];
        }
  
        /* clear unused digits [that existed in the old copy of c] */
        MP_ZERO_DIGITS(tmpc, olduse - ix);
     }
     mp_clamp(c);
     return MP_OKAY;
  }
  #endif
  

Download