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

00001 #include <tommath.h>
00002 #ifdef BN_MP_DIV_3_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 /* divide by three (based on routine from MPI and the GMP manual) */
00019 int
00020 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
00021 {
00022   mp_int   q;
00023   mp_word  w, t;
00024   mp_digit b;
00025   int      res, ix;
00026   
00027   /* b = 2**DIGIT_BIT / 3 */
00028   b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);
00029 
00030   if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
00031      return res;
00032   }
00033   
00034   q.used = a->used;
00035   q.sign = a->sign;
00036   w = 0;
00037   for (ix = a->used - 1; ix >= 0; ix--) {
00038      w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
00039 
00040      if (w >= 3) {
00041         /* multiply w by [1/3] */
00042         t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);
00043 
00044         /* now subtract 3 * [w/3] from w, to get the remainder */
00045         w -= t+t+t;
00046 
00047         /* fixup the remainder as required since
00048          * the optimization is not exact.
00049          */
00050         while (w >= 3) {
00051            t += 1;
00052            w -= 3;
00053         }
00054       } else {
00055         t = 0;
00056       }
00057       q.dp[ix] = (mp_digit)t;
00058   }
00059 
00060   /* [optional] store the remainder */
00061   if (d != NULL) {
00062      *d = (mp_digit)w;
00063   }
00064 
00065   /* [optional] store the quotient */
00066   if (c != NULL) {
00067      mp_clamp(&q);
00068      mp_exch(&q, c);
00069   }
00070   mp_clear(&q);
00071   
00072   return res;
00073 }
00074 
00075 #endif
00076 
00077 /* $Source: /cvsroot/tcl/libtommath/bn_mp_div_3.c,v $ */
00078 /* $Revision: 1.1.1.3 $ */
00079 /* $Date: 2006/12/01 00:08:11 $ */