3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
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.
12 * The library is free for all purposes without any express
15 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
18 static int s_is_power_of_two(mp_digit b, int *p)
22 for (x = 1; x < DIGIT_BIT; x++) {
23 if (b == (((mp_digit)1)<<x)) {
31 /* single digit division (based on routine from MPI) */
32 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
39 /* cannot divide by zero */
45 if (b == 1 || mp_iszero(a) == 1) {
56 if (s_is_power_of_two(b, &ix) == 1) {
58 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
61 return mp_div_2d(a, ix, c, NULL);
69 return mp_div_3(a, c, d);
73 /* no easy answer [c'est la vie]. Just division */
74 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
81 for (ix = a->used - 1; ix >= 0; ix--) {
82 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
85 t = (mp_digit)(w / b);
86 w -= ((mp_word)t) * ((mp_word)b);
90 q.dp[ix] = (mp_digit)t;