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

/*
 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the OpenSSL license (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#include <assert.h>
#include "internal/cryptlib.h"
#include "bn_lcl.h"

#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
/*
 * Here follows specialised variants of bn_add_words() and bn_sub_words().
 * They have the property performing operations on arrays of different sizes.
 * The sizes of those arrays is expressed through cl, which is the common
 * length ( basically, min(len(a),len(b)) ), and dl, which is the delta
 * between the two lengths, calculated as len(a)-len(b). All lengths are the
 * number of BN_ULONGs...  For the operations that require a result array as
 * parameter, it must have the length cl+abs(dl). These functions should
 * probably end up in bn_asm.c as soon as there are assembler counterparts
 * for the systems that use assembler files.
 */

BN_ULONG bn_sub_part_words(BN_ULONG *r,
                           const BN_ULONG *a, const BN_ULONG *b,
                           int cl, int dl)
{
    BN_ULONG c, t;

    assert(cl >= 0);
    c = bn_sub_words(r, a, b, cl);

    if (dl == 0)
        return c;

    r += cl;
    a += cl;
    b += cl;

    if (dl < 0) {
        for (;;) {
            t = b[0];
            r[0] = (0 - t - c) & BN_MASK2;
            if (t != 0)
                c = 1;
            if (++dl >= 0)
                break;

            t = b[1];
            r[1] = (0 - t - c) & BN_MASK2;
            if (t != 0)
                c = 1;
            if (++dl >= 0)
                break;

            t = b[2];
            r[2] = (0 - t - c) & BN_MASK2;
            if (t != 0)
                c = 1;
            if (++dl >= 0)
                break;

            t = b[3];
            r[3] = (0 - t - c) & BN_MASK2;
            if (t != 0)
                c = 1;
            if (++dl >= 0)
                break;

            b += 4;
            r += 4;
        }
    } else {
        int save_dl = dl;
        while (c) {
            t = a[0];
            r[0] = (t - c) & BN_MASK2;
            if (t != 0)
                c = 0;
            if (--dl <= 0)
                break;

            t = a[1];
            r[1] = (t - c) & BN_MASK2;
            if (t != 0)
                c = 0;
            if (--dl <= 0)
                break;

            t = a[2];
            r[2] = (t - c) & BN_MASK2;
            if (t != 0)
                c = 0;
            if (--dl <= 0)
                break;

            t = a[3];
            r[3] = (t - c) & BN_MASK2;
            if (t != 0)
                c = 0;
            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;
                    /* fall thru */
                case 2:
                    r[2] = a[2];
                    if (--dl <= 0)
                        break;
                    /* fall thru */
                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;
}
#endif

#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.
 * We multiply and return the result.
 * t must be 2*n2 words in size
 * 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]
 */
/* dnX may not be positive, but n2/2+dnX has to be */
void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
                      int dna, int dnb, BN_ULONG *t)
{
    int n = n2 / 2, c1, c2;
    int tna = n + dna, tnb = n + dnb;
    unsigned int neg, zero;
    BN_ULONG ln, lo, *p;

# ifdef BN_MUL_COMBA
#  if 0
    if (n2 == 4) {
        bn_mul_comba4(r, a, b);
        return;
    }
#  endif
    /*
     * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
     * [steve]
     */
    if (n2 == 8 && dna == 0 && dnb == 0) {
        bn_mul_comba8(r, a, b);
        return;
    }
# endif                         /* BN_MUL_COMBA */
    /* Else do normal multiply */
    if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
        bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
        if ((dna + dnb) < 0)
            memset(&r[2 * n2 + dna + dnb], 0,
                   sizeof(BN_ULONG) * -(dna + dnb));
        return;
    }
    /* r=(a[0]-a[1])*(b[1]-b[0]) */
    c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
    c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
    zero = neg = 0;
    switch (c1 * 3 + c2) {
    case -4:
        bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
        bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
        break;
    case -3:
        zero = 1;
        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); /* + */
        neg = 1;
        break;
    case -1:
    case 0:
    case 1:
        zero = 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:
        zero = 1;
        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);
        break;
    }

# ifdef BN_MUL_COMBA
    if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
                                           * extra args to do this well */
        if (!zero)
            bn_mul_comba4(&(t[n2]), t, &(t[n]));
        else
            memset(&t[n2], 0, sizeof(*t) * 8);

        bn_mul_comba4(r, a, b);
        bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
    } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
                                                  * take extra args to do
                                                  * this well */
        if (!zero)
            bn_mul_comba8(&(t[n2]), t, &(t[n]));
        else
            memset(&t[n2], 0, sizeof(*t) * 16);

        bn_mul_comba8(r, a, b);
        bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
    } else
