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