userapps/opensource/sshd/libtommath/bn_s_mp_mul_high_digs.c

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   2  *
   3  * LibTomMath is library that provides for multiple-precision
   4  * integer arithmetic as well as number theoretic functionality.
   5  *
   6  * The library is designed directly after the MPI library by
   7  * Michael Fromberger but has been written from scratch with
   8  * additional optimizations in place.
   9  *
  10  * The library is free for all purposes without any express
  11  * guarantee it works.
  12  *
  13  * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
  14  */
  15 #include <tommath.h>
  16
  17 /* multiplies |a| * |b| and does not compute the lower digs digits
  18  * [meant to get the higher part of the product]
  19  */
  20 int
  21 s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
  22 {
  23   mp_int  t;
  24   int     res, pa, pb, ix, iy;
  25   mp_digit u;
  26   mp_word r;
  27   mp_digit tmpx, *tmpt, *tmpy;
  28
  29
  30   /* can we use the fast multiplier? */
  31   if (((a->used + b->used + 1) < MP_WARRAY)
  32       && MIN (a->used, b->used) < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
  33     return fast_s_mp_mul_high_digs (a, b, c, digs);
  34   }
  35
  36   if ((res = mp_init_size (&t, a->used + b->used + 1)) != MP_OKAY) {
  37     return res;
  38   }
  39   t.used = a->used + b->used + 1;
  40
  41   pa = a->used;
  42   pb = b->used;
  43   for (ix = 0; ix < pa; ix++) {
  44     /* clear the carry */
  45     u = 0;
  46
  47     /* left hand side of A[ix] * B[iy] */
  48     tmpx = a->dp[ix];
  49
  50     /* alias to the address of where the digits will be stored */
  51     tmpt = &(t.dp[digs]);
  52
  53     /* alias for where to read the right hand side from */
  54     tmpy = b->dp + (digs - ix);
  55
  56     for (iy = digs - ix; iy < pb; iy++) {
  57       /* calculate the double precision result */
  58       r = ((mp_word) * tmpt) + ((mp_word) tmpx) * ((mp_word) * tmpy++) + ((mp_word) u);
  59
  60       /* get the lower part */
  61       *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
  62
  63       /* carry the carry */
  64       u = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
  65     }
  66     *tmpt = u;
  67   }
  68   mp_clamp (&t);
  69   mp_exch (&t, c);
  70   mp_clear (&t);
  71   return MP_OKAY;
  72 }