fp_div_d.c

00001 /* TomsFastMath, a fast ISO C bignum library.
00002  * 
00003  * This project is meant to fill in where LibTomMath
00004  * falls short.  That is speed ;-)
00005  *
00006  * This project is public domain and free for all purposes.
00007  * 
00008  * Tom St Denis, tomstdenis@gmail.com
00009  */
00010 #include <tfm.h>
00011 
00012 static int s_is_power_of_two(fp_digit b, int *p)
00013 {
00014    int x;
00015 
00016    /* fast return if no power of two */
00017    if ((b==0) || (b & (b-1))) {
00018       return 0;
00019    }
00020 
00021    for (x = 0; x < DIGIT_BIT; x++) {
00022       if (b == (((fp_digit)1)<<x)) {
00023          *p = x;
00024          return 1;
00025       }
00026    }
00027    return 0;
00028 }
00029 
00030 /* a/b => cb + d == a */
00031 int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d)
00032 {
00033   fp_int   q;
00034   fp_word  w;
00035   fp_digit t;
00036   int      ix;
00037 
00038   /* cannot divide by zero */
00039   if (b == 0) {
00040      return FP_VAL;
00041   }
00042 
00043   /* quick outs */
00044   if (b == 1 || fp_iszero(a) == 1) {
00045      if (d != NULL) {
00046         *d = 0;
00047      }
00048      if (c != NULL) {
00049         fp_copy(a, c);
00050      }
00051      return FP_OKAY;
00052   }
00053 
00054   /* power of two ? */
00055   if (s_is_power_of_two(b, &ix) == 1) {
00056      if (d != NULL) {
00057         *d = a->dp[0] & ((((fp_digit)1)<<ix) - 1);
00058      }
00059      if (c != NULL) {
00060         fp_div_2d(a, ix, c, NULL);
00061      }
00062      return FP_OKAY;
00063   }
00064 
00065   /* no easy answer [c'est la vie].  Just division */
00066   fp_init(&q);
00067   
00068   q.used = a->used;
00069   q.sign = a->sign;
00070   w = 0;
00071   for (ix = a->used - 1; ix >= 0; ix--) {
00072      w = (w << ((fp_word)DIGIT_BIT)) | ((fp_word)a->dp[ix]);
00073      
00074      if (w >= b) {
00075         t = (fp_digit)(w / b);
00076         w -= ((fp_word)t) * ((fp_word)b);
00077       } else {
00078         t = 0;
00079       }
00080       q.dp[ix] = (fp_digit)t;
00081   }
00082   
00083   if (d != NULL) {
00084      *d = (fp_digit)w;
00085   }
00086   
00087   if (c != NULL) {
00088      fp_clamp(&q);
00089      fp_copy(&q, c);
00090   }
00091  
00092   return FP_OKAY;
00093 }
00094 
00095 
00096 /* $Source: /cvs/libtom/tomsfastmath/src/divide/fp_div_d.c,v $ */
00097 /* $Revision: 1.2 $ */
00098 /* $Date: 2007/01/12 15:13:54 $ */