* 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)
{
BN_ULONG ln,lo,*p;
# ifdef BN_COUNT
- fprintf(stderr," bn_mul_recursive %d * %d\n",n2,n2);
+ fprintf(stderr," bn_mul_recursive %d%+d * %d%+d\n",n2,dna,n2,dnb);
# endif
# ifdef BN_MUL_COMBA
# if 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,zero;
+ int c1,c2,neg;
BN_ULONG ln,lo,*p;
# ifdef BN_COUNT
- fprintf(stderr," bn_mul_part_recursive (%d+%d) * (%d+%d)\n",
- tna, n, tnb, n);
+ fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n",
+ n, tna, n, tnb);
# endif
if (n < 8)
{
/* 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;
+ neg=0;
switch (c1*3+c2)
{
case -4:
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); /* - */
case -1:
case 0:
case 1:
- zero=1;
/* break; */
case 2:
bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */
neg=1;
break;
case 3:
- zero=1;
/* break; */
case 4:
bn_sub_part_words(t, a, &(a[n]),tna,n-tna);
for (;;)
{
i/=2;
- if (i < tna && i < tnb)
+ /* 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)
+ else if (i == tna || i == tnb)
{
bn_mul_recursive(&(r[n2]),
&(a[n]),&(b[n]),
/* The overflow will stop before we over write
* words we should not overwrite */
- if (ln < c1)
+ if (ln < (BN_ULONG)c1)
{
do {
p++;
if ((al == 0) || (bl == 0))
{
- if (!BN_zero(r)) goto err;
+ BN_zero(r);
return(1);
}
top=al+bl;
{
if (i >= -1 && i <= 1)
{
- int sav_j =0;
/* 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)bl);
}
- sav_j = j;
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)
{
- bn_wexpand(t,k*4);
- bn_wexpand(rr,k*4);
+ 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 */
{
- bn_wexpand(t,k*2);
- bn_wexpand(rr,k*2);
+ 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);
}
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
end:
#endif
- bn_fix_top(rr);
+ bn_correct_top(rr);
if (r != rr) BN_copy(r,rr);
ret=1;
err:
+ bn_check_top(r);
BN_CTX_end(ctx);
return(ret);
}