Home | History | Annotate | Download | only in libtommath 
      1 #include <tommath.h>
      2 #ifdef BN_S_MP_SUB_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 (at) gmail.com, http://math.libtomcrypt.com
     16  */
     17 
     18 /* low level subtraction (assumes |a| > |b|), HAC pp.595 Algorithm 14.9 */
     19 int
     20 s_mp_sub (mp_int * a, mp_int * b, mp_int * c)
     21 {
     22   int     olduse, res, min, max;
     23 
     24   /* find sizes */
     25   min = b->used;
     26   max = a->used;
     27 
     28   /* init result */
     29   if (c->alloc < max) {
     30     if ((res = mp_grow (c, max)) != MP_OKAY) {
     31       return res;
     32     }
     33   }
     34   olduse = c->used;
     35   c->used = max;
     36 
     37   {
     38     register mp_digit u, *tmpa, *tmpb, *tmpc;
     39     register int i;
     40 
     41     /* alias for digit pointers */
     42     tmpa = a->dp;
     43     tmpb = b->dp;
     44     tmpc = c->dp;
     45 
     46     /* set carry to zero */
     47     u = 0;
     48     for (i = 0; i < min; i++) {
     49       /* T[i] = A[i] - B[i] - U */
     50       *tmpc = *tmpa++ - *tmpb++ - u;
     51 
     52       /* U = carry bit of T[i]
     53        * Note this saves performing an AND operation since
     54        * if a carry does occur it will propagate all the way to the
     55        * MSB.  As a result a single shift is enough to get the carry
     56        */
     57       u = *tmpc >> ((mp_digit)(CHAR_BIT * sizeof (mp_digit) - 1));
     58 
     59       /* Clear carry from T[i] */
     60       *tmpc++ &= MP_MASK;
     61     }
     62 
     63     /* now copy higher words if any, e.g. if A has more digits than B  */
     64     for (; i < max; i++) {
     65       /* T[i] = A[i] - U */
     66       *tmpc = *tmpa++ - u;
     67 
     68       /* U = carry bit of T[i] */
     69       u = *tmpc >> ((mp_digit)(CHAR_BIT * sizeof (mp_digit) - 1));
     70 
     71       /* Clear carry from T[i] */
     72       *tmpc++ &= MP_MASK;
     73     }
     74 
     75     /* clear digits above used (since we may not have grown result above) */
     76     for (i = c->used; i < olduse; i++) {
     77       *tmpc++ = 0;
     78     }
     79   }
     80 
     81   mp_clamp (c);
     82   return MP_OKAY;
     83 }
     84 
     85 #endif
     86 
     87 /* $Source: /cvs/libtom/libtommath/bn_s_mp_sub.c,v $ */
     88 /* $Revision: 1.3 $ */
     89 /* $Date: 2006/03/31 14:18:44 $ */
     90