- 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 /* BN_MUL_COMBA */
- {
- 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=(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 */
-void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
- int n, BN_ULONG *t)
- {
- int i,j,n2=n*2;
- unsigned int c1,c2,neg,zero;
- 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]) */
- c1=bn_cmp_words(a,&(a[n]),n);
- c2=bn_cmp_words(&(b[n]),b,n);
- zero=neg=0;
- switch (c1*3+c2)
- {
- case -4:
- bn_sub_words(t, &(a[n]),a, n); /* - */
- bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
- break;
- case -3:
- zero=1;
- /* break; */
- case -2:
- bn_sub_words(t, &(a[n]),a, n); /* - */
- bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
- neg=1;
- break;
- case -1:
- case 0:
- case 1:
- zero=1;
- /* break; */
- case 2:
- bn_sub_words(t, a, &(a[n]),n); /* + */
- bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
- neg=1;
- break;
- case 3:
- zero=1;
- /* break; */
- case 4:
- bn_sub_words(t, a, &(a[n]),n);
- bn_sub_words(&(t[n]),&(b[n]),b, n);
- break;
- }
- /* The zero case isn't yet implemented here. The speedup
- would probably be negligible. */
+ 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.
+ */