libs/libtommath/bn_s_mp_sub.c

   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@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 $ */