libs/libtommath/bn_mp_div_3.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_DIV_3_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 /* divide by three (based on routine from MPI and the GMP manual) */
  19 int
  20 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
  21 {
  22   mp_int   q;
  23   mp_word  w, t;
  24   mp_digit b;
  25   int      res, ix;
  26
  27   /* b = 2**DIGIT_BIT / 3 */
  28   b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);
  29
  30   if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
  31      return res;
  32   }
  33
  34   q.used = a->used;
  35   q.sign = a->sign;
  36   w = 0;
  37   for (ix = a->used - 1; ix >= 0; ix--) {
  38      w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
  39
  40      if (w >= 3) {
  41         /* multiply w by [1/3] */
  42         t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);
  43
  44         /* now subtract 3 * [w/3] from w, to get the remainder */
  45         w -= t+t+t;
  46
  47         /* fixup the remainder as required since
  48          * the optimization is not exact.
  49          */
  50         while (w >= 3) {
  51            t += 1;
  52            w -= 3;
  53         }
  54       } else {
  55         t = 0;
  56       }
  57       q.dp[ix] = (mp_digit)t;
  58   }
  59
  60   /* [optional] store the remainder */
  61   if (d != NULL) {
  62      *d = (mp_digit)w;
  63   }
  64
  65   /* [optional] store the quotient */
  66   if (c != NULL) {
  67      mp_clamp(&q);
  68      mp_exch(&q, c);
  69   }
  70   mp_clear(&q);
  71
  72   return res;
  73 }
  74
  75 #endif
  76
  77 /* $Source: /cvs/libtom/libtommath/bn_mp_div_3.c,v $ */
  78 /* $Revision: 1.3 $ */
  79 /* $Date: 2006/03/31 14:18:44 $ */