-#ifdef BN_MUL_COMBA
- if (n == 4)
- {
- if (!zero)
- bn_mul_comba4(&(t[n2]),t,&(t[n]));
- else
- memset(&(t[n2]),0,8*sizeof(BN_ULONG));
-
- bn_mul_comba4(r,a,b);
- bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n]));
- }
- else if (n == 8)
- {
- if (!zero)
- bn_mul_comba8(&(t[n2]),t,&(t[n]));
- else
- memset(&(t[n2]),0,16*sizeof(BN_ULONG));
-
- bn_mul_comba8(r,a,b);
- bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
- }
- else
-#endif
- {
- p= &(t[n2*2]);
- if (!zero)
- bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
- else
- memset(&(t[n2]),0,n2*sizeof(BN_ULONG));
- bn_mul_recursive(r,a,b,n,p);
- bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,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=bn_add_words(t,r,&(r[n2]),n2);
-
- if (neg) /* if t[32] is negative */
- {
- c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
- }
- else
- {
- /* Might have a carry */
- c1+=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+=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 */
-void bn_mul_part_recursive(r,a,b,tn,n,t)
-BN_ULONG *r,*a,*b;
-int tn,n;
-BN_ULONG *t;
- {
- int i,j,n2=n*2;
- unsigned int c1;
- BN_ULONG ln,lo,*p;
-
-#ifdef BN_COUNT
-printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
-#endif
- if (n < 8)
- {
- i=tn+n;
- bn_mul_normal(r,a,i,b,i);
- return;
- }
-
- /* r=(a[0]-a[1])*(b[1]-b[0]) */
- bn_sub_words(t, a, &(a[n]),n); /* + */
- bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
-
-/* 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(BN_ULONG)*(n2-tn*2));
- }
- else */ if (n == 8)
- {
- bn_mul_comba8(&(t[n2]),t,&(t[n]));
- bn_mul_comba8(r,a,b);
- bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
- memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
- }
- else
- {
- p= &(t[n2*2]);
- bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
- bn_mul_recursive(r,a,b,n,p);
- i=n/2;
- /* If there is only a bottom half to the number,
- * just do it */
- j=tn-i;
- if (j == 0)
- {
- bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
- memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(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]),
- j,i,p);
- memset(&(r[n2+tn*2]),0,
- sizeof(BN_ULONG)*(n2-tn*2));
- }
- else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
- {
- memset(&(r[n2]),0,sizeof(BN_ULONG)*n2);
- if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL)
- {
- bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
- }
- else
- {
- for (;;)
- {
- i/=2;
- if (i < tn)
- {
- bn_mul_part_recursive(&(r[n2]),
- &(a[n]),&(b[n]),
- tn-i,i,p);
- break;
- }
- else if (i == tn)
- {
- bn_mul_recursive(&(r[n2]),
- &(a[n]),&(b[n]),
- 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=bn_add_words(t,r,&(r[n2]),n2);
- c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),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+=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 < 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.
+# 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:
+ /* 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:
+ /* 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:
+ /* 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;
+ }
+ /*
+ * 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.