crypto/bn/bn_asm.c

   1 /* crypto/bn/bn_asm.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62
  63 #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
  64
  65 BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
  66         {
  67         BN_ULONG c1=0;
  68
  69         bn_check_num(num);
  70         if (num <= 0) return(c1);
  71
  72         while (num&~3)
  73                 {
  74                 mul_add(rp[0],ap[0],w,c1);
  75                 mul_add(rp[1],ap[1],w,c1);
  76                 mul_add(rp[2],ap[2],w,c1);
  77                 mul_add(rp[3],ap[3],w,c1);
  78                 ap+=4; rp+=4; num-=4;
  79                 }
  80         if (num)
  81                 {
  82                 mul_add(rp[0],ap[0],w,c1); if (--num==0) return c1;
  83                 mul_add(rp[1],ap[1],w,c1); if (--num==0) return c1;
  84                 mul_add(rp[2],ap[2],w,c1); return c1;
  85                 }
  86
  87         return(c1);
  88         }
  89
  90 BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
  91         {
  92         BN_ULONG c1=0;
  93
  94         bn_check_num(num);
  95         if (num <= 0) return(c1);
  96
  97         while (num&~3)
  98                 {
  99                 mul(rp[0],ap[0],w,c1);
 100                 mul(rp[1],ap[1],w,c1);
 101                 mul(rp[2],ap[2],w,c1);
 102                 mul(rp[3],ap[3],w,c1);
 103                 ap+=4; rp+=4; num-=4;
 104                 }
 105         if (num)
 106                 {
 107                 mul(rp[0],ap[0],w,c1); if (--num == 0) return c1;
 108                 mul(rp[1],ap[1],w,c1); if (--num == 0) return c1;
 109                 mul(rp[2],ap[2],w,c1);
 110                 }
 111         return(c1);
 112         }
 113
 114 void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n)
 115         {
 116         bn_check_num(n);
 117         if (n <= 0) return;
 118         while (n&~3)
 119                 {
 120                 sqr(r[0],r[1],a[0]);
 121                 sqr(r[2],r[3],a[1]);
 122                 sqr(r[4],r[5],a[2]);
 123                 sqr(r[6],r[7],a[3]);
 124                 a+=4; r+=8; n-=4;
 125                 }
 126         if (n)
 127                 {
 128                 sqr(r[0],r[1],a[0]); if (--n == 0) return;
 129                 sqr(r[2],r[3],a[1]); if (--n == 0) return;
 130                 sqr(r[4],r[5],a[2]);
 131                 }
 132         }
 133
 134 #else
 135
 136 BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
 137         {
 138         BN_ULONG c=0;
 139         BN_ULONG bl,bh;
 140
 141         bn_check_num(num);
 142         if (num <= 0) return((BN_ULONG)0);
 143
 144         bl=LBITS(w);
 145         bh=HBITS(w);
 146
 147         for (;;)
 148                 {
 149                 mul_add(rp[0],ap[0],bl,bh,c);
 150                 if (--num == 0) break;
 151                 mul_add(rp[1],ap[1],bl,bh,c);
 152                 if (--num == 0) break;
 153                 mul_add(rp[2],ap[2],bl,bh,c);
 154                 if (--num == 0) break;
 155                 mul_add(rp[3],ap[3],bl,bh,c);
 156                 if (--num == 0) break;
 157                 ap+=4;
 158                 rp+=4;
 159                 }
 160         return(c);
 161         }
 162
 163 BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
 164         {
 165         BN_ULONG carry=0;
 166         BN_ULONG bl,bh;
 167
 168         bn_check_num(num);
 169         if (num <= 0) return((BN_ULONG)0);
 170
 171         bl=LBITS(w);
 172         bh=HBITS(w);
 173
 174         for (;;)
 175                 {
 176                 mul(rp[0],ap[0],bl,bh,carry);
 177                 if (--num == 0) break;
 178                 mul(rp[1],ap[1],bl,bh,carry);
 179                 if (--num == 0) break;
 180                 mul(rp[2],ap[2],bl,bh,carry);
 181                 if (--num == 0) break;
 182                 mul(rp[3],ap[3],bl,bh,carry);
 183                 if (--num == 0) break;
 184                 ap+=4;
 185                 rp+=4;
 186                 }
 187         return(carry);
 188         }
 189
 190 void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n)
 191         {
 192         bn_check_num(n);
 193         if (n <= 0) return;
 194         for (;;)
 195                 {
 196                 sqr64(r[0],r[1],a[0]);
 197                 if (--n == 0) break;
 198
 199                 sqr64(r[2],r[3],a[1]);
 200                 if (--n == 0) break;
 201
 202                 sqr64(r[4],r[5],a[2]);
 203                 if (--n == 0) break;
 204
 205                 sqr64(r[6],r[7],a[3]);
 206                 if (--n == 0) break;
 207
 208                 a+=4;
 209                 r+=8;
 210                 }
 211         }
 212
 213 #endif
 214
 215 #if defined(BN_LLONG) && defined(BN_DIV2W)
 216
 217 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
 218         {
 219         return((BN_ULONG)(((((BN_ULLONG)h)<<BN_BITS2)|l)/(BN_ULLONG)d));
 220         }
 221
 222 #else
 223
 224 /* Divide h-l by d and return the result. */
 225 /* I need to test this some more :-( */
 226 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
 227         {
 228         BN_ULONG dh,dl,q,ret=0,th,tl,t;
 229         int i,count=2;
 230
 231         if (d == 0) return(BN_MASK2);
 232
 233         i=BN_num_bits_word(d);
 234         if ((i != BN_BITS2) && (h > (BN_ULONG)1<<i))
 235                 {
 236 #if !defined(NO_STDIO) && !defined(WIN16)
 237                 fprintf(stderr,"Division would overflow (%d)\n",i);
 238 #endif
 239                 abort();
 240                 }
 241         i=BN_BITS2-i;
 242         if (h >= d) h-=d;
 243
 244         if (i)
 245                 {
 246                 d<<=i;
 247                 h=(h<<i)|(l>>(BN_BITS2-i));
 248                 l<<=i;
 249                 }
 250         dh=(d&BN_MASK2h)>>BN_BITS4;
 251         dl=(d&BN_MASK2l);
 252         for (;;)
 253                 {
 254                 if ((h>>BN_BITS4) == dh)
 255                         q=BN_MASK2l;
 256                 else
 257                         q=h/dh;
 258
 259                 th=q*dh;
 260                 tl=dl*q;
 261                 for (;;)
 262                         {
 263                         t=h-th;
 264                         if ((t&BN_MASK2h) ||
 265                                 ((tl) <= (
 266                                         (t<<BN_BITS4)|
 267                                         ((l&BN_MASK2h)>>BN_BITS4))))
 268                                 break;
 269                         q--;
 270                         th-=dh;
 271                         tl-=dl;
 272                         }
 273                 t=(tl>>BN_BITS4);
 274                 tl=(tl<<BN_BITS4)&BN_MASK2h;
 275                 th+=t;
 276
 277                 if (l < tl) th++;
 278                 l-=tl;
 279                 if (h < th)
 280                         {
 281                         h+=d;
 282                         q--;
 283                         }
 284                 h-=th;
 285
 286                 if (--count == 0) break;
 287
 288                 ret=q<<BN_BITS4;
 289                 h=((h<<BN_BITS4)|(l>>BN_BITS4))&BN_MASK2;
 290                 l=(l&BN_MASK2l)<<BN_BITS4;
 291                 }
 292         ret|=q;
 293         return(ret);
 294         }
 295 #endif
 296
 297 #ifdef BN_LLONG
 298 BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
 299         {
 300         BN_ULLONG ll=0;
 301
 302         bn_check_num(n);
 303         if (n <= 0) return((BN_ULONG)0);
 304
 305         for (;;)
 306                 {
 307                 ll+=(BN_ULLONG)a[0]+b[0];
 308                 r[0]=(BN_ULONG)ll&BN_MASK2;
 309                 ll>>=BN_BITS2;
 310                 if (--n <= 0) break;
 311
 312                 ll+=(BN_ULLONG)a[1]+b[1];
 313                 r[1]=(BN_ULONG)ll&BN_MASK2;
 314                 ll>>=BN_BITS2;
 315                 if (--n <= 0) break;
 316
 317                 ll+=(BN_ULLONG)a[2]+b[2];
 318                 r[2]=(BN_ULONG)ll&BN_MASK2;
 319                 ll>>=BN_BITS2;
 320                 if (--n <= 0) break;
 321
 322                 ll+=(BN_ULLONG)a[3]+b[3];
 323                 r[3]=(BN_ULONG)ll&BN_MASK2;
 324                 ll>>=BN_BITS2;
 325                 if (--n <= 0) break;
 326
 327                 a+=4;
 328                 b+=4;
 329                 r+=4;
 330                 }
 331         return((BN_ULONG)ll);
 332         }
 333 #else
 334 BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
 335         {
 336         BN_ULONG c,l,t;
 337
 338         bn_check_num(n);
 339         if (n <= 0) return((BN_ULONG)0);
 340
 341         c=0;
 342         for (;;)
 343                 {
 344                 t=a[0];
 345                 t=(t+c)&BN_MASK2;
 346                 c=(t < c);
 347                 l=(t+b[0])&BN_MASK2;
 348                 c+=(l < t);
 349                 r[0]=l;
 350                 if (--n <= 0) break;
 351
 352                 t=a[1];
 353                 t=(t+c)&BN_MASK2;
 354                 c=(t < c);
 355                 l=(t+b[1])&BN_MASK2;
 356                 c+=(l < t);
 357                 r[1]=l;
 358                 if (--n <= 0) break;
 359
 360                 t=a[2];
 361                 t=(t+c)&BN_MASK2;
 362                 c=(t < c);
 363                 l=(t+b[2])&BN_MASK2;
 364                 c+=(l < t);
 365                 r[2]=l;
 366                 if (--n <= 0) break;
 367
 368                 t=a[3];
 369                 t=(t+c)&BN_MASK2;
 370                 c=(t < c);
 371                 l=(t+b[3])&BN_MASK2;
 372                 c+=(l < t);
 373                 r[3]=l;
 374                 if (--n <= 0) break;
 375
 376                 a+=4;
 377                 b+=4;
 378                 r+=4;
 379                 }
 380         return((BN_ULONG)c);
 381         }
 382 #endif
 383
 384 BN_ULONG bn_sub_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
 385         {
 386         BN_ULONG t1,t2;
 387         int c=0;
 388
 389         bn_check_num(n);
 390         if (n <= 0) return((BN_ULONG)0);
 391
 392         for (;;)
 393                 {
 394                 t1=a[0]; t2=b[0];
 395                 r[0]=(t1-t2-c)&BN_MASK2;
 396                 if (t1 != t2) c=(t1 < t2);
 397                 if (--n <= 0) break;
 398
 399                 t1=a[1]; t2=b[1];
 400                 r[1]=(t1-t2-c)&BN_MASK2;
 401                 if (t1 != t2) c=(t1 < t2);
 402                 if (--n <= 0) break;
 403
 404                 t1=a[2]; t2=b[2];
 405                 r[2]=(t1-t2-c)&BN_MASK2;
 406                 if (t1 != t2) c=(t1 < t2);
 407                 if (--n <= 0) break;
 408
 409                 t1=a[3]; t2=b[3];
 410                 r[3]=(t1-t2-c)&BN_MASK2;
 411                 if (t1 != t2) c=(t1 < t2);
 412                 if (--n <= 0) break;
 413
 414                 a+=4;
 415                 b+=4;
 416                 r+=4;
 417                 }
 418         return(c);
 419         }
 420
 421 #ifdef BN_MUL_COMBA
 422
 423 #undef bn_mul_comba8
 424 #undef bn_mul_comba4
 425 #undef bn_sqr_comba8
 426 #undef bn_sqr_comba4
 427
 428 #ifdef BN_LLONG
 429 #define mul_add_c(a,b,c0,c1,c2) \
 430         t=(BN_ULLONG)a*b; \
 431         t1=(BN_ULONG)Lw(t); \
 432         t2=(BN_ULONG)Hw(t); \
 433         c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 434         c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 435
 436 #define mul_add_c2(a,b,c0,c1,c2) \
 437         t=(BN_ULLONG)a*b; \
 438         tt=(t+t)&BN_MASK; \
 439         if (tt < t) c2++; \
 440         t1=(BN_ULONG)Lw(tt); \
 441         t2=(BN_ULONG)Hw(tt); \
 442         c0=(c0+t1)&BN_MASK2;  \
 443         if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
 444         c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 445
 446 #define sqr_add_c(a,i,c0,c1,c2) \
 447         t=(BN_ULLONG)a[i]*a[i]; \
 448         t1=(BN_ULONG)Lw(t); \
 449         t2=(BN_ULONG)Hw(t); \
 450         c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 451         c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 452
 453 #define sqr_add_c2(a,i,j,c0,c1,c2) \
 454         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
 455
 456 #elif defined(BN_UMULT_HIGH)
 457
 458 #define mul_add_c(a,b,c0,c1,c2) {       \
 459         BN_ULONG ta=(a),tb=(b);         \
 460         t1 = ta * tb;                   \
 461         t2 = BN_UMULT_HIGH(ta,tb);      \
 462         c0 += t1; t2 += (c0<t1)?1:0;    \
 463         c1 += t2; c2 += (c1<t2)?1:0;    \
 464         }
 465
 466 #define mul_add_c2(a,b,c0,c1,c2) {      \
 467         BN_ULONG ta=(a),tb=(b),t0;      \
 468         t1 = BN_UMULT_HIGH(ta,tb);      \
 469         t0 = ta * tb;                   \
 470         t2 = t1+t1; c2 += (t2<t1)?1:0;  \
 471         t1 = t0+t0; t2 += (t1<t0)?1:0;  \
 472         c0 += t1; t2 += (c0<t1)?1:0;    \
 473         c1 += t2; c2 += (c1<t2)?1:0;    \
 474         }
 475
 476 #define sqr_add_c(a,i,c0,c1,c2) {       \
 477         BN_ULONG ta=(a)[i];             \
 478         t1 = ta * ta;                   \
 479         t2 = BN_UMULT_HIGH(ta,ta);      \
 480         c0 += t1; t2 += (c0<t1)?1:0;    \
 481         c1 += t2; c2 += (c1<t2)?1:0;    \
 482         }
 483
 484 #define sqr_add_c2(a,i,j,c0,c1,c2)      \
 485         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
 486
 487 #else
 488 #define mul_add_c(a,b,c0,c1,c2) \
 489         t1=LBITS(a); t2=HBITS(a); \
 490         bl=LBITS(b); bh=HBITS(b); \
 491         mul64(t1,t2,bl,bh); \
 492         c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 493         c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 494
 495 #define mul_add_c2(a,b,c0,c1,c2) \
 496         t1=LBITS(a); t2=HBITS(a); \
 497         bl=LBITS(b); bh=HBITS(b); \
 498         mul64(t1,t2,bl,bh); \
 499         if (t2 & BN_TBIT) c2++; \
 500         t2=(t2+t2)&BN_MASK2; \
 501         if (t1 & BN_TBIT) t2++; \
 502         t1=(t1+t1)&BN_MASK2; \
 503         c0=(c0+t1)&BN_MASK2;  \
 504         if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
 505         c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 506
 507 #define sqr_add_c(a,i,c0,c1,c2) \
 508         sqr64(t1,t2,(a)[i]); \
 509         c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 510         c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 511
 512 #define sqr_add_c2(a,i,j,c0,c1,c2) \
 513         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
 514 #endif
 515
 516 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 517         {
 518 #ifdef BN_LLONG
 519         BN_ULLONG t;
 520 #else
 521         BN_ULONG bl,bh;
 522 #endif
 523         BN_ULONG t1,t2;
 524         BN_ULONG c1,c2,c3;
 525
 526         c1=0;
 527         c2=0;
 528         c3=0;
 529         mul_add_c(a[0],b[0],c1,c2,c3);
 530         r[0]=c1;
 531         c1=0;
 532         mul_add_c(a[0],b[1],c2,c3,c1);
 533         mul_add_c(a[1],b[0],c2,c3,c1);
 534         r[1]=c2;
 535         c2=0;
 536         mul_add_c(a[2],b[0],c3,c1,c2);
 537         mul_add_c(a[1],b[1],c3,c1,c2);
 538         mul_add_c(a[0],b[2],c3,c1,c2);
 539         r[2]=c3;
 540         c3=0;
 541         mul_add_c(a[0],b[3],c1,c2,c3);
 542         mul_add_c(a[1],b[2],c1,c2,c3);
 543         mul_add_c(a[2],b[1],c1,c2,c3);
 544         mul_add_c(a[3],b[0],c1,c2,c3);
 545         r[3]=c1;
 546         c1=0;
 547         mul_add_c(a[4],b[0],c2,c3,c1);
 548         mul_add_c(a[3],b[1],c2,c3,c1);
 549         mul_add_c(a[2],b[2],c2,c3,c1);
 550         mul_add_c(a[1],b[3],c2,c3,c1);
 551         mul_add_c(a[0],b[4],c2,c3,c1);
 552         r[4]=c2;
 553         c2=0;
 554         mul_add_c(a[0],b[5],c3,c1,c2);
 555         mul_add_c(a[1],b[4],c3,c1,c2);
 556         mul_add_c(a[2],b[3],c3,c1,c2);
 557         mul_add_c(a[3],b[2],c3,c1,c2);
 558         mul_add_c(a[4],b[1],c3,c1,c2);
 559         mul_add_c(a[5],b[0],c3,c1,c2);
 560         r[5]=c3;
 561         c3=0;
 562         mul_add_c(a[6],b[0],c1,c2,c3);
 563         mul_add_c(a[5],b[1],c1,c2,c3);
 564         mul_add_c(a[4],b[2],c1,c2,c3);
 565         mul_add_c(a[3],b[3],c1,c2,c3);
 566         mul_add_c(a[2],b[4],c1,c2,c3);
 567         mul_add_c(a[1],b[5],c1,c2,c3);
 568         mul_add_c(a[0],b[6],c1,c2,c3);
 569         r[6]=c1;
 570         c1=0;
 571         mul_add_c(a[0],b[7],c2,c3,c1);
 572         mul_add_c(a[1],b[6],c2,c3,c1);
 573         mul_add_c(a[2],b[5],c2,c3,c1);
 574         mul_add_c(a[3],b[4],c2,c3,c1);
 575         mul_add_c(a[4],b[3],c2,c3,c1);
 576         mul_add_c(a[5],b[2],c2,c3,c1);
 577         mul_add_c(a[6],b[1],c2,c3,c1);
 578         mul_add_c(a[7],b[0],c2,c3,c1);
 579         r[7]=c2;
 580         c2=0;
 581         mul_add_c(a[7],b[1],c3,c1,c2);
 582         mul_add_c(a[6],b[2],c3,c1,c2);
 583         mul_add_c(a[5],b[3],c3,c1,c2);
 584         mul_add_c(a[4],b[4],c3,c1,c2);
 585         mul_add_c(a[3],b[5],c3,c1,c2);
 586         mul_add_c(a[2],b[6],c3,c1,c2);
 587         mul_add_c(a[1],b[7],c3,c1,c2);
 588         r[8]=c3;
 589         c3=0;
 590         mul_add_c(a[2],b[7],c1,c2,c3);
 591         mul_add_c(a[3],b[6],c1,c2,c3);
 592         mul_add_c(a[4],b[5],c1,c2,c3);
 593         mul_add_c(a[5],b[4],c1,c2,c3);
 594         mul_add_c(a[6],b[3],c1,c2,c3);
 595         mul_add_c(a[7],b[2],c1,c2,c3);
 596         r[9]=c1;
 597         c1=0;
 598         mul_add_c(a[7],b[3],c2,c3,c1);
 599         mul_add_c(a[6],b[4],c2,c3,c1);
 600         mul_add_c(a[5],b[5],c2,c3,c1);
 601         mul_add_c(a[4],b[6],c2,c3,c1);
 602         mul_add_c(a[3],b[7],c2,c3,c1);
 603         r[10]=c2;
 604         c2=0;
 605         mul_add_c(a[4],b[7],c3,c1,c2);
 606         mul_add_c(a[5],b[6],c3,c1,c2);
 607         mul_add_c(a[6],b[5],c3,c1,c2);
 608         mul_add_c(a[7],b[4],c3,c1,c2);
 609         r[11]=c3;
 610         c3=0;
 611         mul_add_c(a[7],b[5],c1,c2,c3);
 612         mul_add_c(a[6],b[6],c1,c2,c3);
 613         mul_add_c(a[5],b[7],c1,c2,c3);
 614         r[12]=c1;
 615         c1=0;
 616         mul_add_c(a[6],b[7],c2,c3,c1);
 617         mul_add_c(a[7],b[6],c2,c3,c1);
 618         r[13]=c2;
 619         c2=0;
 620         mul_add_c(a[7],b[7],c3,c1,c2);
 621         r[14]=c3;
 622         r[15]=c1;
 623         }
 624
 625 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 626         {
 627 #ifdef BN_LLONG
 628         BN_ULLONG t;
 629 #else
 630         BN_ULONG bl,bh;
 631 #endif
 632         BN_ULONG t1,t2;
 633         BN_ULONG c1,c2,c3;
 634
 635         c1=0;
 636         c2=0;
 637         c3=0;
 638         mul_add_c(a[0],b[0],c1,c2,c3);
 639         r[0]=c1;
 640         c1=0;
 641         mul_add_c(a[0],b[1],c2,c3,c1);
 642         mul_add_c(a[1],b[0],c2,c3,c1);
 643         r[1]=c2;
 644         c2=0;
 645         mul_add_c(a[2],b[0],c3,c1,c2);
 646         mul_add_c(a[1],b[1],c3,c1,c2);
 647         mul_add_c(a[0],b[2],c3,c1,c2);
 648         r[2]=c3;
 649         c3=0;
 650         mul_add_c(a[0],b[3],c1,c2,c3);
 651         mul_add_c(a[1],b[2],c1,c2,c3);
 652         mul_add_c(a[2],b[1],c1,c2,c3);
 653         mul_add_c(a[3],b[0],c1,c2,c3);
 654         r[3]=c1;
 655         c1=0;
 656         mul_add_c(a[3],b[1],c2,c3,c1);
 657         mul_add_c(a[2],b[2],c2,c3,c1);
 658         mul_add_c(a[1],b[3],c2,c3,c1);
 659         r[4]=c2;
 660         c2=0;
 661         mul_add_c(a[2],b[3],c3,c1,c2);
 662         mul_add_c(a[3],b[2],c3,c1,c2);
 663         r[5]=c3;
 664         c3=0;
 665         mul_add_c(a[3],b[3],c1,c2,c3);
 666         r[6]=c1;
 667         r[7]=c2;
 668         }
 669
 670 void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a)
 671         {
 672 #ifdef BN_LLONG
 673         BN_ULLONG t,tt;
 674 #else
 675         BN_ULONG bl,bh;
 676 #endif
 677         BN_ULONG t1,t2;
 678         BN_ULONG c1,c2,c3;
 679
 680         c1=0;
 681         c2=0;
 682         c3=0;
 683         sqr_add_c(a,0,c1,c2,c3);
 684         r[0]=c1;
 685         c1=0;
 686         sqr_add_c2(a,1,0,c2,c3,c1);
 687         r[1]=c2;
 688         c2=0;
 689         sqr_add_c(a,1,c3,c1,c2);
 690         sqr_add_c2(a,2,0,c3,c1,c2);
 691         r[2]=c3;
 692         c3=0;
 693         sqr_add_c2(a,3,0,c1,c2,c3);
 694         sqr_add_c2(a,2,1,c1,c2,c3);
 695         r[3]=c1;
 696         c1=0;
 697         sqr_add_c(a,2,c2,c3,c1);
 698         sqr_add_c2(a,3,1,c2,c3,c1);
 699         sqr_add_c2(a,4,0,c2,c3,c1);
 700         r[4]=c2;
 701         c2=0;
 702         sqr_add_c2(a,5,0,c3,c1,c2);
 703         sqr_add_c2(a,4,1,c3,c1,c2);
 704         sqr_add_c2(a,3,2,c3,c1,c2);
 705         r[5]=c3;
 706         c3=0;
 707         sqr_add_c(a,3,c1,c2,c3);
 708         sqr_add_c2(a,4,2,c1,c2,c3);
 709         sqr_add_c2(a,5,1,c1,c2,c3);
 710         sqr_add_c2(a,6,0,c1,c2,c3);
 711         r[6]=c1;
 712         c1=0;
 713         sqr_add_c2(a,7,0,c2,c3,c1);
 714         sqr_add_c2(a,6,1,c2,c3,c1);
 715         sqr_add_c2(a,5,2,c2,c3,c1);
 716         sqr_add_c2(a,4,3,c2,c3,c1);
 717         r[7]=c2;
 718         c2=0;
 719         sqr_add_c(a,4,c3,c1,c2);
 720         sqr_add_c2(a,5,3,c3,c1,c2);
 721         sqr_add_c2(a,6,2,c3,c1,c2);
 722         sqr_add_c2(a,7,1,c3,c1,c2);
 723         r[8]=c3;
 724         c3=0;
 725         sqr_add_c2(a,7,2,c1,c2,c3);
 726         sqr_add_c2(a,6,3,c1,c2,c3);
 727         sqr_add_c2(a,5,4,c1,c2,c3);
 728         r[9]=c1;
 729         c1=0;
 730         sqr_add_c(a,5,c2,c3,c1);
 731         sqr_add_c2(a,6,4,c2,c3,c1);
 732         sqr_add_c2(a,7,3,c2,c3,c1);
 733         r[10]=c2;
 734         c2=0;
 735         sqr_add_c2(a,7,4,c3,c1,c2);
 736         sqr_add_c2(a,6,5,c3,c1,c2);
 737         r[11]=c3;
 738         c3=0;
 739         sqr_add_c(a,6,c1,c2,c3);
 740         sqr_add_c2(a,7,5,c1,c2,c3);
 741         r[12]=c1;
 742         c1=0;
 743         sqr_add_c2(a,7,6,c2,c3,c1);
 744         r[13]=c2;
 745         c2=0;
 746         sqr_add_c(a,7,c3,c1,c2);
 747         r[14]=c3;
 748         r[15]=c1;
 749         }
 750
 751 void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a)
 752         {
 753 #ifdef BN_LLONG
 754         BN_ULLONG t,tt;
 755 #else
 756         BN_ULONG bl,bh;
 757 #endif
 758         BN_ULONG t1,t2;
 759         BN_ULONG c1,c2,c3;
 760
 761         c1=0;
 762         c2=0;
 763         c3=0;
 764         sqr_add_c(a,0,c1,c2,c3);
 765         r[0]=c1;
 766         c1=0;
 767         sqr_add_c2(a,1,0,c2,c3,c1);
 768         r[1]=c2;
 769         c2=0;
 770         sqr_add_c(a,1,c3,c1,c2);
 771         sqr_add_c2(a,2,0,c3,c1,c2);
 772         r[2]=c3;
 773         c3=0;
 774         sqr_add_c2(a,3,0,c1,c2,c3);
 775         sqr_add_c2(a,2,1,c1,c2,c3);
 776         r[3]=c1;
 777         c1=0;
 778         sqr_add_c(a,2,c2,c3,c1);
 779         sqr_add_c2(a,3,1,c2,c3,c1);
 780         r[4]=c2;
 781         c2=0;
 782         sqr_add_c2(a,3,2,c3,c1,c2);
 783         r[5]=c3;
 784         c3=0;
 785         sqr_add_c(a,3,c1,c2,c3);
 786         r[6]=c1;
 787         r[7]=c2;
 788         }
 789 #else
 790
 791 /* hmm... is it faster just to do a multiply? */
 792 #undef bn_sqr_comba4
 793 void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a)
 794         {
 795         BN_ULONG t[8];
 796         bn_sqr_normal(r,a,4,t);
 797         }
 798
 799 #undef bn_sqr_comba8
 800 void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a)
 801         {
 802         BN_ULONG t[16];
 803         bn_sqr_normal(r,a,8,t);
 804         }
 805
 806 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 807         {
 808         r[4]=bn_mul_words(    &(r[0]),a,4,b[0]);
 809         r[5]=bn_mul_add_words(&(r[1]),a,4,b[1]);
 810         r[6]=bn_mul_add_words(&(r[2]),a,4,b[2]);
 811         r[7]=bn_mul_add_words(&(r[3]),a,4,b[3]);
 812         }
 813
 814 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 815         {
 816         r[ 8]=bn_mul_words(    &(r[0]),a,8,b[0]);
 817         r[ 9]=bn_mul_add_words(&(r[1]),a,8,b[1]);
 818         r[10]=bn_mul_add_words(&(r[2]),a,8,b[2]);
 819         r[11]=bn_mul_add_words(&(r[3]),a,8,b[3]);
 820         r[12]=bn_mul_add_words(&(r[4]),a,8,b[4]);
 821         r[13]=bn_mul_add_words(&(r[5]),a,8,b[5]);
 822         r[14]=bn_mul_add_words(&(r[6]),a,8,b[6]);
 823         r[15]=bn_mul_add_words(&(r[7]),a,8,b[7]);
 824         }
 825
 826 #endif /* BN_COMBA */