diff options
| -rw-r--r-- | ChangeLog | 7 | ||||
| -rw-r--r-- | libtommath/bn_mp_add.c | 5 | ||||
| -rw-r--r-- | libtommath/bn_mp_div.c | 156 | ||||
| -rw-r--r-- | libtommath/bncore.c | 7 | ||||
| -rw-r--r-- | libtommath/tommath_class.h | 8 |
5 files changed, 16 insertions, 167 deletions
@@ -1,3 +1,10 @@ +2006-12-01 Kevin Kenny <kennykb@acm.org> + + * libtommath/bn_mp_add.c: Corrected the effects of a + * libtommath/bn_mp_div.c: bollixed 'cvs merge' operation + * libtommath/bncore.c: that inadvertently committed some + * libtommath/tommath_class.h: half-developed code. + 2006-12-01 Don Porter <dgp@users.sourceforge.net> * tests/chan.test: Correct timing sensitivity in new test diff --git a/libtommath/bn_mp_add.c b/libtommath/bn_mp_add.c index 25ef75f..ab3bb87 100644 --- a/libtommath/bn_mp_add.c +++ b/libtommath/bn_mp_add.c @@ -49,6 +49,5 @@ 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 $ */ -/* Tom's version 1.3 */ -/* $Revision: 1.2 $ */ -/* $Date: 2006/12/01 00:31:32 $ */ +/* $Revision: 1.3 $ */ +/* $Date: 2006/12/01 19:45:38 $ */ diff --git a/libtommath/bn_mp_div.c b/libtommath/bn_mp_div.c index b80797f..ce6c255 100644 --- a/libtommath/bn_mp_div.c +++ b/libtommath/bn_mp_div.c @@ -87,158 +87,6 @@ LBL_ERR: #else -#if 0 -/* 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; - -} -#endif - /* integer signed division. * c*b + d == a [e.g. a/b, c=quotient, d=remainder] * HAC pp.598 Algorithm 14.20 @@ -440,5 +288,5 @@ LBL_Q:mp_clear (&q); #endif /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div.c,v $ */ -/* $Revision: 1.3 $ */ -/* $Date: 2006/12/01 15:55:45 $ */ +/* $Revision: 1.4 $ */ +/* $Date: 2006/12/01 19:45:38 $ */ diff --git a/libtommath/bncore.c b/libtommath/bncore.c index dcf093e..ac19aa6 100644 --- a/libtommath/bncore.c +++ b/libtommath/bncore.c @@ -24,8 +24,7 @@ */ -int BZ_DIV_CUTOFF = 30, /* Min. number of digits before Burnikel-Ziegler division is used. */ - KARATSUBA_MUL_CUTOFF = 80, /* Min. number of digits before Karatsuba multiplication is used. */ +int KARATSUBA_MUL_CUTOFF = 80, /* Min. number of digits before Karatsuba multiplication is used. */ KARATSUBA_SQR_CUTOFF = 120, /* Min. number of digits before Karatsuba squaring is used. */ TOOM_MUL_CUTOFF = 350, /* no optimal values of these are known yet so set em high */ @@ -33,5 +32,5 @@ int BZ_DIV_CUTOFF = 30, /* Min. number of digits before Burnikel #endif /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bncore.c,v $ */ -/* $Revision: 1.2 $ */ -/* $Date: 2006/12/01 00:31:32 $ */ +/* $Revision: 1.3 $ */ +/* $Date: 2006/12/01 19:45:38 $ */ diff --git a/libtommath/tommath_class.h b/libtommath/tommath_class.h index ebc5a60..649e823 100644 --- a/libtommath/tommath_class.h +++ b/libtommath/tommath_class.h @@ -20,7 +20,6 @@ #define BN_MP_ADD_D_C #define BN_MP_ADDMOD_C #define BN_MP_AND_C -#define BN_MP_BZ_DIV_C #define BN_MP_CLAMP_C #define BN_MP_CLEAR_C #define BN_MP_CLEAR_MULTI_C @@ -253,10 +252,7 @@ #define BN_MP_CMP_C #define BN_MP_SUB_C #define BN_MP_ADD_C - #define BN_MP_DIV_D_C #define BN_MP_DIV_2D_C - #define BN_S_MP_DIV_SCHOOL_C -/* #define BN_S_MP_DIV_BZ_C once I write this one! */ #define BN_MP_EXCH_C #define BN_MP_CLEAR_MULTI_C #define BN_MP_INIT_SIZE_C @@ -999,5 +995,5 @@ #endif /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/tommath_class.h,v $ */ -/* $Revision: 1.2 $ */ -/* $Date: 2006/12/01 00:31:32 $ */ +/* $Revision: 1.3 $ */ +/* $Date: 2006/12/01 19:45:39 $ */ |