OpenSSL 0.9.5 merge

*warning* this bumps shared lib minors for libssl and libcrypto from 2.1 to 2.2
if you are using the ssl26 packages for ssh and other things to work you will
need to get new ones (see ~beck/libsslsnap/<arch>) on cvs or ~beck/src-patent.tar.gz on cvs

1 files changed, 141 insertions, 106 deletions

diff --git a/lib/libcrypto/bn/bn_mul.c b/lib/libcrypto/bn/bn_mul.c
index 38c47f3d1f0..eb007e19e9a 100644
--- a/lib/libcrypto/bn/bn_mul.c
+++ b/lib/libcrypto/bn/bn_mul.c
@@ -66,7 +66,7 @@
  * n2 must be a power of 2.
  * We multiply and return the result.
  * t must be 2*n2 words in size
- * We calulate
+ * We calculate
  * a[0]*b[0]
  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
  * a[1]*b[1]
@@ -78,21 +78,23 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
 	unsigned int neg,zero;
 	BN_ULONG ln,lo,*p;
 
-#ifdef BN_COUNT
-printf(" bn_mul_recursive %d * %d\n",n2,n2);
-#endif
-#ifdef BN_MUL_COMBA
-/*	if (n2 == 4)
+# ifdef BN_COUNT
+	printf(" bn_mul_recursive %d * %d\n",n2,n2);
+# endif
+# ifdef BN_MUL_COMBA
+#  if 0
+	if (n2 == 4)
 		{
 		bn_mul_comba4(r,a,b);
 		return;
 		}
-	else */ if (n2 == 8)
+#  endif
+	if (n2 == 8)
 		{
 		bn_mul_comba8(r,a,b);
 		return; 
 		}
-#endif
+# endif /* BN_MUL_COMBA */
 	if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
 		{
 		/* This should not happen */
@@ -136,7 +138,7 @@ printf(" bn_mul_recursive %d * %d\n",n2,n2);
 		break;
 		}
 
-#ifdef BN_MUL_COMBA
+# ifdef BN_MUL_COMBA
 	if (n == 4)
 		{
 		if (!zero)
@@ -158,7 +160,7 @@ printf(" bn_mul_recursive %d * %d\n",n2,n2);
 		bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
 		}
 	else
-#endif
+# endif /* BN_MUL_COMBA */
 		{
 		p= &(t[n2*2]);
 		if (!zero)
@@ -219,12 +221,12 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
 	     int n, BN_ULONG *t)
 	{
 	int i,j,n2=n*2;
-	unsigned int c1;
+	unsigned int c1,c2,neg,zero;
 	BN_ULONG ln,lo,*p;
 
-#ifdef BN_COUNT
-printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
-#endif
+# ifdef BN_COUNT
+	printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
+# endif
 	if (n < 8)
 		{
 		i=tn+n;
@@ -233,17 +235,54 @@ printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
 		}
 
 	/* r=(a[0]-a[1])*(b[1]-b[0]) */
-	bn_sub_words(t,      a,      &(a[n]),n); /* + */
-	bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
-
-/*	if (n == 4)
+	c1=bn_cmp_words(a,&(a[n]),n);
+	c2=bn_cmp_words(&(b[n]),b,n);
+	zero=neg=0;
+	switch (c1*3+c2)
+		{
+	case -4:
+		bn_sub_words(t,      &(a[n]),a,      n); /* - */
+		bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
+		break;
+	case -3:
+		zero=1;
+		/* break; */
+	case -2:
+		bn_sub_words(t,      &(a[n]),a,      n); /* - */
+		bn_sub_words(&(t[n]),&(b[n]),b,      n); /* + */
+		neg=1;
+		break;
+	case -1:
+	case 0:
+	case 1:
+		zero=1;
+		/* break; */
+	case 2:
+		bn_sub_words(t,      a,      &(a[n]),n); /* + */
+		bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
+		neg=1;
+		break;
+	case 3:
+		zero=1;
+		/* break; */
+	case 4:
+		bn_sub_words(t,      a,      &(a[n]),n);
+		bn_sub_words(&(t[n]),&(b[n]),b,      n);
+		break;
+		}
+		/* The zero case isn't yet implemented here. The speedup
+		   would probably be negligible. */
+# if 0
+	if (n == 4)
 		{
 		bn_mul_comba4(&(t[n2]),t,&(t[n]));
 		bn_mul_comba4(r,a,b);
 		bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
 		memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
 		}