# endif                         /* BN_MUL_COMBA */
    {
        p = &(t[n2 * 2]);
        if (!zero)
            bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
        else
            memset(&t[n2], 0, sizeof(*t) * n2);
        bn_mul_recursive(r, a, b, n, 0, 0, p);
        bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
    }

    /*-
     * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
     * r[10] holds (a[0]*b[0])
     * r[32] holds (b[1]*b[1])
     */

    c1 = (int)(bn_add_words(t, r, &(r[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])
     * r[32] holds (b[1]*b[1])
     * c1 holds the carry bits
     */
    c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
    if (c1) {
        p = &(r[n + n2]);
        lo = *p;
        ln = (lo + c1) & BN_MASK2;
        *p = ln;

        /*
         * The overflow will stop before we over write words we should not
         * overwrite
         */
        if (ln < (BN_ULONG)c1) {
            do {
                p++;
                lo = *p;
                ln = (lo + 1) & BN_MASK2;
                *p = ln;
            } while (ln == 0);
        }
    }
}

/*
 * n+tn is the word length t needs to be n*4 is size, as does r
 */
/* tnX may not be negative but less than n */
void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
                           int tna, int tnb, BN_ULONG *t)
{
    int i, j, n2 = n * 2;
    int c1, c2, neg;
    BN_ULONG ln, lo, *p;

    if (n < 8) {
        bn_mul_normal(r, a, n + tna, b, n + tnb);
        return;
    }

    /* r=(a[0]-a[1])*(b[1]-b[0]) */
    c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
    c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
    neg = 0;
    switch (c1 * 3 + c2) {
    case -4:
        bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
        bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
        break;
    case -3:
    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); /* + */
        neg = 1;
        break;
    case -1:
    case 0:
    case 1:
    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:
    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);
        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(*r) * (n2 - tn * 2));
    } else
# endif
    if (n == 8) {
        bn_mul_comba8(&(t[n2]), t, &(t[n]));
        bn_mul_comba8(r, a, b);
        bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
        memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb));
    } else {
        p = &(t[n2 * 2]);
        bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
        bn_mul_recursive(r, a, b, n, 0, 0, p);
        i = n / 2;
        /*
         * If there is only a bottom half to the number, just do it
         */
        if (tna > tnb)
            j = tna - i;
        else
            j = tnb - i;
        if (j == 0) {
            bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
                             i, tna - i, tnb - i, p);
            memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2));
        } else if (j > 0) {     /* eg, n == 16, i == 8 and tn == 11 */
            bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
                                  i, tna - i, tnb - i, p);
            memset(&(r[n2 + tna + tnb]), 0,
                   sizeof(BN_ULONG) * (n2 - tna - tnb));
        } else {                /* (j < 0) eg, n == 16, i == 8 and tn == 5 */

            memset(&r[n2], 0, sizeof(*r) * n2);
            if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
                && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
                bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
            } else {
                for (;;) {
                    i /= 2;
                    /*
                     * these simplified conditions work exclusively because
                     * difference between tna and tnb is 1 or 0
                     */
                    if (i < tna || i < tnb) {
                        bn_mul_part_recursive(&(r[n2]),
                                              &(a[n]), &(b[n]),
                                              i, tna - i, tnb - i, p);
                        break;
                    } else if (i == tna || i == tnb) {
                        bn_mul_recursive(&(r[n2]),
                                         &(a[n]), &(b[n]),
                                         i, tna - i, tnb - i, p);
                        break;
                    }
                }
            }
        }
    }

    /*-
     * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
     * r[10] holds (a[0]*b[0])
     * r[32] holds (b[1]*b[1])
     */

    c1 = (int)(bn_add_words(t, r, &(r[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])
     * r[32] holds (b[1]*b[1])
     * c1 holds the carry bits
     */
    c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
    if (c1) {
        p = &(r[n + n2]);
        lo = *p;
        ln = (lo + c1) & BN_MASK2;
        *p = ln;

        /*
         * The overflow will stop before we over write words we should not
         * overwrite
         */
        if (ln < (BN_ULONG)c1) {
            do {
                p++;
                lo = *p;
                ln = (lo + 1) & BN_MASK2;
                *p = ln;
            } while (ln == 0);
        }
    }
}

/*-
 * a and b must be the same size, which is n2.
 * r needs to be n2 words and t needs to be n2*2
 */
void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
                          BN_ULONG *t)
{
    int n = n2 / 2;

    bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
    if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
        bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
        bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
        bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
        bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
    } else {
        bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
        bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
        bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
        bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
    }
}
#endif                          /* BN_RECURSION */

