Line data    Source code

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