diff options
Diffstat (limited to 'libtommath/bn_mp_div.c')
| -rw-r--r-- | libtommath/bn_mp_div.c | 81 |
1 files changed, 42 insertions, 39 deletions
diff --git a/libtommath/bn_mp_div.c b/libtommath/bn_mp_div.c index af5c55d..3ca5d7f 100644 --- a/libtommath/bn_mp_div.c +++ b/libtommath/bn_mp_div.c @@ -1,4 +1,4 @@ -#include <tommath.h> +#include <tommath_private.h> #ifdef BN_MP_DIV_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * @@ -12,7 +12,7 @@ * The library is free for all purposes without any express * guarantee it works. * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + * Tom St Denis, tstdenis82@gmail.com, http://libtom.org */ #ifdef BN_MP_DIV_SMALL @@ -24,7 +24,7 @@ int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) int res, n, n2; /* is divisor zero ? */ - if (mp_iszero (b) == 1) { + if (mp_iszero (b) == MP_YES) { return MP_VAL; } @@ -40,9 +40,9 @@ int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) } return res; } - + /* init our temps */ - if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL) != MP_OKAY)) { + if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL)) != MP_OKAY) { return res; } @@ -50,7 +50,7 @@ int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) mp_set(&tq, 1); n = mp_count_bits(a) - mp_count_bits(b); if (((res = mp_abs(a, &ta)) != MP_OKAY) || - ((res = mp_abs(b, &tb)) != MP_OKAY) || + ((res = mp_abs(b, &tb)) != MP_OKAY) || ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) || ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) { goto LBL_ERR; @@ -71,7 +71,7 @@ int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) /* now q == quotient and ta == remainder */ n = a->sign; - n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG); + n2 = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; if (c != NULL) { mp_exch(c, &q); c->sign = (mp_iszero(c) == MP_YES) ? MP_ZPOS : n2; @@ -87,17 +87,17 @@ LBL_ERR: #else -/* integer signed division. +/* integer signed division. * c*b + d == a [e.g. a/b, c=quotient, d=remainder] * HAC pp.598 Algorithm 14.20 * - * Note that the description in HAC is horribly - * incomplete. For example, it doesn't consider - * the case where digits are removed from 'x' in - * the inner loop. It also doesn't consider the + * Note that the description in HAC is horribly + * incomplete. For example, it doesn't consider + * the case where digits are removed from 'x' in + * the inner loop. It also doesn't consider the * case that y has fewer than three digits, etc.. * - * The overall algorithm is as described as + * The overall algorithm is as described as * 14.20 from HAC but fixed to treat these cases. */ int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) @@ -106,7 +106,7 @@ int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) int res, n, t, i, norm, neg; /* is divisor zero ? */ - if (mp_iszero (b) == 1) { + if (mp_iszero (b) == MP_YES) { return MP_VAL; } @@ -187,51 +187,52 @@ int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) continue; } - /* step 3.1 if xi == yt then set q{i-t-1} to b-1, + /* step 3.1 if xi == yt then set q{i-t-1} to b-1, * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */ if (x.dp[i] == y.dp[t]) { - q.dp[i - t - 1] = ((((mp_digit)1) << DIGIT_BIT) - 1); + q.dp[(i - t) - 1] = ((((mp_digit)1) << DIGIT_BIT) - 1); } else { mp_word tmp; tmp = ((mp_word) x.dp[i]) << ((mp_word) DIGIT_BIT); tmp |= ((mp_word) x.dp[i - 1]); tmp /= ((mp_word) y.dp[t]); - if (tmp > (mp_word) MP_MASK) + if (tmp > (mp_word) MP_MASK) { tmp = MP_MASK; - q.dp[i - t - 1] = (mp_digit) (tmp & (mp_word) (MP_MASK)); + } + q.dp[(i - t) - 1] = (mp_digit) (tmp & (mp_word) (MP_MASK)); } - /* while (q{i-t-1} * (yt * b + y{t-1})) > - xi * b**2 + xi-1 * b + xi-2 - - do q{i-t-1} -= 1; + /* while (q{i-t-1} * (yt * b + y{t-1})) > + xi * b**2 + xi-1 * b + xi-2 + + do q{i-t-1} -= 1; */ - q.dp[i - t - 1] = (q.dp[i - t - 1] + 1) & MP_MASK; + q.dp[(i - t) - 1] = (q.dp[(i - t) - 1] + 1) & MP_MASK; do { - q.dp[i - t - 1] = (q.dp[i - t - 1] - 1) & MP_MASK; + q.dp[(i - t) - 1] = (q.dp[(i - t) - 1] - 1) & MP_MASK; /* find left hand */ mp_zero (&t1); - t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1]; + t1.dp[0] = ((t - 1) < 0) ? 0 : y.dp[t - 1]; t1.dp[1] = y.dp[t]; t1.used = 2; - if ((res = mp_mul_d (&t1, q.dp[i - t - 1], &t1)) != MP_OKAY) { + if ((res = mp_mul_d (&t1, q.dp[(i - t) - 1], &t1)) != MP_OKAY) { goto LBL_Y; } /* find right hand */ - t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2]; - t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1]; + t2.dp[0] = ((i - 2) < 0) ? 0 : x.dp[i - 2]; + t2.dp[1] = ((i - 1) < 0) ? 0 : x.dp[i - 1]; t2.dp[2] = x.dp[i]; t2.used = 3; } while (mp_cmp_mag(&t1, &t2) == MP_GT); /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */ - if ((res = mp_mul_d (&y, q.dp[i - t - 1], &t1)) != MP_OKAY) { + if ((res = mp_mul_d (&y, q.dp[(i - t) - 1], &t1)) != MP_OKAY) { goto LBL_Y; } - if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) { + if ((res = mp_lshd (&t1, (i - t) - 1)) != MP_OKAY) { goto LBL_Y; } @@ -244,23 +245,23 @@ int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) if ((res = mp_copy (&y, &t1)) != MP_OKAY) { goto LBL_Y; } - if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) { + if ((res = mp_lshd (&t1, (i - t) - 1)) != MP_OKAY) { goto LBL_Y; } if ((res = mp_add (&x, &t1, &x)) != MP_OKAY) { goto LBL_Y; } - q.dp[i - t - 1] = (q.dp[i - t - 1] - 1UL) & MP_MASK; + q.dp[(i - t) - 1] = (q.dp[(i - t) - 1] - 1UL) & MP_MASK; } } - /* now q is the quotient and x is the remainder - * [which we have to normalize] + /* now q is the quotient and x is the remainder + * [which we have to normalize] */ - + /* get sign before writing to c */ - x.sign = x.used == 0 ? MP_ZPOS : a->sign; + x.sign = (x.used == 0) ? MP_ZPOS : a->sign; if (c != NULL) { mp_clamp (&q); @@ -269,7 +270,9 @@ int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) } if (d != NULL) { - mp_div_2d (&x, norm, &x, NULL); + if ((res = mp_div_2d (&x, norm, &x, NULL)) != MP_OKAY) { + goto LBL_Y; + } mp_exch (&x, d); } @@ -288,5 +291,5 @@ LBL_Q:mp_clear (&q); #endif /* $Source$ */ -/* $Revision: 0.41 $ */ -/* $Date: 2007-04-18 09:58:18 +0000 $ */ +/* $Revision$ */ +/* $Date$ */ |