lib/hcrypto/libtommath/bn_s_mp_mul_high_digs_fast.c

   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 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    if (digs < 0) {
  23       return MP_VAL;
  24    }
  25
  26    /* grow the destination as required */
  27    pa = a->used + b->used;
  28    if (c->alloc < pa) {
  29       if ((err = mp_grow(c, pa)) != MP_OKAY) {
  30          return err;
  31       }
  32    }
  33
  34    /* number of output digits to produce */
  35    pa = a->used + b->used;
  36    _W = 0;
  37    for (ix = digs; ix < pa; ix++) {
  38       int      tx, ty, iy;
  39       mp_digit *tmpx, *tmpy;
  40
  41       /* get offsets into the two bignums */
  42       ty = MP_MIN(b->used-1, ix);
  43       tx = ix - ty;
  44
  45       /* setup temp aliases */
  46       tmpx = a->dp + tx;
  47       tmpy = b->dp + ty;
  48
  49       /* this is the number of times the loop will iterrate, essentially its
  50          while (tx++ < a->used && ty-- >= 0) { ... }
  51        */
  52       iy = MP_MIN(a->used-tx, ty+1);
  53
  54       /* execute loop */
  55       for (iz = 0; iz < iy; iz++) {
  56          _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
  57       }
  58
  59       /* store term */
  60       W[ix] = (mp_digit)_W & MP_MASK;
  61
  62       /* make next carry */
  63       _W = _W >> (mp_word)MP_DIGIT_BIT;
  64    }
  65
  66    /* setup dest */
  67    olduse  = c->used;
  68    c->used = pa;
  69
  70    {
  71       mp_digit *tmpc;
  72
  73       tmpc = c->dp + digs;
  74       for (ix = digs; ix < pa; ix++) {
  75          /* now extract the previous digit [below the carry] */
  76          *tmpc++ = W[ix];
  77       }
  78
  79       /* clear unused digits [that existed in the old copy of c] */
  80       MP_ZERO_DIGITS(tmpc, olduse - ix);
  81    }
  82    mp_clamp(c);
  83    return MP_OKAY;
  84 }
  85 #endif