int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
{
    int ret = 0;
    int top, al, bl;
    BIGNUM *rr;
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
    int i;
#endif
#ifdef BN_RECURSION
    BIGNUM *t = NULL;
    int j = 0, k;
#endif

    bn_check_top(a);
    bn_check_top(b);
    bn_check_top(r);

    al = a->top;
    bl = b->top;

    if ((al == 0) || (bl == 0)) {
        BN_zero(r);
        return 1;
    }
    top = al + bl;

    BN_CTX_start(ctx);
    if ((r == a) || (r == b)) {
        if ((rr = BN_CTX_get(ctx)) == NULL)
            goto err;
    } else
        rr = r;

#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
    i = al - bl;
#endif
#ifdef BN_MUL_COMBA
    if (i == 0) {
# if 0
        if (al == 4) {
            if (bn_wexpand(rr, 8) == NULL)
                goto err;
            rr->top = 8;
            bn_mul_comba4(rr->d, a->d, b->d);
            goto end;
        }
# endif
        if (al == 8) {
            if (bn_wexpand(rr, 16) == NULL)
                goto err;
            rr->top = 16;
            bn_mul_comba8(rr->d, a->d, b->d);
            goto end;
        }
    }
#endif                          /* BN_MUL_COMBA */
#ifdef BN_RECURSION
    if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
        if (i >= -1 && i <= 1) {
            /*
             * Find out the power of two lower or equal to the longest of the
             * two numbers
             */
            if (i >= 0) {
                j = BN_num_bits_word((BN_ULONG)al);
            }
            if (i == -1) {
                j = BN_num_bits_word((BN_ULONG)bl);
            }
            j = 1 << (j - 1);
            assert(j <= al || j <= bl);
            k = j + j;
            t = BN_CTX_get(ctx);
            if (t == NULL)
                goto err;
            if (al > j || bl > j) {
                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,
                                      j, al - j, bl - j, t->d);
            } else {            /* al <= j || bl <= j */

                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, j, al - j, bl - j, t->d);
            }
            rr->top = top;
            goto end;
        }
    }
#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);

#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) == NULL)
        goto err;

    ret = 1;
 err:
    bn_check_top(r);
    BN_CTX_end(ctx);
    return (ret);
}

void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
{
    BN_ULONG *rr;

    if (na < nb) {
        int itmp;
        BN_ULONG *ltmp;

        itmp = na;
        na = nb;
        nb = itmp;
        ltmp = a;
        a = b;
        b = ltmp;

    }
    rr = &(r[na]);
    if (nb <= 0) {
        (void)bn_mul_words(r, a, na, 0);
        return;
    } else
        rr[0] = bn_mul_words(r, a, na, b[0]);

    for (;;) {
        if (--nb <= 0)
            return;
        rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
        if (--nb <= 0)
            return;
        rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
        if (--nb <= 0)
            return;
        rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
        if (--nb <= 0)
            return;
        rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
        rr += 4;
        r += 4;
        b += 4;
    }
}

