/src/openssl/crypto/bn/bn_mul.c

Source (jump to first uncovered line)
/*
 * 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 = bn_mul_fixed_top(r, a, b, ctx);

    bn_correct_top(r);
    bn_check_top(r);

    return ret;
}

int bn_mul_fixed_top(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;
    rr->flags |= BN_FLG_FIXED_TOP;
    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;
    }
}

Coverage Report

Created: 2018-08-29 13:53

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