Home | History | Annotate | Download | only in libtommath 
      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 (at) 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 $ */
    111