void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
{
    bn_mul_words(r, a, n, b[0]);

    for (;;) {
        if (--n <= 0)
            return;
        bn_mul_add_words(&(r[1]), a, n, b[1]);
        if (--n <= 0)
            return;
        bn_mul_add_words(&(r[2]), a, n, b[2]);
        if (--n <= 0)
            return;
        bn_mul_add_words(&(r[3]), a, n, b[3]);
        if (--n <= 0)
            return;
        bn_mul_add_words(&(r[4]), a, n, b[4]);
        r += 4;
        b += 4;
    }
}
Commit	Line	Data
4f22f405 RS	1	/*
4f22f405 RS	2	* Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
0f113f3e	3	*
4f22f405 RS	4	* Licensed under the OpenSSL license (the "License"). You may not use
	5	* this file except in compliance with the License. You can obtain a copy
	6	* in the file LICENSE in the source distribution or at
	7	* https://www.openssl.org/source/license.html
d02b48c6 RE	8	*/
d02b48c6 RE	9
baa257f1	10	#include <assert.h>
b39fc560	11	#include "internal/cryptlib.h"
d02b48c6 RE	12	#include "bn_lcl.h"
d02b48c6 RE	13
699543e4	14	#if defined(OPENSSL_NO_ASM) \|\| !defined(OPENSSL_BN_ASM_PART_WORDS)
0f113f3e MC	15	/*
	16	* Here follows specialised variants of bn_add_words() and bn_sub_words().
	17	* They have the property performing operations on arrays of different sizes.
	18	* The sizes of those arrays is expressed through cl, which is the common
0d4fb843	19	* length ( basically, min(len(a),len(b)) ), and dl, which is the delta
0f113f3e MC	20	* between the two lengths, calculated as len(a)-len(b). All lengths are the
	21	* number of BN_ULONGs... For the operations that require a result array as
	22	* parameter, it must have the length cl+abs(dl). These functions should
	23	* probably end up in bn_asm.c as soon as there are assembler counterparts
	24	* for the systems that use assembler files.
	25	*/
baa257f1	26
baa257f1	27	BN_ULONG bn_sub_part_words(BN_ULONG *r,
0f113f3e MC	28	const BN_ULONG a, const BN_ULONG b,
	29	int cl, int dl)
	30	{
	31	BN_ULONG c, t;
	32
	33	assert(cl >= 0);
	34	c = bn_sub_words(r, a, b, cl);
	35
	36	if (dl == 0)
	37	return c;
	38
	39	r += cl;
	40	a += cl;
	41	b += cl;
	42
	43	if (dl < 0) {
	44	for (;;) {
	45	t = b[0];
	46	r[0] = (0 - t - c) & BN_MASK2;
	47	if (t != 0)
	48	c = 1;
	49	if (++dl >= 0)
	50	break;
	51
	52	t = b[1];
	53	r[1] = (0 - t - c) & BN_MASK2;
	54	if (t != 0)
	55	c = 1;
	56	if (++dl >= 0)
	57	break;
	58
	59	t = b[2];
	60	r[2] = (0 - t - c) & BN_MASK2;
	61	if (t != 0)
	62	c = 1;
	63	if (++dl >= 0)
	64	break;
	65
	66	t = b[3];
	67	r[3] = (0 - t - c) & BN_MASK2;
	68	if (t != 0)
	69	c = 1;
	70	if (++dl >= 0)
	71	break;
	72
	73	b += 4;
	74	r += 4;
	75	}
	76	} else {
	77	int save_dl = dl;
	78	while (c) {
	79	t = a[0];
	80	r[0] = (t - c) & BN_MASK2;
	81	if (t != 0)
	82	c = 0;
	83	if (--dl <= 0)
	84	break;
	85
	86	t = a[1];
	87	r[1] = (t - c) & BN_MASK2;
	88	if (t != 0)
	89	c = 0;
	90	if (--dl <= 0)
	91	break;
92
93	t = a[2];
94	r[2] = (t - c) & BN_MASK2;
95	if (t != 0)
96	c = 0;
97	if (--dl <= 0)
98	break;
99
100	t = a[3];
101	r[3] = (t - c) & BN_MASK2;
102	if (t != 0)
103	c = 0;
104	if (--dl <= 0)
105	break;
106
107	save_dl = dl;
108	a += 4;
109	r += 4;
110	}
111	if (dl > 0) {
112	if (save_dl > dl) {
113	switch (save_dl - dl) {
114	case 1:
115	r[1] = a[1];
116	if (--dl <= 0)
117	break;
018fcbec	118	/* fall thru */
0f113f3e MC	119	case 2:
	120	r[2] = a[2];
	121	if (--dl <= 0)
	122	break;
018fcbec	123	/* fall thru */
0f113f3e MC	124	case 3:
	125	r[3] = a[3];
	126	if (--dl <= 0)
	127	break;
	128	}
	129	a += 4;
	130	r += 4;
	131	}
	132	}
	133	if (dl > 0) {
	134	for (;;) {
	135	r[0] = a[0];
	136	if (--dl <= 0)
	137	break;
	138	r[1] = a[1];
	139	if (--dl <= 0)
	140	break;
	141	r[2] = a[2];
	142	if (--dl <= 0)
	143	break;
	144	r[3] = a[3];
	145	if (--dl <= 0)
	146	break;
	147
	148	a += 4;
	149	r += 4;
	150	}
	151	}
	152	}
	153	return c;
	154	}