-	else */ if (n == 8)
+	else
+# endif
+	if (n == 8)
 		{
 		bn_mul_comba8(&(t[n2]),t,&(t[n]));
 		bn_mul_comba8(r,a,b);
@@ -308,7 +347,16 @@ printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
 	 */
 
 	c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
-	c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
+
+	if (neg) /* if t[32] is negative */
+		{
+		c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
+		}
+	else
+		{
+		/* Might have a carry */
+		c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
+		}
 
 	/* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
 	 * r[10] holds (a[0]*b[0])
@@ -345,9 +393,9 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
 	{
 	int n=n2/2;
 
-#ifdef BN_COUNT
-printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
-#endif
+# ifdef BN_COUNT
+	printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
+# endif
 
 	bn_mul_recursive(r,a,b,n,&(t[0]));
 	if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
@@ -379,9 +427,9 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
 	int neg,oneg,zero;
 	BN_ULONG ll,lc,*lp,*mp;
 
-#ifdef BN_COUNT
-printf(" bn_mul_high %d * %d\n",n2,n2);
-#endif
+# ifdef BN_COUNT
+	printf(" bn_mul_high %d * %d\n",n2,n2);
+# endif
 	n=n2/2;
 
 	/* Calculate (al-ah)*(bh-bl) */
@@ -424,14 +472,14 @@ printf(" bn_mul_high %d * %d\n",n2,n2);
 	oneg=neg;
 	/* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
 	/* r[10] = (a[1]*b[1]) */
-#ifdef BN_MUL_COMBA
+# ifdef BN_MUL_COMBA
 	if (n == 8)
 		{
 		bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
 		bn_mul_comba8(r,&(a[n]),&(b[n]));
 		}
 	else
-#endif
+# endif
 		{
 		bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
 		bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
@@ -555,19 +603,23 @@ printf(" bn_mul_high %d * %d\n",n2,n2);
 			}
 		}
 	}
-#endif
+#endif /* BN_RECURSION */
 
 int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
 	{
 	int top,al,bl;
 	BIGNUM *rr;
+	int ret = 0;
+#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
+	int i;
+#endif
 #ifdef BN_RECURSION
 	BIGNUM *t;
-	int i,j,k;
+	int j,k;
 #endif
 
 #ifdef BN_COUNT
-printf("BN_mul %d * %d\n",a->top,b->top);
+	printf("BN_mul %d * %d\n",a->top,b->top);
 #endif
 
 	bn_check_top(a);
@@ -585,115 +637,99 @@ printf("BN_mul %d * %d\n",a->top,b->top);
 		}
 	top=al+bl;
 
+	BN_CTX_start(ctx);
 	if ((r == a) || (r == b))
-		rr= &(ctx->bn[ctx->tos+1]);
+		{
+		if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
+		}
 	else
-		rr=r;
+		rr = r;
 
 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
-	if (al == bl)
+	i = al-bl;
+#endif
+#ifdef BN_MUL_COMBA
+	if (i == 0)
 		{
-#  ifdef BN_MUL_COMBA
-/*		if (al == 4)
+# if 0
+		if (al == 4)
 			{
-			if (bn_wexpand(rr,8) == NULL) return(0);
+			if (bn_wexpand(rr,8) == NULL) goto err;
 			rr->top=8;
 			bn_mul_comba4(rr->d,a->d,b->d);
 			goto end;
 			}
-		else */ if (al == 8)
+# endif
+		if (al == 8)
 			{
-			if (bn_wexpand(rr,16) == NULL) return(0);
+			if (bn_wexpand(rr,16) == NULL) goto err;
 			rr->top=16;
 			bn_mul_comba8(rr->d,a->d,b->d);
 			goto end;
 			}
-		else
-#  endif
-#ifdef BN_RECURSION
-		if (al < BN_MULL_SIZE_NORMAL)
-#endif
-			{
-			if (bn_wexpand(rr,top) == NULL) return(0);
-			rr->top=top;
-			bn_mul_normal(rr->d,a->d,al,b->d,bl);
-			goto end;
-			}
-#  ifdef BN_RECURSION
-		goto symetric;
-#  endif
 		}
