From e2b2a49eaf9b2b79351be7d294a10704a3e0061d Mon Sep 17 00:00:00 2001 From: Kevin B Kenny Date: Fri, 1 Dec 2006 00:31:32 +0000 Subject: Upgrade to tommath 0.39 plus patches from Tom --- libtommath/bn_mp_add.c | 5 +- libtommath/bn_mp_add_d.c | 4 +- libtommath/bn_mp_div.c | 154 +++++++++++++++++++++++++++++++++++++++++- libtommath/bn_mp_div_d.c | 8 ++- libtommath/bn_mp_radix_size.c | 6 +- libtommath/bn_mp_read_radix.c | 6 +- libtommath/bn_mp_sqrt.c | 7 +- libtommath/bncore.c | 7 +- libtommath/tommath.h | 7 +- libtommath/tommath_class.h | 8 ++- 10 files changed, 190 insertions(+), 22 deletions(-) diff --git a/libtommath/bn_mp_add.c b/libtommath/bn_mp_add.c index b7effdb..25ef75f 100644 --- a/libtommath/bn_mp_add.c +++ b/libtommath/bn_mp_add.c @@ -49,5 +49,6 @@ int mp_add (mp_int * a, mp_int * b, mp_int * c) #endif /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_add.c,v $ */ -/* $Revision: 1.1.1.3 $ */ -/* $Date: 2006/12/01 00:08:11 $ */ +/* Tom's version 1.3 */ +/* $Revision: 1.2 $ */ +/* $Date: 2006/12/01 00:31:32 $ */ diff --git a/libtommath/bn_mp_add_d.c b/libtommath/bn_mp_add_d.c index 38ae268..325b067 100644 --- a/libtommath/bn_mp_add_d.c +++ b/libtommath/bn_mp_add_d.c @@ -12,7 +12,7 @@ * The library is free for all purposes without any express * guarantee it works. * - * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org + * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com */ /* single digit addition */ @@ -110,3 +110,5 @@ mp_add_d (mp_int * a, mp_digit b, mp_int * c) /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_add_d.c,v $ */ /* Tom's revision is 1.2 */ +/* $Revision: 1.4 $ */ +/* $Date: 2006/12/01 00:31:32 $ */ diff --git a/libtommath/bn_mp_div.c b/libtommath/bn_mp_div.c index 4a94172..d1b5c48 100644 --- a/libtommath/bn_mp_div.c +++ b/libtommath/bn_mp_div.c @@ -87,6 +87,156 @@ LBL_ERR: #else +/* Integer signed division. + * + * c*b + d == a, that is, c = a/b and c = a%b + * + * This is a wrapper function that dispatches to various service + * functions that actually perform the division. + */ + +int mp_div(mp_int* a, mp_int* b, mp_int* c, mp_int* d) +{ + + int bitShift; /* Amount by which the divisor and + * dividend were scaled in the normalization + * step */ + mp_digit dig; + int res; + mp_int x, y, q; + + /* Division by zero is an error. */ + if (mp_iszero (b) == 1) { + return MP_VAL; + } + + /* If a < b, the quotient is zero, no need to divide. */ + if (mp_cmp_mag (a, b) == MP_LT) { + if (d != NULL) { + res = mp_copy (a, d); + } else { + res = MP_OKAY; + } + if (c != NULL) { + mp_zero (c); + } + return res; + } + + /* If the divisor has a single digit, then use short division + * to handle it. */ + + if (b->used == 1) { + mp_digit rem; + if ((res = mp_div_d(a, b->dp[0], c, &rem)) != MP_OKAY) { + return res; + } + if (a->sign != b->sign) { + c->sign = MP_NEG; + } else { + c->sign = MP_ZPOS; + } + if (d != NULL) { + d->dp[0] = rem; + d->used = 1; + d->sign = a->sign; + mp_clamp(d); + } + return MP_OKAY; + } + + /* Allocate temporary storage */ + + if ((res = mp_init_size(&q, a->used + 2 - b->used)) != MP_OKAY) { + return res; + } + if ((res = mp_init_copy(&x, a)) != MP_OKAY) { + goto LBL_Q; + } + if ((res = mp_init_copy(&y, b)) != MP_OKAY) { + goto LBL_X; + } + + /* Divisor is at least two digits. Prescale so that the divisor + * has 1 in its most significant bit. */ + + bitShift = 0; + dig = y->dp[y->used-1]; + while (dig < 1<<(DIGIT_BIT-1)) { + dig <<= 1; + ++bitShift; + } + if ((res = mp_mul_2d(&x, bitShift, &x)) != MP_OKAY + || (res = mp_mul_2d(&y, bitShift, &y)) != MP_OKAY) { + goto LBL_Y; + } + + /* Perform the division, leaving quotient in q and remainder in x */ + +#ifdef BN_S_MP_DIV_BZ_C + if (y->used > BZ_DIV_THRESHOLD) { + + /* Above the threshold of digits for Burnikel-Ziegler */ + + if ((res = bn_s_mp_div_bz(&x, &y, &q)) != MP_OKAY) { + goto LBL_Y; + } + + } else +#endif + { + /* Either Burnikel-Ziegler is not available, or the divisor has + * too few digits for it to be profitable. Hence, we shall use + * ordinary school division for this case. Accumulate the quotient + * in q, and leave the remainder in x. */ + + if ((res = bn_s_mp_div_school(&x, &y, &q)) != MP_OKAY) { + goto LBL_Y; + } + } + + /* Correct the sign of the remainder */ + + if (x->used == 0) { + x->sign = MP_ZPOS; + } else { + x->sign = a->sign; + } + + /* Store quotient, setting the correct sign */ + + if (c != NULL) { + mp_clamp(&q); + if (a->sign == b->sign) { + q->sign = MP_ZPOS; + } else { + q->sign = MP_NEG; + } + mp_exch(&q, c); + } + + /* Store remainder, copying the sign of a */ + + if (d != NULL) { + mp_div_2d(&x, bitShift, &x, NULL); + mp_exch(&x, d); + } + + res = MP_OKAY; + + /* Free memory */ + + LBL_Y: + mp_clear(&y); + LBL_X: + mp_clear(&x); + LBL_Q: + mp_clear(&q); + + return res; + +} + /* integer signed division. * c*b + d == a [e.g. a/b, c=quotient, d=remainder] * HAC pp.598 Algorithm 14.20 @@ -288,5 +438,5 @@ LBL_Q:mp_clear (&q); #endif /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div.c,v $ */ -/* $Revision: 1.1.1.3 $ */ -/* $Date: 2006/12/01 00:08:11 $ */ +/* $Revision: 1.2 $ */ +/* $Date: 2006/12/01 00:31:32 $ */ diff --git a/libtommath/bn_mp_div_d.c b/libtommath/bn_mp_div_d.c index 4f210e6..b12fb5c 100644 --- a/libtommath/bn_mp_div_d.c +++ b/libtommath/bn_mp_div_d.c @@ -19,6 +19,10 @@ static int s_is_power_of_two(mp_digit b, int *p) { int x; + /* quick out - if (b & (b-1)) isn't zero, b isn't a power of two */ + if ( b & (b-1) != 0 ) { + return 0; + } for (x = 1; x < DIGIT_BIT; x++) { if (b == (((mp_digit)1)<