6 /* r is 2*n2 words in size,
7 * a and b are both n2 words in size.
8 * n2 must be a power of 2.
9 * We multiply and return the result.
10 * t must be 2*n2 words in size
13 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
16 void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
24 printf(" bn_mul_recursive %d * %d\n",n2,n2);
31 bn_mul_normal(r,a,n2,b,n2);
35 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
37 /* This should not happen */
39 bn_mul_normal(r,a,n2,b,n2);
42 /* r=(a[0]-a[1])*(b[1]-b[0]) */
43 c1=bn_cmp_words(a,&(a[n]),n);
44 c2=bn_cmp_words(&(b[n]),b,n);
49 bn_sub_words(t, &(a[n]),a, n); /* - */
50 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
56 bn_sub_words(t, &(a[n]),a, n); /* - */
57 bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
66 bn_sub_words(t, a, &(a[n]),n); /* + */
67 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
74 bn_sub_words(t, a, &(a[n]),n);
75 bn_sub_words(&(t[n]),&(b[n]),b, n);
82 bn_mul_comba8(&(t[n2]),t,&(t[n]));
84 memset(&(t[n2]),0,8*sizeof(BN_ULONG));
87 bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
93 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
95 memset(&(t[n2]),0,n*sizeof(BN_ULONG));
96 bn_mul_recursive(r,a,b,n,p);
97 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
100 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
101 * r[10] holds (a[0]*b[0])
102 * r[32] holds (b[1]*b[1])
105 c1=bn_add_words(t,r,&(r[n2]),n2);
107 if (neg) /* if t[32] is negative */
109 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
113 /* Might have a carry */
114 c1+=bn_add_words(&(t[n2]),&(t[n2]),t,n2);
117 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
118 * r[10] holds (a[0]*b[0])
119 * r[32] holds (b[1]*b[1])
120 * c1 holds the carry bits
122 c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
130 /* The overflow will stop before we over write
131 * words we should not overwrite */
144 /* n+tn is the word length
145 * t needs to be n*4 is size, as does r */
146 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
154 printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
159 bn_mul_normal(r,a,i,b,i);
163 /* r=(a[0]-a[1])*(b[1]-b[0]) */
164 bn_sub_words(t, a, &(a[n]),n); /* + */
165 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
169 bn_mul_comba8(&(t[n2]),t,&(t[n]));
170 bn_mul_comba8(r,a,b);
171 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
172 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
177 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
178 bn_mul_recursive(r,a,b,n,p);
180 /* If there is only a bottom half to the number,
185 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
186 memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
188 else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
190 bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
192 memset(&(r[n2+tn*2]),0,
193 sizeof(BN_ULONG)*(n2-tn*2));
195 else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
197 memset(&(r[n2]),0,sizeof(BN_ULONG)*(tn*2));
203 bn_mul_part_recursive(&(r[n2]),
210 bn_mul_recursive(&(r[n2]),
219 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
220 * r[10] holds (a[0]*b[0])
221 * r[32] holds (b[1]*b[1])
224 c1=bn_add_words(t,r,&(r[n2]),n2);
225 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
227 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
228 * r[10] holds (a[0]*b[0])
229 * r[32] holds (b[1]*b[1])
230 * c1 holds the carry bits
232 c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
240 /* The overflow will stop before we over write
241 * words we should not overwrite */
254 /* r is 2*n words in size,
255 * a and b are both n words in size.
256 * n must be a power of 2.
257 * We multiply and return the result.
258 * t must be 2*n words in size
261 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
264 void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t)
271 printf(" bn_sqr_recursive %d * %d\n",n2,n2);
283 if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
285 bn_sqr_normal(r,a,n2,t);
289 /* r=(a[0]-a[1])*(a[1]-a[0]) */
290 c1=bn_cmp_words(a,&(a[n]),n);
293 bn_sub_words(t,a,&(a[n]),n);
295 bn_sub_words(t,&(a[n]),a,n);
299 /* The result will always be negative unless it is zero */
304 bn_sqr_comba8(&(t[n2]),t);
306 memset(&(t[n2]),0,8*sizeof(BN_ULONG));
309 bn_sqr_comba8(&(r[n2]),&(a[n]));
315 bn_sqr_recursive(&(t[n2]),t,n,p);
317 memset(&(t[n2]),0,n*sizeof(BN_ULONG));
318 bn_sqr_recursive(r,a,n,p);
319 bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
322 /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
323 * r[10] holds (a[0]*b[0])
324 * r[32] holds (b[1]*b[1])
327 c1=bn_add_words(t,r,&(r[n2]),n2);
329 /* t[32] is negative */
330 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
332 /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
333 * r[10] holds (a[0]*a[0])
334 * r[32] holds (a[1]*a[1])
335 * c1 holds the carry bits
337 c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
345 /* The overflow will stop before we over write
346 * words we should not overwrite */
360 /* a and b must be the same size, which is n2.
361 * r needs to be n2 words and t needs to be n2*2
363 void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
369 printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
372 bn_mul_recursive(r,a,b,n,&(t[0]));
373 if (n > BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
375 bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
376 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
377 bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
378 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
382 bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
383 bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
384 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
385 bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
389 /* a and b must be the same size, which is n2.
390 * r needs to be n2 words and t needs to be n2*2
391 * l is the low words of the output.
394 void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
399 BN_ULONG ll,lc,*lp,*mp;
402 printf(" bn_mul_high %d * %d\n",n2,n2);
406 /* Calculate (al-ah)*(bh-bl) */
408 c1=bn_cmp_words(&(a[0]),&(a[n]),n);
409 c2=bn_cmp_words(&(b[n]),&(b[0]),n);
413 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
414 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
420 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
421 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
430 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
431 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
438 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
439 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
444 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
445 bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
446 /* r[10] = (a[1]*b[1]) */
447 bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
450 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
451 * We know s0 and s1 so the only unknown is high(al*bl)
452 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
453 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
458 c1=bn_add_words(lp,&(r[0]),&(l[0]),n);
467 neg=bn_sub_words(&(t[n2]),lp,&(t[0]),n);
470 bn_add_words(&(t[n2]),lp,&(t[0]),n);
476 bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
483 lp[i]=((~mp[i])+1)&BN_MASK2;
488 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
489 * r[10] = (a[1]*b[1])
492 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
495 /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
496 * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
497 * R[3]=r[1]+(carry/borrow)
502 c1= bn_add_words(lp,&(t[n2+n]),&(l[0]),n);
509 c1+=bn_add_words(&(t[n2]),lp, &(r[0]),n);
511 c1-=bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n);
513 c1+=bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n);
515 c2 =bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n);
516 c2+=bn_add_words(&(r[0]),&(r[0]),&(r[n]),n);
518 c2-=bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n);
520 c2+=bn_add_words(&(r[0]),&(r[0]),&(t[n]),n);
522 if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
529 ll=(r[i]+lc)&BN_MASK2;
539 r[i++]=(ll-lc)&BN_MASK2;
544 if (c2 != 0) /* Add starting at r[1] */
551 ll=(r[i]+lc)&BN_MASK2;
561 r[i++]=(ll-lc)&BN_MASK2;