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 (at) 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 $ */ 80
