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