pd.if.org Git - zpackage/blob - tomsfastmath/src/divide/fp_div_d.c

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@gmail.com
   9  */
  10 #include <tfm_private.h>
  11
  12 static int s_is_power_of_two(fp_digit b, int *p)
  13 {
  14    int x;
  15
  16    /* fast return if no power of two */
  17    if ((b==0) || (b & (b-1))) {
  18       return 0;
  19    }
  20
  21    for (x = 0; x < DIGIT_BIT; x++) {
  22       if (b == (((fp_digit)1)<<x)) {
  23          *p = x;
  24          return 1;
  25       }
  26    }
  27    return 0;
  28 }
  29
  30 /* a/b => cb + d == a */
  31 int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d)
  32 {
  33   fp_int   q;
  34   fp_word  w;
  35   fp_digit t;
  36   int      ix;
  37
  38   /* cannot divide by zero */
  39   if (b == 0) {
  40      return FP_VAL;
  41   }
  42
  43   /* quick outs */
  44   if (b == 1 || fp_iszero(a) == 1) {
  45      if (d != NULL) {
  46         *d = 0;
  47      }
  48      if (c != NULL) {
  49         fp_copy(a, c);
  50      }
  51      return FP_OKAY;
  52   }
  53
  54   /* power of two ? */
  55   if (s_is_power_of_two(b, &ix) == 1) {
  56      if (d != NULL) {
  57         *d = a->dp[0] & ((((fp_digit)1)<<ix) - 1);
  58      }
  59      if (c != NULL) {
  60         fp_div_2d(a, ix, c, NULL);
  61      }
  62      return FP_OKAY;
  63   }
  64
  65   /* no easy answer [c'est la vie].  Just division */
  66   fp_init(&q);
  67
  68   q.used = a->used;
  69   q.sign = a->sign;
  70   w = 0;
  71   for (ix = a->used - 1; ix >= 0; ix--) {
  72      w = (w << ((fp_word)DIGIT_BIT)) | ((fp_word)a->dp[ix]);
  73
  74      if (w >= b) {
  75         t = (fp_digit)(w / b);
  76         w -= ((fp_word)t) * ((fp_word)b);
  77       } else {
  78         t = 0;
  79       }
  80       q.dp[ix] = (fp_digit)t;
  81   }
  82
  83   if (d != NULL) {
  84      *d = (fp_digit)w;
  85   }
  86
  87   if (c != NULL) {
  88      fp_clamp(&q);
  89      fp_copy(&q, c);
  90   }
  91
  92   return FP_OKAY;
  93 }
  94
  95
  96 /* $Source$ */
  97 /* $Revision$ */
  98 /* $Date$ */