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