Constify the BIGNUM routines a bit more. The only trouble were the

[openssl.git] / crypto / bn / bn_mul.c

diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c
index ce7c548150e458212f783638717da1e784ff8a2d..aed752818295424b3cbeae33af02cb54475737f0 100644 (file)
--- a/crypto/bn/bn_mul.c
+++ b/crypto/bn/bn_mul.c
@@ -61,6 +61,9 @@
 #include "bn_lcl.h"
 
 #ifdef BN_RECURSION
+/* Karatsuba recursive multiplication algorithm
+ * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
+
 /* r is 2*n2 words in size,
  * a and b are both n2 words in size.
  * n2 must be a power of 2.
@@ -221,7 +224,7 @@ 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
@@ -235,9 +238,43 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
                }
 
        /* 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); /* - */
-
+       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)
                {
@@ -313,7 +350,16 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
         */
 
        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])
@@ -562,7 +608,7 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
        }
 #endif /* BN_RECURSION */
 
-int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
+int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
        {
        int top,al,bl;
        BIGNUM *rr;
@@ -574,6 +620,7 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
        BIGNUM *t;
        int j,k;
 #endif
+       BIGNUM *free_a = NULL, *free_b = NULL;
 
 #ifdef BN_COUNT
        printf("BN_mul %d * %d\n",a->top,b->top);
@@ -585,7 +632,6 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
 
        al=a->top;
        bl=b->top;
-       r->neg=a->neg^b->neg;
 
        if ((al == 0) || (bl == 0))
                {
@@ -601,6 +647,7 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
                }
        else
                rr = r;
+       rr->neg=a->neg^b->neg;
 
 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
        i = al-bl;
@@ -631,17 +678,21 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
                {
                if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
                        {
-                       bn_wexpand(b,al);
-                       b->d[bl]=0;
+                       BIGNUM *tmp_bn = free_b;
+                       b = free_b = bn_dup_expand(b,al);
+                       free_b->d[bl]=0;
                        bl++;
                        i--;
+                       if (tmp_bn) BN_free(tmp_bn);
                        }
                else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
                        {
-                       bn_wexpand(a,bl);
-                       a->d[al]=0;
+                       BIGNUM *tmp_bn = free_a;
+                       a = free_a = bn_dup_expand(a,bl);
+                       free_a->d[al]=0;
                        al++;
                        i++;
+                       if (tmp_bn) BN_free(tmp_bn);
                        }
                if (i == 0)
                        {
@@ -659,14 +710,17 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
                                }
                        else
                                {
-                               bn_wexpand(a,k);
-                               bn_wexpand(b,k);
+                               BIGNUM *tmp_a = free_a,*tmp_b = free_b;
+                               a = free_a = bn_dup_expand(a,k);
+                               b = free_b = bn_dup_expand(b,k);
+                               if (tmp_a) BN_free(tmp_a);
+                               if (tmp_b) BN_free(tmp_b);
                                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;
+                               for (i=free_a->top; i<k; i++)
+                                       free_a->d[i]=0;
+                               for (i=free_b->top; i<k; i++)
+                                       free_b->d[i]=0;
                                bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
                                }
                        rr->top=top;
@@ -674,7 +728,6 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
                        }
                }
 #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);
@@ -686,6 +739,8 @@ end:
        if (r != rr) BN_copy(r,rr);
        ret=1;
 err:
+       if (free_a) BN_free(free_a);
+       if (free_b) BN_free(free_b);
        BN_CTX_end(ctx);
        return(ret);
        }