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. 8296465Sdelphij * 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). 15296465Sdelphij * 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. 22296465Sdelphij * 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 :-). 37296465Sdelphij * 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)" 40296465Sdelphij * 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. 52296465Sdelphij * 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 60296465Sdelphij# 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) 70296465Sdelphij/* 71296465Sdelphij * Here follows specialised variants of bn_add_words() and bn_sub_words(). 72296465Sdelphij * They have the property performing operations on arrays of different sizes. 73296465Sdelphij * The sizes of those arrays is expressed through cl, which is the common 74296465Sdelphij * length ( basicall, min(len(a),len(b)) ), and dl, which is the delta 75296465Sdelphij * between the two lengths, calculated as len(a)-len(b). All lengths are the 76296465Sdelphij * number of BN_ULONGs... For the operations that require a result array as 77296465Sdelphij * parameter, it must have the length cl+abs(dl). These functions should 78296465Sdelphij * probably end up in bn_asm.c as soon as there are assembler counterparts 79296465Sdelphij * for the systems that use assembler files. 80296465Sdelphij */ 81160814Ssimon 82160814SsimonBN_ULONG bn_sub_part_words(BN_ULONG *r, 83296465Sdelphij const BN_ULONG *a, const BN_ULONG *b, 84296465Sdelphij int cl, int dl) 85296465Sdelphij{ 86296465Sdelphij BN_ULONG c, t; 87160814Ssimon 88296465Sdelphij assert(cl >= 0); 89296465Sdelphij c = bn_sub_words(r, a, b, cl); 90160814Ssimon 91296465Sdelphij if (dl == 0) 92296465Sdelphij return c; 93160814Ssimon 94296465Sdelphij r += cl; 95296465Sdelphij a += cl; 96296465Sdelphij b += cl; 97160814Ssimon 98296465Sdelphij if (dl < 0) { 99296465Sdelphij# ifdef BN_COUNT 100296465Sdelphij fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, 101296465Sdelphij dl, c); 102296465Sdelphij# endif 103296465Sdelphij for (;;) { 104296465Sdelphij t = b[0]; 105296465Sdelphij r[0] = (0 - t - c) & BN_MASK2; 106296465Sdelphij if (t != 0) 107296465Sdelphij c = 1; 108296465Sdelphij if (++dl >= 0) 109296465Sdelphij break; 110160814Ssimon 111296465Sdelphij t = b[1]; 112296465Sdelphij r[1] = (0 - t - c) & BN_MASK2; 113296465Sdelphij if (t != 0) 114296465Sdelphij c = 1; 115296465Sdelphij if (++dl >= 0) 116296465Sdelphij break; 117160814Ssimon 118296465Sdelphij t = b[2]; 119296465Sdelphij r[2] = (0 - t - c) & BN_MASK2; 120296465Sdelphij if (t != 0) 121296465Sdelphij c = 1; 122296465Sdelphij if (++dl >= 0) 123296465Sdelphij break; 124160814Ssimon 125296465Sdelphij t = b[3]; 126296465Sdelphij r[3] = (0 - t - c) & BN_MASK2; 127296465Sdelphij if (t != 0) 128296465Sdelphij c = 1; 129296465Sdelphij if (++dl >= 0) 130296465Sdelphij break; 131160814Ssimon 132296465Sdelphij b += 4; 133296465Sdelphij r += 4; 134296465Sdelphij } 135296465Sdelphij } else { 136296465Sdelphij int save_dl = dl; 137296465Sdelphij# ifdef BN_COUNT 138296465Sdelphij fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, 139296465Sdelphij dl, c); 140296465Sdelphij# endif 141296465Sdelphij while (c) { 142296465Sdelphij t = a[0]; 143296465Sdelphij r[0] = (t - c) & BN_MASK2; 144296465Sdelphij if (t != 0) 145296465Sdelphij c = 0; 146296465Sdelphij if (--dl <= 0) 147296465Sdelphij break; 148160814Ssimon 149296465Sdelphij t = a[1]; 150296465Sdelphij r[1] = (t - c) & BN_MASK2; 151296465Sdelphij if (t != 0) 152296465Sdelphij c = 0; 153296465Sdelphij if (--dl <= 0) 154296465Sdelphij break; 155160814Ssimon 156296465Sdelphij t = a[2]; 157296465Sdelphij r[2] = (t - c) & BN_MASK2; 158296465Sdelphij if (t != 0) 159296465Sdelphij c = 0; 160296465Sdelphij if (--dl <= 0) 161296465Sdelphij break; 162160814Ssimon 163296465Sdelphij t = a[3]; 164296465Sdelphij r[3] = (t - c) & BN_MASK2; 165296465Sdelphij if (t != 0) 166296465Sdelphij c = 0; 167296465Sdelphij if (--dl <= 0) 168296465Sdelphij break; 169160814Ssimon 170296465Sdelphij save_dl = dl; 171296465Sdelphij a += 4; 172296465Sdelphij r += 4; 173296465Sdelphij } 174296465Sdelphij if (dl > 0) { 175296465Sdelphij# ifdef BN_COUNT 176296465Sdelphij fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", 177296465Sdelphij cl, dl); 178296465Sdelphij# endif 179296465Sdelphij if (save_dl > dl) { 180296465Sdelphij switch (save_dl - dl) { 181296465Sdelphij case 1: 182296465Sdelphij r[1] = a[1]; 183296465Sdelphij if (--dl <= 0) 184296465Sdelphij break; 185296465Sdelphij case 2: 186296465Sdelphij r[2] = a[2]; 187296465Sdelphij if (--dl <= 0) 188296465Sdelphij break; 189296465Sdelphij case 3: 190296465Sdelphij r[3] = a[3]; 191296465Sdelphij if (--dl <= 0) 192296465Sdelphij break; 193296465Sdelphij } 194296465Sdelphij a += 4; 195296465Sdelphij r += 4; 196296465Sdelphij } 197296465Sdelphij } 198296465Sdelphij if (dl > 0) { 199296465Sdelphij# ifdef BN_COUNT 200296465Sdelphij fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", 201296465Sdelphij cl, dl); 202296465Sdelphij# endif 203296465Sdelphij for (;;) { 204296465Sdelphij r[0] = a[0]; 205296465Sdelphij if (--dl <= 0) 206296465Sdelphij break; 207296465Sdelphij r[1] = a[1]; 208296465Sdelphij if (--dl <= 0) 209296465Sdelphij break; 210296465Sdelphij r[2] = a[2]; 211296465Sdelphij if (--dl <= 0) 212296465Sdelphij break; 213296465Sdelphij r[3] = a[3]; 214296465Sdelphij if (--dl <= 0) 215296465Sdelphij break; 216160814Ssimon 217296465Sdelphij a += 4; 218296465Sdelphij r += 4; 219296465Sdelphij } 220296465Sdelphij } 221296465Sdelphij } 222296465Sdelphij return c; 223296465Sdelphij} 224160814Ssimon#endif 225160814Ssimon 226160814SsimonBN_ULONG bn_add_part_words(BN_ULONG *r, 227296465Sdelphij const BN_ULONG *a, const BN_ULONG *b, 228296465Sdelphij int cl, int dl) 229296465Sdelphij{ 230296465Sdelphij BN_ULONG c, l, t; 231160814Ssimon 232296465Sdelphij assert(cl >= 0); 233296465Sdelphij c = bn_add_words(r, a, b, cl); 234160814Ssimon 235296465Sdelphij if (dl == 0) 236296465Sdelphij return c; 237160814Ssimon 238296465Sdelphij r += cl; 239296465Sdelphij a += cl; 240296465Sdelphij b += cl; 241160814Ssimon 242296465Sdelphij if (dl < 0) { 243296465Sdelphij int save_dl = dl; 244160814Ssimon#ifdef BN_COUNT 245296465Sdelphij fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, 246296465Sdelphij dl, c); 247160814Ssimon#endif 248296465Sdelphij while (c) { 249296465Sdelphij l = (c + b[0]) & BN_MASK2; 250296465Sdelphij c = (l < c); 251296465Sdelphij r[0] = l; 252296465Sdelphij if (++dl >= 0) 253296465Sdelphij break; 254160814Ssimon 255296465Sdelphij l = (c + b[1]) & BN_MASK2; 256296465Sdelphij c = (l < c); 257296465Sdelphij r[1] = l; 258296465Sdelphij if (++dl >= 0) 259296465Sdelphij break; 260160814Ssimon 261296465Sdelphij l = (c + b[2]) & BN_MASK2; 262296465Sdelphij c = (l < c); 263296465Sdelphij r[2] = l; 264296465Sdelphij if (++dl >= 0) 265296465Sdelphij break; 266160814Ssimon 267296465Sdelphij l = (c + b[3]) & BN_MASK2; 268296465Sdelphij c = (l < c); 269296465Sdelphij r[3] = l; 270296465Sdelphij if (++dl >= 0) 271296465Sdelphij break; 272160814Ssimon 273296465Sdelphij save_dl = dl; 274296465Sdelphij b += 4; 275296465Sdelphij r += 4; 276296465Sdelphij } 277296465Sdelphij if (dl < 0) { 278160814Ssimon#ifdef BN_COUNT 279296465Sdelphij fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", 280296465Sdelphij cl, dl); 281160814Ssimon#endif 282296465Sdelphij if (save_dl < dl) { 283296465Sdelphij switch (dl - save_dl) { 284296465Sdelphij case 1: 285296465Sdelphij r[1] = b[1]; 286296465Sdelphij if (++dl >= 0) 287296465Sdelphij break; 288296465Sdelphij case 2: 289296465Sdelphij r[2] = b[2]; 290296465Sdelphij if (++dl >= 0) 291296465Sdelphij break; 292296465Sdelphij case 3: 293296465Sdelphij r[3] = b[3]; 294296465Sdelphij if (++dl >= 0) 295296465Sdelphij break; 296296465Sdelphij } 297296465Sdelphij b += 4; 298296465Sdelphij r += 4; 299296465Sdelphij } 300296465Sdelphij } 301296465Sdelphij if (dl < 0) { 302160814Ssimon#ifdef BN_COUNT 303296465Sdelphij fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", 304296465Sdelphij cl, dl); 305160814Ssimon#endif 306296465Sdelphij for (;;) { 307296465Sdelphij r[0] = b[0]; 308296465Sdelphij if (++dl >= 0) 309296465Sdelphij break; 310296465Sdelphij r[1] = b[1]; 311296465Sdelphij if (++dl >= 0) 312296465Sdelphij break; 313296465Sdelphij r[2] = b[2]; 314296465Sdelphij if (++dl >= 0) 315296465Sdelphij break; 316296465Sdelphij r[3] = b[3]; 317296465Sdelphij if (++dl >= 0) 318296465Sdelphij break; 319160814Ssimon 320296465Sdelphij b += 4; 321296465Sdelphij r += 4; 322296465Sdelphij } 323296465Sdelphij } 324296465Sdelphij } else { 325296465Sdelphij int save_dl = dl; 326160814Ssimon#ifdef BN_COUNT 327296465Sdelphij fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); 328160814Ssimon#endif 329296465Sdelphij while (c) { 330296465Sdelphij t = (a[0] + c) & BN_MASK2; 331296465Sdelphij c = (t < c); 332296465Sdelphij r[0] = t; 333296465Sdelphij if (--dl <= 0) 334296465Sdelphij break; 335160814Ssimon 336296465Sdelphij t = (a[1] + c) & BN_MASK2; 337296465Sdelphij c = (t < c); 338296465Sdelphij r[1] = t; 339296465Sdelphij if (--dl <= 0) 340296465Sdelphij break; 341160814Ssimon 342296465Sdelphij t = (a[2] + c) & BN_MASK2; 343296465Sdelphij c = (t < c); 344296465Sdelphij r[2] = t; 345296465Sdelphij if (--dl <= 0) 346296465Sdelphij break; 347160814Ssimon 348296465Sdelphij t = (a[3] + c) & BN_MASK2; 349296465Sdelphij c = (t < c); 350296465Sdelphij r[3] = t; 351296465Sdelphij if (--dl <= 0) 352296465Sdelphij break; 353160814Ssimon 354296465Sdelphij save_dl = dl; 355296465Sdelphij a += 4; 356296465Sdelphij r += 4; 357296465Sdelphij } 358160814Ssimon#ifdef BN_COUNT 359296465Sdelphij fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, 360296465Sdelphij dl); 361160814Ssimon#endif 362296465Sdelphij if (dl > 0) { 363296465Sdelphij if (save_dl > dl) { 364296465Sdelphij switch (save_dl - dl) { 365296465Sdelphij case 1: 366296465Sdelphij r[1] = a[1]; 367296465Sdelphij if (--dl <= 0) 368296465Sdelphij break; 369296465Sdelphij case 2: 370296465Sdelphij r[2] = a[2]; 371296465Sdelphij if (--dl <= 0) 372296465Sdelphij break; 373296465Sdelphij case 3: 374296465Sdelphij r[3] = a[3]; 375296465Sdelphij if (--dl <= 0) 376296465Sdelphij break; 377296465Sdelphij } 378296465Sdelphij a += 4; 379296465Sdelphij r += 4; 380296465Sdelphij } 381296465Sdelphij } 382296465Sdelphij if (dl > 0) { 383160814Ssimon#ifdef BN_COUNT 384296465Sdelphij fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", 385296465Sdelphij cl, dl); 386160814Ssimon#endif 387296465Sdelphij for (;;) { 388296465Sdelphij r[0] = a[0]; 389296465Sdelphij if (--dl <= 0) 390296465Sdelphij break; 391296465Sdelphij r[1] = a[1]; 392296465Sdelphij if (--dl <= 0) 393296465Sdelphij break; 394296465Sdelphij r[2] = a[2]; 395296465Sdelphij if (--dl <= 0) 396296465Sdelphij break; 397296465Sdelphij r[3] = a[3]; 398296465Sdelphij if (--dl <= 0) 399296465Sdelphij break; 400160814Ssimon 401296465Sdelphij a += 4; 402296465Sdelphij r += 4; 403296465Sdelphij } 404296465Sdelphij } 405296465Sdelphij } 406296465Sdelphij return c; 407296465Sdelphij} 408160814Ssimon 40955714Skris#ifdef BN_RECURSION 410296465Sdelphij/* 411296465Sdelphij * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of 412296465Sdelphij * Computer Programming, Vol. 2) 413296465Sdelphij */ 41459191Skris 415296465Sdelphij/*- 416296465Sdelphij * r is 2*n2 words in size, 41755714Skris * a and b are both n2 words in size. 41855714Skris * n2 must be a power of 2. 41955714Skris * We multiply and return the result. 42055714Skris * t must be 2*n2 words in size 42159191Skris * We calculate 42255714Skris * a[0]*b[0] 42355714Skris * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 42455714Skris * a[1]*b[1] 42555714Skris */ 426194206Ssimon/* dnX may not be positive, but n2/2+dnX has to be */ 42755714Skrisvoid bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 428296465Sdelphij int dna, int dnb, BN_ULONG *t) 429296465Sdelphij{ 430296465Sdelphij int n = n2 / 2, c1, c2; 431296465Sdelphij int tna = n + dna, tnb = n + dnb; 432296465Sdelphij unsigned int neg, zero; 433296465Sdelphij BN_ULONG ln, lo, *p; 43455714Skris 43559191Skris# ifdef BN_COUNT 436296465Sdelphij fprintf(stderr, " bn_mul_recursive %d%+d * %d%+d\n", n2, dna, n2, dnb); 43759191Skris# endif 43859191Skris# ifdef BN_MUL_COMBA 43959191Skris# if 0 440296465Sdelphij if (n2 == 4) { 441296465Sdelphij bn_mul_comba4(r, a, b); 442296465Sdelphij return; 443296465Sdelphij } 44459191Skris# endif 445296465Sdelphij /* 446296465Sdelphij * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete 447296465Sdelphij * [steve] 448296465Sdelphij */ 449296465Sdelphij if (n2 == 8 && dna == 0 && dnb == 0) { 450296465Sdelphij bn_mul_comba8(r, a, b); 451296465Sdelphij return; 452296465Sdelphij } 453296465Sdelphij# endif /* BN_MUL_COMBA */ 454296465Sdelphij /* Else do normal multiply */ 455296465Sdelphij if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { 456296465Sdelphij bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); 457296465Sdelphij if ((dna + dnb) < 0) 458296465Sdelphij memset(&r[2 * n2 + dna + dnb], 0, 459296465Sdelphij sizeof(BN_ULONG) * -(dna + dnb)); 460296465Sdelphij return; 461296465Sdelphij } 462296465Sdelphij /* r=(a[0]-a[1])*(b[1]-b[0]) */ 463296465Sdelphij c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 464296465Sdelphij c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 465296465Sdelphij zero = neg = 0; 466296465Sdelphij switch (c1 * 3 + c2) { 467296465Sdelphij case -4: 468296465Sdelphij bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 469296465Sdelphij bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 470296465Sdelphij break; 471296465Sdelphij case -3: 472296465Sdelphij zero = 1; 473296465Sdelphij break; 474296465Sdelphij case -2: 475296465Sdelphij bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 476296465Sdelphij bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 477296465Sdelphij neg = 1; 478296465Sdelphij break; 479296465Sdelphij case -1: 480296465Sdelphij case 0: 481296465Sdelphij case 1: 482296465Sdelphij zero = 1; 483296465Sdelphij break; 484296465Sdelphij case 2: 485296465Sdelphij bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 486296465Sdelphij bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 487296465Sdelphij neg = 1; 488296465Sdelphij break; 489296465Sdelphij case 3: 490296465Sdelphij zero = 1; 491296465Sdelphij break; 492296465Sdelphij case 4: 493296465Sdelphij bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 494296465Sdelphij bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 495296465Sdelphij break; 496296465Sdelphij } 49755714Skris 49859191Skris# ifdef BN_MUL_COMBA 499296465Sdelphij if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take 500296465Sdelphij * extra args to do this well */ 501296465Sdelphij if (!zero) 502296465Sdelphij bn_mul_comba4(&(t[n2]), t, &(t[n])); 503296465Sdelphij else 504296465Sdelphij memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG)); 50555714Skris 506296465Sdelphij bn_mul_comba4(r, a, b); 507296465Sdelphij bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); 508296465Sdelphij } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could 509296465Sdelphij * take extra args to do 510296465Sdelphij * this well */ 511296465Sdelphij if (!zero) 512296465Sdelphij bn_mul_comba8(&(t[n2]), t, &(t[n])); 513296465Sdelphij else 514296465Sdelphij memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG)); 51555714Skris 516296465Sdelphij bn_mul_comba8(r, a, b); 517296465Sdelphij bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n])); 518296465Sdelphij } else 519296465Sdelphij# endif /* BN_MUL_COMBA */ 520296465Sdelphij { 521296465Sdelphij p = &(t[n2 * 2]); 522296465Sdelphij if (!zero) 523296465Sdelphij bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 524296465Sdelphij else 525296465Sdelphij memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); 526296465Sdelphij bn_mul_recursive(r, a, b, n, 0, 0, p); 527296465Sdelphij bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); 528296465Sdelphij } 52955714Skris 530296465Sdelphij /*- 531296465Sdelphij * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 532296465Sdelphij * r[10] holds (a[0]*b[0]) 533296465Sdelphij * r[32] holds (b[1]*b[1]) 534296465Sdelphij */ 53555714Skris 536296465Sdelphij c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 53755714Skris 538296465Sdelphij if (neg) { /* if t[32] is negative */ 539296465Sdelphij c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 540296465Sdelphij } else { 541296465Sdelphij /* Might have a carry */ 542296465Sdelphij c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 543296465Sdelphij } 54455714Skris 545296465Sdelphij /*- 546296465Sdelphij * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 547296465Sdelphij * r[10] holds (a[0]*b[0]) 548296465Sdelphij * r[32] holds (b[1]*b[1]) 549296465Sdelphij * c1 holds the carry bits 550296465Sdelphij */ 551296465Sdelphij c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 552296465Sdelphij if (c1) { 553296465Sdelphij p = &(r[n + n2]); 554296465Sdelphij lo = *p; 555296465Sdelphij ln = (lo + c1) & BN_MASK2; 556296465Sdelphij *p = ln; 557296465Sdelphij 558296465Sdelphij /* 559296465Sdelphij * The overflow will stop before we over write words we should not 560296465Sdelphij * overwrite 561296465Sdelphij */ 562296465Sdelphij if (ln < (BN_ULONG)c1) { 563296465Sdelphij do { 564296465Sdelphij p++; 565296465Sdelphij lo = *p; 566296465Sdelphij ln = (lo + 1) & BN_MASK2; 567296465Sdelphij *p = ln; 568296465Sdelphij } while (ln == 0); 569296465Sdelphij } 570296465Sdelphij } 571296465Sdelphij} 572296465Sdelphij 573296465Sdelphij/* 574296465Sdelphij * n+tn is the word length t needs to be n*4 is size, as does r 575296465Sdelphij */ 576194206Ssimon/* tnX may not be negative but less than n */ 577160814Ssimonvoid bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, 578296465Sdelphij int tna, int tnb, BN_ULONG *t) 579296465Sdelphij{ 580296465Sdelphij int i, j, n2 = n * 2; 581296465Sdelphij int c1, c2, neg; 582296465Sdelphij BN_ULONG ln, lo, *p; 58355714Skris 58459191Skris# ifdef BN_COUNT 585296465Sdelphij fprintf(stderr, " bn_mul_part_recursive (%d%+d) * (%d%+d)\n", 586296465Sdelphij n, tna, n, tnb); 58759191Skris# endif 588296465Sdelphij if (n < 8) { 589296465Sdelphij bn_mul_normal(r, a, n + tna, b, n + tnb); 590296465Sdelphij return; 591296465Sdelphij } 59255714Skris 593296465Sdelphij /* r=(a[0]-a[1])*(b[1]-b[0]) */ 594296465Sdelphij c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 595296465Sdelphij c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 596296465Sdelphij neg = 0; 597296465Sdelphij switch (c1 * 3 + c2) { 598296465Sdelphij case -4: 599296465Sdelphij bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 600296465Sdelphij bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 601296465Sdelphij break; 602296465Sdelphij case -3: 603296465Sdelphij /* break; */ 604296465Sdelphij case -2: 605296465Sdelphij bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 606296465Sdelphij bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 607296465Sdelphij neg = 1; 608296465Sdelphij break; 609296465Sdelphij case -1: 610296465Sdelphij case 0: 611296465Sdelphij case 1: 612296465Sdelphij /* break; */ 613296465Sdelphij case 2: 614296465Sdelphij bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 615296465Sdelphij bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 616296465Sdelphij neg = 1; 617296465Sdelphij break; 618296465Sdelphij case 3: 619296465Sdelphij /* break; */ 620296465Sdelphij case 4: 621296465Sdelphij bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 622296465Sdelphij bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 623296465Sdelphij break; 624296465Sdelphij } 625296465Sdelphij /* 626296465Sdelphij * The zero case isn't yet implemented here. The speedup would probably 627296465Sdelphij * be negligible. 628296465Sdelphij */ 62959191Skris# if 0 630296465Sdelphij if (n == 4) { 631296465Sdelphij bn_mul_comba4(&(t[n2]), t, &(t[n])); 632296465Sdelphij bn_mul_comba4(r, a, b); 633296465Sdelphij bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn); 634296465Sdelphij memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2)); 635296465Sdelphij } else 63659191Skris# endif 637296465Sdelphij if (n == 8) { 638296465Sdelphij bn_mul_comba8(&(t[n2]), t, &(t[n])); 639296465Sdelphij bn_mul_comba8(r, a, b); 640296465Sdelphij bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 641296465Sdelphij memset(&(r[n2 + tna + tnb]), 0, sizeof(BN_ULONG) * (n2 - tna - tnb)); 642296465Sdelphij } else { 643296465Sdelphij p = &(t[n2 * 2]); 644296465Sdelphij bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 645296465Sdelphij bn_mul_recursive(r, a, b, n, 0, 0, p); 646296465Sdelphij i = n / 2; 647296465Sdelphij /* 648296465Sdelphij * If there is only a bottom half to the number, just do it 649296465Sdelphij */ 650296465Sdelphij if (tna > tnb) 651296465Sdelphij j = tna - i; 652296465Sdelphij else 653296465Sdelphij j = tnb - i; 654296465Sdelphij if (j == 0) { 655296465Sdelphij bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), 656296465Sdelphij i, tna - i, tnb - i, p); 657296465Sdelphij memset(&(r[n2 + i * 2]), 0, sizeof(BN_ULONG) * (n2 - i * 2)); 658296465Sdelphij } else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */ 659296465Sdelphij bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), 660296465Sdelphij i, tna - i, tnb - i, p); 661296465Sdelphij memset(&(r[n2 + tna + tnb]), 0, 662296465Sdelphij sizeof(BN_ULONG) * (n2 - tna - tnb)); 663296465Sdelphij } else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 66455714Skris 665296465Sdelphij memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2); 666296465Sdelphij if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL 667296465Sdelphij && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { 668296465Sdelphij bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 669296465Sdelphij } else { 670296465Sdelphij for (;;) { 671296465Sdelphij i /= 2; 672296465Sdelphij /* 673296465Sdelphij * these simplified conditions work exclusively because 674296465Sdelphij * difference between tna and tnb is 1 or 0 675296465Sdelphij */ 676296465Sdelphij if (i < tna || i < tnb) { 677296465Sdelphij bn_mul_part_recursive(&(r[n2]), 678296465Sdelphij &(a[n]), &(b[n]), 679296465Sdelphij i, tna - i, tnb - i, p); 680296465Sdelphij break; 681296465Sdelphij } else if (i == tna || i == tnb) { 682296465Sdelphij bn_mul_recursive(&(r[n2]), 683296465Sdelphij &(a[n]), &(b[n]), 684296465Sdelphij i, tna - i, tnb - i, p); 685296465Sdelphij break; 686296465Sdelphij } 687296465Sdelphij } 688296465Sdelphij } 689296465Sdelphij } 690296465Sdelphij } 69155714Skris 692296465Sdelphij /*- 693296465Sdelphij * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 694296465Sdelphij * r[10] holds (a[0]*b[0]) 695296465Sdelphij * r[32] holds (b[1]*b[1]) 696296465Sdelphij */ 69755714Skris 698296465Sdelphij c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 69959191Skris 700296465Sdelphij if (neg) { /* if t[32] is negative */ 701296465Sdelphij c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 702296465Sdelphij } else { 703296465Sdelphij /* Might have a carry */ 704296465Sdelphij c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 705296465Sdelphij } 70655714Skris 707296465Sdelphij /*- 708296465Sdelphij * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 709296465Sdelphij * r[10] holds (a[0]*b[0]) 710296465Sdelphij * r[32] holds (b[1]*b[1]) 711296465Sdelphij * c1 holds the carry bits 712296465Sdelphij */ 713296465Sdelphij c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 714296465Sdelphij if (c1) { 715296465Sdelphij p = &(r[n + n2]); 716296465Sdelphij lo = *p; 717296465Sdelphij ln = (lo + c1) & BN_MASK2; 718296465Sdelphij *p = ln; 71955714Skris 720296465Sdelphij /* 721296465Sdelphij * The overflow will stop before we over write words we should not 722296465Sdelphij * overwrite 723296465Sdelphij */ 724296465Sdelphij if (ln < (BN_ULONG)c1) { 725296465Sdelphij do { 726296465Sdelphij p++; 727296465Sdelphij lo = *p; 728296465Sdelphij ln = (lo + 1) & BN_MASK2; 729296465Sdelphij *p = ln; 730296465Sdelphij } while (ln == 0); 731296465Sdelphij } 732296465Sdelphij } 733296465Sdelphij} 734296465Sdelphij 735296465Sdelphij/*- 736296465Sdelphij * a and b must be the same size, which is n2. 73755714Skris * r needs to be n2 words and t needs to be n2*2 73855714Skris */ 73955714Skrisvoid bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 740296465Sdelphij BN_ULONG *t) 741296465Sdelphij{ 742296465Sdelphij int n = n2 / 2; 74355714Skris 74459191Skris# ifdef BN_COUNT 745296465Sdelphij fprintf(stderr, " bn_mul_low_recursive %d * %d\n", n2, n2); 74659191Skris# endif 74755714Skris 748296465Sdelphij bn_mul_recursive(r, a, b, n, 0, 0, &(t[0])); 749296465Sdelphij if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) { 750296465Sdelphij bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2])); 751296465Sdelphij bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 752296465Sdelphij bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2])); 753296465Sdelphij bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 754296465Sdelphij } else { 755296465Sdelphij bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n); 756296465Sdelphij bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n); 757296465Sdelphij bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 758296465Sdelphij bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); 759296465Sdelphij } 760296465Sdelphij} 76155714Skris 762296465Sdelphij/*- 763296465Sdelphij * a and b must be the same size, which is n2. 76455714Skris * r needs to be n2 words and t needs to be n2*2 76555714Skris * l is the low words of the output. 76655714Skris * t needs to be n2*3 76755714Skris */ 76855714Skrisvoid bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, 769296465Sdelphij BN_ULONG *t) 770296465Sdelphij{ 771296465Sdelphij int i, n; 772296465Sdelphij int c1, c2; 773296465Sdelphij int neg, oneg, zero; 774296465Sdelphij BN_ULONG ll, lc, *lp, *mp; 77555714Skris 77659191Skris# ifdef BN_COUNT 777296465Sdelphij fprintf(stderr, " bn_mul_high %d * %d\n", n2, n2); 77859191Skris# endif 779296465Sdelphij n = n2 / 2; 78055714Skris 781296465Sdelphij /* Calculate (al-ah)*(bh-bl) */ 782296465Sdelphij neg = zero = 0; 783296465Sdelphij c1 = bn_cmp_words(&(a[0]), &(a[n]), n); 784296465Sdelphij c2 = bn_cmp_words(&(b[n]), &(b[0]), n); 785296465Sdelphij switch (c1 * 3 + c2) { 786296465Sdelphij case -4: 787296465Sdelphij bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); 788296465Sdelphij bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); 789296465Sdelphij break; 790296465Sdelphij case -3: 791296465Sdelphij zero = 1; 792296465Sdelphij break; 793296465Sdelphij case -2: 794296465Sdelphij bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); 795296465Sdelphij bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); 796296465Sdelphij neg = 1; 797296465Sdelphij break; 798296465Sdelphij case -1: 799296465Sdelphij case 0: 800296465Sdelphij case 1: 801296465Sdelphij zero = 1; 802296465Sdelphij break; 803296465Sdelphij case 2: 804296465Sdelphij bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); 805296465Sdelphij bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); 806296465Sdelphij neg = 1; 807296465Sdelphij break; 808296465Sdelphij case 3: 809296465Sdelphij zero = 1; 810296465Sdelphij break; 811296465Sdelphij case 4: 812296465Sdelphij bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); 813296465Sdelphij bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); 814296465Sdelphij break; 815296465Sdelphij } 816296465Sdelphij 817296465Sdelphij oneg = neg; 818296465Sdelphij /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ 819296465Sdelphij /* r[10] = (a[1]*b[1]) */ 82059191Skris# ifdef BN_MUL_COMBA 821296465Sdelphij if (n == 8) { 822296465Sdelphij bn_mul_comba8(&(t[0]), &(r[0]), &(r[n])); 823296465Sdelphij bn_mul_comba8(r, &(a[n]), &(b[n])); 824296465Sdelphij } else 82559191Skris# endif 826296465Sdelphij { 827296465Sdelphij bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2])); 828296465Sdelphij bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); 829296465Sdelphij } 83055714Skris 831296465Sdelphij /*- 832296465Sdelphij * s0 == low(al*bl) 833296465Sdelphij * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) 834296465Sdelphij * We know s0 and s1 so the only unknown is high(al*bl) 835296465Sdelphij * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) 836296465Sdelphij * high(al*bl) == s1 - (r[0]+l[0]+t[0]) 837296465Sdelphij */ 838296465Sdelphij if (l != NULL) { 839296465Sdelphij lp = &(t[n2 + n]); 840296465Sdelphij c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n)); 841296465Sdelphij } else { 842296465Sdelphij c1 = 0; 843296465Sdelphij lp = &(r[0]); 844296465Sdelphij } 84555714Skris 846296465Sdelphij if (neg) 847296465Sdelphij neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n)); 848296465Sdelphij else { 849296465Sdelphij bn_add_words(&(t[n2]), lp, &(t[0]), n); 850296465Sdelphij neg = 0; 851296465Sdelphij } 85255714Skris 853296465Sdelphij if (l != NULL) { 854296465Sdelphij bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n); 855296465Sdelphij } else { 856296465Sdelphij lp = &(t[n2 + n]); 857296465Sdelphij mp = &(t[n2]); 858296465Sdelphij for (i = 0; i < n; i++) 859296465Sdelphij lp[i] = ((~mp[i]) + 1) & BN_MASK2; 860296465Sdelphij } 86155714Skris 862296465Sdelphij /*- 863296465Sdelphij * s[0] = low(al*bl) 864296465Sdelphij * t[3] = high(al*bl) 865296465Sdelphij * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign 866296465Sdelphij * r[10] = (a[1]*b[1]) 867296465Sdelphij */ 868296465Sdelphij /*- 869296465Sdelphij * R[10] = al*bl 870296465Sdelphij * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) 871296465Sdelphij * R[32] = ah*bh 872296465Sdelphij */ 873296465Sdelphij /*- 874296465Sdelphij * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) 875296465Sdelphij * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) 876296465Sdelphij * R[3]=r[1]+(carry/borrow) 877296465Sdelphij */ 878296465Sdelphij if (l != NULL) { 879296465Sdelphij lp = &(t[n2]); 880296465Sdelphij c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); 881296465Sdelphij } else { 882296465Sdelphij lp = &(t[n2 + n]); 883296465Sdelphij c1 = 0; 884296465Sdelphij } 885296465Sdelphij c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n)); 886296465Sdelphij if (oneg) 887296465Sdelphij c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n)); 888296465Sdelphij else 889296465Sdelphij c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n)); 89055714Skris 891296465Sdelphij c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n)); 892296465Sdelphij c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n)); 893296465Sdelphij if (oneg) 894296465Sdelphij c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n)); 895296465Sdelphij else 896296465Sdelphij c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n)); 89755714Skris 898296465Sdelphij if (c1 != 0) { /* Add starting at r[0], could be +ve or -ve */ 899296465Sdelphij i = 0; 900296465Sdelphij if (c1 > 0) { 901296465Sdelphij lc = c1; 902296465Sdelphij do { 903296465Sdelphij ll = (r[i] + lc) & BN_MASK2; 904296465Sdelphij r[i++] = ll; 905296465Sdelphij lc = (lc > ll); 906296465Sdelphij } while (lc); 907296465Sdelphij } else { 908296465Sdelphij lc = -c1; 909296465Sdelphij do { 910296465Sdelphij ll = r[i]; 911296465Sdelphij r[i++] = (ll - lc) & BN_MASK2; 912296465Sdelphij lc = (lc > ll); 913296465Sdelphij } while (lc); 914296465Sdelphij } 915296465Sdelphij } 916296465Sdelphij if (c2 != 0) { /* Add starting at r[1] */ 917296465Sdelphij i = n; 918296465Sdelphij if (c2 > 0) { 919296465Sdelphij lc = c2; 920296465Sdelphij do { 921296465Sdelphij ll = (r[i] + lc) & BN_MASK2; 922296465Sdelphij r[i++] = ll; 923296465Sdelphij lc = (lc > ll); 924296465Sdelphij } while (lc); 925296465Sdelphij } else { 926296465Sdelphij lc = -c2; 927296465Sdelphij do { 928296465Sdelphij ll = r[i]; 929296465Sdelphij r[i++] = (ll - lc) & BN_MASK2; 930296465Sdelphij lc = (lc > ll); 931296465Sdelphij } while (lc); 932296465Sdelphij } 933296465Sdelphij } 934296465Sdelphij} 935296465Sdelphij#endif /* BN_RECURSION */ 936296465Sdelphij 937109998Smarkmint BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 938296465Sdelphij{ 939296465Sdelphij int ret = 0; 940296465Sdelphij int top, al, bl; 941296465Sdelphij BIGNUM *rr; 94259191Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 943296465Sdelphij int i; 94459191Skris#endif 94555714Skris#ifdef BN_RECURSION 946296465Sdelphij BIGNUM *t = NULL; 947296465Sdelphij int j = 0, k; 94855714Skris#endif 94955714Skris 95055714Skris#ifdef BN_COUNT 951296465Sdelphij fprintf(stderr, "BN_mul %d * %d\n", a->top, b->top); 95255714Skris#endif 95355714Skris 954296465Sdelphij bn_check_top(a); 955296465Sdelphij bn_check_top(b); 956296465Sdelphij bn_check_top(r); 95755714Skris 958296465Sdelphij al = a->top; 959296465Sdelphij bl = b->top; 96055714Skris 961296465Sdelphij if ((al == 0) || (bl == 0)) { 962296465Sdelphij BN_zero(r); 963296465Sdelphij return (1); 964296465Sdelphij } 965296465Sdelphij top = al + bl; 96655714Skris 967296465Sdelphij BN_CTX_start(ctx); 968296465Sdelphij if ((r == a) || (r == b)) { 969296465Sdelphij if ((rr = BN_CTX_get(ctx)) == NULL) 970296465Sdelphij goto err; 971296465Sdelphij } else 972296465Sdelphij rr = r; 973296465Sdelphij rr->neg = a->neg ^ b->neg; 97455714Skris 97555714Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 976296465Sdelphij i = al - bl; 97759191Skris#endif 97859191Skris#ifdef BN_MUL_COMBA 979296465Sdelphij if (i == 0) { 98059191Skris# if 0 981296465Sdelphij if (al == 4) { 982296465Sdelphij if (bn_wexpand(rr, 8) == NULL) 983296465Sdelphij goto err; 984296465Sdelphij rr->top = 8; 985296465Sdelphij bn_mul_comba4(rr->d, a->d, b->d); 986296465Sdelphij goto end; 987296465Sdelphij } 98859191Skris# endif 989296465Sdelphij if (al == 8) { 990296465Sdelphij if (bn_wexpand(rr, 16) == NULL) 991296465Sdelphij goto err; 992296465Sdelphij rr->top = 16; 993296465Sdelphij bn_mul_comba8(rr->d, a->d, b->d); 994296465Sdelphij goto end; 995296465Sdelphij } 996296465Sdelphij } 997296465Sdelphij#endif /* BN_MUL_COMBA */ 99855714Skris#ifdef BN_RECURSION 999296465Sdelphij if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { 1000296465Sdelphij if (i >= -1 && i <= 1) { 1001296465Sdelphij /* 1002296465Sdelphij * Find out the power of two lower or equal to the longest of the 1003296465Sdelphij * two numbers 1004296465Sdelphij */ 1005296465Sdelphij if (i >= 0) { 1006296465Sdelphij j = BN_num_bits_word((BN_ULONG)al); 1007296465Sdelphij } 1008296465Sdelphij if (i == -1) { 1009296465Sdelphij j = BN_num_bits_word((BN_ULONG)bl); 1010296465Sdelphij } 1011296465Sdelphij j = 1 << (j - 1); 1012296465Sdelphij assert(j <= al || j <= bl); 1013296465Sdelphij k = j + j; 1014296465Sdelphij t = BN_CTX_get(ctx); 1015296465Sdelphij if (t == NULL) 1016296465Sdelphij goto err; 1017296465Sdelphij if (al > j || bl > j) { 1018296465Sdelphij if (bn_wexpand(t, k * 4) == NULL) 1019296465Sdelphij goto err; 1020296465Sdelphij if (bn_wexpand(rr, k * 4) == NULL) 1021296465Sdelphij goto err; 1022296465Sdelphij bn_mul_part_recursive(rr->d, a->d, b->d, 1023296465Sdelphij j, al - j, bl - j, t->d); 1024296465Sdelphij } else { /* al <= j || bl <= j */ 102555714Skris 1026296465Sdelphij if (bn_wexpand(t, k * 2) == NULL) 1027296465Sdelphij goto err; 1028296465Sdelphij if (bn_wexpand(rr, k * 2) == NULL) 1029296465Sdelphij goto err; 1030296465Sdelphij bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); 1031296465Sdelphij } 1032296465Sdelphij rr->top = top; 1033296465Sdelphij goto end; 1034296465Sdelphij } 1035296465Sdelphij# if 0 1036296465Sdelphij if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) { 1037296465Sdelphij BIGNUM *tmp_bn = (BIGNUM *)b; 1038296465Sdelphij if (bn_wexpand(tmp_bn, al) == NULL) 1039296465Sdelphij goto err; 1040296465Sdelphij tmp_bn->d[bl] = 0; 1041296465Sdelphij bl++; 1042296465Sdelphij i--; 1043296465Sdelphij } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) { 1044296465Sdelphij BIGNUM *tmp_bn = (BIGNUM *)a; 1045296465Sdelphij if (bn_wexpand(tmp_bn, bl) == NULL) 1046296465Sdelphij goto err; 1047296465Sdelphij tmp_bn->d[al] = 0; 1048296465Sdelphij al++; 1049296465Sdelphij i++; 1050296465Sdelphij } 1051296465Sdelphij if (i == 0) { 1052296465Sdelphij /* symmetric and > 4 */ 1053296465Sdelphij /* 16 or larger */ 1054296465Sdelphij j = BN_num_bits_word((BN_ULONG)al); 1055296465Sdelphij j = 1 << (j - 1); 1056296465Sdelphij k = j + j; 1057296465Sdelphij t = BN_CTX_get(ctx); 1058296465Sdelphij if (al == j) { /* exact multiple */ 1059296465Sdelphij if (bn_wexpand(t, k * 2) == NULL) 1060296465Sdelphij goto err; 1061296465Sdelphij if (bn_wexpand(rr, k * 2) == NULL) 1062296465Sdelphij goto err; 1063296465Sdelphij bn_mul_recursive(rr->d, a->d, b->d, al, t->d); 1064296465Sdelphij } else { 1065296465Sdelphij if (bn_wexpand(t, k * 4) == NULL) 1066296465Sdelphij goto err; 1067296465Sdelphij if (bn_wexpand(rr, k * 4) == NULL) 1068296465Sdelphij goto err; 1069296465Sdelphij bn_mul_part_recursive(rr->d, a->d, b->d, al - j, j, t->d); 1070296465Sdelphij } 1071296465Sdelphij rr->top = top; 1072296465Sdelphij goto end; 1073296465Sdelphij } 1074296465Sdelphij# endif 1075296465Sdelphij } 1076296465Sdelphij#endif /* BN_RECURSION */ 1077296465Sdelphij if (bn_wexpand(rr, top) == NULL) 1078296465Sdelphij goto err; 1079296465Sdelphij rr->top = top; 1080296465Sdelphij bn_mul_normal(rr->d, a->d, al, b->d, bl); 1081296465Sdelphij 108255714Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 1083296465Sdelphij end: 108455714Skris#endif 1085296465Sdelphij bn_correct_top(rr); 1086296465Sdelphij if (r != rr) 1087296465Sdelphij BN_copy(r, rr); 1088296465Sdelphij ret = 1; 1089296465Sdelphij err: 1090296465Sdelphij bn_check_top(r); 1091296465Sdelphij BN_CTX_end(ctx); 1092296465Sdelphij return (ret); 1093296465Sdelphij} 109455714Skris 109555714Skrisvoid bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 1096296465Sdelphij{ 1097296465Sdelphij BN_ULONG *rr; 109855714Skris 109955714Skris#ifdef BN_COUNT 1100296465Sdelphij fprintf(stderr, " bn_mul_normal %d * %d\n", na, nb); 110155714Skris#endif 110255714Skris 1103296465Sdelphij if (na < nb) { 1104296465Sdelphij int itmp; 1105296465Sdelphij BN_ULONG *ltmp; 110655714Skris 1107296465Sdelphij itmp = na; 1108296465Sdelphij na = nb; 1109296465Sdelphij nb = itmp; 1110296465Sdelphij ltmp = a; 1111296465Sdelphij a = b; 1112296465Sdelphij b = ltmp; 111355714Skris 1114296465Sdelphij } 1115296465Sdelphij rr = &(r[na]); 1116296465Sdelphij if (nb <= 0) { 1117296465Sdelphij (void)bn_mul_words(r, a, na, 0); 1118296465Sdelphij return; 1119296465Sdelphij } else 1120296465Sdelphij rr[0] = bn_mul_words(r, a, na, b[0]); 112155714Skris 1122296465Sdelphij for (;;) { 1123296465Sdelphij if (--nb <= 0) 1124296465Sdelphij return; 1125296465Sdelphij rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); 1126296465Sdelphij if (--nb <= 0) 1127296465Sdelphij return; 1128296465Sdelphij rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); 1129296465Sdelphij if (--nb <= 0) 1130296465Sdelphij return; 1131296465Sdelphij rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); 1132296465Sdelphij if (--nb <= 0) 1133296465Sdelphij return; 1134296465Sdelphij rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); 1135296465Sdelphij rr += 4; 1136296465Sdelphij r += 4; 1137296465Sdelphij b += 4; 1138296465Sdelphij } 1139296465Sdelphij} 114055714Skris 114155714Skrisvoid bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) 1142296465Sdelphij{ 114355714Skris#ifdef BN_COUNT 1144296465Sdelphij fprintf(stderr, " bn_mul_low_normal %d * %d\n", n, n); 114555714Skris#endif 1146296465Sdelphij bn_mul_words(r, a, n, b[0]); 114755714Skris 1148296465Sdelphij for (;;) { 1149296465Sdelphij if (--n <= 0) 1150296465Sdelphij return; 1151296465Sdelphij bn_mul_add_words(&(r[1]), a, n, b[1]); 1152296465Sdelphij if (--n <= 0) 1153296465Sdelphij return; 1154296465Sdelphij bn_mul_add_words(&(r[2]), a, n, b[2]); 1155296465Sdelphij if (--n <= 0) 1156296465Sdelphij return; 1157296465Sdelphij bn_mul_add_words(&(r[3]), a, n, b[3]); 1158296465Sdelphij if (--n <= 0) 1159296465Sdelphij return; 1160296465Sdelphij bn_mul_add_words(&(r[4]), a, n, b[4]); 1161296465Sdelphij r += 4; 1162296465Sdelphij b += 4; 1163296465Sdelphij } 1164296465Sdelphij} 1165