240f5169	155	#endif
baa257f1	156
dfeab068	157	#ifdef BN_RECURSION
0f113f3e MC	158	/*
	159	* Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of
	160	* Computer Programming, Vol. 2)
	161	*/
8782a426	162
1d97c843 TH	163	/*-
1d97c843 TH	164	* r is 2*n2 words in size,
dfeab068 RE	165	* a and b are both n2 words in size.
	166	* n2 must be a power of 2.
	167	* We multiply and return the result.
	168	* t must be 2*n2 words in size
657e60fa	169	* We calculate
dfeab068 RE	170	* a[0]*b[0]
	171	* a[0]b[0]+a[1]b[1]+(a[0]-a[1])*(b[1]-b[0])
	172	* a[1]*b[1]
	173	*/
70ba4ee5	174	/* dnX may not be positive, but n2/2+dnX has to be */
6343829a	175	void bn_mul_recursive(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n2,
0f113f3e MC	176	int dna, int dnb, BN_ULONG *t)
	177	{
	178	int n = n2 / 2, c1, c2;
	179	int tna = n + dna, tnb = n + dnb;
	180	unsigned int neg, zero;
	181	BN_ULONG ln, lo, *p;
d02b48c6	182
775c63fc UM	183	# ifdef BN_MUL_COMBA
775c63fc UM	184	# if 0
0f113f3e MC	185	if (n2 == 4) {
	186	bn_mul_comba4(r, a, b);
	187	return;
	188	}
775c63fc	189	# endif
0f113f3e MC	190	/*
	191	* Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
	192	* [steve]
	193	*/
	194	if (n2 == 8 && dna == 0 && dnb == 0) {
	195	bn_mul_comba8(r, a, b);
	196	return;
	197	}
	198	# endif /* BN_MUL_COMBA */
	199	/* Else do normal multiply */
	200	if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
	201	bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
	202	if ((dna + dnb) < 0)
	203	memset(&r[2 * n2 + dna + dnb], 0,
	204	sizeof(BN_ULONG) * -(dna + dnb));
	205	return;
	206	}
	207	/* r=(a[0]-a[1])(b[1]-b[0]) /
	208	c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
	209	c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
	210	zero = neg = 0;
	211	switch (c1 * 3 + c2) {
	212	case -4:
	213	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
	214	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
	215	break;
	216	case -3:
	217	zero = 1;
	218	break;
	219	case -2:
	220	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
	221	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
	222	neg = 1;
	223	break;
	224	case -1:
	225	case 0:
	226	case 1:
	227	zero = 1;
	228	break;
	229	case 2:
	230	bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
	231	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
	232	neg = 1;
	233	break;
	234	case 3:
	235	zero = 1;
	236	break;
	237	case 4:
	238	bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
	239	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
	240	break;
	241	}
d02b48c6	242
775c63fc	243	# ifdef BN_MUL_COMBA
0f113f3e MC	244	if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
	245	* extra args to do this well */
	246	if (!zero)
	247	bn_mul_comba4(&(t[n2]), t, &(t[n]));
	248	else
16f8d4eb	249	memset(&t[n2], 0, sizeof(t) 8);
0f113f3e MC	250
	251	bn_mul_comba4(r, a, b);
	252	bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
	253	} else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
	254	* take extra args to do
	255	* this well */
	256	if (!zero)
	257	bn_mul_comba8(&(t[n2]), t, &(t[n]));
	258	else
16f8d4eb	259	memset(&t[n2], 0, sizeof(t) 16);
0f113f3e MC	260
	261	bn_mul_comba8(r, a, b);
	262	bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
	263	} else
	264	# endif /* BN_MUL_COMBA */
	265	{
	266	p = &(t[n2 * 2]);
	267	if (!zero)
	268	bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
	269	else
16f8d4eb	270	memset(&t[n2], 0, sizeof(t) n2);
0f113f3e MC	271	bn_mul_recursive(r, a, b, n, 0, 0, p);
	272	bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
	273	}
	274
50e735f9 MC	275	/*-
	276	* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
	277	* r[10] holds (a[0]*b[0])
	278	* r[32] holds (b[1]*b[1])
	279	*/
