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