Table for driving key data extraction.

[u/mdw/catacomb] / mp-arith.c

diff --git a/mp-arith.c b/mp-arith.c
index cd6b0bd..f0502e1 100644 (file)
--- a/mp-arith.c
+++ b/mp-arith.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mp-arith.c,v 1.3 1999/12/11 10:57:43 mdw Exp $
+ * $Id: mp-arith.c,v 1.5 1999/12/22 15:54:41 mdw Exp $
  *
  * Basic arithmetic on multiprecision integers
  *
@@ -30,6 +30,12 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mp-arith.c,v $
+ * Revision 1.5  1999/12/22 15:54:41  mdw
+ * Adjust Karatsuba parameters.  Calculate destination size better.
+ *
+ * Revision 1.4  1999/12/13 15:35:16  mdw
+ * Slightly different rules on memory allocation.
+ *
  * Revision 1.3  1999/12/11 10:57:43  mdw
  * Karatsuba squaring algorithm.
  *
@@ -208,13 +214,14 @@ mp *mp_mul(mp *d, mp *a, mp *b)
   a = MP_COPY(a);
   b = MP_COPY(b);
 
-  MP_MODIFY(d, MP_LEN(a) + MP_LEN(b));
-  if (MP_LEN(a) <= KARATSUBA_CUTOFF || MP_LEN(b) <= KARATSUBA_CUTOFF)
+  if (MP_LEN(a) <= KARATSUBA_CUTOFF || MP_LEN(b) <= KARATSUBA_CUTOFF) {
+    MP_MODIFY(d, MP_LEN(a) + MP_LEN(b));
     mpx_umul(d->v, d->vl, a->v, a->vl, b->v, b->vl);
-  else {
-    size_t m = MAX(MP_LEN(a), MP_LEN(b)) * 2 + KARATSUBA_SLOP;
+  } else {
+    size_t m = 2 * MAX(MP_LEN(a), MP_LEN(b)) + 2;
     mpw *s;
-    m += 32;
+    MP_MODIFY(d, m);
+    m += KARATSUBA_SLOP;
     s = MP_ALLOC(m);
     mpx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + m);
     MP_FREE(s);
@@ -240,10 +247,10 @@ mp *mp_sqr(mp *d, mp *a)
   size_t m = MP_LEN(a);
 
   a = MP_COPY(a);
-  MP_MODIFY(d, 2 * m);
+  MP_MODIFY(d, 2 * m + 2);
   if (m > KARATSUBA_CUTOFF) {
     mpw *s;
-    m = 2 * (m + 1) + 32;
+    m = 2 * (m + 1) + KARATSUBA_SLOP;
     s = MP_ALLOC(m);
     mpx_ksqr(d->v, d->vl, a->v, a->vl, s, s + m);
     MP_FREE(s);