]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_asm.c
1 /* crypto/bn/bn_asm.c */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
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.
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).
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.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
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)"
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
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.]
60 # undef NDEBUG /* avoid conflicting definitions */
69 #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
71 BN_ULONG
bn_mul_add_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
76 if (num
<= 0) return(c1
);
78 #ifndef OPENSSL_SMALL_FOOTPRINT
81 mul_add(rp
[0],ap
[0],w
,c1
);
82 mul_add(rp
[1],ap
[1],w
,c1
);
83 mul_add(rp
[2],ap
[2],w
,c1
);
84 mul_add(rp
[3],ap
[3],w
,c1
);
90 mul_add(rp
[0],ap
[0],w
,c1
);
97 BN_ULONG
bn_mul_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
102 if (num
<= 0) return(c1
);
104 #ifndef OPENSSL_SMALL_FOOTPRINT
107 mul(rp
[0],ap
[0],w
,c1
);
108 mul(rp
[1],ap
[1],w
,c1
);
109 mul(rp
[2],ap
[2],w
,c1
);
110 mul(rp
[3],ap
[3],w
,c1
);
111 ap
+=4; rp
+=4; num
-=4;
116 mul(rp
[0],ap
[0],w
,c1
);
122 void bn_sqr_words(BN_ULONG
*r
, const BN_ULONG
*a
, int n
)
127 #ifndef OPENSSL_SMALL_FOOTPRINT
144 #else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
146 BN_ULONG
bn_mul_add_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
152 if (num
<= 0) return((BN_ULONG
)0);
157 #ifndef OPENSSL_SMALL_FOOTPRINT
160 mul_add(rp
[0],ap
[0],bl
,bh
,c
);
161 mul_add(rp
[1],ap
[1],bl
,bh
,c
);
162 mul_add(rp
[2],ap
[2],bl
,bh
,c
);
163 mul_add(rp
[3],ap
[3],bl
,bh
,c
);
164 ap
+=4; rp
+=4; num
-=4;
169 mul_add(rp
[0],ap
[0],bl
,bh
,c
);
175 BN_ULONG
bn_mul_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
181 if (num
<= 0) return((BN_ULONG
)0);
186 #ifndef OPENSSL_SMALL_FOOTPRINT
189 mul(rp
[0],ap
[0],bl
,bh
,carry
);
190 mul(rp
[1],ap
[1],bl
,bh
,carry
);
191 mul(rp
[2],ap
[2],bl
,bh
,carry
);
192 mul(rp
[3],ap
[3],bl
,bh
,carry
);
193 ap
+=4; rp
+=4; num
-=4;
198 mul(rp
[0],ap
[0],bl
,bh
,carry
);
204 void bn_sqr_words(BN_ULONG
*r
, const BN_ULONG
*a
, int n
)
209 #ifndef OPENSSL_SMALL_FOOTPRINT
212 sqr64(r
[0],r
[1],a
[0]);
213 sqr64(r
[2],r
[3],a
[1]);
214 sqr64(r
[4],r
[5],a
[2]);
215 sqr64(r
[6],r
[7],a
[3]);
221 sqr64(r
[0],r
[1],a
[0]);
226 #endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
228 #if defined(BN_LLONG) && defined(BN_DIV2W)
230 BN_ULONG
bn_div_words(BN_ULONG h
, BN_ULONG l
, BN_ULONG d
)
232 return((BN_ULONG
)(((((BN_ULLONG
)h
)<<BN_BITS2
)|l
)/(BN_ULLONG
)d
));
237 /* Divide h,l by d and return the result. */
238 /* I need to test this some more :-( */
239 BN_ULONG
bn_div_words(BN_ULONG h
, BN_ULONG l
, BN_ULONG d
)
241 BN_ULONG dh
,dl
,q
,ret
=0,th
,tl
,t
;
244 if (d
== 0) return(BN_MASK2
);
246 i
=BN_num_bits_word(d
);
247 assert((i
== BN_BITS2
) || (h
<= (BN_ULONG
)1<<i
));
255 h
=(h
<<i
)|(l
>>(BN_BITS2
-i
));
258 dh
=(d
&BN_MASK2h
)>>BN_BITS4
;
262 if ((h
>>BN_BITS4
) == dh
)
275 ((l
&BN_MASK2h
)>>BN_BITS4
))))
282 tl
=(tl
<<BN_BITS4
)&BN_MASK2h
;
294 if (--count
== 0) break;
297 h
=((h
<<BN_BITS4
)|(l
>>BN_BITS4
))&BN_MASK2
;
298 l
=(l
&BN_MASK2l
)<<BN_BITS4
;
303 #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
306 BN_ULONG
bn_add_words(BN_ULONG
*r
, const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
311 if (n
<= 0) return((BN_ULONG
)0);
313 #ifndef OPENSSL_SMALL_FOOTPRINT
316 ll
+=(BN_ULLONG
)a
[0]+b
[0];
317 r
[0]=(BN_ULONG
)ll
&BN_MASK2
;
319 ll
+=(BN_ULLONG
)a
[1]+b
[1];
320 r
[1]=(BN_ULONG
)ll
&BN_MASK2
;
322 ll
+=(BN_ULLONG
)a
[2]+b
[2];
323 r
[2]=(BN_ULONG
)ll
&BN_MASK2
;
325 ll
+=(BN_ULLONG
)a
[3]+b
[3];
326 r
[3]=(BN_ULONG
)ll
&BN_MASK2
;
328 a
+=4; b
+=4; r
+=4; n
-=4;
333 ll
+=(BN_ULLONG
)a
[0]+b
[0];
334 r
[0]=(BN_ULONG
)ll
&BN_MASK2
;
338 return((BN_ULONG
)ll
);
340 #else /* !BN_LLONG */
341 BN_ULONG
bn_add_words(BN_ULONG
*r
, const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
346 if (n
<= 0) return((BN_ULONG
)0);
349 #ifndef OPENSSL_SMALL_FOOTPRINT
376 a
+=4; b
+=4; r
+=4; n
-=4;
391 #endif /* !BN_LLONG */
393 BN_ULONG
bn_sub_words(BN_ULONG
*r
, const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
399 if (n
<= 0) return((BN_ULONG
)0);
401 #ifndef OPENSSL_SMALL_FOOTPRINT
405 r
[0]=(t1
-t2
-c
)&BN_MASK2
;
406 if (t1
!= t2
) c
=(t1
< t2
);
408 r
[1]=(t1
-t2
-c
)&BN_MASK2
;
409 if (t1
!= t2
) c
=(t1
< t2
);
411 r
[2]=(t1
-t2
-c
)&BN_MASK2
;
412 if (t1
!= t2
) c
=(t1
< t2
);
414 r
[3]=(t1
-t2
-c
)&BN_MASK2
;
415 if (t1
!= t2
) c
=(t1
< t2
);
416 a
+=4; b
+=4; r
+=4; n
-=4;
422 r
[0]=(t1
-t2
-c
)&BN_MASK2
;
423 if (t1
!= t2
) c
=(t1
< t2
);
429 #if defined(BN_MUL_COMBA) && !defined(OPENSSL_SMALL_FOOTPRINT)
436 /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
437 /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
438 /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
439 /* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0) */
442 #define mul_add_c(a,b,c0,c1,c2) \
444 t1=(BN_ULONG)Lw(t); \
445 t2=(BN_ULONG)Hw(t); \
446 c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
447 c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
449 #define mul_add_c2(a,b,c0,c1,c2) \
453 t1=(BN_ULONG)Lw(tt); \
454 t2=(BN_ULONG)Hw(tt); \
455 c0=(c0+t1)&BN_MASK2; \
456 if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
457 c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
459 #define sqr_add_c(a,i,c0,c1,c2) \
460 t=(BN_ULLONG)a[i]*a[i]; \
461 t1=(BN_ULONG)Lw(t); \
462 t2=(BN_ULONG)Hw(t); \
463 c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
464 c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
466 #define sqr_add_c2(a,i,j,c0,c1,c2) \
467 mul_add_c2((a)[i],(a)[j],c0,c1,c2)
469 #elif defined(BN_UMULT_LOHI)
471 #define mul_add_c(a,b,c0,c1,c2) { \
472 BN_ULONG ta=(a),tb=(b); \
473 BN_UMULT_LOHI(t1,t2,ta,tb); \
474 c0 += t1; t2 += (c0<t1)?1:0; \
475 c1 += t2; c2 += (c1<t2)?1:0; \
478 #define mul_add_c2(a,b,c0,c1,c2) { \
479 BN_ULONG ta=(a),tb=(b),t0; \
480 BN_UMULT_LOHI(t0,t1,ta,tb); \
481 t2 = t1+t1; c2 += (t2<t1)?1:0; \
482 t1 = t0+t0; t2 += (t1<t0)?1:0; \
483 c0 += t1; t2 += (c0<t1)?1:0; \
484 c1 += t2; c2 += (c1<t2)?1:0; \
487 #define sqr_add_c(a,i,c0,c1,c2) { \
488 BN_ULONG ta=(a)[i]; \
489 BN_UMULT_LOHI(t1,t2,ta,ta); \
490 c0 += t1; t2 += (c0<t1)?1:0; \
491 c1 += t2; c2 += (c1<t2)?1:0; \
494 #define sqr_add_c2(a,i,j,c0,c1,c2) \
495 mul_add_c2((a)[i],(a)[j],c0,c1,c2)
497 #elif defined(BN_UMULT_HIGH)
499 #define mul_add_c(a,b,c0,c1,c2) { \
500 BN_ULONG ta=(a),tb=(b); \
502 t2 = BN_UMULT_HIGH(ta,tb); \
503 c0 += t1; t2 += (c0<t1)?1:0; \
504 c1 += t2; c2 += (c1<t2)?1:0; \
507 #define mul_add_c2(a,b,c0,c1,c2) { \
508 BN_ULONG ta=(a),tb=(b),t0; \
509 t1 = BN_UMULT_HIGH(ta,tb); \
511 t2 = t1+t1; c2 += (t2<t1)?1:0; \
512 t1 = t0+t0; t2 += (t1<t0)?1:0; \
513 c0 += t1; t2 += (c0<t1)?1:0; \
514 c1 += t2; c2 += (c1<t2)?1:0; \
517 #define sqr_add_c(a,i,c0,c1,c2) { \
518 BN_ULONG ta=(a)[i]; \
520 t2 = BN_UMULT_HIGH(ta,ta); \
521 c0 += t1; t2 += (c0<t1)?1:0; \
522 c1 += t2; c2 += (c1<t2)?1:0; \
525 #define sqr_add_c2(a,i,j,c0,c1,c2) \
526 mul_add_c2((a)[i],(a)[j],c0,c1,c2)
528 #else /* !BN_LLONG */
529 #define mul_add_c(a,b,c0,c1,c2) \
530 t1=LBITS(a); t2=HBITS(a); \
531 bl=LBITS(b); bh=HBITS(b); \
532 mul64(t1,t2,bl,bh); \
533 c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
534 c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
536 #define mul_add_c2(a,b,c0,c1,c2) \
537 t1=LBITS(a); t2=HBITS(a); \
538 bl=LBITS(b); bh=HBITS(b); \
539 mul64(t1,t2,bl,bh); \
540 if (t2 & BN_TBIT) c2++; \
541 t2=(t2+t2)&BN_MASK2; \
542 if (t1 & BN_TBIT) t2++; \
543 t1=(t1+t1)&BN_MASK2; \
544 c0=(c0+t1)&BN_MASK2; \
545 if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
546 c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
548 #define sqr_add_c(a,i,c0,c1,c2) \
549 sqr64(t1,t2,(a)[i]); \
550 c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
551 c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
553 #define sqr_add_c2(a,i,j,c0,c1,c2) \
554 mul_add_c2((a)[i],(a)[j],c0,c1,c2)
555 #endif /* !BN_LLONG */
557 void bn_mul_comba8(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
570 mul_add_c(a
[0],b
[0],c1
,c2
,c3
);
573 mul_add_c(a
[0],b
[1],c2
,c3
,c1
);
574 mul_add_c(a
[1],b
[0],c2
,c3
,c1
);
577 mul_add_c(a
[2],b
[0],c3
,c1
,c2
);
578 mul_add_c(a
[1],b
[1],c3
,c1
,c2
);
579 mul_add_c(a
[0],b
[2],c3
,c1
,c2
);
582 mul_add_c(a
[0],b
[3],c1
,c2
,c3
);
583 mul_add_c(a
[1],b
[2],c1
,c2
,c3
);
584 mul_add_c(a
[2],b
[1],c1
,c2
,c3
);
585 mul_add_c(a
[3],b
[0],c1
,c2
,c3
);
588 mul_add_c(a
[4],b
[0],c2
,c3
,c1
);
589 mul_add_c(a
[3],b
[1],c2
,c3
,c1
);
590 mul_add_c(a
[2],b
[2],c2
,c3
,c1
);
591 mul_add_c(a
[1],b
[3],c2
,c3
,c1
);
592 mul_add_c(a
[0],b
[4],c2
,c3
,c1
);
595 mul_add_c(a
[0],b
[5],c3
,c1
,c2
);
596 mul_add_c(a
[1],b
[4],c3
,c1
,c2
);
597 mul_add_c(a
[2],b
[3],c3
,c1
,c2
);
598 mul_add_c(a
[3],b
[2],c3
,c1
,c2
);
599 mul_add_c(a
[4],b
[1],c3
,c1
,c2
);
600 mul_add_c(a
[5],b
[0],c3
,c1
,c2
);
603 mul_add_c(a
[6],b
[0],c1
,c2
,c3
);
604 mul_add_c(a
[5],b
[1],c1
,c2
,c3
);
605 mul_add_c(a
[4],b
[2],c1
,c2
,c3
);
606 mul_add_c(a
[3],b
[3],c1
,c2
,c3
);
607 mul_add_c(a
[2],b
[4],c1
,c2
,c3
);
608 mul_add_c(a
[1],b
[5],c1
,c2
,c3
);
609 mul_add_c(a
[0],b
[6],c1
,c2
,c3
);
612 mul_add_c(a
[0],b
[7],c2
,c3
,c1
);
613 mul_add_c(a
[1],b
[6],c2
,c3
,c1
);
614 mul_add_c(a
[2],b
[5],c2
,c3
,c1
);
615 mul_add_c(a
[3],b
[4],c2
,c3
,c1
);
616 mul_add_c(a
[4],b
[3],c2
,c3
,c1
);
617 mul_add_c(a
[5],b
[2],c2
,c3
,c1
);
618 mul_add_c(a
[6],b
[1],c2
,c3
,c1
);
619 mul_add_c(a
[7],b
[0],c2
,c3
,c1
);
622 mul_add_c(a
[7],b
[1],c3
,c1
,c2
);
623 mul_add_c(a
[6],b
[2],c3
,c1
,c2
);
624 mul_add_c(a
[5],b
[3],c3
,c1
,c2
);
625 mul_add_c(a
[4],b
[4],c3
,c1
,c2
);
626 mul_add_c(a
[3],b
[5],c3
,c1
,c2
);
627 mul_add_c(a
[2],b
[6],c3
,c1
,c2
);
628 mul_add_c(a
[1],b
[7],c3
,c1
,c2
);
631 mul_add_c(a
[2],b
[7],c1
,c2
,c3
);
632 mul_add_c(a
[3],b
[6],c1
,c2
,c3
);
633 mul_add_c(a
[4],b
[5],c1
,c2
,c3
);
634 mul_add_c(a
[5],b
[4],c1
,c2
,c3
);
635 mul_add_c(a
[6],b
[3],c1
,c2
,c3
);
636 mul_add_c(a
[7],b
[2],c1
,c2
,c3
);
639 mul_add_c(a
[7],b
[3],c2
,c3
,c1
);
640 mul_add_c(a
[6],b
[4],c2
,c3
,c1
);
641 mul_add_c(a
[5],b
[5],c2
,c3
,c1
);
642 mul_add_c(a
[4],b
[6],c2
,c3
,c1
);
643 mul_add_c(a
[3],b
[7],c2
,c3
,c1
);
646 mul_add_c(a
[4],b
[7],c3
,c1
,c2
);
647 mul_add_c(a
[5],b
[6],c3
,c1
,c2
);
648 mul_add_c(a
[6],b
[5],c3
,c1
,c2
);
649 mul_add_c(a
[7],b
[4],c3
,c1
,c2
);
652 mul_add_c(a
[7],b
[5],c1
,c2
,c3
);
653 mul_add_c(a
[6],b
[6],c1
,c2
,c3
);
654 mul_add_c(a
[5],b
[7],c1
,c2
,c3
);
657 mul_add_c(a
[6],b
[7],c2
,c3
,c1
);
658 mul_add_c(a
[7],b
[6],c2
,c3
,c1
);
661 mul_add_c(a
[7],b
[7],c3
,c1
,c2
);
666 void bn_mul_comba4(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
679 mul_add_c(a
[0],b
[0],c1
,c2
,c3
);
682 mul_add_c(a
[0],b
[1],c2
,c3
,c1
);
683 mul_add_c(a
[1],b
[0],c2
,c3
,c1
);
686 mul_add_c(a
[2],b
[0],c3
,c1
,c2
);
687 mul_add_c(a
[1],b
[1],c3
,c1
,c2
);
688 mul_add_c(a
[0],b
[2],c3
,c1
,c2
);
691 mul_add_c(a
[0],b
[3],c1
,c2
,c3
);
692 mul_add_c(a
[1],b
[2],c1
,c2
,c3
);
693 mul_add_c(a
[2],b
[1],c1
,c2
,c3
);
694 mul_add_c(a
[3],b
[0],c1
,c2
,c3
);
697 mul_add_c(a
[3],b
[1],c2
,c3
,c1
);
698 mul_add_c(a
[2],b
[2],c2
,c3
,c1
);
699 mul_add_c(a
[1],b
[3],c2
,c3
,c1
);
702 mul_add_c(a
[2],b
[3],c3
,c1
,c2
);
703 mul_add_c(a
[3],b
[2],c3
,c1
,c2
);
706 mul_add_c(a
[3],b
[3],c1
,c2
,c3
);
711 void bn_sqr_comba8(BN_ULONG
*r
, const BN_ULONG
*a
)
724 sqr_add_c(a
,0,c1
,c2
,c3
);
727 sqr_add_c2(a
,1,0,c2
,c3
,c1
);
730 sqr_add_c(a
,1,c3
,c1
,c2
);
731 sqr_add_c2(a
,2,0,c3
,c1
,c2
);
734 sqr_add_c2(a
,3,0,c1
,c2
,c3
);
735 sqr_add_c2(a
,2,1,c1
,c2
,c3
);
738 sqr_add_c(a
,2,c2
,c3
,c1
);
739 sqr_add_c2(a
,3,1,c2
,c3
,c1
);
740 sqr_add_c2(a
,4,0,c2
,c3
,c1
);
743 sqr_add_c2(a
,5,0,c3
,c1
,c2
);
744 sqr_add_c2(a
,4,1,c3
,c1
,c2
);
745 sqr_add_c2(a
,3,2,c3
,c1
,c2
);
748 sqr_add_c(a
,3,c1
,c2
,c3
);
749 sqr_add_c2(a
,4,2,c1
,c2
,c3
);
750 sqr_add_c2(a
,5,1,c1
,c2
,c3
);
751 sqr_add_c2(a
,6,0,c1
,c2
,c3
);
754 sqr_add_c2(a
,7,0,c2
,c3
,c1
);
755 sqr_add_c2(a
,6,1,c2
,c3
,c1
);
756 sqr_add_c2(a
,5,2,c2
,c3
,c1
);
757 sqr_add_c2(a
,4,3,c2
,c3
,c1
);
760 sqr_add_c(a
,4,c3
,c1
,c2
);
761 sqr_add_c2(a
,5,3,c3
,c1
,c2
);
762 sqr_add_c2(a
,6,2,c3
,c1
,c2
);
763 sqr_add_c2(a
,7,1,c3
,c1
,c2
);
766 sqr_add_c2(a
,7,2,c1
,c2
,c3
);
767 sqr_add_c2(a
,6,3,c1
,c2
,c3
);
768 sqr_add_c2(a
,5,4,c1
,c2
,c3
);
771 sqr_add_c(a
,5,c2
,c3
,c1
);
772 sqr_add_c2(a
,6,4,c2
,c3
,c1
);
773 sqr_add_c2(a
,7,3,c2
,c3
,c1
);
776 sqr_add_c2(a
,7,4,c3
,c1
,c2
);
777 sqr_add_c2(a
,6,5,c3
,c1
,c2
);
780 sqr_add_c(a
,6,c1
,c2
,c3
);
781 sqr_add_c2(a
,7,5,c1
,c2
,c3
);
784 sqr_add_c2(a
,7,6,c2
,c3
,c1
);
787 sqr_add_c(a
,7,c3
,c1
,c2
);
792 void bn_sqr_comba4(BN_ULONG
*r
, const BN_ULONG
*a
)
805 sqr_add_c(a
,0,c1
,c2
,c3
);
808 sqr_add_c2(a
,1,0,c2
,c3
,c1
);
811 sqr_add_c(a
,1,c3
,c1
,c2
);
812 sqr_add_c2(a
,2,0,c3
,c1
,c2
);
815 sqr_add_c2(a
,3,0,c1
,c2
,c3
);
816 sqr_add_c2(a
,2,1,c1
,c2
,c3
);
819 sqr_add_c(a
,2,c2
,c3
,c1
);
820 sqr_add_c2(a
,3,1,c2
,c3
,c1
);
823 sqr_add_c2(a
,3,2,c3
,c1
,c2
);
826 sqr_add_c(a
,3,c1
,c2
,c3
);
831 #ifdef OPENSSL_BN_ASM_MONT
833 * This is essentially reference implementation, which may or may not
834 * result in performance improvement. E.g. on IA-32 this routine was
835 * observed to give 40% faster rsa1024 private key operations and 10%
836 * faster rsa4096 ones, while on AMD64 it improves rsa1024 sign only
837 * by 10% and *worsens* rsa4096 sign by 15%. Once again, it's a
838 * reference implementation, one to be used as starting point for
839 * platform-specific assembler. Mentioned numbers apply to compiler
840 * generated code compiled with and without -DOPENSSL_BN_ASM_MONT and
841 * can vary not only from platform to platform, but even for compiler
842 * versions. Assembler vs. assembler improvement coefficients can
843 * [and are known to] differ and are to be documented elsewhere.
845 int bn_mul_mont(BN_ULONG
*rp
, const BN_ULONG
*ap
, const BN_ULONG
*bp
, const BN_ULONG
*np
,const BN_ULONG
*n0p
, int num
)
847 BN_ULONG c0
,c1
,ml
,*tp
,n0
;
851 volatile BN_ULONG
*vp
;
854 #if 0 /* template for platform-specific implementation */
855 if (ap
==bp
) return bn_sqr_mont(rp
,ap
,np
,n0p
,num
);
857 vp
= tp
= alloca((num
+2)*sizeof(BN_ULONG
));
861 tp
[num
] = bn_mul_words(tp
,ap
,num
,bp
[0]);
867 c0
= bn_mul_add_words(tp
,ap
,num
,bp
[i
]);
868 c1
= (tp
[num
] + c0
)&BN_MASK2
;
870 tp
[num
+1] = (c1
<c0
?1:0);
873 ml
= (c1
*n0
)&BN_MASK2
;
878 mul_add(c1
,np
[0],ml
,mh
,c0
);
880 mul_add(c1
,ml
,np
[0],c0
);
886 mul_add(c1
,np
[j
],ml
,mh
,c0
);
888 mul_add(c1
,ml
,np
[j
],c0
);
890 tp
[j
-1] = c1
&BN_MASK2
;
892 c1
= (tp
[num
] + c0
)&BN_MASK2
;
894 tp
[num
] = tp
[num
+1] + (c1
<c0
?1:0);
897 if (tp
[num
]!=0 || tp
[num
-1]>=np
[num
-1])
899 c0
= bn_sub_words(rp
,tp
,np
,num
);
900 if (tp
[num
]!=0 || c0
==0)
902 for(i
=0;i
<num
+2;i
++) vp
[i
] = 0;
906 for(i
=0;i
<num
;i
++) rp
[i
] = tp
[i
], vp
[i
] = 0;
913 * Return value of 0 indicates that multiplication/convolution was not
914 * performed to signal the caller to fall down to alternative/original
917 int bn_mul_mont(BN_ULONG
*rp
, const BN_ULONG
*ap
, const BN_ULONG
*bp
, const BN_ULONG
*np
,BN_ULONG n0
, int num
)
919 #endif /* OPENSSL_BN_ASM_MONT */
921 #else /* !BN_MUL_COMBA */
923 /* hmm... is it faster just to do a multiply? */
925 void bn_sqr_comba4(BN_ULONG
*r
, const BN_ULONG
*a
)
928 bn_sqr_normal(r
,a
,4,t
);
932 void bn_sqr_comba8(BN_ULONG
*r
, const BN_ULONG
*a
)
935 bn_sqr_normal(r
,a
,8,t
);
938 void bn_mul_comba4(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
940 r
[4]=bn_mul_words( &(r
[0]),a
,4,b
[0]);
941 r
[5]=bn_mul_add_words(&(r
[1]),a
,4,b
[1]);
942 r
[6]=bn_mul_add_words(&(r
[2]),a
,4,b
[2]);
943 r
[7]=bn_mul_add_words(&(r
[3]),a
,4,b
[3]);
946 void bn_mul_comba8(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
948 r
[ 8]=bn_mul_words( &(r
[0]),a
,8,b
[0]);
949 r
[ 9]=bn_mul_add_words(&(r
[1]),a
,8,b
[1]);
950 r
[10]=bn_mul_add_words(&(r
[2]),a
,8,b
[2]);
951 r
[11]=bn_mul_add_words(&(r
[3]),a
,8,b
[3]);
952 r
[12]=bn_mul_add_words(&(r
[4]),a
,8,b
[4]);
953 r
[13]=bn_mul_add_words(&(r
[5]),a
,8,b
[5]);
954 r
[14]=bn_mul_add_words(&(r
[6]),a
,8,b
[6]);
955 r
[15]=bn_mul_add_words(&(r
[7]),a
,8,b
[7]);
958 #ifdef OPENSSL_BN_ASM_MONT
959 int bn_mul_mont(BN_ULONG
*rp
, const BN_ULONG
*ap
, const BN_ULONG
*bp
, const BN_ULONG
*np
,BN_ULONG n0
, int num
)
962 volatile BN_ULONG
*vp
;
965 vp
= tp
= alloca((num
+2)*sizeof(BN_ULONG
));
967 for(i
=0;i
<=num
;i
++) tp
[i
]=0;
971 c0
= bn_mul_add_words(tp
,ap
,num
,bp
[i
]);
972 c1
= (tp
[num
] + c0
)&BN_MASK2
;
974 tp
[num
+1] = (c1
<c0
?1:0);
976 c0
= bn_mul_add_words(tp
,np
,num
,tp
[0]*n0
);
977 c1
= (tp
[num
] + c0
)&BN_MASK2
;
979 tp
[num
+1] += (c1
<c0
?1:0);
980 for(j
=0;j
<=num
;j
++) tp
[j
]=tp
[j
+1];
983 if (tp
[num
]!=0 || tp
[num
-1]>=np
[num
-1])
985 c0
= bn_sub_words(rp
,tp
,np
,num
);
986 if (tp
[num
]!=0 || c0
==0)
988 for(i
=0;i
<num
+2;i
++) vp
[i
] = 0;
992 for(i
=0;i
<num
;i
++) rp
[i
] = tp
[i
], vp
[i
] = 0;
998 int bn_mul_mont(BN_ULONG
*rp
, const BN_ULONG
*ap
, const BN_ULONG
*bp
, const BN_ULONG
*np
,BN_ULONG n0
, int num
)
1000 #endif /* OPENSSL_BN_ASM_MONT */
1002 #endif /* !BN_MUL_COMBA */