# define NDEBUG
#endif
-#include <stdio.h>
#include <assert.h>
#include "cryptlib.h"
#include "bn_lcl.h"
if (dl < 0)
{
-#ifdef BN_COUNT
- fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c);
-#endif
for (;;)
{
t = b[0];
else
{
int save_dl = dl;
-#ifdef BN_COUNT
- fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c);
-#endif
while(c)
{
t = a[0];
}
if (dl > 0)
{
-#ifdef BN_COUNT
- fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl);
-#endif
if (save_dl > dl)
{
switch (save_dl - dl)
}
if (dl > 0)
{
-#ifdef BN_COUNT
- fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl);
-#endif
for(;;)
{
r[0] = a[0];
if (dl < 0)
{
int save_dl = dl;
-#ifdef BN_COUNT
- fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c);
-#endif
while (c)
{
l=(c+b[0])&BN_MASK2;
}
if (dl < 0)
{
-#ifdef BN_COUNT
- fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl);
-#endif
if (save_dl < dl)
{
switch (dl - save_dl)
}
if (dl < 0)
{
-#ifdef BN_COUNT
- fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl);
-#endif
for(;;)
{
r[0] = b[0];
else
{
int save_dl = dl;
-#ifdef BN_COUNT
- fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl);
-#endif
while (c)
{
t=(a[0]+c)&BN_MASK2;
a+=4;
r+=4;
}
-#ifdef BN_COUNT
- fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl);
-#endif
if (dl > 0)
{
if (save_dl > dl)
}
if (dl > 0)
{
-#ifdef BN_COUNT
- fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl);
-#endif
for(;;)
{
r[0] = a[0];
/* Karatsuba recursive multiplication algorithm
* (cf. Knuth, The Art of Computer Programming, Vol. 2) */
-/* r is 2*n2 words in size,
+/*-
+ * 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.
* 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)
{
unsigned int neg,zero;
BN_ULONG ln,lo,*p;
-# ifdef BN_COUNT
- fprintf(stderr," bn_mul_recursive %d * %d\n",n2,n2);
-# endif
# ifdef BN_MUL_COMBA
# if 0
if (n2 == 4)
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
+ /*-
+ * 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[n2]),&(t[n2]),t,n2));
}
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
+ /*-
+ * 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
/* 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;
- unsigned 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);
-# endif
if (n < 8)
{
bn_mul_normal(r,a,n+tna,b,n+tnb);
/* 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]),
}
}
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
+ /*-
+ * 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[n2]),&(t[n2]),t,n2));
}
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
+ /*-
+ * 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
/* The overflow will stop before we over write
* words we should not overwrite */
- if (ln < c1)
+ if (ln < (BN_ULONG)c1)
{
do {
p++;
}
}
-/* a and b must be the same size, which is n2.
+/*-
+ * 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,
{
int n=n2/2;
-# ifdef BN_COUNT
- fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2);
-# endif
-
bn_mul_recursive(r,a,b,n,0,0,&(t[0]));
if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
{
}
}
-/* a and b must be the same size, which is n2.
+/*-
+ * 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
int neg,oneg,zero;
BN_ULONG ll,lc,*lp,*mp;
-# ifdef BN_COUNT
- fprintf(stderr," bn_mul_high %d * %d\n",n2,n2);
-# endif
n=n2/2;
/* Calculate (al-ah)*(bh-bl) */
bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2]));
}
- /* s0 == low(al*bl)
+ /*-
+ * 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))
lp[i]=((~mp[i])+1)&BN_MASK2;
}
- /* s[0] = low(al*bl)
+ /*-
+ * 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[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[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)
*/
int j=0,k;
#endif
-#ifdef BN_COUNT
- fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top);
-#endif
-
bn_check_top(a);
bn_check_top(b);
bn_check_top(r);
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);
}
{
BN_ULONG *rr;
-#ifdef BN_COUNT
- fprintf(stderr," bn_mul_normal %d * %d\n",na,nb);
-#endif
-
if (na < nb)
{
int itmp;
void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
{
-#ifdef BN_COUNT
- fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n);
-#endif
bn_mul_words(r,a,n,b[0]);
for (;;)
projects / oweals / openssl.git / blobdiff