1#include <tommath.h> 2#ifdef BN_MP_DIV_D_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 18static int s_is_power_of_two(mp_digit b, int *p) 19{ 20 int x; 21 22 /* fast return if no power of two */ 23 if ((b==0) || (b & (b-1))) { 24 return 0; 25 } 26 27 for (x = 0; x < DIGIT_BIT; x++) { 28 if (b == (((mp_digit)1)<<x)) { 29 *p = x; 30 return 1; 31 } 32 } 33 return 0; 34} 35 36/* single digit division (based on routine from MPI) */ 37int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d) 38{ 39 mp_int q; 40 mp_word w; 41 mp_digit t; 42 int res, ix; 43 44 /* cannot divide by zero */ 45 if (b == 0) { 46 return MP_VAL; 47 } 48 49 /* quick outs */ 50 if (b == 1 || mp_iszero(a) == 1) { 51 if (d != NULL) { 52 *d = 0; 53 } 54 if (c != NULL) { 55 return mp_copy(a, c); 56 } 57 return MP_OKAY; 58 } 59 60 /* power of two ? */ 61 if (s_is_power_of_two(b, &ix) == 1) { 62 if (d != NULL) { 63 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1); 64 } 65 if (c != NULL) { 66 return mp_div_2d(a, ix, c, NULL); 67 } 68 return MP_OKAY; 69 } 70 71#ifdef BN_MP_DIV_3_C 72 /* three? */ 73 if (b == 3) { 74 return mp_div_3(a, c, d); 75 } 76#endif 77 78 /* no easy answer [c'est la vie]. Just division */ 79 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 80 return res; 81 } 82 83 q.used = a->used; 84 q.sign = a->sign; 85 w = 0; 86 for (ix = a->used - 1; ix >= 0; ix--) { 87 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]); 88 89 if (w >= b) { 90 t = (mp_digit)(w / b); 91 w -= ((mp_word)t) * ((mp_word)b); 92 } else { 93 t = 0; 94 } 95 q.dp[ix] = (mp_digit)t; 96 } 97 98 if (d != NULL) { 99 *d = (mp_digit)w; 100 } 101 102 if (c != NULL) { 103 mp_clamp(&q); 104 mp_exch(&q, c); 105 } 106 mp_clear(&q); 107 108 return res; 109} 110 111#endif 112 113/* $Source: /cvs/libtom/libtommath/bn_mp_div_d.c,v $ */ 114/* $Revision: 1.5 $ */ 115/* $Date: 2007/01/09 04:44:32 $ */ 116