X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_mul.c;h=36d1b4ecc8068a06664feb61cdf4f079835f7d3d;hp=1ff8efe39ca96d3be60646710f12a17bc87a049f;hb=93a8b3ba793c769a3634e56642dac55a8d44023f;hpb=fe81a1b0515bf51983150dc7c428ed4c9fd31c7a

diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c
index 1ff8efe39c..36d1b4ecc8 100644
--- a/crypto/bn/bn_mul.c
+++ b/crypto/bn/bn_mul.c
@@ -115,10 +115,12 @@ BN_ULONG bn_sub_part_words(BN_ULONG *r,
                     r[1] = a[1];
                     if (--dl <= 0)
                         break;
+                    /* fall thru */
                 case 2:
                     r[2] = a[2];
                     if (--dl <= 0)
                         break;
+                    /* fall thru */
                 case 3:
                     r[3] = a[3];
                     if (--dl <= 0)
@@ -152,166 +154,6 @@ BN_ULONG bn_sub_part_words(BN_ULONG *r,
 }
 #endif
 
-BN_ULONG bn_add_part_words(BN_ULONG *r,
-                           const BN_ULONG *a, const BN_ULONG *b,
-                           int cl, int dl)
-{
-    BN_ULONG c, l, t;
-
-    assert(cl >= 0);
-    c = bn_add_words(r, a, b, cl);
-
-    if (dl == 0)
-        return c;
-
-    r += cl;
-    a += cl;
-    b += cl;
-
-    if (dl < 0) {
-        int save_dl = dl;
-        while (c) {
-            l = (c + b[0]) & BN_MASK2;
-            c = (l < c);
-            r[0] = l;
-            if (++dl >= 0)
-                break;
-
-            l = (c + b[1]) & BN_MASK2;
-            c = (l < c);
-            r[1] = l;
-            if (++dl >= 0)
-                break;
-
-            l = (c + b[2]) & BN_MASK2;
-            c = (l < c);
-            r[2] = l;
-            if (++dl >= 0)
-                break;
-
-            l = (c + b[3]) & BN_MASK2;
-            c = (l < c);
-            r[3] = l;
-            if (++dl >= 0)
-                break;
-
-            save_dl = dl;
-            b += 4;
-            r += 4;
-        }
-        if (dl < 0) {
-            if (save_dl < dl) {
-                switch (dl - save_dl) {
-                case 1:
-                    r[1] = b[1];
-                    if (++dl >= 0)
-                        break;
-                case 2:
-                    r[2] = b[2];
-                    if (++dl >= 0)
-                        break;
-                case 3:
-                    r[3] = b[3];
-                    if (++dl >= 0)
-                        break;
-                }
-                b += 4;
-                r += 4;
-            }
-        }
-        if (dl < 0) {
-            for (;;) {
-                r[0] = b[0];
-                if (++dl >= 0)
-                    break;
-                r[1] = b[1];
-                if (++dl >= 0)
-                    break;
-                r[2] = b[2];
-                if (++dl >= 0)
-                    break;
-                r[3] = b[3];
-                if (++dl >= 0)
-                    break;
-
-                b += 4;
-                r += 4;
-            }
-        }
-    } else {
-        int save_dl = dl;
-        while (c) {
-            t = (a[0] + c) & BN_MASK2;
-            c = (t < c);
-            r[0] = t;
-            if (--dl <= 0)
-                break;
-
-            t = (a[1] + c) & BN_MASK2;
-            c = (t < c);
-            r[1] = t;
-            if (--dl <= 0)
-                break;
-
-            t = (a[2] + c) & BN_MASK2;
-            c = (t < c);
-            r[2] = t;
-            if (--dl <= 0)
-                break;
-
-            t = (a[3] + c) & BN_MASK2;
-            c = (t < c);
-            r[3] = t;
-            if (--dl <= 0)
-                break;
-
-            save_dl = dl;
-            a += 4;
-            r += 4;
-        }
-        if (dl > 0) {
-            if (save_dl > dl) {
-                switch (save_dl - dl) {
-                case 1:
-                    r[1] = a[1];
-                    if (--dl <= 0)
-                        break;
-                case 2:
-                    r[2] = a[2];
-                    if (--dl <= 0)
-                        break;
-                case 3:
-                    r[3] = a[3];
-                    if (--dl <= 0)
-                        break;
-                }
-                a += 4;
-                r += 4;
-            }
-        }
-        if (dl > 0) {
-            for (;;) {
-                r[0] = a[0];
-                if (--dl <= 0)
-                    break;
-                r[1] = a[1];
-                if (--dl <= 0)
-                    break;
-                r[2] = a[2];
-                if (--dl <= 0)
-                    break;
-                r[3] = a[3];
-                if (--dl <= 0)
-                    break;
-
-                a += 4;
-                r += 4;
-            }
-        }
-    }
-    return c;
-}
-
 #ifdef BN_RECURSION
 /*
  * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of
@@ -499,7 +341,6 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
         break;
     case -3:
-        /* break; */
     case -2:
         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
@@ -508,14 +349,12 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
     case -1:
     case 0:
     case 1:
-        /* break; */
     case 2:
         bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
         neg = 1;
         break;
     case 3:
-        /* break; */
     case 4:
         bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
@@ -653,176 +492,6 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
         bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
     }
 }
