1*df1d0ed5Sjsing /* $OpenBSD: bn_mul.c,v 1.32 2023/02/14 18:37:15 jsing 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 #include <assert.h> 60a8913c44Sjsing #include <stdio.h> 61a8913c44Sjsing #include <string.h> 62a8913c44Sjsing 638cf4d6a6Sjsing #include <openssl/opensslconf.h> 648cf4d6a6Sjsing 65de344ea3Sjsing #include "bn_arch.h" 66*df1d0ed5Sjsing #include "bn_internal.h" 67c9675a23Stb #include "bn_local.h" 685b37fcf3Sryker 69*df1d0ed5Sjsing /* 70*df1d0ed5Sjsing * bn_mul_add_words() computes (carry:r[i]) = a[i] * w + r[i] + carry, where 71*df1d0ed5Sjsing * a is an array of words and w is a single word. This should really be called 72*df1d0ed5Sjsing * bn_mulw_add_words() since only one input is an array. This is used as a step 73*df1d0ed5Sjsing * in the multiplication of word arrays. 74*df1d0ed5Sjsing */ 758889fb99Sjsing #ifndef HAVE_BN_MUL_ADD_WORDS 768889fb99Sjsing BN_ULONG 77*df1d0ed5Sjsing bn_mul_add_words(BN_ULONG *r, const BN_ULONG *a, int num, BN_ULONG w) 788889fb99Sjsing { 79*df1d0ed5Sjsing BN_ULONG carry = 0; 808889fb99Sjsing 818889fb99Sjsing assert(num >= 0); 828889fb99Sjsing if (num <= 0) 83*df1d0ed5Sjsing return 0; 848889fb99Sjsing 858889fb99Sjsing #ifndef OPENSSL_SMALL_FOOTPRINT 868889fb99Sjsing while (num & ~3) { 87*df1d0ed5Sjsing bn_mulw_addw_addw(a[0], w, r[0], carry, &carry, &r[0]); 88*df1d0ed5Sjsing bn_mulw_addw_addw(a[1], w, r[1], carry, &carry, &r[1]); 89*df1d0ed5Sjsing bn_mulw_addw_addw(a[2], w, r[2], carry, &carry, &r[2]); 90*df1d0ed5Sjsing bn_mulw_addw_addw(a[3], w, r[3], carry, &carry, &r[3]); 91*df1d0ed5Sjsing a += 4; 92*df1d0ed5Sjsing r += 4; 938889fb99Sjsing num -= 4; 948889fb99Sjsing } 958889fb99Sjsing #endif 968889fb99Sjsing while (num) { 97*df1d0ed5Sjsing bn_mulw_addw_addw(a[0], w, r[0], carry, &carry, &r[0]); 98*df1d0ed5Sjsing a++; 99*df1d0ed5Sjsing r++; 1008889fb99Sjsing num--; 1018889fb99Sjsing } 1028889fb99Sjsing 103*df1d0ed5Sjsing return carry; 1048889fb99Sjsing } 1058889fb99Sjsing #endif 1068889fb99Sjsing 107*df1d0ed5Sjsing /* 108*df1d0ed5Sjsing * bn_mul_comba4() computes r[] = a[] * b[] using Comba multiplication 109*df1d0ed5Sjsing * (https://everything2.com/title/Comba+multiplication), where a and b are both 110*df1d0ed5Sjsing * four word arrays, producing an eight word array result. 111*df1d0ed5Sjsing */ 112de344ea3Sjsing #ifndef HAVE_BN_MUL_COMBA4 113de344ea3Sjsing void 114de344ea3Sjsing bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) 115de344ea3Sjsing { 116*df1d0ed5Sjsing BN_ULONG c0, c1, c2; 117de344ea3Sjsing 118*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[0], 0, 0, 0, &c2, &c1, &r[0]); 119*df1d0ed5Sjsing 120*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[1], 0, c2, c1, &c2, &c1, &c0); 121*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[0], c2, c1, c0, &c2, &c1, &r[1]); 122*df1d0ed5Sjsing 123*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[0], 0, c2, c1, &c2, &c1, &c0); 124*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[1], c2, c1, c0, &c2, &c1, &c0); 125*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[2], c2, c1, c0, &c2, &c1, &r[2]); 126*df1d0ed5Sjsing 127*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[3], 0, c2, c1, &c2, &c1, &c0); 128*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[2], c2, c1, c0, &c2, &c1, &c0); 129*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[1], c2, c1, c0, &c2, &c1, &c0); 130*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[0], c2, c1, c0, &c2, &c1, &r[3]); 131*df1d0ed5Sjsing 132*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[1], 0, c2, c1, &c2, &c1, &c0); 133*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[2], c2, c1, c0, &c2, &c1, &c0); 134*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[3], c2, c1, c0, &c2, &c1, &r[4]); 135*df1d0ed5Sjsing 136*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[3], 0, c2, c1, &c2, &c1, &c0); 137*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[2], c2, c1, c0, &c2, &c1, &r[5]); 138*df1d0ed5Sjsing 139*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[3], 0, c2, c1, &c2, &r[7], &r[6]); 140de344ea3Sjsing } 141de344ea3Sjsing #endif 142de344ea3Sjsing 143*df1d0ed5Sjsing /* 144*df1d0ed5Sjsing * bn_mul_comba8() computes r[] = a[] * b[] using Comba multiplication 145*df1d0ed5Sjsing * (https://everything2.com/title/Comba+multiplication), where a and b are both 146*df1d0ed5Sjsing * eight word arrays, producing a 16 word array result. 147*df1d0ed5Sjsing */ 148de344ea3Sjsing #ifndef HAVE_BN_MUL_COMBA8 149de344ea3Sjsing void 150de344ea3Sjsing bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) 151de344ea3Sjsing { 152*df1d0ed5Sjsing BN_ULONG c0, c1, c2; 153de344ea3Sjsing 154*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[0], 0, 0, 0, &c2, &c1, &r[0]); 155*df1d0ed5Sjsing 156*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[1], 0, c2, c1, &c2, &c1, &c0); 157*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[0], c2, c1, c0, &c2, &c1, &r[1]); 158*df1d0ed5Sjsing 159*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[0], 0, c2, c1, &c2, &c1, &c0); 160*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[1], c2, c1, c0, &c2, &c1, &c0); 161*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[2], c2, c1, c0, &c2, &c1, &r[2]); 162*df1d0ed5Sjsing 163*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[3], 0, c2, c1, &c2, &c1, &c0); 164*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[2], c2, c1, c0, &c2, &c1, &c0); 165*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[1], c2, c1, c0, &c2, &c1, &c0); 166*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[0], c2, c1, c0, &c2, &c1, &r[3]); 167*df1d0ed5Sjsing 168*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[0], 0, c2, c1, &c2, &c1, &c0); 169*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[1], c2, c1, c0, &c2, &c1, &c0); 170*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[2], c2, c1, c0, &c2, &c1, &c0); 171*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[3], c2, c1, c0, &c2, &c1, &c0); 172*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[4], c2, c1, c0, &c2, &c1, &r[4]); 173*df1d0ed5Sjsing 174*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[5], 0, c2, c1, &c2, &c1, &c0); 175*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[4], c2, c1, c0, &c2, &c1, &c0); 176*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[3], c2, c1, c0, &c2, &c1, &c0); 177*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[2], c2, c1, c0, &c2, &c1, &c0); 178*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[1], c2, c1, c0, &c2, &c1, &c0); 179*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[0], c2, c1, c0, &c2, &c1, &r[5]); 180*df1d0ed5Sjsing 181*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[0], 0, c2, c1, &c2, &c1, &c0); 182*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[1], c2, c1, c0, &c2, &c1, &c0); 183*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[2], c2, c1, c0, &c2, &c1, &c0); 184*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[3], c2, c1, c0, &c2, &c1, &c0); 185*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[4], c2, c1, c0, &c2, &c1, &c0); 186*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[5], c2, c1, c0, &c2, &c1, &c0); 187*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[6], c2, c1, c0, &c2, &c1, &r[6]); 188*df1d0ed5Sjsing 189*df1d0ed5Sjsing bn_mulw_addtw(a[0], b[7], 0, c2, c1, &c2, &c1, &c0); 190*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[6], c2, c1, c0, &c2, &c1, &c0); 191*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[5], c2, c1, c0, &c2, &c1, &c0); 192*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[4], c2, c1, c0, &c2, &c1, &c0); 193*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[3], c2, c1, c0, &c2, &c1, &c0); 194*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[2], c2, c1, c0, &c2, &c1, &c0); 195*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[1], c2, c1, c0, &c2, &c1, &c0); 196*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[0], c2, c1, c0, &c2, &c1, &r[7]); 197*df1d0ed5Sjsing 198*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[1], 0, c2, c1, &c2, &c1, &c0); 199*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[2], c2, c1, c0, &c2, &c1, &c0); 200*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[3], c2, c1, c0, &c2, &c1, &c0); 201*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[4], c2, c1, c0, &c2, &c1, &c0); 202*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[5], c2, c1, c0, &c2, &c1, &c0); 203*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[6], c2, c1, c0, &c2, &c1, &c0); 204*df1d0ed5Sjsing bn_mulw_addtw(a[1], b[7], c2, c1, c0, &c2, &c1, &r[8]); 205*df1d0ed5Sjsing 206*df1d0ed5Sjsing bn_mulw_addtw(a[2], b[7], 0, c2, c1, &c2, &c1, &c0); 207*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[6], c2, c1, c0, &c2, &c1, &c0); 208*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[5], c2, c1, c0, &c2, &c1, &c0); 209*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[4], c2, c1, c0, &c2, &c1, &c0); 210*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[3], c2, c1, c0, &c2, &c1, &c0); 211*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[2], c2, c1, c0, &c2, &c1, &r[9]); 212*df1d0ed5Sjsing 213*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[3], 0, c2, c1, &c2, &c1, &c0); 214*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[4], c2, c1, c0, &c2, &c1, &c0); 215*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[5], c2, c1, c0, &c2, &c1, &c0); 216*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[6], c2, c1, c0, &c2, &c1, &c0); 217*df1d0ed5Sjsing bn_mulw_addtw(a[3], b[7], c2, c1, c0, &c2, &c1, &r[10]); 218*df1d0ed5Sjsing 219*df1d0ed5Sjsing bn_mulw_addtw(a[4], b[7], 0, c2, c1, &c2, &c1, &c0); 220*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[6], c2, c1, c0, &c2, &c1, &c0); 221*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[5], c2, c1, c0, &c2, &c1, &c0); 222*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[4], c2, c1, c0, &c2, &c1, &r[11]); 223*df1d0ed5Sjsing 224*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[5], 0, c2, c1, &c2, &c1, &c0); 225*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[6], c2, c1, c0, &c2, &c1, &c0); 226*df1d0ed5Sjsing bn_mulw_addtw(a[5], b[7], c2, c1, c0, &c2, &c1, &r[12]); 227*df1d0ed5Sjsing 228*df1d0ed5Sjsing bn_mulw_addtw(a[6], b[7], 0, c2, c1, &c2, &c1, &c0); 229*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[6], c2, c1, c0, &c2, &c1, &r[13]); 230*df1d0ed5Sjsing 231*df1d0ed5Sjsing bn_mulw_addtw(a[7], b[7], 0, c2, c1, &c2, &r[15], &r[14]); 232de344ea3Sjsing } 233de344ea3Sjsing #endif 234de344ea3Sjsing 235*df1d0ed5Sjsing /* 236*df1d0ed5Sjsing * bn_mul_words() computes (carry:r[i]) = a[i] * w + carry, where a is an array 237*df1d0ed5Sjsing * of words and w is a single word. This should really be called bn_mulw_words() 238*df1d0ed5Sjsing * since only one input is an array. This is used as a step in the multiplication 239*df1d0ed5Sjsing * of word arrays. 240*df1d0ed5Sjsing */ 2418889fb99Sjsing #ifndef HAVE_BN_MUL_WORDS 2428889fb99Sjsing BN_ULONG 243*df1d0ed5Sjsing bn_mul_words(BN_ULONG *r, const BN_ULONG *a, int num, BN_ULONG w) 2448889fb99Sjsing { 2458889fb99Sjsing BN_ULONG carry = 0; 2468889fb99Sjsing 2478889fb99Sjsing assert(num >= 0); 2488889fb99Sjsing if (num <= 0) 249*df1d0ed5Sjsing return 0; 2508889fb99Sjsing 2518889fb99Sjsing #ifndef OPENSSL_SMALL_FOOTPRINT 2528889fb99Sjsing while (num & ~3) { 253*df1d0ed5Sjsing bn_mulw_addw(a[0], w, carry, &carry, &r[0]); 254*df1d0ed5Sjsing bn_mulw_addw(a[1], w, carry, &carry, &r[1]); 255*df1d0ed5Sjsing bn_mulw_addw(a[2], w, carry, &carry, &r[2]); 256*df1d0ed5Sjsing bn_mulw_addw(a[3], w, carry, &carry, &r[3]); 257*df1d0ed5Sjsing a += 4; 258*df1d0ed5Sjsing r += 4; 2598889fb99Sjsing num -= 4; 2608889fb99Sjsing } 2618889fb99Sjsing #endif 2628889fb99Sjsing while (num) { 263*df1d0ed5Sjsing bn_mulw_addw(a[0], w, carry, &carry, &r[0]); 264*df1d0ed5Sjsing a++; 265*df1d0ed5Sjsing r++; 2668889fb99Sjsing num--; 2678889fb99Sjsing } 268*df1d0ed5Sjsing return carry; 2698889fb99Sjsing } 2708889fb99Sjsing #endif 2718889fb99Sjsing 272e8d08ebaSjsing #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) 273fa7eac9fSjsing /* 274fa7eac9fSjsing * Here follows a specialised variant of bn_sub_words(), which has the property 275fa7eac9fSjsing * performing operations on arrays of different sizes. The sizes of those arrays 276fa7eac9fSjsing * is expressed through cl, which is the common length (basically, 277fa7eac9fSjsing * min(len(a),len(b))), and dl, which is the delta between the two lengths, 278fa7eac9fSjsing * calculated as len(a)-len(b). All lengths are the number of BN_ULONGs. For the 279fa7eac9fSjsing * operations that require a result array as parameter, it must have the length 280fa7eac9fSjsing * cl+abs(dl). 281fa7eac9fSjsing */ 282e8d08ebaSjsing BN_ULONG 283e8d08ebaSjsing bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, 284e8d08ebaSjsing int dl) 285e8d08ebaSjsing { 286e8d08ebaSjsing BN_ULONG c, t; 287e8d08ebaSjsing 288e8d08ebaSjsing assert(cl >= 0); 289e8d08ebaSjsing c = bn_sub_words(r, a, b, cl); 290e8d08ebaSjsing 291e8d08ebaSjsing if (dl == 0) 292e8d08ebaSjsing return c; 293e8d08ebaSjsing 294e8d08ebaSjsing r += cl; 295e8d08ebaSjsing a += cl; 296e8d08ebaSjsing b += cl; 297e8d08ebaSjsing 298e8d08ebaSjsing if (dl < 0) { 299e8d08ebaSjsing for (;;) { 300e8d08ebaSjsing t = b[0]; 301e8d08ebaSjsing r[0] = (0 - t - c) & BN_MASK2; 302e8d08ebaSjsing if (t != 0) 303e8d08ebaSjsing c = 1; 304e8d08ebaSjsing if (++dl >= 0) 305e8d08ebaSjsing break; 306e8d08ebaSjsing 307e8d08ebaSjsing t = b[1]; 308e8d08ebaSjsing r[1] = (0 - t - c) & BN_MASK2; 309e8d08ebaSjsing if (t != 0) 310e8d08ebaSjsing c = 1; 311e8d08ebaSjsing if (++dl >= 0) 312e8d08ebaSjsing break; 313e8d08ebaSjsing 314e8d08ebaSjsing t = b[2]; 315e8d08ebaSjsing r[2] = (0 - t - c) & BN_MASK2; 316e8d08ebaSjsing if (t != 0) 317e8d08ebaSjsing c = 1; 318e8d08ebaSjsing if (++dl >= 0) 319e8d08ebaSjsing break; 320e8d08ebaSjsing 321e8d08ebaSjsing t = b[3]; 322e8d08ebaSjsing r[3] = (0 - t - c) & BN_MASK2; 323e8d08ebaSjsing if (t != 0) 324e8d08ebaSjsing c = 1; 325e8d08ebaSjsing if (++dl >= 0) 326e8d08ebaSjsing break; 327e8d08ebaSjsing 328e8d08ebaSjsing b += 4; 329e8d08ebaSjsing r += 4; 330e8d08ebaSjsing } 331e8d08ebaSjsing } else { 332e8d08ebaSjsing int save_dl = dl; 333e8d08ebaSjsing while (c) { 334e8d08ebaSjsing t = a[0]; 335e8d08ebaSjsing r[0] = (t - c) & BN_MASK2; 336e8d08ebaSjsing if (t != 0) 337e8d08ebaSjsing c = 0; 338e8d08ebaSjsing if (--dl <= 0) 339e8d08ebaSjsing break; 340e8d08ebaSjsing 341e8d08ebaSjsing t = a[1]; 342e8d08ebaSjsing r[1] = (t - c) & BN_MASK2; 343e8d08ebaSjsing if (t != 0) 344e8d08ebaSjsing c = 0; 345e8d08ebaSjsing if (--dl <= 0) 346e8d08ebaSjsing break; 347e8d08ebaSjsing 348e8d08ebaSjsing t = a[2]; 349e8d08ebaSjsing r[2] = (t - c) & BN_MASK2; 350e8d08ebaSjsing if (t != 0) 351e8d08ebaSjsing c = 0; 352e8d08ebaSjsing if (--dl <= 0) 353e8d08ebaSjsing break; 354e8d08ebaSjsing 355e8d08ebaSjsing t = a[3]; 356e8d08ebaSjsing r[3] = (t - c) & BN_MASK2; 357e8d08ebaSjsing if (t != 0) 358e8d08ebaSjsing c = 0; 359e8d08ebaSjsing if (--dl <= 0) 360e8d08ebaSjsing break; 361e8d08ebaSjsing 362e8d08ebaSjsing save_dl = dl; 363e8d08ebaSjsing a += 4; 364e8d08ebaSjsing r += 4; 365e8d08ebaSjsing } 366e8d08ebaSjsing if (dl > 0) { 367e8d08ebaSjsing if (save_dl > dl) { 368e8d08ebaSjsing switch (save_dl - dl) { 369e8d08ebaSjsing case 1: 370e8d08ebaSjsing r[1] = a[1]; 371e8d08ebaSjsing if (--dl <= 0) 372e8d08ebaSjsing break; 373e8d08ebaSjsing case 2: 374e8d08ebaSjsing r[2] = a[2]; 375e8d08ebaSjsing if (--dl <= 0) 376e8d08ebaSjsing break; 377e8d08ebaSjsing case 3: 378e8d08ebaSjsing r[3] = a[3]; 379e8d08ebaSjsing if (--dl <= 0) 380e8d08ebaSjsing break; 381e8d08ebaSjsing } 382e8d08ebaSjsing a += 4; 383e8d08ebaSjsing r += 4; 384e8d08ebaSjsing } 385e8d08ebaSjsing } 386e8d08ebaSjsing if (dl > 0) { 387e8d08ebaSjsing for (;;) { 388e8d08ebaSjsing r[0] = a[0]; 389e8d08ebaSjsing if (--dl <= 0) 390e8d08ebaSjsing break; 391e8d08ebaSjsing r[1] = a[1]; 392e8d08ebaSjsing if (--dl <= 0) 393e8d08ebaSjsing break; 394e8d08ebaSjsing r[2] = a[2]; 395e8d08ebaSjsing if (--dl <= 0) 396e8d08ebaSjsing break; 397e8d08ebaSjsing r[3] = a[3]; 398e8d08ebaSjsing if (--dl <= 0) 399e8d08ebaSjsing break; 400e8d08ebaSjsing 401e8d08ebaSjsing a += 4; 402e8d08ebaSjsing r += 4; 403e8d08ebaSjsing } 404e8d08ebaSjsing } 405e8d08ebaSjsing } 406e8d08ebaSjsing return c; 407e8d08ebaSjsing } 408e8d08ebaSjsing #endif 409e8d08ebaSjsing 410e8d08ebaSjsing void 411e8d08ebaSjsing bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 412e8d08ebaSjsing { 413e8d08ebaSjsing BN_ULONG *rr; 414e8d08ebaSjsing 415e8d08ebaSjsing 416e8d08ebaSjsing if (na < nb) { 417e8d08ebaSjsing int itmp; 418e8d08ebaSjsing BN_ULONG *ltmp; 419e8d08ebaSjsing 420e8d08ebaSjsing itmp = na; 421e8d08ebaSjsing na = nb; 422e8d08ebaSjsing nb = itmp; 423e8d08ebaSjsing ltmp = a; 424e8d08ebaSjsing a = b; 425e8d08ebaSjsing b = ltmp; 426e8d08ebaSjsing 427e8d08ebaSjsing } 428e8d08ebaSjsing rr = &(r[na]); 429e8d08ebaSjsing if (nb <= 0) { 430e8d08ebaSjsing (void)bn_mul_words(r, a, na, 0); 431e8d08ebaSjsing return; 432e8d08ebaSjsing } else 433e8d08ebaSjsing rr[0] = bn_mul_words(r, a, na, b[0]); 434e8d08ebaSjsing 435e8d08ebaSjsing for (;;) { 436e8d08ebaSjsing if (--nb <= 0) 437e8d08ebaSjsing return; 438e8d08ebaSjsing rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); 439e8d08ebaSjsing if (--nb <= 0) 440e8d08ebaSjsing return; 441e8d08ebaSjsing rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); 442e8d08ebaSjsing if (--nb <= 0) 443e8d08ebaSjsing return; 444e8d08ebaSjsing rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); 445e8d08ebaSjsing if (--nb <= 0) 446e8d08ebaSjsing return; 447e8d08ebaSjsing rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); 448e8d08ebaSjsing rr += 4; 449e8d08ebaSjsing r += 4; 450e8d08ebaSjsing b += 4; 451e8d08ebaSjsing } 452e8d08ebaSjsing } 453e8d08ebaSjsing 454913ec974Sbeck #ifdef BN_RECURSION 455f6e3f262Sbeck /* Karatsuba recursive multiplication algorithm 456f6e3f262Sbeck * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 457f6e3f262Sbeck 458913ec974Sbeck /* r is 2*n2 words in size, 459913ec974Sbeck * a and b are both n2 words in size. 460913ec974Sbeck * n2 must be a power of 2. 461913ec974Sbeck * We multiply and return the result. 462913ec974Sbeck * t must be 2*n2 words in size 463ba5406e9Sbeck * We calculate 464913ec974Sbeck * a[0]*b[0] 465913ec974Sbeck * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 466913ec974Sbeck * a[1]*b[1] 467913ec974Sbeck */ 4684fcf65c5Sdjm /* dnX may not be positive, but n2/2+dnX has to be */ 4692bd9bb84Sjsing void 4702bd9bb84Sjsing bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna, 4712bd9bb84Sjsing int dnb, BN_ULONG *t) 4725b37fcf3Sryker { 473913ec974Sbeck int n = n2 / 2, c1, c2; 4744fcf65c5Sdjm int tna = n + dna, tnb = n + dnb; 475913ec974Sbeck unsigned int neg, zero; 476913ec974Sbeck BN_ULONG ln, lo, *p; 4775b37fcf3Sryker 478913ec974Sbeck # ifdef BN_MUL_COMBA 479ba5406e9Sbeck # if 0 4802bd9bb84Sjsing if (n2 == 4) { 481913ec974Sbeck bn_mul_comba4(r, a, b); 482913ec974Sbeck return; 483913ec974Sbeck } 484ba5406e9Sbeck # endif 4854fcf65c5Sdjm /* Only call bn_mul_comba 8 if n2 == 8 and the 4864fcf65c5Sdjm * two arrays are complete [steve] 4874fcf65c5Sdjm */ 4882bd9bb84Sjsing if (n2 == 8 && dna == 0 && dnb == 0) { 489913ec974Sbeck bn_mul_comba8(r, a, b); 490913ec974Sbeck return; 491913ec974Sbeck } 492ba5406e9Sbeck # endif /* BN_MUL_COMBA */ 4934fcf65c5Sdjm /* Else do normal multiply */ 4942bd9bb84Sjsing if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { 4954fcf65c5Sdjm bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); 4964fcf65c5Sdjm if ((dna + dnb) < 0) 4974fcf65c5Sdjm memset(&r[2*n2 + dna + dnb], 0, 4984fcf65c5Sdjm sizeof(BN_ULONG) * -(dna + dnb)); 499913ec974Sbeck return; 500913ec974Sbeck } 501913ec974Sbeck /* r=(a[0]-a[1])*(b[1]-b[0]) */ 5024fcf65c5Sdjm c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 5034fcf65c5Sdjm c2 = bn_cmp_part_words(&(b[n]), b,tnb, tnb - n); 504913ec974Sbeck zero = neg = 0; 5052bd9bb84Sjsing switch (c1 * 3 + c2) { 506913ec974Sbeck case -4: 5074fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 5084fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 509913ec974Sbeck break; 510913ec974Sbeck case -3: 511913ec974Sbeck zero = 1; 512913ec974Sbeck break; 513913ec974Sbeck case -2: 5144fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 5154fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 516913ec974Sbeck neg = 1; 517913ec974Sbeck break; 518913ec974Sbeck case -1: 519913ec974Sbeck case 0: 520913ec974Sbeck case 1: 521913ec974Sbeck zero = 1; 522913ec974Sbeck break; 523913ec974Sbeck case 2: 5244fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 5254fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 526913ec974Sbeck neg = 1; 527913ec974Sbeck break; 528913ec974Sbeck case 3: 529913ec974Sbeck zero = 1; 530913ec974Sbeck break; 531913ec974Sbeck case 4: 5324fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 5334fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 534913ec974Sbeck break; 5355b37fcf3Sryker } 5365b37fcf3Sryker 537913ec974Sbeck # ifdef BN_MUL_COMBA 5384fcf65c5Sdjm if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take 5394fcf65c5Sdjm extra args to do this well */ 5405b37fcf3Sryker { 541913ec974Sbeck if (!zero) 542913ec974Sbeck bn_mul_comba4(&(t[n2]), t, &(t[n])); 543913ec974Sbeck else 544913ec974Sbeck memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG)); 545913ec974Sbeck 546913ec974Sbeck bn_mul_comba4(r, a, b); 547913ec974Sbeck bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); 5482bd9bb84Sjsing } else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could 5494fcf65c5Sdjm take extra args to do this 5504fcf65c5Sdjm well */ 551913ec974Sbeck { 552913ec974Sbeck if (!zero) 553913ec974Sbeck bn_mul_comba8(&(t[n2]), t, &(t[n])); 554913ec974Sbeck else 555913ec974Sbeck memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG)); 556913ec974Sbeck 557913ec974Sbeck bn_mul_comba8(r, a, b); 558913ec974Sbeck bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n])); 5592bd9bb84Sjsing } else 560ba5406e9Sbeck # endif /* BN_MUL_COMBA */ 561913ec974Sbeck { 562913ec974Sbeck p = &(t[n2 * 2]); 563913ec974Sbeck if (!zero) 5644fcf65c5Sdjm bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 565913ec974Sbeck else 566913ec974Sbeck memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); 5674fcf65c5Sdjm bn_mul_recursive(r, a, b, n, 0, 0, p); 5684fcf65c5Sdjm bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); 5695b37fcf3Sryker } 5705b37fcf3Sryker 571913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 572913ec974Sbeck * r[10] holds (a[0]*b[0]) 573913ec974Sbeck * r[32] holds (b[1]*b[1]) 574913ec974Sbeck */ 5755b37fcf3Sryker 576913ec974Sbeck c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 5775b37fcf3Sryker 578913ec974Sbeck if (neg) /* if t[32] is negative */ 5795b37fcf3Sryker { 580913ec974Sbeck c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 5812bd9bb84Sjsing } else { 582913ec974Sbeck /* Might have a carry */ 583913ec974Sbeck c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 5845b37fcf3Sryker } 5855b37fcf3Sryker 586913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 587913ec974Sbeck * r[10] holds (a[0]*b[0]) 588913ec974Sbeck * r[32] holds (b[1]*b[1]) 589913ec974Sbeck * c1 holds the carry bits 590913ec974Sbeck */ 591913ec974Sbeck c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 5922bd9bb84Sjsing if (c1) { 593913ec974Sbeck p = &(r[n + n2]); 594913ec974Sbeck lo= *p; 595913ec974Sbeck ln = (lo + c1) & BN_MASK2; 596913ec974Sbeck *p = ln; 597913ec974Sbeck 598913ec974Sbeck /* The overflow will stop before we over write 599913ec974Sbeck * words we should not overwrite */ 6002bd9bb84Sjsing if (ln < (BN_ULONG)c1) { 601913ec974Sbeck do { 602913ec974Sbeck p++; 603913ec974Sbeck lo= *p; 604913ec974Sbeck ln = (lo + 1) & BN_MASK2; 605913ec974Sbeck *p = ln; 606913ec974Sbeck } while (ln == 0); 607913ec974Sbeck } 608913ec974Sbeck } 6095b37fcf3Sryker } 6105b37fcf3Sryker 611913ec974Sbeck /* n+tn is the word length 612913ec974Sbeck * t needs to be n*4 is size, as does r */ 6134fcf65c5Sdjm /* tnX may not be negative but less than n */ 6142bd9bb84Sjsing void 6152bd9bb84Sjsing bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna, 6162bd9bb84Sjsing int tnb, BN_ULONG *t) 6175b37fcf3Sryker { 618913ec974Sbeck int i, j, n2 = n * 2; 619c32db552Sdjm int c1, c2, neg; 620913ec974Sbeck BN_ULONG ln, lo, *p; 6215b37fcf3Sryker 6222bd9bb84Sjsing if (n < 8) { 6234fcf65c5Sdjm bn_mul_normal(r, a, n + tna, b, n + tnb); 624913ec974Sbeck return; 6255b37fcf3Sryker } 6265b37fcf3Sryker 627913ec974Sbeck /* r=(a[0]-a[1])*(b[1]-b[0]) */ 6284fcf65c5Sdjm c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 6294fcf65c5Sdjm c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 630c32db552Sdjm neg = 0; 6312bd9bb84Sjsing switch (c1 * 3 + c2) { 632ba5406e9Sbeck case -4: 6334fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 6344fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 635ba5406e9Sbeck break; 636ba5406e9Sbeck case -3: 637ba5406e9Sbeck /* break; */ 638ba5406e9Sbeck case -2: 6394fcf65c5Sdjm bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 6404fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 641ba5406e9Sbeck neg = 1; 642ba5406e9Sbeck break; 643ba5406e9Sbeck case -1: 644ba5406e9Sbeck case 0: 645ba5406e9Sbeck case 1: 646ba5406e9Sbeck /* break; */ 647ba5406e9Sbeck case 2: 6484fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 6494fcf65c5Sdjm bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 650ba5406e9Sbeck neg = 1; 651ba5406e9Sbeck break; 652ba5406e9Sbeck case 3: 653ba5406e9Sbeck /* break; */ 654ba5406e9Sbeck case 4: 6554fcf65c5Sdjm bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 6564fcf65c5Sdjm bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 657ba5406e9Sbeck break; 658ba5406e9Sbeck } 659ba5406e9Sbeck /* The zero case isn't yet implemented here. The speedup 660ba5406e9Sbeck would probably be negligible. */ 661ba5406e9Sbeck # if 0 6622bd9bb84Sjsing if (n == 4) { 663913ec974Sbeck bn_mul_comba4(&(t[n2]), t, &(t[n])); 664913ec974Sbeck bn_mul_comba4(r, a, b); 665913ec974Sbeck bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn); 666913ec974Sbeck memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2)); 6672bd9bb84Sjsing } else 668ba5406e9Sbeck # endif 6692bd9bb84Sjsing if (n == 8) { 670913ec974Sbeck bn_mul_comba8(&(t[n2]), t, &(t[n])); 671913ec974Sbeck bn_mul_comba8(r, a, b); 6724fcf65c5Sdjm bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 6732bd9bb84Sjsing memset(&(r[n2 + tna + tnb]), 0, 6742bd9bb84Sjsing sizeof(BN_ULONG) * (n2 - tna - tnb)); 6752bd9bb84Sjsing } else { 676913ec974Sbeck p = &(t[n2*2]); 6774fcf65c5Sdjm bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 6784fcf65c5Sdjm bn_mul_recursive(r, a, b, n, 0, 0, p); 679913ec974Sbeck i = n / 2; 680913ec974Sbeck /* If there is only a bottom half to the number, 681913ec974Sbeck * just do it */ 6824fcf65c5Sdjm if (tna > tnb) 6834fcf65c5Sdjm j = tna - i; 6844fcf65c5Sdjm else 6854fcf65c5Sdjm j = tnb - i; 6862bd9bb84Sjsing if (j == 0) { 6874fcf65c5Sdjm bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), 6884fcf65c5Sdjm i, tna - i, tnb - i, p); 6892bd9bb84Sjsing memset(&(r[n2 + i * 2]), 0, 6902bd9bb84Sjsing sizeof(BN_ULONG) * (n2 - i * 2)); 691913ec974Sbeck } 692913ec974Sbeck else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ 693913ec974Sbeck { 694913ec974Sbeck bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), 6954fcf65c5Sdjm i, tna - i, tnb - i, p); 6964fcf65c5Sdjm memset(&(r[n2 + tna + tnb]), 0, 6974fcf65c5Sdjm sizeof(BN_ULONG) * (n2 - tna - tnb)); 698913ec974Sbeck } 699913ec974Sbeck else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 700913ec974Sbeck { 701913ec974Sbeck memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2); 7022bd9bb84Sjsing if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL && 7032bd9bb84Sjsing tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { 7042bd9bb84Sjsing bn_mul_normal(&(r[n2]), &(a[n]), tna, 7052bd9bb84Sjsing &(b[n]), tnb); 7062bd9bb84Sjsing } else { 7072bd9bb84Sjsing for (;;) { 708913ec974Sbeck i /= 2; 7094fcf65c5Sdjm /* these simplified conditions work 7104fcf65c5Sdjm * exclusively because difference 7114fcf65c5Sdjm * between tna and tnb is 1 or 0 */ 7122bd9bb84Sjsing if (i < tna || i < tnb) { 713913ec974Sbeck bn_mul_part_recursive(&(r[n2]), 7142bd9bb84Sjsing &(a[n]), &(b[n]), i, 7152bd9bb84Sjsing tna - i, tnb - i, p); 716913ec974Sbeck break; 7172bd9bb84Sjsing } else if (i == tna || i == tnb) { 718913ec974Sbeck bn_mul_recursive(&(r[n2]), 7192bd9bb84Sjsing &(a[n]), &(b[n]), i, 7202bd9bb84Sjsing tna - i, tnb - i, p); 721913ec974Sbeck break; 722913ec974Sbeck } 723913ec974Sbeck } 724913ec974Sbeck } 725913ec974Sbeck } 7265b37fcf3Sryker } 7275b37fcf3Sryker 728913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 729913ec974Sbeck * r[10] holds (a[0]*b[0]) 730913ec974Sbeck * r[32] holds (b[1]*b[1]) 731913ec974Sbeck */ 7325b37fcf3Sryker 733913ec974Sbeck c1 = (int)(bn_add_words(t, r,&(r[n2]), n2)); 734ba5406e9Sbeck 735ba5406e9Sbeck if (neg) /* if t[32] is negative */ 736ba5406e9Sbeck { 737913ec974Sbeck c1 -= (int)(bn_sub_words(&(t[n2]), t,&(t[n2]), n2)); 7382bd9bb84Sjsing } else { 739ba5406e9Sbeck /* Might have a carry */ 740ba5406e9Sbeck c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 741ba5406e9Sbeck } 7425b37fcf3Sryker 743913ec974Sbeck /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 744913ec974Sbeck * r[10] holds (a[0]*b[0]) 745913ec974Sbeck * r[32] holds (b[1]*b[1]) 746913ec974Sbeck * c1 holds the carry bits 747913ec974Sbeck */ 748913ec974Sbeck c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 7492bd9bb84Sjsing if (c1) { 750913ec974Sbeck p = &(r[n + n2]); 751913ec974Sbeck lo= *p; 752913ec974Sbeck ln = (lo + c1)&BN_MASK2; 753913ec974Sbeck *p = ln; 7545b37fcf3Sryker 755913ec974Sbeck /* The overflow will stop before we over write 756913ec974Sbeck * words we should not overwrite */ 7572bd9bb84Sjsing if (ln < (BN_ULONG)c1) { 758913ec974Sbeck do { 759913ec974Sbeck p++; 760913ec974Sbeck lo= *p; 761913ec974Sbeck ln = (lo + 1) & BN_MASK2; 762913ec974Sbeck *p = ln; 763913ec974Sbeck } while (ln == 0); 764913ec974Sbeck } 765913ec974Sbeck } 766913ec974Sbeck } 767ba5406e9Sbeck #endif /* BN_RECURSION */ 768913ec974Sbeck 7699554b5edSjsing #ifndef HAVE_BN_MUL 7709554b5edSjsing #ifndef BN_RECURSION 7712bd9bb84Sjsing int 7729554b5edSjsing bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx) 773913ec974Sbeck { 7749554b5edSjsing bn_mul_normal(r->d, a->d, a->top, b->d, b->top); 7759554b5edSjsing 7769554b5edSjsing return 1; 7779554b5edSjsing } 7789554b5edSjsing 7799554b5edSjsing #else /* BN_RECURSION */ 7809554b5edSjsing int 7819554b5edSjsing bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx) 7829554b5edSjsing { 7834fcf65c5Sdjm BIGNUM *t = NULL; 7849554b5edSjsing int al, bl, i, k; 7859554b5edSjsing int j = 0; 7869554b5edSjsing int ret = 0; 787913ec974Sbeck 7889554b5edSjsing BN_CTX_start(ctx); 789913ec974Sbeck 790913ec974Sbeck al = a->top; 791913ec974Sbeck bl = b->top; 792913ec974Sbeck 793ba5406e9Sbeck i = al - bl; 7949554b5edSjsing 7952bd9bb84Sjsing if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { 7962bd9bb84Sjsing if (i >= -1 && i <= 1) { 7974fcf65c5Sdjm /* Find out the power of two lower or equal 7984fcf65c5Sdjm to the longest of the two numbers */ 7992bd9bb84Sjsing if (i >= 0) { 8004fcf65c5Sdjm j = BN_num_bits_word((BN_ULONG)al); 8014fcf65c5Sdjm } 8022bd9bb84Sjsing if (i == -1) { 8034fcf65c5Sdjm j = BN_num_bits_word((BN_ULONG)bl); 8044fcf65c5Sdjm } 8054fcf65c5Sdjm j = 1 << (j - 1); 8064fcf65c5Sdjm assert(j <= al || j <= bl); 8074fcf65c5Sdjm k = j + j; 808aa389b8cSjsing if ((t = BN_CTX_get(ctx)) == NULL) 8090a5d6edeSdjm goto err; 8102bd9bb84Sjsing if (al > j || bl > j) { 811e729bd5aSjsing if (!bn_wexpand(t, k * 4)) 8122bd9bb84Sjsing goto err; 8139554b5edSjsing if (!bn_wexpand(r, k * 4)) 8142bd9bb84Sjsing goto err; 8159554b5edSjsing bn_mul_part_recursive(r->d, a->d, b->d, 8164fcf65c5Sdjm j, al - j, bl - j, t->d); 8174fcf65c5Sdjm } 8184fcf65c5Sdjm else /* al <= j || bl <= j */ 8194fcf65c5Sdjm { 820e729bd5aSjsing if (!bn_wexpand(t, k * 2)) 8212bd9bb84Sjsing goto err; 8229554b5edSjsing if (!bn_wexpand(r, k * 2)) 8232bd9bb84Sjsing goto err; 8249554b5edSjsing bn_mul_recursive(r->d, a->d, b->d, 8254fcf65c5Sdjm j, al - j, bl - j, t->d); 8264fcf65c5Sdjm } 8279554b5edSjsing r->top = rn; 8284fcf65c5Sdjm goto end; 8294fcf65c5Sdjm } 8304fcf65c5Sdjm #if 0 8312bd9bb84Sjsing if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) { 8324fcf65c5Sdjm BIGNUM *tmp_bn = (BIGNUM *)b; 833e729bd5aSjsing if (!bn_wexpand(tmp_bn, al)) 8342bd9bb84Sjsing goto err; 8354fcf65c5Sdjm tmp_bn->d[bl] = 0; 836913ec974Sbeck bl++; 837ba5406e9Sbeck i--; 8382bd9bb84Sjsing } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) { 8394fcf65c5Sdjm BIGNUM *tmp_bn = (BIGNUM *)a; 840e729bd5aSjsing if (!bn_wexpand(tmp_bn, bl)) 8412bd9bb84Sjsing goto err; 8424fcf65c5Sdjm tmp_bn->d[al] = 0; 843913ec974Sbeck al++; 844ba5406e9Sbeck i++; 845913ec974Sbeck } 8462bd9bb84Sjsing if (i == 0) { 847ba5406e9Sbeck /* symmetric and > 4 */ 848913ec974Sbeck /* 16 or larger */ 849913ec974Sbeck j = BN_num_bits_word((BN_ULONG)al); 850913ec974Sbeck j = 1 << (j - 1); 851913ec974Sbeck k = j + j; 852aa389b8cSjsing if ((t = BN_CTX_get(ctx)) == NULL) 853aa389b8cSjsing goto err; 854913ec974Sbeck if (al == j) /* exact multiple */ 855913ec974Sbeck { 856e729bd5aSjsing if (!bn_wexpand(t, k * 2)) 8572bd9bb84Sjsing goto err; 8589554b5edSjsing if (!bn_wexpand(r, k * 2)) 8592bd9bb84Sjsing goto err; 8609554b5edSjsing bn_mul_recursive(r->d, a->d, b->d, al, t->d); 8612bd9bb84Sjsing } else { 862e729bd5aSjsing if (!bn_wexpand(t, k * 4)) 8632bd9bb84Sjsing goto err; 8649554b5edSjsing if (!bn_wexpand(r, k * 4)) 8652bd9bb84Sjsing goto err; 8669554b5edSjsing bn_mul_part_recursive(r->d, a->d, b->d, 8672bd9bb84Sjsing al - j, j, t->d); 868913ec974Sbeck } 8699554b5edSjsing r->top = top; 870ba5406e9Sbeck goto end; 871ba5406e9Sbeck } 8724fcf65c5Sdjm #endif 873767fe2ffSmarkus } 874ba5406e9Sbeck 8759554b5edSjsing bn_mul_normal(r->d, a->d, al, b->d, bl); 8769554b5edSjsing 877913ec974Sbeck end: 878ba5406e9Sbeck ret = 1; 879ba5406e9Sbeck err: 880ba5406e9Sbeck BN_CTX_end(ctx); 8819554b5edSjsing 8829554b5edSjsing return ret; 8839554b5edSjsing } 8849554b5edSjsing #endif /* BN_RECURSION */ 8859554b5edSjsing #endif /* HAVE_BN_MUL */ 8869554b5edSjsing 8879554b5edSjsing int 8889554b5edSjsing BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 8899554b5edSjsing { 8909554b5edSjsing BIGNUM *rr; 8919554b5edSjsing int rn; 8929554b5edSjsing int ret = 0; 8939554b5edSjsing 8949554b5edSjsing BN_CTX_start(ctx); 8959554b5edSjsing 8969554b5edSjsing if (BN_is_zero(a) || BN_is_zero(b)) { 8979554b5edSjsing BN_zero(r); 8989554b5edSjsing goto done; 8999554b5edSjsing } 9009554b5edSjsing 9019554b5edSjsing rr = r; 9029554b5edSjsing if (rr == a || rr == b) 9039554b5edSjsing rr = BN_CTX_get(ctx); 9049554b5edSjsing if (rr == NULL) 9059554b5edSjsing goto err; 9069554b5edSjsing 9079554b5edSjsing rn = a->top + b->top; 9089554b5edSjsing if (rn < a->top) 9099554b5edSjsing goto err; 9109554b5edSjsing if (!bn_wexpand(rr, rn)) 9119554b5edSjsing goto err; 9129554b5edSjsing 9139554b5edSjsing if (a->top == 4 && b->top == 4) { 9149554b5edSjsing bn_mul_comba4(rr->d, a->d, b->d); 9159554b5edSjsing } else if (a->top == 8 && b->top == 8) { 9169554b5edSjsing bn_mul_comba8(rr->d, a->d, b->d); 9179554b5edSjsing } else { 9189554b5edSjsing if (!bn_mul(rr, a, b, rn, ctx)) 9199554b5edSjsing goto err; 9209554b5edSjsing } 9219554b5edSjsing 9229554b5edSjsing rr->top = rn; 9239554b5edSjsing bn_correct_top(rr); 9249554b5edSjsing 925896da13fSjsing BN_set_negative(rr, a->neg ^ b->neg); 926896da13fSjsing 9279554b5edSjsing if (r != rr) 9289554b5edSjsing BN_copy(r, rr); 9299554b5edSjsing done: 9309554b5edSjsing ret = 1; 9319554b5edSjsing err: 9329554b5edSjsing BN_CTX_end(ctx); 9339554b5edSjsing 9349554b5edSjsing return ret; 935913ec974Sbeck } 936