bn_mul.c revision 194206
155714Skris/* crypto/bn/bn_mul.c */ 255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 355714Skris * All rights reserved. 455714Skris * 555714Skris * This package is an SSL implementation written 655714Skris * by Eric Young (eay@cryptsoft.com). 755714Skris * The implementation was written so as to conform with Netscapes SSL. 855714Skris * 955714Skris * This library is free for commercial and non-commercial use as long as 1055714Skris * the following conditions are aheared to. The following conditions 1155714Skris * apply to all code found in this distribution, be it the RC4, RSA, 1255714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1355714Skris * included with this distribution is covered by the same copyright terms 1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1555714Skris * 1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1755714Skris * the code are not to be removed. 1855714Skris * If this package is used in a product, Eric Young should be given attribution 1955714Skris * as the author of the parts of the library used. 2055714Skris * This can be in the form of a textual message at program startup or 2155714Skris * in documentation (online or textual) provided with the package. 2255714Skris * 2355714Skris * Redistribution and use in source and binary forms, with or without 2455714Skris * modification, are permitted provided that the following conditions 2555714Skris * are met: 2655714Skris * 1. Redistributions of source code must retain the copyright 2755714Skris * notice, this list of conditions and the following disclaimer. 2855714Skris * 2. Redistributions in binary form must reproduce the above copyright 2955714Skris * notice, this list of conditions and the following disclaimer in the 3055714Skris * documentation and/or other materials provided with the distribution. 3155714Skris * 3. All advertising materials mentioning features or use of this software 3255714Skris * must display the following acknowledgement: 3355714Skris * "This product includes cryptographic software written by 3455714Skris * Eric Young (eay@cryptsoft.com)" 3555714Skris * The word 'cryptographic' can be left out if the rouines from the library 3655714Skris * being used are not cryptographic related :-). 3755714Skris * 4. If you include any Windows specific code (or a derivative thereof) from 3855714Skris * the apps directory (application code) you must include an acknowledgement: 3955714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4055714Skris * 4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4455714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5155714Skris * SUCH DAMAGE. 5255714Skris * 5355714Skris * The licence and distribution terms for any publically available version or 5455714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5555714Skris * copied and put under another distribution licence 5655714Skris * [including the GNU Public Licence.] 5755714Skris */ 5855714Skris 59160814Ssimon#ifndef BN_DEBUG 60160814Ssimon# undef NDEBUG /* avoid conflicting definitions */ 61160814Ssimon# define NDEBUG 62160814Ssimon#endif 63160814Ssimon 6455714Skris#include <stdio.h> 65160814Ssimon#include <assert.h> 6655714Skris#include "cryptlib.h" 6755714Skris#include "bn_lcl.h" 6855714Skris 69160814Ssimon#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) 70160814Ssimon/* Here follows specialised variants of bn_add_words() and 71160814Ssimon bn_sub_words(). They have the property performing operations on 72160814Ssimon arrays of different sizes. The sizes of those arrays is expressed through 73160814Ssimon cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl, 74160814Ssimon which is the delta between the two lengths, calculated as len(a)-len(b). 75160814Ssimon All lengths are the number of BN_ULONGs... For the operations that require 76160814Ssimon a result array as parameter, it must have the length cl+abs(dl). 77160814Ssimon These functions should probably end up in bn_asm.c as soon as there are 78160814Ssimon assembler counterparts for the systems that use assembler files. */ 79160814Ssimon 80160814SsimonBN_ULONG bn_sub_part_words(BN_ULONG *r, 81160814Ssimon const BN_ULONG *a, const BN_ULONG *b, 82160814Ssimon int cl, int dl) 83160814Ssimon { 84160814Ssimon BN_ULONG c, t; 85160814Ssimon 86160814Ssimon assert(cl >= 0); 87160814Ssimon c = bn_sub_words(r, a, b, cl); 88160814Ssimon 89160814Ssimon if (dl == 0) 90160814Ssimon return c; 91160814Ssimon 92160814Ssimon r += cl; 93160814Ssimon a += cl; 94160814Ssimon b += cl; 95160814Ssimon 96160814Ssimon if (dl < 0) 97160814Ssimon { 98160814Ssimon#ifdef BN_COUNT 99160814Ssimon fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); 100160814Ssimon#endif 101160814Ssimon for (;;) 102160814Ssimon { 103160814Ssimon t = b[0]; 104160814Ssimon r[0] = (0-t-c)&BN_MASK2; 105160814Ssimon if (t != 0) c=1; 106160814Ssimon if (++dl >= 0) break; 107160814Ssimon 108160814Ssimon t = b[1]; 109160814Ssimon r[1] = (0-t-c)&BN_MASK2; 110160814Ssimon if (t != 0) c=1; 111160814Ssimon if (++dl >= 0) break; 112160814Ssimon 113160814Ssimon t = b[2]; 114160814Ssimon r[2] = (0-t-c)&BN_MASK2; 115160814Ssimon if (t != 0) c=1; 116160814Ssimon if (++dl >= 0) break; 117160814Ssimon 118160814Ssimon t = b[3]; 119160814Ssimon r[3] = (0-t-c)&BN_MASK2; 120160814Ssimon if (t != 0) c=1; 121160814Ssimon if (++dl >= 0) break; 122160814Ssimon 123160814Ssimon b += 4; 124160814Ssimon r += 4; 125160814Ssimon } 126160814Ssimon } 127160814Ssimon else 128160814Ssimon { 129160814Ssimon int save_dl = dl; 130160814Ssimon#ifdef BN_COUNT 131160814Ssimon fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c); 132160814Ssimon#endif 133160814Ssimon while(c) 134160814Ssimon { 135160814Ssimon t = a[0]; 136160814Ssimon r[0] = (t-c)&BN_MASK2; 137160814Ssimon if (t != 0) c=0; 138160814Ssimon if (--dl <= 0) break; 139160814Ssimon 140160814Ssimon t = a[1]; 141160814Ssimon r[1] = (t-c)&BN_MASK2; 142160814Ssimon if (t != 0) c=0; 143160814Ssimon if (--dl <= 0) break; 144160814Ssimon 145160814Ssimon t = a[2]; 146160814Ssimon r[2] = (t-c)&BN_MASK2; 147160814Ssimon if (t != 0) c=0; 148160814Ssimon if (--dl <= 0) break; 149160814Ssimon 150160814Ssimon t = a[3]; 151160814Ssimon r[3] = (t-c)&BN_MASK2; 152160814Ssimon if (t != 0) c=0; 153160814Ssimon if (--dl <= 0) break; 154160814Ssimon 155160814Ssimon save_dl = dl; 156160814Ssimon a += 4; 157160814Ssimon r += 4; 158160814Ssimon } 159160814Ssimon if (dl > 0) 160160814Ssimon { 161160814Ssimon#ifdef BN_COUNT 162160814Ssimon fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); 163160814Ssimon#endif 164160814Ssimon if (save_dl > dl) 165160814Ssimon { 166160814Ssimon switch (save_dl - dl) 167160814Ssimon { 168160814Ssimon case 1: 169160814Ssimon r[1] = a[1]; 170160814Ssimon if (--dl <= 0) break; 171160814Ssimon case 2: 172160814Ssimon r[2] = a[2]; 173160814Ssimon if (--dl <= 0) break; 174160814Ssimon case 3: 175160814Ssimon r[3] = a[3]; 176160814Ssimon if (--dl <= 0) break; 177160814Ssimon } 178160814Ssimon a += 4; 179160814Ssimon r += 4; 180160814Ssimon } 181160814Ssimon } 182160814Ssimon if (dl > 0) 183160814Ssimon { 184160814Ssimon#ifdef BN_COUNT 185160814Ssimon fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl); 186160814Ssimon#endif 187160814Ssimon for(;;) 188160814Ssimon { 189160814Ssimon r[0] = a[0]; 190160814Ssimon if (--dl <= 0) break; 191160814Ssimon r[1] = a[1]; 192160814Ssimon if (--dl <= 0) break; 193160814Ssimon r[2] = a[2]; 194160814Ssimon if (--dl <= 0) break; 195160814Ssimon r[3] = a[3]; 196160814Ssimon if (--dl <= 0) break; 197160814Ssimon 198160814Ssimon a += 4; 199160814Ssimon r += 4; 200160814Ssimon } 201160814Ssimon } 202160814Ssimon } 203160814Ssimon return c; 204160814Ssimon } 205160814Ssimon#endif 206160814Ssimon 207160814SsimonBN_ULONG bn_add_part_words(BN_ULONG *r, 208160814Ssimon const BN_ULONG *a, const BN_ULONG *b, 209160814Ssimon int cl, int dl) 210160814Ssimon { 211160814Ssimon BN_ULONG c, l, t; 212160814Ssimon 213160814Ssimon assert(cl >= 0); 214160814Ssimon c = bn_add_words(r, a, b, cl); 215160814Ssimon 216160814Ssimon if (dl == 0) 217160814Ssimon return c; 218160814Ssimon 219160814Ssimon r += cl; 220160814Ssimon a += cl; 221160814Ssimon b += cl; 222160814Ssimon 223160814Ssimon if (dl < 0) 224160814Ssimon { 225160814Ssimon int save_dl = dl; 226160814Ssimon#ifdef BN_COUNT 227160814Ssimon fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); 228160814Ssimon#endif 229160814Ssimon while (c) 230160814Ssimon { 231160814Ssimon l=(c+b[0])&BN_MASK2; 232160814Ssimon c=(l < c); 233160814Ssimon r[0]=l; 234160814Ssimon if (++dl >= 0) break; 235160814Ssimon 236160814Ssimon l=(c+b[1])&BN_MASK2; 237160814Ssimon c=(l < c); 238160814Ssimon r[1]=l; 239160814Ssimon if (++dl >= 0) break; 240160814Ssimon 241160814Ssimon l=(c+b[2])&BN_MASK2; 242160814Ssimon c=(l < c); 243160814Ssimon r[2]=l; 244160814Ssimon if (++dl >= 0) break; 245160814Ssimon 246160814Ssimon l=(c+b[3])&BN_MASK2; 247160814Ssimon c=(l < c); 248160814Ssimon r[3]=l; 249160814Ssimon if (++dl >= 0) break; 250160814Ssimon 251160814Ssimon save_dl = dl; 252160814Ssimon b+=4; 253160814Ssimon r+=4; 254160814Ssimon } 255160814Ssimon if (dl < 0) 256160814Ssimon { 257160814Ssimon#ifdef BN_COUNT 258160814Ssimon fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl); 259160814Ssimon#endif 260160814Ssimon if (save_dl < dl) 261160814Ssimon { 262160814Ssimon switch (dl - save_dl) 263160814Ssimon { 264160814Ssimon case 1: 265160814Ssimon r[1] = b[1]; 266160814Ssimon if (++dl >= 0) break; 267160814Ssimon case 2: 268160814Ssimon r[2] = b[2]; 269160814Ssimon if (++dl >= 0) break; 270160814Ssimon case 3: 271160814Ssimon r[3] = b[3]; 272160814Ssimon if (++dl >= 0) break; 273160814Ssimon } 274160814Ssimon b += 4; 275160814Ssimon r += 4; 276160814Ssimon } 277160814Ssimon } 278160814Ssimon if (dl < 0) 279160814Ssimon { 280160814Ssimon#ifdef BN_COUNT 281160814Ssimon fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl); 282160814Ssimon#endif 283160814Ssimon for(;;) 284160814Ssimon { 285160814Ssimon r[0] = b[0]; 286160814Ssimon if (++dl >= 0) break; 287160814Ssimon r[1] = b[1]; 288160814Ssimon if (++dl >= 0) break; 289160814Ssimon r[2] = b[2]; 290160814Ssimon if (++dl >= 0) break; 291160814Ssimon r[3] = b[3]; 292160814Ssimon if (++dl >= 0) break; 293160814Ssimon 294160814Ssimon b += 4; 295160814Ssimon r += 4; 296160814Ssimon } 297160814Ssimon } 298160814Ssimon } 299160814Ssimon else 300160814Ssimon { 301160814Ssimon int save_dl = dl; 302160814Ssimon#ifdef BN_COUNT 303160814Ssimon fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); 304160814Ssimon#endif 305160814Ssimon while (c) 306160814Ssimon { 307160814Ssimon t=(a[0]+c)&BN_MASK2; 308160814Ssimon c=(t < c); 309160814Ssimon r[0]=t; 310160814Ssimon if (--dl <= 0) break; 311160814Ssimon 312160814Ssimon t=(a[1]+c)&BN_MASK2; 313160814Ssimon c=(t < c); 314160814Ssimon r[1]=t; 315160814Ssimon if (--dl <= 0) break; 316160814Ssimon 317160814Ssimon t=(a[2]+c)&BN_MASK2; 318160814Ssimon c=(t < c); 319160814Ssimon r[2]=t; 320160814Ssimon if (--dl <= 0) break; 321160814Ssimon 322160814Ssimon t=(a[3]+c)&BN_MASK2; 323160814Ssimon c=(t < c); 324160814Ssimon r[3]=t; 325160814Ssimon if (--dl <= 0) break; 326160814Ssimon 327160814Ssimon save_dl = dl; 328160814Ssimon a+=4; 329160814Ssimon r+=4; 330160814Ssimon } 331160814Ssimon#ifdef BN_COUNT 332160814Ssimon fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); 333160814Ssimon#endif 334160814Ssimon if (dl > 0) 335160814Ssimon { 336160814Ssimon if (save_dl > dl) 337160814Ssimon { 338160814Ssimon switch (save_dl - dl) 339160814Ssimon { 340160814Ssimon case 1: 341160814Ssimon r[1] = a[1]; 342160814Ssimon if (--dl <= 0) break; 343160814Ssimon case 2: 344160814Ssimon r[2] = a[2]; 345160814Ssimon if (--dl <= 0) break; 346160814Ssimon case 3: 347160814Ssimon r[3] = a[3]; 348160814Ssimon if (--dl <= 0) break; 349160814Ssimon } 350160814Ssimon a += 4; 351160814Ssimon r += 4; 352160814Ssimon } 353160814Ssimon } 354160814Ssimon if (dl > 0) 355160814Ssimon { 356160814Ssimon#ifdef BN_COUNT 357160814Ssimon fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl); 358160814Ssimon#endif 359160814Ssimon for(;;) 360160814Ssimon { 361160814Ssimon r[0] = a[0]; 362160814Ssimon if (--dl <= 0) break; 363160814Ssimon r[1] = a[1]; 364160814Ssimon if (--dl <= 0) break; 365160814Ssimon r[2] = a[2]; 366160814Ssimon if (--dl <= 0) break; 367160814Ssimon r[3] = a[3]; 368160814Ssimon if (--dl <= 0) break; 369160814Ssimon 370160814Ssimon a += 4; 371160814Ssimon r += 4; 372160814Ssimon } 373160814Ssimon } 374160814Ssimon } 375160814Ssimon return c; 376160814Ssimon } 377160814Ssimon 37855714Skris#ifdef BN_RECURSION 37959191Skris/* Karatsuba recursive multiplication algorithm 38059191Skris * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 38159191Skris 38255714Skris/* r is 2*n2 words in size, 38355714Skris * a and b are both n2 words in size. 38455714Skris * n2 must be a power of 2. 38555714Skris * We multiply and return the result. 38655714Skris * t must be 2*n2 words in size 38759191Skris * We calculate 38855714Skris * a[0]*b[0] 38955714Skris * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 39055714Skris * a[1]*b[1] 39155714Skris */ 392194206Ssimon/* dnX may not be positive, but n2/2+dnX has to be */ 39355714Skrisvoid bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 394160814Ssimon int dna, int dnb, BN_ULONG *t) 39555714Skris { 39655714Skris int n=n2/2,c1,c2; 397160814Ssimon int tna=n+dna, tnb=n+dnb; 39855714Skris unsigned int neg,zero; 39955714Skris BN_ULONG ln,lo,*p; 40055714Skris 40159191Skris# ifdef BN_COUNT 402194206Ssimon fprintf(stderr," bn_mul_recursive %d%+d * %d%+d\n",n2,dna,n2,dnb); 40359191Skris# endif 40459191Skris# ifdef BN_MUL_COMBA 40559191Skris# if 0 40659191Skris if (n2 == 4) 40755714Skris { 40855714Skris bn_mul_comba4(r,a,b); 40955714Skris return; 41055714Skris } 41159191Skris# endif 412160814Ssimon /* Only call bn_mul_comba 8 if n2 == 8 and the 413160814Ssimon * two arrays are complete [steve] 414160814Ssimon */ 415160814Ssimon if (n2 == 8 && dna == 0 && dnb == 0) 41655714Skris { 41755714Skris bn_mul_comba8(r,a,b); 41855714Skris return; 41955714Skris } 42059191Skris# endif /* BN_MUL_COMBA */ 421160814Ssimon /* Else do normal multiply */ 42255714Skris if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) 42355714Skris { 424160814Ssimon bn_mul_normal(r,a,n2+dna,b,n2+dnb); 425160814Ssimon if ((dna + dnb) < 0) 426160814Ssimon memset(&r[2*n2 + dna + dnb], 0, 427160814Ssimon sizeof(BN_ULONG) * -(dna + dnb)); 42855714Skris return; 42955714Skris } 43055714Skris /* r=(a[0]-a[1])*(b[1]-b[0]) */ 431160814Ssimon c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); 432160814Ssimon c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); 43355714Skris zero=neg=0; 43455714Skris switch (c1*3+c2) 43555714Skris { 43655714Skris case -4: 437160814Ssimon bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 438160814Ssimon bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 43955714Skris break; 44055714Skris case -3: 44155714Skris zero=1; 44255714Skris break; 44355714Skris case -2: 444160814Ssimon bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 445160814Ssimon bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ 44655714Skris neg=1; 44755714Skris break; 44855714Skris case -1: 44955714Skris case 0: 45055714Skris case 1: 45155714Skris zero=1; 45255714Skris break; 45355714Skris case 2: 454160814Ssimon bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ 455160814Ssimon bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 45655714Skris neg=1; 45755714Skris break; 45855714Skris case 3: 45955714Skris zero=1; 46055714Skris break; 46155714Skris case 4: 462160814Ssimon bn_sub_part_words(t, a, &(a[n]),tna,n-tna); 463160814Ssimon bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); 46455714Skris break; 46555714Skris } 46655714Skris 46759191Skris# ifdef BN_MUL_COMBA 468160814Ssimon if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take 469160814Ssimon extra args to do this well */ 47055714Skris { 47155714Skris if (!zero) 47255714Skris bn_mul_comba4(&(t[n2]),t,&(t[n])); 47355714Skris else 47455714Skris memset(&(t[n2]),0,8*sizeof(BN_ULONG)); 47555714Skris 47655714Skris bn_mul_comba4(r,a,b); 47755714Skris bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n])); 47855714Skris } 479160814Ssimon else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could 480160814Ssimon take extra args to do this 481160814Ssimon well */ 48255714Skris { 48355714Skris if (!zero) 48455714Skris bn_mul_comba8(&(t[n2]),t,&(t[n])); 48555714Skris else 48655714Skris memset(&(t[n2]),0,16*sizeof(BN_ULONG)); 48755714Skris 48855714Skris bn_mul_comba8(r,a,b); 48955714Skris bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n])); 49055714Skris } 49155714Skris else 49259191Skris# endif /* BN_MUL_COMBA */ 49355714Skris { 49455714Skris p= &(t[n2*2]); 49555714Skris if (!zero) 496160814Ssimon bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); 49755714Skris else 49855714Skris memset(&(t[n2]),0,n2*sizeof(BN_ULONG)); 499160814Ssimon bn_mul_recursive(r,a,b,n,0,0,p); 500160814Ssimon bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,dna,dnb,p); 50155714Skris } 50255714Skris 50355714Skris /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 50455714Skris * r[10] holds (a[0]*b[0]) 50555714Skris * r[32] holds (b[1]*b[1]) 50655714Skris */ 50755714Skris 50855714Skris c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); 50955714Skris 51055714Skris if (neg) /* if t[32] is negative */ 51155714Skris { 51255714Skris c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); 51355714Skris } 51455714Skris else 51555714Skris { 51655714Skris /* Might have a carry */ 51755714Skris c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); 51855714Skris } 51955714Skris 52055714Skris /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 52155714Skris * r[10] holds (a[0]*b[0]) 52255714Skris * r[32] holds (b[1]*b[1]) 52355714Skris * c1 holds the carry bits 52455714Skris */ 52555714Skris c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); 52655714Skris if (c1) 52755714Skris { 52855714Skris p= &(r[n+n2]); 52955714Skris lo= *p; 53055714Skris ln=(lo+c1)&BN_MASK2; 53155714Skris *p=ln; 53255714Skris 53355714Skris /* The overflow will stop before we over write 53455714Skris * words we should not overwrite */ 53555714Skris if (ln < (BN_ULONG)c1) 53655714Skris { 53755714Skris do { 53855714Skris p++; 53955714Skris lo= *p; 54055714Skris ln=(lo+1)&BN_MASK2; 54155714Skris *p=ln; 54255714Skris } while (ln == 0); 54355714Skris } 54455714Skris } 54555714Skris } 54655714Skris 54755714Skris/* n+tn is the word length 54855714Skris * t needs to be n*4 is size, as does r */ 549194206Ssimon/* tnX may not be negative but less than n */ 550160814Ssimonvoid bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, 551160814Ssimon int tna, int tnb, BN_ULONG *t) 55255714Skris { 55355714Skris int i,j,n2=n*2; 554120631Snectar int c1,c2,neg,zero; 55555714Skris BN_ULONG ln,lo,*p; 55655714Skris 55759191Skris# ifdef BN_COUNT 558194206Ssimon fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n", 559194206Ssimon n, tna, n, tnb); 56059191Skris# endif 56155714Skris if (n < 8) 56255714Skris { 563160814Ssimon bn_mul_normal(r,a,n+tna,b,n+tnb); 56455714Skris return; 56555714Skris } 56655714Skris 56755714Skris /* r=(a[0]-a[1])*(b[1]-b[0]) */ 568160814Ssimon c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); 569160814Ssimon c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); 57059191Skris zero=neg=0; 57159191Skris switch (c1*3+c2) 57255714Skris { 57359191Skris case -4: 574160814Ssimon bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 575160814Ssimon bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 57659191Skris break; 57759191Skris case -3: 57859191Skris zero=1; 57959191Skris /* break; */ 58059191Skris case -2: 581160814Ssimon bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 582160814Ssimon bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ 58359191Skris neg=1; 58459191Skris break; 58559191Skris case -1: 58659191Skris case 0: 58759191Skris case 1: 58859191Skris zero=1; 58959191Skris /* break; */ 59059191Skris case 2: 591160814Ssimon bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ 592160814Ssimon bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 59359191Skris neg=1; 59459191Skris break; 59559191Skris case 3: 59659191Skris zero=1; 59759191Skris /* break; */ 59859191Skris case 4: 599160814Ssimon bn_sub_part_words(t, a, &(a[n]),tna,n-tna); 600160814Ssimon bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); 60159191Skris break; 60259191Skris } 60359191Skris /* The zero case isn't yet implemented here. The speedup 60459191Skris would probably be negligible. */ 60559191Skris# if 0 60659191Skris if (n == 4) 60759191Skris { 60855714Skris bn_mul_comba4(&(t[n2]),t,&(t[n])); 60955714Skris bn_mul_comba4(r,a,b); 61055714Skris bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); 61155714Skris memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); 61255714Skris } 61359191Skris else 61459191Skris# endif 61559191Skris if (n == 8) 61655714Skris { 61755714Skris bn_mul_comba8(&(t[n2]),t,&(t[n])); 61855714Skris bn_mul_comba8(r,a,b); 619160814Ssimon bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); 620160814Ssimon memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb)); 62155714Skris } 62255714Skris else 62355714Skris { 62455714Skris p= &(t[n2*2]); 625160814Ssimon bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); 626160814Ssimon bn_mul_recursive(r,a,b,n,0,0,p); 62755714Skris i=n/2; 62855714Skris /* If there is only a bottom half to the number, 62955714Skris * just do it */ 630160814Ssimon if (tna > tnb) 631160814Ssimon j = tna - i; 632160814Ssimon else 633160814Ssimon j = tnb - i; 63455714Skris if (j == 0) 63555714Skris { 636160814Ssimon bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]), 637160814Ssimon i,tna-i,tnb-i,p); 63855714Skris memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2)); 63955714Skris } 64055714Skris else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ 64155714Skris { 64255714Skris bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]), 643160814Ssimon i,tna-i,tnb-i,p); 644160814Ssimon memset(&(r[n2+tna+tnb]),0, 645160814Ssimon sizeof(BN_ULONG)*(n2-tna-tnb)); 64655714Skris } 64755714Skris else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 64855714Skris { 64955714Skris memset(&(r[n2]),0,sizeof(BN_ULONG)*n2); 650160814Ssimon if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL 651160814Ssimon && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) 65255714Skris { 653160814Ssimon bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); 65455714Skris } 65555714Skris else 65655714Skris { 65755714Skris for (;;) 65855714Skris { 65955714Skris i/=2; 660194206Ssimon /* these simplified conditions work 661194206Ssimon * exclusively because difference 662194206Ssimon * between tna and tnb is 1 or 0 */ 663194206Ssimon if (i < tna || i < tnb) 66455714Skris { 66555714Skris bn_mul_part_recursive(&(r[n2]), 66655714Skris &(a[n]),&(b[n]), 667160814Ssimon i,tna-i,tnb-i,p); 66855714Skris break; 66955714Skris } 670194206Ssimon else if (i == tna || i == tnb) 67155714Skris { 67255714Skris bn_mul_recursive(&(r[n2]), 67355714Skris &(a[n]),&(b[n]), 674160814Ssimon i,tna-i,tnb-i,p); 67555714Skris break; 67655714Skris } 67755714Skris } 67855714Skris } 67955714Skris } 68055714Skris } 68155714Skris 68255714Skris /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 68355714Skris * r[10] holds (a[0]*b[0]) 68455714Skris * r[32] holds (b[1]*b[1]) 68555714Skris */ 68655714Skris 68755714Skris c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); 68855714Skris 68959191Skris if (neg) /* if t[32] is negative */ 69059191Skris { 69159191Skris c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); 69259191Skris } 69359191Skris else 69459191Skris { 69559191Skris /* Might have a carry */ 69659191Skris c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); 69759191Skris } 69859191Skris 69955714Skris /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 70055714Skris * r[10] holds (a[0]*b[0]) 70155714Skris * r[32] holds (b[1]*b[1]) 70255714Skris * c1 holds the carry bits 70355714Skris */ 70455714Skris c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); 70555714Skris if (c1) 70655714Skris { 70755714Skris p= &(r[n+n2]); 70855714Skris lo= *p; 70955714Skris ln=(lo+c1)&BN_MASK2; 71055714Skris *p=ln; 71155714Skris 71255714Skris /* The overflow will stop before we over write 71355714Skris * words we should not overwrite */ 714120631Snectar if (ln < (BN_ULONG)c1) 71555714Skris { 71655714Skris do { 71755714Skris p++; 71855714Skris lo= *p; 71955714Skris ln=(lo+1)&BN_MASK2; 72055714Skris *p=ln; 72155714Skris } while (ln == 0); 72255714Skris } 72355714Skris } 72455714Skris } 72555714Skris 72655714Skris/* a and b must be the same size, which is n2. 72755714Skris * r needs to be n2 words and t needs to be n2*2 72855714Skris */ 72955714Skrisvoid bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 73055714Skris BN_ULONG *t) 73155714Skris { 73255714Skris int n=n2/2; 73355714Skris 73459191Skris# ifdef BN_COUNT 735160814Ssimon fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2); 73659191Skris# endif 73755714Skris 738160814Ssimon bn_mul_recursive(r,a,b,n,0,0,&(t[0])); 73955714Skris if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) 74055714Skris { 74155714Skris bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2])); 74255714Skris bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); 74355714Skris bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2])); 74455714Skris bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); 74555714Skris } 74655714Skris else 74755714Skris { 74855714Skris bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n); 74955714Skris bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n); 75055714Skris bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); 75155714Skris bn_add_words(&(r[n]),&(r[n]),&(t[n]),n); 75255714Skris } 75355714Skris } 75455714Skris 75555714Skris/* a and b must be the same size, which is n2. 75655714Skris * r needs to be n2 words and t needs to be n2*2 75755714Skris * l is the low words of the output. 75855714Skris * t needs to be n2*3 75955714Skris */ 76055714Skrisvoid bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, 76155714Skris BN_ULONG *t) 76255714Skris { 76355714Skris int i,n; 76455714Skris int c1,c2; 76555714Skris int neg,oneg,zero; 76655714Skris BN_ULONG ll,lc,*lp,*mp; 76755714Skris 76859191Skris# ifdef BN_COUNT 769160814Ssimon fprintf(stderr," bn_mul_high %d * %d\n",n2,n2); 77059191Skris# endif 77155714Skris n=n2/2; 77255714Skris 77355714Skris /* Calculate (al-ah)*(bh-bl) */ 77455714Skris neg=zero=0; 77555714Skris c1=bn_cmp_words(&(a[0]),&(a[n]),n); 77655714Skris c2=bn_cmp_words(&(b[n]),&(b[0]),n); 77755714Skris switch (c1*3+c2) 77855714Skris { 77955714Skris case -4: 78055714Skris bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); 78155714Skris bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); 78255714Skris break; 78355714Skris case -3: 78455714Skris zero=1; 78555714Skris break; 78655714Skris case -2: 78755714Skris bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); 78855714Skris bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); 78955714Skris neg=1; 79055714Skris break; 79155714Skris case -1: 79255714Skris case 0: 79355714Skris case 1: 79455714Skris zero=1; 79555714Skris break; 79655714Skris case 2: 79755714Skris bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); 79855714Skris bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); 79955714Skris neg=1; 80055714Skris break; 80155714Skris case 3: 80255714Skris zero=1; 80355714Skris break; 80455714Skris case 4: 80555714Skris bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); 80655714Skris bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); 80755714Skris break; 80855714Skris } 80955714Skris 81055714Skris oneg=neg; 81155714Skris /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ 81255714Skris /* r[10] = (a[1]*b[1]) */ 81359191Skris# ifdef BN_MUL_COMBA 81455714Skris if (n == 8) 81555714Skris { 81655714Skris bn_mul_comba8(&(t[0]),&(r[0]),&(r[n])); 81755714Skris bn_mul_comba8(r,&(a[n]),&(b[n])); 81855714Skris } 81955714Skris else 82059191Skris# endif 82155714Skris { 822160814Ssimon bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2])); 823160814Ssimon bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); 82455714Skris } 82555714Skris 82655714Skris /* s0 == low(al*bl) 82755714Skris * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) 82855714Skris * We know s0 and s1 so the only unknown is high(al*bl) 82955714Skris * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) 83055714Skris * high(al*bl) == s1 - (r[0]+l[0]+t[0]) 83155714Skris */ 83255714Skris if (l != NULL) 83355714Skris { 83455714Skris lp= &(t[n2+n]); 83555714Skris c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n)); 83655714Skris } 83755714Skris else 83855714Skris { 83955714Skris c1=0; 84055714Skris lp= &(r[0]); 84155714Skris } 84255714Skris 84355714Skris if (neg) 84455714Skris neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n)); 84555714Skris else 84655714Skris { 84755714Skris bn_add_words(&(t[n2]),lp,&(t[0]),n); 84855714Skris neg=0; 84955714Skris } 85055714Skris 85155714Skris if (l != NULL) 85255714Skris { 85355714Skris bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n); 85455714Skris } 85555714Skris else 85655714Skris { 85755714Skris lp= &(t[n2+n]); 85855714Skris mp= &(t[n2]); 85955714Skris for (i=0; i<n; i++) 86055714Skris lp[i]=((~mp[i])+1)&BN_MASK2; 86155714Skris } 86255714Skris 86355714Skris /* s[0] = low(al*bl) 86455714Skris * t[3] = high(al*bl) 86555714Skris * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign 86655714Skris * r[10] = (a[1]*b[1]) 86755714Skris */ 86855714Skris /* R[10] = al*bl 86955714Skris * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) 87055714Skris * R[32] = ah*bh 87155714Skris */ 87255714Skris /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) 87355714Skris * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) 87455714Skris * R[3]=r[1]+(carry/borrow) 87555714Skris */ 87655714Skris if (l != NULL) 87755714Skris { 87855714Skris lp= &(t[n2]); 87955714Skris c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n)); 88055714Skris } 88155714Skris else 88255714Skris { 88355714Skris lp= &(t[n2+n]); 88455714Skris c1=0; 88555714Skris } 88655714Skris c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n)); 88755714Skris if (oneg) 88855714Skris c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n)); 88955714Skris else 89055714Skris c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n)); 89155714Skris 89255714Skris c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n)); 89355714Skris c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n)); 89455714Skris if (oneg) 89555714Skris c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n)); 89655714Skris else 89755714Skris c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n)); 89855714Skris 89955714Skris if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ 90055714Skris { 90155714Skris i=0; 90255714Skris if (c1 > 0) 90355714Skris { 90455714Skris lc=c1; 90555714Skris do { 90655714Skris ll=(r[i]+lc)&BN_MASK2; 90755714Skris r[i++]=ll; 90855714Skris lc=(lc > ll); 90955714Skris } while (lc); 91055714Skris } 91155714Skris else 91255714Skris { 91355714Skris lc= -c1; 91455714Skris do { 91555714Skris ll=r[i]; 91655714Skris r[i++]=(ll-lc)&BN_MASK2; 91755714Skris lc=(lc > ll); 91855714Skris } while (lc); 91955714Skris } 92055714Skris } 92155714Skris if (c2 != 0) /* Add starting at r[1] */ 92255714Skris { 92355714Skris i=n; 92455714Skris if (c2 > 0) 92555714Skris { 92655714Skris lc=c2; 92755714Skris do { 92855714Skris ll=(r[i]+lc)&BN_MASK2; 92955714Skris r[i++]=ll; 93055714Skris lc=(lc > ll); 93155714Skris } while (lc); 93255714Skris } 93355714Skris else 93455714Skris { 93555714Skris lc= -c2; 93655714Skris do { 93755714Skris ll=r[i]; 93855714Skris r[i++]=(ll-lc)&BN_MASK2; 93955714Skris lc=(lc > ll); 94055714Skris } while (lc); 94155714Skris } 94255714Skris } 94355714Skris } 94459191Skris#endif /* BN_RECURSION */ 94555714Skris 946109998Smarkmint BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 94755714Skris { 948160814Ssimon int ret=0; 94955714Skris int top,al,bl; 95055714Skris BIGNUM *rr; 95159191Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 95259191Skris int i; 95359191Skris#endif 95455714Skris#ifdef BN_RECURSION 955160814Ssimon BIGNUM *t=NULL; 956160814Ssimon int j=0,k; 95755714Skris#endif 95855714Skris 95955714Skris#ifdef BN_COUNT 960160814Ssimon fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top); 96155714Skris#endif 96255714Skris 96355714Skris bn_check_top(a); 96455714Skris bn_check_top(b); 96555714Skris bn_check_top(r); 96655714Skris 96755714Skris al=a->top; 96855714Skris bl=b->top; 96955714Skris 97055714Skris if ((al == 0) || (bl == 0)) 97155714Skris { 972160814Ssimon BN_zero(r); 97355714Skris return(1); 97455714Skris } 97555714Skris top=al+bl; 97655714Skris 97759191Skris BN_CTX_start(ctx); 97855714Skris if ((r == a) || (r == b)) 97959191Skris { 98059191Skris if ((rr = BN_CTX_get(ctx)) == NULL) goto err; 98159191Skris } 98255714Skris else 98359191Skris rr = r; 98468651Skris rr->neg=a->neg^b->neg; 98555714Skris 98655714Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 98759191Skris i = al-bl; 98859191Skris#endif 98959191Skris#ifdef BN_MUL_COMBA 99059191Skris if (i == 0) 99155714Skris { 99259191Skris# if 0 99359191Skris if (al == 4) 99455714Skris { 99559191Skris if (bn_wexpand(rr,8) == NULL) goto err; 99655714Skris rr->top=8; 99755714Skris bn_mul_comba4(rr->d,a->d,b->d); 99855714Skris goto end; 99955714Skris } 100059191Skris# endif 100159191Skris if (al == 8) 100255714Skris { 100359191Skris if (bn_wexpand(rr,16) == NULL) goto err; 100455714Skris rr->top=16; 100555714Skris bn_mul_comba8(rr->d,a->d,b->d); 100655714Skris goto end; 100755714Skris } 100855714Skris } 100959191Skris#endif /* BN_MUL_COMBA */ 101055714Skris#ifdef BN_RECURSION 101159191Skris if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) 101255714Skris { 1013160814Ssimon if (i >= -1 && i <= 1) 101455714Skris { 1015160814Ssimon int sav_j =0; 1016160814Ssimon /* Find out the power of two lower or equal 1017160814Ssimon to the longest of the two numbers */ 1018160814Ssimon if (i >= 0) 1019160814Ssimon { 1020160814Ssimon j = BN_num_bits_word((BN_ULONG)al); 1021160814Ssimon } 1022160814Ssimon if (i == -1) 1023160814Ssimon { 1024160814Ssimon j = BN_num_bits_word((BN_ULONG)bl); 1025160814Ssimon } 1026160814Ssimon sav_j = j; 1027160814Ssimon j = 1<<(j-1); 1028160814Ssimon assert(j <= al || j <= bl); 1029160814Ssimon k = j+j; 1030160814Ssimon t = BN_CTX_get(ctx); 1031160814Ssimon if (al > j || bl > j) 1032160814Ssimon { 1033160814Ssimon bn_wexpand(t,k*4); 1034160814Ssimon bn_wexpand(rr,k*4); 1035160814Ssimon bn_mul_part_recursive(rr->d,a->d,b->d, 1036160814Ssimon j,al-j,bl-j,t->d); 1037160814Ssimon } 1038160814Ssimon else /* al <= j || bl <= j */ 1039160814Ssimon { 1040160814Ssimon bn_wexpand(t,k*2); 1041160814Ssimon bn_wexpand(rr,k*2); 1042160814Ssimon bn_mul_recursive(rr->d,a->d,b->d, 1043160814Ssimon j,al-j,bl-j,t->d); 1044160814Ssimon } 1045160814Ssimon rr->top=top; 1046160814Ssimon goto end; 1047160814Ssimon } 1048160814Ssimon#if 0 1049160814Ssimon if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA)) 1050160814Ssimon { 1051160814Ssimon BIGNUM *tmp_bn = (BIGNUM *)b; 1052160814Ssimon if (bn_wexpand(tmp_bn,al) == NULL) goto err; 1053160814Ssimon tmp_bn->d[bl]=0; 105455714Skris bl++; 105559191Skris i--; 105655714Skris } 1057160814Ssimon else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA)) 105855714Skris { 1059160814Ssimon BIGNUM *tmp_bn = (BIGNUM *)a; 1060160814Ssimon if (bn_wexpand(tmp_bn,bl) == NULL) goto err; 1061160814Ssimon tmp_bn->d[al]=0; 106255714Skris al++; 106359191Skris i++; 106455714Skris } 106559191Skris if (i == 0) 106659191Skris { 106759191Skris /* symmetric and > 4 */ 106859191Skris /* 16 or larger */ 106959191Skris j=BN_num_bits_word((BN_ULONG)al); 107059191Skris j=1<<(j-1); 107159191Skris k=j+j; 107259191Skris t = BN_CTX_get(ctx); 107359191Skris if (al == j) /* exact multiple */ 107459191Skris { 1075100936Snectar if (bn_wexpand(t,k*2) == NULL) goto err; 1076100936Snectar if (bn_wexpand(rr,k*2) == NULL) goto err; 107759191Skris bn_mul_recursive(rr->d,a->d,b->d,al,t->d); 107859191Skris } 107959191Skris else 108059191Skris { 1081160814Ssimon if (bn_wexpand(t,k*4) == NULL) goto err; 1082160814Ssimon if (bn_wexpand(rr,k*4) == NULL) goto err; 108359191Skris bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d); 108459191Skris } 108559191Skris rr->top=top; 108659191Skris goto end; 1087160814Ssimon } 1088109998Smarkm#endif 108955714Skris } 109059191Skris#endif /* BN_RECURSION */ 109159191Skris if (bn_wexpand(rr,top) == NULL) goto err; 109255714Skris rr->top=top; 109355714Skris bn_mul_normal(rr->d,a->d,al,b->d,bl); 109455714Skris 109555714Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 109655714Skrisend: 109755714Skris#endif 1098160814Ssimon bn_correct_top(rr); 109955714Skris if (r != rr) BN_copy(r,rr); 110059191Skris ret=1; 110159191Skriserr: 1102160814Ssimon bn_check_top(r); 110359191Skris BN_CTX_end(ctx); 110459191Skris return(ret); 110555714Skris } 110655714Skris 110755714Skrisvoid bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 110855714Skris { 110955714Skris BN_ULONG *rr; 111055714Skris 111155714Skris#ifdef BN_COUNT 1112160814Ssimon fprintf(stderr," bn_mul_normal %d * %d\n",na,nb); 111355714Skris#endif 111455714Skris 111555714Skris if (na < nb) 111655714Skris { 111755714Skris int itmp; 111855714Skris BN_ULONG *ltmp; 111955714Skris 112055714Skris itmp=na; na=nb; nb=itmp; 112155714Skris ltmp=a; a=b; b=ltmp; 112255714Skris 112355714Skris } 112455714Skris rr= &(r[na]); 1125160814Ssimon if (nb <= 0) 1126160814Ssimon { 1127160814Ssimon (void)bn_mul_words(r,a,na,0); 1128160814Ssimon return; 1129160814Ssimon } 1130160814Ssimon else 1131160814Ssimon rr[0]=bn_mul_words(r,a,na,b[0]); 113255714Skris 113355714Skris for (;;) 113455714Skris { 113555714Skris if (--nb <= 0) return; 113655714Skris rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]); 113755714Skris if (--nb <= 0) return; 113855714Skris rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]); 113955714Skris if (--nb <= 0) return; 114055714Skris rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]); 114155714Skris if (--nb <= 0) return; 114255714Skris rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]); 114355714Skris rr+=4; 114455714Skris r+=4; 114555714Skris b+=4; 114655714Skris } 114755714Skris } 114855714Skris 114955714Skrisvoid bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) 115055714Skris { 115155714Skris#ifdef BN_COUNT 1152160814Ssimon fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n); 115355714Skris#endif 115455714Skris bn_mul_words(r,a,n,b[0]); 115555714Skris 115655714Skris for (;;) 115755714Skris { 115855714Skris if (--n <= 0) return; 115955714Skris bn_mul_add_words(&(r[1]),a,n,b[1]); 116055714Skris if (--n <= 0) return; 116155714Skris bn_mul_add_words(&(r[2]),a,n,b[2]); 116255714Skris if (--n <= 0) return; 116355714Skris bn_mul_add_words(&(r[3]),a,n,b[3]); 116455714Skris if (--n <= 0) return; 116555714Skris bn_mul_add_words(&(r[4]),a,n,b[4]); 116655714Skris r+=4; 116755714Skris b+=4; 116855714Skris } 116955714Skris } 1170