cscrypt/bn_mul.c

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