1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ssl/libcrypto/src/crypto/bn/bn_mul.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,1164 @@
1.4 +/* crypto/bn/bn_mul.c */
1.5 +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
1.6 + * All rights reserved.
1.7 + *
1.8 + * This package is an SSL implementation written
1.9 + * by Eric Young (eay@cryptsoft.com).
1.10 + * The implementation was written so as to conform with Netscapes SSL.
1.11 + *
1.12 + * This library is free for commercial and non-commercial use as long as
1.13 + * the following conditions are aheared to. The following conditions
1.14 + * apply to all code found in this distribution, be it the RC4, RSA,
1.15 + * lhash, DES, etc., code; not just the SSL code. The SSL documentation
1.16 + * included with this distribution is covered by the same copyright terms
1.17 + * except that the holder is Tim Hudson (tjh@cryptsoft.com).
1.18 + *
1.19 + * Copyright remains Eric Young's, and as such any Copyright notices in
1.20 + * the code are not to be removed.
1.21 + * If this package is used in a product, Eric Young should be given attribution
1.22 + * as the author of the parts of the library used.
1.23 + * This can be in the form of a textual message at program startup or
1.24 + * in documentation (online or textual) provided with the package.
1.25 + *
1.26 + * Redistribution and use in source and binary forms, with or without
1.27 + * modification, are permitted provided that the following conditions
1.28 + * are met:
1.29 + * 1. Redistributions of source code must retain the copyright
1.30 + * notice, this list of conditions and the following disclaimer.
1.31 + * 2. Redistributions in binary form must reproduce the above copyright
1.32 + * notice, this list of conditions and the following disclaimer in the
1.33 + * documentation and/or other materials provided with the distribution.
1.34 + * 3. All advertising materials mentioning features or use of this software
1.35 + * must display the following acknowledgement:
1.36 + * "This product includes cryptographic software written by
1.37 + * Eric Young (eay@cryptsoft.com)"
1.38 + * The word 'cryptographic' can be left out if the rouines from the library
1.39 + * being used are not cryptographic related :-).
1.40 + * 4. If you include any Windows specific code (or a derivative thereof) from
1.41 + * the apps directory (application code) you must include an acknowledgement:
1.42 + * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
1.43 + *
1.44 + * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
1.45 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.46 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.47 + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
1.48 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.49 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.50 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.51 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.52 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.53 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.54 + * SUCH DAMAGE.
1.55 + *
1.56 + * The licence and distribution terms for any publically available version or
1.57 + * derivative of this code cannot be changed. i.e. this code cannot simply be
1.58 + * copied and put under another distribution licence
1.59 + * [including the GNU Public Licence.]
1.60 + */
1.61 +
1.62 +#ifndef BN_DEBUG
1.63 +# undef NDEBUG /* avoid conflicting definitions */
1.64 +# define NDEBUG
1.65 +#endif
1.66 +
1.67 +#include <stdio.h>
1.68 +#include <assert.h>
1.69 +#include "cryptlib.h"
1.70 +#include "bn_lcl.h"
1.71 +
1.72 +#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
1.73 +/* Here follows specialised variants of bn_add_words() and
1.74 + bn_sub_words(). They have the property performing operations on
1.75 + arrays of different sizes. The sizes of those arrays is expressed through
1.76 + cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl,
1.77 + which is the delta between the two lengths, calculated as len(a)-len(b).
1.78 + All lengths are the number of BN_ULONGs... For the operations that require
1.79 + a result array as parameter, it must have the length cl+abs(dl).
1.80 + These functions should probably end up in bn_asm.c as soon as there are
1.81 + assembler counterparts for the systems that use assembler files. */
1.82 +
1.83 +EXPORT_C BN_ULONG bn_sub_part_words(BN_ULONG *r,
1.84 + const BN_ULONG *a, const BN_ULONG *b,
1.85 + int cl, int dl)
1.86 + {
1.87 + BN_ULONG c, t;
1.88 +
1.89 + assert(cl >= 0);
1.90 + c = bn_sub_words(r, a, b, cl);
1.91 +
1.92 + if (dl == 0)
1.93 + return c;
1.94 +
1.95 + r += cl;
1.96 + a += cl;
1.97 + b += cl;
1.98 +
1.99 + if (dl < 0)
1.100 + {
1.101 +#ifdef BN_COUNT
1.102 + fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c);
1.103 +#endif
1.104 + for (;;)
1.105 + {
1.106 + t = b[0];
1.107 + r[0] = (0-t-c)&BN_MASK2;
1.108 + if (t != 0) c=1;
1.109 + if (++dl >= 0) break;
1.110 +
1.111 + t = b[1];
1.112 + r[1] = (0-t-c)&BN_MASK2;
1.113 + if (t != 0) c=1;
1.114 + if (++dl >= 0) break;
1.115 +
1.116 + t = b[2];
1.117 + r[2] = (0-t-c)&BN_MASK2;
1.118 + if (t != 0) c=1;
1.119 + if (++dl >= 0) break;
1.120 +
1.121 + t = b[3];
1.122 + r[3] = (0-t-c)&BN_MASK2;
1.123 + if (t != 0) c=1;
1.124 + if (++dl >= 0) break;
1.125 +
1.126 + b += 4;
1.127 + r += 4;
1.128 + }
1.129 + }
1.130 + else
1.131 + {
1.132 + int save_dl = dl;
1.133 +#ifdef BN_COUNT
1.134 + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c);
1.135 +#endif
1.136 + while(c)
1.137 + {
1.138 + t = a[0];
1.139 + r[0] = (t-c)&BN_MASK2;
1.140 + if (t != 0) c=0;
1.141 + if (--dl <= 0) break;
1.142 +
1.143 + t = a[1];
1.144 + r[1] = (t-c)&BN_MASK2;
1.145 + if (t != 0) c=0;
1.146 + if (--dl <= 0) break;
1.147 +
1.148 + t = a[2];
1.149 + r[2] = (t-c)&BN_MASK2;
1.150 + if (t != 0) c=0;
1.151 + if (--dl <= 0) break;
1.152 +
1.153 + t = a[3];
1.154 + r[3] = (t-c)&BN_MASK2;
1.155 + if (t != 0) c=0;
1.156 + if (--dl <= 0) break;
1.157 +
1.158 + save_dl = dl;
1.159 + a += 4;
1.160 + r += 4;
1.161 + }
1.162 + if (dl > 0)
1.163 + {
1.164 +#ifdef BN_COUNT
1.165 + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl);
1.166 +#endif
1.167 + if (save_dl > dl)
1.168 + {
1.169 + switch (save_dl - dl)
1.170 + {
1.171 + case 1:
1.172 + r[1] = a[1];
1.173 + if (--dl <= 0) break;
1.174 + case 2:
1.175 + r[2] = a[2];
1.176 + if (--dl <= 0) break;
1.177 + case 3:
1.178 + r[3] = a[3];
1.179 + if (--dl <= 0) break;
1.180 + }
1.181 + a += 4;
1.182 + r += 4;
1.183 + }
1.184 + }
1.185 + if (dl > 0)
1.186 + {
1.187 +#ifdef BN_COUNT
1.188 + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl);
1.189 +#endif
1.190 + for(;;)
1.191 + {
1.192 + r[0] = a[0];
1.193 + if (--dl <= 0) break;
1.194 + r[1] = a[1];
1.195 + if (--dl <= 0) break;
1.196 + r[2] = a[2];
1.197 + if (--dl <= 0) break;
1.198 + r[3] = a[3];
1.199 + if (--dl <= 0) break;
1.200 +
1.201 + a += 4;
1.202 + r += 4;
1.203 + }
1.204 + }
1.205 + }
1.206 + return c;
1.207 + }
1.208 +#endif
1.209 +
1.210 +EXPORT_C BN_ULONG bn_add_part_words(BN_ULONG *r,
1.211 + const BN_ULONG *a, const BN_ULONG *b,
1.212 + int cl, int dl)
1.213 + {
1.214 + BN_ULONG c, l, t;
1.215 +
1.216 + assert(cl >= 0);
1.217 + c = bn_add_words(r, a, b, cl);
1.218 +
1.219 + if (dl == 0)
1.220 + return c;
1.221 +
1.222 + r += cl;
1.223 + a += cl;
1.224 + b += cl;
1.225 +
1.226 + if (dl < 0)
1.227 + {
1.228 + int save_dl = dl;
1.229 +#ifdef BN_COUNT
1.230 + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c);
1.231 +#endif
1.232 + while (c)
1.233 + {
1.234 + l=(c+b[0])&BN_MASK2;
1.235 + c=(l < c);
1.236 + r[0]=l;
1.237 + if (++dl >= 0) break;
1.238 +
1.239 + l=(c+b[1])&BN_MASK2;
1.240 + c=(l < c);
1.241 + r[1]=l;
1.242 + if (++dl >= 0) break;
1.243 +
1.244 + l=(c+b[2])&BN_MASK2;
1.245 + c=(l < c);
1.246 + r[2]=l;
1.247 + if (++dl >= 0) break;
1.248 +
1.249 + l=(c+b[3])&BN_MASK2;
1.250 + c=(l < c);
1.251 + r[3]=l;
1.252 + if (++dl >= 0) break;
1.253 +
1.254 + save_dl = dl;
1.255 + b+=4;
1.256 + r+=4;
1.257 + }
1.258 + if (dl < 0)
1.259 + {
1.260 +#ifdef BN_COUNT
1.261 + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl);
1.262 +#endif
1.263 + if (save_dl < dl)
1.264 + {
1.265 + switch (dl - save_dl)
1.266 + {
1.267 + case 1:
1.268 + r[1] = b[1];
1.269 + if (++dl >= 0) break;
1.270 + case 2:
1.271 + r[2] = b[2];
1.272 + if (++dl >= 0) break;
1.273 + case 3:
1.274 + r[3] = b[3];
1.275 + if (++dl >= 0) break;
1.276 + }
1.277 + b += 4;
1.278 + r += 4;
1.279 + }
1.280 + }
1.281 + if (dl < 0)
1.282 + {
1.283 +#ifdef BN_COUNT
1.284 + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl);
1.285 +#endif
1.286 + for(;;)
1.287 + {
1.288 + r[0] = b[0];
1.289 + if (++dl >= 0) break;
1.290 + r[1] = b[1];
1.291 + if (++dl >= 0) break;
1.292 + r[2] = b[2];
1.293 + if (++dl >= 0) break;
1.294 + r[3] = b[3];
1.295 + if (++dl >= 0) break;
1.296 +
1.297 + b += 4;
1.298 + r += 4;
1.299 + }
1.300 + }
1.301 + }
1.302 + else
1.303 + {
1.304 + int save_dl = dl;
1.305 +#ifdef BN_COUNT
1.306 + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl);
1.307 +#endif
1.308 + while (c)
1.309 + {
1.310 + t=(a[0]+c)&BN_MASK2;
1.311 + c=(t < c);
1.312 + r[0]=t;
1.313 + if (--dl <= 0) break;
1.314 +
1.315 + t=(a[1]+c)&BN_MASK2;
1.316 + c=(t < c);
1.317 + r[1]=t;
1.318 + if (--dl <= 0) break;
1.319 +
1.320 + t=(a[2]+c)&BN_MASK2;
1.321 + c=(t < c);
1.322 + r[2]=t;
1.323 + if (--dl <= 0) break;
1.324 +
1.325 + t=(a[3]+c)&BN_MASK2;
1.326 + c=(t < c);
1.327 + r[3]=t;
1.328 + if (--dl <= 0) break;
1.329 +
1.330 + save_dl = dl;
1.331 + a+=4;
1.332 + r+=4;
1.333 + }
1.334 +#ifdef BN_COUNT
1.335 + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl);
1.336 +#endif
1.337 + if (dl > 0)
1.338 + {
1.339 + if (save_dl > dl)
1.340 + {
1.341 + switch (save_dl - dl)
1.342 + {
1.343 + case 1:
1.344 + r[1] = a[1];
1.345 + if (--dl <= 0) break;
1.346 + case 2:
1.347 + r[2] = a[2];
1.348 + if (--dl <= 0) break;
1.349 + case 3:
1.350 + r[3] = a[3];
1.351 + if (--dl <= 0) break;
1.352 + }
1.353 + a += 4;
1.354 + r += 4;
1.355 + }
1.356 + }
1.357 + if (dl > 0)
1.358 + {
1.359 +#ifdef BN_COUNT
1.360 + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl);
1.361 +#endif
1.362 + for(;;)
1.363 + {
1.364 + r[0] = a[0];
1.365 + if (--dl <= 0) break;
1.366 + r[1] = a[1];
1.367 + if (--dl <= 0) break;
1.368 + r[2] = a[2];
1.369 + if (--dl <= 0) break;
1.370 + r[3] = a[3];
1.371 + if (--dl <= 0) break;
1.372 +
1.373 + a += 4;
1.374 + r += 4;
1.375 + }
1.376 + }
1.377 + }
1.378 + return c;
1.379 + }
1.380 +
1.381 +#ifdef BN_RECURSION
1.382 +/* Karatsuba recursive multiplication algorithm
1.383 + * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
1.384 +
1.385 +/* r is 2*n2 words in size,
1.386 + * a and b are both n2 words in size.
1.387 + * n2 must be a power of 2.
1.388 + * We multiply and return the result.
1.389 + * t must be 2*n2 words in size
1.390 + * We calculate
1.391 + * a[0]*b[0]
1.392 + * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
1.393 + * a[1]*b[1]
1.394 + */
1.395 +EXPORT_C void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
1.396 + int dna, int dnb, BN_ULONG *t)
1.397 + {
1.398 + int n=n2/2,c1,c2;
1.399 + int tna=n+dna, tnb=n+dnb;
1.400 + unsigned int neg,zero;
1.401 + BN_ULONG ln,lo,*p;
1.402 +
1.403 +# ifdef BN_COUNT
1.404 + fprintf(stderr," bn_mul_recursive %d * %d\n",n2,n2);
1.405 +# endif
1.406 +# ifdef BN_MUL_COMBA
1.407 +# if 0
1.408 + if (n2 == 4)
1.409 + {
1.410 + bn_mul_comba4(r,a,b);
1.411 + return;
1.412 + }
1.413 +# endif
1.414 + /* Only call bn_mul_comba 8 if n2 == 8 and the
1.415 + * two arrays are complete [steve]
1.416 + */
1.417 + if (n2 == 8 && dna == 0 && dnb == 0)
1.418 + {
1.419 + bn_mul_comba8(r,a,b);
1.420 + return;
1.421 + }
1.422 +# endif /* BN_MUL_COMBA */
1.423 + /* Else do normal multiply */
1.424 + if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
1.425 + {
1.426 + bn_mul_normal(r,a,n2+dna,b,n2+dnb);
1.427 + if ((dna + dnb) < 0)
1.428 + memset(&r[2*n2 + dna + dnb], 0,
1.429 + sizeof(BN_ULONG) * -(dna + dnb));
1.430 + return;
1.431 + }
1.432 + /* r=(a[0]-a[1])*(b[1]-b[0]) */
1.433 + c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna);
1.434 + c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n);
1.435 + zero=neg=0;
1.436 + switch (c1*3+c2)
1.437 + {
1.438 + case -4:
1.439 + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */
1.440 + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */
1.441 + break;
1.442 + case -3:
1.443 + zero=1;
1.444 + break;
1.445 + case -2:
1.446 + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */
1.447 + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */
1.448 + neg=1;
1.449 + break;
1.450 + case -1:
1.451 + case 0:
1.452 + case 1:
1.453 + zero=1;
1.454 + break;
1.455 + case 2:
1.456 + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */
1.457 + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */
1.458 + neg=1;
1.459 + break;
1.460 + case 3:
1.461 + zero=1;
1.462 + break;
1.463 + case 4:
1.464 + bn_sub_part_words(t, a, &(a[n]),tna,n-tna);
1.465 + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n);
1.466 + break;
1.467 + }
1.468 +
1.469 +# ifdef BN_MUL_COMBA
1.470 + if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take
1.471 + extra args to do this well */
1.472 + {
1.473 + if (!zero)
1.474 + bn_mul_comba4(&(t[n2]),t,&(t[n]));
1.475 + else
1.476 + memset(&(t[n2]),0,8*sizeof(BN_ULONG));
1.477 +
1.478 + bn_mul_comba4(r,a,b);
1.479 + bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n]));
1.480 + }
1.481 + else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could
1.482 + take extra args to do this
1.483 + well */
1.484 + {
1.485 + if (!zero)
1.486 + bn_mul_comba8(&(t[n2]),t,&(t[n]));
1.487 + else
1.488 + memset(&(t[n2]),0,16*sizeof(BN_ULONG));
1.489 +
1.490 + bn_mul_comba8(r,a,b);
1.491 + bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
1.492 + }
1.493 + else
1.494 +# endif /* BN_MUL_COMBA */
1.495 + {
1.496 + p= &(t[n2*2]);
1.497 + if (!zero)
1.498 + bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p);
1.499 + else
1.500 + memset(&(t[n2]),0,n2*sizeof(BN_ULONG));
1.501 + bn_mul_recursive(r,a,b,n,0,0,p);
1.502 + bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,dna,dnb,p);
1.503 + }
1.504 +
1.505 + /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
1.506 + * r[10] holds (a[0]*b[0])
1.507 + * r[32] holds (b[1]*b[1])
1.508 + */
1.509 +
1.510 + c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
1.511 +
1.512 + if (neg) /* if t[32] is negative */
1.513 + {
1.514 + c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
1.515 + }
1.516 + else
1.517 + {
1.518 + /* Might have a carry */
1.519 + c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
1.520 + }
1.521 +
1.522 + /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
1.523 + * r[10] holds (a[0]*b[0])
1.524 + * r[32] holds (b[1]*b[1])
1.525 + * c1 holds the carry bits
1.526 + */
1.527 + c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
1.528 + if (c1)
1.529 + {
1.530 + p= &(r[n+n2]);
1.531 + lo= *p;
1.532 + ln=(lo+c1)&BN_MASK2;
1.533 + *p=ln;
1.534 +
1.535 + /* The overflow will stop before we over write
1.536 + * words we should not overwrite */
1.537 + if (ln < (BN_ULONG)c1)
1.538 + {
1.539 + do {
1.540 + p++;
1.541 + lo= *p;
1.542 + ln=(lo+1)&BN_MASK2;
1.543 + *p=ln;
1.544 + } while (ln == 0);
1.545 + }
1.546 + }
1.547 + }
1.548 +
1.549 +/* n+tn is the word length
1.550 + * t needs to be n*4 is size, as does r */
1.551 +EXPORT_C void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
1.552 + int tna, int tnb, BN_ULONG *t)
1.553 + {
1.554 + int i,j,n2=n*2;
1.555 + int c1,c2,neg,zero;
1.556 + BN_ULONG ln,lo,*p;
1.557 +
1.558 +# ifdef BN_COUNT
1.559 + fprintf(stderr," bn_mul_part_recursive (%d+%d) * (%d+%d)\n",
1.560 + tna, n, tnb, n);
1.561 +# endif
1.562 + if (n < 8)
1.563 + {
1.564 + bn_mul_normal(r,a,n+tna,b,n+tnb);
1.565 + return;
1.566 + }
1.567 +
1.568 + /* r=(a[0]-a[1])*(b[1]-b[0]) */
1.569 + c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna);
1.570 + c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n);
1.571 + zero=neg=0;
1.572 + switch (c1*3+c2)
1.573 + {
1.574 + case -4:
1.575 + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */
1.576 + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */
1.577 + break;
1.578 + case -3:
1.579 + zero=1;
1.580 + /* break; */
1.581 + case -2:
1.582 + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */
1.583 + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */
1.584 + neg=1;
1.585 + break;
1.586 + case -1:
1.587 + case 0:
1.588 + case 1:
1.589 + zero=1;
1.590 + /* break; */
1.591 + case 2:
1.592 + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */
1.593 + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */
1.594 + neg=1;
1.595 + break;
1.596 + case 3:
1.597 + zero=1;
1.598 + /* break; */
1.599 + case 4:
1.600 + bn_sub_part_words(t, a, &(a[n]),tna,n-tna);
1.601 + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n);
1.602 + break;
1.603 + }
1.604 + /* The zero case isn't yet implemented here. The speedup
1.605 + would probably be negligible. */
1.606 +# if 0
1.607 + if (n == 4)
1.608 + {
1.609 + bn_mul_comba4(&(t[n2]),t,&(t[n]));
1.610 + bn_mul_comba4(r,a,b);
1.611 + bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
1.612 + memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
1.613 + }
1.614 + else
1.615 +# endif
1.616 + if (n == 8)
1.617 + {
1.618 + bn_mul_comba8(&(t[n2]),t,&(t[n]));
1.619 + bn_mul_comba8(r,a,b);
1.620 + bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb);
1.621 + memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb));
1.622 + }
1.623 + else
1.624 + {
1.625 + p= &(t[n2*2]);
1.626 + bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p);
1.627 + bn_mul_recursive(r,a,b,n,0,0,p);
1.628 + i=n/2;
1.629 + /* If there is only a bottom half to the number,
1.630 + * just do it */
1.631 + if (tna > tnb)
1.632 + j = tna - i;
1.633 + else
1.634 + j = tnb - i;
1.635 + if (j == 0)
1.636 + {
1.637 + bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),
1.638 + i,tna-i,tnb-i,p);
1.639 + memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
1.640 + }
1.641 + else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
1.642 + {
1.643 + bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
1.644 + i,tna-i,tnb-i,p);
1.645 + memset(&(r[n2+tna+tnb]),0,
1.646 + sizeof(BN_ULONG)*(n2-tna-tnb));
1.647 + }
1.648 + else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
1.649 + {
1.650 + memset(&(r[n2]),0,sizeof(BN_ULONG)*n2);
1.651 + if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
1.652 + && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL)
1.653 + {
1.654 + bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb);
1.655 + }
1.656 + else
1.657 + {
1.658 + for (;;)
1.659 + {
1.660 + i/=2;
1.661 + if (i <= tna && tna == tnb)
1.662 + {
1.663 + bn_mul_recursive(&(r[n2]),
1.664 + &(a[n]),&(b[n]),
1.665 + i,tna-i,tnb-i,p);
1.666 + break;
1.667 + }
1.668 + else if (i < tna || i < tnb)
1.669 + {
1.670 + bn_mul_part_recursive(&(r[n2]),
1.671 + &(a[n]),&(b[n]),
1.672 + i,tna-i,tnb-i,p);
1.673 + break;
1.674 + }
1.675 + }
1.676 + }
1.677 + }
1.678 + }
1.679 +
1.680 + /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
1.681 + * r[10] holds (a[0]*b[0])
1.682 + * r[32] holds (b[1]*b[1])
1.683 + */
1.684 +
1.685 + c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
1.686 +
1.687 + if (neg) /* if t[32] is negative */
1.688 + {
1.689 + c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
1.690 + }
1.691 + else
1.692 + {
1.693 + /* Might have a carry */
1.694 + c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
1.695 + }
1.696 +
1.697 + /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
1.698 + * r[10] holds (a[0]*b[0])
1.699 + * r[32] holds (b[1]*b[1])
1.700 + * c1 holds the carry bits
1.701 + */
1.702 + c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
1.703 + if (c1)
1.704 + {
1.705 + p= &(r[n+n2]);
1.706 + lo= *p;
1.707 + ln=(lo+c1)&BN_MASK2;
1.708 + *p=ln;
1.709 +
1.710 + /* The overflow will stop before we over write
1.711 + * words we should not overwrite */
1.712 + if (ln < (BN_ULONG)c1)
1.713 + {
1.714 + do {
1.715 + p++;
1.716 + lo= *p;
1.717 + ln=(lo+1)&BN_MASK2;
1.718 + *p=ln;
1.719 + } while (ln == 0);
1.720 + }
1.721 + }
1.722 + }
1.723 +
1.724 +/* a and b must be the same size, which is n2.
1.725 + * r needs to be n2 words and t needs to be n2*2
1.726 + */
1.727 +EXPORT_C void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
1.728 + BN_ULONG *t)
1.729 + {
1.730 + int n=n2/2;
1.731 +
1.732 +# ifdef BN_COUNT
1.733 + fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2);
1.734 +# endif
1.735 +
1.736 + bn_mul_recursive(r,a,b,n,0,0,&(t[0]));
1.737 + if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
1.738 + {
1.739 + bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
1.740 + bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
1.741 + bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
1.742 + bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
1.743 + }
1.744 + else
1.745 + {
1.746 + bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
1.747 + bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
1.748 + bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
1.749 + bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
1.750 + }
1.751 + }
1.752 +
1.753 +/* a and b must be the same size, which is n2.
1.754 + * r needs to be n2 words and t needs to be n2*2
1.755 + * l is the low words of the output.
1.756 + * t needs to be n2*3
1.757 + */
1.758 +EXPORT_C void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
1.759 + BN_ULONG *t)
1.760 + {
1.761 + int i,n;
1.762 + int c1,c2;
1.763 + int neg,oneg,zero;
1.764 + BN_ULONG ll,lc,*lp,*mp;
1.765 +
1.766 +# ifdef BN_COUNT
1.767 + fprintf(stderr," bn_mul_high %d * %d\n",n2,n2);
1.768 +# endif
1.769 + n=n2/2;
1.770 +
1.771 + /* Calculate (al-ah)*(bh-bl) */
1.772 + neg=zero=0;
1.773 + c1=bn_cmp_words(&(a[0]),&(a[n]),n);
1.774 + c2=bn_cmp_words(&(b[n]),&(b[0]),n);
1.775 + switch (c1*3+c2)
1.776 + {
1.777 + case -4:
1.778 + bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
1.779 + bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
1.780 + break;
1.781 + case -3:
1.782 + zero=1;
1.783 + break;
1.784 + case -2:
1.785 + bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
1.786 + bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
1.787 + neg=1;
1.788 + break;
1.789 + case -1:
1.790 + case 0:
1.791 + case 1:
1.792 + zero=1;
1.793 + break;
1.794 + case 2:
1.795 + bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
1.796 + bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
1.797 + neg=1;
1.798 + break;
1.799 + case 3:
1.800 + zero=1;
1.801 + break;
1.802 + case 4:
1.803 + bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
1.804 + bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
1.805 + break;
1.806 + }
1.807 +
1.808 + oneg=neg;
1.809 + /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
1.810 + /* r[10] = (a[1]*b[1]) */
1.811 +# ifdef BN_MUL_COMBA
1.812 + if (n == 8)
1.813 + {
1.814 + bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
1.815 + bn_mul_comba8(r,&(a[n]),&(b[n]));
1.816 + }
1.817 + else
1.818 +# endif
1.819 + {
1.820 + bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2]));
1.821 + bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2]));
1.822 + }
1.823 +
1.824 + /* s0 == low(al*bl)
1.825 + * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
1.826 + * We know s0 and s1 so the only unknown is high(al*bl)
1.827 + * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
1.828 + * high(al*bl) == s1 - (r[0]+l[0]+t[0])
1.829 + */
1.830 + if (l != NULL)
1.831 + {
1.832 + lp= &(t[n2+n]);
1.833 + c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n));
1.834 + }
1.835 + else
1.836 + {
1.837 + c1=0;
1.838 + lp= &(r[0]);
1.839 + }
1.840 +
1.841 + if (neg)
1.842 + neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n));
1.843 + else
1.844 + {
1.845 + bn_add_words(&(t[n2]),lp,&(t[0]),n);
1.846 + neg=0;
1.847 + }
1.848 +
1.849 + if (l != NULL)
1.850 + {
1.851 + bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
1.852 + }
1.853 + else
1.854 + {
1.855 + lp= &(t[n2+n]);
1.856 + mp= &(t[n2]);
1.857 + for (i=0; i<n; i++)
1.858 + lp[i]=((~mp[i])+1)&BN_MASK2;
1.859 + }
1.860 +
1.861 + /* s[0] = low(al*bl)
1.862 + * t[3] = high(al*bl)
1.863 + * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
1.864 + * r[10] = (a[1]*b[1])
1.865 + */
1.866 + /* R[10] = al*bl
1.867 + * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
1.868 + * R[32] = ah*bh
1.869 + */
1.870 + /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
1.871 + * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
1.872 + * R[3]=r[1]+(carry/borrow)
1.873 + */
1.874 + if (l != NULL)
1.875 + {
1.876 + lp= &(t[n2]);
1.877 + c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n));
1.878 + }
1.879 + else
1.880 + {
1.881 + lp= &(t[n2+n]);
1.882 + c1=0;
1.883 + }
1.884 + c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n));
1.885 + if (oneg)
1.886 + c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n));
1.887 + else
1.888 + c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n));
1.889 +
1.890 + c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n));
1.891 + c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n));
1.892 + if (oneg)
1.893 + c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n));
1.894 + else
1.895 + c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n));
1.896 +
1.897 + if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
1.898 + {
1.899 + i=0;
1.900 + if (c1 > 0)
1.901 + {
1.902 + lc=c1;
1.903 + do {
1.904 + ll=(r[i]+lc)&BN_MASK2;
1.905 + r[i++]=ll;
1.906 + lc=(lc > ll);
1.907 + } while (lc);
1.908 + }
1.909 + else
1.910 + {
1.911 + lc= -c1;
1.912 + do {
1.913 + ll=r[i];
1.914 + r[i++]=(ll-lc)&BN_MASK2;
1.915 + lc=(lc > ll);
1.916 + } while (lc);
1.917 + }
1.918 + }
1.919 + if (c2 != 0) /* Add starting at r[1] */
1.920 + {
1.921 + i=n;
1.922 + if (c2 > 0)
1.923 + {
1.924 + lc=c2;
1.925 + do {
1.926 + ll=(r[i]+lc)&BN_MASK2;
1.927 + r[i++]=ll;
1.928 + lc=(lc > ll);
1.929 + } while (lc);
1.930 + }
1.931 + else
1.932 + {
1.933 + lc= -c2;
1.934 + do {
1.935 + ll=r[i];
1.936 + r[i++]=(ll-lc)&BN_MASK2;
1.937 + lc=(lc > ll);
1.938 + } while (lc);
1.939 + }
1.940 + }
1.941 + }
1.942 +#endif /* BN_RECURSION */
1.943 +
1.944 +EXPORT_C int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1.945 + {
1.946 + int ret=0;
1.947 + int top,al,bl;
1.948 + BIGNUM *rr;
1.949 +#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
1.950 + int i;
1.951 +#endif
1.952 +#ifdef BN_RECURSION
1.953 + BIGNUM *t=NULL;
1.954 + int j=0,k;
1.955 +#endif
1.956 +
1.957 +#ifdef BN_COUNT
1.958 + fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top);
1.959 +#endif
1.960 +
1.961 + bn_check_top(a);
1.962 + bn_check_top(b);
1.963 + bn_check_top(r);
1.964 +
1.965 + al=a->top;
1.966 + bl=b->top;
1.967 +
1.968 + if ((al == 0) || (bl == 0))
1.969 + {
1.970 + BN_zero(r);
1.971 + return(1);
1.972 + }
1.973 + top=al+bl;
1.974 +
1.975 + BN_CTX_start(ctx);
1.976 + if ((r == a) || (r == b))
1.977 + {
1.978 + if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
1.979 + }
1.980 + else
1.981 + rr = r;
1.982 + rr->neg=a->neg^b->neg;
1.983 +
1.984 +#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
1.985 + i = al-bl;
1.986 +#endif
1.987 +#ifdef BN_MUL_COMBA
1.988 + if (i == 0)
1.989 + {
1.990 +# if 0
1.991 + if (al == 4)
1.992 + {
1.993 + if (bn_wexpand(rr,8) == NULL) goto err;
1.994 + rr->top=8;
1.995 + bn_mul_comba4(rr->d,a->d,b->d);
1.996 + goto end;
1.997 + }
1.998 +# endif
1.999 + if (al == 8)
1.1000 + {
1.1001 + if (bn_wexpand(rr,16) == NULL) goto err;
1.1002 + rr->top=16;
1.1003 + bn_mul_comba8(rr->d,a->d,b->d);
1.1004 + goto end;
1.1005 + }
1.1006 + }
1.1007 +#endif /* BN_MUL_COMBA */
1.1008 +#ifdef BN_RECURSION
1.1009 + if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
1.1010 + {
1.1011 + if (i >= -1 && i <= 1)
1.1012 + {
1.1013 + int sav_j =0;
1.1014 + /* Find out the power of two lower or equal
1.1015 + to the longest of the two numbers */
1.1016 + if (i >= 0)
1.1017 + {
1.1018 + j = BN_num_bits_word((BN_ULONG)al);
1.1019 + }
1.1020 + if (i == -1)
1.1021 + {
1.1022 + j = BN_num_bits_word((BN_ULONG)bl);
1.1023 + }
1.1024 + sav_j = j;
1.1025 + j = 1<<(j-1);
1.1026 + assert(j <= al || j <= bl);
1.1027 + k = j+j;
1.1028 + t = BN_CTX_get(ctx);
1.1029 + if (al > j || bl > j)
1.1030 + {
1.1031 + bn_wexpand(t,k*4);
1.1032 + bn_wexpand(rr,k*4);
1.1033 + bn_mul_part_recursive(rr->d,a->d,b->d,
1.1034 + j,al-j,bl-j,t->d);
1.1035 + }
1.1036 + else /* al <= j || bl <= j */
1.1037 + {
1.1038 + bn_wexpand(t,k*2);
1.1039 + bn_wexpand(rr,k*2);
1.1040 + bn_mul_recursive(rr->d,a->d,b->d,
1.1041 + j,al-j,bl-j,t->d);
1.1042 + }
1.1043 + rr->top=top;
1.1044 + goto end;
1.1045 + }
1.1046 +#if 0
1.1047 + if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
1.1048 + {
1.1049 + BIGNUM *tmp_bn = (BIGNUM *)b;
1.1050 + if (bn_wexpand(tmp_bn,al) == NULL) goto err;
1.1051 + tmp_bn->d[bl]=0;
1.1052 + bl++;
1.1053 + i--;
1.1054 + }
1.1055 + else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
1.1056 + {
1.1057 + BIGNUM *tmp_bn = (BIGNUM *)a;
1.1058 + if (bn_wexpand(tmp_bn,bl) == NULL) goto err;
1.1059 + tmp_bn->d[al]=0;
1.1060 + al++;
1.1061 + i++;
1.1062 + }
1.1063 + if (i == 0)
1.1064 + {
1.1065 + /* symmetric and > 4 */
1.1066 + /* 16 or larger */
1.1067 + j=BN_num_bits_word((BN_ULONG)al);
1.1068 + j=1<<(j-1);
1.1069 + k=j+j;
1.1070 + t = BN_CTX_get(ctx);
1.1071 + if (al == j) /* exact multiple */
1.1072 + {
1.1073 + if (bn_wexpand(t,k*2) == NULL) goto err;
1.1074 + if (bn_wexpand(rr,k*2) == NULL) goto err;
1.1075 + bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
1.1076 + }
1.1077 + else
1.1078 + {
1.1079 + if (bn_wexpand(t,k*4) == NULL) goto err;
1.1080 + if (bn_wexpand(rr,k*4) == NULL) goto err;
1.1081 + bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
1.1082 + }
1.1083 + rr->top=top;
1.1084 + goto end;
1.1085 + }
1.1086 +#endif
1.1087 + }
1.1088 +#endif /* BN_RECURSION */
1.1089 + if (bn_wexpand(rr,top) == NULL) goto err;
1.1090 + rr->top=top;
1.1091 + bn_mul_normal(rr->d,a->d,al,b->d,bl);
1.1092 +
1.1093 +#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
1.1094 +end:
1.1095 +#endif
1.1096 + bn_correct_top(rr);
1.1097 + if (r != rr) BN_copy(r,rr);
1.1098 + ret=1;
1.1099 +err:
1.1100 + bn_check_top(r);
1.1101 + BN_CTX_end(ctx);
1.1102 + return(ret);
1.1103 + }
1.1104 +
1.1105 +EXPORT_C void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
1.1106 + {
1.1107 + BN_ULONG *rr;
1.1108 +
1.1109 +#ifdef BN_COUNT
1.1110 + fprintf(stderr," bn_mul_normal %d * %d\n",na,nb);
1.1111 +#endif
1.1112 +
1.1113 + if (na < nb)
1.1114 + {
1.1115 + int itmp;
1.1116 + BN_ULONG *ltmp;
1.1117 +
1.1118 + itmp=na; na=nb; nb=itmp;
1.1119 + ltmp=a; a=b; b=ltmp;
1.1120 +
1.1121 + }
1.1122 + rr= &(r[na]);
1.1123 + if (nb <= 0)
1.1124 + {
1.1125 + (void)bn_mul_words(r,a,na,0);
1.1126 + return;
1.1127 + }
1.1128 + else
1.1129 + rr[0]=bn_mul_words(r,a,na,b[0]);
1.1130 +
1.1131 + for (;;)
1.1132 + {
1.1133 + if (--nb <= 0) return;
1.1134 + rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]);
1.1135 + if (--nb <= 0) return;
1.1136 + rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]);
1.1137 + if (--nb <= 0) return;
1.1138 + rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]);
1.1139 + if (--nb <= 0) return;
1.1140 + rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]);
1.1141 + rr+=4;
1.1142 + r+=4;
1.1143 + b+=4;
1.1144 + }
1.1145 + }
1.1146 +
1.1147 +EXPORT_C void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
1.1148 + {
1.1149 +#ifdef BN_COUNT
1.1150 + fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n);
1.1151 +#endif
1.1152 + bn_mul_words(r,a,n,b[0]);
1.1153 +
1.1154 + for (;;)
1.1155 + {
1.1156 + if (--n <= 0) return;
1.1157 + bn_mul_add_words(&(r[1]),a,n,b[1]);
1.1158 + if (--n <= 0) return;
1.1159 + bn_mul_add_words(&(r[2]),a,n,b[2]);
1.1160 + if (--n <= 0) return;
1.1161 + bn_mul_add_words(&(r[3]),a,n,b[3]);
1.1162 + if (--n <= 0) return;
1.1163 + bn_mul_add_words(&(r[4]),a,n,b[4]);
1.1164 + r+=4;
1.1165 + b+=4;
1.1166 + }
1.1167 + }