From dd22938ef0d9b0131dad9171a8a95866ceec9607 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 9 Oct 2002 00:36:03 +0000 Subject: [PATCH] Fix bounds on workspace for Karatsuba operations. --- gfx-kmul.c | 12 ++++++------ mp-arith.c | 25 ++++++++++++++----------- mpx-kmul.c | 24 ++++++++++++------------ mpx-ksqr.c | 24 ++++++++++++------------ mpx.h | 30 ++++++++++++------------------ 5 files changed, 56 insertions(+), 59 deletions(-) diff --git a/gfx-kmul.c b/gfx-kmul.c index dc2e524..f5390f4 100644 --- a/gfx-kmul.c +++ b/gfx-kmul.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: gfx-kmul.c,v 1.1 2000/10/08 15:49:37 mdw Exp $ + * $Id: gfx-kmul.c,v 1.2 2002/10/09 00:36:03 mdw Exp $ * * Karatsuba's multiplication algorithm on binary polynomials * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: gfx-kmul.c,v $ + * Revision 1.2 2002/10/09 00:36:03 mdw + * Fix bounds on workspace for Karatsuba operations. + * * Revision 1.1 2000/10/08 15:49:37 mdw * First glimmerings of binary polynomial arithmetic. * @@ -130,17 +133,14 @@ void gfx_kmul(mpw *dv, mpw *dvl, avm = avl; } - assert(((void)"Destination too small for Karatsuba gf-multiply", - dvl - dv >= 4 * m)); - assert(((void)"Not enough workspace for Karatsuba gf-multiply", - svl - sv >= 4 * m)); - /* --- Sort out the middle term --- */ { mpw *bsv = sv + m, *ssv = bsv + m; mpw *rdv = dv + m, *rdvl = rdv + 2 * m; + assert(rdvl < dvl); + assert(ssv < svl); UXOR2(sv, bsv, av, avm, avm, avl); UXOR2(bsv, ssv, bv, bvm, bvm, bvl); if (m > GFK_THRESH) diff --git a/mp-arith.c b/mp-arith.c index d31309b..23137e2 100644 --- a/mp-arith.c +++ b/mp-arith.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-arith.c,v 1.11 2002/10/06 22:52:50 mdw Exp $ + * $Id: mp-arith.c,v 1.12 2002/10/09 00:36:03 mdw Exp $ * * Basic arithmetic on multiprecision integers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-arith.c,v $ + * Revision 1.12 2002/10/09 00:36:03 mdw + * Fix bounds on workspace for Karatsuba operations. + * * Revision 1.11 2002/10/06 22:52:50 mdw * Pile of changes for supporting two's complement properly. * @@ -421,12 +424,11 @@ mp *mp_mul(mp *d, mp *a, mp *b) MP_DEST(d, MP_LEN(a) + MP_LEN(b), a->f | b->f | MP_UNDEF); mpx_umul(d->v, d->vl, a->v, a->vl, b->v, b->vl); } else { - size_t m = 2 * MAX(MP_LEN(a), MP_LEN(b)) + 2; + size_t m = MAX(MP_LEN(a), MP_LEN(b)); mpw *s; - MP_DEST(d, m, a->f | b->f | MP_UNDEF); - m += MPK_SLOP; - s = mpalloc(d->a, m); - mpx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + m); + MP_DEST(d, 3 * m, a->f | b->f | MP_UNDEF); + s = mpalloc(d->a, 5 * m); + mpx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 5 * m); mpfree(d->a, s); } @@ -450,15 +452,16 @@ mp *mp_sqr(mp *d, mp *a) size_t m = MP_LEN(a); a = MP_COPY(a); - MP_DEST(d, 2 * m + 2, a->f | MP_UNDEF); if (m > MPK_THRESH) { mpw *s; - m = 2 * (m + 1) + MPK_SLOP; - s = mpalloc(d->a, m); - mpx_ksqr(d->v, d->vl, a->v, a->vl, s, s + m); + MP_DEST(d, 3 * m, a->f | MP_UNDEF); + s = mpalloc(d->a, 5 * m); + mpx_ksqr(d->v, d->vl, a->v, a->vl, s, s + 5 * m); mpfree(d->a, s); - } else + } else { + MP_DEST(d, 2 * m + 2, a->f | MP_UNDEF); mpx_usqr(d->v, d->vl, a->v, a->vl); + } d->f = a->f & MP_BURN; MP_SHRINK(d); MP_DROP(a); diff --git a/mpx-kmul.c b/mpx-kmul.c index f6b0b4f..1981a28 100644 --- a/mpx-kmul.c +++ b/mpx-kmul.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx-kmul.c,v 1.7 2000/10/08 15:48:35 mdw Exp $ + * $Id: mpx-kmul.c,v 1.8 2002/10/09 00:36:03 mdw Exp $ * * Karatsuba's multiplication algorithm * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx-kmul.c,v $ + * Revision 1.8 2002/10/09 00:36:03 mdw + * Fix bounds on workspace for Karatsuba operations. + * * Revision 1.7 2000/10/08 15:48:35 mdw * Rename Karatsuba constants now that we have @gfx_kmul@ too. * @@ -66,7 +69,7 @@ #ifdef TEST_RIG # undef MPK_THRESH -# define MPK_THRESH 2 +# define MPK_THRESH 4 /* Smallest possible correct value */ #endif /*----- Main code ---------------------------------------------------------*/ @@ -85,9 +88,9 @@ * multiplication (e.g., @mpx_umul@) on large numbers, although * more expensive on small ones. * - * The destination must be twice as large as the larger - * argument. The scratch space must be twice as large as the - * larger argument, plus the magic number @MPK_SLOP@. + * The destination must be three times as large as the larger + * argument. The scratch space must be five times as large as + * the larger argument. */ void mpx_kmul(mpw *dv, mpw *dvl, @@ -149,17 +152,14 @@ void mpx_kmul(mpw *dv, mpw *dvl, avm = avl; } - assert(((void)"Destination too small for Karatsuba multiply", - dvl - dv >= 4 * m)); - assert(((void)"Not enough workspace for Karatsuba multiply", - svl - sv >= 4 * m)); - /* --- Sort out the middle term --- */ { mpw *bsv = sv + m + 1, *ssv = bsv + m + 1; mpw *rdv = dv + m, *rdvl = rdv + 2 * (m + 2); + assert(rdvl < dvl); + assert(ssv < svl); UADD2(sv, bsv, av, avm, avm, avl); UADD2(bsv, ssv, bv, bvm, bvm, bvl); if (m > MPK_THRESH) @@ -246,8 +246,8 @@ static int umul(dstr *v) LOAD(b, bl, &v[1]); LOAD(c, cl, &v[2]); m = MAX(al - a, bl - b) + 1; - ALLOC(d, dl, 2 * m); - ALLOC(s, sl, 2 * m + 32); + ALLOC(d, dl, 3 * m); + ALLOC(s, sl, 5 * m); mpx_kmul(d, dl, a, al, b, bl, s, sl); if (!mpx_ueq(d, dl, c, cl)) { diff --git a/mpx-ksqr.c b/mpx-ksqr.c index 25dbb70..8a0ad64 100644 --- a/mpx-ksqr.c +++ b/mpx-ksqr.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx-ksqr.c,v 1.6 2000/10/08 15:48:35 mdw Exp $ + * $Id: mpx-ksqr.c,v 1.7 2002/10/09 00:36:03 mdw Exp $ * * Karatsuba-based squaring algorithm * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx-ksqr.c,v $ + * Revision 1.7 2002/10/09 00:36:03 mdw + * Fix bounds on workspace for Karatsuba operations. + * * Revision 1.6 2000/10/08 15:48:35 mdw * Rename Karatsuba constants now that we have @gfx_kmul@ too. * @@ -64,7 +67,7 @@ #ifdef TEST_RIG # undef MPK_THRESH -# define MPK_THRESH 2 +# define MPK_THRESH 4 #endif /*----- Main code ---------------------------------------------------------*/ @@ -83,9 +86,9 @@ * large numbers, although more expensive on small ones, and * rather simpler than full-blown Karatsuba multiplication. * - * The destination must be twice as large as the argument. The - * scratch space must be twice as large as the argument, plus - * the magic number @MPK_SLOP@. + * The destination must be three times as large as the larger + * argument. The scratch space must be five times as large as + * the larger argument. */ void mpx_ksqr(mpw *dv, mpw *dvl, @@ -126,11 +129,6 @@ void mpx_ksqr(mpw *dv, mpw *dvl, m = (avl - av + 1) >> 1; avm = av + m; - assert(((void)"Destination too small for Karatsuba square", - dvl - dv >= 4 * m)); - assert(((void)"Not enough workspace for Karatsuba square", - svl - sv >= 4 * m)); - /* --- Sort out everything --- */ { @@ -138,6 +136,8 @@ void mpx_ksqr(mpw *dv, mpw *dvl, mpw *tdv = dv + m; mpw *rdv = tdv + m; + assert(rdv + m + 4 < dvl); + assert(ssv < svl); UADD2(sv, svm, av, avm, avm, avl); if (m > MPK_THRESH) mpx_ksqr(tdv, rdv + m + 4, sv, svm + 1, ssv, svl); @@ -209,8 +209,8 @@ static int usqr(dstr *v) LOAD(a, al, &v[0]); LOAD(c, cl, &v[1]); m = al - a + 1; - ALLOC(d, dl, 2 * m); - ALLOC(s, sl, 2 * m + 32); + ALLOC(d, dl, 3 * m); + ALLOC(s, sl, 5 * m); mpx_ksqr(d, dl, a, al, s, sl); if (!mpx_ueq(d, dl, c, cl)) { diff --git a/mpx.h b/mpx.h index 948e7dd..bc4b356 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ + * $Id: mpx.h,v 1.14 2002/10/09 00:36:03 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.h,v $ + * Revision 1.14 2002/10/09 00:36:03 mdw + * Fix bounds on workspace for Karatsuba operations. + * * Revision 1.13 2002/10/06 22:52:50 mdw * Pile of changes for supporting two's complement properly. * @@ -733,20 +736,12 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, * * This is the limiting length for using Karatsuba algorithms. It's best to * use the simpler classical multiplication method on numbers smaller than - * this. + * this. It is unsafe to make this constant less than four (i.e., the + * algorithms will fail). */ #define MPK_THRESH 16 -/* --- @MPK_SLOP@ --- * - * - * The extra number of words required as scratch space by the Karatsuba - * routines. This is a (generous) guess, since the actual amount of space - * required is proportional to the recursion depth. - */ - -#define MPK_SLOP 64 - /* --- @mpx_kmul@ --- * * * Arguments: @mpw *dv, *dvl@ = pointer to destination buffer @@ -761,10 +756,9 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, * multiplication (e.g., @mpx_umul@) on large numbers, although * more expensive on small ones. * - * The destination and scratch buffers must be twice as large as - * the larger argument. The scratch space must be twice as - * large as the larger argument, plus the magic number - * @MPK_SLOP@. + * The destination must be three times as large as the larger + * argument. The scratch space must be five times as large as + * the larger argument. */ extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, @@ -786,9 +780,9 @@ extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, * large numbers, although more expensive on small ones, and * rather simpler than full-blown Karatsuba multiplication. * - * The destination must be twice as large as the argument. The - * scratch space must be twice as large as the argument, plus - * the magic number @MPK_SLOP@. + * The destination must be three times as large as the larger + * argument. The scratch space must be five times as large as + * the larger argument. */ extern void mpx_ksqr(mpw */*dv*/, mpw */*dvl*/, -- 2.11.0