lib/hcrypto/libtommath/bn_s_mp_mul_digs_fast.c

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