Line data    Source code

       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://libtom.org
      16             :  */
      17             : 
      18             : /* low level addition, based on HAC pp.594, Algorithm 14.7 */
      19             : int
      20      350416 : 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      350416 :   if (a->used > b->used) {
      29        4319 :     min = b->used;
      30        4319 :     max = a->used;
      31        4319 :     x = a;
      32             :   } else {
      33      346088 :     min = a->used;
      34      346088 :     max = b->used;
      35      346088 :     x = b;
      36             :   }
      37             : 
      38             :   /* init result */
      39      350416 :   if (c->alloc < max + 1) {
      40        1837 :     if ((res = mp_grow (c, max + 1)) != MP_OKAY) {
      41           0 :       return res;
      42             :     }
      43             :   }
      44             : 
      45             :   /* get old used digit count and set new one */
      46      350416 :   olduse = c->used;
      47      350416 :   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      350416 :     tmpa = a->dp;
      57             : 
      58             :     /* second input */
      59      350416 :     tmpb = b->dp;
      60             : 
      61             :     /* destination */
      62      350416 :     tmpc = c->dp;
      63             : 
      64             :     /* zero the carry */
      65      350416 :     u = 0;
      66    21496934 :     for (i = 0; i < min; i++) {
      67             :       /* Compute the sum at one digit, T[i] = A[i] + B[i] + U */
      68    21146518 :       *tmpc = *tmpa++ + *tmpb++ + u;
      69             : 
      70             :       /* U = carry bit of T[i] */
      71    21146518 :       u = *tmpc >> ((mp_digit)DIGIT_BIT);
      72             : 
      73             :       /* take away carry bit from T[i] */
      74    21146518 :       *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      350416 :     if (min != max) {
      81      456251 :       for (; i < max; i++) {
      82             :         /* T[i] = X[i] + U */
      83      441789 :         *tmpc = x->dp[i] + u;
      84             : 
      85             :         /* U = carry bit of T[i] */
      86      441789 :         u = *tmpc >> ((mp_digit)DIGIT_BIT);
      87             : 
      88             :         /* take away carry bit from T[i] */
      89      441789 :         *tmpc++ &= MP_MASK;
      90             :       }
      91             :     }
      92             : 
      93             :     /* add carry */
      94      350416 :     *tmpc++ = u;
      95             : 
      96             :     /* clear digits above oldused */
      97      350416 :     for (i = c->used; i < olduse; i++) {
      98           0 :       *tmpc++ = 0;
      99             :     }
     100             :   }
     101             : 
     102      350416 :   mp_clamp (c);
     103      350416 :   return MP_OKAY;
     104             : }
     105             : #endif
     106             : 
     107             : /* $Source: /cvs/libtom/libtommath/bn_s_mp_add.c,v $ */
     108             : /* $Revision: 1.4 $ */
     109             : /* $Date: 2006/12/28 01:25:13 $ */