Home | History | Annotate | Download | only in bn
      1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com)
      2  * All rights reserved.
      3  *
      4  * This package is an SSL implementation written
      5  * by Eric Young (eay (at) cryptsoft.com).
      6  * The implementation was written so as to conform with Netscapes SSL.
      7  *
      8  * This library is free for commercial and non-commercial use as long as
      9  * the following conditions are aheared to.  The following conditions
     10  * apply to all code found in this distribution, be it the RC4, RSA,
     11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
     12  * included with this distribution is covered by the same copyright terms
     13  * except that the holder is Tim Hudson (tjh (at) cryptsoft.com).
     14  *
     15  * Copyright remains Eric Young's, and as such any Copyright notices in
     16  * the code are not to be removed.
     17  * If this package is used in a product, Eric Young should be given attribution
     18  * as the author of the parts of the library used.
     19  * This can be in the form of a textual message at program startup or
     20  * in documentation (online or textual) provided with the package.
     21  *
     22  * Redistribution and use in source and binary forms, with or without
     23  * modification, are permitted provided that the following conditions
     24  * are met:
     25  * 1. Redistributions of source code must retain the copyright
     26  *    notice, this list of conditions and the following disclaimer.
     27  * 2. Redistributions in binary form must reproduce the above copyright
     28  *    notice, this list of conditions and the following disclaimer in the
     29  *    documentation and/or other materials provided with the distribution.
     30  * 3. All advertising materials mentioning features or use of this software
     31  *    must display the following acknowledgement:
     32  *    "This product includes cryptographic software written by
     33  *     Eric Young (eay (at) cryptsoft.com)"
     34  *    The word 'cryptographic' can be left out if the rouines from the library
     35  *    being used are not cryptographic related :-).
     36  * 4. If you include any Windows specific code (or a derivative thereof) from
     37  *    the apps directory (application code) you must include an acknowledgement:
     38  *    "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)"
     39  *
     40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
     41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
     44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     50  * SUCH DAMAGE.
     51  *
     52  * The licence and distribution terms for any publically available version or
     53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
     54  * copied and put under another distribution licence
     55  * [including the GNU Public Licence.] */
     56 
     57 #include <openssl/bn.h>
     58 
     59 #include <assert.h>
     60 #include <string.h>
     61 
     62 #include "internal.h"
     63 
     64 
     65 #define BN_MUL_RECURSIVE_SIZE_NORMAL 16
     66 #define BN_SQR_RECURSIVE_SIZE_NORMAL BN_MUL_RECURSIVE_SIZE_NORMAL
     67 
     68 
     69 static void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
     70                           int nb) {
     71   BN_ULONG *rr;
     72 
     73   if (na < nb) {
     74     int itmp;
     75     BN_ULONG *ltmp;
     76 
     77     itmp = na;
     78     na = nb;
     79     nb = itmp;
     80     ltmp = a;
     81     a = b;
     82     b = ltmp;
     83   }
     84   rr = &(r[na]);
     85   if (nb <= 0) {
     86     (void)bn_mul_words(r, a, na, 0);
     87     return;
     88   } else {
     89     rr[0] = bn_mul_words(r, a, na, b[0]);
     90   }
     91 
     92   for (;;) {
     93     if (--nb <= 0) {
     94       return;
     95     }
     96     rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
     97     if (--nb <= 0) {
     98       return;
     99     }
    100     rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
    101     if (--nb <= 0) {
    102       return;
    103     }
    104     rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
    105     if (--nb <= 0) {
    106       return;
    107     }
    108     rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
    109     rr += 4;
    110     r += 4;
    111     b += 4;
    112   }
    113 }
    114 
    115 #if !defined(OPENSSL_X86) || defined(OPENSSL_NO_ASM)
    116 /* Here follows specialised variants of bn_add_words() and bn_sub_words(). They
    117  * have the property performing operations on arrays of different sizes. The
    118  * sizes of those arrays is expressed through cl, which is the common length (
    119  * basicall, min(len(a),len(b)) ), and dl, which is the delta between the two
    120  * lengths, calculated as len(a)-len(b). All lengths are the number of
    121  * BN_ULONGs...  For the operations that require a result array as parameter,
    122  * it must have the length cl+abs(dl). These functions should probably end up
    123  * in bn_asm.c as soon as there are assembler counterparts for the systems that
    124  * use assembler files.  */
    125 
    126 static BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a,
    127                                   const BN_ULONG *b, int cl, int dl) {
    128   BN_ULONG c, t;
    129 
    130   assert(cl >= 0);
    131   c = bn_sub_words(r, a, b, cl);
    132 
    133   if (dl == 0) {
    134     return c;
    135   }
    136 
    137   r += cl;
    138   a += cl;
    139   b += cl;
    140 
    141   if (dl < 0) {
    142     for (;;) {
    143       t = b[0];
    144       r[0] = (0 - t - c) & BN_MASK2;
    145       if (t != 0) {
    146         c = 1;
    147       }
    148       if (++dl >= 0) {
    149         break;
    150       }
    151 
    152       t = b[1];
    153       r[1] = (0 - t - c) & BN_MASK2;
    154       if (t != 0) {
    155         c = 1;
    156       }
    157       if (++dl >= 0) {
    158         break;
    159       }
    160 
    161       t = b[2];
    162       r[2] = (0 - t - c) & BN_MASK2;
    163       if (t != 0) {
    164         c = 1;
    165       }
    166       if (++dl >= 0) {
    167         break;
    168       }
    169 
    170       t = b[3];
    171       r[3] = (0 - t - c) & BN_MASK2;
    172       if (t != 0) {
    173         c = 1;
    174       }
    175       if (++dl >= 0) {
    176         break;
    177       }
    178 
    179       b += 4;
    180       r += 4;
    181     }
    182   } else {
    183     int save_dl = dl;
    184     while (c) {
    185       t = a[0];
    186       r[0] = (t - c) & BN_MASK2;
    187       if (t != 0) {
    188         c = 0;
    189       }
    190       if (--dl <= 0) {
    191         break;
    192       }
    193 
    194       t = a[1];
    195       r[1] = (t - c) & BN_MASK2;
    196       if (t != 0) {
    197         c = 0;
    198       }
    199       if (--dl <= 0) {
    200         break;
    201       }
    202 
    203       t = a[2];
    204       r[2] = (t - c) & BN_MASK2;
    205       if (t != 0) {
    206         c = 0;
    207       }
    208       if (--dl <= 0) {
    209         break;
    210       }
    211 
    212       t = a[3];
    213       r[3] = (t - c) & BN_MASK2;
    214       if (t != 0) {
    215         c = 0;
    216       }
    217       if (--dl <= 0) {
    218         break;
    219       }
    220 
    221       save_dl = dl;
    222       a += 4;
    223       r += 4;
    224     }
    225     if (dl > 0) {
    226       if (save_dl > dl) {
    227         switch (save_dl - dl) {
    228           case 1:
    229             r[1] = a[1];
    230             if (--dl <= 0) {
    231               break;
    232             }
    233           case 2:
    234             r[2] = a[2];
    235             if (--dl <= 0) {
    236               break;
    237             }
    238           case 3:
    239             r[3] = a[3];
    240             if (--dl <= 0) {
    241               break;
    242             }
    243         }
    244         a += 4;
    245         r += 4;
    246       }
    247     }
    248 
    249     if (dl > 0) {
    250       for (;;) {
    251         r[0] = a[0];
    252         if (--dl <= 0) {
    253           break;
    254         }
    255         r[1] = a[1];
    256         if (--dl <= 0) {
    257           break;
    258         }
    259         r[2] = a[2];
    260         if (--dl <= 0) {
    261           break;
    262         }
    263         r[3] = a[3];
    264         if (--dl <= 0) {
    265           break;
    266         }
    267 
    268         a += 4;
    269         r += 4;
    270       }
    271     }
    272   }
    273 
    274   return c;
    275 }
    276 #else
    277 /* On other platforms the function is defined in asm. */
    278 BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
    279                            int cl, int dl);
    280 #endif
    281 
    282 /* Karatsuba recursive multiplication algorithm
    283  * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
    284 
    285 /* r is 2*n2 words in size,
    286  * a and b are both n2 words in size.
    287  * n2 must be a power of 2.
    288  * We multiply and return the result.
    289  * t must be 2*n2 words in size
    290  * We calculate
    291  * a[0]*b[0]
    292  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
    293  * a[1]*b[1]
    294  */
    295 /* dnX may not be positive, but n2/2+dnX has to be */
    296 static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
    297                              int dna, int dnb, BN_ULONG *t) {
    298   int n = n2 / 2, c1, c2;
    299   int tna = n + dna, tnb = n + dnb;
    300   unsigned int neg, zero;
    301   BN_ULONG ln, lo, *p;
    302 
    303   /* Only call bn_mul_comba 8 if n2 == 8 and the
    304    * two arrays are complete [steve]
    305    */
    306   if (n2 == 8 && dna == 0 && dnb == 0) {
    307     bn_mul_comba8(r, a, b);
    308     return;
    309   }
    310 
    311   /* Else do normal multiply */
    312   if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
    313     bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
    314     if ((dna + dnb) < 0) {
    315       OPENSSL_memset(&r[2 * n2 + dna + dnb], 0,
    316                      sizeof(BN_ULONG) * -(dna + dnb));
    317     }
    318     return;
    319   }
    320 
    321   /* r=(a[0]-a[1])*(b[1]-b[0]) */
    322   c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
    323   c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
    324   zero = neg = 0;
    325   switch (c1 * 3 + c2) {
    326     case -4:
    327       bn_sub_part_words(t, &(a[n]), a, tna, tna - n);       /* - */
    328       bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
    329       break;
    330     case -3:
    331       zero = 1;
    332       break;
    333     case -2:
    334       bn_sub_part_words(t, &(a[n]), a, tna, tna - n);       /* - */
    335       bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
    336       neg = 1;
    337       break;
    338     case -1:
    339     case 0:
    340     case 1:
    341       zero = 1;
    342       break;
    343     case 2:
    344       bn_sub_part_words(t, a, &(a[n]), tna, n - tna);       /* + */
    345       bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
    346       neg = 1;
    347       break;
    348     case 3:
    349       zero = 1;
    350       break;
    351     case 4:
    352       bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
    353       bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
    354       break;
    355   }
    356 
    357   if (n == 4 && dna == 0 && dnb == 0) {
    358     /* XXX: bn_mul_comba4 could take extra args to do this well */
    359     if (!zero) {
    360       bn_mul_comba4(&(t[n2]), t, &(t[n]));
    361     } else {
    362       OPENSSL_memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG));
    363     }
    364 
    365     bn_mul_comba4(r, a, b);
    366     bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
    367   } else if (n == 8 && dna == 0 && dnb == 0) {
    368     /* XXX: bn_mul_comba8 could take extra args to do this well */
    369     if (!zero) {
    370       bn_mul_comba8(&(t[n2]), t, &(t[n]));
    371     } else {
    372       OPENSSL_memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG));
    373     }
    374 
    375     bn_mul_comba8(r, a, b);
    376     bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
    377   } else {
    378     p = &(t[n2 * 2]);
    379     if (!zero) {
    380       bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
    381     } else {
    382       OPENSSL_memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
    383     }
    384     bn_mul_recursive(r, a, b, n, 0, 0, p);
    385     bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
    386   }
    387 
    388   /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
    389    * r[10] holds (a[0]*b[0])
    390    * r[32] holds (b[1]*b[1]) */
    391 
    392   c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
    393 
    394   if (neg) {
    395     /* if t[32] is negative */
    396     c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
    397   } else {
    398     /* Might have a carry */
    399     c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
    400   }
    401 
    402   /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
    403    * r[10] holds (a[0]*b[0])
    404    * r[32] holds (b[1]*b[1])
    405    * c1 holds the carry bits */
    406   c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
    407   if (c1) {
    408     p = &(r[n + n2]);
    409     lo = *p;
    410     ln = (lo + c1) & BN_MASK2;
    411     *p = ln;
    412 
    413     /* The overflow will stop before we over write
    414      * words we should not overwrite */
    415     if (ln < (BN_ULONG)c1) {
    416       do {
    417         p++;
    418         lo = *p;
    419         ln = (lo + 1) & BN_MASK2;
    420         *p = ln;
    421       } while (ln == 0);
    422     }
    423   }
    424 }
    425 
    426 /* n+tn is the word length
    427  * t needs to be n*4 is size, as does r */
    428 /* tnX may not be negative but less than n */
    429 static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
    430                                   int tna, int tnb, BN_ULONG *t) {
    431   int i, j, n2 = n * 2;
    432   int c1, c2, neg;
    433   BN_ULONG ln, lo, *p;
    434 
    435   if (n < 8) {
    436     bn_mul_normal(r, a, n + tna, b, n + tnb);
    437     return;
    438   }
    439 
    440   /* r=(a[0]-a[1])*(b[1]-b[0]) */
    441   c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
    442   c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
    443   neg = 0;
    444   switch (c1 * 3 + c2) {
    445     case -4:
    446       bn_sub_part_words(t, &(a[n]), a, tna, tna - n);       /* - */
    447       bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
    448       break;
    449     case -3:
    450     /* break; */
    451     case -2:
    452       bn_sub_part_words(t, &(a[n]), a, tna, tna - n);       /* - */
    453       bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
    454       neg = 1;
    455       break;
    456     case -1:
    457     case 0:
    458     case 1:
    459     /* break; */
    460     case 2:
    461       bn_sub_part_words(t, a, &(a[n]), tna, n - tna);       /* + */
    462       bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
    463       neg = 1;
    464       break;
    465     case 3:
    466     /* break; */
    467     case 4:
    468       bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
    469       bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
    470       break;
    471   }
    472 
    473   if (n == 8) {
    474     bn_mul_comba8(&(t[n2]), t, &(t[n]));
    475     bn_mul_comba8(r, a, b);
    476     bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
    477     OPENSSL_memset(&(r[n2 + tna + tnb]), 0, sizeof(BN_ULONG) * (n2 - tna - tnb));
    478   } else {
    479     p = &(t[n2 * 2]);
    480     bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
    481     bn_mul_recursive(r, a, b, n, 0, 0, p);
    482     i = n / 2;
    483     /* If there is only a bottom half to the number,
    484      * just do it */
    485     if (tna > tnb) {
    486       j = tna - i;
    487     } else {
    488       j = tnb - i;
    489     }
    490 
    491     if (j == 0) {
    492       bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p);
    493       OPENSSL_memset(&(r[n2 + i * 2]), 0, sizeof(BN_ULONG) * (n2 - i * 2));
    494     } else if (j > 0) {
    495       /* eg, n == 16, i == 8 and tn == 11 */
    496       bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p);
    497       OPENSSL_memset(&(r[n2 + tna + tnb]), 0,
    498                      sizeof(BN_ULONG) * (n2 - tna - tnb));
    499     } else {
    500       /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
    501       OPENSSL_memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2);
    502       if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL &&
    503           tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
    504         bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
    505       } else {
    506         for (;;) {
    507           i /= 2;
    508           /* these simplified conditions work
    509            * exclusively because difference
    510            * between tna and tnb is 1 or 0 */
    511           if (i < tna || i < tnb) {
    512             bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i,
    513                                   tnb - i, p);
    514             break;
    515           } else if (i == tna || i == tnb) {
    516             bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i,
    517                              p);
    518             break;
    519           }
    520         }
    521       }
    522     }
    523   }
    524 
    525   /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
    526    * r[10] holds (a[0]*b[0])
    527    * r[32] holds (b[1]*b[1])
    528    */
    529 
    530   c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
    531 
    532   if (neg) {
    533     /* if t[32] is negative */
    534     c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
    535   } else {
    536     /* Might have a carry */
    537     c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
    538   }
    539 
    540   /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
    541    * r[10] holds (a[0]*b[0])
    542    * r[32] holds (b[1]*b[1])
    543    * c1 holds the carry bits */
    544   c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
    545   if (c1) {
    546     p = &(r[n + n2]);
    547     lo = *p;
    548     ln = (lo + c1) & BN_MASK2;
    549     *p = ln;
    550 
    551     /* The overflow will stop before we over write
    552      * words we should not overwrite */
    553     if (ln < (BN_ULONG)c1) {
    554       do {
    555         p++;
    556         lo = *p;
    557         ln = (lo + 1) & BN_MASK2;
    558         *p = ln;
    559       } while (ln == 0);
    560     }
    561   }
    562 }
    563 
    564 int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
    565   int ret = 0;
    566   int top, al, bl;
    567   BIGNUM *rr;
    568   int i;
    569   BIGNUM *t = NULL;
    570   int j = 0, k;
    571 
    572   al = a->top;
    573   bl = b->top;
    574 
    575   if ((al == 0) || (bl == 0)) {
    576     BN_zero(r);
    577     return 1;
    578   }
    579   top = al + bl;
    580 
    581   BN_CTX_start(ctx);
    582   if ((r == a) || (r == b)) {
    583     if ((rr = BN_CTX_get(ctx)) == NULL) {
    584       goto err;
    585     }
    586   } else {
    587     rr = r;
    588   }
    589   rr->neg = a->neg ^ b->neg;
    590 
    591   i = al - bl;
    592   if (i == 0) {
    593     if (al == 8) {
    594       if (bn_wexpand(rr, 16) == NULL) {
    595         goto err;
    596       }
    597       rr->top = 16;
    598       bn_mul_comba8(rr->d, a->d, b->d);
    599       goto end;
    600     }
    601   }
    602 
    603   static const int kMulNormalSize = 16;
    604   if (al >= kMulNormalSize && bl >= kMulNormalSize) {
    605     if (i >= -1 && i <= 1) {
    606       /* Find out the power of two lower or equal
    607          to the longest of the two numbers */
    608       if (i >= 0) {
    609         j = BN_num_bits_word((BN_ULONG)al);
    610       }
    611       if (i == -1) {
    612         j = BN_num_bits_word((BN_ULONG)bl);
    613       }
    614       j = 1 << (j - 1);
    615       assert(j <= al || j <= bl);
    616       k = j + j;
    617       t = BN_CTX_get(ctx);
    618       if (t == NULL) {
    619         goto err;
    620       }
    621       if (al > j || bl > j) {
    622         if (bn_wexpand(t, k * 4) == NULL) {
    623           goto err;
    624         }
    625         if (bn_wexpand(rr, k * 4) == NULL) {
    626           goto err;
    627         }
    628         bn_mul_part_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
    629       } else {
    630         /* al <= j || bl <= j */
    631         if (bn_wexpand(t, k * 2) == NULL) {
    632           goto err;
    633         }
    634         if (bn_wexpand(rr, k * 2) == NULL) {
    635           goto err;
    636         }
    637         bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
    638       }
    639       rr->top = top;
    640       goto end;
    641     }
    642   }
    643 
    644   if (bn_wexpand(rr, top) == NULL) {
    645     goto err;
    646   }
    647   rr->top = top;
    648   bn_mul_normal(rr->d, a->d, al, b->d, bl);
    649 
    650 end:
    651   bn_correct_top(rr);
    652   if (r != rr && !BN_copy(r, rr)) {
    653     goto err;
    654   }
    655   ret = 1;
    656 
    657 err:
    658   BN_CTX_end(ctx);
    659   return ret;
    660 }
    661 
    662 /* tmp must have 2*n words */
    663 static void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) {
    664   int i, j, max;
    665   const BN_ULONG *ap;
    666   BN_ULONG *rp;
    667 
    668   max = n * 2;
    669   ap = a;
    670   rp = r;
    671   rp[0] = rp[max - 1] = 0;
    672   rp++;
    673   j = n;
    674 
    675   if (--j > 0) {
    676     ap++;
    677     rp[j] = bn_mul_words(rp, ap, j, ap[-1]);
    678     rp += 2;
    679   }
    680 
    681   for (i = n - 2; i > 0; i--) {
    682     j--;
    683     ap++;
    684     rp[j] = bn_mul_add_words(rp, ap, j, ap[-1]);
    685     rp += 2;
    686   }
    687 
    688   bn_add_words(r, r, r, max);
    689 
    690   /* There will not be a carry */
    691 
    692   bn_sqr_words(tmp, a, n);
    693 
    694   bn_add_words(r, r, tmp, max);
    695 }
    696 
    697 /* r is 2*n words in size,
    698  * a and b are both n words in size.    (There's not actually a 'b' here ...)
    699  * n must be a power of 2.
    700  * We multiply and return the result.
    701  * t must be 2*n words in size
    702  * We calculate
    703  * a[0]*b[0]
    704  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
    705  * a[1]*b[1]
    706  */
    707 static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t) {
    708   int n = n2 / 2;
    709   int zero, c1;
    710   BN_ULONG ln, lo, *p;
    711 
    712   if (n2 == 4) {
    713     bn_sqr_comba4(r, a);
    714     return;
    715   } else if (n2 == 8) {
    716     bn_sqr_comba8(r, a);
    717     return;
    718   }
    719   if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) {
    720     bn_sqr_normal(r, a, n2, t);
    721     return;
    722   }
    723   /* r=(a[0]-a[1])*(a[1]-a[0]) */
    724   c1 = bn_cmp_words(a, &(a[n]), n);
    725   zero = 0;
    726   if (c1 > 0) {
    727     bn_sub_words(t, a, &(a[n]), n);
    728   } else if (c1 < 0) {
    729     bn_sub_words(t, &(a[n]), a, n);
    730   } else {
    731     zero = 1;
    732   }
    733 
    734   /* The result will always be negative unless it is zero */
    735   p = &(t[n2 * 2]);
    736 
    737   if (!zero) {
    738     bn_sqr_recursive(&(t[n2]), t, n, p);
    739   } else {
    740     OPENSSL_memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
    741   }
    742   bn_sqr_recursive(r, a, n, p);
    743   bn_sqr_recursive(&(r[n2]), &(a[n]), n, p);
    744 
    745   /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
    746    * r[10] holds (a[0]*b[0])
    747    * r[32] holds (b[1]*b[1]) */
    748 
    749   c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
    750 
    751   /* t[32] is negative */
    752   c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
    753 
    754   /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
    755    * r[10] holds (a[0]*a[0])
    756    * r[32] holds (a[1]*a[1])
    757    * c1 holds the carry bits */
    758   c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
    759   if (c1) {
    760     p = &(r[n + n2]);
    761     lo = *p;
    762     ln = (lo + c1) & BN_MASK2;
    763     *p = ln;
    764 
    765     /* The overflow will stop before we over write
    766      * words we should not overwrite */
    767     if (ln < (BN_ULONG)c1) {
    768       do {
    769         p++;
    770         lo = *p;
    771         ln = (lo + 1) & BN_MASK2;
    772         *p = ln;
    773       } while (ln == 0);
    774     }
    775   }
    776 }
    777 
    778 int BN_mul_word(BIGNUM *bn, BN_ULONG w) {
    779   BN_ULONG ll;
    780 
    781   w &= BN_MASK2;
    782   if (!bn->top) {
    783     return 1;
    784   }
    785 
    786   if (w == 0) {
    787     BN_zero(bn);
    788     return 1;
    789   }
    790 
    791   ll = bn_mul_words(bn->d, bn->d, bn->top, w);
    792   if (ll) {
    793     if (bn_wexpand(bn, bn->top + 1) == NULL) {
    794       return 0;
    795     }
    796     bn->d[bn->top++] = ll;
    797   }
    798 
    799   return 1;
    800 }
    801 
    802 int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) {
    803   int max, al;
    804   int ret = 0;
    805   BIGNUM *tmp, *rr;
    806 
    807   al = a->top;
    808   if (al <= 0) {
    809     r->top = 0;
    810     r->neg = 0;
    811     return 1;
    812   }
    813 
    814   BN_CTX_start(ctx);
    815   rr = (a != r) ? r : BN_CTX_get(ctx);
    816   tmp = BN_CTX_get(ctx);
    817   if (!rr || !tmp) {
    818     goto err;
    819   }
    820 
    821   max = 2 * al; /* Non-zero (from above) */
    822   if (bn_wexpand(rr, max) == NULL) {
    823     goto err;
    824   }
    825 
    826   if (al == 4) {
    827     bn_sqr_comba4(rr->d, a->d);
    828   } else if (al == 8) {
    829     bn_sqr_comba8(rr->d, a->d);
    830   } else {
    831     if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) {
    832       BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL * 2];
    833       bn_sqr_normal(rr->d, a->d, al, t);
    834     } else {
    835       int j, k;
    836 
    837       j = BN_num_bits_word((BN_ULONG)al);
    838       j = 1 << (j - 1);
    839       k = j + j;
    840       if (al == j) {
    841         if (bn_wexpand(tmp, k * 2) == NULL) {
    842           goto err;
    843         }
    844         bn_sqr_recursive(rr->d, a->d, al, tmp->d);
    845       } else {
    846         if (bn_wexpand(tmp, max) == NULL) {
    847           goto err;
    848         }
    849         bn_sqr_normal(rr->d, a->d, al, tmp->d);
    850       }
    851     }
    852   }
    853 
    854   rr->neg = 0;
    855   /* If the most-significant half of the top word of 'a' is zero, then
    856    * the square of 'a' will max-1 words. */
    857   if (a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) {
    858     rr->top = max - 1;
    859   } else {
    860     rr->top = max;
    861   }
    862 
    863   if (rr != r && !BN_copy(r, rr)) {
    864     goto err;
    865   }
    866   ret = 1;
    867 
    868 err:
    869   BN_CTX_end(ctx);
    870   return ret;
    871 }
    872