source: trunk/cscrypt/bn_mul.c@ 3181

Last change on this file since 3181 was 3181, checked in by dingo35, 10 years ago

Adding threadsafety FIXMEs, feel free to join checking..

File size: 17.5 KB
Line 
1//FIXME Not checked on threadsafety yet; after checking please remove this line
2/* crypto/bn/bn_mul.c */
3/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
4 * All rights reserved.
5 *
6 * This package is an SSL implementation written
7 * by Eric Young (eay@cryptsoft.com).
8 * The implementation was written so as to conform with Netscapes SSL.
9 *
10 * This library is free for commercial and non-commercial use as long as
11 * the following conditions are aheared to. The following conditions
12 * apply to all code found in this distribution, be it the RC4, RSA,
13 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
14 * included with this distribution is covered by the same copyright terms
15 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
16 *
17 * Copyright remains Eric Young's, and as such any Copyright notices in
18 * the code are not to be removed.
19 * If this package is used in a product, Eric Young should be given attribution
20 * as the author of the parts of the library used.
21 * This can be in the form of a textual message at program startup or
22 * in documentation (online or textual) provided with the package.
23 *
24 * Redistribution and use in source and binary forms, with or without
25 * modification, are permitted provided that the following conditions
26 * are met:
27 * 1. Redistributions of source code must retain the copyright
28 * notice, this list of conditions and the following disclaimer.
29 * 2. Redistributions in binary form must reproduce the above copyright
30 * notice, this list of conditions and the following disclaimer in the
31 * documentation and/or other materials provided with the distribution.
32 * 3. All advertising materials mentioning features or use of this software
33 * must display the following acknowledgement:
34 * "This product includes cryptographic software written by
35 * Eric Young (eay@cryptsoft.com)"
36 * The word 'cryptographic' can be left out if the rouines from the library
37 * being used are not cryptographic related :-).
38 * 4. If you include any Windows specific code (or a derivative thereof) from
39 * the apps directory (application code) you must include an acknowledgement:
40 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
41 *
42 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
43 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
44 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
45 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
46 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
47 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
48 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
49 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
50 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
51 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 * SUCH DAMAGE.
53 *
54 * The licence and distribution terms for any publically available version or
55 * derivative of this code cannot be changed. i.e. this code cannot simply be
56 * copied and put under another distribution licence
57 * [including the GNU Public Licence.]
58 */
59
60#include <stdio.h>
61#include <string.h>
62#include "bn_lcl.h"
63#include "openssl_mods.h"
64
65#ifdef BN_RECURSION
66/* Karatsuba recursive multiplication algorithm
67 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
68
69/* r is 2*n2 words in size,
70 * a and b are both n2 words in size.
71 * n2 must be a power of 2.
72 * We multiply and return the result.
73 * t must be 2*n2 words in size
74 * We calculate
75 * a[0]*b[0]
76 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
77 * a[1]*b[1]
78 */
79void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
80 BN_ULONG *t)
81 {
82 int n=n2/2,c1,c2;
83 unsigned int neg,zero;
84 BN_ULONG ln,lo,*p;
85
86# ifdef BN_COUNT
87 printf(" bn_mul_recursive %d * %d\n",n2,n2);
88# endif
89# ifdef BN_MUL_COMBA
90# if 0
91 if (n2 == 4)
92 {
93 bn_mul_comba4(r,a,b);
94 return;
95 }
96# endif
97 if (n2 == 8)
98 {
99 bn_mul_comba8(r,a,b);
100 return;
101 }
102# endif /* BN_MUL_COMBA */
103 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
104 {
105 /* This should not happen */
106 bn_mul_normal(r,a,n2,b,n2);
107 return;
108 }
109 /* r=(a[0]-a[1])*(b[1]-b[0]) */
110 c1=bn_cmp_words(a,&(a[n]),n);
111 c2=bn_cmp_words(&(b[n]),b,n);
112 zero=neg=0;
113 switch (c1*3+c2)
114 {
115 case -4:
116 bn_sub_words(t, &(a[n]),a, n); /* - */
117 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
118 break;
119 case -3:
120 zero=1;
121 break;
122 case -2:
123 bn_sub_words(t, &(a[n]),a, n); /* - */
124 bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
125 neg=1;
126 break;
127 case -1:
128 case 0:
129 case 1:
130 zero=1;
131 break;
132 case 2:
133 bn_sub_words(t, a, &(a[n]),n); /* + */
134 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
135 neg=1;
136 break;
137 case 3:
138 zero=1;
139 break;
140 case 4:
141 bn_sub_words(t, a, &(a[n]),n);
142 bn_sub_words(&(t[n]),&(b[n]),b, n);
143 break;
144 }
145
146# ifdef BN_MUL_COMBA
147 if (n == 4)
148 {
149 if (!zero)
150 bn_mul_comba4(&(t[n2]),t,&(t[n]));
151 else
152 memset(&(t[n2]),0,8*sizeof(BN_ULONG));
153
154 bn_mul_comba4(r,a,b);
155 bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n]));
156 }
157 else if (n == 8)
158 {
159 if (!zero)
160 bn_mul_comba8(&(t[n2]),t,&(t[n]));
161 else
162 memset(&(t[n2]),0,16*sizeof(BN_ULONG));
163
164 bn_mul_comba8(r,a,b);
165 bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
166 }
167 else
168# endif /* BN_MUL_COMBA */
169 {
170 p= &(t[n2*2]);
171 if (!zero)
172 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
173 else
174 memset(&(t[n2]),0,n2*sizeof(BN_ULONG));
175 bn_mul_recursive(r,a,b,n,p);
176 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
177 }
178
179 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
180 * r[10] holds (a[0]*b[0])
181 * r[32] holds (b[1]*b[1])
182 */
183
184 c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
185
186 if (neg) /* if t[32] is negative */
187 {
188 c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
189 }
190 else
191 {
192 /* Might have a carry */
193 c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
194 }
195
196 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
197 * r[10] holds (a[0]*b[0])
198 * r[32] holds (b[1]*b[1])
199 * c1 holds the carry bits
200 */
201 c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
202 if (c1)
203 {
204 p= &(r[n+n2]);
205 lo= *p;
206 ln=(lo+c1)&BN_MASK2;
207 *p=ln;
208
209 /* The overflow will stop before we over write
210 * words we should not overwrite */
211 if (ln < (BN_ULONG)c1)
212 {
213 do {
214 p++;
215 lo= *p;
216 ln=(lo+1)&BN_MASK2;
217 *p=ln;
218 } while (ln == 0);
219 }
220 }
221 }
222
223/* n+tn is the word length
224 * t needs to be n*4 is size, as does r */
225void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
226 int n, BN_ULONG *t)
227 {
228 int c1,c2,i,j,n2=n*2;
229 unsigned int neg,zero;
230 BN_ULONG ln,lo,*p;
231
232# ifdef BN_COUNT
233 printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
234# endif
235 if (n < 8)
236 {
237 i=tn+n;
238 bn_mul_normal(r,a,i,b,i);
239 return;
240 }
241
242 /* r=(a[0]-a[1])*(b[1]-b[0]) */
243 c1=bn_cmp_words(a,&(a[n]),n);
244 c2=bn_cmp_words(&(b[n]),b,n);
245 zero=neg=0;
246 switch (c1*3+c2)
247 {
248 case -4:
249 bn_sub_words(t, &(a[n]),a, n); /* - */
250 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
251 break;
252 case -3:
253 zero=1;
254 /* break; */
255 case -2:
256 bn_sub_words(t, &(a[n]),a, n); /* - */
257 bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
258 neg=1;
259 break;
260 case -1:
261 case 0:
262 case 1:
263 zero=1;
264 /* break; */
265 case 2:
266 bn_sub_words(t, a, &(a[n]),n); /* + */
267 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
268 neg=1;
269 break;
270 case 3:
271 zero=1;
272 /* break; */
273 case 4:
274 bn_sub_words(t, a, &(a[n]),n);
275 bn_sub_words(&(t[n]),&(b[n]),b, n);
276 break;
277 }
278 /* The zero case isn't yet implemented here. The speedup
279 would probably be negligible. */
280# if 0
281 if (n == 4)
282 {
283 bn_mul_comba4(&(t[n2]),t,&(t[n]));
284 bn_mul_comba4(r,a,b);
285 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
286 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
287 }
288 else
289# endif
290 if (n == 8)
291 {
292 bn_mul_comba8(&(t[n2]),t,&(t[n]));
293 bn_mul_comba8(r,a,b);
294 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
295 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
296 }
297 else
298 {
299 p= &(t[n2*2]);
300 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
301 bn_mul_recursive(r,a,b,n,p);
302 i=n/2;
303 /* If there is only a bottom half to the number,
304 * just do it */
305 j=tn-i;
306 if (j == 0)
307 {
308 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
309 memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
310 }
311 else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
312 {
313 bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
314 j,i,p);
315 memset(&(r[n2+tn*2]),0,
316 sizeof(BN_ULONG)*(n2-tn*2));
317 }
318 else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
319 {
320 memset(&(r[n2]),0,sizeof(BN_ULONG)*n2);
321 if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL)
322 {
323 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
324 }
325 else
326 {
327 for (;;)
328 {
329 i/=2;
330 if (i < tn)
331 {
332 bn_mul_part_recursive(&(r[n2]),
333 &(a[n]),&(b[n]),
334 tn-i,i,p);
335 break;
336 }
337 else if (i == tn)
338 {
339 bn_mul_recursive(&(r[n2]),
340 &(a[n]),&(b[n]),
341 i,p);
342 break;
343 }
344 }
345 }
346 }
347 }
348
349 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
350 * r[10] holds (a[0]*b[0])
351 * r[32] holds (b[1]*b[1])
352 */
353
354 c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
355
356 if (neg) /* if t[32] is negative */
357 {
358 c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
359 }
360 else
361 {
362 /* Might have a carry */
363 c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
364 }
365
366 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
367 * r[10] holds (a[0]*b[0])
368 * r[32] holds (b[1]*b[1])
369 * c1 holds the carry bits
370 */
371 c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
372 if (c1)
373 {
374 p= &(r[n+n2]);
375 lo= *p;
376 ln=(lo+c1)&BN_MASK2;
377 *p=ln;
378
379 /* The overflow will stop before we over write
380 * words we should not overwrite */
381 if (ln < (BN_ULONG)c1)
382 {
383 do {
384 p++;
385 lo= *p;
386 ln=(lo+1)&BN_MASK2;
387 *p=ln;
388 } while (ln == 0);
389 }
390 }
391 }
392
393/* a and b must be the same size, which is n2.
394 * r needs to be n2 words and t needs to be n2*2
395 */
396void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
397 BN_ULONG *t)
398 {
399 int n=n2/2;
400
401# ifdef BN_COUNT
402 printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
403# endif
404
405 bn_mul_recursive(r,a,b,n,&(t[0]));
406 if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
407 {
408 bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
409 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
410 bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
411 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
412 }
413 else
414 {
415 bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
416 bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
417 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
418 bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
419 }
420 }
421
422/* a and b must be the same size, which is n2.
423 * r needs to be n2 words and t needs to be n2*2
424 * l is the low words of the output.
425 * t needs to be n2*3
426 */
427void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
428 BN_ULONG *t)
429 {
430 int i,n;
431 int c1,c2;
432 int neg,oneg,zero;
433 BN_ULONG ll,lc,*lp,*mp;
434
435# ifdef BN_COUNT
436 printf(" bn_mul_high %d * %d\n",n2,n2);
437# endif
438 n=n2/2;
439
440 /* Calculate (al-ah)*(bh-bl) */
441 neg=zero=0;
442 c1=bn_cmp_words(&(a[0]),&(a[n]),n);
443 c2=bn_cmp_words(&(b[n]),&(b[0]),n);
444 switch (c1*3+c2)
445 {
446 case -4:
447 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
448 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
449 break;
450 case -3:
451 zero=1;
452 break;
453 case -2:
454 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
455 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
456 neg=1;
457 break;
458 case -1:
459 case 0:
460 case 1:
461 zero=1;
462 break;
463 case 2:
464 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
465 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
466 neg=1;
467 break;
468 case 3:
469 zero=1;
470 break;
471 case 4:
472 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
473 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
474 break;
475 }
476
477 oneg=neg;
478 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
479 /* r[10] = (a[1]*b[1]) */
480# ifdef BN_MUL_COMBA
481 if (n == 8)
482 {
483 bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
484 bn_mul_comba8(r,&(a[n]),&(b[n]));
485 }
486 else
487# endif
488 {
489 bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
490 bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
491 }
492
493 /* s0 == low(al*bl)
494 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
495 * We know s0 and s1 so the only unknown is high(al*bl)
496 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
497 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
498 */
499 if (l != NULL)
500 {
501 lp= &(t[n2+n]);
502 c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n));
503 }
504 else
505 {
506 c1=0;
507 lp= &(r[0]);
508 }
509
510 if (neg)
511 neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n));
512 else
513 {
514 bn_add_words(&(t[n2]),lp,&(t[0]),n);
515 neg=0;
516 }
517
518 if (l != NULL)
519 {
520 bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
521 }
522 else
523 {
524 lp= &(t[n2+n]);
525 mp= &(t[n2]);
526 for (i=0; i<n; i++)
527 lp[i]=((~mp[i])+1)&BN_MASK2;
528 }
529
530 /* s[0] = low(al*bl)
531 * t[3] = high(al*bl)
532 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
533 * r[10] = (a[1]*b[1])
534 */
535 /* R[10] = al*bl
536 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
537 * R[32] = ah*bh
538 */
539 /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
540 * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
541 * R[3]=r[1]+(carry/borrow)
542 */
543 if (l != NULL)
544 {
545 lp= &(t[n2]);
546 c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n));
547 }
548 else
549 {
550 lp= &(t[n2+n]);
551 c1=0;
552 }
553 c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n));
554 if (oneg)
555 c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n));
556 else
557 c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n));
558
559 c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n));
560 c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n));
561 if (oneg)
562 c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n));
563 else
564 c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n));
565
566 if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
567 {
568 i=0;
569 if (c1 > 0)
570 {
571 lc=c1;
572 do {
573 ll=(r[i]+lc)&BN_MASK2;
574 r[i++]=ll;
575 lc=(lc > ll);
576 } while (lc);
577 }
578 else
579 {
580 lc= -c1;
581 do {
582 ll=r[i];
583 r[i++]=(ll-lc)&BN_MASK2;
584 lc=(lc > ll);
585 } while (lc);
586 }
587 }
588 if (c2 != 0) /* Add starting at r[1] */
589 {
590 i=n;
591 if (c2 > 0)
592 {
593 lc=c2;
594 do {
595 ll=(r[i]+lc)&BN_MASK2;
596 r[i++]=ll;
597 lc=(lc > ll);
598 } while (lc);
599 }
600 else
601 {
602 lc= -c2;
603 do {
604 ll=r[i];
605 r[i++]=(ll-lc)&BN_MASK2;
606 lc=(lc > ll);
607 } while (lc);
608 }
609 }
610 }
611#endif /* BN_RECURSION */
612
613int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
614 {
615 int top,al,bl;
616 BIGNUM *rr;
617 int ret = 0;
618#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
619 int i;
620#endif
621#ifdef BN_RECURSION
622 BIGNUM *t;
623 int j,k;
624#endif
625
626#ifdef BN_COUNT
627 printf("BN_mul %d * %d\n",a->top,b->top);
628#endif
629
630 bn_check_top(a);
631 bn_check_top(b);
632 bn_check_top(r);
633
634 al=a->top;
635 bl=b->top;
636
637 if ((al == 0) || (bl == 0))
638 {
639 BN_zero(r);
640 return(1);
641 }
642 top=al+bl;
643
644 BN_CTX_start(ctx);
645 if ((r == a) || (r == b))
646 {
647 if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
648 }
649 else
650 rr = r;
651 rr->neg=a->neg^b->neg;
652
653#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
654 i = al-bl;
655#endif
656#ifdef BN_MUL_COMBA
657 if (i == 0)
658 {
659# if 0
660 if (al == 4)
661 {
662 if (bn_wexpand(rr,8) == NULL) goto err;
663 rr->top=8;
664 bn_mul_comba4(rr->d,a->d,b->d);
665 goto end;
666 }
667# endif
668 if (al == 8)
669 {
670 if (bn_wexpand(rr,16) == NULL) goto err;
671 rr->top=16;
672 bn_mul_comba8(rr->d,a->d,b->d);
673 goto end;
674 }
675 }
676#endif /* BN_MUL_COMBA */
677#ifdef BN_RECURSION
678 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
679 {
680 if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
681 {
682 if (bn_wexpand(b,al) == NULL) goto err;
683 b->d[bl]=0;
684 bl++;
685 i--;
686 }
687 else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
688 {
689 if (bn_wexpand(a,bl) == NULL) goto err;
690 a->d[al]=0;
691 al++;
692 i++;
693 }
694 if (i == 0)
695 {
696 /* symmetric and > 4 */
697 /* 16 or larger */
698 j=BN_num_bits_word((BN_ULONG)al);
699 j=1<<(j-1);
700 k=j+j;
701 t = BN_CTX_get(ctx);
702 if (al == j) /* exact multiple */
703 {
704 if (bn_wexpand(t,k*2) == NULL) goto err;
705 if (bn_wexpand(rr,k*2) == NULL) goto err;
706 bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
707 }
708 else
709 {
710 if (bn_wexpand(a,k) == NULL) goto err;
711 if (bn_wexpand(b,k) == NULL) goto err;
712 if (bn_wexpand(t,k*4) == NULL) goto err;
713 if (bn_wexpand(rr,k*4) == NULL) goto err;
714 for (i=a->top; i<k; i++)
715 a->d[i]=0;
716 for (i=b->top; i<k; i++)
717 b->d[i]=0;
718 bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
719 }
720 rr->top=top;
721 goto end;
722 }
723 }
724#endif /* BN_RECURSION */
725 if (bn_wexpand(rr,top) == NULL) goto err;
726 rr->top=top;
727 bn_mul_normal(rr->d,a->d,al,b->d,bl);
728
729#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
730end:
731#endif
732 bn_fix_top(rr);
733 if (r != rr) BN_copy(r,rr);
734 ret=1;
735err:
736 BN_CTX_end(ctx);
737 return(ret);
738 }
739
740void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
741 {
742 BN_ULONG *rr;
743
744#ifdef BN_COUNT
745 printf(" bn_mul_normal %d * %d\n",na,nb);
746#endif
747
748 if (na < nb)
749 {
750 int itmp;
751 BN_ULONG *ltmp;
752
753 itmp=na; na=nb; nb=itmp;
754 ltmp=a; a=b; b=ltmp;
755
756 }
757 rr= &(r[na]);
758 rr[0]=bn_mul_words(r,a,na,b[0]);
759
760 for (;;)
761 {
762 if (--nb <= 0) return;
763 rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]);
764 if (--nb <= 0) return;
765 rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]);
766 if (--nb <= 0) return;
767 rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]);
768 if (--nb <= 0) return;
769 rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]);
770 rr+=4;
771 r+=4;
772 b+=4;
773 }
774 }
775
776void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
777 {
778#ifdef BN_COUNT
779 printf(" bn_mul_low_normal %d * %d\n",n,n);
780#endif
781 bn_mul_words(r,a,n,b[0]);
782
783 for (;;)
784 {
785 if (--n <= 0) return;
786 bn_mul_add_words(&(r[1]),a,n,b[1]);
787 if (--n <= 0) return;
788 bn_mul_add_words(&(r[2]),a,n,b[2]);
789 if (--n <= 0) return;
790 bn_mul_add_words(&(r[3]),a,n,b[3]);
791 if (--n <= 0) return;
792 bn_mul_add_words(&(r[4]),a,n,b[4]);
793 r+=4;
794 b+=4;
795 }
796 }
Note: See TracBrowser for help on using the repository browser.