1 #include <openssl/bn.h>
3 #if defined(OPENSSL_X86_64) && !defined(OPENSSL_WINDOWS)
5 #include "../internal.h"
7 /* x86_64 BIGNUM accelerator version 0.1, December 2002.
9 * Implemented by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
12 * Rights for redistribution and usage in source and binary forms are
13 * granted according to the OpenSSL license. Warranty of any kind is
16 * Q. Version 0.1? It doesn't sound like Andy, he used to assign real
17 * versions, like 1.0...
18 * A. Well, that's because this code is basically a quick-n-dirty
19 * proof-of-concept hack. As you can see it's implemented with
20 * inline assembler, which means that you're bound to GCC and that
21 * there might be enough room for further improvement.
23 * Q. Why inline assembler?
24 * A. x86_64 features own ABI which I'm not familiar with. This is
25 * why I decided to let the compiler take care of subroutine
26 * prologue/epilogue as well as register allocation. For reference.
27 * Win64 implements different ABI for AMD64, different from Linux.
29 * Q. How much faster does it get?
30 * A. 'apps/openssl speed rsa dsa' output with no-asm:
32 * sign verify sign/s verify/s
33 * rsa 512 bits 0.0006s 0.0001s 1683.8 18456.2
34 * rsa 1024 bits 0.0028s 0.0002s 356.0 6407.0
35 * rsa 2048 bits 0.0172s 0.0005s 58.0 1957.8
36 * rsa 4096 bits 0.1155s 0.0018s 8.7 555.6
37 * sign verify sign/s verify/s
38 * dsa 512 bits 0.0005s 0.0006s 2100.8 1768.3
39 * dsa 1024 bits 0.0014s 0.0018s 692.3 559.2
40 * dsa 2048 bits 0.0049s 0.0061s 204.7 165.0
42 * 'apps/openssl speed rsa dsa' output with this module:
44 * sign verify sign/s verify/s
45 * rsa 512 bits 0.0004s 0.0000s 2767.1 33297.9
46 * rsa 1024 bits 0.0012s 0.0001s 867.4 14674.7
47 * rsa 2048 bits 0.0061s 0.0002s 164.0 5270.0
48 * rsa 4096 bits 0.0384s 0.0006s 26.1 1650.8
49 * sign verify sign/s verify/s
50 * dsa 512 bits 0.0002s 0.0003s 4442.2 3786.3
51 * dsa 1024 bits 0.0005s 0.0007s 1835.1 1497.4
52 * dsa 2048 bits 0.0016s 0.0020s 620.4 504.6
54 * For the reference. IA-32 assembler implementation performs
55 * very much like 64-bit code compiled with no-asm on the same
59 /* TODO(davidben): Get this file working on Windows x64. */
67 * "m"(a), "+m"(r) is the way to favor DirectPath ยต-code;
68 * "g"(0) let the compiler to decide where does it
69 * want to keep the value of zero;
71 #define mul_add(r, a, word, carry) \
73 register BN_ULONG high, low; \
74 asm("mulq %3" : "=a"(low), "=d"(high) : "a"(word), "m"(a) : "cc"); \
75 asm("addq %2,%0; adcq %3,%1" \
76 : "+r"(carry), "+d"(high) \
79 asm("addq %2,%0; adcq %3,%1" \
80 : "+m"(r), "+d"(high) \
81 : "r"(carry), "g"(0) \
86 #define mul(r, a, word, carry) \
88 register BN_ULONG high, low; \
89 asm("mulq %3" : "=a"(low), "=d"(high) : "a"(word), "g"(a) : "cc"); \
90 asm("addq %2,%0; adcq %3,%1" \
91 : "+r"(carry), "+d"(high) \
94 (r) = carry, carry = high; \
97 #define sqr(r0, r1, a) asm("mulq %2" : "=a"(r0), "=d"(r1) : "a"(a) : "cc");
99 BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
107 mul_add(rp[0], ap[0], w, c1);
108 mul_add(rp[1], ap[1], w, c1);
109 mul_add(rp[2], ap[2], w, c1);
110 mul_add(rp[3], ap[3], w, c1);
116 mul_add(rp[0], ap[0], w, c1);
119 mul_add(rp[1], ap[1], w, c1);
122 mul_add(rp[2], ap[2], w, c1);
129 BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w) {
136 mul(rp[0], ap[0], w, c1);
137 mul(rp[1], ap[1], w, c1);
138 mul(rp[2], ap[2], w, c1);
139 mul(rp[3], ap[3], w, c1);
145 mul(rp[0], ap[0], w, c1);
148 mul(rp[1], ap[1], w, c1);
151 mul(rp[2], ap[2], w, c1);
156 void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n) {
161 sqr(r[0], r[1], a[0]);
162 sqr(r[2], r[3], a[1]);
163 sqr(r[4], r[5], a[2]);
164 sqr(r[6], r[7], a[3]);
170 sqr(r[0], r[1], a[0]);
173 sqr(r[2], r[3], a[1]);
176 sqr(r[4], r[5], a[2]);
180 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d) {
183 asm("divq %4" : "=a"(ret), "=d"(waste) : "a"(l), "d"(h), "g"(d) : "cc");
188 BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
197 " subq %0,%0 \n" /* clear carry */
200 "1: movq (%4,%2,8),%0 \n"
201 " adcq (%5,%2,8),%0 \n"
202 " movq %0,(%3,%2,8) \n"
206 : "=&r"(ret), "+c"(n), "+r"(i)
207 : "r"(rp), "r"(ap), "r"(bp)
214 BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
223 " subq %0,%0 \n" /* clear borrow */
226 "1: movq (%4,%2,8),%0 \n"
227 " sbbq (%5,%2,8),%0 \n"
228 " movq %0,(%3,%2,8) \n"
232 : "=&r"(ret), "+c"(n), "+r"(i)
233 : "r"(rp), "r"(ap), "r"(bp)
239 /* Simics 1.4<7 has buggy sbbq:-( */
240 #define BN_MASK2 0xffffffffffffffffL
241 BN_ULONG bn_sub_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) {
246 return ((BN_ULONG)0);
251 r[0] = (t1 - t2 - c) & BN_MASK2;
259 r[1] = (t1 - t2 - c) & BN_MASK2;
267 r[2] = (t1 - t2 - c) & BN_MASK2;
275 r[3] = (t1 - t2 - c) & BN_MASK2;
289 /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
290 /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
291 /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
292 /* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0)
296 /* original macros are kept for reference purposes */
297 #define mul_add_c(a, b, c0, c1, c2) \
299 BN_ULONG ta = (a), tb = (b); \
301 t2 = BN_UMULT_HIGH(ta, tb); \
303 t2 += (c0 < t1) ? 1 : 0; \
305 c2 += (c1 < t2) ? 1 : 0; \
308 #define mul_add_c2(a, b, c0, c1, c2) \
310 BN_ULONG ta = (a), tb = (b), t0; \
311 t1 = BN_UMULT_HIGH(ta, tb); \
314 c2 += (t2 < t1) ? 1 : 0; \
316 t2 += (t1 < t0) ? 1 : 0; \
318 t2 += (c0 < t1) ? 1 : 0; \
320 c2 += (c1 < t2) ? 1 : 0; \
323 #define mul_add_c(a, b, c0, c1, c2) \
325 asm("mulq %3" : "=a"(t1), "=d"(t2) : "a"(a), "m"(b) : "cc"); \
326 asm("addq %2,%0; adcq %3,%1" \
327 : "+r"(c0), "+d"(t2) \
330 asm("addq %2,%0; adcq %3,%1" \
331 : "+r"(c1), "+r"(c2) \
336 #define sqr_add_c(a, i, c0, c1, c2) \
338 asm("mulq %2" : "=a"(t1), "=d"(t2) : "a"(a[i]) : "cc"); \
339 asm("addq %2,%0; adcq %3,%1" \
340 : "+r"(c0), "+d"(t2) \
343 asm("addq %2,%0; adcq %3,%1" \
344 : "+r"(c1), "+r"(c2) \
349 #define mul_add_c2(a, b, c0, c1, c2) \
351 asm("mulq %3" : "=a"(t1), "=d"(t2) : "a"(a), "m"(b) : "cc"); \
352 asm("addq %0,%0; adcq %2,%1" : "+d"(t2), "+r"(c2) : "g"(0) : "cc"); \
353 asm("addq %0,%0; adcq %2,%1" : "+a"(t1), "+d"(t2) : "g"(0) : "cc"); \
354 asm("addq %2,%0; adcq %3,%1" \
355 : "+r"(c0), "+d"(t2) \
358 asm("addq %2,%0; adcq %3,%1" \
359 : "+r"(c1), "+r"(c2) \
365 #define sqr_add_c2(a, i, j, c0, c1, c2) mul_add_c2((a)[i], (a)[j], c0, c1, c2)
367 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) {
374 mul_add_c(a[0], b[0], c1, c2, c3);
377 mul_add_c(a[0], b[1], c2, c3, c1);
378 mul_add_c(a[1], b[0], c2, c3, c1);
381 mul_add_c(a[2], b[0], c3, c1, c2);
382 mul_add_c(a[1], b[1], c3, c1, c2);
383 mul_add_c(a[0], b[2], c3, c1, c2);
386 mul_add_c(a[0], b[3], c1, c2, c3);
387 mul_add_c(a[1], b[2], c1, c2, c3);
388 mul_add_c(a[2], b[1], c1, c2, c3);
389 mul_add_c(a[3], b[0], c1, c2, c3);
392 mul_add_c(a[4], b[0], c2, c3, c1);
393 mul_add_c(a[3], b[1], c2, c3, c1);
394 mul_add_c(a[2], b[2], c2, c3, c1);
395 mul_add_c(a[1], b[3], c2, c3, c1);
396 mul_add_c(a[0], b[4], c2, c3, c1);
399 mul_add_c(a[0], b[5], c3, c1, c2);
400 mul_add_c(a[1], b[4], c3, c1, c2);
401 mul_add_c(a[2], b[3], c3, c1, c2);
402 mul_add_c(a[3], b[2], c3, c1, c2);
403 mul_add_c(a[4], b[1], c3, c1, c2);
404 mul_add_c(a[5], b[0], c3, c1, c2);
407 mul_add_c(a[6], b[0], c1, c2, c3);
408 mul_add_c(a[5], b[1], c1, c2, c3);
409 mul_add_c(a[4], b[2], c1, c2, c3);
410 mul_add_c(a[3], b[3], c1, c2, c3);
411 mul_add_c(a[2], b[4], c1, c2, c3);
412 mul_add_c(a[1], b[5], c1, c2, c3);
413 mul_add_c(a[0], b[6], c1, c2, c3);
416 mul_add_c(a[0], b[7], c2, c3, c1);
417 mul_add_c(a[1], b[6], c2, c3, c1);
418 mul_add_c(a[2], b[5], c2, c3, c1);
419 mul_add_c(a[3], b[4], c2, c3, c1);
420 mul_add_c(a[4], b[3], c2, c3, c1);
421 mul_add_c(a[5], b[2], c2, c3, c1);
422 mul_add_c(a[6], b[1], c2, c3, c1);
423 mul_add_c(a[7], b[0], c2, c3, c1);
426 mul_add_c(a[7], b[1], c3, c1, c2);
427 mul_add_c(a[6], b[2], c3, c1, c2);
428 mul_add_c(a[5], b[3], c3, c1, c2);
429 mul_add_c(a[4], b[4], c3, c1, c2);
430 mul_add_c(a[3], b[5], c3, c1, c2);
431 mul_add_c(a[2], b[6], c3, c1, c2);
432 mul_add_c(a[1], b[7], c3, c1, c2);
435 mul_add_c(a[2], b[7], c1, c2, c3);
436 mul_add_c(a[3], b[6], c1, c2, c3);
437 mul_add_c(a[4], b[5], c1, c2, c3);
438 mul_add_c(a[5], b[4], c1, c2, c3);
439 mul_add_c(a[6], b[3], c1, c2, c3);
440 mul_add_c(a[7], b[2], c1, c2, c3);
443 mul_add_c(a[7], b[3], c2, c3, c1);
444 mul_add_c(a[6], b[4], c2, c3, c1);
445 mul_add_c(a[5], b[5], c2, c3, c1);
446 mul_add_c(a[4], b[6], c2, c3, c1);
447 mul_add_c(a[3], b[7], c2, c3, c1);
450 mul_add_c(a[4], b[7], c3, c1, c2);
451 mul_add_c(a[5], b[6], c3, c1, c2);
452 mul_add_c(a[6], b[5], c3, c1, c2);
453 mul_add_c(a[7], b[4], c3, c1, c2);
456 mul_add_c(a[7], b[5], c1, c2, c3);
457 mul_add_c(a[6], b[6], c1, c2, c3);
458 mul_add_c(a[5], b[7], c1, c2, c3);
461 mul_add_c(a[6], b[7], c2, c3, c1);
462 mul_add_c(a[7], b[6], c2, c3, c1);
465 mul_add_c(a[7], b[7], c3, c1, c2);
470 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) {
477 mul_add_c(a[0], b[0], c1, c2, c3);
480 mul_add_c(a[0], b[1], c2, c3, c1);
481 mul_add_c(a[1], b[0], c2, c3, c1);
484 mul_add_c(a[2], b[0], c3, c1, c2);
485 mul_add_c(a[1], b[1], c3, c1, c2);
486 mul_add_c(a[0], b[2], c3, c1, c2);
489 mul_add_c(a[0], b[3], c1, c2, c3);
490 mul_add_c(a[1], b[2], c1, c2, c3);
491 mul_add_c(a[2], b[1], c1, c2, c3);
492 mul_add_c(a[3], b[0], c1, c2, c3);
495 mul_add_c(a[3], b[1], c2, c3, c1);
496 mul_add_c(a[2], b[2], c2, c3, c1);
497 mul_add_c(a[1], b[3], c2, c3, c1);
500 mul_add_c(a[2], b[3], c3, c1, c2);
501 mul_add_c(a[3], b[2], c3, c1, c2);
504 mul_add_c(a[3], b[3], c1, c2, c3);
509 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a) {
516 sqr_add_c(a, 0, c1, c2, c3);
519 sqr_add_c2(a, 1, 0, c2, c3, c1);
522 sqr_add_c(a, 1, c3, c1, c2);
523 sqr_add_c2(a, 2, 0, c3, c1, c2);
526 sqr_add_c2(a, 3, 0, c1, c2, c3);
527 sqr_add_c2(a, 2, 1, c1, c2, c3);
530 sqr_add_c(a, 2, c2, c3, c1);
531 sqr_add_c2(a, 3, 1, c2, c3, c1);
532 sqr_add_c2(a, 4, 0, c2, c3, c1);
535 sqr_add_c2(a, 5, 0, c3, c1, c2);
536 sqr_add_c2(a, 4, 1, c3, c1, c2);
537 sqr_add_c2(a, 3, 2, c3, c1, c2);
540 sqr_add_c(a, 3, c1, c2, c3);
541 sqr_add_c2(a, 4, 2, c1, c2, c3);
542 sqr_add_c2(a, 5, 1, c1, c2, c3);
543 sqr_add_c2(a, 6, 0, c1, c2, c3);
546 sqr_add_c2(a, 7, 0, c2, c3, c1);
547 sqr_add_c2(a, 6, 1, c2, c3, c1);
548 sqr_add_c2(a, 5, 2, c2, c3, c1);
549 sqr_add_c2(a, 4, 3, c2, c3, c1);
552 sqr_add_c(a, 4, c3, c1, c2);
553 sqr_add_c2(a, 5, 3, c3, c1, c2);
554 sqr_add_c2(a, 6, 2, c3, c1, c2);
555 sqr_add_c2(a, 7, 1, c3, c1, c2);
558 sqr_add_c2(a, 7, 2, c1, c2, c3);
559 sqr_add_c2(a, 6, 3, c1, c2, c3);
560 sqr_add_c2(a, 5, 4, c1, c2, c3);
563 sqr_add_c(a, 5, c2, c3, c1);
564 sqr_add_c2(a, 6, 4, c2, c3, c1);
565 sqr_add_c2(a, 7, 3, c2, c3, c1);
568 sqr_add_c2(a, 7, 4, c3, c1, c2);
569 sqr_add_c2(a, 6, 5, c3, c1, c2);
572 sqr_add_c(a, 6, c1, c2, c3);
573 sqr_add_c2(a, 7, 5, c1, c2, c3);
576 sqr_add_c2(a, 7, 6, c2, c3, c1);
579 sqr_add_c(a, 7, c3, c1, c2);
584 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a) {
591 sqr_add_c(a, 0, c1, c2, c3);
594 sqr_add_c2(a, 1, 0, c2, c3, c1);
597 sqr_add_c(a, 1, c3, c1, c2);
598 sqr_add_c2(a, 2, 0, c3, c1, c2);
601 sqr_add_c2(a, 3, 0, c1, c2, c3);
602 sqr_add_c2(a, 2, 1, c1, c2, c3);
605 sqr_add_c(a, 2, c2, c3, c1);
606 sqr_add_c2(a, 3, 1, c2, c3, c1);
609 sqr_add_c2(a, 3, 2, c3, c1, c2);
612 sqr_add_c(a, 3, c1, c2, c3);
617 #endif /* defined(OPENSSL_X86_64) && !defined(OPENSSL_WINDOWS) */