-#endif
+#endif /* BN_MUL_COMBA */
 #ifdef BN_RECURSION
-	else if ((al < BN_MULL_SIZE_NORMAL) || (bl < BN_MULL_SIZE_NORMAL))
+	if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
 		{
-		if (bn_wexpand(rr,top) == NULL) return(0);
-		rr->top=top;
-		bn_mul_normal(rr->d,a->d,al,b->d,bl);
-		goto end;
-		}
-	else
-		{
-		i=(al-bl);
-		if ((i ==  1) && !BN_get_flags(b,BN_FLG_STATIC_DATA))
+		if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
 			{
 			bn_wexpand(b,al);
 			b->d[bl]=0;
 			bl++;
-			goto symetric;
+			i--;
 			}
-		else if ((i ==  -1) && !BN_get_flags(a,BN_FLG_STATIC_DATA))
+		else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
 			{
 			bn_wexpand(a,bl);
 			a->d[al]=0;
 			al++;
-			goto symetric;
+			i++;
+			}
+		if (i == 0)
+			{
+			/* symmetric and > 4 */
+			/* 16 or larger */
+			j=BN_num_bits_word((BN_ULONG)al);
+			j=1<<(j-1);
+			k=j+j;
+			t = BN_CTX_get(ctx);
+			if (al == j) /* exact multiple */
+				{
+				bn_wexpand(t,k*2);
+				bn_wexpand(rr,k*2);
+				bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
+				}
+			else
+				{
+				bn_wexpand(a,k);
+				bn_wexpand(b,k);
+				bn_wexpand(t,k*4);
+				bn_wexpand(rr,k*4);
+				for (i=a->top; i<k; i++)
+					a->d[i]=0;
+				for (i=b->top; i<k; i++)
+					b->d[i]=0;
+				bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
+				}
+			rr->top=top;
+			goto end;
 			}
 		}
-#endif
-
-	/* asymetric and >= 4 */ 
-	if (bn_wexpand(rr,top) == NULL) return(0);
+#endif /* BN_RECURSION */
+	if (bn_wexpand(rr,top) == NULL) goto err;
 	rr->top=top;
 	bn_mul_normal(rr->d,a->d,al,b->d,bl);
 
-#ifdef BN_RECURSION
-	if (0)
-		{
-symetric:
-		/* symetric and > 4 */
-		/* 16 or larger */
-		j=BN_num_bits_word((BN_ULONG)al);
-		j=1<<(j-1);
-		k=j+j;
-		t= &(ctx->bn[ctx->tos]);
-		if (al == j) /* exact multiple */
-			{
-			bn_wexpand(t,k*2);
-			bn_wexpand(rr,k*2);
-			bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
-			}
-		else
-			{
-			bn_wexpand(a,k);
-			bn_wexpand(b,k);
-			bn_wexpand(t,k*4);
-			bn_wexpand(rr,k*4);
-			for (i=a->top; i<k; i++)
-				a->d[i]=0;
-			for (i=b->top; i<k; i++)
-				b->d[i]=0;
-			bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
-			}
-		rr->top=top;
-		}
-#endif
 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
 end:
 #endif
 	bn_fix_top(rr);
 	if (r != rr) BN_copy(r,rr);
-	return(1);
+	ret=1;
+err:
+	BN_CTX_end(ctx);
+	return(ret);
 	}
 
 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
@@ -701,7 +737,7 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
 	BN_ULONG *rr;
 
 #ifdef BN_COUNT
-printf(" bn_mul_normal %d * %d\n",na,nb);
+	printf(" bn_mul_normal %d * %d\n",na,nb);
 #endif
 
 	if (na < nb)
@@ -735,7 +771,7 @@ printf(" bn_mul_normal %d * %d\n",na,nb);
 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
 	{
 #ifdef BN_COUNT
-printf(" bn_mul_low_normal %d * %d\n",n,n);
+	printf(" bn_mul_low_normal %d * %d\n",n,n);
 #endif
 	bn_mul_words(r,a,n,b[0]);
 
@@ -753,4 +789,3 @@ printf(" bn_mul_low_normal %d * %d\n",n,n);
 		b+=4;
 		}
 	}
-