0f113f3e MC	280
	281	c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
	282
	283	if (neg) { /* if t[32] is negative */
	284	c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
	285	} else {
	286	/* Might have a carry */
	287	c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
	288	}
	289
50e735f9 MC	290	/*-
	291	* t[32] holds (a[0]-a[1])(b[1]-b[0])+(a[0]b[0])+(a[1]*b[1])
	292	* r[10] holds (a[0]*b[0])
	293	* r[32] holds (b[1]*b[1])
	294	* c1 holds the carry bits
	295	*/
0f113f3e MC	296	c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
	297	if (c1) {
	298	p = &(r[n + n2]);
	299	lo = *p;
	300	ln = (lo + c1) & BN_MASK2;
	301	*p = ln;
	302
	303	/*
	304	* The overflow will stop before we over write words we should not
	305	* overwrite
	306	*/
	307	if (ln < (BN_ULONG)c1) {
	308	do {
	309	p++;
	310	lo = *p;
	311	ln = (lo + 1) & BN_MASK2;
	312	*p = ln;
	313	} while (ln == 0);
	314	}
	315	}
	316	}
	317
	318	/*
	319	* n+tn is the word length t needs to be n*4 is size, as does r
	320	*/
70ba4ee5	321	/* tnX may not be negative but less than n */
6a2347ee	322	void bn_mul_part_recursive(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n,
0f113f3e MC	323	int tna, int tnb, BN_ULONG *t)
	324	{
	325	int i, j, n2 = n * 2;
	326	int c1, c2, neg;
	327	BN_ULONG ln, lo, *p;
	328
	329	if (n < 8) {
	330	bn_mul_normal(r, a, n + tna, b, n + tnb);
	331	return;
	332	}
	333
	334	/* r=(a[0]-a[1])(b[1]-b[0]) /
	335	c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
	336	c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
	337	neg = 0;
	338	switch (c1 * 3 + c2) {
	339	case -4:
	340	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
	341	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
	342	break;
	343	case -3:
0f113f3e MC	344	case -2:
	345	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
	346	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
	347	neg = 1;
	348	break;
	349	case -1:
	350	case 0:
	351	case 1:
0f113f3e MC	352	case 2:
	353	bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
	354	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
	355	neg = 1;
	356	break;
	357	case 3:
0f113f3e MC	358	case 4:
	359	bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
	360	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
	361	break;
	362	}
	363	/*
	364	* The zero case isn't yet implemented here. The speedup would probably
	365	* be negligible.
	366	*/
775c63fc	367	# if 0
0f113f3e MC	368	if (n == 4) {
	369	bn_mul_comba4(&(t[n2]), t, &(t[n]));
	370	bn_mul_comba4(r, a, b);
	371	bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
16f8d4eb	372	memset(&r[n2 + tn * 2], 0, sizeof(r) (n2 - tn * 2));
0f113f3e	373	} else
775c63fc	374	# endif
0f113f3e MC	375	if (n == 8) {
	376	bn_mul_comba8(&(t[n2]), t, &(t[n]));
	377	bn_mul_comba8(r, a, b);
	378	bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
16f8d4eb	379	memset(&r[n2 + tna + tnb], 0, sizeof(r) (n2 - tna - tnb));
0f113f3e MC	380	} else {
	381	p = &(t[n2 * 2]);
	382	bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
	383	bn_mul_recursive(r, a, b, n, 0, 0, p);
	384	i = n / 2;
	385	/*
	386	* If there is only a bottom half to the number, just do it
	387	*/
	388	if (tna > tnb)
	389	j = tna - i;
	390	else
	391	j = tnb - i;
	392	if (j == 0) {
	393	bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
	394	i, tna - i, tnb - i, p);
16f8d4eb	395	memset(&r[n2 + i * 2], 0, sizeof(r) (n2 - i * 2));
0f113f3e MC	396	} else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */
	397	bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
	398	i, tna - i, tnb - i, p);
	399	memset(&(r[n2 + tna + tnb]), 0,
	400	sizeof(BN_ULONG) * (n2 - tna - tnb));
	401	} else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
	402
