crypto/bn/bn_mul.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <assert.h>
  11 #include "internal/cryptlib.h"
  12 #include "bn_lcl.h"
  13
  14 #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
  15 /*
  16  * Here follows specialised variants of bn_add_words() and bn_sub_words().
  17  * They have the property performing operations on arrays of different sizes.
  18  * The sizes of those arrays is expressed through cl, which is the common
  19  * length ( basically, min(len(a),len(b)) ), and dl, which is the delta
  20  * between the two lengths, calculated as len(a)-len(b). All lengths are the
  21  * number of BN_ULONGs...  For the operations that require a result array as
  22  * parameter, it must have the length cl+abs(dl). These functions should
  23  * probably end up in bn_asm.c as soon as there are assembler counterparts
  24  * for the systems that use assembler files.
  25  */
  26
  27 BN_ULONG bn_sub_part_words(BN_ULONG *r,
  28                            const BN_ULONG *a, const BN_ULONG *b,
  29                            int cl, int dl)
  30 {
  31     BN_ULONG c, t;
  32
  33     assert(cl >= 0);
  34     c = bn_sub_words(r, a, b, cl);
  35
  36     if (dl == 0)
  37         return c;
  38
  39     r += cl;
  40     a += cl;
  41     b += cl;
  42
  43     if (dl < 0) {
  44         for (;;) {
  45             t = b[0];
  46             r[0] = (0 - t - c) & BN_MASK2;
  47             if (t != 0)
  48                 c = 1;
  49             if (++dl >= 0)
  50                 break;
  51
  52             t = b[1];
  53             r[1] = (0 - t - c) & BN_MASK2;
  54             if (t != 0)
  55                 c = 1;
  56             if (++dl >= 0)
  57                 break;
  58
  59             t = b[2];
  60             r[2] = (0 - t - c) & BN_MASK2;
  61             if (t != 0)
  62                 c = 1;
  63             if (++dl >= 0)
  64                 break;
  65
  66             t = b[3];
  67             r[3] = (0 - t - c) & BN_MASK2;
  68             if (t != 0)
  69                 c = 1;
  70             if (++dl >= 0)
  71                 break;
  72
  73             b += 4;
  74             r += 4;
  75         }
  76     } else {
  77         int save_dl = dl;
  78         while (c) {
  79             t = a[0];
  80             r[0] = (t - c) & BN_MASK2;
  81             if (t != 0)
  82                 c = 0;
  83             if (--dl <= 0)
  84                 break;
  85
  86             t = a[1];
  87             r[1] = (t - c) & BN_MASK2;
  88             if (t != 0)
  89                 c = 0;
  90             if (--dl <= 0)
  91                 break;
  92
  93             t = a[2];
  94             r[2] = (t - c) & BN_MASK2;
  95             if (t != 0)
  96                 c = 0;
  97             if (--dl <= 0)
  98                 break;
  99
 100             t = a[3];
 101             r[3] = (t - c) & BN_MASK2;
 102             if (t != 0)
 103                 c = 0;
 104             if (--dl <= 0)
 105                 break;
 106
 107             save_dl = dl;
 108             a += 4;
 109             r += 4;
 110         }
 111         if (dl > 0) {
 112             if (save_dl > dl) {
 113                 switch (save_dl - dl) {
 114                 case 1:
 115                     r[1] = a[1];
 116                     if (--dl <= 0)
 117                         break;
 118                     /* fall thru */
 119                 case 2:
 120                     r[2] = a[2];
 121                     if (--dl <= 0)
 122                         break;
 123                     /* fall thru */
 124                 case 3:
 125                     r[3] = a[3];
 126                     if (--dl <= 0)
 127                         break;
 128                 }
 129                 a += 4;
 130                 r += 4;
 131             }
 132         }
 133         if (dl > 0) {
 134             for (;;) {
 135                 r[0] = a[0];
 136                 if (--dl <= 0)
 137                     break;
 138                 r[1] = a[1];
 139                 if (--dl <= 0)
 140                     break;
 141                 r[2] = a[2];
 142                 if (--dl <= 0)
 143                     break;
 144                 r[3] = a[3];
 145                 if (--dl <= 0)
 146                     break;
 147
 148                 a += 4;
 149                 r += 4;
 150             }
 151         }
 152     }
 153     return c;
 154 }
 155 #endif
 156
 157 #ifdef BN_RECURSION
 158 /*
 159  * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of
 160  * Computer Programming, Vol. 2)
 161  */
 162
 163 /*-
 164  * r is 2*n2 words in size,
 165  * a and b are both n2 words in size.
 166  * n2 must be a power of 2.
 167  * We multiply and return the result.
 168  * t must be 2*n2 words in size
 169  * We calculate
 170  * a[0]*b[0]
 171  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
 172  * a[1]*b[1]
 173  */
 174 /* dnX may not be positive, but n2/2+dnX has to be */
 175 void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
 176                       int dna, int dnb, BN_ULONG *t)
 177 {
 178     int n = n2 / 2, c1, c2;
 179     int tna = n + dna, tnb = n + dnb;
 180     unsigned int neg, zero;
 181     BN_ULONG ln, lo, *p;
 182
 183 # ifdef BN_MUL_COMBA
 184 #  if 0
 185     if (n2 == 4) {
 186         bn_mul_comba4(r, a, b);
 187         return;
 188     }
 189 #  endif
 190     /*
 191      * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
 192      * [steve]
 193      */
 194     if (n2 == 8 && dna == 0 && dnb == 0) {
 195         bn_mul_comba8(r, a, b);
 196         return;
 197     }
 198 # endif                         /* BN_MUL_COMBA */
 199     /* Else do normal multiply */
 200     if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
 201         bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
 202         if ((dna + dnb) < 0)
 203             memset(&r[2 * n2 + dna + dnb], 0,
 204                    sizeof(BN_ULONG) * -(dna + dnb));
 205         return;
 206     }
 207     /* r=(a[0]-a[1])*(b[1]-b[0]) */
 208     c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
 209     c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
 210     zero = neg = 0;
 211     switch (c1 * 3 + c2) {
 212     case -4:
 213         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
 214         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
 215         break;
 216     case -3:
 217         zero = 1;
 218         break;
 219     case -2:
 220         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
 221         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
 222         neg = 1;
 223         break;
 224     case -1:
 225     case 0:
 226     case 1:
 227         zero = 1;
 228         break;
 229     case 2:
 230         bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
 231         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
 232         neg = 1;
 233         break;
 234     case 3:
 235         zero = 1;
 236         break;
 237     case 4:
 238         bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
 239         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
 240         break;
 241     }
 242
 243 # ifdef BN_MUL_COMBA
 244     if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
 245                                            * extra args to do this well */
 246         if (!zero)
 247             bn_mul_comba4(&(t[n2]), t, &(t[n]));
 248         else
 249             memset(&t[n2], 0, sizeof(*t) * 8);
 250
 251         bn_mul_comba4(r, a, b);
 252         bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
 253     } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
 254                                                   * take extra args to do
 255                                                   * this well */
 256         if (!zero)
 257             bn_mul_comba8(&(t[n2]), t, &(t[n]));
 258         else
 259             memset(&t[n2], 0, sizeof(*t) * 16);
 260
 261         bn_mul_comba8(r, a, b);
 262         bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
 263     } else
 264 # endif                         /* BN_MUL_COMBA */
 265     {
 266         p = &(t[n2 * 2]);
 267         if (!zero)
 268             bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
 269         else
 270             memset(&t[n2], 0, sizeof(*t) * n2);
 271         bn_mul_recursive(r, a, b, n, 0, 0, p);
 272         bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
 273     }
 274
 275     /*-
 276      * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
 277      * r[10] holds (a[0]*b[0])
 278      * r[32] holds (b[1]*b[1])
 279      */
 280
 281     c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
 282
 283     if (neg) {                  /* if t[32] is negative */
 284         c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
 285     } else {
 286         /* Might have a carry */
 287         c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
 288     }
 289
 290     /*-
 291      * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
 292      * r[10] holds (a[0]*b[0])
 293      * r[32] holds (b[1]*b[1])
 294      * c1 holds the carry bits
 295      */
 296     c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
 297     if (c1) {
 298         p = &(r[n + n2]);
 299         lo = *p;
 300         ln = (lo + c1) & BN_MASK2;
 301         *p = ln;
 302
 303         /*
 304          * The overflow will stop before we over write words we should not
 305          * overwrite
 306          */
 307         if (ln < (BN_ULONG)c1) {
 308             do {
 309                 p++;
 310                 lo = *p;
 311                 ln = (lo + 1) & BN_MASK2;
 312                 *p = ln;
 313             } while (ln == 0);
 314         }
 315     }
 316 }
 317
 318 /*
 319  * n+tn is the word length t needs to be n*4 is size, as does r
 320  */
 321 /* tnX may not be negative but less than n */
 322 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
 323                            int tna, int tnb, BN_ULONG *t)
 324 {
 325     int i, j, n2 = n * 2;
 326     int c1, c2, neg;
 327     BN_ULONG ln, lo, *p;
 328
 329     if (n < 8) {
 330         bn_mul_normal(r, a, n + tna, b, n + tnb);
 331         return;
 332     }
 333
 334     /* r=(a[0]-a[1])*(b[1]-b[0]) */
 335     c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
 336     c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
 337     neg = 0;
 338     switch (c1 * 3 + c2) {
 339     case -4:
 340         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
 341         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
 342         break;
 343     case -3:
 344     case -2:
 345         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
 346         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
 347         neg = 1;
 348         break;
 349     case -1:
 350     case 0:
 351     case 1:
 352     case 2:
 353         bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
 354         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
 355         neg = 1;
 356         break;
 357     case 3:
 358     case 4:
 359         bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
 360         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
 361         break;
 362     }
 363     /*
 364      * The zero case isn't yet implemented here. The speedup would probably
 365      * be negligible.
 366      */
 367 # if 0
 368     if (n == 4) {
 369         bn_mul_comba4(&(t[n2]), t, &(t[n]));
 370         bn_mul_comba4(r, a, b);
 371         bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
 372         memset(&r[n2 + tn * 2], 0, sizeof(*r) * (n2 - tn * 2));
 373     } else
 374 # endif
 375     if (n == 8) {
 376         bn_mul_comba8(&(t[n2]), t, &(t[n]));
 377         bn_mul_comba8(r, a, b);
 378         bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
 379         memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb));
 380     } else {
 381         p = &(t[n2 * 2]);
 382         bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
 383         bn_mul_recursive(r, a, b, n, 0, 0, p);
 384         i = n / 2;
 385         /*
 386          * If there is only a bottom half to the number, just do it
 387          */
 388         if (tna > tnb)
 389             j = tna - i;
 390         else
 391             j = tnb - i;
 392         if (j == 0) {
 393             bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
 394                              i, tna - i, tnb - i, p);
 395             memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2));
 396         } else if (j > 0) {     /* eg, n == 16, i == 8 and tn == 11 */
 397             bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
 398                                   i, tna - i, tnb - i, p);
 399             memset(&(r[n2 + tna + tnb]), 0,
 400                    sizeof(BN_ULONG) * (n2 - tna - tnb));
 401         } else {                /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
 402
 403             memset(&r[n2], 0, sizeof(*r) * n2);
 404             if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
 405                 && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
 406                 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
 407             } else {
 408                 for (;;) {
 409                     i /= 2;
 410                     /*
 411                      * these simplified conditions work exclusively because
 412                      * difference between tna and tnb is 1 or 0
 413                      */
 414                     if (i < tna || i < tnb) {
 415                         bn_mul_part_recursive(&(r[n2]),
 416                                               &(a[n]), &(b[n]),
 417                                               i, tna - i, tnb - i, p);
 418                         break;
 419                     } else if (i == tna || i == tnb) {
 420                         bn_mul_recursive(&(r[n2]),
 421                                          &(a[n]), &(b[n]),
 422                                          i, tna - i, tnb - i, p);
 423                         break;
 424                     }
 425                 }
 426             }
 427         }
 428     }
 429
 430     /*-
 431      * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
 432      * r[10] holds (a[0]*b[0])
 433      * r[32] holds (b[1]*b[1])
 434      */
 435
 436     c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
 437
 438     if (neg) {                  /* if t[32] is negative */
 439         c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
 440     } else {
 441         /* Might have a carry */
 442         c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
 443     }
 444
 445     /*-
 446      * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
 447      * r[10] holds (a[0]*b[0])
 448      * r[32] holds (b[1]*b[1])
 449      * c1 holds the carry bits
 450      */
 451     c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
 452     if (c1) {
 453         p = &(r[n + n2]);
 454         lo = *p;
 455         ln = (lo + c1) & BN_MASK2;
 456         *p = ln;
 457
 458         /*
 459          * The overflow will stop before we over write words we should not
 460          * overwrite
 461          */
 462         if (ln < (BN_ULONG)c1) {
 463             do {
 464                 p++;
 465                 lo = *p;
 466                 ln = (lo + 1) & BN_MASK2;
 467                 *p = ln;
 468             } while (ln == 0);
 469         }
 470     }
 471 }
 472
 473 /*-
 474  * a and b must be the same size, which is n2.
 475  * r needs to be n2 words and t needs to be n2*2
 476  */
 477 void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
 478                           BN_ULONG *t)
 479 {
 480     int n = n2 / 2;
 481
 482     bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
 483     if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
 484         bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
 485         bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
 486         bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
 487         bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
 488     } else {
 489         bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
 490         bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
 491         bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
 492         bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
 493     }
 494 }
 495 #endif                          /* BN_RECURSION */
 496
 497 int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 498 {
 499     int ret = 0;
 500     int top, al, bl;
 501     BIGNUM *rr;
 502 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
 503     int i;
 504 #endif
 505 #ifdef BN_RECURSION
 506     BIGNUM *t = NULL;
 507     int j = 0, k;
 508 #endif
 509
 510     bn_check_top(a);
 511     bn_check_top(b);
 512     bn_check_top(r);
 513
 514     al = a->top;
 515     bl = b->top;
 516
 517     if ((al == 0) || (bl == 0)) {
 518         BN_zero(r);
 519         return (1);
 520     }
 521     top = al + bl;
 522
 523     BN_CTX_start(ctx);
 524     if ((r == a) || (r == b)) {
 525         if ((rr = BN_CTX_get(ctx)) == NULL)
 526             goto err;
 527     } else
 528         rr = r;
 529
 530 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
 531     i = al - bl;
 532 #endif
 533 #ifdef BN_MUL_COMBA
 534     if (i == 0) {
 535 # if 0
 536         if (al == 4) {
 537             if (bn_wexpand(rr, 8) == NULL)
 538                 goto err;
 539             rr->top = 8;
 540             bn_mul_comba4(rr->d, a->d, b->d);
 541             goto end;
 542         }
 543 # endif
 544         if (al == 8) {
 545             if (bn_wexpand(rr, 16) == NULL)
 546                 goto err;
 547             rr->top = 16;
 548             bn_mul_comba8(rr->d, a->d, b->d);
 549             goto end;
 550         }
 551     }
 552 #endif                          /* BN_MUL_COMBA */
 553 #ifdef BN_RECURSION
 554     if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
 555         if (i >= -1 && i <= 1) {
 556             /*
 557              * Find out the power of two lower or equal to the longest of the
 558              * two numbers
 559              */
 560             if (i >= 0) {
 561                 j = BN_num_bits_word((BN_ULONG)al);
 562             }
 563             if (i == -1) {
 564                 j = BN_num_bits_word((BN_ULONG)bl);
 565             }
 566             j = 1 << (j - 1);
 567             assert(j <= al || j <= bl);
 568             k = j + j;
 569             t = BN_CTX_get(ctx);
 570             if (t == NULL)
 571                 goto err;
 572             if (al > j || bl > j) {
 573                 if (bn_wexpand(t, k * 4) == NULL)
 574                     goto err;
 575                 if (bn_wexpand(rr, k * 4) == NULL)
 576                     goto err;
 577                 bn_mul_part_recursive(rr->d, a->d, b->d,
 578                                       j, al - j, bl - j, t->d);
 579             } else {            /* al <= j || bl <= j */
 580
 581                 if (bn_wexpand(t, k * 2) == NULL)
 582                     goto err;
 583                 if (bn_wexpand(rr, k * 2) == NULL)
 584                     goto err;
 585                 bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
 586             }
 587             rr->top = top;
 588             goto end;
 589         }
 590 # if 0
 591         if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 592             BIGNUM *tmp_bn = (BIGNUM *)b;
 593             if (bn_wexpand(tmp_bn, al) == NULL)
 594                 goto err;
 595             tmp_bn->d[bl] = 0;
 596             bl++;
 597             i--;
 598         } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
 599             BIGNUM *tmp_bn = (BIGNUM *)a;
 600             if (bn_wexpand(tmp_bn, bl) == NULL)
 601                 goto err;
 602             tmp_bn->d[al] = 0;
 603             al++;
 604             i++;
 605         }
 606         if (i == 0) {
 607             /* symmetric and > 4 */
 608             /* 16 or larger */
 609             j = BN_num_bits_word((BN_ULONG)al);
 610             j = 1 << (j - 1);
 611             k = j + j;
 612             t = BN_CTX_get(ctx);
 613             if (al == j) {      /* exact multiple */
 614                 if (bn_wexpand(t, k * 2) == NULL)
 615                     goto err;
 616                 if (bn_wexpand(rr, k * 2) == NULL)
 617                     goto err;
 618                 bn_mul_recursive(rr->d, a->d, b->d, al, t->d);
 619             } else {
 620                 if (bn_wexpand(t, k * 4) == NULL)
 621                     goto err;
 622                 if (bn_wexpand(rr, k * 4) == NULL)
 623                     goto err;
 624                 bn_mul_part_recursive(rr->d, a->d, b->d, al - j, j, t->d);
 625             }
 626             rr->top = top;
 627             goto end;
 628         }
 629 # endif
 630     }
 631 #endif                          /* BN_RECURSION */
 632     if (bn_wexpand(rr, top) == NULL)
 633         goto err;
 634     rr->top = top;
 635     bn_mul_normal(rr->d, a->d, al, b->d, bl);
 636
 637 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
 638  end:
 639 #endif
 640     rr->neg = a->neg ^ b->neg;
 641     bn_correct_top(rr);
 642     if (r != rr && BN_copy(r, rr) == NULL)
 643         goto err;
 644
 645     ret = 1;
 646  err:
 647     bn_check_top(r);
 648     BN_CTX_end(ctx);
 649     return (ret);
 650 }
 651
 652 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
 653 {
 654     BN_ULONG *rr;
 655
 656     if (na < nb) {
 657         int itmp;
 658         BN_ULONG *ltmp;
 659
 660         itmp = na;
 661         na = nb;
 662         nb = itmp;
 663         ltmp = a;
 664         a = b;
 665         b = ltmp;
 666
 667     }
 668     rr = &(r[na]);
 669     if (nb <= 0) {
 670         (void)bn_mul_words(r, a, na, 0);
 671         return;
 672     } else
 673         rr[0] = bn_mul_words(r, a, na, b[0]);
 674
 675     for (;;) {
 676         if (--nb <= 0)
 677             return;
 678         rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
 679         if (--nb <= 0)
 680             return;
 681         rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
 682         if (--nb <= 0)
 683             return;
 684         rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
 685         if (--nb <= 0)
 686             return;
 687         rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
 688         rr += 4;
 689         r += 4;
 690         b += 4;
 691     }
 692 }
 693
 694 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
 695 {
 696     bn_mul_words(r, a, n, b[0]);
 697
 698     for (;;) {
 699         if (--n <= 0)
 700             return;
 701         bn_mul_add_words(&(r[1]), a, n, b[1]);
 702         if (--n <= 0)
 703             return;
 704         bn_mul_add_words(&(r[2]), a, n, b[2]);
 705         if (--n <= 0)
 706             return;
 707         bn_mul_add_words(&(r[3]), a, n, b[3]);
 708         if (--n <= 0)
 709             return;
 710         bn_mul_add_words(&(r[4]), a, n, b[4]);
 711         r += 4;
 712         b += 4;
 713     }
 714 }