userapps/opensource/sshd/libtommath/bn_s_mp_sub.c

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   2  *
   3  * LibTomMath is library that provides for multiple-precision
   4  * integer arithmetic as well as number theoretic functionality.
   5  *
   6  * The library is designed directly after the MPI library by
   7  * Michael Fromberger but has been written from scratch with
   8  * additional optimizations in place.
   9  *
  10  * The library is free for all purposes without any express
  11  * guarantee it works.
  12  *
  13  * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
  14  */
  15 #include <tommath.h>
  16
  17 /* low level subtraction (assumes |a| > |b|), HAC pp.595 Algorithm 14.9 */
  18 int
  19 s_mp_sub (mp_int * a, mp_int * b, mp_int * c)
  20 {
  21   int     olduse, res, min, max;
  22
  23   /* find sizes */
  24   min = b->used;
  25   max = a->used;
  26
  27   /* init result */
  28   if (c->alloc < max) {
  29     if ((res = mp_grow (c, max)) != MP_OKAY) {
  30       return res;
  31     }
  32   }
  33   olduse = c->used;
  34   c->used = max;
  35
  36   {
  37     register mp_digit u, *tmpa, *tmpb, *tmpc;
  38     register int i;
  39
  40     /* alias for digit pointers */
  41     tmpa = a->dp;
  42     tmpb = b->dp;
  43     tmpc = c->dp;
  44
  45     /* set carry to zero */
  46     u = 0;
  47     for (i = 0; i < min; i++) {
  48       /* T[i] = A[i] - B[i] - U */
  49       *tmpc = *tmpa++ - *tmpb++ - u;
  50
  51       /* U = carry bit of T[i]
  52        * Note this saves performing an AND operation since
  53        * if a carry does occur it will propagate all the way to the
  54        * MSB.  As a result a single shift is enough to get the carry
  55        */
  56       u = *tmpc >> ((mp_digit)(CHAR_BIT * sizeof (mp_digit) - 1));
  57
  58       /* Clear carry from T[i] */
  59       *tmpc++ &= MP_MASK;
  60     }
  61
  62     /* now copy higher words if any, e.g. if A has more digits than B  */
  63     for (; i < max; i++) {
  64       /* T[i] = A[i] - U */
  65       *tmpc = *tmpa++ - u;
  66
  67       /* U = carry bit of T[i] */
  68       u = *tmpc >> ((mp_digit)(CHAR_BIT * sizeof (mp_digit) - 1));
  69
  70       /* Clear carry from T[i] */
  71       *tmpc++ &= MP_MASK;
  72     }
  73
  74     /* clear digits above used (since we may not have grown result above) */
  75     for (i = c->used; i < olduse; i++) {
  76       *tmpc++ = 0;
  77     }
  78   }
  79
  80   mp_clamp (c);
  81   return MP_OKAY;
  82 }
  83