OLD | NEW |
1 /* crypto/bn/bn_mul.c */ | 1 /* crypto/bn/bn_mul.c */ |
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
3 * All rights reserved. | 3 * All rights reserved. |
4 * | 4 * |
5 * This package is an SSL implementation written | 5 * This package is an SSL implementation written |
6 * by Eric Young (eay@cryptsoft.com). | 6 * by Eric Young (eay@cryptsoft.com). |
7 * The implementation was written so as to conform with Netscapes SSL. | 7 * The implementation was written so as to conform with Netscapes SSL. |
8 * | 8 * |
9 * This library is free for commercial and non-commercial use as long as | 9 * This library is free for commercial and non-commercial use as long as |
10 * the following conditions are aheared to. The following conditions | 10 * the following conditions are aheared to. The following conditions |
(...skipping 533 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
544 } | 544 } |
545 } | 545 } |
546 | 546 |
547 /* n+tn is the word length | 547 /* n+tn is the word length |
548 * t needs to be n*4 is size, as does r */ | 548 * t needs to be n*4 is size, as does r */ |
549 /* tnX may not be negative but less than n */ | 549 /* tnX may not be negative but less than n */ |
550 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, | 550 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, |
551 int tna, int tnb, BN_ULONG *t) | 551 int tna, int tnb, BN_ULONG *t) |
552 { | 552 { |
553 int i,j,n2=n*2; | 553 int i,j,n2=n*2; |
554 » int c1,c2,neg,zero; | 554 » int c1,c2,neg; |
555 BN_ULONG ln,lo,*p; | 555 BN_ULONG ln,lo,*p; |
556 | 556 |
557 # ifdef BN_COUNT | 557 # ifdef BN_COUNT |
558 fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n", | 558 fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n", |
559 n, tna, n, tnb); | 559 n, tna, n, tnb); |
560 # endif | 560 # endif |
561 if (n < 8) | 561 if (n < 8) |
562 { | 562 { |
563 bn_mul_normal(r,a,n+tna,b,n+tnb); | 563 bn_mul_normal(r,a,n+tna,b,n+tnb); |
564 return; | 564 return; |
565 } | 565 } |
566 | 566 |
567 /* r=(a[0]-a[1])*(b[1]-b[0]) */ | 567 /* r=(a[0]-a[1])*(b[1]-b[0]) */ |
568 c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); | 568 c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); |
569 c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); | 569 c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); |
570 » zero=neg=0; | 570 » neg=0; |
571 switch (c1*3+c2) | 571 switch (c1*3+c2) |
572 { | 572 { |
573 case -4: | 573 case -4: |
574 bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ | 574 bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
575 bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | 575 bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ |
576 break; | 576 break; |
577 case -3: | 577 case -3: |
578 zero=1; | |
579 /* break; */ | 578 /* break; */ |
580 case -2: | 579 case -2: |
581 bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ | 580 bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
582 bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ | 581 bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ |
583 neg=1; | 582 neg=1; |
584 break; | 583 break; |
585 case -1: | 584 case -1: |
586 case 0: | 585 case 0: |
587 case 1: | 586 case 1: |
588 zero=1; | |
589 /* break; */ | 587 /* break; */ |
590 case 2: | 588 case 2: |
591 bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ | 589 bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ |
592 bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | 590 bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ |
593 neg=1; | 591 neg=1; |
594 break; | 592 break; |
595 case 3: | 593 case 3: |
596 zero=1; | |
597 /* break; */ | 594 /* break; */ |
598 case 4: | 595 case 4: |
599 bn_sub_part_words(t, a, &(a[n]),tna,n-tna); | 596 bn_sub_part_words(t, a, &(a[n]),tna,n-tna); |
600 bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); | 597 bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); |
601 break; | 598 break; |
602 } | 599 } |
603 /* The zero case isn't yet implemented here. The speedup | 600 /* The zero case isn't yet implemented here. The speedup |
604 would probably be negligible. */ | 601 would probably be negligible. */ |
605 # if 0 | 602 # if 0 |
606 if (n == 4) | 603 if (n == 4) |
(...skipping 398 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1005 bn_mul_comba8(rr->d,a->d,b->d); | 1002 bn_mul_comba8(rr->d,a->d,b->d); |
1006 goto end; | 1003 goto end; |
1007 } | 1004 } |
1008 } | 1005 } |
1009 #endif /* BN_MUL_COMBA */ | 1006 #endif /* BN_MUL_COMBA */ |
1010 #ifdef BN_RECURSION | 1007 #ifdef BN_RECURSION |
1011 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) | 1008 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) |
1012 { | 1009 { |
1013 if (i >= -1 && i <= 1) | 1010 if (i >= -1 && i <= 1) |
1014 { | 1011 { |
1015 int sav_j =0; | |
1016 /* Find out the power of two lower or equal | 1012 /* Find out the power of two lower or equal |
1017 to the longest of the two numbers */ | 1013 to the longest of the two numbers */ |
1018 if (i >= 0) | 1014 if (i >= 0) |
1019 { | 1015 { |
1020 j = BN_num_bits_word((BN_ULONG)al); | 1016 j = BN_num_bits_word((BN_ULONG)al); |
1021 } | 1017 } |
1022 if (i == -1) | 1018 if (i == -1) |
1023 { | 1019 { |
1024 j = BN_num_bits_word((BN_ULONG)bl); | 1020 j = BN_num_bits_word((BN_ULONG)bl); |
1025 } | 1021 } |
1026 sav_j = j; | |
1027 j = 1<<(j-1); | 1022 j = 1<<(j-1); |
1028 assert(j <= al || j <= bl); | 1023 assert(j <= al || j <= bl); |
1029 k = j+j; | 1024 k = j+j; |
1030 t = BN_CTX_get(ctx); | 1025 t = BN_CTX_get(ctx); |
1031 if (t == NULL) | 1026 if (t == NULL) |
1032 goto err; | 1027 goto err; |
1033 if (al > j || bl > j) | 1028 if (al > j || bl > j) |
1034 { | 1029 { |
1035 if (bn_wexpand(t,k*4) == NULL) goto err; | 1030 if (bn_wexpand(t,k*4) == NULL) goto err; |
1036 if (bn_wexpand(rr,k*4) == NULL) goto err; | 1031 if (bn_wexpand(rr,k*4) == NULL) goto err; |
(...skipping 125 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1162 if (--n <= 0) return; | 1157 if (--n <= 0) return; |
1163 bn_mul_add_words(&(r[2]),a,n,b[2]); | 1158 bn_mul_add_words(&(r[2]),a,n,b[2]); |
1164 if (--n <= 0) return; | 1159 if (--n <= 0) return; |
1165 bn_mul_add_words(&(r[3]),a,n,b[3]); | 1160 bn_mul_add_words(&(r[3]),a,n,b[3]); |
1166 if (--n <= 0) return; | 1161 if (--n <= 0) return; |
1167 bn_mul_add_words(&(r[4]),a,n,b[4]); | 1162 bn_mul_add_words(&(r[4]),a,n,b[4]); |
1168 r+=4; | 1163 r+=4; |
1169 b+=4; | 1164 b+=4; |
1170 } | 1165 } |
1171 } | 1166 } |
OLD | NEW |