/home/ntakagi/work/tcl8.5.1/libtommath/bn_mp_div_d.c Source File

00001 #include <tommath.h>
00002 #ifdef BN_MP_DIV_D_C
00003 /* LibTomMath, multiple-precision integer library -- Tom St Denis
00004  *
00005  * LibTomMath is a library that provides multiple-precision
00006  * integer arithmetic as well as number theoretic functionality.
00007  *
00008  * The library was designed directly after the MPI library by
00009  * Michael Fromberger but has been written from scratch with
00010  * additional optimizations in place.
00011  *
00012  * The library is free for all purposes without any express
00013  * guarantee it works.
00014  *
00015  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
00016  */
00017 
00018 static int s_is_power_of_two(mp_digit b, int *p)
00019 {
00020    int x;
00021 
00022    /* quick out - if (b & (b-1)) isn't zero, b isn't a power of two */
00023    if ((b & (b-1)) != 0) {
00024        return 0;
00025    }
00026    for (x = 1; x < DIGIT_BIT; x++) {
00027       if (b == (((mp_digit)1)<<x)) {
00028          *p = x;
00029          return 1;
00030       }
00031    }
00032    return 0;
00033 }
00034 
00035 /* single digit division (based on routine from MPI) */
00036 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
00037 {
00038   mp_int  q;
00039   mp_word w;
00040   mp_digit t;
00041   int     res, ix;
00042 
00043   /* cannot divide by zero */
00044   if (b == 0) {
00045      return MP_VAL;
00046   }
00047 
00048   /* quick outs */
00049   if (b == 1 || mp_iszero(a) == 1) {
00050      if (d != NULL) {
00051         *d = 0;
00052      }
00053      if (c != NULL) {
00054         return mp_copy(a, c);
00055      }
00056      return MP_OKAY;
00057   }
00058 
00059   /* power of two ? */
00060   if (s_is_power_of_two(b, &ix) == 1) {
00061      if (d != NULL) {
00062         *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
00063      }
00064      if (c != NULL) {
00065         return mp_div_2d(a, ix, c, NULL);
00066      }
00067      return MP_OKAY;
00068   }
00069 
00070 #ifdef BN_MP_DIV_3_C
00071   /* three? */
00072   if (b == 3) {
00073      return mp_div_3(a, c, d);
00074   }
00075 #endif
00076 
00077   /* no easy answer [c'est la vie].  Just division */
00078   if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
00079      return res;
00080   }
00081   
00082   q.used = a->used;
00083   q.sign = a->sign;
00084   w = 0;
00085   for (ix = a->used - 1; ix >= 0; ix--) {
00086      w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
00087      
00088      if (w >= b) {
00089         t = (mp_digit)(w / b);
00090         w -= ((mp_word)t) * ((mp_word)b);
00091       } else {
00092         t = 0;
00093       }
00094       q.dp[ix] = (mp_digit)t;
00095   }
00096   
00097   if (d != NULL) {
00098      *d = (mp_digit)w;
00099   }
00100   
00101   if (c != NULL) {
00102      mp_clamp(&q);
00103      mp_exch(&q, c);
00104   }
00105   mp_clear(&q);
00106   
00107   return res;
00108 }
00109 
00110 #endif
00111 
00112 /* $Source: /cvsroot/tcl/libtommath/bn_mp_div_d.c,v $ */
00113 /* $Revision: 1.3 $ */
00114 /* $Date: 2006/12/01 05:47:47 $ */