bn_mul.c

RMI的处理器au1200系列所用的BOOTLOAD,包括SD卡启动USB启动硬盘启动网络启动,并初始化硬件的所有参数,支持内核调试.

	bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
    }
}

/* a and b must be the same size, which is n2.
 * r needs to be n2 words and t needs to be n2*2
 * l is the low words of the output.
 * t needs to be n2*3
 */
#if 0				/* RW */
void bn_mul_high(BN_ULONG * r, BN_ULONG * a, BN_ULONG * b, BN_ULONG * l,
		 int n2, BN_ULONG * t)
{
    int i, n;
    int c1, c2;
    int neg, oneg, zero;
    BN_ULONG ll, lc, *lp, *mp;

# ifdef BN_COUNT
    printf(" bn_mul_high %d * %d\n", n2, n2);
# endif
    n = n2 / 2;

    /* Calculate (al-ah)*(bh-bl) */
    neg = zero = 0;
    c1 = bn_cmp_words(&(a[0]), &(a[n]), n);
    c2 = bn_cmp_words(&(b[n]), &(b[0]), n);
    switch (c1 * 3 + c2) {
    case -4:
	bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
	bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
	break;
    case -3:
	zero = 1;
	break;
    case -2:
	bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
	bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
	neg = 1;
	break;
    case -1:
    case 0:
    case 1:
	zero = 1;
	break;
    case 2:
	bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
	bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
	neg = 1;
	break;
    case 3:
	zero = 1;
	break;
    case 4:
	bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
	bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
	break;
    }

    oneg = neg;
    /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
    /* r[10] = (a[1]*b[1]) */
# ifdef BN_MUL_COMBA
    if (n == 8) {
	bn_mul_comba8(&(t[0]), &(r[0]), &(r[n]));
	bn_mul_comba8(r, &(a[n]), &(b[n]));
    } else
# endif
    {
	bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, &(t[n2]));
	bn_mul_recursive(r, &(a[n]), &(b[n]), n, &(t[n2]));
    }

    /* s0 == low(al*bl)
     * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
     * We know s0 and s1 so the only unknown is high(al*bl)
     * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
     * high(al*bl) == s1 - (r[0]+l[0]+t[0])
     */
    if (l != NULL) {
	lp = &(t[n2 + n]);
	c1 = (int) (bn_add_words(lp, &(r[0]), &(l[0]), n));
    } else {
	c1 = 0;
	lp = &(r[0]);
    }

    if (neg)
	neg = (int) (bn_sub_words(&(t[n2]), lp, &(t[0]), n));
    else {
	bn_add_words(&(t[n2]), lp, &(t[0]), n);
	neg = 0;
    }

    if (l != NULL) {
	bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n);
    } else {
	lp = &(t[n2 + n]);
	mp = &(t[n2]);
	for (i = 0; i < n; i++)
	    lp[i] = ((~mp[i]) + 1) & BN_MASK2;
    }

    /* s[0] = low(al*bl)
     * t[3] = high(al*bl)
     * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
     * r[10] = (a[1]*b[1])
     */
    /* R[10] = al*bl
     * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
     * R[32] = ah*bh
     */
    /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
     * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
     * R[3]=r[1]+(carry/borrow)
     */
    if (l != NULL) {
	lp = &(t[n2]);
	c1 = (int) (bn_add_words(lp, &(t[n2 + n]), &(l[0]), n));
    } else {
	lp = &(t[n2 + n]);
	c1 = 0;
    }
    c1 += (int) (bn_add_words(&(t[n2]), lp, &(r[0]), n));
    if (oneg)
	c1 -= (int) (bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n));
    else
	c1 += (int) (bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n));

    c2 = (int) (bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n));
    c2 += (int) (bn_add_words(&(r[0]), &(r[0]), &(r[n]), n));
    if (oneg)
	c2 -= (int) (bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n));
    else
	c2 += (int) (bn_add_words(&(r[0]), &(r[0]), &(t[n]), n));

    if (c1 != 0) {		/* Add starting at r[0], could be +ve or -ve */
	i = 0;
	if (c1 > 0) {
	    lc = c1;
	    do {
		ll = (r[i] + lc) & BN_MASK2;
		r[i++] = ll;
		lc = (lc > ll);
	    } while (lc);
	} else {
	    lc = -c1;
	    do {
		ll = r[i];
		r[i++] = (ll - lc) & BN_MASK2;
		lc = (lc > ll);
	    } while (lc);
	}
    }
    if (c2 != 0) {		/* Add starting at r[1] */
	i = n;
	if (c2 > 0) {
	    lc = c2;
	    do {
		ll = (r[i] + lc) & BN_MASK2;
		r[i++] = ll;
		lc = (lc > ll);
	    } while (lc);
	} else {
	    lc = -c2;
	    do {
		ll = r[i];
		r[i++] = (ll - lc) & BN_MASK2;
		lc = (lc > ll);
	    } while (lc);
	}
    }
}
#endif
#endif				/* BN_RECURSION */

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

#ifdef BN_COUNT
    printf("BN_mul %d * %d\n", a->top, b->top);
#endif

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

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

    if ((al == 0) || (bl == 0)) {
	if (!BN_zero(r))
	    goto err;
	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;
    rr->neg = a->neg ^ b->neg;

#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 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
	    if (bn_wexpand(b, al) == NULL)
		goto err;
	    b->d[bl] = 0;
	    bl++;
	    i--;
	} else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
	    if (bn_wexpand(a, bl) == NULL)
		goto err;
	    a->d[al] = 0;
	    al++;
	    i++;
	}
	if (i == 0) {
	    /* symmetric and > 4 */
	    /* 16 or larger */
	    j = BN_num_bits_word((BN_ULONG) al);
	    j = 1 << (j - 1);
	    k = j + j;
	    t = BN_CTX_get(ctx);
	    if (al == j) {	/* exact multiple */
		if (bn_wexpand(t, k * 2) == NULL)
		    goto err;
		if (bn_wexpand(rr, k * 2) == NULL)
		    goto err;
		bn_mul_recursive(rr->d, a->d, b->d, al, t->d);
	    } else {
		if (bn_wexpand(a, k) == NULL)
		    goto err;
		if (bn_wexpand(b, k) == NULL)
		    goto err;
		if (bn_wexpand(t, k * 4) == NULL)
		    goto err;
		if (bn_wexpand(rr, k * 4) == NULL)
		    goto err;
		for (i = a->top; i < k; i++)
		    a->d[i] = 0;
		for (i = b->top; i < k; i++)
		    b->d[i] = 0;
		bn_mul_part_recursive(rr->d, a->d, b->d, al - j, 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
    bn_fix_top(rr);
    if (r != rr)
	BN_copy(r, rr);
    ret = 1;
  err:
    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;

#ifdef BN_COUNT
    printf(" bn_mul_normal %d * %d\n", na, nb);
#endif

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

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

    }
    rr = &(r[na]);
    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)
{
#ifdef BN_COUNT
    printf(" bn_mul_low_normal %d * %d\n", n, n);
#endif
    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;
    }
}