1*c9675a23Stb /* $OpenBSD: bn_mul.c,v 1.23 2022/11/26 16:08:51 tb Exp $ */ 25b37fcf3Sryker /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 35b37fcf3Sryker * All rights reserved. 45b37fcf3Sryker * 55b37fcf3Sryker * This package is an SSL implementation written 65b37fcf3Sryker * by Eric Young (eay@cryptsoft.com). 75b37fcf3Sryker * The implementation was written so as to conform with Netscapes SSL. 85b37fcf3Sryker * 95b37fcf3Sryker * This library is free for commercial and non-commercial use as long as 105b37fcf3Sryker * the following conditions are aheared to. The following conditions 115b37fcf3Sryker * apply to all code found in this distribution, be it the RC4, RSA, 125b37fcf3Sryker * lhash, DES, etc., code; not just the SSL code. The SSL documentation 135b37fcf3Sryker * included with this distribution is covered by the same copyright terms 145b37fcf3Sryker * except that the holder is Tim Hudson (tjh@cryptsoft.com). 155b37fcf3Sryker * 165b37fcf3Sryker * Copyright remains Eric Young's, and as such any Copyright notices in 175b37fcf3Sryker * the code are not to be removed. 185b37fcf3Sryker * If this package is used in a product, Eric Young should be given attribution 195b37fcf3Sryker * as the author of the parts of the library used. 205b37fcf3Sryker * This can be in the form of a textual message at program startup or 215b37fcf3Sryker * in documentation (online or textual) provided with the package. 225b37fcf3Sryker * 235b37fcf3Sryker * Redistribution and use in source and binary forms, with or without 245b37fcf3Sryker * modification, are permitted provided that the following conditions 255b37fcf3Sryker * are met: 265b37fcf3Sryker * 1. Redistributions of source code must retain the copyright 275b37fcf3Sryker * notice, this list of conditions and the following disclaimer. 285b37fcf3Sryker * 2. Redistributions in binary form must reproduce the above copyright 295b37fcf3Sryker * notice, this list of conditions and the following disclaimer in the 305b37fcf3Sryker * documentation and/or other materials provided with the distribution. 315b37fcf3Sryker * 3. All advertising materials mentioning features or use of this software 325b37fcf3Sryker * must display the following acknowledgement: 335b37fcf3Sryker * "This product includes cryptographic software written by 345b37fcf3Sryker * Eric Young (eay@cryptsoft.com)" 355b37fcf3Sryker * The word 'cryptographic' can be left out if the rouines from the library 365b37fcf3Sryker * being used are not cryptographic related :-). 375b37fcf3Sryker * 4. If you include any Windows specific code (or a derivative thereof) from 385b37fcf3Sryker * the apps directory (application code) you must include an acknowledgement: 395b37fcf3Sryker * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 405b37fcf3Sryker * 415b37fcf3Sryker * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 425b37fcf3Sryker * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 435b37fcf3Sryker * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 445b37fcf3Sryker * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 455b37fcf3Sryker * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 465b37fcf3Sryker * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 475b37fcf3Sryker * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 485b37fcf3Sryker * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 495b37fcf3Sryker * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 505b37fcf3Sryker * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 515b37fcf3Sryker * SUCH DAMAGE. 525b37fcf3Sryker * 535b37fcf3Sryker * The licence and distribution terms for any publically available version or 545b37fcf3Sryker * derivative of this code cannot be changed. i.e. this code cannot simply be 555b37fcf3Sryker * copied and put under another distribution licence 565b37fcf3Sryker * [including the GNU Public Licence.] 575b37fcf3Sryker */ 585b37fcf3Sryker 594fcf65c5Sdjm #ifndef BN_DEBUG 604fcf65c5Sdjm # undef NDEBUG /* avoid conflicting definitions */ 614fcf65c5Sdjm # define NDEBUG 624fcf65c5Sdjm #endif 634fcf65c5Sdjm 644fcf65c5Sdjm #include <assert.h> 65a8913c44Sjsing #include <stdio.h> 66a8913c44Sjsing #include <string.h> 67a8913c44Sjsing 688cf4d6a6Sjsing #include <openssl/opensslconf.h> 698cf4d6a6Sjsing 70*c9675a23Stb #include "bn_local.h" 715b37fcf3Sryker 724fcf65c5Sdjm #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) 734fcf65c5Sdjm /* Here follows specialised variants of bn_add_words() and 744fcf65c5Sdjm bn_sub_words(). They have the property performing operations on 754fcf65c5Sdjm arrays of different sizes. The sizes of those arrays is expressed through 764fcf65c5Sdjm cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl, 774fcf65c5Sdjm which is the delta between the two lengths, calculated as len(a)-len(b). 784fcf65c5Sdjm All lengths are the number of BN_ULONGs... For the operations that require 794fcf65c5Sdjm a result array as parameter, it must have the length cl+abs(dl). 804fcf65c5Sdjm These functions should probably end up in bn_asm.c as soon as there are 814fcf65c5Sdjm assembler counterparts for the systems that use assembler files. */ 824fcf65c5Sdjm 832bd9bb84Sjsing BN_ULONG 842bd9bb84Sjsing bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, 852bd9bb84Sjsing int dl) 864fcf65c5Sdjm { 874fcf65c5Sdjm BN_ULONG c, t; 884fcf65c5Sdjm 894fcf65c5Sdjm assert(cl >= 0); 904fcf65c5Sdjm c = bn_sub_words(r, a, b, cl); 914fcf65c5Sdjm 924fcf65c5Sdjm if (dl == 0) 934fcf65c5Sdjm return c; 944fcf65c5Sdjm 954fcf65c5Sdjm r += cl; 964fcf65c5Sdjm a += cl; 974fcf65c5Sdjm b += cl; 984fcf65c5Sdjm 992bd9bb84Sjsing if (dl < 0) { 1004fcf65c5Sdjm #ifdef BN_COUNT 1012bd9bb84Sjsing fprintf(stderr, 1022bd9bb84Sjsing " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", 1032bd9bb84Sjsing cl, dl, c); 1044fcf65c5Sdjm #endif 1052bd9bb84Sjsing for (;;) { 1064fcf65c5Sdjm t = b[0]; 1074fcf65c5Sdjm r[0] = (0 - t - c) & BN_MASK2; 1082bd9bb84Sjsing if (t != 0) 1092bd9bb84Sjsing c = 1; 1102bd9bb84Sjsing if (++dl >= 0) 1112bd9bb84Sjsing break; 1124fcf65c5Sdjm 1134fcf65c5Sdjm t = b[1]; 1144fcf65c5Sdjm r[1] = (0 - t - c) & BN_MASK2; 1152bd9bb84Sjsing if (t != 0) 1162bd9bb84Sjsing c = 1; 1172bd9bb84Sjsing if (++dl >= 0) 1182bd9bb84Sjsing break; 1194fcf65c5Sdjm 1204fcf65c5Sdjm t = b[2]; 1214fcf65c5Sdjm r[2] = (0 - t - c) & BN_MASK2; 1222bd9bb84Sjsing if (t != 0) 1232bd9bb84Sjsing c = 1; 1242bd9bb84Sjsing if (++dl >= 0) 1252bd9bb84Sjsing break; 1264fcf65c5Sdjm 1274fcf65c5Sdjm t = b[3]; 1284fcf65c5Sdjm r[3] = (0 - t - c) & BN_MASK2; 1292bd9bb84Sjsing if (t != 0) 1302bd9bb84Sjsing c = 1; 1312bd9bb84Sjsing if (++dl >= 0) 1322bd9bb84Sjsing break; 1334fcf65c5Sdjm 1344fcf65c5Sdjm b += 4; 1354fcf65c5Sdjm r += 4; 1364fcf65c5Sdjm } 1372bd9bb84Sjsing } else { 1384fcf65c5Sdjm int save_dl = dl; 1394fcf65c5Sdjm #ifdef BN_COUNT 1402bd9bb84Sjsing fprintf(stderr, 1412bd9bb84Sjsing " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", 1422bd9bb84Sjsing cl, dl, c); 1434fcf65c5Sdjm #endif 1442bd9bb84Sjsing while (c) { 1454fcf65c5Sdjm t = a[0]; 1464fcf65c5Sdjm r[0] = (t - c) & BN_MASK2; 1472bd9bb84Sjsing if (t != 0) 1482bd9bb84Sjsing c = 0; 1492bd9bb84Sjsing if (--dl <= 0) 1502bd9bb84Sjsing break; 1514fcf65c5Sdjm 1524fcf65c5Sdjm t = a[1]; 1534fcf65c5Sdjm r[1] = (t - c) & BN_MASK2; 1542bd9bb84Sjsing if (t != 0) 1552bd9bb84Sjsing c = 0; 1562bd9bb84Sjsing if (--dl <= 0) 1572bd9bb84Sjsing break; 1584fcf65c5Sdjm 1594fcf65c5Sdjm t = a[2]; 1604fcf65c5Sdjm r[2] = (t - c) & BN_MASK2; 1612bd9bb84Sjsing if (t != 0) 1622bd9bb84Sjsing c = 0; 1632bd9bb84Sjsing if (--dl <= 0) 1642bd9bb84Sjsing break; 1654fcf65c5Sdjm 1664fcf65c5Sdjm t = a[3]; 1674fcf65c5Sdjm r[3] = (t - c) & BN_MASK2; 1682bd9bb84Sjsing if (t != 0) 1692bd9bb84Sjsing c = 0; 1702bd9bb84Sjsing if (--dl <= 0) 1712bd9bb84Sjsing break; 1724fcf65c5Sdjm 1734fcf65c5Sdjm save_dl = dl; 1744fcf65c5Sdjm a += 4; 1754fcf65c5Sdjm r += 4; 1764fcf65c5Sdjm } 1772bd9bb84Sjsing if (dl > 0) { 1784fcf65c5Sdjm #ifdef BN_COUNT 1792bd9bb84Sjsing fprintf(stderr, 1802bd9bb84Sjsing " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", 1812bd9bb84Sjsing cl, dl); 1824fcf65c5Sdjm #endif 1832bd9bb84Sjsing if (save_dl > dl) { 1842bd9bb84Sjsing switch (save_dl - dl) { 1854fcf65c5Sdjm case 1: 1864fcf65c5Sdjm r[1] = a[1]; 1872bd9bb84Sjsing if (--dl <= 0) 1882bd9bb84Sjsing break; 1894fcf65c5Sdjm case 2: 1904fcf65c5Sdjm r[2] = a[2]; 1912bd9bb84Sjsing if (--dl <= 0) 1922bd9bb84Sjsing break; 1934fcf65c5Sdjm case 3: 1944fcf65c5Sdjm r[3] = a[3]; 1952bd9bb84Sjsing if (--dl <= 0) 1962bd9bb84Sjsing break; 1974fcf65c5Sdjm } 1984fcf65c5Sdjm a += 4; 1994fcf65c5Sdjm r += 4; 2004fcf65c5Sdjm } 2014fcf65c5Sdjm } 2022bd9bb84Sjsing if (dl > 0) { 2034fcf65c5Sdjm #ifdef BN_COUNT 2042bd9bb84Sjsing fprintf(stderr, 2052bd9bb84Sjsing " bn_sub_part_words %d + %d (dl > 0, copy)\n", 2062bd9bb84Sjsing cl, dl); 2074fcf65c5Sdjm #endif 2082bd9bb84Sjsing for (;;) { 2094fcf65c5Sdjm r[0] = a[0]; 2102bd9bb84Sjsing if (--dl <= 0) 2112bd9bb84Sjsing break; 2124fcf65c5Sdjm r[1] = a[1]; 2132bd9bb84Sjsing if (--dl <= 0) 2142bd9bb84Sjsing break; 2154fcf65c5Sdjm r[2] = a[2]; 2162bd9bb84Sjsing if (--dl <= 0) 2172bd9bb84Sjsing break; 2184fcf65c5Sdjm r[3] = a[3]; 2192bd9bb84Sjsing if (--dl <= 0) 2202bd9bb84Sjsing break; 2214fcf65c5Sdjm 2224fcf65c5Sdjm a += 4; 2234fcf65c5Sdjm r += 4; 2244fcf65c5Sdjm } 2254fcf65c5Sdjm } 2264fcf65c5Sdjm } 2274fcf65c5Sdjm return c; 2284fcf65c5Sdjm } 2294fcf65c5Sdjm #endif 2304fcf65c5Sdjm 2312bd9bb84Sjsing BN_ULONG 2322bd9bb84Sjsing bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, 2332bd9bb84Sjsing int dl) 2344fcf65c5Sdjm { 2354fcf65c5Sdjm BN_ULONG c, l, t; 2364fcf65c5Sdjm 2374fcf65c5Sdjm assert(cl >= 0); 2384fcf65c5Sdjm c = bn_add_words(r, a, b, cl); 2394fcf65c5Sdjm 2404fcf65c5Sdjm if (dl == 0) 2414fcf65c5Sdjm return c; 2424fcf65c5Sdjm 2434fcf65c5Sdjm r += cl; 2444fcf65c5Sdjm a += cl; 2454fcf65c5Sdjm b += cl; 2464fcf65c5Sdjm 2472bd9bb84Sjsing if (dl < 0) { 2484fcf65c5Sdjm int save_dl = dl; 2494fcf65c5Sdjm #ifdef BN_COUNT 2502bd9bb84Sjsing fprintf(stderr, 2512bd9bb84Sjsing " bn_add_part_words %d + %d (dl < 0, c = %d)\n", 2522bd9bb84Sjsing cl, dl, c); 2534fcf65c5Sdjm #endif 2542bd9bb84Sjsing while (c) { 2554fcf65c5Sdjm l = (c + b[0]) & BN_MASK2; 2564fcf65c5Sdjm c = (l < c); 2574fcf65c5Sdjm r[0] = l; 2582bd9bb84Sjsing if (++dl >= 0) 2592bd9bb84Sjsing break; 2604fcf65c5Sdjm 2614fcf65c5Sdjm l = (c + b[1]) & BN_MASK2; 2624fcf65c5Sdjm c = (l < c); 2634fcf65c5Sdjm r[1] = l; 2642bd9bb84Sjsing if (++dl >= 0) 2652bd9bb84Sjsing break; 2664fcf65c5Sdjm 2674fcf65c5Sdjm l = (c + b[2]) & BN_MASK2; 2684fcf65c5Sdjm c = (l < c); 2694fcf65c5Sdjm r[2] = l; 2702bd9bb84Sjsing if (++dl >= 0) 2712bd9bb84Sjsing break; 2724fcf65c5Sdjm 2734fcf65c5Sdjm l = (c + b[3]) & BN_MASK2; 2744fcf65c5Sdjm c = (l < c); 2754fcf65c5Sdjm r[3] = l; 2762bd9bb84Sjsing if (++dl >= 0) 2772bd9bb84Sjsing break; 2784fcf65c5Sdjm 2794fcf65c5Sdjm save_dl = dl; 2804fcf65c5Sdjm b += 4; 2814fcf65c5Sdjm r += 4; 2824fcf65c5Sdjm } 2832bd9bb84Sjsing if (dl < 0) { 2844fcf65c5Sdjm #ifdef BN_COUNT 2852bd9bb84Sjsing fprintf(stderr, 2862bd9bb84Sjsing " bn_add_part_words %d + %d (dl < 0, c == 0)\n", 2872bd9bb84Sjsing cl, dl); 2884fcf65c5Sdjm #endif 2892bd9bb84Sjsing if (save_dl < dl) { 2902bd9bb84Sjsing switch (dl - save_dl) { 2914fcf65c5Sdjm case 1: 2924fcf65c5Sdjm r[1] = b[1]; 2932bd9bb84Sjsing if (++dl >= 0) 2942bd9bb84Sjsing break; 2954fcf65c5Sdjm case 2: 2964fcf65c5Sdjm r[2] = b[2]; 2972bd9bb84Sjsing if (++dl >= 0) 2982bd9bb84Sjsing break; 2994fcf65c5Sdjm case 3: 3004fcf65c5Sdjm r[3] = b[3]; 3012bd9bb84Sjsing if (++dl >= 0) 3022bd9bb84Sjsing break; 3034fcf65c5Sdjm } 3044fcf65c5Sdjm b += 4; 3054fcf65c5Sdjm r += 4; 3064fcf65c5Sdjm } 3074fcf65c5Sdjm } 3082bd9bb84Sjsing if (dl < 0) { 3094fcf65c5Sdjm #ifdef BN_COUNT 3102bd9bb84Sjsing fprintf(stderr, 3112bd9bb84Sjsing " bn_add_part_words %d + %d (dl < 0, copy)\n", 3122bd9bb84Sjsing cl, dl); 3134fcf65c5Sdjm #endif 3142bd9bb84Sjsing for (;;) { 3154fcf65c5Sdjm r[0] = b[0]; 3162bd9bb84Sjsing if (++dl >= 0) 3172bd9bb84Sjsing break; 3184fcf65c5Sdjm r[1] = b[1]; 3192bd9bb84Sjsing if (++dl >= 0) 3202bd9bb84Sjsing break; 3214fcf65c5Sdjm r[2] = b[2]; 3222bd9bb84Sjsing if (++dl >= 0) 3232bd9bb84Sjsing break; 3244fcf65c5Sdjm r[3] = b[3]; 3252bd9bb84Sjsing if (++dl >= 0) 3262bd9bb84Sjsing break; 3274fcf65c5Sdjm 3284fcf65c5Sdjm b += 4; 3294fcf65c5Sdjm r += 4; 3304fcf65c5Sdjm } 3314fcf65c5Sdjm } 3322bd9bb84Sjsing } else { 3334fcf65c5Sdjm int save_dl = dl; 3344fcf65c5Sdjm #ifdef BN_COUNT 3352bd9bb84Sjsing fprintf(stderr, 3362bd9bb84Sjsing " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); 3374fcf65c5Sdjm #endif 3382bd9bb84Sjsing while (c) { 3394fcf65c5Sdjm t = (a[0] + c) & BN_MASK2; 3404fcf65c5Sdjm c = (t < c); 3414fcf65c5Sdjm r[0] = t; 3422bd9bb84Sjsing if (--dl <= 0) 3432bd9bb84Sjsing break; 3444fcf65c5Sdjm 3454fcf65c5Sdjm t = (a[1] + c) & BN_MASK2; 3464fcf65c5Sdjm c = (t < c); 3474fcf65c5Sdjm r[1] = t; 3482bd9bb84Sjsing if (--dl <= 0) 3492bd9bb84Sjsing break; 3504fcf65c5Sdjm 3514fcf65c5Sdjm t = (a[2] + c) & BN_MASK2; 3524fcf65c5Sdjm c = (t < c); 3534fcf65c5Sdjm r[2] = t; 3542bd9bb84Sjsing if (--dl <= 0) 3552bd9bb84Sjsing break; 3564fcf65c5Sdjm 3574fcf65c5Sdjm t = (a[3] + c) & BN_MASK2; 3584fcf65c5Sdjm c = (t < c); 3594fcf65c5Sdjm r[3] = t; 3602bd9bb84Sjsing if (--dl <= 0) 3612bd9bb84Sjsing break; 3624fcf65c5Sdjm 3634fcf65c5Sdjm save_dl = dl; 3644fcf65c5Sdjm a += 4; 3654fcf65c5Sdjm r += 4; 3664fcf65c5Sdjm } 3674fcf65c5Sdjm #ifdef BN_COUNT 3682bd9bb84Sjsing fprintf(stderr, 3692bd9bb84Sjsing " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); 3704fcf65c5Sdjm #endif 3712bd9bb84Sjsing if (dl > 0) { 3722bd9bb84Sjsing if (save_dl > dl) { 3732bd9bb84Sjsing switch (save_dl - dl) { 3744fcf65c5Sdjm case 1: 3754fcf65c5Sdjm r[1] = a[1]; 3762bd9bb84Sjsing if (--dl <= 0) 3772bd9bb84Sjsing break; 3784fcf65c5Sdjm case 2: 3794fcf65c5Sdjm r[2] = a[2]; 3802bd9bb84Sjsing if (--dl <= 0) 3812bd9bb84Sjsing break; 3824fcf65c5Sdjm case 3: 3834fcf65c5Sdjm r[3] = a[3]; 3842bd9bb84Sjsing if (--dl <= 0) 3852bd9bb84Sjsing break; 3864fcf65c5Sdjm } 3874fcf65c5Sdjm a += 4; 3884fcf65c5Sdjm r += 4; 3894fcf65c5Sdjm } 3904fcf65c5Sdjm } 3912bd9bb84Sjsing if (dl > 0) { 3924fcf65c5Sdjm #ifdef BN_COUNT 3932bd9bb84Sjsing fprintf(stderr, 3942bd9bb84Sjsing " bn_add_part_words %d + %d (dl > 0, copy)\n", 3952bd9bb84Sjsing cl, dl); 3964fcf65c5Sdjm #endif 3972bd9bb84Sjsing for (;;) { 3984fcf65c5Sdjm r[0] = a[0]; 3992bd9bb84Sjsing if (--dl <= 0) 4002bd9bb84Sjsing break; 4014fcf65c5Sdjm r[1] = a[1]; 4022bd9bb84Sjsing if (--dl <= 0) 4032bd9bb84Sjsing break; 4044fcf65c5Sdjm r[2] = a[2]; 4052bd9bb84Sjsing if (--dl <= 0) 4062bd9bb84Sjsing break; 4074fcf65c5Sdjm r[3] = a[3]; 4082bd9bb84Sjsing if (--dl <= 0) 4092bd9bb84Sjsing break; 4104fcf65c5Sdjm 4114fcf65c5Sdjm a += 4; 4124fcf65c5Sdjm r += 4; 4134fcf65c5Sdjm } 4144fcf65c5Sdjm } 4154fcf65c5Sdjm } 4164fcf65c5Sdjm return c; 4174fcf65c5Sdjm } 4184fcf65c5Sdjm 419913ec974Sbeck #ifdef BN_RECURSION 420f6e3f262Sbeck /* Karatsuba recursive multiplication algorithm 421f6e3f262Sbeck * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 422f6e3f262Sbeck 423913ec974Sbeck /* r is 2*n2 words in size, 424913ec974Sbeck * a and b are both n2 words in size. 425913ec974Sbeck * n2 must be a power of 2. 426913ec974Sbeck * We multiply and return the result. 427913ec974Sbeck * t must be 2*n2 words in size 428ba5406e9Sbeck * We calculate 429913ec974Sbeck * a[0]*b[0] 430913ec974Sbeck * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 431913ec974Sbeck * a[1]*b[1] 432913ec974Sbeck */ 4334fcf65c5Sdjm /* dnX may not be positive, but n2/2+dnX has to be */ 4342bd9bb84Sjsing void 4352bd9bb84Sjsing bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna, 4362bd9bb84Sjsing int dnb, BN_ULONG *t) 4375b37fcf3Sryker { 438913ec974Sbeck int n = n2 / 2, c1, c2; 4394fcf65c5Sdjm int tna = n + dna, tnb = n + dnb; 440913ec974Sbeck unsigned int neg, zero; 441913ec974Sbeck BN_ULONG ln, lo, *p; 4425b37fcf3Sryker 443913ec974Sbeck # ifdef BN_COUNT 4444fcf65c5Sdjm fprintf(stderr, " bn_mul_recursive %d%+d * %d%+d\n",n2,dna,n2,dnb); 445913ec974Sbeck # endif 446913ec974Sbeck # ifdef BN_MUL_COMBA 447ba5406e9Sbeck # if 0 4482bd9bb84Sjsing if (n2 == 4) { 449913ec974Sbeck bn_mul_comba4(r, a, b); 450913ec974Sbeck return; 451913ec974Sbeck } 452ba5406e9Sbeck # endif 4534fcf65c5Sdjm /* Only call bn_mul_comba 8 if n2 == 8 and the 4544fcf65c5Sdjm * two arrays are complete [steve] 4554fcf65c5Sdjm */ 4562bd9bb84Sjsing if (n2 == 8 && dna == 0 && dnb == 0) { 457913ec974Sbeck bn_mul_comba8(r, a, b); 458913ec974Sbeck return; 459913ec974Sbeck } 460ba5406e9Sbeck # endif /* BN_MUL_COMBA */ 4614fcf65c5Sdjm /* Else do normal multiply */ 4622bd9bb84Sjsing if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { 4634fcf65c5Sdjm bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); 4644fcf65c5Sdjm if ((dna + dnb) < 0) 4654fcf65c5Sdjm memset(&r[2*n2 + dna + dnb], 0, 4664fcf65c5Sdjm sizeof(BN_ULONG) * -(dna + dnb)); 467913ec974Sbeck return; 468913ec974Sbeck } 469913ec974Sbeck /* r=(a[0]-a[1])*(b[1]-b[0]) */ 4704fcf65c5Sdjm c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 4714fcf65c5Sdjm c2 = bn_cmp_part_words(&(b[n]), b,tnb, tnb - n); 472913ec974Sbeck zero = neg = 0; 4732bd9bb84Sjsing switch (c1 * 3 + c2) { 474913ec974Sbeck case -4: 4754fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 4764fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 477913ec974Sbeck break; 478913ec974Sbeck case -3: 479913ec974Sbeck zero = 1; 480913ec974Sbeck break; 481913ec974Sbeck case -2: 4824fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 4834fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 484913ec974Sbeck neg = 1; 485913ec974Sbeck break; 486913ec974Sbeck case -1: 487913ec974Sbeck case 0: 488913ec974Sbeck case 1: 489913ec974Sbeck zero = 1; 490913ec974Sbeck break; 491913ec974Sbeck case 2: 4924fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 4934fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 494913ec974Sbeck neg = 1; 495913ec974Sbeck break; 496913ec974Sbeck case 3: 497913ec974Sbeck zero = 1; 498913ec974Sbeck break; 499913ec974Sbeck case 4: 5004fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 5014fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 502913ec974Sbeck break; 5035b37fcf3Sryker } 5045b37fcf3Sryker 505913ec974Sbeck # ifdef BN_MUL_COMBA 5064fcf65c5Sdjm if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take 5074fcf65c5Sdjm extra args to do this well */ 5085b37fcf3Sryker { 509913ec974Sbeck if (!zero) 510913ec974Sbeck bn_mul_comba4(&(t[n2]), t, &(t[n])); 511913ec974Sbeck else 512913ec974Sbeck memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG)); 513913ec974Sbeck 514913ec974Sbeck bn_mul_comba4(r, a, b); 515913ec974Sbeck bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); 5162bd9bb84Sjsing } else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could 5174fcf65c5Sdjm take extra args to do this 5184fcf65c5Sdjm well */ 519913ec974Sbeck { 520913ec974Sbeck if (!zero) 521913ec974Sbeck bn_mul_comba8(&(t[n2]), t, &(t[n])); 522913ec974Sbeck else 523913ec974Sbeck memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG)); 524913ec974Sbeck 525913ec974Sbeck bn_mul_comba8(r, a, b); 526913ec974Sbeck bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n])); 5272bd9bb84Sjsing } else 528ba5406e9Sbeck # endif /* BN_MUL_COMBA */ 529913ec974Sbeck { 530913ec974Sbeck p = &(t[n2 * 2]); 531913ec974Sbeck if (!zero) 5324fcf65c5Sdjm bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 533913ec974Sbeck else 534913ec974Sbeck memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); 5354fcf65c5Sdjm bn_mul_recursive(r, a, b, n, 0, 0, p); 5364fcf65c5Sdjm bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); 5375b37fcf3Sryker } 5385b37fcf3Sryker 539913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 540913ec974Sbeck * r[10] holds (a[0]*b[0]) 541913ec974Sbeck * r[32] holds (b[1]*b[1]) 542913ec974Sbeck */ 5435b37fcf3Sryker 544913ec974Sbeck c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 5455b37fcf3Sryker 546913ec974Sbeck if (neg) /* if t[32] is negative */ 5475b37fcf3Sryker { 548913ec974Sbeck c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 5492bd9bb84Sjsing } else { 550913ec974Sbeck /* Might have a carry */ 551913ec974Sbeck c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 5525b37fcf3Sryker } 5535b37fcf3Sryker 554913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 555913ec974Sbeck * r[10] holds (a[0]*b[0]) 556913ec974Sbeck * r[32] holds (b[1]*b[1]) 557913ec974Sbeck * c1 holds the carry bits 558913ec974Sbeck */ 559913ec974Sbeck c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 5602bd9bb84Sjsing if (c1) { 561913ec974Sbeck p = &(r[n + n2]); 562913ec974Sbeck lo= *p; 563913ec974Sbeck ln = (lo + c1) & BN_MASK2; 564913ec974Sbeck *p = ln; 565913ec974Sbeck 566913ec974Sbeck /* The overflow will stop before we over write 567913ec974Sbeck * words we should not overwrite */ 5682bd9bb84Sjsing if (ln < (BN_ULONG)c1) { 569913ec974Sbeck do { 570913ec974Sbeck p++; 571913ec974Sbeck lo= *p; 572913ec974Sbeck ln = (lo + 1) & BN_MASK2; 573913ec974Sbeck *p = ln; 574913ec974Sbeck } while (ln == 0); 575913ec974Sbeck } 576913ec974Sbeck } 5775b37fcf3Sryker } 5785b37fcf3Sryker 579913ec974Sbeck /* n+tn is the word length 580913ec974Sbeck * t needs to be n*4 is size, as does r */ 5814fcf65c5Sdjm /* tnX may not be negative but less than n */ 5822bd9bb84Sjsing void 5832bd9bb84Sjsing bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna, 5842bd9bb84Sjsing int tnb, BN_ULONG *t) 5855b37fcf3Sryker { 586913ec974Sbeck int i, j, n2 = n * 2; 587c32db552Sdjm int c1, c2, neg; 588913ec974Sbeck BN_ULONG ln, lo, *p; 5895b37fcf3Sryker 590913ec974Sbeck # ifdef BN_COUNT 5914fcf65c5Sdjm fprintf(stderr, " bn_mul_part_recursive (%d%+d) * (%d%+d)\n", 5924fcf65c5Sdjm n, tna, n, tnb); 593913ec974Sbeck # endif 5942bd9bb84Sjsing if (n < 8) { 5954fcf65c5Sdjm bn_mul_normal(r, a, n + tna, b, n + tnb); 596913ec974Sbeck return; 5975b37fcf3Sryker } 5985b37fcf3Sryker 599913ec974Sbeck /* r=(a[0]-a[1])*(b[1]-b[0]) */ 6004fcf65c5Sdjm c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 6014fcf65c5Sdjm c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 602c32db552Sdjm neg = 0; 6032bd9bb84Sjsing switch (c1 * 3 + c2) { 604ba5406e9Sbeck case -4: 6054fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 6064fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 607ba5406e9Sbeck break; 608ba5406e9Sbeck case -3: 609ba5406e9Sbeck /* break; */ 610ba5406e9Sbeck case -2: 6114fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 6124fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 613ba5406e9Sbeck neg = 1; 614ba5406e9Sbeck break; 615ba5406e9Sbeck case -1: 616ba5406e9Sbeck case 0: 617ba5406e9Sbeck case 1: 618ba5406e9Sbeck /* break; */ 619ba5406e9Sbeck case 2: 6204fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 6214fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 622ba5406e9Sbeck neg = 1; 623ba5406e9Sbeck break; 624ba5406e9Sbeck case 3: 625ba5406e9Sbeck /* break; */ 626ba5406e9Sbeck case 4: 6274fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 6284fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 629ba5406e9Sbeck break; 630ba5406e9Sbeck } 631ba5406e9Sbeck /* The zero case isn't yet implemented here. The speedup 632ba5406e9Sbeck would probably be negligible. */ 633ba5406e9Sbeck # if 0 6342bd9bb84Sjsing if (n == 4) { 635913ec974Sbeck bn_mul_comba4(&(t[n2]), t, &(t[n])); 636913ec974Sbeck bn_mul_comba4(r, a, b); 637913ec974Sbeck bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn); 638913ec974Sbeck memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2)); 6392bd9bb84Sjsing } else 640ba5406e9Sbeck # endif 6412bd9bb84Sjsing if (n == 8) { 642913ec974Sbeck bn_mul_comba8(&(t[n2]), t, &(t[n])); 643913ec974Sbeck bn_mul_comba8(r, a, b); 6444fcf65c5Sdjm bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 6452bd9bb84Sjsing memset(&(r[n2 + tna + tnb]), 0, 6462bd9bb84Sjsing sizeof(BN_ULONG) * (n2 - tna - tnb)); 6472bd9bb84Sjsing } else { 648913ec974Sbeck p = &(t[n2*2]); 6494fcf65c5Sdjm bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 6504fcf65c5Sdjm bn_mul_recursive(r, a, b, n, 0, 0, p); 651913ec974Sbeck i = n / 2; 652913ec974Sbeck /* If there is only a bottom half to the number, 653913ec974Sbeck * just do it */ 6544fcf65c5Sdjm if (tna > tnb) 6554fcf65c5Sdjm j = tna - i; 6564fcf65c5Sdjm else 6574fcf65c5Sdjm j = tnb - i; 6582bd9bb84Sjsing if (j == 0) { 6594fcf65c5Sdjm bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), 6604fcf65c5Sdjm i, tna - i, tnb - i, p); 6612bd9bb84Sjsing memset(&(r[n2 + i * 2]), 0, 6622bd9bb84Sjsing sizeof(BN_ULONG) * (n2 - i * 2)); 663913ec974Sbeck } 664913ec974Sbeck else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ 665913ec974Sbeck { 666913ec974Sbeck bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), 6674fcf65c5Sdjm i, tna - i, tnb - i, p); 6684fcf65c5Sdjm memset(&(r[n2 + tna + tnb]), 0, 6694fcf65c5Sdjm sizeof(BN_ULONG) * (n2 - tna - tnb)); 670913ec974Sbeck } 671913ec974Sbeck else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 672913ec974Sbeck { 673913ec974Sbeck memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2); 6742bd9bb84Sjsing if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL && 6752bd9bb84Sjsing tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { 6762bd9bb84Sjsing bn_mul_normal(&(r[n2]), &(a[n]), tna, 6772bd9bb84Sjsing &(b[n]), tnb); 6782bd9bb84Sjsing } else { 6792bd9bb84Sjsing for (;;) { 680913ec974Sbeck i /= 2; 6814fcf65c5Sdjm /* these simplified conditions work 6824fcf65c5Sdjm * exclusively because difference 6834fcf65c5Sdjm * between tna and tnb is 1 or 0 */ 6842bd9bb84Sjsing if (i < tna || i < tnb) { 685913ec974Sbeck bn_mul_part_recursive(&(r[n2]), 6862bd9bb84Sjsing &(a[n]), &(b[n]), i, 6872bd9bb84Sjsing tna - i, tnb - i, p); 688913ec974Sbeck break; 6892bd9bb84Sjsing } else if (i == tna || i == tnb) { 690913ec974Sbeck bn_mul_recursive(&(r[n2]), 6912bd9bb84Sjsing &(a[n]), &(b[n]), i, 6922bd9bb84Sjsing tna - i, tnb - i, p); 693913ec974Sbeck break; 694913ec974Sbeck } 695913ec974Sbeck } 696913ec974Sbeck } 697913ec974Sbeck } 6985b37fcf3Sryker } 6995b37fcf3Sryker 700913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 701913ec974Sbeck * r[10] holds (a[0]*b[0]) 702913ec974Sbeck * r[32] holds (b[1]*b[1]) 703913ec974Sbeck */ 7045b37fcf3Sryker 705913ec974Sbeck c1 = (int)(bn_add_words(t, r,&(r[n2]), n2)); 706ba5406e9Sbeck 707ba5406e9Sbeck if (neg) /* if t[32] is negative */ 708ba5406e9Sbeck { 709913ec974Sbeck c1 -= (int)(bn_sub_words(&(t[n2]), t,&(t[n2]), n2)); 7102bd9bb84Sjsing } else { 711ba5406e9Sbeck /* Might have a carry */ 712ba5406e9Sbeck c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 713ba5406e9Sbeck } 7145b37fcf3Sryker 715913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 716913ec974Sbeck * r[10] holds (a[0]*b[0]) 717913ec974Sbeck * r[32] holds (b[1]*b[1]) 718913ec974Sbeck * c1 holds the carry bits 719913ec974Sbeck */ 720913ec974Sbeck c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 7212bd9bb84Sjsing if (c1) { 722913ec974Sbeck p = &(r[n + n2]); 723913ec974Sbeck lo= *p; 724913ec974Sbeck ln = (lo + c1)&BN_MASK2; 725913ec974Sbeck *p = ln; 7265b37fcf3Sryker 727913ec974Sbeck /* The overflow will stop before we over write 728913ec974Sbeck * words we should not overwrite */ 7292bd9bb84Sjsing if (ln < (BN_ULONG)c1) { 730913ec974Sbeck do { 731913ec974Sbeck p++; 732913ec974Sbeck lo= *p; 733913ec974Sbeck ln = (lo + 1) & BN_MASK2; 734913ec974Sbeck *p = ln; 735913ec974Sbeck } while (ln == 0); 736913ec974Sbeck } 737913ec974Sbeck } 738913ec974Sbeck } 7395b37fcf3Sryker 740913ec974Sbeck /* a and b must be the same size, which is n2. 741913ec974Sbeck * r needs to be n2 words and t needs to be n2*2 742913ec974Sbeck */ 7432bd9bb84Sjsing void 7442bd9bb84Sjsing bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t) 745913ec974Sbeck { 746913ec974Sbeck int n = n2 / 2; 7475b37fcf3Sryker 748913ec974Sbeck # ifdef BN_COUNT 7494fcf65c5Sdjm fprintf(stderr, " bn_mul_low_recursive %d * %d\n",n2,n2); 750913ec974Sbeck # endif 7515b37fcf3Sryker 7524fcf65c5Sdjm bn_mul_recursive(r, a, b, n, 0, 0, &(t[0])); 7532bd9bb84Sjsing if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) { 754913ec974Sbeck bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2])); 755913ec974Sbeck bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 756913ec974Sbeck bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2])); 757913ec974Sbeck bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 7582bd9bb84Sjsing } else { 759913ec974Sbeck bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n); 760913ec974Sbeck bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n); 761913ec974Sbeck bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 762913ec974Sbeck bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); 763913ec974Sbeck } 764913ec974Sbeck } 7655b37fcf3Sryker 766913ec974Sbeck /* a and b must be the same size, which is n2. 767913ec974Sbeck * r needs to be n2 words and t needs to be n2*2 768913ec974Sbeck * l is the low words of the output. 769913ec974Sbeck * t needs to be n2*3 770913ec974Sbeck */ 7712bd9bb84Sjsing void 7722bd9bb84Sjsing bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, 773913ec974Sbeck BN_ULONG *t) 774913ec974Sbeck { 775913ec974Sbeck int i, n; 776913ec974Sbeck int c1, c2; 777913ec974Sbeck int neg, oneg, zero; 778913ec974Sbeck BN_ULONG ll, lc, *lp, *mp; 779913ec974Sbeck 780913ec974Sbeck # ifdef BN_COUNT 7814fcf65c5Sdjm fprintf(stderr, " bn_mul_high %d * %d\n",n2,n2); 782913ec974Sbeck # endif 783913ec974Sbeck n = n2 / 2; 784913ec974Sbeck 785913ec974Sbeck /* Calculate (al-ah)*(bh-bl) */ 786913ec974Sbeck neg = zero = 0; 787913ec974Sbeck c1 = bn_cmp_words(&(a[0]), &(a[n]), n); 788913ec974Sbeck c2 = bn_cmp_words(&(b[n]), &(b[0]), n); 7892bd9bb84Sjsing switch (c1 * 3 + c2) { 790913ec974Sbeck case -4: 791913ec974Sbeck bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); 792913ec974Sbeck bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); 793913ec974Sbeck break; 794913ec974Sbeck case -3: 795913ec974Sbeck zero = 1; 796913ec974Sbeck break; 797913ec974Sbeck case -2: 798913ec974Sbeck bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); 799913ec974Sbeck bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); 800913ec974Sbeck neg = 1; 801913ec974Sbeck break; 802913ec974Sbeck case -1: 803913ec974Sbeck case 0: 804913ec974Sbeck case 1: 805913ec974Sbeck zero = 1; 806913ec974Sbeck break; 807913ec974Sbeck case 2: 808913ec974Sbeck bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); 809913ec974Sbeck bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); 810913ec974Sbeck neg = 1; 811913ec974Sbeck break; 812913ec974Sbeck case 3: 813913ec974Sbeck zero = 1; 814913ec974Sbeck break; 815913ec974Sbeck case 4: 816913ec974Sbeck bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); 817913ec974Sbeck bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); 818913ec974Sbeck break; 819913ec974Sbeck } 820913ec974Sbeck 821913ec974Sbeck oneg = neg; 822913ec974Sbeck /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ 823913ec974Sbeck /* r[10] = (a[1]*b[1]) */ 824913ec974Sbeck # ifdef BN_MUL_COMBA 8252bd9bb84Sjsing if (n == 8) { 826913ec974Sbeck bn_mul_comba8(&(t[0]), &(r[0]), &(r[n])); 827913ec974Sbeck bn_mul_comba8(r, &(a[n]), &(b[n])); 8282bd9bb84Sjsing } else 829913ec974Sbeck # endif 830913ec974Sbeck { 8314fcf65c5Sdjm bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2])); 8324fcf65c5Sdjm bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); 833913ec974Sbeck } 834913ec974Sbeck 835913ec974Sbeck /* s0 == low(al*bl) 836913ec974Sbeck * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) 837913ec974Sbeck * We know s0 and s1 so the only unknown is high(al*bl) 838913ec974Sbeck * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) 839913ec974Sbeck * high(al*bl) == s1 - (r[0]+l[0]+t[0]) 840913ec974Sbeck */ 8412bd9bb84Sjsing if (l != NULL) { 842913ec974Sbeck lp = &(t[n2 + n]); 843913ec974Sbeck c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n)); 8442bd9bb84Sjsing } else { 845913ec974Sbeck c1 = 0; 846913ec974Sbeck lp = &(r[0]); 847913ec974Sbeck } 848913ec974Sbeck 849913ec974Sbeck if (neg) 850913ec974Sbeck neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n)); 8512bd9bb84Sjsing else { 852913ec974Sbeck bn_add_words(&(t[n2]), lp, &(t[0]), n); 853913ec974Sbeck neg = 0; 854913ec974Sbeck } 855913ec974Sbeck 8562bd9bb84Sjsing if (l != NULL) { 857913ec974Sbeck bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n); 8582bd9bb84Sjsing } else { 859913ec974Sbeck lp = &(t[n2 + n]); 860913ec974Sbeck mp = &(t[n2]); 861913ec974Sbeck for (i = 0; i < n; i++) 862913ec974Sbeck lp[i] = ((~mp[i]) + 1) & BN_MASK2; 863913ec974Sbeck } 864913ec974Sbeck 865913ec974Sbeck /* s[0] = low(al*bl) 866913ec974Sbeck * t[3] = high(al*bl) 867913ec974Sbeck * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign 868913ec974Sbeck * r[10] = (a[1]*b[1]) 869913ec974Sbeck */ 870913ec974Sbeck /* R[10] = al*bl 871913ec974Sbeck * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) 872913ec974Sbeck * R[32] = ah*bh 873913ec974Sbeck */ 874913ec974Sbeck /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) 875913ec974Sbeck * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) 876913ec974Sbeck * R[3]=r[1]+(carry/borrow) 877913ec974Sbeck */ 8782bd9bb84Sjsing if (l != NULL) { 879913ec974Sbeck lp = &(t[n2]); 880913ec974Sbeck c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); 8812bd9bb84Sjsing } else { 882913ec974Sbeck lp = &(t[n2 + n]); 883913ec974Sbeck c1 = 0; 884913ec974Sbeck } 885913ec974Sbeck c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n)); 886913ec974Sbeck if (oneg) 887913ec974Sbeck c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n)); 888913ec974Sbeck else 889913ec974Sbeck c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n)); 890913ec974Sbeck 891913ec974Sbeck c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n)); 892913ec974Sbeck c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n)); 893913ec974Sbeck if (oneg) 894913ec974Sbeck c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n)); 895913ec974Sbeck else 896913ec974Sbeck c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n)); 897913ec974Sbeck 898913ec974Sbeck if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ 899913ec974Sbeck { 900913ec974Sbeck i = 0; 9012bd9bb84Sjsing if (c1 > 0) { 902913ec974Sbeck lc = c1; 903913ec974Sbeck do { 904913ec974Sbeck ll = (r[i] + lc) & BN_MASK2; 905913ec974Sbeck r[i++] = ll; 906913ec974Sbeck lc = (lc > ll); 907913ec974Sbeck } while (lc); 9082bd9bb84Sjsing } else { 909913ec974Sbeck lc = -c1; 910913ec974Sbeck do { 911913ec974Sbeck ll = r[i]; 912913ec974Sbeck r[i++] = (ll - lc) & BN_MASK2; 913913ec974Sbeck lc = (lc > ll); 914913ec974Sbeck } while (lc); 915913ec974Sbeck } 916913ec974Sbeck } 917913ec974Sbeck if (c2 != 0) /* Add starting at r[1] */ 918913ec974Sbeck { 919913ec974Sbeck i = n; 9202bd9bb84Sjsing if (c2 > 0) { 921913ec974Sbeck lc = c2; 922913ec974Sbeck do { 923913ec974Sbeck ll = (r[i] + lc) & BN_MASK2; 924913ec974Sbeck r[i++] = ll; 925913ec974Sbeck lc = (lc > ll); 926913ec974Sbeck } while (lc); 9272bd9bb84Sjsing } else { 928913ec974Sbeck lc = -c2; 929913ec974Sbeck do { 930913ec974Sbeck ll = r[i]; 931913ec974Sbeck r[i++] = (ll - lc) & BN_MASK2; 932913ec974Sbeck lc = (lc > ll); 933913ec974Sbeck } while (lc); 934913ec974Sbeck } 935913ec974Sbeck } 9365b37fcf3Sryker } 937ba5406e9Sbeck #endif /* BN_RECURSION */ 938913ec974Sbeck 9392bd9bb84Sjsing int 9402bd9bb84Sjsing BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 941913ec974Sbeck { 9424fcf65c5Sdjm int ret = 0; 943913ec974Sbeck int top, al, bl; 944913ec974Sbeck BIGNUM *rr; 945ba5406e9Sbeck #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 946ba5406e9Sbeck int i; 947ba5406e9Sbeck #endif 948913ec974Sbeck #ifdef BN_RECURSION 9494fcf65c5Sdjm BIGNUM *t = NULL; 9504fcf65c5Sdjm int j = 0, k; 951913ec974Sbeck #endif 952913ec974Sbeck 953913ec974Sbeck #ifdef BN_COUNT 9544fcf65c5Sdjm fprintf(stderr, "BN_mul %d * %d\n",a->top,b->top); 955913ec974Sbeck #endif 956913ec974Sbeck 957913ec974Sbeck 958913ec974Sbeck al = a->top; 959913ec974Sbeck bl = b->top; 960913ec974Sbeck 9612bd9bb84Sjsing if ((al == 0) || (bl == 0)) { 9624fcf65c5Sdjm BN_zero(r); 963913ec974Sbeck return (1); 964913ec974Sbeck } 965913ec974Sbeck top = al + bl; 966913ec974Sbeck 967ba5406e9Sbeck BN_CTX_start(ctx); 9682bd9bb84Sjsing if ((r == a) || (r == b)) { 9692bd9bb84Sjsing if ((rr = BN_CTX_get(ctx)) == NULL) 9702bd9bb84Sjsing goto err; 9712bd9bb84Sjsing } else 972913ec974Sbeck rr = r; 973c109e398Sbeck rr->neg = a->neg ^ b->neg; 974913ec974Sbeck 975913ec974Sbeck #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 976ba5406e9Sbeck i = al - bl; 977ba5406e9Sbeck #endif 978913ec974Sbeck #ifdef BN_MUL_COMBA 9792bd9bb84Sjsing if (i == 0) { 980ba5406e9Sbeck # if 0 9812bd9bb84Sjsing if (al == 4) { 982e729bd5aSjsing if (!bn_wexpand(rr, 8)) 9832bd9bb84Sjsing goto err; 984913ec974Sbeck rr->top = 8; 985913ec974Sbeck bn_mul_comba4(rr->d, a->d, b->d); 986913ec974Sbeck goto end; 987913ec974Sbeck } 988ba5406e9Sbeck # endif 9892bd9bb84Sjsing if (al == 8) { 990e729bd5aSjsing if (!bn_wexpand(rr, 16)) 9912bd9bb84Sjsing goto err; 992913ec974Sbeck rr->top = 16; 993913ec974Sbeck bn_mul_comba8(rr->d, a->d, b->d); 994913ec974Sbeck goto end; 995913ec974Sbeck } 996913ec974Sbeck } 997ba5406e9Sbeck #endif /* BN_MUL_COMBA */ 998913ec974Sbeck #ifdef BN_RECURSION 9992bd9bb84Sjsing if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { 10002bd9bb84Sjsing if (i >= -1 && i <= 1) { 10014fcf65c5Sdjm /* Find out the power of two lower or equal 10024fcf65c5Sdjm to the longest of the two numbers */ 10032bd9bb84Sjsing if (i >= 0) { 10044fcf65c5Sdjm j = BN_num_bits_word((BN_ULONG)al); 10054fcf65c5Sdjm } 10062bd9bb84Sjsing if (i == -1) { 10074fcf65c5Sdjm j = BN_num_bits_word((BN_ULONG)bl); 10084fcf65c5Sdjm } 10094fcf65c5Sdjm j = 1 << (j - 1); 10104fcf65c5Sdjm assert(j <= al || j <= bl); 10114fcf65c5Sdjm k = j + j; 1012aa389b8cSjsing if ((t = BN_CTX_get(ctx)) == NULL) 10130a5d6edeSdjm goto err; 10142bd9bb84Sjsing if (al > j || bl > j) { 1015e729bd5aSjsing if (!bn_wexpand(t, k * 4)) 10162bd9bb84Sjsing goto err; 1017e729bd5aSjsing if (!bn_wexpand(rr, k * 4)) 10182bd9bb84Sjsing goto err; 10194fcf65c5Sdjm bn_mul_part_recursive(rr->d, a->d, b->d, 10204fcf65c5Sdjm j, al - j, bl - j, t->d); 10214fcf65c5Sdjm } 10224fcf65c5Sdjm else /* al <= j || bl <= j */ 10234fcf65c5Sdjm { 1024e729bd5aSjsing if (!bn_wexpand(t, k * 2)) 10252bd9bb84Sjsing goto err; 1026e729bd5aSjsing if (!bn_wexpand(rr, k * 2)) 10272bd9bb84Sjsing goto err; 10284fcf65c5Sdjm bn_mul_recursive(rr->d, a->d, b->d, 10294fcf65c5Sdjm j, al - j, bl - j, t->d); 10304fcf65c5Sdjm } 10314fcf65c5Sdjm rr->top = top; 10324fcf65c5Sdjm goto end; 10334fcf65c5Sdjm } 10344fcf65c5Sdjm #if 0 10352bd9bb84Sjsing if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) { 10364fcf65c5Sdjm BIGNUM *tmp_bn = (BIGNUM *)b; 1037e729bd5aSjsing if (!bn_wexpand(tmp_bn, al)) 10382bd9bb84Sjsing goto err; 10394fcf65c5Sdjm tmp_bn->d[bl] = 0; 1040913ec974Sbeck bl++; 1041ba5406e9Sbeck i--; 10422bd9bb84Sjsing } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) { 10434fcf65c5Sdjm BIGNUM *tmp_bn = (BIGNUM *)a; 1044e729bd5aSjsing if (!bn_wexpand(tmp_bn, bl)) 10452bd9bb84Sjsing goto err; 10464fcf65c5Sdjm tmp_bn->d[al] = 0; 1047913ec974Sbeck al++; 1048ba5406e9Sbeck i++; 1049913ec974Sbeck } 10502bd9bb84Sjsing if (i == 0) { 1051ba5406e9Sbeck /* symmetric and > 4 */ 1052913ec974Sbeck /* 16 or larger */ 1053913ec974Sbeck j = BN_num_bits_word((BN_ULONG)al); 1054913ec974Sbeck j = 1 << (j - 1); 1055913ec974Sbeck k = j + j; 1056aa389b8cSjsing if ((t = BN_CTX_get(ctx)) == NULL) 1057aa389b8cSjsing goto err; 1058913ec974Sbeck if (al == j) /* exact multiple */ 1059913ec974Sbeck { 1060e729bd5aSjsing if (!bn_wexpand(t, k * 2)) 10612bd9bb84Sjsing goto err; 1062e729bd5aSjsing if (!bn_wexpand(rr, k * 2)) 10632bd9bb84Sjsing goto err; 1064913ec974Sbeck bn_mul_recursive(rr->d, a->d, b->d, al, t->d); 10652bd9bb84Sjsing } else { 1066e729bd5aSjsing if (!bn_wexpand(t, k * 4)) 10672bd9bb84Sjsing goto err; 1068e729bd5aSjsing if (!bn_wexpand(rr, k * 4)) 10692bd9bb84Sjsing goto err; 10702bd9bb84Sjsing bn_mul_part_recursive(rr->d, a->d, b->d, 10712bd9bb84Sjsing al - j, j, t->d); 1072913ec974Sbeck } 1073913ec974Sbeck rr->top = top; 1074ba5406e9Sbeck goto end; 1075ba5406e9Sbeck } 10764fcf65c5Sdjm #endif 1077767fe2ffSmarkus } 1078ba5406e9Sbeck #endif /* BN_RECURSION */ 1079e729bd5aSjsing if (!bn_wexpand(rr, top)) 10802bd9bb84Sjsing goto err; 1081ba5406e9Sbeck rr->top = top; 1082ba5406e9Sbeck bn_mul_normal(rr->d, a->d, al, b->d, bl); 1083ba5406e9Sbeck 1084913ec974Sbeck #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 1085913ec974Sbeck end: 1086913ec974Sbeck #endif 10874fcf65c5Sdjm bn_correct_top(rr); 10882bd9bb84Sjsing if (r != rr) 10892bd9bb84Sjsing BN_copy(r, rr); 1090ba5406e9Sbeck ret = 1; 1091ba5406e9Sbeck err: 1092ba5406e9Sbeck BN_CTX_end(ctx); 1093ba5406e9Sbeck return (ret); 1094913ec974Sbeck } 1095913ec974Sbeck 10962bd9bb84Sjsing void 10972bd9bb84Sjsing bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 1098913ec974Sbeck { 1099913ec974Sbeck BN_ULONG *rr; 1100913ec974Sbeck 1101913ec974Sbeck #ifdef BN_COUNT 11024fcf65c5Sdjm fprintf(stderr, " bn_mul_normal %d * %d\n", na, nb); 1103913ec974Sbeck #endif 1104913ec974Sbeck 11052bd9bb84Sjsing if (na < nb) { 1106913ec974Sbeck int itmp; 1107913ec974Sbeck BN_ULONG *ltmp; 1108913ec974Sbeck 11092bd9bb84Sjsing itmp = na; 11102bd9bb84Sjsing na = nb; 11112bd9bb84Sjsing nb = itmp; 11122bd9bb84Sjsing ltmp = a; 11132bd9bb84Sjsing a = b; 11142bd9bb84Sjsing b = ltmp; 1115913ec974Sbeck 1116913ec974Sbeck } 1117913ec974Sbeck rr = &(r[na]); 11182bd9bb84Sjsing if (nb <= 0) { 11194fcf65c5Sdjm (void)bn_mul_words(r, a, na, 0); 11204fcf65c5Sdjm return; 11212bd9bb84Sjsing } else 1122913ec974Sbeck rr[0] = bn_mul_words(r, a, na, b[0]); 1123913ec974Sbeck 11242bd9bb84Sjsing for (;;) { 11252bd9bb84Sjsing if (--nb <= 0) 11262bd9bb84Sjsing return; 1127913ec974Sbeck rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); 11282bd9bb84Sjsing if (--nb <= 0) 11292bd9bb84Sjsing return; 1130913ec974Sbeck rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); 11312bd9bb84Sjsing if (--nb <= 0) 11322bd9bb84Sjsing return; 1133913ec974Sbeck rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); 11342bd9bb84Sjsing if (--nb <= 0) 11352bd9bb84Sjsing return; 1136913ec974Sbeck rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); 1137913ec974Sbeck rr += 4; 1138913ec974Sbeck r += 4; 1139913ec974Sbeck b += 4; 1140913ec974Sbeck } 1141913ec974Sbeck } 1142913ec974Sbeck 11432bd9bb84Sjsing void 11442bd9bb84Sjsing bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) 1145913ec974Sbeck { 1146913ec974Sbeck #ifdef BN_COUNT 11474fcf65c5Sdjm fprintf(stderr, " bn_mul_low_normal %d * %d\n", n, n); 1148913ec974Sbeck #endif 1149913ec974Sbeck bn_mul_words(r, a, n, b[0]); 1150913ec974Sbeck 11512bd9bb84Sjsing for (;;) { 11522bd9bb84Sjsing if (--n <= 0) 11532bd9bb84Sjsing return; 1154913ec974Sbeck bn_mul_add_words(&(r[1]), a, n, b[1]); 11552bd9bb84Sjsing if (--n <= 0) 11562bd9bb84Sjsing return; 1157913ec974Sbeck bn_mul_add_words(&(r[2]), a, n, b[2]); 11582bd9bb84Sjsing if (--n <= 0) 11592bd9bb84Sjsing return; 1160913ec974Sbeck bn_mul_add_words(&(r[3]), a, n, b[3]); 11612bd9bb84Sjsing if (--n <= 0) 11622bd9bb84Sjsing return; 1163913ec974Sbeck bn_mul_add_words(&(r[4]), a, n, b[4]); 1164913ec974Sbeck r += 4; 1165913ec974Sbeck b += 4; 1166913ec974Sbeck } 1167913ec974Sbeck } 1168