/* -*-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
*
/*----- 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.
*
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)
/* -*-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
*
/*----- 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.
*
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);
}
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);
/* -*-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
*
/*----- 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.
*
#ifdef TEST_RIG
# undef MPK_THRESH
-# define MPK_THRESH 2
+# define MPK_THRESH 4 /* Smallest possible correct value */
#endif
/*----- Main code ---------------------------------------------------------*/
* 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,
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)
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)) {
/* -*-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
*
/*----- 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.
*
#ifdef TEST_RIG
# undef MPK_THRESH
-# define MPK_THRESH 2
+# define MPK_THRESH 4
#endif
/*----- Main code ---------------------------------------------------------*/
* 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,
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 --- */
{
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);
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)) {
/* -*-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
*
/*----- 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.
*
*
* 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
* 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*/,
* 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*/,
projects / u / mdw / catacomb / commitdiff