16f8d4eb	403	memset(&r[n2], 0, sizeof(r) n2);
0f113f3e MC	404	if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
	405	&& tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
	406	bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
	407	} else {
	408	for (;;) {
	409	i /= 2;
	410	/*
	411	* these simplified conditions work exclusively because
	412	* difference between tna and tnb is 1 or 0
	413	*/
	414	if (i < tna \|\| i < tnb) {
	415	bn_mul_part_recursive(&(r[n2]),
	416	&(a[n]), &(b[n]),
	417	i, tna - i, tnb - i, p);
	418	break;
	419	} else if (i == tna \|\| i == tnb) {
	420	bn_mul_recursive(&(r[n2]),
	421	&(a[n]), &(b[n]),
	422	i, tna - i, tnb - i, p);
	423	break;
	424	}
	425	}
	426	}
	427	}
	428	}
	429
50e735f9 MC	430	/*-
	431	* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
	432	* r[10] holds (a[0]*b[0])
	433	* r[32] holds (b[1]*b[1])
	434	*/
0f113f3e MC	435
	436	c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
	437
	438	if (neg) { /* if t[32] is negative */
	439	c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
	440	} else {
	441	/* Might have a carry */
	442	c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
	443	}
	444
50e735f9 MC	445	/*-
	446	* t[32] holds (a[0]-a[1])(b[1]-b[0])+(a[0]b[0])+(a[1]*b[1])
	447	* r[10] holds (a[0]*b[0])
	448	* r[32] holds (b[1]*b[1])
	449	* c1 holds the carry bits
	450	*/
0f113f3e MC	451	c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
	452	if (c1) {
	453	p = &(r[n + n2]);
	454	lo = *p;
	455	ln = (lo + c1) & BN_MASK2;
	456	*p = ln;
	457
	458	/*
	459	* The overflow will stop before we over write words we should not
	460	* overwrite
	461	*/
	462	if (ln < (BN_ULONG)c1) {
	463	do {
	464	p++;
	465	lo = *p;
	466	ln = (lo + 1) & BN_MASK2;
	467	*p = ln;
	468	} while (ln == 0);
	469	}
	470	}
	471	}
58964a49	472
1d97c843 TH	473	/*-
1d97c843 TH	474	* a and b must be the same size, which is n2.
dfeab068 RE	475	* r needs to be n2 words and t needs to be n2*2
dfeab068 RE	476	*/
6b691a5c	477	void bn_mul_low_recursive(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n2,
0f113f3e MC	478	BN_ULONG *t)
	479	{
	480	int n = n2 / 2;
	481
	482	bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
	483	if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
	484	bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
	485	bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
	486	bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
	487	bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
	488	} else {
	489	bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
	490	bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
	491	bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
	492	bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
	493	}
	494	}
0f113f3e	495	#endif /* BN_RECURSION */
58964a49	496
6a2347ee	497	int BN_mul(BIGNUM r, const BIGNUM a, const BIGNUM b, BN_CTX ctx)
0f113f3e MC	498	{
	499	int ret = 0;
	500	int top, al, bl;
	501	BIGNUM *rr;
775c63fc	502	#if defined(BN_MUL_COMBA) \|\| defined(BN_RECURSION)
0f113f3e	503	int i;
775c63fc	504	#endif
a0a54079	505	#ifdef BN_RECURSION
0f113f3e MC	506	BIGNUM *t = NULL;
0f113f3e MC	507	int j = 0, k;
a0a54079	508	#endif
dfeab068	509
0f113f3e MC	510	bn_check_top(a);
	511	bn_check_top(b);
	512	bn_check_top(r);
	513
	514	al = a->top;
	515	bl = b->top;
	516
	517	if ((al == 0) \|\| (bl == 0)) {
	518	BN_zero(r);
208fb891	519	return 1;
0f113f3e MC	520	}
	521	top = al + bl;
	522
	523	BN_CTX_start(ctx);
	524	if ((r == a) \|\| (r == b)) {
	525	if ((rr = BN_CTX_get(ctx)) == NULL)
	526	goto err;
	527	} else
	528	rr = r;
a0a54079	529
dfeab068	530	#if defined(BN_MUL_COMBA) \|\| defined(BN_RECURSION)
0f113f3e	531	i = al - bl;
775c63fc UM	532	#endif
775c63fc UM	533	#ifdef BN_MUL_COMBA
0f113f3e	534	if (i == 0) {
775c63fc	535	# if 0
0f113f3e MC	536	if (al == 4) {
	537	if (bn_wexpand(rr, 8) == NULL)
	538	goto err;
	539	rr->top = 8;
	540	bn_mul_comba4(rr->d, a->d, b->d);
	541	goto end;
	542	}
775c63fc	543	# endif
0f113f3e MC	544	if (al == 8) {
	545	if (bn_wexpand(rr, 16) == NULL)
	546	goto err;
	547	rr->top = 16;
	548	bn_mul_comba8(rr->d, a->d, b->d);
	549	goto end;
	550	}
	551	}
	552	#endif /* BN_MUL_COMBA */
dfeab068	553	#ifdef BN_RECURSION
0f113f3e MC	554	if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
	555	if (i >= -1 && i <= 1) {
	556	/*
	557	* Find out the power of two lower or equal to the longest of the
	558	* two numbers
	559	*/
	560	if (i >= 0) {
	561	j = BN_num_bits_word((BN_ULONG)al);
	562	}
	563	if (i == -1) {
	564	j = BN_num_bits_word((BN_ULONG)bl);
	565	}
	566	j = 1 << (j - 1);
	567	assert(j <= al \|\| j <= bl);
	568	k = j + j;
	569	t = BN_CTX_get(ctx);
	570	if (t == NULL)
	571	goto err;
	572	if (al > j \|\| bl > j) {
	573	if (bn_wexpand(t, k * 4) == NULL)
	574	goto err;
	575	if (bn_wexpand(rr, k * 4) == NULL)
	576	goto err;
	577	bn_mul_part_recursive(rr->d, a->d, b->d,
	578	j, al - j, bl - j, t->d);
	579	} else { /* al <= j \|\| bl <= j */
	580
	581	if (bn_wexpand(t, k * 2) == NULL)
	582	goto err;
	583	if (bn_wexpand(rr, k * 2) == NULL)
	584	goto err;
	585	bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
	586	}
	587	rr->top = top;
	588	goto end;
	589	}
0f113f3e MC	590	}
	591	#endif /* BN_RECURSION */
	592	if (bn_wexpand(rr, top) == NULL)
	593	goto err;
	594	rr->top = top;
	595	bn_mul_normal(rr->d, a->d, al, b->d, bl);
