| 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 |