-
-/*-
- * a and b must be the same size, which is n2.
- * r needs to be n2 words and t needs to be n2*2
- * l is the low words of the output.
- * t needs to be n2*3
- */
-void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
-                 BN_ULONG *t)
-{
-    int i, n;
-    int c1, c2;
-    int neg, oneg, zero;
-    BN_ULONG ll, lc, *lp, *mp;
-
-    n = n2 / 2;
-
-    /* Calculate (al-ah)*(bh-bl) */
-    neg = zero = 0;
-    c1 = bn_cmp_words(&(a[0]), &(a[n]), n);
-    c2 = bn_cmp_words(&(b[n]), &(b[0]), n);
-    switch (c1 * 3 + c2) {
-    case -4:
-        bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
-        bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
-        break;
-    case -3:
-        zero = 1;
-        break;
-    case -2:
-        bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
-        bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
-        neg = 1;
-        break;
-    case -1:
-    case 0:
-    case 1:
-        zero = 1;
-        break;
-    case 2:
-        bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
-        bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
-        neg = 1;
-        break;
-    case 3:
-        zero = 1;
-        break;
-    case 4:
-        bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
-        bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
-        break;
-    }
-
-    oneg = neg;
-    /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
-    /* r[10] = (a[1]*b[1]) */
-# 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
-    {
-        bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2]));
-        bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2]));
-    }
-
-    /*-
-     * s0 == low(al*bl)
-     * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
-     * We know s0 and s1 so the only unknown is high(al*bl)
-     * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
-     * high(al*bl) == s1 - (r[0]+l[0]+t[0])
-     */
-    if (l != NULL) {
-        lp = &(t[n2 + n]);
-        bn_add_words(lp, &(r[0]), &(l[0]), n);
-    } else {
-        lp = &(r[0]);
-    }
-
-    if (neg)
-        neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n));
-    else {
-        bn_add_words(&(t[n2]), lp, &(t[0]), n);
-        neg = 0;
-    }
-
-    if (l != NULL) {
-        bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n);
-    } else {
-        lp = &(t[n2 + n]);
-        mp = &(t[n2]);
-        for (i = 0; i < n; i++)
-            lp[i] = ((~mp[i]) + 1) & BN_MASK2;
-    }
-
-    /*-
-     * s[0] = low(al*bl)
-     * t[3] = high(al*bl)
-     * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
-     * r[10] = (a[1]*b[1])
-     */
-    /*-
-     * R[10] = al*bl
-     * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
-     * R[32] = ah*bh
-     */
-    /*-
-     * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
-     * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
-     * R[3]=r[1]+(carry/borrow)
-     */
-    if (l != NULL) {
-        lp = &(t[n2]);
-        c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n));
-    } else {
-        lp = &(t[n2 + n]);
-        c1 = 0;
-    }
-    c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n));
-    if (oneg)
-        c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n));
-    else
-        c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n));
-
-    c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n));
-    c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n));
-    if (oneg)
-        c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n));
-    else
-        c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n));
-
-    if (c1 != 0) {              /* Add starting at r[0], could be +ve or -ve */
-        i = 0;
-        if (c1 > 0) {
-            lc = c1;
-            do {
-                ll = (r[i] + lc) & BN_MASK2;
-                r[i++] = ll;
-                lc = (lc > ll);
-            } while (lc);
-        } else {
-            lc = -c1;
-            do {
-                ll = r[i];
-                r[i++] = (ll - lc) & BN_MASK2;
-                lc = (lc > ll);
-            } while (lc);
-        }
-    }
-    if (c2 != 0) {              /* Add starting at r[1] */
-        i = n;
-        if (c2 > 0) {
-            lc = c2;
-            do {
-                ll = (r[i] + lc) & BN_MASK2;
-                r[i++] = ll;
-                lc = (lc > ll);
-            } while (lc);
-        } else {
-            lc = -c2;
-            do {
-                ll = r[i];
-                r[i++] = (ll - lc) & BN_MASK2;
-                lc = (lc > ll);
-            } while (lc);
-        }
-    }
-}
 #endif                          /* BN_RECURSION */
 
 int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
@@ -857,7 +526,6 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
             goto err;
     } else
         rr = r;
-    rr->neg = a->neg ^ b->neg;
 
 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
     i = al - bl;
@@ -919,46 +587,6 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
             rr->top = top;
             goto end;
         }
-# if 0
-        if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
-            BIGNUM *tmp_bn = (BIGNUM *)b;
-            if (bn_wexpand(tmp_bn, al) == NULL)
-                goto err;
-            tmp_bn->d[bl] = 0;
-            bl++;
-            i--;
-        } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
-            BIGNUM *tmp_bn = (BIGNUM *)a;
-            if (bn_wexpand(tmp_bn, bl) == NULL)
-                goto err;
-            tmp_bn->d[al] = 0;
-            al++;
-            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 */
-                if (bn_wexpand(t, k * 2) == NULL)
-                    goto err;
-                if (bn_wexpand(rr, k * 2) == NULL)
-                    goto err;
-                bn_mul_recursive(rr->d, a->d, b->d, al, t->d);
-            } else {
-                if (bn_wexpand(t, k * 4) == NULL)
-                    goto err;
-                if (bn_wexpand(rr, k * 4) == NULL)
-                    goto err;
-                bn_mul_part_recursive(rr->d, a->d, b->d, al - j, j, t->d);
-            }
-            rr->top = top;
-            goto end;
-        }
-# endif
     }
 #endif                          /* BN_RECURSION */
     if (bn_wexpand(rr, top) == NULL)
@@ -969,9 +597,11 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
  end:
 #endif
+    rr->neg = a->neg ^ b->neg;
     bn_correct_top(rr);
-    if (r != rr)
-        BN_copy(r, rr);
+    if (r != rr && BN_copy(r, rr) == NULL)
+        goto err;
+
     ret = 1;
  err:
     bn_check_top(r);