Upgrade to tommath 0.39 plus patches from Tom

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)<<x)) {
          *p = x;
@@ -106,5 +110,5 @@ int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
 #endif
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div_d.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_radix_size.c b/libtommath/bn_mp_radix_size.c
index a8b98af2..4aa407b 100644
--- a/libtommath/bn_mp_radix_size.c
+++ b/libtommath/bn_mp_radix_size.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
  */
 
 /* returns size of ASCII reprensentation */
@@ -83,4 +83,6 @@ int mp_radix_size (mp_int * a, int radix, int *size)
 #endif
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_radix_size.c,v $ */
-/* Tom's revision is 1.3 */
+/* Tom's revision is 1.4 */
+/* $Revision: 1.5 $ */
+/* $Date: 2006/12/01 00:31:32 $ */
diff --git a/libtommath/bn_mp_read_radix.c b/libtommath/bn_mp_read_radix.c
index fceccb7..75859f8 100644
--- a/libtommath/bn_mp_read_radix.c
+++ b/libtommath/bn_mp_read_radix.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
  */
 
 /* read a string [ASCII] in a given radix */
@@ -88,5 +88,7 @@ int mp_read_radix (mp_int * a, const char *str, int radix)
 #endif
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_read_radix.c,v $ */
-/* Tom's revision is 1.3. */
+/* Tom's revision is 1.4. */
+/* $Revision: 1.5 $ */
+/* $Date: 2006/12/01 00:31:32 $ */
 
diff --git a/libtommath/bn_mp_sqrt.c b/libtommath/bn_mp_sqrt.c
index f6e65dc..8fa5ad0 100644
--- a/libtommath/bn_mp_sqrt.c
+++ b/libtommath/bn_mp_sqrt.c
@@ -13,7 +13,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
  */
 
 #ifndef NO_FLOATING_POINT
@@ -125,5 +125,6 @@ E2: mp_clear(&t1);
 #endif
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_sqrt.c,v $ */
-/* $Revision: 1.3 $ */
-/* $Date: 2006/11/30 23:33:49 $ */
+/* Based on Tom's 1.3 */
+/* $Revision: 1.4 $ */
+/* $Date: 2006/12/01 00:31:32 $ */
diff --git a/libtommath/bncore.c b/libtommath/bncore.c
index e53fdee..dcf093e 100644
--- a/libtommath/bncore.c
+++ b/libtommath/bncore.c
@@ -24,7 +24,8 @@
  
 */
 
-int     KARATSUBA_MUL_CUTOFF = 80,      /* Min. number of digits before Karatsuba multiplication is used. */
+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. */
         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 */
@@ -32,5 +33,5 @@ int     KARATSUBA_MUL_CUTOFF = 80,      /* Min. number of digits before Karatsub
 #endif
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bncore.c,v $ */
-/* $Revision: 1.1.1.4 $ */
-/* $Date: 2006/12/01 00:08:11 $ */
+/* $Revision: 1.2 $ */
+/* $Date: 2006/12/01 00:31:32 $ */
diff --git a/libtommath/tommath.h b/libtommath/tommath.h
index bae09ce..82d9814 100644
--- a/libtommath/tommath.h
+++ b/libtommath/tommath.h
@@ -10,7 +10,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
  */
 #ifndef BN_H_
 #define BN_H_
@@ -580,5 +580,6 @@ extern const char *mp_s_rmap;
 
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/tommath.h,v $ */
-/* $Revision: 1.3 $ */
-/* $Date: 2005/09/26 18:27:14 $ */
+/* Based on Tom's version 1.8 */
+/* $Revision: 1.4 $ */
+/* $Date: 2006/12/01 00:31:32 $ */
diff --git a/libtommath/tommath_class.h b/libtommath/tommath_class.h
index 29e36fc..ebc5a60 100644
--- a/libtommath/tommath_class.h
+++ b/libtommath/tommath_class.h
@@ -20,6 +20,7 @@
 #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
@@ -252,7 +253,10 @@
    #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
@@ -995,5 +999,5 @@
 #endif
 
 /* $Source: /root/tcl/repos-to-convert/tcl/libtommath/tommath_class.h,v $ */
-/* $Revision: 1.1.1.3 $ */
-/* $Date: 2005/09/26 16:32:16 $ */
+/* $Revision: 1.2 $ */
+/* $Date: 2006/12/01 00:31:32 $ */