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