58964a49	596
a0a54079	597	#if defined(BN_MUL_COMBA) \|\| defined(BN_RECURSION)
0f113f3e	598	end:
a0a54079	599	#endif
38d1b3cc	600	rr->neg = a->neg ^ b->neg;
0f113f3e	601	bn_correct_top(rr);
78e09b53 RS	602	if (r != rr && BN_copy(r, rr) == NULL)
	603	goto err;
	604
0f113f3e MC	605	ret = 1;
	606	err:
	607	bn_check_top(r);
	608	BN_CTX_end(ctx);
	609	return (ret);
	610	}
58964a49	611
6b691a5c	612	void bn_mul_normal(BN_ULONG r, BN_ULONG a, int na, BN_ULONG *b, int nb)
0f113f3e MC	613	{
	614	BN_ULONG *rr;
	615
	616	if (na < nb) {
	617	int itmp;
	618	BN_ULONG *ltmp;
	619
	620	itmp = na;
	621	na = nb;
	622	nb = itmp;
	623	ltmp = a;
	624	a = b;
	625	b = ltmp;
	626
	627	}
	628	rr = &(r[na]);
	629	if (nb <= 0) {
	630	(void)bn_mul_words(r, a, na, 0);
	631	return;
	632	} else
	633	rr[0] = bn_mul_words(r, a, na, b[0]);
	634
	635	for (;;) {
	636	if (--nb <= 0)
	637	return;
	638	rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
	639	if (--nb <= 0)
	640	return;
	641	rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
	642	if (--nb <= 0)
	643	return;
	644	rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
	645	if (--nb <= 0)
	646	return;
	647	rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
	648	rr += 4;
	649	r += 4;
	650	b += 4;
	651	}
	652	}
dfeab068	653
6b691a5c	654	void bn_mul_low_normal(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n)
0f113f3e MC	655	{
	656	bn_mul_words(r, a, n, b[0]);
	657
	658	for (;;) {
	659	if (--n <= 0)
	660	return;
	661	bn_mul_add_words(&(r[1]), a, n, b[1]);
	662	if (--n <= 0)
	663	return;
	664	bn_mul_add_words(&(r[2]), a, n, b[2]);
	665	if (--n <= 0)
	666	return;
	667	bn_mul_add_words(&(r[3]), a, n, b[3]);
	668	if (--n <= 0)
	669	return;
	670	bn_mul_add_words(&(r[4]), a, n, b[4]);
	671	r += 4;
	672	b += 4;
	673	}
	674	}