summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_mul.c
diff options
context:
space:
mode:
authorbeck <>2000-03-19 11:13:58 +0000
committerbeck <>2000-03-19 11:13:58 +0000
commit796d609550df3a33fc11468741c5d2f6d3df4c11 (patch)
tree6c6d539061caa20372dad0ac4ddb1dfae2fbe7fe /src/lib/libcrypto/bn/bn_mul.c
parent5be3114c1fd7e0dfea1e38d3abb4cbba75244419 (diff)
downloadopenbsd-796d609550df3a33fc11468741c5d2f6d3df4c11.tar.gz
openbsd-796d609550df3a33fc11468741c5d2f6d3df4c11.tar.bz2
openbsd-796d609550df3a33fc11468741c5d2f6d3df4c11.zip
OpenSSL 0.9.5 merge
*warning* this bumps shared lib minors for libssl and libcrypto from 2.1 to 2.2 if you are using the ssl26 packages for ssh and other things to work you will need to get new ones (see ~beck/libsslsnap/<arch>) on cvs or ~beck/src-patent.tar.gz on cvs
Diffstat (limited to 'src/lib/libcrypto/bn/bn_mul.c')
-rw-r--r--src/lib/libcrypto/bn/bn_mul.c247
1 files changed, 141 insertions, 106 deletions
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c
index 38c47f3d1f..eb007e19e9 100644
--- a/src/lib/libcrypto/bn/bn_mul.c
+++ b/src/lib/libcrypto/bn/bn_mul.c
@@ -66,7 +66,7 @@
66 * n2 must be a power of 2. 66 * n2 must be a power of 2.
67 * We multiply and return the result. 67 * We multiply and return the result.
68 * t must be 2*n2 words in size 68 * t must be 2*n2 words in size
69 * We calulate 69 * We calculate
70 * a[0]*b[0] 70 * a[0]*b[0]
71 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 71 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
72 * a[1]*b[1] 72 * a[1]*b[1]
@@ -78,21 +78,23 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
78 unsigned int neg,zero; 78 unsigned int neg,zero;
79 BN_ULONG ln,lo,*p; 79 BN_ULONG ln,lo,*p;
80 80
81#ifdef BN_COUNT 81# ifdef BN_COUNT
82printf(" bn_mul_recursive %d * %d\n",n2,n2); 82 printf(" bn_mul_recursive %d * %d\n",n2,n2);
83#endif 83# endif
84#ifdef BN_MUL_COMBA 84# ifdef BN_MUL_COMBA
85/* if (n2 == 4) 85# if 0
86 if (n2 == 4)
86 { 87 {
87 bn_mul_comba4(r,a,b); 88 bn_mul_comba4(r,a,b);
88 return; 89 return;
89 } 90 }
90 else */ if (n2 == 8) 91# endif
92 if (n2 == 8)
91 { 93 {
92 bn_mul_comba8(r,a,b); 94 bn_mul_comba8(r,a,b);
93 return; 95 return;
94 } 96 }
95#endif 97# endif /* BN_MUL_COMBA */
96 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) 98 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
97 { 99 {
98 /* This should not happen */ 100 /* This should not happen */
@@ -136,7 +138,7 @@ printf(" bn_mul_recursive %d * %d\n",n2,n2);
136 break; 138 break;
137 } 139 }
138 140
139#ifdef BN_MUL_COMBA 141# ifdef BN_MUL_COMBA
140 if (n == 4) 142 if (n == 4)
141 { 143 {
142 if (!zero) 144 if (!zero)
@@ -158,7 +160,7 @@ printf(" bn_mul_recursive %d * %d\n",n2,n2);
158 bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n])); 160 bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
159 } 161 }
160 else 162 else
161#endif 163# endif /* BN_MUL_COMBA */
162 { 164 {
163 p= &(t[n2*2]); 165 p= &(t[n2*2]);
164 if (!zero) 166 if (!zero)
@@ -219,12 +221,12 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
219 int n, BN_ULONG *t) 221 int n, BN_ULONG *t)
220 { 222 {
221 int i,j,n2=n*2; 223 int i,j,n2=n*2;
222 unsigned int c1; 224 unsigned int c1,c2,neg,zero;
223 BN_ULONG ln,lo,*p; 225 BN_ULONG ln,lo,*p;
224 226
225#ifdef BN_COUNT 227# ifdef BN_COUNT
226printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n); 228 printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
227#endif 229# endif
228 if (n < 8) 230 if (n < 8)
229 { 231 {
230 i=tn+n; 232 i=tn+n;
@@ -233,17 +235,54 @@ printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
233 } 235 }
234 236
235 /* r=(a[0]-a[1])*(b[1]-b[0]) */ 237 /* r=(a[0]-a[1])*(b[1]-b[0]) */
236 bn_sub_words(t, a, &(a[n]),n); /* + */ 238 c1=bn_cmp_words(a,&(a[n]),n);
237 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ 239 c2=bn_cmp_words(&(b[n]),b,n);
238 240 zero=neg=0;
239/* if (n == 4) 241 switch (c1*3+c2)
242 {
243 case -4:
244 bn_sub_words(t, &(a[n]),a, n); /* - */
245 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
246 break;
247 case -3:
248 zero=1;
249 /* break; */
250 case -2:
251 bn_sub_words(t, &(a[n]),a, n); /* - */
252 bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
253 neg=1;
254 break;
255 case -1:
256 case 0:
257 case 1:
258 zero=1;
259 /* break; */
260 case 2:
261 bn_sub_words(t, a, &(a[n]),n); /* + */
262 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
263 neg=1;
264 break;
265 case 3:
266 zero=1;
267 /* break; */
268 case 4:
269 bn_sub_words(t, a, &(a[n]),n);
270 bn_sub_words(&(t[n]),&(b[n]),b, n);
271 break;
272 }
273 /* The zero case isn't yet implemented here. The speedup
274 would probably be negligible. */
275# if 0
276 if (n == 4)
240 { 277 {
241 bn_mul_comba4(&(t[n2]),t,&(t[n])); 278 bn_mul_comba4(&(t[n2]),t,&(t[n]));
242 bn_mul_comba4(r,a,b); 279 bn_mul_comba4(r,a,b);
243 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); 280 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
244 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); 281 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
245 } 282 }
246 else */ if (n == 8) 283 else
284# endif
285 if (n == 8)
247 { 286 {
248 bn_mul_comba8(&(t[n2]),t,&(t[n])); 287 bn_mul_comba8(&(t[n2]),t,&(t[n]));
249 bn_mul_comba8(r,a,b); 288 bn_mul_comba8(r,a,b);
@@ -308,7 +347,16 @@ printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
308 */ 347 */
309 348
310 c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); 349 c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
311 c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); 350
351 if (neg) /* if t[32] is negative */
352 {
353 c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
354 }
355 else
356 {
357 /* Might have a carry */
358 c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
359 }
312 360
313 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 361 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
314 * r[10] holds (a[0]*b[0]) 362 * r[10] holds (a[0]*b[0])
@@ -345,9 +393,9 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
345 { 393 {
346 int n=n2/2; 394 int n=n2/2;
347 395
348#ifdef BN_COUNT 396# ifdef BN_COUNT
349printf(" bn_mul_low_recursive %d * %d\n",n2,n2); 397 printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
350#endif 398# endif
351 399
352 bn_mul_recursive(r,a,b,n,&(t[0])); 400 bn_mul_recursive(r,a,b,n,&(t[0]));
353 if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) 401 if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
@@ -379,9 +427,9 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
379 int neg,oneg,zero; 427 int neg,oneg,zero;
380 BN_ULONG ll,lc,*lp,*mp; 428 BN_ULONG ll,lc,*lp,*mp;
381 429
382#ifdef BN_COUNT 430# ifdef BN_COUNT
383printf(" bn_mul_high %d * %d\n",n2,n2); 431 printf(" bn_mul_high %d * %d\n",n2,n2);
384#endif 432# endif
385 n=n2/2; 433 n=n2/2;
386 434
387 /* Calculate (al-ah)*(bh-bl) */ 435 /* Calculate (al-ah)*(bh-bl) */
@@ -424,14 +472,14 @@ printf(" bn_mul_high %d * %d\n",n2,n2);
424 oneg=neg; 472 oneg=neg;
425 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ 473 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
426 /* r[10] = (a[1]*b[1]) */ 474 /* r[10] = (a[1]*b[1]) */
427#ifdef BN_MUL_COMBA 475# ifdef BN_MUL_COMBA
428 if (n == 8) 476 if (n == 8)
429 { 477 {
430 bn_mul_comba8(&(t[0]),&(r[0]),&(r[n])); 478 bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
431 bn_mul_comba8(r,&(a[n]),&(b[n])); 479 bn_mul_comba8(r,&(a[n]),&(b[n]));
432 } 480 }
433 else 481 else
434#endif 482# endif
435 { 483 {
436 bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2])); 484 bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
437 bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2])); 485 bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
@@ -555,19 +603,23 @@ printf(" bn_mul_high %d * %d\n",n2,n2);
555 } 603 }
556 } 604 }
557 } 605 }
558#endif 606#endif /* BN_RECURSION */
559 607
560int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) 608int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
561 { 609 {
562 int top,al,bl; 610 int top,al,bl;
563 BIGNUM *rr; 611 BIGNUM *rr;
612 int ret = 0;
613#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
614 int i;
615#endif
564#ifdef BN_RECURSION 616#ifdef BN_RECURSION
565 BIGNUM *t; 617 BIGNUM *t;
566 int i,j,k; 618 int j,k;
567#endif 619#endif
568 620
569#ifdef BN_COUNT 621#ifdef BN_COUNT
570printf("BN_mul %d * %d\n",a->top,b->top); 622 printf("BN_mul %d * %d\n",a->top,b->top);
571#endif 623#endif
572 624
573 bn_check_top(a); 625 bn_check_top(a);
@@ -585,115 +637,99 @@ printf("BN_mul %d * %d\n",a->top,b->top);
585 } 637 }
586 top=al+bl; 638 top=al+bl;
587 639
640 BN_CTX_start(ctx);
588 if ((r == a) || (r == b)) 641 if ((r == a) || (r == b))
589 rr= &(ctx->bn[ctx->tos+1]); 642 {
643 if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
644 }
590 else 645 else
591 rr=r; 646 rr = r;
592 647
593#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 648#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
594 if (al == bl) 649 i = al-bl;
650#endif
651#ifdef BN_MUL_COMBA
652 if (i == 0)
595 { 653 {
596# ifdef BN_MUL_COMBA 654# if 0
597/* if (al == 4) 655 if (al == 4)
598 { 656 {
599 if (bn_wexpand(rr,8) == NULL) return(0); 657 if (bn_wexpand(rr,8) == NULL) goto err;
600 rr->top=8; 658 rr->top=8;
601 bn_mul_comba4(rr->d,a->d,b->d); 659 bn_mul_comba4(rr->d,a->d,b->d);
602 goto end; 660 goto end;
603 } 661 }
604 else */ if (al == 8) 662# endif
663 if (al == 8)
605 { 664 {
606 if (bn_wexpand(rr,16) == NULL) return(0); 665 if (bn_wexpand(rr,16) == NULL) goto err;
607 rr->top=16; 666 rr->top=16;
608 bn_mul_comba8(rr->d,a->d,b->d); 667 bn_mul_comba8(rr->d,a->d,b->d);
609 goto end; 668 goto end;
610 } 669 }
611 else
612# endif
613#ifdef BN_RECURSION
614 if (al < BN_MULL_SIZE_NORMAL)
615#endif
616 {
617 if (bn_wexpand(rr,top) == NULL) return(0);
618 rr->top=top;
619 bn_mul_normal(rr->d,a->d,al,b->d,bl);
620 goto end;
621 }
622# ifdef BN_RECURSION
623 goto symetric;
624# endif
625 } 670 }
626#endif 671#endif /* BN_MUL_COMBA */
627#ifdef BN_RECURSION 672#ifdef BN_RECURSION
628 else if ((al < BN_MULL_SIZE_NORMAL) || (bl < BN_MULL_SIZE_NORMAL)) 673 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
629 { 674 {
630 if (bn_wexpand(rr,top) == NULL) return(0); 675 if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
631 rr->top=top;
632 bn_mul_normal(rr->d,a->d,al,b->d,bl);
633 goto end;
634 }
635 else
636 {
637 i=(al-bl);
638 if ((i == 1) && !BN_get_flags(b,BN_FLG_STATIC_DATA))
639 { 676 {
640 bn_wexpand(b,al); 677 bn_wexpand(b,al);
641 b->d[bl]=0; 678 b->d[bl]=0;
642 bl++; 679 bl++;
643 goto symetric; 680 i--;
644 } 681 }
645 else if ((i == -1) && !BN_get_flags(a,BN_FLG_STATIC_DATA)) 682 else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
646 { 683 {
647 bn_wexpand(a,bl); 684 bn_wexpand(a,bl);
648 a->d[al]=0; 685 a->d[al]=0;
649 al++; 686 al++;
650 goto symetric; 687 i++;
688 }
689 if (i == 0)
690 {
691 /* symmetric and > 4 */
692 /* 16 or larger */
693 j=BN_num_bits_word((BN_ULONG)al);
694 j=1<<(j-1);
695 k=j+j;
696 t = BN_CTX_get(ctx);
697 if (al == j) /* exact multiple */
698 {
699 bn_wexpand(t,k*2);
700 bn_wexpand(rr,k*2);
701 bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
702 }
703 else
704 {
705 bn_wexpand(a,k);
706 bn_wexpand(b,k);
707 bn_wexpand(t,k*4);
708 bn_wexpand(rr,k*4);
709 for (i=a->top; i<k; i++)
710 a->d[i]=0;
711 for (i=b->top; i<k; i++)
712 b->d[i]=0;
713 bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
714 }
715 rr->top=top;
716 goto end;
651 } 717 }
652 } 718 }
653#endif 719#endif /* BN_RECURSION */
654 720 if (bn_wexpand(rr,top) == NULL) goto err;
655 /* asymetric and >= 4 */
656 if (bn_wexpand(rr,top) == NULL) return(0);
657 rr->top=top; 721 rr->top=top;
658 bn_mul_normal(rr->d,a->d,al,b->d,bl); 722 bn_mul_normal(rr->d,a->d,al,b->d,bl);
659 723
660#ifdef BN_RECURSION
661 if (0)
662 {
663symetric:
664 /* symetric and > 4 */
665 /* 16 or larger */
666 j=BN_num_bits_word((BN_ULONG)al);
667 j=1<<(j-1);
668 k=j+j;
669 t= &(ctx->bn[ctx->tos]);
670 if (al == j) /* exact multiple */
671 {
672 bn_wexpand(t,k*2);
673 bn_wexpand(rr,k*2);
674 bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
675 }
676 else
677 {
678 bn_wexpand(a,k);
679 bn_wexpand(b,k);
680 bn_wexpand(t,k*4);
681 bn_wexpand(rr,k*4);
682 for (i=a->top; i<k; i++)
683 a->d[i]=0;
684 for (i=b->top; i<k; i++)
685 b->d[i]=0;
686 bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
687 }
688 rr->top=top;
689 }
690#endif
691#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 724#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
692end: 725end:
693#endif 726#endif
694 bn_fix_top(rr); 727 bn_fix_top(rr);
695 if (r != rr) BN_copy(r,rr); 728 if (r != rr) BN_copy(r,rr);
696 return(1); 729 ret=1;
730err:
731 BN_CTX_end(ctx);
732 return(ret);
697 } 733 }
698 734
699void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 735void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
@@ -701,7 +737,7 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
701 BN_ULONG *rr; 737 BN_ULONG *rr;
702 738
703#ifdef BN_COUNT 739#ifdef BN_COUNT
704printf(" bn_mul_normal %d * %d\n",na,nb); 740 printf(" bn_mul_normal %d * %d\n",na,nb);
705#endif 741#endif
706 742
707 if (na < nb) 743 if (na < nb)
@@ -735,7 +771,7 @@ printf(" bn_mul_normal %d * %d\n",na,nb);
735void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) 771void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
736 { 772 {
737#ifdef BN_COUNT 773#ifdef BN_COUNT
738printf(" bn_mul_low_normal %d * %d\n",n,n); 774 printf(" bn_mul_low_normal %d * %d\n",n,n);
739#endif 775#endif
740 bn_mul_words(r,a,n,b[0]); 776 bn_mul_words(r,a,n,b[0]);
741 777
@@ -753,4 +789,3 @@ printf(" bn_mul_low_normal %d * %d\n",n,n);
753 b+=4; 789 b+=4;
754 } 790 }
755 } 791 }
756