1e71b7053SJung-uk Kim /*
2c9cf7b5cSJung-uk Kim * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved.
3e71b7053SJung-uk Kim *
4b077aed3SPierre Pronchery * Licensed under the Apache License 2.0 (the "License"). You may not use
5e71b7053SJung-uk Kim * this file except in compliance with the License. You can obtain a copy
6e71b7053SJung-uk Kim * in the file LICENSE in the source distribution or at
7e71b7053SJung-uk Kim * https://www.openssl.org/source/license.html
8e71b7053SJung-uk Kim */
9e71b7053SJung-uk Kim
1017f01e99SJung-uk Kim #include "../bn_local.h"
111f13597dSJung-uk Kim #if !(defined(__GNUC__) && __GNUC__>=2)
12ed5d4f9aSSimon L. B. Nielsen # include "../bn_asm.c" /* kind of dirty hack for Sun Studio */
13ed5d4f9aSSimon L. B. Nielsen #else
146f9291ceSJung-uk Kim /*-
155c87c606SMark Murray * x86_64 BIGNUM accelerator version 0.1, December 2002.
165c87c606SMark Murray *
17e71b7053SJung-uk Kim * Implemented by Andy Polyakov <appro@openssl.org> for the OpenSSL
185c87c606SMark Murray * project.
195c87c606SMark Murray *
205c87c606SMark Murray * Rights for redistribution and usage in source and binary forms are
21b077aed3SPierre Pronchery * granted according to the License. Warranty of any kind is disclaimed.
225c87c606SMark Murray *
235c87c606SMark Murray * Q. Version 0.1? It doesn't sound like Andy, he used to assign real
245c87c606SMark Murray * versions, like 1.0...
255c87c606SMark Murray * A. Well, that's because this code is basically a quick-n-dirty
265c87c606SMark Murray * proof-of-concept hack. As you can see it's implemented with
275c87c606SMark Murray * inline assembler, which means that you're bound to GCC and that
283b4e3dcbSSimon L. B. Nielsen * there might be enough room for further improvement.
295c87c606SMark Murray *
305c87c606SMark Murray * Q. Why inline assembler?
313b4e3dcbSSimon L. B. Nielsen * A. x86_64 features own ABI which I'm not familiar with. This is
323b4e3dcbSSimon L. B. Nielsen * why I decided to let the compiler take care of subroutine
333b4e3dcbSSimon L. B. Nielsen * prologue/epilogue as well as register allocation. For reference.
343b4e3dcbSSimon L. B. Nielsen * Win64 implements different ABI for AMD64, different from Linux.
355c87c606SMark Murray *
365c87c606SMark Murray * Q. How much faster does it get?
373b4e3dcbSSimon L. B. Nielsen * A. 'apps/openssl speed rsa dsa' output with no-asm:
383b4e3dcbSSimon L. B. Nielsen *
393b4e3dcbSSimon L. B. Nielsen * sign verify sign/s verify/s
403b4e3dcbSSimon L. B. Nielsen * rsa 512 bits 0.0006s 0.0001s 1683.8 18456.2
413b4e3dcbSSimon L. B. Nielsen * rsa 1024 bits 0.0028s 0.0002s 356.0 6407.0
423b4e3dcbSSimon L. B. Nielsen * rsa 2048 bits 0.0172s 0.0005s 58.0 1957.8
433b4e3dcbSSimon L. B. Nielsen * rsa 4096 bits 0.1155s 0.0018s 8.7 555.6
443b4e3dcbSSimon L. B. Nielsen * sign verify sign/s verify/s
453b4e3dcbSSimon L. B. Nielsen * dsa 512 bits 0.0005s 0.0006s 2100.8 1768.3
463b4e3dcbSSimon L. B. Nielsen * dsa 1024 bits 0.0014s 0.0018s 692.3 559.2
473b4e3dcbSSimon L. B. Nielsen * dsa 2048 bits 0.0049s 0.0061s 204.7 165.0
483b4e3dcbSSimon L. B. Nielsen *
493b4e3dcbSSimon L. B. Nielsen * 'apps/openssl speed rsa dsa' output with this module:
503b4e3dcbSSimon L. B. Nielsen *
513b4e3dcbSSimon L. B. Nielsen * sign verify sign/s verify/s
523b4e3dcbSSimon L. B. Nielsen * rsa 512 bits 0.0004s 0.0000s 2767.1 33297.9
533b4e3dcbSSimon L. B. Nielsen * rsa 1024 bits 0.0012s 0.0001s 867.4 14674.7
543b4e3dcbSSimon L. B. Nielsen * rsa 2048 bits 0.0061s 0.0002s 164.0 5270.0
553b4e3dcbSSimon L. B. Nielsen * rsa 4096 bits 0.0384s 0.0006s 26.1 1650.8
563b4e3dcbSSimon L. B. Nielsen * sign verify sign/s verify/s
573b4e3dcbSSimon L. B. Nielsen * dsa 512 bits 0.0002s 0.0003s 4442.2 3786.3
583b4e3dcbSSimon L. B. Nielsen * dsa 1024 bits 0.0005s 0.0007s 1835.1 1497.4
593b4e3dcbSSimon L. B. Nielsen * dsa 2048 bits 0.0016s 0.0020s 620.4 504.6
603b4e3dcbSSimon L. B. Nielsen *
613b4e3dcbSSimon L. B. Nielsen * For the reference. IA-32 assembler implementation performs
623b4e3dcbSSimon L. B. Nielsen * very much like 64-bit code compiled with no-asm on the same
633b4e3dcbSSimon L. B. Nielsen * machine.
645c87c606SMark Murray */
655c87c606SMark Murray
666a599222SSimon L. B. Nielsen # undef mul
676a599222SSimon L. B. Nielsen # undef mul_add
686a599222SSimon L. B. Nielsen
696f9291ceSJung-uk Kim /*-
7080815a77SJung-uk Kim * "m"(a), "+m"(r) is the way to favor DirectPath µ-code;
715c87c606SMark Murray * "g"(0) let the compiler to decide where does it
725c87c606SMark Murray * want to keep the value of zero;
735c87c606SMark Murray */
745c87c606SMark Murray # define mul_add(r,a,word,carry) do { \
755c87c606SMark Murray register BN_ULONG high,low; \
765c87c606SMark Murray asm ("mulq %3" \
775c87c606SMark Murray : "=a"(low),"=d"(high) \
785c87c606SMark Murray : "a"(word),"m"(a) \
795c87c606SMark Murray : "cc"); \
805c87c606SMark Murray asm ("addq %2,%0; adcq %3,%1" \
815c87c606SMark Murray : "+r"(carry),"+d"(high)\
825c87c606SMark Murray : "a"(low),"g"(0) \
835c87c606SMark Murray : "cc"); \
845c87c606SMark Murray asm ("addq %2,%0; adcq %3,%1" \
855c87c606SMark Murray : "+m"(r),"+d"(high) \
865c87c606SMark Murray : "r"(carry),"g"(0) \
875c87c606SMark Murray : "cc"); \
885c87c606SMark Murray carry=high; \
895c87c606SMark Murray } while (0)
905c87c606SMark Murray
915c87c606SMark Murray # define mul(r,a,word,carry) do { \
925c87c606SMark Murray register BN_ULONG high,low; \
935c87c606SMark Murray asm ("mulq %3" \
945c87c606SMark Murray : "=a"(low),"=d"(high) \
955c87c606SMark Murray : "a"(word),"g"(a) \
965c87c606SMark Murray : "cc"); \
975c87c606SMark Murray asm ("addq %2,%0; adcq %3,%1" \
985c87c606SMark Murray : "+r"(carry),"+d"(high)\
995c87c606SMark Murray : "a"(low),"g"(0) \
1005c87c606SMark Murray : "cc"); \
1015c87c606SMark Murray (r)=carry, carry=high; \
1025c87c606SMark Murray } while (0)
1037bded2dbSJung-uk Kim # undef sqr
1045c87c606SMark Murray # define sqr(r0,r1,a) \
1055c87c606SMark Murray asm ("mulq %2" \
1065c87c606SMark Murray : "=a"(r0),"=d"(r1) \
1075c87c606SMark Murray : "a"(a) \
1085c87c606SMark Murray : "cc");
1095c87c606SMark Murray
bn_mul_add_words(BN_ULONG * rp,const BN_ULONG * ap,int num,BN_ULONG w)1106f9291ceSJung-uk Kim BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
1116f9291ceSJung-uk Kim BN_ULONG w)
1125c87c606SMark Murray {
1135c87c606SMark Murray BN_ULONG c1 = 0;
1145c87c606SMark Murray
1156f9291ceSJung-uk Kim if (num <= 0)
116e71b7053SJung-uk Kim return c1;
1175c87c606SMark Murray
1186f9291ceSJung-uk Kim while (num & ~3) {
1195c87c606SMark Murray mul_add(rp[0], ap[0], w, c1);
1205c87c606SMark Murray mul_add(rp[1], ap[1], w, c1);
1215c87c606SMark Murray mul_add(rp[2], ap[2], w, c1);
1225c87c606SMark Murray mul_add(rp[3], ap[3], w, c1);
1236f9291ceSJung-uk Kim ap += 4;
1246f9291ceSJung-uk Kim rp += 4;
1256f9291ceSJung-uk Kim num -= 4;
1265c87c606SMark Murray }
1276f9291ceSJung-uk Kim if (num) {
1286f9291ceSJung-uk Kim mul_add(rp[0], ap[0], w, c1);
1296f9291ceSJung-uk Kim if (--num == 0)
1306f9291ceSJung-uk Kim return c1;
1316f9291ceSJung-uk Kim mul_add(rp[1], ap[1], w, c1);
1326f9291ceSJung-uk Kim if (--num == 0)
1336f9291ceSJung-uk Kim return c1;
1346f9291ceSJung-uk Kim mul_add(rp[2], ap[2], w, c1);
1356f9291ceSJung-uk Kim return c1;
1365c87c606SMark Murray }
1375c87c606SMark Murray
138e71b7053SJung-uk Kim return c1;
1395c87c606SMark Murray }
1405c87c606SMark Murray
bn_mul_words(BN_ULONG * rp,const BN_ULONG * ap,int num,BN_ULONG w)1416a599222SSimon L. B. Nielsen BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
1425c87c606SMark Murray {
1435c87c606SMark Murray BN_ULONG c1 = 0;
1445c87c606SMark Murray
1456f9291ceSJung-uk Kim if (num <= 0)
146e71b7053SJung-uk Kim return c1;
1475c87c606SMark Murray
1486f9291ceSJung-uk Kim while (num & ~3) {
1495c87c606SMark Murray mul(rp[0], ap[0], w, c1);
1505c87c606SMark Murray mul(rp[1], ap[1], w, c1);
1515c87c606SMark Murray mul(rp[2], ap[2], w, c1);
1525c87c606SMark Murray mul(rp[3], ap[3], w, c1);
1536f9291ceSJung-uk Kim ap += 4;
1546f9291ceSJung-uk Kim rp += 4;
1556f9291ceSJung-uk Kim num -= 4;
1565c87c606SMark Murray }
1576f9291ceSJung-uk Kim if (num) {
1586f9291ceSJung-uk Kim mul(rp[0], ap[0], w, c1);
1596f9291ceSJung-uk Kim if (--num == 0)
1606f9291ceSJung-uk Kim return c1;
1616f9291ceSJung-uk Kim mul(rp[1], ap[1], w, c1);
1626f9291ceSJung-uk Kim if (--num == 0)
1636f9291ceSJung-uk Kim return c1;
1645c87c606SMark Murray mul(rp[2], ap[2], w, c1);
1655c87c606SMark Murray }
166e71b7053SJung-uk Kim return c1;
1675c87c606SMark Murray }
1685c87c606SMark Murray
bn_sqr_words(BN_ULONG * r,const BN_ULONG * a,int n)1696a599222SSimon L. B. Nielsen void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
1705c87c606SMark Murray {
1716f9291ceSJung-uk Kim if (n <= 0)
1726f9291ceSJung-uk Kim return;
1735c87c606SMark Murray
1746f9291ceSJung-uk Kim while (n & ~3) {
1755c87c606SMark Murray sqr(r[0], r[1], a[0]);
1765c87c606SMark Murray sqr(r[2], r[3], a[1]);
1775c87c606SMark Murray sqr(r[4], r[5], a[2]);
1785c87c606SMark Murray sqr(r[6], r[7], a[3]);
1796f9291ceSJung-uk Kim a += 4;
1806f9291ceSJung-uk Kim r += 8;
1816f9291ceSJung-uk Kim n -= 4;
1825c87c606SMark Murray }
1836f9291ceSJung-uk Kim if (n) {
1846f9291ceSJung-uk Kim sqr(r[0], r[1], a[0]);
1856f9291ceSJung-uk Kim if (--n == 0)
1866f9291ceSJung-uk Kim return;
1876f9291ceSJung-uk Kim sqr(r[2], r[3], a[1]);
1886f9291ceSJung-uk Kim if (--n == 0)
1896f9291ceSJung-uk Kim return;
1905c87c606SMark Murray sqr(r[4], r[5], a[2]);
1915c87c606SMark Murray }
1925c87c606SMark Murray }
1935c87c606SMark Murray
bn_div_words(BN_ULONG h,BN_ULONG l,BN_ULONG d)1945c87c606SMark Murray BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
1956f9291ceSJung-uk Kim {
1966f9291ceSJung-uk Kim BN_ULONG ret, waste;
1975c87c606SMark Murray
1986f9291ceSJung-uk Kim asm("divq %4":"=a"(ret), "=d"(waste)
199aeb5019cSJung-uk Kim : "a"(l), "d"(h), "r"(d)
2005c87c606SMark Murray : "cc");
2015c87c606SMark Murray
2025c87c606SMark Murray return ret;
2035c87c606SMark Murray }
2045c87c606SMark Murray
bn_add_words(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,int n)2056f9291ceSJung-uk Kim BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
2066f9291ceSJung-uk Kim int n)
2076f9291ceSJung-uk Kim {
2087bded2dbSJung-uk Kim BN_ULONG ret;
2097bded2dbSJung-uk Kim size_t i = 0;
2105c87c606SMark Murray
2116f9291ceSJung-uk Kim if (n <= 0)
2126f9291ceSJung-uk Kim return 0;
2135c87c606SMark Murray
2147bded2dbSJung-uk Kim asm volatile (" subq %0,%0 \n" /* clear carry */
2157bded2dbSJung-uk Kim " jmp 1f \n"
2161f13597dSJung-uk Kim ".p2align 4 \n"
2175c87c606SMark Murray "1: movq (%4,%2,8),%0 \n"
2185c87c606SMark Murray " adcq (%5,%2,8),%0 \n"
2195c87c606SMark Murray " movq %0,(%3,%2,8) \n"
2207bded2dbSJung-uk Kim " lea 1(%2),%2 \n"
221e71b7053SJung-uk Kim " dec %1 \n"
222e71b7053SJung-uk Kim " jnz 1b \n"
223e71b7053SJung-uk Kim " sbbq %0,%0 \n"
224e71b7053SJung-uk Kim :"=&r" (ret), "+c"(n), "+r"(i)
2255c87c606SMark Murray :"r"(rp), "r"(ap), "r"(bp)
2266f9291ceSJung-uk Kim :"cc", "memory");
2275c87c606SMark Murray
2285c87c606SMark Murray return ret & 1;
2295c87c606SMark Murray }
2305c87c606SMark Murray
2315c87c606SMark Murray # ifndef SIMICS
bn_sub_words(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,int n)2326f9291ceSJung-uk Kim BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
2336f9291ceSJung-uk Kim int n)
2346f9291ceSJung-uk Kim {
2357bded2dbSJung-uk Kim BN_ULONG ret;
2367bded2dbSJung-uk Kim size_t i = 0;
2375c87c606SMark Murray
2386f9291ceSJung-uk Kim if (n <= 0)
2396f9291ceSJung-uk Kim return 0;
2405c87c606SMark Murray
2417bded2dbSJung-uk Kim asm volatile (" subq %0,%0 \n" /* clear borrow */
2427bded2dbSJung-uk Kim " jmp 1f \n"
2431f13597dSJung-uk Kim ".p2align 4 \n"
2445c87c606SMark Murray "1: movq (%4,%2,8),%0 \n"
2455c87c606SMark Murray " sbbq (%5,%2,8),%0 \n"
2465c87c606SMark Murray " movq %0,(%3,%2,8) \n"
2477bded2dbSJung-uk Kim " lea 1(%2),%2 \n"
248e71b7053SJung-uk Kim " dec %1 \n"
249e71b7053SJung-uk Kim " jnz 1b \n"
250e71b7053SJung-uk Kim " sbbq %0,%0 \n"
251e71b7053SJung-uk Kim :"=&r" (ret), "+c"(n), "+r"(i)
2525c87c606SMark Murray :"r"(rp), "r"(ap), "r"(bp)
2536f9291ceSJung-uk Kim :"cc", "memory");
2545c87c606SMark Murray
2555c87c606SMark Murray return ret & 1;
2565c87c606SMark Murray }
2575c87c606SMark Murray # else
2585c87c606SMark Murray /* Simics 1.4<7 has buggy sbbq:-( */
2595c87c606SMark Murray # define BN_MASK2 0xffffffffffffffffL
bn_sub_words(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b,int n)2605c87c606SMark Murray BN_ULONG bn_sub_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
2615c87c606SMark Murray {
2625c87c606SMark Murray BN_ULONG t1, t2;
2635c87c606SMark Murray int c = 0;
2645c87c606SMark Murray
2656f9291ceSJung-uk Kim if (n <= 0)
266e71b7053SJung-uk Kim return (BN_ULONG)0;
2675c87c606SMark Murray
2686f9291ceSJung-uk Kim for (;;) {
2696f9291ceSJung-uk Kim t1 = a[0];
2706f9291ceSJung-uk Kim t2 = b[0];
2715c87c606SMark Murray r[0] = (t1 - t2 - c) & BN_MASK2;
2726f9291ceSJung-uk Kim if (t1 != t2)
2736f9291ceSJung-uk Kim c = (t1 < t2);
2746f9291ceSJung-uk Kim if (--n <= 0)
2756f9291ceSJung-uk Kim break;
2765c87c606SMark Murray
2776f9291ceSJung-uk Kim t1 = a[1];
2786f9291ceSJung-uk Kim t2 = b[1];
2795c87c606SMark Murray r[1] = (t1 - t2 - c) & BN_MASK2;
2806f9291ceSJung-uk Kim if (t1 != t2)
2816f9291ceSJung-uk Kim c = (t1 < t2);
2826f9291ceSJung-uk Kim if (--n <= 0)
2836f9291ceSJung-uk Kim break;
2845c87c606SMark Murray
2856f9291ceSJung-uk Kim t1 = a[2];
2866f9291ceSJung-uk Kim t2 = b[2];
2875c87c606SMark Murray r[2] = (t1 - t2 - c) & BN_MASK2;
2886f9291ceSJung-uk Kim if (t1 != t2)
2896f9291ceSJung-uk Kim c = (t1 < t2);
2906f9291ceSJung-uk Kim if (--n <= 0)
2916f9291ceSJung-uk Kim break;
2925c87c606SMark Murray
2936f9291ceSJung-uk Kim t1 = a[3];
2946f9291ceSJung-uk Kim t2 = b[3];
2955c87c606SMark Murray r[3] = (t1 - t2 - c) & BN_MASK2;
2966f9291ceSJung-uk Kim if (t1 != t2)
2976f9291ceSJung-uk Kim c = (t1 < t2);
2986f9291ceSJung-uk Kim if (--n <= 0)
2996f9291ceSJung-uk Kim break;
3005c87c606SMark Murray
3015c87c606SMark Murray a += 4;
3025c87c606SMark Murray b += 4;
3035c87c606SMark Murray r += 4;
3045c87c606SMark Murray }
305e71b7053SJung-uk Kim return c;
3065c87c606SMark Murray }
3075c87c606SMark Murray # endif
3085c87c606SMark Murray
3095c87c606SMark Murray /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
3105c87c606SMark Murray /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
3115c87c606SMark Murray /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
3126f9291ceSJung-uk Kim /*
3136f9291ceSJung-uk Kim * sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number
3146f9291ceSJung-uk Kim * c=(c2,c1,c0)
3156f9291ceSJung-uk Kim */
3165c87c606SMark Murray
317751d2991SJung-uk Kim /*
318751d2991SJung-uk Kim * Keep in mind that carrying into high part of multiplication result
319751d2991SJung-uk Kim * can not overflow, because it cannot be all-ones.
320751d2991SJung-uk Kim */
3215c87c606SMark Murray # if 0
3225c87c606SMark Murray /* original macros are kept for reference purposes */
3237bded2dbSJung-uk Kim # define mul_add_c(a,b,c0,c1,c2) do { \
3245c87c606SMark Murray BN_ULONG ta = (a), tb = (b); \
3257bded2dbSJung-uk Kim BN_ULONG lo, hi; \
3267bded2dbSJung-uk Kim BN_UMULT_LOHI(lo,hi,ta,tb); \
3277bded2dbSJung-uk Kim c0 += lo; hi += (c0<lo)?1:0; \
3287bded2dbSJung-uk Kim c1 += hi; c2 += (c1<hi)?1:0; \
3297bded2dbSJung-uk Kim } while(0)
3305c87c606SMark Murray
3317bded2dbSJung-uk Kim # define mul_add_c2(a,b,c0,c1,c2) do { \
3327bded2dbSJung-uk Kim BN_ULONG ta = (a), tb = (b); \
3337bded2dbSJung-uk Kim BN_ULONG lo, hi, tt; \
3347bded2dbSJung-uk Kim BN_UMULT_LOHI(lo,hi,ta,tb); \
3357bded2dbSJung-uk Kim c0 += lo; tt = hi+((c0<lo)?1:0); \
3367bded2dbSJung-uk Kim c1 += tt; c2 += (c1<tt)?1:0; \
3377bded2dbSJung-uk Kim c0 += lo; hi += (c0<lo)?1:0; \
3387bded2dbSJung-uk Kim c1 += hi; c2 += (c1<hi)?1:0; \
3397bded2dbSJung-uk Kim } while(0)
3407bded2dbSJung-uk Kim
3417bded2dbSJung-uk Kim # define sqr_add_c(a,i,c0,c1,c2) do { \
3427bded2dbSJung-uk Kim BN_ULONG ta = (a)[i]; \
3437bded2dbSJung-uk Kim BN_ULONG lo, hi; \
3447bded2dbSJung-uk Kim BN_UMULT_LOHI(lo,hi,ta,ta); \
3457bded2dbSJung-uk Kim c0 += lo; hi += (c0<lo)?1:0; \
3467bded2dbSJung-uk Kim c1 += hi; c2 += (c1<hi)?1:0; \
3477bded2dbSJung-uk Kim } while(0)
3485c87c606SMark Murray # else
3495c87c606SMark Murray # define mul_add_c(a,b,c0,c1,c2) do { \
3507bded2dbSJung-uk Kim BN_ULONG t1,t2; \
3515c87c606SMark Murray asm ("mulq %3" \
3525c87c606SMark Murray : "=a"(t1),"=d"(t2) \
3535c87c606SMark Murray : "a"(a),"m"(b) \
3545c87c606SMark Murray : "cc"); \
3557bded2dbSJung-uk Kim asm ("addq %3,%0; adcq %4,%1; adcq %5,%2" \
3567bded2dbSJung-uk Kim : "+r"(c0),"+r"(c1),"+r"(c2) \
3577bded2dbSJung-uk Kim : "r"(t1),"r"(t2),"g"(0) \
3585c87c606SMark Murray : "cc"); \
3595c87c606SMark Murray } while (0)
3605c87c606SMark Murray
3615c87c606SMark Murray # define sqr_add_c(a,i,c0,c1,c2) do { \
3627bded2dbSJung-uk Kim BN_ULONG t1,t2; \
3635c87c606SMark Murray asm ("mulq %2" \
3645c87c606SMark Murray : "=a"(t1),"=d"(t2) \
3655c87c606SMark Murray : "a"(a[i]) \
3665c87c606SMark Murray : "cc"); \
3677bded2dbSJung-uk Kim asm ("addq %3,%0; adcq %4,%1; adcq %5,%2" \
3687bded2dbSJung-uk Kim : "+r"(c0),"+r"(c1),"+r"(c2) \
3697bded2dbSJung-uk Kim : "r"(t1),"r"(t2),"g"(0) \
3705c87c606SMark Murray : "cc"); \
3715c87c606SMark Murray } while (0)
3725c87c606SMark Murray
3735c87c606SMark Murray # define mul_add_c2(a,b,c0,c1,c2) do { \
3747bded2dbSJung-uk Kim BN_ULONG t1,t2; \
3755c87c606SMark Murray asm ("mulq %3" \
3765c87c606SMark Murray : "=a"(t1),"=d"(t2) \
3775c87c606SMark Murray : "a"(a),"m"(b) \
3785c87c606SMark Murray : "cc"); \
379751d2991SJung-uk Kim asm ("addq %3,%0; adcq %4,%1; adcq %5,%2" \
380751d2991SJung-uk Kim : "+r"(c0),"+r"(c1),"+r"(c2) \
381751d2991SJung-uk Kim : "r"(t1),"r"(t2),"g"(0) \
3825c87c606SMark Murray : "cc"); \
383751d2991SJung-uk Kim asm ("addq %3,%0; adcq %4,%1; adcq %5,%2" \
384751d2991SJung-uk Kim : "+r"(c0),"+r"(c1),"+r"(c2) \
385751d2991SJung-uk Kim : "r"(t1),"r"(t2),"g"(0) \
3865c87c606SMark Murray : "cc"); \
3875c87c606SMark Murray } while (0)
3885c87c606SMark Murray # endif
3895c87c606SMark Murray
3905c87c606SMark Murray # define sqr_add_c2(a,i,j,c0,c1,c2) \
3915c87c606SMark Murray mul_add_c2((a)[i],(a)[j],c0,c1,c2)
3925c87c606SMark Murray
bn_mul_comba8(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)3935c87c606SMark Murray void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
3945c87c606SMark Murray {
3955c87c606SMark Murray BN_ULONG c1, c2, c3;
3965c87c606SMark Murray
3975c87c606SMark Murray c1 = 0;
3985c87c606SMark Murray c2 = 0;
3995c87c606SMark Murray c3 = 0;
4005c87c606SMark Murray mul_add_c(a[0], b[0], c1, c2, c3);
4015c87c606SMark Murray r[0] = c1;
4025c87c606SMark Murray c1 = 0;
4035c87c606SMark Murray mul_add_c(a[0], b[1], c2, c3, c1);
4045c87c606SMark Murray mul_add_c(a[1], b[0], c2, c3, c1);
4055c87c606SMark Murray r[1] = c2;
4065c87c606SMark Murray c2 = 0;
4075c87c606SMark Murray mul_add_c(a[2], b[0], c3, c1, c2);
4085c87c606SMark Murray mul_add_c(a[1], b[1], c3, c1, c2);
4095c87c606SMark Murray mul_add_c(a[0], b[2], c3, c1, c2);
4105c87c606SMark Murray r[2] = c3;
4115c87c606SMark Murray c3 = 0;
4125c87c606SMark Murray mul_add_c(a[0], b[3], c1, c2, c3);
4135c87c606SMark Murray mul_add_c(a[1], b[2], c1, c2, c3);
4145c87c606SMark Murray mul_add_c(a[2], b[1], c1, c2, c3);
4155c87c606SMark Murray mul_add_c(a[3], b[0], c1, c2, c3);
4165c87c606SMark Murray r[3] = c1;
4175c87c606SMark Murray c1 = 0;
4185c87c606SMark Murray mul_add_c(a[4], b[0], c2, c3, c1);
4195c87c606SMark Murray mul_add_c(a[3], b[1], c2, c3, c1);
4205c87c606SMark Murray mul_add_c(a[2], b[2], c2, c3, c1);
4215c87c606SMark Murray mul_add_c(a[1], b[3], c2, c3, c1);
4225c87c606SMark Murray mul_add_c(a[0], b[4], c2, c3, c1);
4235c87c606SMark Murray r[4] = c2;
4245c87c606SMark Murray c2 = 0;
4255c87c606SMark Murray mul_add_c(a[0], b[5], c3, c1, c2);
4265c87c606SMark Murray mul_add_c(a[1], b[4], c3, c1, c2);
4275c87c606SMark Murray mul_add_c(a[2], b[3], c3, c1, c2);
4285c87c606SMark Murray mul_add_c(a[3], b[2], c3, c1, c2);
4295c87c606SMark Murray mul_add_c(a[4], b[1], c3, c1, c2);
4305c87c606SMark Murray mul_add_c(a[5], b[0], c3, c1, c2);
4315c87c606SMark Murray r[5] = c3;
4325c87c606SMark Murray c3 = 0;
4335c87c606SMark Murray mul_add_c(a[6], b[0], c1, c2, c3);
4345c87c606SMark Murray mul_add_c(a[5], b[1], c1, c2, c3);
4355c87c606SMark Murray mul_add_c(a[4], b[2], c1, c2, c3);
4365c87c606SMark Murray mul_add_c(a[3], b[3], c1, c2, c3);
4375c87c606SMark Murray mul_add_c(a[2], b[4], c1, c2, c3);
4385c87c606SMark Murray mul_add_c(a[1], b[5], c1, c2, c3);
4395c87c606SMark Murray mul_add_c(a[0], b[6], c1, c2, c3);
4405c87c606SMark Murray r[6] = c1;
4415c87c606SMark Murray c1 = 0;
4425c87c606SMark Murray mul_add_c(a[0], b[7], c2, c3, c1);
4435c87c606SMark Murray mul_add_c(a[1], b[6], c2, c3, c1);
4445c87c606SMark Murray mul_add_c(a[2], b[5], c2, c3, c1);
4455c87c606SMark Murray mul_add_c(a[3], b[4], c2, c3, c1);
4465c87c606SMark Murray mul_add_c(a[4], b[3], c2, c3, c1);
4475c87c606SMark Murray mul_add_c(a[5], b[2], c2, c3, c1);
4485c87c606SMark Murray mul_add_c(a[6], b[1], c2, c3, c1);
4495c87c606SMark Murray mul_add_c(a[7], b[0], c2, c3, c1);
4505c87c606SMark Murray r[7] = c2;
4515c87c606SMark Murray c2 = 0;
4525c87c606SMark Murray mul_add_c(a[7], b[1], c3, c1, c2);
4535c87c606SMark Murray mul_add_c(a[6], b[2], c3, c1, c2);
4545c87c606SMark Murray mul_add_c(a[5], b[3], c3, c1, c2);
4555c87c606SMark Murray mul_add_c(a[4], b[4], c3, c1, c2);
4565c87c606SMark Murray mul_add_c(a[3], b[5], c3, c1, c2);
4575c87c606SMark Murray mul_add_c(a[2], b[6], c3, c1, c2);
4585c87c606SMark Murray mul_add_c(a[1], b[7], c3, c1, c2);
4595c87c606SMark Murray r[8] = c3;
4605c87c606SMark Murray c3 = 0;
4615c87c606SMark Murray mul_add_c(a[2], b[7], c1, c2, c3);
4625c87c606SMark Murray mul_add_c(a[3], b[6], c1, c2, c3);
4635c87c606SMark Murray mul_add_c(a[4], b[5], c1, c2, c3);
4645c87c606SMark Murray mul_add_c(a[5], b[4], c1, c2, c3);
4655c87c606SMark Murray mul_add_c(a[6], b[3], c1, c2, c3);
4665c87c606SMark Murray mul_add_c(a[7], b[2], c1, c2, c3);
4675c87c606SMark Murray r[9] = c1;
4685c87c606SMark Murray c1 = 0;
4695c87c606SMark Murray mul_add_c(a[7], b[3], c2, c3, c1);
4705c87c606SMark Murray mul_add_c(a[6], b[4], c2, c3, c1);
4715c87c606SMark Murray mul_add_c(a[5], b[5], c2, c3, c1);
4725c87c606SMark Murray mul_add_c(a[4], b[6], c2, c3, c1);
4735c87c606SMark Murray mul_add_c(a[3], b[7], c2, c3, c1);
4745c87c606SMark Murray r[10] = c2;
4755c87c606SMark Murray c2 = 0;
4765c87c606SMark Murray mul_add_c(a[4], b[7], c3, c1, c2);
4775c87c606SMark Murray mul_add_c(a[5], b[6], c3, c1, c2);
4785c87c606SMark Murray mul_add_c(a[6], b[5], c3, c1, c2);
4795c87c606SMark Murray mul_add_c(a[7], b[4], c3, c1, c2);
4805c87c606SMark Murray r[11] = c3;
4815c87c606SMark Murray c3 = 0;
4825c87c606SMark Murray mul_add_c(a[7], b[5], c1, c2, c3);
4835c87c606SMark Murray mul_add_c(a[6], b[6], c1, c2, c3);
4845c87c606SMark Murray mul_add_c(a[5], b[7], c1, c2, c3);
4855c87c606SMark Murray r[12] = c1;
4865c87c606SMark Murray c1 = 0;
4875c87c606SMark Murray mul_add_c(a[6], b[7], c2, c3, c1);
4885c87c606SMark Murray mul_add_c(a[7], b[6], c2, c3, c1);
4895c87c606SMark Murray r[13] = c2;
4905c87c606SMark Murray c2 = 0;
4915c87c606SMark Murray mul_add_c(a[7], b[7], c3, c1, c2);
4925c87c606SMark Murray r[14] = c3;
4935c87c606SMark Murray r[15] = c1;
4945c87c606SMark Murray }
4955c87c606SMark Murray
bn_mul_comba4(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)4965c87c606SMark Murray void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
4975c87c606SMark Murray {
4985c87c606SMark Murray BN_ULONG c1, c2, c3;
4995c87c606SMark Murray
5005c87c606SMark Murray c1 = 0;
5015c87c606SMark Murray c2 = 0;
5025c87c606SMark Murray c3 = 0;
5035c87c606SMark Murray mul_add_c(a[0], b[0], c1, c2, c3);
5045c87c606SMark Murray r[0] = c1;
5055c87c606SMark Murray c1 = 0;
5065c87c606SMark Murray mul_add_c(a[0], b[1], c2, c3, c1);
5075c87c606SMark Murray mul_add_c(a[1], b[0], c2, c3, c1);
5085c87c606SMark Murray r[1] = c2;
5095c87c606SMark Murray c2 = 0;
5105c87c606SMark Murray mul_add_c(a[2], b[0], c3, c1, c2);
5115c87c606SMark Murray mul_add_c(a[1], b[1], c3, c1, c2);
5125c87c606SMark Murray mul_add_c(a[0], b[2], c3, c1, c2);
5135c87c606SMark Murray r[2] = c3;
5145c87c606SMark Murray c3 = 0;
5155c87c606SMark Murray mul_add_c(a[0], b[3], c1, c2, c3);
5165c87c606SMark Murray mul_add_c(a[1], b[2], c1, c2, c3);
5175c87c606SMark Murray mul_add_c(a[2], b[1], c1, c2, c3);
5185c87c606SMark Murray mul_add_c(a[3], b[0], c1, c2, c3);
5195c87c606SMark Murray r[3] = c1;
5205c87c606SMark Murray c1 = 0;
5215c87c606SMark Murray mul_add_c(a[3], b[1], c2, c3, c1);
5225c87c606SMark Murray mul_add_c(a[2], b[2], c2, c3, c1);
5235c87c606SMark Murray mul_add_c(a[1], b[3], c2, c3, c1);
5245c87c606SMark Murray r[4] = c2;
5255c87c606SMark Murray c2 = 0;
5265c87c606SMark Murray mul_add_c(a[2], b[3], c3, c1, c2);
5275c87c606SMark Murray mul_add_c(a[3], b[2], c3, c1, c2);
5285c87c606SMark Murray r[5] = c3;
5295c87c606SMark Murray c3 = 0;
5305c87c606SMark Murray mul_add_c(a[3], b[3], c1, c2, c3);
5315c87c606SMark Murray r[6] = c1;
5325c87c606SMark Murray r[7] = c2;
5335c87c606SMark Murray }
5345c87c606SMark Murray
bn_sqr_comba8(BN_ULONG * r,const BN_ULONG * a)5356a599222SSimon L. B. Nielsen void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
5365c87c606SMark Murray {
5375c87c606SMark Murray BN_ULONG c1, c2, c3;
5385c87c606SMark Murray
5395c87c606SMark Murray c1 = 0;
5405c87c606SMark Murray c2 = 0;
5415c87c606SMark Murray c3 = 0;
5425c87c606SMark Murray sqr_add_c(a, 0, c1, c2, c3);
5435c87c606SMark Murray r[0] = c1;
5445c87c606SMark Murray c1 = 0;
5455c87c606SMark Murray sqr_add_c2(a, 1, 0, c2, c3, c1);
5465c87c606SMark Murray r[1] = c2;
5475c87c606SMark Murray c2 = 0;
5485c87c606SMark Murray sqr_add_c(a, 1, c3, c1, c2);
5495c87c606SMark Murray sqr_add_c2(a, 2, 0, c3, c1, c2);
5505c87c606SMark Murray r[2] = c3;
5515c87c606SMark Murray c3 = 0;
5525c87c606SMark Murray sqr_add_c2(a, 3, 0, c1, c2, c3);
5535c87c606SMark Murray sqr_add_c2(a, 2, 1, c1, c2, c3);
5545c87c606SMark Murray r[3] = c1;
5555c87c606SMark Murray c1 = 0;
5565c87c606SMark Murray sqr_add_c(a, 2, c2, c3, c1);
5575c87c606SMark Murray sqr_add_c2(a, 3, 1, c2, c3, c1);
5585c87c606SMark Murray sqr_add_c2(a, 4, 0, c2, c3, c1);
5595c87c606SMark Murray r[4] = c2;
5605c87c606SMark Murray c2 = 0;
5615c87c606SMark Murray sqr_add_c2(a, 5, 0, c3, c1, c2);
5625c87c606SMark Murray sqr_add_c2(a, 4, 1, c3, c1, c2);
5635c87c606SMark Murray sqr_add_c2(a, 3, 2, c3, c1, c2);
5645c87c606SMark Murray r[5] = c3;
5655c87c606SMark Murray c3 = 0;
5665c87c606SMark Murray sqr_add_c(a, 3, c1, c2, c3);
5675c87c606SMark Murray sqr_add_c2(a, 4, 2, c1, c2, c3);
5685c87c606SMark Murray sqr_add_c2(a, 5, 1, c1, c2, c3);
5695c87c606SMark Murray sqr_add_c2(a, 6, 0, c1, c2, c3);
5705c87c606SMark Murray r[6] = c1;
5715c87c606SMark Murray c1 = 0;
5725c87c606SMark Murray sqr_add_c2(a, 7, 0, c2, c3, c1);
5735c87c606SMark Murray sqr_add_c2(a, 6, 1, c2, c3, c1);
5745c87c606SMark Murray sqr_add_c2(a, 5, 2, c2, c3, c1);
5755c87c606SMark Murray sqr_add_c2(a, 4, 3, c2, c3, c1);
5765c87c606SMark Murray r[7] = c2;
5775c87c606SMark Murray c2 = 0;
5785c87c606SMark Murray sqr_add_c(a, 4, c3, c1, c2);
5795c87c606SMark Murray sqr_add_c2(a, 5, 3, c3, c1, c2);
5805c87c606SMark Murray sqr_add_c2(a, 6, 2, c3, c1, c2);
5815c87c606SMark Murray sqr_add_c2(a, 7, 1, c3, c1, c2);
5825c87c606SMark Murray r[8] = c3;
5835c87c606SMark Murray c3 = 0;
5845c87c606SMark Murray sqr_add_c2(a, 7, 2, c1, c2, c3);
5855c87c606SMark Murray sqr_add_c2(a, 6, 3, c1, c2, c3);
5865c87c606SMark Murray sqr_add_c2(a, 5, 4, c1, c2, c3);
5875c87c606SMark Murray r[9] = c1;
5885c87c606SMark Murray c1 = 0;
5895c87c606SMark Murray sqr_add_c(a, 5, c2, c3, c1);
5905c87c606SMark Murray sqr_add_c2(a, 6, 4, c2, c3, c1);
5915c87c606SMark Murray sqr_add_c2(a, 7, 3, c2, c3, c1);
5925c87c606SMark Murray r[10] = c2;
5935c87c606SMark Murray c2 = 0;
5945c87c606SMark Murray sqr_add_c2(a, 7, 4, c3, c1, c2);
5955c87c606SMark Murray sqr_add_c2(a, 6, 5, c3, c1, c2);
5965c87c606SMark Murray r[11] = c3;
5975c87c606SMark Murray c3 = 0;
5985c87c606SMark Murray sqr_add_c(a, 6, c1, c2, c3);
5995c87c606SMark Murray sqr_add_c2(a, 7, 5, c1, c2, c3);
6005c87c606SMark Murray r[12] = c1;
6015c87c606SMark Murray c1 = 0;
6025c87c606SMark Murray sqr_add_c2(a, 7, 6, c2, c3, c1);
6035c87c606SMark Murray r[13] = c2;
6045c87c606SMark Murray c2 = 0;
6055c87c606SMark Murray sqr_add_c(a, 7, c3, c1, c2);
6065c87c606SMark Murray r[14] = c3;
6075c87c606SMark Murray r[15] = c1;
6085c87c606SMark Murray }
6095c87c606SMark Murray
bn_sqr_comba4(BN_ULONG * r,const BN_ULONG * a)6106a599222SSimon L. B. Nielsen void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
6115c87c606SMark Murray {
6125c87c606SMark Murray BN_ULONG c1, c2, c3;
6135c87c606SMark Murray
6145c87c606SMark Murray c1 = 0;
6155c87c606SMark Murray c2 = 0;
6165c87c606SMark Murray c3 = 0;
6175c87c606SMark Murray sqr_add_c(a, 0, c1, c2, c3);
6185c87c606SMark Murray r[0] = c1;
6195c87c606SMark Murray c1 = 0;
6205c87c606SMark Murray sqr_add_c2(a, 1, 0, c2, c3, c1);
6215c87c606SMark Murray r[1] = c2;
6225c87c606SMark Murray c2 = 0;
6235c87c606SMark Murray sqr_add_c(a, 1, c3, c1, c2);
6245c87c606SMark Murray sqr_add_c2(a, 2, 0, c3, c1, c2);
6255c87c606SMark Murray r[2] = c3;
6265c87c606SMark Murray c3 = 0;
6275c87c606SMark Murray sqr_add_c2(a, 3, 0, c1, c2, c3);
6285c87c606SMark Murray sqr_add_c2(a, 2, 1, c1, c2, c3);
6295c87c606SMark Murray r[3] = c1;
6305c87c606SMark Murray c1 = 0;
6315c87c606SMark Murray sqr_add_c(a, 2, c2, c3, c1);
6325c87c606SMark Murray sqr_add_c2(a, 3, 1, c2, c3, c1);
6335c87c606SMark Murray r[4] = c2;
6345c87c606SMark Murray c2 = 0;
6355c87c606SMark Murray sqr_add_c2(a, 3, 2, c3, c1, c2);
6365c87c606SMark Murray r[5] = c3;
6375c87c606SMark Murray c3 = 0;
6385c87c606SMark Murray sqr_add_c(a, 3, c1, c2, c3);
6395c87c606SMark Murray r[6] = c1;
6405c87c606SMark Murray r[7] = c2;
6415c87c606SMark Murray }
642ed5d4f9aSSimon L. B. Nielsen #endif
643