release/src/router/dropbear/libtommath/bn_s_mp_add.c

   1 #include <tommath.h>
   2 #ifdef BN_S_MP_ADD_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   4  *
   5  * LibTomMath is a library that provides multiple-precision
   6  * integer arithmetic as well as number theoretic functionality.
   7  *
   8  * The library was designed directly after the MPI library by
   9  * Michael Fromberger but has been written from scratch with
  10  * additional optimizations in place.
  11  *
  12  * The library is free for all purposes without any express
  13  * guarantee it works.
  14  *
  15  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
  16  */
  17
  18 /* low level addition, based on HAC pp.594, Algorithm 14.7 */
  19 int
  20 s_mp_add (mp_int * a, mp_int * b, mp_int * c)
  21 {
  22   mp_int *x;
  23   int     olduse, res, min, max;
  24
  25   /* find sizes, we let |a| <= |b| which means we have to sort
  26    * them.  "x" will point to the input with the most digits
  27    */
  28   if (a->used > b->used) {
  29     min = b->used;
  30     max = a->used;
  31     x = a;
  32   } else {
  33     min = a->used;
  34     max = b->used;
  35     x = b;
  36   }
  37
  38   /* init result */
  39   if (c->alloc < max + 1) {
  40     if ((res = mp_grow (c, max + 1)) != MP_OKAY) {
  41       return res;
  42     }
  43   }
  44
  45   /* get old used digit count and set new one */
  46   olduse = c->used;
  47   c->used = max + 1;
  48
  49   {
  50     register mp_digit u, *tmpa, *tmpb, *tmpc;
  51     register int i;
  52
  53     /* alias for digit pointers */
  54
  55     /* first input */
  56     tmpa = a->dp;
  57
  58     /* second input */
  59     tmpb = b->dp;
  60
  61     /* destination */
  62     tmpc = c->dp;
  63
  64     /* zero the carry */
  65     u = 0;
  66     for (i = 0; i < min; i++) {
  67       /* Compute the sum at one digit, T[i] = A[i] + B[i] + U */
  68       *tmpc = *tmpa++ + *tmpb++ + u;
  69
  70       /* U = carry bit of T[i] */
  71       u = *tmpc >> ((mp_digit)DIGIT_BIT);
  72
  73       /* take away carry bit from T[i] */
  74       *tmpc++ &= MP_MASK;
  75     }
  76
  77     /* now copy higher words if any, that is in A+B
  78      * if A or B has more digits add those in
  79      */
  80     if (min != max) {
  81       for (; i < max; i++) {
  82         /* T[i] = X[i] + U */
  83         *tmpc = x->dp[i] + u;
  84
  85         /* U = carry bit of T[i] */
  86         u = *tmpc >> ((mp_digit)DIGIT_BIT);
  87
  88         /* take away carry bit from T[i] */
  89         *tmpc++ &= MP_MASK;
  90       }
  91     }
  92
  93     /* add carry */
  94     *tmpc++ = u;
  95
  96     /* clear digits above oldused */
  97     for (i = c->used; i < olduse; i++) {
  98       *tmpc++ = 0;
  99     }
 100   }
 101
 102   mp_clamp (c);
 103   return MP_OKAY;
 104 }
 105 #endif
 106
 107 /* $Source: /cvs/libtom/libtommath/bn_s_mp_add.c,v $ */
 108 /* $Revision: 1.3 $ */
 109 /* $Date: 2006/03/31 14:18:44 $ */