/src/openssl41/crypto/bn/bn_mul.c

Source
/*
 * Copyright 1995-2026 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (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_local.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 through */
                case 2:
                    r[2] = a[2];
                    if (--dl <= 0)
                        break;
                    /* fall through */
                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

#ifndef OPENSSL_SMALL_FOOTPRINT
/*
 * 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;

    /*
     * 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;
    }

    /* 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;
    }

    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 {
        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 /* OPENSSL_SMALL_FOOTPRINT */

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(OPENSSL_SMALL_FOOTPRINT)
    int i;
    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(OPENSSL_SMALL_FOOTPRINT)
    i = al - bl;

    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;
        }
    }

    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 /* OPENSSL_SMALL_FOOTPRINT */
    if (bn_wexpand(rr, top) == NULL)
        goto err;
    rr->top = top;
    bn_mul_normal(rr->d, a->d, al, b->d, bl);

#if !defined(OPENSSL_SMALL_FOOTPRINT)
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: 2026-10-28 06:28

Line	Count	Source
1		/*
2		* Copyright 1995-2026 The OpenSSL Project Authors. All Rights Reserved.
3		*
4		* Licensed under the Apache License 2.0 (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_local.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	124M	{
31	124M	BN_ULONG c, t;
32
33	124M	assert(cl >= 0);
34	124M	c = bn_sub_words(r, a, b, cl);
35
36	124M	if (dl == 0)
37	120M	return c;
38
39	4.40M	r += cl;
40	4.40M	a += cl;
41	4.40M	b += cl;
42
43	4.40M	if (dl < 0) {
44	899k	for (;;) {
45	899k	t = b[0];
46	899k	r[0] = (0 - t - c) & BN_MASK2;
47	899k	if (t != 0)
48	0	c = 1;
49	899k	if (++dl >= 0)
50	94.6k	break;
51
52	805k	t = b[1];
53	805k	r[1] = (0 - t - c) & BN_MASK2;
54	805k	if (t != 0)
55	0	c = 1;
56	805k	if (++dl >= 0)
57	58.4k	break;
58
59	746k	t = b[2];
60	746k	r[2] = (0 - t - c) & BN_MASK2;
61	746k	if (t != 0)
62	0	c = 1;
63	746k	if (++dl >= 0)
64	184k	break;
65
66	562k	t = b[3];
67	562k	r[3] = (0 - t - c) & BN_MASK2;
68	562k	if (t != 0)
69	0	c = 1;
70	562k	if (++dl >= 0)
71	23.6k	break;
72
73	538k	b += 4;
74	538k	r += 4;
75	538k	}
76	4.04M	} else {
77	4.04M	int save_dl = dl;
78	4.62M	while (c) {
79	888k	t = a[0];
80	888k	r[0] = (t - c) & BN_MASK2;
81	888k	if (t != 0)
82	440k	c = 0;
83	888k	if (--dl <= 0)
84	129k	break;
85
86	758k	t = a[1];
87	758k	r[1] = (t - c) & BN_MASK2;
88	758k	if (t != 0)
89	356k	c = 0;
90	758k	if (--dl <= 0)
91	42.9k	break;
92
93	715k	t = a[2];
94	715k	r[2] = (t - c) & BN_MASK2;
95	715k	if (t != 0)
96	342k	c = 0;
97	715k	if (--dl <= 0)
98	98.7k	break;
99
100	616k	t = a[3];
101	616k	r[3] = (t - c) & BN_MASK2;
102	616k	if (t != 0)
103	283k	c = 0;
104	616k	if (--dl <= 0)
105	37.8k	break;
106
107	578k	save_dl = dl;
108	578k	a += 4;
109	578k	r += 4;
110	578k	}
111	4.04M	if (dl > 0) {
112	3.73M	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		/* fall through */
119	0	case 2:
120	0	r[2] = a[2];
121	0	if (--dl <= 0)
122	0	break;
123		/* fall through */
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	3.73M	}
133	4.04M	if (dl > 0) {
134	21.5M	for (;;) {
135	21.5M	r[0] = a[0];
136	21.5M	if (--dl <= 0)
137	839k	break;
138	20.6M	r[1] = a[1];
139	20.6M	if (--dl <= 0)
140	430k	break;
141	20.2M	r[2] = a[2];
142	20.2M	if (--dl <= 0)
143	1.68M	break;
144	18.5M	r[3] = a[3];
145	18.5M	if (--dl <= 0)
146	785k	break;
147
148	17.7M	a += 4;
149	17.7M	r += 4;
150	17.7M	}
151	3.73M	}
152	4.04M	}
153	4.40M	return c;
154	4.40M	}
155		#endif
156
157		#ifndef OPENSSL_SMALL_FOOTPRINT
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	65.2M	{
178	65.2M	int n = n2 / 2, c1, c2;
179	65.2M	int tna = n + dna, tnb = n + dnb;
180	65.2M	unsigned int neg, zero;
181	65.2M	BN_ULONG ln, lo, *p;
182
183		/*
184		* Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
185		* [steve]
186		*/
187	65.2M	if (n2 == 8 && dna == 0 && dnb == 0) {
188	213k	bn_mul_comba8(r, a, b);
189	213k	return;
190	213k	}
191
192		/* Else do normal multiply */
193	65.0M	if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
194	107k	bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
195	107k	if ((dna + dnb) < 0)
196	107k	memset(&r[2 * n2 + dna + dnb], 0,
197	107k	sizeof(BN_ULONG) * -(dna + dnb));
198	107k	return;
199	107k	}
200		/* r=(a[0]-a[1])(b[1]-b[0]) /
201	64.9M	c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
202	64.9M	c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
203	64.9M	zero = neg = 0;
204	64.9M	switch (c1 * 3 + c2) {
205	12.6M	case -4:
206	12.6M	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
207	12.6M	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
208	12.6M	break;
209	1.21M	case -3:
210	1.21M	zero = 1;
211	1.21M	break;
212	13.0M	case -2:
213	13.0M	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
214	13.0M	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
215	13.0M	neg = 1;
216	13.0M	break;
217	222k	case -1:
218	1.90M	case 0:
219	2.10M	case 1:
220	2.10M	zero = 1;
221	2.10M	break;
222	21.6M	case 2:
223	21.6M	bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
224	21.6M	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
225	21.6M	neg = 1;
226	21.6M	break;
227	1.34M	case 3:
228	1.34M	zero = 1;
229	1.34M	break;
230	13.0M	case 4:
231	13.0M	bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
232	13.0M	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
233	13.0M	break;
234	64.9M	}
235
236	64.9M	if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
237		* extra args to do this well */
238	0	if (!zero)
239	0	bn_mul_comba4(&(t[n2]), t, &(t[n]));
240	0	else
241	0	memset(&t[n2], 0, sizeof(t) 8);
242
243	0	bn_mul_comba4(r, a, b);
244	0	bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
245	64.9M	} else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
246		* take extra args to do
247		* this well */
248	44.2M	if (!zero)
249	40.8M	bn_mul_comba8(&(t[n2]), t, &(t[n]));
250	3.36M	else
251	3.36M	memset(&t[n2], 0, sizeof(t) 16);
252
253	44.2M	bn_mul_comba8(r, a, b);
254	44.2M	bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
255	44.2M	} else {
256	20.7M	p = &(t[n2 * 2]);
257	20.7M	if (!zero)
258	19.4M	bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
259	1.29M	else
260	1.29M	memset(&t[n2], 0, sizeof(t) n2);
261	20.7M	bn_mul_recursive(r, a, b, n, 0, 0, p);
262	20.7M	bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
263	20.7M	}
264
265		/*-
266		* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
267		* r[10] holds (a[0]*b[0])
268		* r[32] holds (b[1]*b[1])
269		*/
270
271	64.9M	c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
272
273	64.9M	if (neg) { /* if t[32] is negative */
274	34.6M	c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
275	34.6M	} else {
276		/* Might have a carry */
277	30.3M	c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
278	30.3M	}
279
280		/*-
281		* t[32] holds (a[0]-a[1])(b[1]-b[0])+(a[0]b[0])+(a[1]*b[1])
282		* r[10] holds (a[0]*b[0])
283		* r[32] holds (b[1]*b[1])
284		* c1 holds the carry bits
285		*/
286	64.9M	c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
287	64.9M	if (c1) {
288	25.0M	p = &(r[n + n2]);
289	25.0M	lo = *p;
290	25.0M	ln = (lo + c1) & BN_MASK2;
291	25.0M	*p = ln;
292
293		/*
294		* The overflow will stop before we over write words we should not
295		* overwrite
296		*/
297	25.0M	if (ln < (BN_ULONG)c1) {
298	798k	do {
299	798k	p++;
300	798k	lo = *p;
301	798k	ln = (lo + 1) & BN_MASK2;
302	798k	*p = ln;
303	798k	} while (ln == 0);
304	156k	}
305	25.0M	}
306	64.9M	}
307
308		/*
309		* n+tn is the word length t needs to be n*4 is size, as does r
310		*/
311		/* tnX may not be negative but less than n */
312		void bn_mul_part_recursive(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n,
313		int tna, int tnb, BN_ULONG *t)
314	2.10M	{
315	2.10M	int i, j, n2 = n * 2;
316	2.10M	int c1, c2, neg;
317	2.10M	BN_ULONG ln, lo, *p;
318
319	2.10M	if (n < 8) {
320	0	bn_mul_normal(r, a, n + tna, b, n + tnb);
321	0	return;
322	0	}
323
324		/* r=(a[0]-a[1])(b[1]-b[0]) /
325	2.10M	c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
326	2.10M	c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
327	2.10M	neg = 0;
328	2.10M	switch (c1 * 3 + c2) {
329	229k	case -4:
330	229k	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
331	229k	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
332	229k	break;
333	7.25k	case -3:
334	25.8k	case -2:
335	25.8k	bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
336	25.8k	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
337	25.8k	neg = 1;
338	25.8k	break;
339	25.1k	case -1:
340	29.4k	case 0:
341	32.3k	case 1:
342	1.78M	case 2:
343	1.78M	bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
344	1.78M	bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
345	1.78M	neg = 1;
346	1.78M	break;
347	34.6k	case 3:
348	70.1k	case 4:
349	70.1k	bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
350	70.1k	bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
351	70.1k	break;
352	2.10M	}
353		/*
354		* The zero case isn't yet implemented here. The speedup would probably
355		* be negligible.
356		*/
357		#if 0
358		if (n == 4) {
359		bn_mul_comba4(&(t[n2]), t, &(t[n]));
360		bn_mul_comba4(r, a, b);
361		bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
362		memset(&r[n2 + tn * 2], 0, sizeof(r) (n2 - tn * 2));
363		} else
364		#endif
365	2.10M	if (n == 8) {
366	388k	bn_mul_comba8(&(t[n2]), t, &(t[n]));
367	388k	bn_mul_comba8(r, a, b);
368	388k	bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
369	388k	memset(&r[n2 + tna + tnb], 0, sizeof(r) (n2 - tna - tnb));
370	1.72M	} else {
371	1.72M	p = &(t[n2 * 2]);
372	1.72M	bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
373	1.72M	bn_mul_recursive(r, a, b, n, 0, 0, p);
374	1.72M	i = n / 2;
375		/*
376		* If there is only a bottom half to the number, just do it
377		*/
378	1.72M	if (tna > tnb)
379	135k	j = tna - i;
380	1.58M	else
381	1.58M	j = tnb - i;
382	1.72M	if (j == 0) {
383	43.3k	bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
384	43.3k	i, tna - i, tnb - i, p);
385	43.3k	memset(&r[n2 + i * 2], 0, sizeof(r) (n2 - i * 2));
386	1.67M	} else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */
387	479k	bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
388	479k	i, tna - i, tnb - i, p);
389	479k	memset(&(r[n2 + tna + tnb]), 0,
390	479k	sizeof(BN_ULONG) * (n2 - tna - tnb));
391	1.19M	} else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
392
393	1.19M	memset(&r[n2], 0, sizeof(r) n2);
394	1.19M	if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
395	1.09M	&& tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
396	1.09M	bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
397	1.09M	} else {
398	121k	for (;;) {
399	121k	i /= 2;
400		/*
401		* these simplified conditions work exclusively because
402		* difference between tna and tnb is 1 or 0
403		*/
404	121k	if (i < tna \|\| i < tnb) {
405	61.1k	bn_mul_part_recursive(&(r[n2]),
406	61.1k	&(a[n]), &(b[n]),
407	61.1k	i, tna - i, tnb - i, p);
408	61.1k	break;
409	61.1k	} else if (i == tna \|\| i == tnb) {
410	44.0k	bn_mul_recursive(&(r[n2]),
411	44.0k	&(a[n]), &(b[n]),
412	44.0k	i, tna - i, tnb - i, p);
413	44.0k	break;
414	44.0k	}
415	121k	}
416	105k	}
417	1.19M	}
418	1.72M	}
419
420		/*-
421		* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
422		* r[10] holds (a[0]*b[0])
423		* r[32] holds (b[1]*b[1])
424		*/
425
426	2.10M	c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
427
428	2.10M	if (neg) { /* if t[32] is negative */
429	1.80M	c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
430	1.80M	} else {
431		/* Might have a carry */
432	299k	c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
433	299k	}
434
435		/*-
436		* t[32] holds (a[0]-a[1])(b[1]-b[0])+(a[0]b[0])+(a[1]*b[1])
437		* r[10] holds (a[0]*b[0])
438		* r[32] holds (b[1]*b[1])
439		* c1 holds the carry bits
440		*/
441	2.10M	c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
442	2.10M	if (c1) {
443	27.6k	p = &(r[n + n2]);
444	27.6k	lo = *p;
445	27.6k	ln = (lo + c1) & BN_MASK2;
446	27.6k	*p = ln;
447
448		/*
449		* The overflow will stop before we over write words we should not
450		* overwrite
451		*/
452	27.6k	if (ln < (BN_ULONG)c1) {
453	75.2k	do {
454	75.2k	p++;
455	75.2k	lo = *p;
456	75.2k	ln = (lo + 1) & BN_MASK2;
457	75.2k	*p = ln;
458	75.2k	} while (ln == 0);
459	13.5k	}
460	27.6k	}
461	2.10M	}
462
463		/*-
464		* a and b must be the same size, which is n2.
465		* r needs to be n2 words and t needs to be n2*2
466		*/
467		void bn_mul_low_recursive(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n2,
468		BN_ULONG *t)
469	0	{
470	0	int n = n2 / 2;
471
472	0	bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
473	0	if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
474	0	bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
475	0	bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
476	0	bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
477	0	bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
478	0	} else {
479	0	bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
480	0	bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
481	0	bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
482	0	bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
483	0	}
484	0	}
485		#endif /* OPENSSL_SMALL_FOOTPRINT */
486
487		int BN_mul(BIGNUM r, const BIGNUM a, const BIGNUM b, BN_CTX ctx)
488	29.1M	{
489	29.1M	int ret = bn_mul_fixed_top(r, a, b, ctx);
490
491	29.1M	bn_correct_top(r);
492	29.1M	bn_check_top(r);
493
494	29.1M	return ret;
495	29.1M	}
496
497		int bn_mul_fixed_top(BIGNUM r, const BIGNUM a, const BIGNUM b, BN_CTX ctx)
498	34.1M	{
499	34.1M	int ret = 0;
500	34.1M	int top, al, bl;
501	34.1M	BIGNUM *rr;
502	34.1M	#if !defined(OPENSSL_SMALL_FOOTPRINT)
503	34.1M	int i;
504	34.1M	BIGNUM *t = NULL;
505	34.1M	int j = 0, k;
506	34.1M	#endif
507
508	34.1M	bn_check_top(a);
509	34.1M	bn_check_top(b);
510	34.1M	bn_check_top(r);
511
512	34.1M	al = a->top;
513	34.1M	bl = b->top;
514
515	34.1M	if ((al == 0) \|\| (bl == 0)) {
516	1.50M	BN_zero(r);
517	1.50M	return 1;
518	1.50M	}
519	32.6M	top = al + bl;
520
521	32.6M	BN_CTX_start(ctx);
522	32.6M	if ((r == a) \|\| (r == b)) {
523	198k	if ((rr = BN_CTX_get(ctx)) == NULL)
524	0	goto err;
525	198k	} else
526	32.4M	rr = r;
527
528	32.6M	#if !defined(OPENSSL_SMALL_FOOTPRINT)
529	32.6M	i = al - bl;
530
531	32.6M	if (i == 0) {
532		#if 0
533		if (al == 4) {
534		if (bn_wexpand(rr, 8) == NULL)
535		goto err;
536		rr->top = 8;
537		bn_mul_comba4(rr->d, a->d, b->d);
538		goto end;
539		}
540		#endif
541	10.0M	if (al == 8) {
542	35.0k	if (bn_wexpand(rr, 16) == NULL)
543	0	goto err;
544	35.0k	rr->top = 16;
545	35.0k	bn_mul_comba8(rr->d, a->d, b->d);
546	35.0k	goto end;
547	35.0k	}
548	10.0M	}
549
550	32.6M	if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
551	2.37M	if (i >= -1 && i <= 1) {
552		/*
553		* Find out the power of two lower or equal to the longest of the
554		* two numbers
555		*/
556	2.31M	if (i >= 0) {
557	1.91M	j = BN_num_bits_word((BN_ULONG)al);
558	1.91M	}
559	2.31M	if (i == -1) {
560	398k	j = BN_num_bits_word((BN_ULONG)bl);
561	398k	}
562	2.31M	j = 1 << (j - 1);
563	2.31M	assert(j <= al \|\| j <= bl);
564	2.31M	k = j + j;
565	2.31M	t = BN_CTX_get(ctx);
566	2.31M	if (t == NULL)
567	0	goto err;
568	2.31M	if (al > j \|\| bl > j) {
569	1.56M	if (bn_wexpand(t, k * 4) == NULL)
570	0	goto err;
571	1.56M	if (bn_wexpand(rr, k * 4) == NULL)
572	0	goto err;
573	1.56M	bn_mul_part_recursive(rr->d, a->d, b->d,
574	1.56M	j, al - j, bl - j, t->d);
575	1.56M	} else { /* al <= j \|\| bl <= j */
576
577	747k	if (bn_wexpand(t, k * 2) == NULL)
578	0	goto err;
579	747k	if (bn_wexpand(rr, k * 2) == NULL)
580	0	goto err;
581	747k	bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
582	747k	}
583	2.31M	rr->top = top;
584	2.31M	goto end;
585	2.31M	}
586	2.37M	}
587	30.3M	#endif /* OPENSSL_SMALL_FOOTPRINT */
588	30.3M	if (bn_wexpand(rr, top) == NULL)
589	0	goto err;
590	30.3M	rr->top = top;
591	30.3M	bn_mul_normal(rr->d, a->d, al, b->d, bl);
592
593	30.3M	#if !defined(OPENSSL_SMALL_FOOTPRINT)
594	32.6M	end:
595	32.6M	#endif
596	32.6M	rr->neg = a->neg ^ b->neg;
597	32.6M	rr->flags \|= BN_FLG_FIXED_TOP;
598	32.6M	if (r != rr && BN_copy(r, rr) == NULL)
599	0	goto err;
600
601	32.6M	ret = 1;
602	32.6M	err:
603	32.6M	bn_check_top(r);
604	32.6M	BN_CTX_end(ctx);
605	32.6M	return ret;
606	32.6M	}
607
608		void bn_mul_normal(BN_ULONG r, BN_ULONG a, int na, BN_ULONG *b, int nb)
609	31.8M	{
610	31.8M	BN_ULONG *rr;
611
612	31.8M	if (na < nb) {
613	21.6M	int itmp;
614	21.6M	BN_ULONG *ltmp;
615
616	21.6M	itmp = na;
617	21.6M	na = nb;
618	21.6M	nb = itmp;
619	21.6M	ltmp = a;
620	21.6M	a = b;
621	21.6M	b = ltmp;
622	21.6M	}
623	31.8M	rr = &(r[na]);
624	31.8M	if (nb <= 0) {
625	368k	(void)bn_mul_words(r, a, na, 0);
626	368k	return;
627	368k	} else
628	31.5M	rr[0] = bn_mul_words(r, a, na, b[0]);
629
630	33.1M	for (;;) {
631	33.1M	if (--nb <= 0)
632	25.9M	return;
633	7.17M	rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
634	7.17M	if (--nb <= 0)
635	693k	return;
636	6.48M	rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
637	6.48M	if (--nb <= 0)
638	478k	return;
639	6.00M	rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
640	6.00M	if (--nb <= 0)
641	4.38M	return;
642	1.62M	rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
643	1.62M	rr += 4;
644	1.62M	r += 4;
645	1.62M	b += 4;
646	1.62M	}
647	31.5M	}
648
649		void bn_mul_low_normal(BN_ULONG r, BN_ULONG a, BN_ULONG *b, int n)
650	0	{
651	0	bn_mul_words(r, a, n, b[0]);
652
653	0	for (;;) {
654	0	if (--n <= 0)
655	0	return;
656	0	bn_mul_add_words(&(r[1]), a, n, b[1]);
657	0	if (--n <= 0)
658	0	return;
659	0	bn_mul_add_words(&(r[2]), a, n, b[2]);
660	0	if (--n <= 0)
661	0	return;
662	0	bn_mul_add_words(&(r[3]), a, n, b[3]);
663	0	if (--n <= 0)
664	0	return;
665	0	bn_mul_add_words(&(r[4]), a, n, b[4]);
666	0	r += 4;
667	0	b += 4;
668	0	}
669	0	}