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. 8280304Sjkim * 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). 15280304Sjkim * 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. 22280304Sjkim * 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 :-). 37280304Sjkim * 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)" 40280304Sjkim * 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. 52280304Sjkim * 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 60280304Sjkim# 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) 70280304Sjkim/* 71280304Sjkim * Here follows specialised variants of bn_add_words() and bn_sub_words(). 72280304Sjkim * They have the property performing operations on arrays of different sizes. 73280304Sjkim * The sizes of those arrays is expressed through cl, which is the common 74280304Sjkim * length ( basicall, min(len(a),len(b)) ), and dl, which is the delta 75280304Sjkim * between the two lengths, calculated as len(a)-len(b). All lengths are the 76280304Sjkim * number of BN_ULONGs... For the operations that require a result array as 77280304Sjkim * parameter, it must have the length cl+abs(dl). These functions should 78280304Sjkim * probably end up in bn_asm.c as soon as there are assembler counterparts 79280304Sjkim * for the systems that use assembler files. 80280304Sjkim */ 81160814Ssimon 82160814SsimonBN_ULONG bn_sub_part_words(BN_ULONG *r, 83280304Sjkim const BN_ULONG *a, const BN_ULONG *b, 84280304Sjkim int cl, int dl) 85280304Sjkim{ 86280304Sjkim BN_ULONG c, t; 87160814Ssimon 88280304Sjkim assert(cl >= 0); 89280304Sjkim c = bn_sub_words(r, a, b, cl); 90160814Ssimon 91280304Sjkim if (dl == 0) 92280304Sjkim return c; 93160814Ssimon 94280304Sjkim r += cl; 95280304Sjkim a += cl; 96280304Sjkim b += cl; 97160814Ssimon 98280304Sjkim if (dl < 0) { 99280304Sjkim# ifdef BN_COUNT 100280304Sjkim fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, 101280304Sjkim dl, c); 102280304Sjkim# endif 103280304Sjkim for (;;) { 104280304Sjkim t = b[0]; 105280304Sjkim r[0] = (0 - t - c) & BN_MASK2; 106280304Sjkim if (t != 0) 107280304Sjkim c = 1; 108280304Sjkim if (++dl >= 0) 109280304Sjkim break; 110160814Ssimon 111280304Sjkim t = b[1]; 112280304Sjkim r[1] = (0 - t - c) & BN_MASK2; 113280304Sjkim if (t != 0) 114280304Sjkim c = 1; 115280304Sjkim if (++dl >= 0) 116280304Sjkim break; 117160814Ssimon 118280304Sjkim t = b[2]; 119280304Sjkim r[2] = (0 - t - c) & BN_MASK2; 120280304Sjkim if (t != 0) 121280304Sjkim c = 1; 122280304Sjkim if (++dl >= 0) 123280304Sjkim break; 124160814Ssimon 125280304Sjkim t = b[3]; 126280304Sjkim r[3] = (0 - t - c) & BN_MASK2; 127280304Sjkim if (t != 0) 128280304Sjkim c = 1; 129280304Sjkim if (++dl >= 0) 130280304Sjkim break; 131160814Ssimon 132280304Sjkim b += 4; 133280304Sjkim r += 4; 134280304Sjkim } 135280304Sjkim } else { 136280304Sjkim int save_dl = dl; 137280304Sjkim# ifdef BN_COUNT 138280304Sjkim fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, 139280304Sjkim dl, c); 140280304Sjkim# endif 141280304Sjkim while (c) { 142280304Sjkim t = a[0]; 143280304Sjkim r[0] = (t - c) & BN_MASK2; 144280304Sjkim if (t != 0) 145280304Sjkim c = 0; 146280304Sjkim if (--dl <= 0) 147280304Sjkim break; 148160814Ssimon 149280304Sjkim t = a[1]; 150280304Sjkim r[1] = (t - c) & BN_MASK2; 151280304Sjkim if (t != 0) 152280304Sjkim c = 0; 153280304Sjkim if (--dl <= 0) 154280304Sjkim break; 155160814Ssimon 156280304Sjkim t = a[2]; 157280304Sjkim r[2] = (t - c) & BN_MASK2; 158280304Sjkim if (t != 0) 159280304Sjkim c = 0; 160280304Sjkim if (--dl <= 0) 161280304Sjkim break; 162160814Ssimon 163280304Sjkim t = a[3]; 164280304Sjkim r[3] = (t - c) & BN_MASK2; 165280304Sjkim if (t != 0) 166280304Sjkim c = 0; 167280304Sjkim if (--dl <= 0) 168280304Sjkim break; 169160814Ssimon 170280304Sjkim save_dl = dl; 171280304Sjkim a += 4; 172280304Sjkim r += 4; 173280304Sjkim } 174280304Sjkim if (dl > 0) { 175280304Sjkim# ifdef BN_COUNT 176280304Sjkim fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", 177280304Sjkim cl, dl); 178280304Sjkim# endif 179280304Sjkim if (save_dl > dl) { 180280304Sjkim switch (save_dl - dl) { 181280304Sjkim case 1: 182280304Sjkim r[1] = a[1]; 183280304Sjkim if (--dl <= 0) 184280304Sjkim break; 185280304Sjkim case 2: 186280304Sjkim r[2] = a[2]; 187280304Sjkim if (--dl <= 0) 188280304Sjkim break; 189280304Sjkim case 3: 190280304Sjkim r[3] = a[3]; 191280304Sjkim if (--dl <= 0) 192280304Sjkim break; 193280304Sjkim } 194280304Sjkim a += 4; 195280304Sjkim r += 4; 196280304Sjkim } 197280304Sjkim } 198280304Sjkim if (dl > 0) { 199280304Sjkim# ifdef BN_COUNT 200280304Sjkim fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", 201280304Sjkim cl, dl); 202280304Sjkim# endif 203280304Sjkim for (;;) { 204280304Sjkim r[0] = a[0]; 205280304Sjkim if (--dl <= 0) 206280304Sjkim break; 207280304Sjkim r[1] = a[1]; 208280304Sjkim if (--dl <= 0) 209280304Sjkim break; 210280304Sjkim r[2] = a[2]; 211280304Sjkim if (--dl <= 0) 212280304Sjkim break; 213280304Sjkim r[3] = a[3]; 214280304Sjkim if (--dl <= 0) 215280304Sjkim break; 216160814Ssimon 217280304Sjkim a += 4; 218280304Sjkim r += 4; 219280304Sjkim } 220280304Sjkim } 221280304Sjkim } 222280304Sjkim return c; 223280304Sjkim} 224160814Ssimon#endif 225160814Ssimon 226160814SsimonBN_ULONG bn_add_part_words(BN_ULONG *r, 227280304Sjkim const BN_ULONG *a, const BN_ULONG *b, 228280304Sjkim int cl, int dl) 229280304Sjkim{ 230280304Sjkim BN_ULONG c, l, t; 231160814Ssimon 232280304Sjkim assert(cl >= 0); 233280304Sjkim c = bn_add_words(r, a, b, cl); 234160814Ssimon 235280304Sjkim if (dl == 0) 236280304Sjkim return c; 237160814Ssimon 238280304Sjkim r += cl; 239280304Sjkim a += cl; 240280304Sjkim b += cl; 241160814Ssimon 242280304Sjkim if (dl < 0) { 243280304Sjkim int save_dl = dl; 244160814Ssimon#ifdef BN_COUNT 245280304Sjkim fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, 246280304Sjkim dl, c); 247160814Ssimon#endif 248280304Sjkim while (c) { 249280304Sjkim l = (c + b[0]) & BN_MASK2; 250280304Sjkim c = (l < c); 251280304Sjkim r[0] = l; 252280304Sjkim if (++dl >= 0) 253280304Sjkim break; 254160814Ssimon 255280304Sjkim l = (c + b[1]) & BN_MASK2; 256280304Sjkim c = (l < c); 257280304Sjkim r[1] = l; 258280304Sjkim if (++dl >= 0) 259280304Sjkim break; 260160814Ssimon 261280304Sjkim l = (c + b[2]) & BN_MASK2; 262280304Sjkim c = (l < c); 263280304Sjkim r[2] = l; 264280304Sjkim if (++dl >= 0) 265280304Sjkim break; 266160814Ssimon 267280304Sjkim l = (c + b[3]) & BN_MASK2; 268280304Sjkim c = (l < c); 269280304Sjkim r[3] = l; 270280304Sjkim if (++dl >= 0) 271280304Sjkim break; 272160814Ssimon 273280304Sjkim save_dl = dl; 274280304Sjkim b += 4; 275280304Sjkim r += 4; 276280304Sjkim } 277280304Sjkim if (dl < 0) { 278160814Ssimon#ifdef BN_COUNT 279280304Sjkim fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", 280280304Sjkim cl, dl); 281160814Ssimon#endif 282280304Sjkim if (save_dl < dl) { 283280304Sjkim switch (dl - save_dl) { 284280304Sjkim case 1: 285280304Sjkim r[1] = b[1]; 286280304Sjkim if (++dl >= 0) 287280304Sjkim break; 288280304Sjkim case 2: 289280304Sjkim r[2] = b[2]; 290280304Sjkim if (++dl >= 0) 291280304Sjkim break; 292280304Sjkim case 3: 293280304Sjkim r[3] = b[3]; 294280304Sjkim if (++dl >= 0) 295280304Sjkim break; 296280304Sjkim } 297280304Sjkim b += 4; 298280304Sjkim r += 4; 299280304Sjkim } 300280304Sjkim } 301280304Sjkim if (dl < 0) { 302160814Ssimon#ifdef BN_COUNT 303280304Sjkim fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", 304280304Sjkim cl, dl); 305160814Ssimon#endif 306280304Sjkim for (;;) { 307280304Sjkim r[0] = b[0]; 308280304Sjkim if (++dl >= 0) 309280304Sjkim break; 310280304Sjkim r[1] = b[1]; 311280304Sjkim if (++dl >= 0) 312280304Sjkim break; 313280304Sjkim r[2] = b[2]; 314280304Sjkim if (++dl >= 0) 315280304Sjkim break; 316280304Sjkim r[3] = b[3]; 317280304Sjkim if (++dl >= 0) 318280304Sjkim break; 319160814Ssimon 320280304Sjkim b += 4; 321280304Sjkim r += 4; 322280304Sjkim } 323280304Sjkim } 324280304Sjkim } else { 325280304Sjkim int save_dl = dl; 326160814Ssimon#ifdef BN_COUNT 327280304Sjkim fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); 328160814Ssimon#endif 329280304Sjkim while (c) { 330280304Sjkim t = (a[0] + c) & BN_MASK2; 331280304Sjkim c = (t < c); 332280304Sjkim r[0] = t; 333280304Sjkim if (--dl <= 0) 334280304Sjkim break; 335160814Ssimon 336280304Sjkim t = (a[1] + c) & BN_MASK2; 337280304Sjkim c = (t < c); 338280304Sjkim r[1] = t; 339280304Sjkim if (--dl <= 0) 340280304Sjkim break; 341160814Ssimon 342280304Sjkim t = (a[2] + c) & BN_MASK2; 343280304Sjkim c = (t < c); 344280304Sjkim r[2] = t; 345280304Sjkim if (--dl <= 0) 346280304Sjkim break; 347160814Ssimon 348280304Sjkim t = (a[3] + c) & BN_MASK2; 349280304Sjkim c = (t < c); 350280304Sjkim r[3] = t; 351280304Sjkim if (--dl <= 0) 352280304Sjkim break; 353160814Ssimon 354280304Sjkim save_dl = dl; 355280304Sjkim a += 4; 356280304Sjkim r += 4; 357280304Sjkim } 358160814Ssimon#ifdef BN_COUNT 359280304Sjkim fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, 360280304Sjkim dl); 361160814Ssimon#endif 362280304Sjkim if (dl > 0) { 363280304Sjkim if (save_dl > dl) { 364280304Sjkim switch (save_dl - dl) { 365280304Sjkim case 1: 366280304Sjkim r[1] = a[1]; 367280304Sjkim if (--dl <= 0) 368280304Sjkim break; 369280304Sjkim case 2: 370280304Sjkim r[2] = a[2]; 371280304Sjkim if (--dl <= 0) 372280304Sjkim break; 373280304Sjkim case 3: 374280304Sjkim r[3] = a[3]; 375280304Sjkim if (--dl <= 0) 376280304Sjkim break; 377280304Sjkim } 378280304Sjkim a += 4; 379280304Sjkim r += 4; 380280304Sjkim } 381280304Sjkim } 382280304Sjkim if (dl > 0) { 383160814Ssimon#ifdef BN_COUNT 384280304Sjkim fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", 385280304Sjkim cl, dl); 386160814Ssimon#endif 387280304Sjkim for (;;) { 388280304Sjkim r[0] = a[0]; 389280304Sjkim if (--dl <= 0) 390280304Sjkim break; 391280304Sjkim r[1] = a[1]; 392280304Sjkim if (--dl <= 0) 393280304Sjkim break; 394280304Sjkim r[2] = a[2]; 395280304Sjkim if (--dl <= 0) 396280304Sjkim break; 397280304Sjkim r[3] = a[3]; 398280304Sjkim if (--dl <= 0) 399280304Sjkim break; 400160814Ssimon 401280304Sjkim a += 4; 402280304Sjkim r += 4; 403280304Sjkim } 404280304Sjkim } 405280304Sjkim } 406280304Sjkim return c; 407280304Sjkim} 408160814Ssimon 40955714Skris#ifdef BN_RECURSION 410280304Sjkim/* 411280304Sjkim * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of 412280304Sjkim * Computer Programming, Vol. 2) 413280304Sjkim */ 41459191Skris 415280304Sjkim/*- 416280304Sjkim * 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, 428280304Sjkim int dna, int dnb, BN_ULONG *t) 429280304Sjkim{ 430280304Sjkim int n = n2 / 2, c1, c2; 431280304Sjkim int tna = n + dna, tnb = n + dnb; 432280304Sjkim unsigned int neg, zero; 433280304Sjkim BN_ULONG ln, lo, *p; 43455714Skris 43559191Skris# ifdef BN_COUNT 436280304Sjkim fprintf(stderr, " bn_mul_recursive %d%+d * %d%+d\n", n2, dna, n2, dnb); 43759191Skris# endif 43859191Skris# ifdef BN_MUL_COMBA 43959191Skris# if 0 440280304Sjkim if (n2 == 4) { 441280304Sjkim bn_mul_comba4(r, a, b); 442280304Sjkim return; 443280304Sjkim } 44459191Skris# endif 445280304Sjkim /* 446280304Sjkim * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete 447280304Sjkim * [steve] 448280304Sjkim */ 449280304Sjkim if (n2 == 8 && dna == 0 && dnb == 0) { 450280304Sjkim bn_mul_comba8(r, a, b); 451280304Sjkim return; 452280304Sjkim } 453280304Sjkim# endif /* BN_MUL_COMBA */ 454280304Sjkim /* Else do normal multiply */ 455280304Sjkim if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { 456280304Sjkim bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); 457280304Sjkim if ((dna + dnb) < 0) 458280304Sjkim memset(&r[2 * n2 + dna + dnb], 0, 459280304Sjkim sizeof(BN_ULONG) * -(dna + dnb)); 460280304Sjkim return; 461280304Sjkim } 462280304Sjkim /* r=(a[0]-a[1])*(b[1]-b[0]) */ 463280304Sjkim c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 464280304Sjkim c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 465280304Sjkim zero = neg = 0; 466280304Sjkim switch (c1 * 3 + c2) { 467280304Sjkim case -4: 468280304Sjkim bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 469280304Sjkim bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 470280304Sjkim break; 471280304Sjkim case -3: 472280304Sjkim zero = 1; 473280304Sjkim break; 474280304Sjkim case -2: 475280304Sjkim bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 476280304Sjkim bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 477280304Sjkim neg = 1; 478280304Sjkim break; 479280304Sjkim case -1: 480280304Sjkim case 0: 481280304Sjkim case 1: 482280304Sjkim zero = 1; 483280304Sjkim break; 484280304Sjkim case 2: 485280304Sjkim bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 486280304Sjkim bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 487280304Sjkim neg = 1; 488280304Sjkim break; 489280304Sjkim case 3: 490280304Sjkim zero = 1; 491280304Sjkim break; 492280304Sjkim case 4: 493280304Sjkim bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 494280304Sjkim bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 495280304Sjkim break; 496280304Sjkim } 49755714Skris 49859191Skris# ifdef BN_MUL_COMBA 499280304Sjkim if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take 500280304Sjkim * extra args to do this well */ 501280304Sjkim if (!zero) 502280304Sjkim bn_mul_comba4(&(t[n2]), t, &(t[n])); 503280304Sjkim else 504280304Sjkim memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG)); 50555714Skris 506280304Sjkim bn_mul_comba4(r, a, b); 507280304Sjkim bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); 508280304Sjkim } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could 509280304Sjkim * take extra args to do 510280304Sjkim * this well */ 511280304Sjkim if (!zero) 512280304Sjkim bn_mul_comba8(&(t[n2]), t, &(t[n])); 513280304Sjkim else 514280304Sjkim memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG)); 51555714Skris 516280304Sjkim bn_mul_comba8(r, a, b); 517280304Sjkim bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n])); 518280304Sjkim } else 519280304Sjkim# endif /* BN_MUL_COMBA */ 520280304Sjkim { 521280304Sjkim p = &(t[n2 * 2]); 522280304Sjkim if (!zero) 523280304Sjkim bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 524280304Sjkim else 525280304Sjkim memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); 526280304Sjkim bn_mul_recursive(r, a, b, n, 0, 0, p); 527280304Sjkim bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); 528280304Sjkim } 52955714Skris 530280304Sjkim /*- 531280304Sjkim * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 532280304Sjkim * r[10] holds (a[0]*b[0]) 533280304Sjkim * r[32] holds (b[1]*b[1]) 534280304Sjkim */ 53555714Skris 536280304Sjkim c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 53755714Skris 538280304Sjkim if (neg) { /* if t[32] is negative */ 539280304Sjkim c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 540280304Sjkim } else { 541280304Sjkim /* Might have a carry */ 542280304Sjkim c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 543280304Sjkim } 54455714Skris 545280304Sjkim /*- 546280304Sjkim * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 547280304Sjkim * r[10] holds (a[0]*b[0]) 548280304Sjkim * r[32] holds (b[1]*b[1]) 549280304Sjkim * c1 holds the carry bits 550280304Sjkim */ 551280304Sjkim c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 552280304Sjkim if (c1) { 553280304Sjkim p = &(r[n + n2]); 554280304Sjkim lo = *p; 555280304Sjkim ln = (lo + c1) & BN_MASK2; 556280304Sjkim *p = ln; 557280304Sjkim 558280304Sjkim /* 559280304Sjkim * The overflow will stop before we over write words we should not 560280304Sjkim * overwrite 561280304Sjkim */ 562280304Sjkim if (ln < (BN_ULONG)c1) { 563280304Sjkim do { 564280304Sjkim p++; 565280304Sjkim lo = *p; 566280304Sjkim ln = (lo + 1) & BN_MASK2; 567280304Sjkim *p = ln; 568280304Sjkim } while (ln == 0); 569280304Sjkim } 570280304Sjkim } 571280304Sjkim} 572280304Sjkim 573280304Sjkim/* 574280304Sjkim * n+tn is the word length t needs to be n*4 is size, as does r 575280304Sjkim */ 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, 578280304Sjkim int tna, int tnb, BN_ULONG *t) 579280304Sjkim{ 580280304Sjkim int i, j, n2 = n * 2; 581280304Sjkim int c1, c2, neg; 582280304Sjkim BN_ULONG ln, lo, *p; 58355714Skris 58459191Skris# ifdef BN_COUNT 585280304Sjkim fprintf(stderr, " bn_mul_part_recursive (%d%+d) * (%d%+d)\n", 586280304Sjkim n, tna, n, tnb); 58759191Skris# endif 588280304Sjkim if (n < 8) { 589280304Sjkim bn_mul_normal(r, a, n + tna, b, n + tnb); 590280304Sjkim return; 591280304Sjkim } 59255714Skris 593280304Sjkim /* r=(a[0]-a[1])*(b[1]-b[0]) */ 594280304Sjkim c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 595280304Sjkim c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 596280304Sjkim neg = 0; 597280304Sjkim switch (c1 * 3 + c2) { 598280304Sjkim case -4: 599280304Sjkim bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 600280304Sjkim bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 601280304Sjkim break; 602280304Sjkim case -3: 603280304Sjkim /* break; */ 604280304Sjkim case -2: 605280304Sjkim bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 606280304Sjkim bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 607280304Sjkim neg = 1; 608280304Sjkim break; 609280304Sjkim case -1: 610280304Sjkim case 0: 611280304Sjkim case 1: 612280304Sjkim /* break; */ 613280304Sjkim case 2: 614280304Sjkim bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 615280304Sjkim bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 616280304Sjkim neg = 1; 617280304Sjkim break; 618280304Sjkim case 3: 619280304Sjkim /* break; */ 620280304Sjkim case 4: 621280304Sjkim bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 622280304Sjkim bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 623280304Sjkim break; 624280304Sjkim } 625280304Sjkim /* 626280304Sjkim * The zero case isn't yet implemented here. The speedup would probably 627280304Sjkim * be negligible. 628280304Sjkim */ 62959191Skris# if 0 630280304Sjkim if (n == 4) { 631280304Sjkim bn_mul_comba4(&(t[n2]), t, &(t[n])); 632280304Sjkim bn_mul_comba4(r, a, b); 633280304Sjkim bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn); 634280304Sjkim memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2)); 635280304Sjkim } else 63659191Skris# endif 637280304Sjkim if (n == 8) { 638280304Sjkim bn_mul_comba8(&(t[n2]), t, &(t[n])); 639280304Sjkim bn_mul_comba8(r, a, b); 640280304Sjkim bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 641280304Sjkim memset(&(r[n2 + tna + tnb]), 0, sizeof(BN_ULONG) * (n2 - tna - tnb)); 642280304Sjkim } else { 643280304Sjkim p = &(t[n2 * 2]); 644280304Sjkim bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 645280304Sjkim bn_mul_recursive(r, a, b, n, 0, 0, p); 646280304Sjkim i = n / 2; 647280304Sjkim /* 648280304Sjkim * If there is only a bottom half to the number, just do it 649280304Sjkim */ 650280304Sjkim if (tna > tnb) 651280304Sjkim j = tna - i; 652280304Sjkim else 653280304Sjkim j = tnb - i; 654280304Sjkim if (j == 0) { 655280304Sjkim bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), 656280304Sjkim i, tna - i, tnb - i, p); 657280304Sjkim memset(&(r[n2 + i * 2]), 0, sizeof(BN_ULONG) * (n2 - i * 2)); 658280304Sjkim } else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */ 659280304Sjkim bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), 660280304Sjkim i, tna - i, tnb - i, p); 661280304Sjkim memset(&(r[n2 + tna + tnb]), 0, 662280304Sjkim sizeof(BN_ULONG) * (n2 - tna - tnb)); 663280304Sjkim } else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 66455714Skris 665280304Sjkim memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2); 666280304Sjkim if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL 667280304Sjkim && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { 668280304Sjkim bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 669280304Sjkim } else { 670280304Sjkim for (;;) { 671280304Sjkim i /= 2; 672280304Sjkim /* 673280304Sjkim * these simplified conditions work exclusively because 674280304Sjkim * difference between tna and tnb is 1 or 0 675280304Sjkim */ 676280304Sjkim if (i < tna || i < tnb) { 677280304Sjkim bn_mul_part_recursive(&(r[n2]), 678280304Sjkim &(a[n]), &(b[n]), 679280304Sjkim i, tna - i, tnb - i, p); 680280304Sjkim break; 681280304Sjkim } else if (i == tna || i == tnb) { 682280304Sjkim bn_mul_recursive(&(r[n2]), 683280304Sjkim &(a[n]), &(b[n]), 684280304Sjkim i, tna - i, tnb - i, p); 685280304Sjkim break; 686280304Sjkim } 687280304Sjkim } 688280304Sjkim } 689280304Sjkim } 690280304Sjkim } 69155714Skris 692280304Sjkim /*- 693280304Sjkim * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 694280304Sjkim * r[10] holds (a[0]*b[0]) 695280304Sjkim * r[32] holds (b[1]*b[1]) 696280304Sjkim */ 69755714Skris 698280304Sjkim c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 69959191Skris 700280304Sjkim if (neg) { /* if t[32] is negative */ 701280304Sjkim c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 702280304Sjkim } else { 703280304Sjkim /* Might have a carry */ 704280304Sjkim c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 705280304Sjkim } 70655714Skris 707280304Sjkim /*- 708280304Sjkim * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 709280304Sjkim * r[10] holds (a[0]*b[0]) 710280304Sjkim * r[32] holds (b[1]*b[1]) 711280304Sjkim * c1 holds the carry bits 712280304Sjkim */ 713280304Sjkim c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 714280304Sjkim if (c1) { 715280304Sjkim p = &(r[n + n2]); 716280304Sjkim lo = *p; 717280304Sjkim ln = (lo + c1) & BN_MASK2; 718280304Sjkim *p = ln; 71955714Skris 720280304Sjkim /* 721280304Sjkim * The overflow will stop before we over write words we should not 722280304Sjkim * overwrite 723280304Sjkim */ 724280304Sjkim if (ln < (BN_ULONG)c1) { 725280304Sjkim do { 726280304Sjkim p++; 727280304Sjkim lo = *p; 728280304Sjkim ln = (lo + 1) & BN_MASK2; 729280304Sjkim *p = ln; 730280304Sjkim } while (ln == 0); 731280304Sjkim } 732280304Sjkim } 733280304Sjkim} 734280304Sjkim 735280304Sjkim/*- 736280304Sjkim * 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, 740280304Sjkim BN_ULONG *t) 741280304Sjkim{ 742280304Sjkim int n = n2 / 2; 74355714Skris 74459191Skris# ifdef BN_COUNT 745280304Sjkim fprintf(stderr, " bn_mul_low_recursive %d * %d\n", n2, n2); 74659191Skris# endif 74755714Skris 748280304Sjkim bn_mul_recursive(r, a, b, n, 0, 0, &(t[0])); 749280304Sjkim if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) { 750280304Sjkim bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2])); 751280304Sjkim bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 752280304Sjkim bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2])); 753280304Sjkim bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 754280304Sjkim } else { 755280304Sjkim bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n); 756280304Sjkim bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n); 757280304Sjkim bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); 758280304Sjkim bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); 759280304Sjkim } 760280304Sjkim} 76155714Skris 762280304Sjkim/*- 763280304Sjkim * 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, 769280304Sjkim BN_ULONG *t) 770280304Sjkim{ 771280304Sjkim int i, n; 772280304Sjkim int c1, c2; 773280304Sjkim int neg, oneg, zero; 774280304Sjkim BN_ULONG ll, lc, *lp, *mp; 77555714Skris 77659191Skris# ifdef BN_COUNT 777280304Sjkim fprintf(stderr, " bn_mul_high %d * %d\n", n2, n2); 77859191Skris# endif 779280304Sjkim n = n2 / 2; 78055714Skris 781280304Sjkim /* Calculate (al-ah)*(bh-bl) */ 782280304Sjkim neg = zero = 0; 783280304Sjkim c1 = bn_cmp_words(&(a[0]), &(a[n]), n); 784280304Sjkim c2 = bn_cmp_words(&(b[n]), &(b[0]), n); 785280304Sjkim switch (c1 * 3 + c2) { 786280304Sjkim case -4: 787280304Sjkim bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); 788280304Sjkim bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); 789280304Sjkim break; 790280304Sjkim case -3: 791280304Sjkim zero = 1; 792280304Sjkim break; 793280304Sjkim case -2: 794280304Sjkim bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); 795280304Sjkim bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); 796280304Sjkim neg = 1; 797280304Sjkim break; 798280304Sjkim case -1: 799280304Sjkim case 0: 800280304Sjkim case 1: 801280304Sjkim zero = 1; 802280304Sjkim break; 803280304Sjkim case 2: 804280304Sjkim bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); 805280304Sjkim bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); 806280304Sjkim neg = 1; 807280304Sjkim break; 808280304Sjkim case 3: 809280304Sjkim zero = 1; 810280304Sjkim break; 811280304Sjkim case 4: 812280304Sjkim bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); 813280304Sjkim bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); 814280304Sjkim break; 815280304Sjkim } 816280304Sjkim 817280304Sjkim oneg = neg; 818280304Sjkim /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ 819280304Sjkim /* r[10] = (a[1]*b[1]) */ 82059191Skris# ifdef BN_MUL_COMBA 821280304Sjkim if (n == 8) { 822280304Sjkim bn_mul_comba8(&(t[0]), &(r[0]), &(r[n])); 823280304Sjkim bn_mul_comba8(r, &(a[n]), &(b[n])); 824280304Sjkim } else 82559191Skris# endif 826280304Sjkim { 827280304Sjkim bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2])); 828280304Sjkim bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); 829280304Sjkim } 83055714Skris 831280304Sjkim /*- 832280304Sjkim * s0 == low(al*bl) 833280304Sjkim * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) 834280304Sjkim * We know s0 and s1 so the only unknown is high(al*bl) 835280304Sjkim * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) 836280304Sjkim * high(al*bl) == s1 - (r[0]+l[0]+t[0]) 837280304Sjkim */ 838280304Sjkim if (l != NULL) { 839280304Sjkim lp = &(t[n2 + n]); 840280304Sjkim c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n)); 841280304Sjkim } else { 842280304Sjkim c1 = 0; 843280304Sjkim lp = &(r[0]); 844280304Sjkim } 84555714Skris 846280304Sjkim if (neg) 847280304Sjkim neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n)); 848280304Sjkim else { 849280304Sjkim bn_add_words(&(t[n2]), lp, &(t[0]), n); 850280304Sjkim neg = 0; 851280304Sjkim } 85255714Skris 853280304Sjkim if (l != NULL) { 854280304Sjkim bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n); 855280304Sjkim } else { 856280304Sjkim lp = &(t[n2 + n]); 857280304Sjkim mp = &(t[n2]); 858280304Sjkim for (i = 0; i < n; i++) 859280304Sjkim lp[i] = ((~mp[i]) + 1) & BN_MASK2; 860280304Sjkim } 86155714Skris 862280304Sjkim /*- 863280304Sjkim * s[0] = low(al*bl) 864280304Sjkim * t[3] = high(al*bl) 865280304Sjkim * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign 866280304Sjkim * r[10] = (a[1]*b[1]) 867280304Sjkim */ 868280304Sjkim /*- 869280304Sjkim * R[10] = al*bl 870280304Sjkim * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) 871280304Sjkim * R[32] = ah*bh 872280304Sjkim */ 873280304Sjkim /*- 874280304Sjkim * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) 875280304Sjkim * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) 876280304Sjkim * R[3]=r[1]+(carry/borrow) 877280304Sjkim */ 878280304Sjkim if (l != NULL) { 879280304Sjkim lp = &(t[n2]); 880280304Sjkim c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); 881280304Sjkim } else { 882280304Sjkim lp = &(t[n2 + n]); 883280304Sjkim c1 = 0; 884280304Sjkim } 885280304Sjkim c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n)); 886280304Sjkim if (oneg) 887280304Sjkim c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n)); 888280304Sjkim else 889280304Sjkim c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n)); 89055714Skris 891280304Sjkim c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n)); 892280304Sjkim c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n)); 893280304Sjkim if (oneg) 894280304Sjkim c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n)); 895280304Sjkim else 896280304Sjkim c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n)); 89755714Skris 898280304Sjkim if (c1 != 0) { /* Add starting at r[0], could be +ve or -ve */ 899280304Sjkim i = 0; 900280304Sjkim if (c1 > 0) { 901280304Sjkim lc = c1; 902280304Sjkim do { 903280304Sjkim ll = (r[i] + lc) & BN_MASK2; 904280304Sjkim r[i++] = ll; 905280304Sjkim lc = (lc > ll); 906280304Sjkim } while (lc); 907280304Sjkim } else { 908280304Sjkim lc = -c1; 909280304Sjkim do { 910280304Sjkim ll = r[i]; 911280304Sjkim r[i++] = (ll - lc) & BN_MASK2; 912280304Sjkim lc = (lc > ll); 913280304Sjkim } while (lc); 914280304Sjkim } 915280304Sjkim } 916280304Sjkim if (c2 != 0) { /* Add starting at r[1] */ 917280304Sjkim i = n; 918280304Sjkim if (c2 > 0) { 919280304Sjkim lc = c2; 920280304Sjkim do { 921280304Sjkim ll = (r[i] + lc) & BN_MASK2; 922280304Sjkim r[i++] = ll; 923280304Sjkim lc = (lc > ll); 924280304Sjkim } while (lc); 925280304Sjkim } else { 926280304Sjkim lc = -c2; 927280304Sjkim do { 928280304Sjkim ll = r[i]; 929280304Sjkim r[i++] = (ll - lc) & BN_MASK2; 930280304Sjkim lc = (lc > ll); 931280304Sjkim } while (lc); 932280304Sjkim } 933280304Sjkim } 934280304Sjkim} 935280304Sjkim#endif /* BN_RECURSION */ 936280304Sjkim 937109998Smarkmint BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 938280304Sjkim{ 939280304Sjkim int ret = 0; 940280304Sjkim int top, al, bl; 941280304Sjkim BIGNUM *rr; 94259191Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 943280304Sjkim int i; 94459191Skris#endif 94555714Skris#ifdef BN_RECURSION 946280304Sjkim BIGNUM *t = NULL; 947280304Sjkim int j = 0, k; 94855714Skris#endif 94955714Skris 95055714Skris#ifdef BN_COUNT 951280304Sjkim fprintf(stderr, "BN_mul %d * %d\n", a->top, b->top); 95255714Skris#endif 95355714Skris 954280304Sjkim bn_check_top(a); 955280304Sjkim bn_check_top(b); 956280304Sjkim bn_check_top(r); 95755714Skris 958280304Sjkim al = a->top; 959280304Sjkim bl = b->top; 96055714Skris 961280304Sjkim if ((al == 0) || (bl == 0)) { 962280304Sjkim BN_zero(r); 963280304Sjkim return (1); 964280304Sjkim } 965280304Sjkim top = al + bl; 96655714Skris 967280304Sjkim BN_CTX_start(ctx); 968280304Sjkim if ((r == a) || (r == b)) { 969280304Sjkim if ((rr = BN_CTX_get(ctx)) == NULL) 970280304Sjkim goto err; 971280304Sjkim } else 972280304Sjkim rr = r; 973280304Sjkim rr->neg = a->neg ^ b->neg; 97455714Skris 97555714Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 976280304Sjkim i = al - bl; 97759191Skris#endif 97859191Skris#ifdef BN_MUL_COMBA 979280304Sjkim if (i == 0) { 98059191Skris# if 0 981280304Sjkim if (al == 4) { 982280304Sjkim if (bn_wexpand(rr, 8) == NULL) 983280304Sjkim goto err; 984280304Sjkim rr->top = 8; 985280304Sjkim bn_mul_comba4(rr->d, a->d, b->d); 986280304Sjkim goto end; 987280304Sjkim } 98859191Skris# endif 989280304Sjkim if (al == 8) { 990280304Sjkim if (bn_wexpand(rr, 16) == NULL) 991280304Sjkim goto err; 992280304Sjkim rr->top = 16; 993280304Sjkim bn_mul_comba8(rr->d, a->d, b->d); 994280304Sjkim goto end; 995280304Sjkim } 996280304Sjkim } 997280304Sjkim#endif /* BN_MUL_COMBA */ 99855714Skris#ifdef BN_RECURSION 999280304Sjkim if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { 1000280304Sjkim if (i >= -1 && i <= 1) { 1001280304Sjkim /* 1002280304Sjkim * Find out the power of two lower or equal to the longest of the 1003280304Sjkim * two numbers 1004280304Sjkim */ 1005280304Sjkim if (i >= 0) { 1006280304Sjkim j = BN_num_bits_word((BN_ULONG)al); 1007280304Sjkim } 1008280304Sjkim if (i == -1) { 1009280304Sjkim j = BN_num_bits_word((BN_ULONG)bl); 1010280304Sjkim } 1011280304Sjkim j = 1 << (j - 1); 1012280304Sjkim assert(j <= al || j <= bl); 1013280304Sjkim k = j + j; 1014280304Sjkim t = BN_CTX_get(ctx); 1015280304Sjkim if (t == NULL) 1016280304Sjkim goto err; 1017280304Sjkim if (al > j || bl > j) { 1018280304Sjkim if (bn_wexpand(t, k * 4) == NULL) 1019280304Sjkim goto err; 1020280304Sjkim if (bn_wexpand(rr, k * 4) == NULL) 1021280304Sjkim goto err; 1022280304Sjkim bn_mul_part_recursive(rr->d, a->d, b->d, 1023280304Sjkim j, al - j, bl - j, t->d); 1024280304Sjkim } else { /* al <= j || bl <= j */ 102555714Skris 1026280304Sjkim if (bn_wexpand(t, k * 2) == NULL) 1027280304Sjkim goto err; 1028280304Sjkim if (bn_wexpand(rr, k * 2) == NULL) 1029280304Sjkim goto err; 1030280304Sjkim bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); 1031280304Sjkim } 1032280304Sjkim rr->top = top; 1033280304Sjkim goto end; 1034280304Sjkim } 1035280304Sjkim# if 0 1036280304Sjkim if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) { 1037280304Sjkim BIGNUM *tmp_bn = (BIGNUM *)b; 1038280304Sjkim if (bn_wexpand(tmp_bn, al) == NULL) 1039280304Sjkim goto err; 1040280304Sjkim tmp_bn->d[bl] = 0; 1041280304Sjkim bl++; 1042280304Sjkim i--; 1043280304Sjkim } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) { 1044280304Sjkim BIGNUM *tmp_bn = (BIGNUM *)a; 1045280304Sjkim if (bn_wexpand(tmp_bn, bl) == NULL) 1046280304Sjkim goto err; 1047280304Sjkim tmp_bn->d[al] = 0; 1048280304Sjkim al++; 1049280304Sjkim i++; 1050280304Sjkim } 1051280304Sjkim if (i == 0) { 1052280304Sjkim /* symmetric and > 4 */ 1053280304Sjkim /* 16 or larger */ 1054280304Sjkim j = BN_num_bits_word((BN_ULONG)al); 1055280304Sjkim j = 1 << (j - 1); 1056280304Sjkim k = j + j; 1057280304Sjkim t = BN_CTX_get(ctx); 1058280304Sjkim if (al == j) { /* exact multiple */ 1059280304Sjkim if (bn_wexpand(t, k * 2) == NULL) 1060280304Sjkim goto err; 1061280304Sjkim if (bn_wexpand(rr, k * 2) == NULL) 1062280304Sjkim goto err; 1063280304Sjkim bn_mul_recursive(rr->d, a->d, b->d, al, t->d); 1064280304Sjkim } else { 1065280304Sjkim if (bn_wexpand(t, k * 4) == NULL) 1066280304Sjkim goto err; 1067280304Sjkim if (bn_wexpand(rr, k * 4) == NULL) 1068280304Sjkim goto err; 1069280304Sjkim bn_mul_part_recursive(rr->d, a->d, b->d, al - j, j, t->d); 1070280304Sjkim } 1071280304Sjkim rr->top = top; 1072280304Sjkim goto end; 1073280304Sjkim } 1074280304Sjkim# endif 1075280304Sjkim } 1076280304Sjkim#endif /* BN_RECURSION */ 1077280304Sjkim if (bn_wexpand(rr, top) == NULL) 1078280304Sjkim goto err; 1079280304Sjkim rr->top = top; 1080280304Sjkim bn_mul_normal(rr->d, a->d, al, b->d, bl); 1081280304Sjkim 108255714Skris#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 1083280304Sjkim end: 108455714Skris#endif 1085280304Sjkim bn_correct_top(rr); 1086280304Sjkim if (r != rr) 1087280304Sjkim BN_copy(r, rr); 1088280304Sjkim ret = 1; 1089280304Sjkim err: 1090280304Sjkim bn_check_top(r); 1091280304Sjkim BN_CTX_end(ctx); 1092280304Sjkim return (ret); 1093280304Sjkim} 109455714Skris 109555714Skrisvoid bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 1096280304Sjkim{ 1097280304Sjkim BN_ULONG *rr; 109855714Skris 109955714Skris#ifdef BN_COUNT 1100280304Sjkim fprintf(stderr, " bn_mul_normal %d * %d\n", na, nb); 110155714Skris#endif 110255714Skris 1103280304Sjkim if (na < nb) { 1104280304Sjkim int itmp; 1105280304Sjkim BN_ULONG *ltmp; 110655714Skris 1107280304Sjkim itmp = na; 1108280304Sjkim na = nb; 1109280304Sjkim nb = itmp; 1110280304Sjkim ltmp = a; 1111280304Sjkim a = b; 1112280304Sjkim b = ltmp; 111355714Skris 1114280304Sjkim } 1115280304Sjkim rr = &(r[na]); 1116280304Sjkim if (nb <= 0) { 1117280304Sjkim (void)bn_mul_words(r, a, na, 0); 1118280304Sjkim return; 1119280304Sjkim } else 1120280304Sjkim rr[0] = bn_mul_words(r, a, na, b[0]); 112155714Skris 1122280304Sjkim for (;;) { 1123280304Sjkim if (--nb <= 0) 1124280304Sjkim return; 1125280304Sjkim rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); 1126280304Sjkim if (--nb <= 0) 1127280304Sjkim return; 1128280304Sjkim rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); 1129280304Sjkim if (--nb <= 0) 1130280304Sjkim return; 1131280304Sjkim rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); 1132280304Sjkim if (--nb <= 0) 1133280304Sjkim return; 1134280304Sjkim rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); 1135280304Sjkim rr += 4; 1136280304Sjkim r += 4; 1137280304Sjkim b += 4; 1138280304Sjkim } 1139280304Sjkim} 114055714Skris 114155714Skrisvoid bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) 1142280304Sjkim{ 114355714Skris#ifdef BN_COUNT 1144280304Sjkim fprintf(stderr, " bn_mul_low_normal %d * %d\n", n, n); 114555714Skris#endif 1146280304Sjkim bn_mul_words(r, a, n, b[0]); 114755714Skris 1148280304Sjkim for (;;) { 1149280304Sjkim if (--n <= 0) 1150280304Sjkim return; 1151280304Sjkim bn_mul_add_words(&(r[1]), a, n, b[1]); 1152280304Sjkim if (--n <= 0) 1153280304Sjkim return; 1154280304Sjkim bn_mul_add_words(&(r[2]), a, n, b[2]); 1155280304Sjkim if (--n <= 0) 1156280304Sjkim return; 1157280304Sjkim bn_mul_add_words(&(r[3]), a, n, b[3]); 1158280304Sjkim if (--n <= 0) 1159280304Sjkim return; 1160280304Sjkim bn_mul_add_words(&(r[4]), a, n, b[4]); 1161280304Sjkim r += 4; 1162280304Sjkim b += 4; 1163280304Sjkim } 1164280304Sjkim} 1165