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

   1 #include <tommath.h>
   2 #ifdef BN_MP_DIV_D_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 static int s_is_power_of_two(mp_digit b, int *p)
  19 {
  20    int x;
  21
  22    for (x = 1; x < DIGIT_BIT; x++) {
  23       if (b == (((mp_digit)1)<<x)) {
  24          *p = x;
  25          return 1;
  26       }
  27    }
  28    return 0;
  29 }
  30
  31 /* single digit division (based on routine from MPI) */
  32 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
  33 {
  34   mp_int  q;
  35   mp_word w;
  36   mp_digit t;
  37   int     res, ix;
  38
  39   /* cannot divide by zero */
  40   if (b == 0) {
  41      return MP_VAL;
  42   }
  43
  44   /* quick outs */
  45   if (b == 1 || mp_iszero(a) == 1) {
  46      if (d != NULL) {
  47         *d = 0;
  48      }
  49      if (c != NULL) {
  50         return mp_copy(a, c);
  51      }
  52      return MP_OKAY;
  53   }
  54
  55   /* power of two ? */
  56   if (s_is_power_of_two(b, &ix) == 1) {
  57      if (d != NULL) {
  58         *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
  59      }
  60      if (c != NULL) {
  61         return mp_div_2d(a, ix, c, NULL);
  62      }
  63      return MP_OKAY;
  64   }
  65
  66 #ifdef BN_MP_DIV_3_C
  67   /* three? */
  68   if (b == 3) {
  69      return mp_div_3(a, c, d);
  70   }
  71 #endif
  72
  73   /* no easy answer [c'est la vie].  Just division */
  74   if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
  75      return res;
  76   }
  77
  78   q.used = a->used;
  79   q.sign = a->sign;
  80   w = 0;
  81   for (ix = a->used - 1; ix >= 0; ix--) {
  82      w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
  83
  84      if (w >= b) {
  85         t = (mp_digit)(w / b);
  86         w -= ((mp_word)t) * ((mp_word)b);
  87       } else {
  88         t = 0;
  89       }
  90       q.dp[ix] = (mp_digit)t;
  91   }
  92
  93   if (d != NULL) {
  94      *d = (mp_digit)w;
  95   }
  96
  97   if (c != NULL) {
  98      mp_clamp(&q);
  99      mp_exch(&q, c);
 100   }
 101   mp_clear(&q);
 102
 103   return res;
 104 }
 105
 106 #endif
 107
 108 /* $Source: /cvs/libtom/libtommath/bn_mp_div_d.c,v $ */
 109 /* $Revision: 1.3 $ */
 110 /* $Date: 2006/03/31 14:18:44 $ */