{  int     oldused, newused, res, pa, pb, ix;  mp_word W[MP_WARRAY];  /* calculate size of product and allocate more space if required */  newused = a->used + b->used + 1;  if (c->alloc < newused) {    if ((res = mp_grow (c, newused)) != MP_OKAY) {      return res;    }  }  /* like the other comba method we compute the columns first */  pa = a->used;  pb = b->used;  memset (W + digs, 0, (pa + pb + 1 - digs) * sizeof (mp_word));  for (ix = 0; ix < pa; ix++) {    {      register mp_digit tmpx, *tmpy;      register int iy;      register mp_word *_W;      /* work todo, that is we only calculate digits that are at "digs" or above  */      iy = digs - ix;      /* copy of word on the left of A[ix] * B[iy] */      tmpx = a->dp[ix];      /* alias for right side */      tmpy = b->dp + iy;           /* alias for the columns of output.  Offset to be equal to or above the        * smallest digit place requested        */      _W = W + digs;                 /* skip cases below zero where ix > digs */      if (iy < 0) {         iy    = abs(iy);         tmpy += iy;         _W   += iy;         iy    = 0;      }      /* compute column products for digits above the minimum */      for (; iy < pb; iy++) {         *_W++ += ((mp_word) tmpx) * ((mp_word)*tmpy++);      }    }  }  /* setup dest */  oldused = c->used;  c->used = newused;  /* now convert the array W downto what we need   *   * See comments in bn_fast_s_mp_mul_digs.c   */  for (ix = digs + 1; ix < newused; ix++) {    W[ix] += (W[ix - 1] >> ((mp_word) DIGIT_BIT));    c->dp[ix - 1] = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK));  }  c->dp[newused - 1] = (mp_digit) (W[newused - 1] & ((mp_word) MP_MASK));  for (; ix < oldused; ix++) {    c->dp[ix] = 0;  }  mp_clamp (c);  return MP_OKAY;}/* End: bn_fast_s_mp_mul_high_digs.c *//* Start: bn_fast_s_mp_sqr.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* fast squaring * * This is the comba method where the columns of the product * are computed first then the carries are computed.  This * has the effect of making a very simple inner loop that * is executed the most * * W2 represents the outer products and W the inner. * * A further optimizations is made because the inner * products are of the form "A * B * 2".  The *2 part does * not need to be computed until the end which is good * because 64-bit shifts are slow! * * Based on Algorithm 14.16 on pp.597 of HAC. * */int fast_s_mp_sqr (mp_int * a, mp_int * b){  int     olduse, newused, res, ix, pa;  mp_word W2[MP_WARRAY], W[MP_WARRAY];  /* calculate size of product and allocate as required */  pa = a->used;  newused = pa + pa + 1;  if (b->alloc < newused) {    if ((res = mp_grow (b, newused)) != MP_OKAY) {      return res;    }  }  /* zero temp buffer (columns)   * Note that there are two buffers.  Since squaring requires   * a outer and inner product and the inner product requires   * computing a product and doubling it (a relatively expensive   * op to perform n**2 times if you don't have to) the inner and   * outer products are computed in different buffers.  This way   * the inner product can be doubled using n doublings instead of   * n**2   */  memset (W,  0, newused * sizeof (mp_word));  memset (W2, 0, newused * sizeof (mp_word));  /* This computes the inner product.  To simplify the inner N**2 loop   * the multiplication by two is done afterwards in the N loop.   */  for (ix = 0; ix < pa; ix++) {    /* compute the outer product     *     * Note that every outer product is computed     * for a particular column only once which means that     * there is no need todo a double precision addition     * into the W2[] array.     */    W2[ix + ix] = ((mp_word)a->dp[ix]) * ((mp_word)a->dp[ix]);    {      register mp_digit tmpx, *tmpy;      register mp_word *_W;      register int iy;      /* copy of left side */      tmpx = a->dp[ix];      /* alias for right side */      tmpy = a->dp + (ix + 1);      /* the column to store the result in */      _W = W + (ix + ix + 1);      /* inner products */      for (iy = ix + 1; iy < pa; iy++) {          *_W++ += ((mp_word)tmpx) * ((mp_word)*tmpy++);      }    }  }  /* setup dest */  olduse  = b->used;  b->used = newused;  /* now compute digits   *   * We have to double the inner product sums, add in the   * outer product sums, propagate carries and convert   * to single precision.   */  {    register mp_digit *tmpb;    /* double first value, since the inner products are     * half of what they should be     */    W[0] += W[0] + W2[0];    tmpb = b->dp;    for (ix = 1; ix < newused; ix++) {      /* double/add next digit */      W[ix] += W[ix] + W2[ix];      /* propagate carry forwards [from the previous digit] */      W[ix] = W[ix] + (W[ix - 1] >> ((mp_word) DIGIT_BIT));      /* store the current digit now that the carry isn't       * needed       */      *tmpb++ = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK));    }    /* set the last value.  Note even if the carry is zero     * this is required since the next step will not zero     * it if b originally had a value at b->dp[2*a.used]     */    *tmpb++ = (mp_digit) (W[(newused) - 1] & ((mp_word) MP_MASK));    /* clear high digits of b if there were any originally */    for (; ix < olduse; ix++) {      *tmpb++ = 0;    }  }  mp_clamp (b);  return MP_OKAY;}/* End: bn_fast_s_mp_sqr.c *//* Start: bn_mp_2expt.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* computes a = 2**b  * * Simple algorithm which zeroes the int, grows it then just sets one bit * as required. */intmp_2expt (mp_int * a, int b){  int     res;  /* zero a as per default */  mp_zero (a);  /* grow a to accomodate the single bit */  if ((res = mp_grow (a, b / DIGIT_BIT + 1)) != MP_OKAY) {    return res;  }  /* set the used count of where the bit will go */  a->used = b / DIGIT_BIT + 1;  /* put the single bit in its place */  a->dp[b / DIGIT_BIT] = 1 << (b % DIGIT_BIT);  return MP_OKAY;}/* End: bn_mp_2expt.c *//* Start: bn_mp_abs.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* b = |a|  * * Simple function copies the input and fixes the sign to positive */intmp_abs (mp_int * a, mp_int * b){  int     res;  /* copy a to b */  if (a != b) {     if ((res = mp_copy (a, b)) != MP_OKAY) {       return res;     }  }  /* force the sign of b to positive */  b->sign = MP_ZPOS;  return MP_OKAY;}/* End: bn_mp_abs.c *//* Start: bn_mp_add.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* high level addition (handles signs) */int mp_add (mp_int * a, mp_int * b, mp_int * c){  int     sa, sb, res;  /* get sign of both inputs */  sa = a->sign;  sb = b->sign;  /* handle two cases, not four */  if (sa == sb) {    /* both positive or both negative */    /* add their magnitudes, copy the sign */    c->sign = sa;    res = s_mp_add (a, b, c);  } else {    /* one positive, the other negative */    /* subtract the one with the greater magnitude from */    /* the one of the lesser magnitude.  The result gets */    /* the sign of the one with the greater magnitude. */    if (mp_cmp_mag (a, b) == MP_LT) {      c->sign = sb;      res = s_mp_sub (b, a, c);    } else {      c->sign = sa;      res = s_mp_sub (a, b, c);    }  }  return res;}/* End: bn_mp_add.c *//* Start: bn_mp_add_d.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* single digit addition */intmp_add_d (mp_int * a, mp_digit b, mp_int * c){  int     res, ix, oldused;  mp_digit *tmpa, *tmpc, mu;  /* grow c as required */  if (c->alloc < a->used + 1) {     if ((res = mp_grow(c, a->used + 1)) != MP_OKAY) {        return res;     }  }  /* if a is negative and |a| >= b, call c = |a| - b */  if (a->sign == MP_NEG && (a->used > 1 || a->dp[0] >= b)) {     /* temporarily fix sign of a */     a->sign = MP_ZPOS;     /* c = |a| - b */     res = mp_sub_d(a, b, c);     /* fix sign  */     a->sign = c->sign = MP_NEG;     return res;  }  /* old number of used digits in c */  oldused = c->used;  /* sign always positive */  c->sign = MP_ZPOS;  /* source alias */  tmpa    = a->dp;  /* destination alias */  tmpc    = c->dp;  /* if a is positive */  if (a->sign == MP_ZPOS) {     /* add digit, after this we're propagating      * the carry.      */     *tmpc   = *tmpa++ + b;     mu      = *tmpc >> DIGIT_BIT;     *tmpc++ &= MP_MASK;     /* now handle rest of the digits */     for (ix = 1; ix < a->used; ix++) {        *tmpc   = *tmpa++ + mu;        mu      = *tmpc >> DIGIT_BIT;        *tmpc++ &= MP_MASK;     }     /* set final carry */     ix++;     *tmpc++  = mu;     /* setup size */     c->used = a->used + 1;  } else {     /* a was negative and |a| < b */     c->used  = 1;     /* the result is a single digit */     if (a->used == 1) {        *tmpc++  =  b - a->dp[0];     } else {        *tmpc++  =  b;     }     /* setup count so the clearing of oldused      * can fall through correctly      */     ix       = 1;  }  /* now zero to oldused */  while (ix++ < oldused) {     *tmpc++ = 0;  }  mp_clamp(c);  return MP_OKAY;}/* End: bn_mp_add_d.c *//* Start: bn_mp_addmod.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* d = a + b (mod c) */intmp_addmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d){  int     res;  mp_int  t;  if ((res = mp_init (&t)) != MP_OKAY) {    return res;  }  if ((res = mp_add (a, b, &t)) != MP_OKAY) {    mp_clear (&t);    return res;  }  res = mp_mod (&t, c, d);  mp_clear (&t);  return res;}/* End: bn_mp_addmod.c *//* Start: bn_mp_and.c *//* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include <ltc_tommath.h>/* AND two ints together */intmp_and (mp_int * a, mp_int * b, mp_int * c){  int     res, ix, px;  mp_int  t, *x;