« back to all changes in this revision
Viewing changes to integer.cpp
- browse files at revision 567
- compare with another revision
- download diff
- download tarball
- view history from revision 567
- Committer: noloader
- Date: 2015-07-16 04:38:08 UTC
- Revision ID: svn-v4:57ff6487-cd31-0410-9ec3-f628ee90f5f0:trunk/c5:590
Added targets for UBsan and Asan
- files added:
- GNUmakefile-cross
- TestData
- files removed:
- 3desval.dat
- files modified:
- 3way.cpp
added
removed
integer.cpp
14
14
#include "algparam.h"
15
15
#include "pubkey.h" // for P1363_KDF2
16
16
#include "sha.h"
17
#include "cpu.h"
17
18
18
19
#include <iostream>
19
20
20
#ifdef _M_X64
21
#include <Intrin.h>
22
#endif
23
24
#ifdef SSE2_INTRINSICS_AVAILABLE
25
#ifdef __GNUC__
26
#include <xmmintrin.h>
27
#include <signal.h>
28
#include <setjmp.h>
29
#ifdef CRYPTOPP_MEMALIGN_AVAILABLE
30
#include <malloc.h>
31
#else
32
#include <stdlib.h>
33
#endif
34
#else
35
#include <emmintrin.h>
36
#endif
37
#elif defined(_MSC_VER) && defined(_M_IX86)
38
#pragma message("You do not seem to have the Visual C++ Processor Pack installed, so use of SSE2 intrinsics will be disabled.")
39
#elif defined(__GNUC__) && defined(__i386__)
40
#warning "You do not have GCC 3.3 or later, or did not specify -msse2 compiler option, so use of SSE2 intrinsics will be disabled."
41
#endif
21
#if _MSC_VER >= 1400
22
#include <intrin.h>
23
#endif
24
25
#ifdef __DECCXX
26
#include <c_asm.h>
27
#endif
28
29
#ifdef CRYPTOPP_MSVC6_NO_PP
30
#pragma message("You do not seem to have the Visual C++ Processor Pack installed, so use of SSE2 instructions will be disabled.")
31
#endif
32
33
#if GCC_DIAGNOSTIC_AWARE
34
# pragma GCC diagnostic ignored "-Wunused-value"
35
# pragma GCC diagnostic ignored "-Wunused-variable"
36
#endif
37
38
#define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE && CRYPTOPP_BOOL_X86)
42
39
43
40
NAMESPACE_BEGIN(CryptoPP)
44
41
50
47
return true;
51
48
}
52
49
53
#ifdef SSE2_INTRINSICS_AVAILABLE
54
template <class T>
55
CPP_TYPENAME AllocatorBase<T>::pointer AlignedAllocator<T>::allocate(size_type n, const void *)
56
{
57
CheckSize(n);
58
if (n == 0)
59
return NULL;
60
if (n >= 4)
61
{
62
void *p;
63
#ifdef CRYPTOPP_MM_MALLOC_AVAILABLE
64
while (!(p = _mm_malloc(sizeof(T)*n, 16)))
65
#elif defined(CRYPTOPP_MEMALIGN_AVAILABLE)
66
while (!(p = memalign(16, sizeof(T)*n)))
67
#elif defined(CRYPTOPP_MALLOC_ALIGNMENT_IS_16)
68
while (!(p = malloc(sizeof(T)*n)))
69
#else
70
while (!(p = (byte *)malloc(sizeof(T)*n + 8))) // assume malloc alignment is at least 8
71
#endif
72
CallNewHandler();
73
74
#ifdef CRYPTOPP_NO_ALIGNED_ALLOC
75
assert(m_pBlock == NULL);
76
m_pBlock = p;
77
if (!IsAlignedOn(p, 16))
78
{
79
assert(IsAlignedOn(p, 8));
80
p = (byte *)p + 8;
81
}
82
#endif
83
84
assert(IsAlignedOn(p, 16));
85
return (T*)p;
86
}
87
return new T[n];
88
}
89
90
template <class T>
91
void AlignedAllocator<T>::deallocate(void *p, size_type n)
92
{
93
memset(p, 0, n*sizeof(T));
94
if (n >= 4)
95
{
96
#ifdef CRYPTOPP_MM_MALLOC_AVAILABLE
97
_mm_free(p);
98
#elif defined(CRYPTOPP_NO_ALIGNED_ALLOC)
99
assert(m_pBlock == p || (byte *)m_pBlock+8 == p);
100
free(m_pBlock);
101
m_pBlock = NULL;
102
#else
103
free(p);
104
#endif
105
}
106
else
107
delete [] (T *)p;
108
}
109
110
template class CRYPTOPP_DLL AlignedAllocator<word>;
111
#endif
112
113
static int Compare(const word *A, const word *B, size_t N)
50
inline static int Compare(const word *A, const word *B, size_t N)
114
51
{
115
52
while (N--)
116
53
if (A[N] > B[N])
121
58
return 0;
122
59
}
123
60
124
static int Increment(word *A, size_t N, word B=1)
61
inline static int Increment(word *A, size_t N, word B=1)
125
62
{
126
63
assert(N);
127
64
word t = A[0];
134
71
return 1;
135
72
}
136
73
137
static int Decrement(word *A, size_t N, word B=1)
74
inline static int Decrement(word *A, size_t N, word B=1)
138
75
{
139
76
assert(N);
140
77
word t = A[0];
169
106
170
107
// ********************************************************
171
108
109
#if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE))
110
#define Declare2Words(x) word x##0, x##1;
111
#define AssignWord(a, b) a##0 = b; a##1 = 0;
112
#define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c);
113
#define LowWord(a) a##0
114
#define HighWord(a) a##1
115
#ifdef _MSC_VER
116
#define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1);
117
#ifndef __INTEL_COMPILER
118
#define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2;
119
#endif
120
#elif defined(__DECCXX)
121
#define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b);
122
#elif defined(__x86_64__)
123
#if defined(__SUNPRO_CC) && __SUNPRO_CC < 0x5100
124
// Sun Studio's gcc-style inline assembly is heavily bugged as of version 5.9 Patch 124864-09 2008/12/16, but this one works
125
#define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc");
126
#else
127
#define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
128
#define MulAcc(c, d, a, b) asm ("mulq %6; addq %3, %0; adcq %4, %1; adcq $0, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1), "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
129
#define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc");
130
#define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc");
131
#define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc");
132
#define Acc3WordsBy2(c, d, e) asm ("addq %5, %0; adcq %6, %1; adcq $0, %2;" : "+r"(c), "=r"(e##0), "=r"(e##1) : "1"(d##0), "2"(d##1), "r"(e##0), "r"(e##1) : "cc");
133
#endif
134
#endif
135
#define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b)
136
#ifndef Double3Words
137
#define Double3Words(c, d) d##1 = 2*d##1 + (d##0>>(WORD_BITS-1)); d##0 = 2*d##0 + (c>>(WORD_BITS-1)); c *= 2;
138
#endif
139
#ifndef Acc2WordsBy2
140
#define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1;
141
#endif
142
#define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);}
143
#define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);}
144
#define GetCarry(u) u##1
145
#define GetBorrow(u) u##1
146
#else
147
#define Declare2Words(x) dword x;
148
#if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER)
149
#define MultiplyWords(p, a, b) p = __emulu(a, b);
150
#else
151
#define MultiplyWords(p, a, b) p = (dword)a*b;
152
#endif
153
#define AssignWord(a, b) a = b;
154
#define Add2WordsBy1(a, b, c) a = b + c;
155
#define Acc2WordsBy2(a, b) a += b;
156
#define LowWord(a) word(a)
157
#define HighWord(a) word(a>>WORD_BITS)
158
#define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2;
159
#define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u);
160
#define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u);
161
#define GetCarry(u) HighWord(u)
162
#define GetBorrow(u) word(u>>(WORD_BITS*2-1))
163
#endif
164
#ifndef MulAcc
165
#define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p));
166
#endif
167
#ifndef Acc2WordsBy1
168
#define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b)
169
#endif
170
#ifndef Acc3WordsBy2
171
#define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e));
172
#endif
173
172
174
class DWord
173
175
{
174
176
public:
198
200
DWord r;
199
201
#ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
200
202
r.m_whole = (dword)a * b;
201
#elif defined(__alpha__)
202
r.m_halfs.low = a*b; __asm__("umulh %1,%2,%0" : "=r" (r.m_halfs.high) : "r" (a), "r" (b));
203
#elif defined(__ia64__)
204
r.m_halfs.low = a*b; __asm__("xmpy.hu %0=%1,%2" : "=f" (r.m_halfs.high) : "f" (a), "f" (b));
205
#elif defined(_ARCH_PPC64)
206
r.m_halfs.low = a*b; __asm__("mulhdu %0,%1,%2" : "=r" (r.m_halfs.high) : "r" (a), "r" (b) : "cc");
207
#elif defined(__x86_64__)
208
__asm__("mulq %3" : "=d" (r.m_halfs.high), "=a" (r.m_halfs.low) : "a" (a), "rm" (b) : "cc");
209
#elif defined(__mips64)
210
__asm__("dmultu %2,%3" : "=h" (r.m_halfs.high), "=l" (r.m_halfs.low) : "r" (a), "r" (b));
211
#elif defined(_M_X64)
212
r.m_halfs.low = _umul128(a, b, &r.m_halfs.high);
213
#elif defined(_M_IX86)
214
// for testing
215
word64 t = (word64)a * b;
216
r.m_halfs.high = ((word32 *)(&t))[1];
217
r.m_halfs.low = (word32)t;
218
#else
219
#error can not implement DWord
203
#elif defined(MultiplyWordsLoHi)
204
MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
220
205
#endif
221
206
return r;
222
207
}
378
363
S Q;
379
364
if (S(B1+1) == 0)
380
365
Q = A[2];
381
else
366
else if (B1 > 0)
382
367
Q = D(A[1], A[2]) / S(B1+1);
368
else
369
Q = D(A[0], A[1]) / B0;
383
370
384
371
// now subtract Q*B from A
385
372
D p = D::Multiply(B0, Q);
457
444
458
445
// ********************************************************
459
446
460
class Portable
461
{
462
public:
463
static int Add(word *C, const word *A, const word *B, size_t N);
464
static int Subtract(word *C, const word *A, const word *B, size_t N);
465
466
static inline void Multiply2(word *C, const word *A, const word *B);
467
static inline word Multiply2Add(word *C, const word *A, const word *B);
468
static void Multiply4(word *C, const word *A, const word *B);
469
static void Multiply8(word *C, const word *A, const word *B);
470
static inline unsigned int MultiplyRecursionLimit() {return 8;}
471
472
static inline void Multiply2Bottom(word *C, const word *A, const word *B);
473
static void Multiply4Bottom(word *C, const word *A, const word *B);
474
static void Multiply8Bottom(word *C, const word *A, const word *B);
475
static inline unsigned int MultiplyBottomRecursionLimit() {return 8;}
476
477
static void Square2(word *R, const word *A);
478
static void Square4(word *R, const word *A);
479
static void Square8(word *R, const word *A) {assert(false);}
480
static inline unsigned int SquareRecursionLimit() {return 4;}
481
};
482
483
int Portable::Add(word *C, const word *A, const word *B, size_t N)
484
{
485
assert (N%2 == 0);
486
487
DWord u(0, 0);
488
for (unsigned int i = 0; i < N; i+=2)
489
{
490
u = DWord(A[i]) + B[i] + u.GetHighHalf();
491
C[i] = u.GetLowHalf();
492
u = DWord(A[i+1]) + B[i+1] + u.GetHighHalf();
493
C[i+1] = u.GetLowHalf();
494
}
495
return int(u.GetHighHalf());
496
}
497
498
int Portable::Subtract(word *C, const word *A, const word *B, size_t N)
499
{
500
assert (N%2 == 0);
501
502
DWord u(0, 0);
503
for (unsigned int i = 0; i < N; i+=2)
504
{
505
u = (DWord) A[i] - B[i] - u.GetHighHalfAsBorrow();
506
C[i] = u.GetLowHalf();
507
u = (DWord) A[i+1] - B[i+1] - u.GetHighHalfAsBorrow();
508
C[i+1] = u.GetLowHalf();
509
}
510
return int(0-u.GetHighHalf());
511
}
512
513
void Portable::Multiply2(word *C, const word *A, const word *B)
514
{
515
/*
516
word s;
517
dword d;
518
519
if (A1 >= A0)
520
if (B0 >= B1)
521
{
522
s = 0;
523
d = (dword)(A1-A0)*(B0-B1);
524
}
525
else
526
{
527
s = (A1-A0);
528
d = (dword)s*(word)(B0-B1);
529
}
530
else
531
if (B0 > B1)
532
{
533
s = (B0-B1);
534
d = (word)(A1-A0)*(dword)s;
535
}
536
else
537
{
538
s = 0;
539
d = (dword)(A0-A1)*(B1-B0);
540
}
541
*/
542
// this segment is the branchless equivalent of above
543
word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
544
unsigned int ai = A[1] < A[0];
545
unsigned int bi = B[0] < B[1];
546
unsigned int di = ai & bi;
547
DWord d = DWord::Multiply(D[di], D[di+2]);
548
D[1] = D[3] = 0;
549
unsigned int si = ai + !bi;
550
word s = D[si];
551
552
DWord A0B0 = DWord::Multiply(A[0], B[0]);
553
C[0] = A0B0.GetLowHalf();
554
555
DWord A1B1 = DWord::Multiply(A[1], B[1]);
556
DWord t = (DWord) A0B0.GetHighHalf() + A0B0.GetLowHalf() + d.GetLowHalf() + A1B1.GetLowHalf();
557
C[1] = t.GetLowHalf();
558
559
t = A1B1 + t.GetHighHalf() + A0B0.GetHighHalf() + d.GetHighHalf() + A1B1.GetHighHalf() - s;
560
C[2] = t.GetLowHalf();
561
C[3] = t.GetHighHalf();
562
}
563
564
inline void Portable::Multiply2Bottom(word *C, const word *A, const word *B)
565
{
566
DWord t = DWord::Multiply(A[0], B[0]);
567
C[0] = t.GetLowHalf();
568
C[1] = t.GetHighHalf() + A[0]*B[1] + A[1]*B[0];
569
}
570
571
word Portable::Multiply2Add(word *C, const word *A, const word *B)
572
{
573
word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
574
unsigned int ai = A[1] < A[0];
575
unsigned int bi = B[0] < B[1];
576
unsigned int di = ai & bi;
577
DWord d = DWord::Multiply(D[di], D[di+2]);
578
D[1] = D[3] = 0;
579
unsigned int si = ai + !bi;
580
word s = D[si];
581
582
DWord A0B0 = DWord::Multiply(A[0], B[0]);
583
DWord t = A0B0 + C[0];
584
C[0] = t.GetLowHalf();
585
586
DWord A1B1 = DWord::Multiply(A[1], B[1]);
587
t = (DWord) t.GetHighHalf() + A0B0.GetLowHalf() + d.GetLowHalf() + A1B1.GetLowHalf() + C[1];
588
C[1] = t.GetLowHalf();
589
590
t = (DWord) t.GetHighHalf() + A1B1.GetLowHalf() + A0B0.GetHighHalf() + d.GetHighHalf() + A1B1.GetHighHalf() - s + C[2];
591
C[2] = t.GetLowHalf();
592
593
t = (DWord) t.GetHighHalf() + A1B1.GetHighHalf() + C[3];
594
C[3] = t.GetLowHalf();
595
return t.GetHighHalf();
596
}
597
598
#define MulAcc(x, y) \
599
p = DWord::MultiplyAndAdd(A[x], B[y], c); \
600
c = p.GetLowHalf(); \
601
p = (DWord) d + p.GetHighHalf(); \
602
d = p.GetLowHalf(); \
603
e += p.GetHighHalf();
604
605
#define SaveMulAcc(s, x, y) \
606
R[s] = c; \
607
p = DWord::MultiplyAndAdd(A[x], B[y], d); \
608
c = p.GetLowHalf(); \
609
p = (DWord) e + p.GetHighHalf(); \
610
d = p.GetLowHalf(); \
611
e = p.GetHighHalf();
612
613
#define SquAcc(x, y) \
614
q = DWord::Multiply(A[x], A[y]); \
615
p = q + c; \
616
c = p.GetLowHalf(); \
617
p = (DWord) d + p.GetHighHalf(); \
618
d = p.GetLowHalf(); \
619
e += p.GetHighHalf(); \
620
p = q + c; \
621
c = p.GetLowHalf(); \
622
p = (DWord) d + p.GetHighHalf(); \
623
d = p.GetLowHalf(); \
624
e += p.GetHighHalf();
625
626
#define SaveSquAcc(s, x, y) \
627
R[s] = c; \
628
q = DWord::Multiply(A[x], A[y]); \
629
p = q + d; \
630
c = p.GetLowHalf(); \
631
p = (DWord) e + p.GetHighHalf(); \
632
d = p.GetLowHalf(); \
633
e = p.GetHighHalf(); \
634
p = q + c; \
635
c = p.GetLowHalf(); \
636
p = (DWord) d + p.GetHighHalf(); \
637
d = p.GetLowHalf(); \
638
e += p.GetHighHalf();
639
640
void Portable::Multiply4(word *R, const word *A, const word *B)
641
{
642
DWord p;
643
word c, d, e;
644
645
p = DWord::Multiply(A[0], B[0]);
646
R[0] = p.GetLowHalf();
647
c = p.GetHighHalf();
648
d = e = 0;
649
650
MulAcc(0, 1);
651
MulAcc(1, 0);
652
653
SaveMulAcc(1, 2, 0);
654
MulAcc(1, 1);
655
MulAcc(0, 2);
656
657
SaveMulAcc(2, 0, 3);
658
MulAcc(1, 2);
659
MulAcc(2, 1);
660
MulAcc(3, 0);
661
662
SaveMulAcc(3, 3, 1);
663
MulAcc(2, 2);
664
MulAcc(1, 3);
665
666
SaveMulAcc(4, 2, 3);
667
MulAcc(3, 2);
668
669
R[5] = c;
670
p = DWord::MultiplyAndAdd(A[3], B[3], d);
671
R[6] = p.GetLowHalf();
672
R[7] = e + p.GetHighHalf();
673
}
674
675
void Portable::Square2(word *R, const word *A)
676
{
677
DWord p, q;
678
word c, d, e;
679
680
p = DWord::Multiply(A[0], A[0]);
681
R[0] = p.GetLowHalf();
682
c = p.GetHighHalf();
683
d = e = 0;
684
685
SquAcc(0, 1);
686
687
R[1] = c;
688
p = DWord::MultiplyAndAdd(A[1], A[1], d);
689
R[2] = p.GetLowHalf();
690
R[3] = e + p.GetHighHalf();
691
}
692
693
void Portable::Square4(word *R, const word *A)
694
{
695
#ifdef _MSC_VER
696
// VC60 workaround: MSVC 6.0 has an optimization bug that makes
697
// (dword)A*B where either A or B has been cast to a dword before
698
// very expensive. Revisit this function when this
699
// bug is fixed.
700
Multiply4(R, A, A);
701
#else
702
const word *B = A;
703
DWord p, q;
704
word c, d, e;
705
706
p = DWord::Multiply(A[0], A[0]);
707
R[0] = p.GetLowHalf();
708
c = p.GetHighHalf();
709
d = e = 0;
710
711
SquAcc(0, 1);
712
713
SaveSquAcc(1, 2, 0);
714
MulAcc(1, 1);
715
716
SaveSquAcc(2, 0, 3);
717
SquAcc(1, 2);
718
719
SaveSquAcc(3, 3, 1);
720
MulAcc(2, 2);
721
722
SaveSquAcc(4, 2, 3);
723
724
R[5] = c;
725
p = DWord::MultiplyAndAdd(A[3], A[3], d);
726
R[6] = p.GetLowHalf();
727
R[7] = e + p.GetHighHalf();
728
#endif
729
}
730
731
void Portable::Multiply8(word *R, const word *A, const word *B)
732
{
733
DWord p;
734
word c, d, e;
735
736
p = DWord::Multiply(A[0], B[0]);
737
R[0] = p.GetLowHalf();
738
c = p.GetHighHalf();
739
d = e = 0;
740
741
MulAcc(0, 1);
742
MulAcc(1, 0);
743
744
SaveMulAcc(1, 2, 0);
745
MulAcc(1, 1);
746
MulAcc(0, 2);
747
748
SaveMulAcc(2, 0, 3);
749
MulAcc(1, 2);
750
MulAcc(2, 1);
751
MulAcc(3, 0);
752
753
SaveMulAcc(3, 0, 4);
754
MulAcc(1, 3);
755
MulAcc(2, 2);
756
MulAcc(3, 1);
757
MulAcc(4, 0);
758
759
SaveMulAcc(4, 0, 5);
760
MulAcc(1, 4);
761
MulAcc(2, 3);
762
MulAcc(3, 2);
763
MulAcc(4, 1);
764
MulAcc(5, 0);
765
766
SaveMulAcc(5, 0, 6);
767
MulAcc(1, 5);
768
MulAcc(2, 4);
769
MulAcc(3, 3);
770
MulAcc(4, 2);
771
MulAcc(5, 1);
772
MulAcc(6, 0);
773
774
SaveMulAcc(6, 0, 7);
775
MulAcc(1, 6);
776
MulAcc(2, 5);
777
MulAcc(3, 4);
778
MulAcc(4, 3);
779
MulAcc(5, 2);
780
MulAcc(6, 1);
781
MulAcc(7, 0);
782
783
SaveMulAcc(7, 1, 7);
784
MulAcc(2, 6);
785
MulAcc(3, 5);
786
MulAcc(4, 4);
787
MulAcc(5, 3);
788
MulAcc(6, 2);
789
MulAcc(7, 1);
790
791
SaveMulAcc(8, 2, 7);
792
MulAcc(3, 6);
793
MulAcc(4, 5);
794
MulAcc(5, 4);
795
MulAcc(6, 3);
796
MulAcc(7, 2);
797
798
SaveMulAcc(9, 3, 7);
799
MulAcc(4, 6);
800
MulAcc(5, 5);
801
MulAcc(6, 4);
802
MulAcc(7, 3);
803
804
SaveMulAcc(10, 4, 7);
805
MulAcc(5, 6);
806
MulAcc(6, 5);
807
MulAcc(7, 4);
808
809
SaveMulAcc(11, 5, 7);
810
MulAcc(6, 6);
811
MulAcc(7, 5);
812
813
SaveMulAcc(12, 6, 7);
814
MulAcc(7, 6);
815
816
R[13] = c;
817
p = DWord::MultiplyAndAdd(A[7], B[7], d);
818
R[14] = p.GetLowHalf();
819
R[15] = e + p.GetHighHalf();
820
}
821
822
void Portable::Multiply4Bottom(word *R, const word *A, const word *B)
823
{
824
DWord p;
825
word c, d, e;
826
827
p = DWord::Multiply(A[0], B[0]);
828
R[0] = p.GetLowHalf();
829
c = p.GetHighHalf();
830
d = e = 0;
831
832
MulAcc(0, 1);
833
MulAcc(1, 0);
834
835
SaveMulAcc(1, 2, 0);
836
MulAcc(1, 1);
837
MulAcc(0, 2);
838
839
R[2] = c;
840
R[3] = d + A[0] * B[3] + A[1] * B[2] + A[2] * B[1] + A[3] * B[0];
841
}
842
843
void Portable::Multiply8Bottom(word *R, const word *A, const word *B)
844
{
845
DWord p;
846
word c, d, e;
847
848
p = DWord::Multiply(A[0], B[0]);
849
R[0] = p.GetLowHalf();
850
c = p.GetHighHalf();
851
d = e = 0;
852
853
MulAcc(0, 1);
854
MulAcc(1, 0);
855
856
SaveMulAcc(1, 2, 0);
857
MulAcc(1, 1);
858
MulAcc(0, 2);
859
860
SaveMulAcc(2, 0, 3);
861
MulAcc(1, 2);
862
MulAcc(2, 1);
863
MulAcc(3, 0);
864
865
SaveMulAcc(3, 0, 4);
866
MulAcc(1, 3);
867
MulAcc(2, 2);
868
MulAcc(3, 1);
869
MulAcc(4, 0);
870
871
SaveMulAcc(4, 0, 5);
872
MulAcc(1, 4);
873
MulAcc(2, 3);
874
MulAcc(3, 2);
875
MulAcc(4, 1);
876
MulAcc(5, 0);
877
878
SaveMulAcc(5, 0, 6);
879
MulAcc(1, 5);
880
MulAcc(2, 4);
881
MulAcc(3, 3);
882
MulAcc(4, 2);
883
MulAcc(5, 1);
884
MulAcc(6, 0);
885
886
R[6] = c;
887
R[7] = d + A[0] * B[7] + A[1] * B[6] + A[2] * B[5] + A[3] * B[4] +
888
A[4] * B[3] + A[5] * B[2] + A[6] * B[1] + A[7] * B[0];
889
}
890
891
#undef MulAcc
892
#undef SaveMulAcc
893
#undef SquAcc
894
#undef SaveSquAcc
895
896
#ifdef CRYPTOPP_X86ASM_AVAILABLE
897
898
// ************** x86 feature detection ***************
899
900
static bool s_sse2Enabled = true;
901
902
static void CpuId(word32 input, word32 *output)
903
{
904
#ifdef __GNUC__
905
__asm__
906
(
907
// save ebx in case -fPIC is being used
908
"push %%ebx; cpuid; mov %%ebx, %%edi; pop %%ebx"
909
: "=a" (output[0]), "=D" (output[1]), "=c" (output[2]), "=d" (output[3])
910
: "a" (input)
911
);
912
#else
913
__asm
914
{
915
mov eax, input
916
cpuid
917
mov edi, output
918
mov [edi], eax
919
mov [edi+4], ebx
920
mov [edi+8], ecx
921
mov [edi+12], edx
922
}
923
#endif
924
}
925
926
#ifdef SSE2_INTRINSICS_AVAILABLE
927
#ifndef _MSC_VER
928
static jmp_buf s_env;
929
static void SigIllHandler(int)
930
{
931
longjmp(s_env, 1);
932
}
933
#endif
934
935
static bool HasSSE2()
936
{
937
if (!s_sse2Enabled)
938
return false;
939
940
word32 cpuid[4];
941
CpuId(1, cpuid);
942
if ((cpuid[3] & (1 << 26)) == 0)
943
return false;
944
945
#ifdef _MSC_VER
946
__try
947
{
948
__asm xorpd xmm0, xmm0 // executing SSE2 instruction
949
}
950
__except (1)
951
{
952
return false;
953
}
954
return true;
955
#else
956
typedef void (*SigHandler)(int);
957
958
SigHandler oldHandler = signal(SIGILL, SigIllHandler);
959
if (oldHandler == SIG_ERR)
960
return false;
961
962
bool result = true;
963
if (setjmp(s_env))
964
result = false;
965
else
966
__asm __volatile ("xorps %xmm0, %xmm0");
967
968
signal(SIGILL, oldHandler);
969
return result;
970
#endif
971
}
972
#endif
973
974
static bool IsP4()
975
{
976
word32 cpuid[4];
977
978
CpuId(0, cpuid);
979
std::swap(cpuid[2], cpuid[3]);
980
if (memcmp(cpuid+1, "GenuineIntel", 12) != 0)
981
return false;
982
983
CpuId(1, cpuid);
984
return ((cpuid[0] >> 8) & 0xf) == 0xf;
985
}
986
987
// ************** Pentium/P4 optimizations ***************
988
989
class PentiumOptimized : public Portable
990
{
991
public:
992
static int Add(word *C, const word *A, const word *B, size_t N);
993
static int Subtract(word *C, const word *A, const word *B, size_t N);
994
static void Multiply4(word *C, const word *A, const word *B);
995
static void Multiply8(word *C, const word *A, const word *B);
996
static void Multiply8Bottom(word *C, const word *A, const word *B);
997
};
998
999
class P4Optimized
1000
{
1001
public:
1002
static int Add(word *C, const word *A, const word *B, size_t N);
1003
static int Subtract(word *C, const word *A, const word *B, size_t N);
1004
#ifdef SSE2_INTRINSICS_AVAILABLE
1005
static void Multiply4(word *C, const word *A, const word *B);
1006
static void Multiply8(word *C, const word *A, const word *B);
1007
static void Multiply8Bottom(word *C, const word *A, const word *B);
1008
#endif
1009
};
1010
1011
typedef int (* PAddSub)(word *C, const word *A, const word *B, size_t N);
447
// use some tricks to share assembly code between MSVC and GCC
448
#if defined(__GNUC__)
449
#define AddPrologue \
450
int result; \
451
__asm__ __volatile__ \
452
( \
453
".intel_syntax noprefix;"
454
#define AddEpilogue \
455
".att_syntax prefix;" \
456
: "=a" (result)\
457
: "d" (C), "a" (A), "D" (B), "c" (N) \
458
: "%esi", "memory", "cc" \
459
);\
460
return result;
461
#define MulPrologue \
462
__asm__ __volatile__ \
463
( \
464
".intel_syntax noprefix;" \
465
AS1( push ebx) \
466
AS2( mov ebx, edx)
467
#define MulEpilogue \
468
AS1( pop ebx) \
469
".att_syntax prefix;" \
470
: \
471
: "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \
472
: "%esi", "memory", "cc" \
473
);
474
#define SquPrologue MulPrologue
475
#define SquEpilogue \
476
AS1( pop ebx) \
477
".att_syntax prefix;" \
478
: \
479
: "d" (s_maskLow16), "c" (C), "a" (A) \
480
: "%esi", "%edi", "memory", "cc" \
481
);
482
#define TopPrologue MulPrologue
483
#define TopEpilogue \
484
AS1( pop ebx) \
485
".att_syntax prefix;" \
486
: \
487
: "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \
488
: "memory", "cc" \
489
);
490
#else
491
#define AddPrologue \
492
__asm push edi \
493
__asm push esi \
494
__asm mov eax, [esp+12] \
495
__asm mov edi, [esp+16]
496
#define AddEpilogue \
497
__asm pop esi \
498
__asm pop edi \
499
__asm ret 8
500
#if _MSC_VER < 1300
501
#define SaveEBX __asm push ebx
502
#define RestoreEBX __asm pop ebx
503
#else
504
#define SaveEBX
505
#define RestoreEBX
506
#endif
507
#define SquPrologue \
508
AS2( mov eax, A) \
509
AS2( mov ecx, C) \
510
SaveEBX \
511
AS2( lea ebx, s_maskLow16)
512
#define MulPrologue \
513
AS2( mov eax, A) \
514
AS2( mov edi, B) \
515
AS2( mov ecx, C) \
516
SaveEBX \
517
AS2( lea ebx, s_maskLow16)
518
#define TopPrologue \
519
AS2( mov eax, A) \
520
AS2( mov edi, B) \
521
AS2( mov ecx, C) \
522
AS2( mov esi, L) \
523
SaveEBX \
524
AS2( lea ebx, s_maskLow16)
525
#define SquEpilogue RestoreEBX
526
#define MulEpilogue RestoreEBX
527
#define TopEpilogue RestoreEBX
528
#endif
529
530
#ifdef CRYPTOPP_X64_MASM_AVAILABLE
531
extern "C" {
532
int Baseline_Add(size_t N, word *C, const word *A, const word *B);
533
int Baseline_Sub(size_t N, word *C, const word *A, const word *B);
534
}
535
#elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE)
536
int Baseline_Add(size_t N, word *C, const word *A, const word *B)
537
{
538
word result;
539
__asm__ __volatile__
540
(
541
".intel_syntax;"
542
AS1( neg %1)
543
ASJ( jz, 1, f)
544
AS2( mov %0,[%3+8*%1])
545
AS2( add %0,[%4+8*%1])
546
AS2( mov [%2+8*%1],%0)
547
ASL(0)
548
AS2( mov %0,[%3+8*%1+8])
549
AS2( adc %0,[%4+8*%1+8])
550
AS2( mov [%2+8*%1+8],%0)
551
AS2( lea %1,[%1+2])
552
ASJ( jrcxz, 1, f)
553
AS2( mov %0,[%3+8*%1])
554
AS2( adc %0,[%4+8*%1])
555
AS2( mov [%2+8*%1],%0)
556
ASJ( jmp, 0, b)
557
ASL(1)
558
AS2( mov %0, 0)
559
AS2( adc %0, %0)
560
".att_syntax;"
561
: "=&r" (result), "+c" (N)
562
: "r" (C+N), "r" (A+N), "r" (B+N)
563
: "memory", "cc"
564
);
565
return (int)result;
566
}
567
568
int Baseline_Sub(size_t N, word *C, const word *A, const word *B)
569
{
570
word result;
571
__asm__ __volatile__
572
(
573
".intel_syntax;"
574
AS1( neg %1)
575
ASJ( jz, 1, f)
576
AS2( mov %0,[%3+8*%1])
577
AS2( sub %0,[%4+8*%1])
578
AS2( mov [%2+8*%1],%0)
579
ASL(0)
580
AS2( mov %0,[%3+8*%1+8])
581
AS2( sbb %0,[%4+8*%1+8])
582
AS2( mov [%2+8*%1+8],%0)
583
AS2( lea %1,[%1+2])
584
ASJ( jrcxz, 1, f)
585
AS2( mov %0,[%3+8*%1])
586
AS2( sbb %0,[%4+8*%1])
587
AS2( mov [%2+8*%1],%0)
588
ASJ( jmp, 0, b)
589
ASL(1)
590
AS2( mov %0, 0)
591
AS2( adc %0, %0)
592
".att_syntax;"
593
: "=&r" (result), "+c" (N)
594
: "r" (C+N), "r" (A+N), "r" (B+N)
595
: "memory", "cc"
596
);
597
return (int)result;
598
}
599
#elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86
600
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
601
{
602
AddPrologue
603
604
// now: eax = A, edi = B, edx = C, ecx = N
605
AS2( lea eax, [eax+4*ecx])
606
AS2( lea edi, [edi+4*ecx])
607
AS2( lea edx, [edx+4*ecx])
608
609
AS1( neg ecx) // ecx is negative index
610
AS2( test ecx, 2) // this clears carry flag
611
ASJ( jz, 0, f)
612
AS2( sub ecx, 2)
613
ASJ( jmp, 1, f)
614
615
ASL(0)
616
ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero
617
AS2( mov esi,[eax+4*ecx])
618
AS2( adc esi,[edi+4*ecx])
619
AS2( mov [edx+4*ecx],esi)
620
AS2( mov esi,[eax+4*ecx+4])
621
AS2( adc esi,[edi+4*ecx+4])
622
AS2( mov [edx+4*ecx+4],esi)
623
ASL(1)
624
AS2( mov esi,[eax+4*ecx+8])
625
AS2( adc esi,[edi+4*ecx+8])
626
AS2( mov [edx+4*ecx+8],esi)
627
AS2( mov esi,[eax+4*ecx+12])
628
AS2( adc esi,[edi+4*ecx+12])
629
AS2( mov [edx+4*ecx+12],esi)
630
631
AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2
632
ASJ( jmp, 0, b)
633
634
ASL(2)
635
AS2( mov eax, 0)
636
AS1( setc al) // store carry into eax (return result register)
637
638
AddEpilogue
639
}
640
641
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
642
{
643
AddPrologue
644
645
// now: eax = A, edi = B, edx = C, ecx = N
646
AS2( lea eax, [eax+4*ecx])
647
AS2( lea edi, [edi+4*ecx])
648
AS2( lea edx, [edx+4*ecx])
649
650
AS1( neg ecx) // ecx is negative index
651
AS2( test ecx, 2) // this clears carry flag
652
ASJ( jz, 0, f)
653
AS2( sub ecx, 2)
654
ASJ( jmp, 1, f)
655
656
ASL(0)
657
ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero
658
AS2( mov esi,[eax+4*ecx])
659
AS2( sbb esi,[edi+4*ecx])
660
AS2( mov [edx+4*ecx],esi)
661
AS2( mov esi,[eax+4*ecx+4])
662
AS2( sbb esi,[edi+4*ecx+4])
663
AS2( mov [edx+4*ecx+4],esi)
664
ASL(1)
665
AS2( mov esi,[eax+4*ecx+8])
666
AS2( sbb esi,[edi+4*ecx+8])
667
AS2( mov [edx+4*ecx+8],esi)
668
AS2( mov esi,[eax+4*ecx+12])
669
AS2( sbb esi,[edi+4*ecx+12])
670
AS2( mov [edx+4*ecx+12],esi)
671
672
AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2
673
ASJ( jmp, 0, b)
674
675
ASL(2)
676
AS2( mov eax, 0)
677
AS1( setc al) // store carry into eax (return result register)
678
679
AddEpilogue
680
}
681
682
#if CRYPTOPP_INTEGER_SSE2
683
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Add(size_t N, word *C, const word *A, const word *B)
684
{
685
AddPrologue
686
687
// now: eax = A, edi = B, edx = C, ecx = N
688
AS2( lea eax, [eax+4*ecx])
689
AS2( lea edi, [edi+4*ecx])
690
AS2( lea edx, [edx+4*ecx])
691
692
AS1( neg ecx) // ecx is negative index
693
AS2( pxor mm2, mm2)
694
ASJ( jz, 2, f)
695
AS2( test ecx, 2) // this clears carry flag
696
ASJ( jz, 0, f)
697
AS2( sub ecx, 2)
698
ASJ( jmp, 1, f)
699
700
ASL(0)
701
AS2( movd mm0, DWORD PTR [eax+4*ecx])
702
AS2( movd mm1, DWORD PTR [edi+4*ecx])
703
AS2( paddq mm0, mm1)
704
AS2( paddq mm2, mm0)
705
AS2( movd DWORD PTR [edx+4*ecx], mm2)
706
AS2( psrlq mm2, 32)
707
708
AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
709
AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
710
AS2( paddq mm0, mm1)
711
AS2( paddq mm2, mm0)
712
AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
713
AS2( psrlq mm2, 32)
714
715
ASL(1)
716
AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
717
AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
718
AS2( paddq mm0, mm1)
719
AS2( paddq mm2, mm0)
720
AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
721
AS2( psrlq mm2, 32)
722
723
AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
724
AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
725
AS2( paddq mm0, mm1)
726
AS2( paddq mm2, mm0)
727
AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
728
AS2( psrlq mm2, 32)
729
730
AS2( add ecx, 4)
731
ASJ( jnz, 0, b)
732
733
ASL(2)
734
AS2( movd eax, mm2)
735
AS1( emms)
736
737
AddEpilogue
738
}
739
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Sub(size_t N, word *C, const word *A, const word *B)
740
{
741
AddPrologue
742
743
// now: eax = A, edi = B, edx = C, ecx = N
744
AS2( lea eax, [eax+4*ecx])
745
AS2( lea edi, [edi+4*ecx])
746
AS2( lea edx, [edx+4*ecx])
747
748
AS1( neg ecx) // ecx is negative index
749
AS2( pxor mm2, mm2)
750
ASJ( jz, 2, f)
751
AS2( test ecx, 2) // this clears carry flag
752
ASJ( jz, 0, f)
753
AS2( sub ecx, 2)
754
ASJ( jmp, 1, f)
755
756
ASL(0)
757
AS2( movd mm0, DWORD PTR [eax+4*ecx])
758
AS2( movd mm1, DWORD PTR [edi+4*ecx])
759
AS2( psubq mm0, mm1)
760
AS2( psubq mm0, mm2)
761
AS2( movd DWORD PTR [edx+4*ecx], mm0)
762
AS2( psrlq mm0, 63)
763
764
AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
765
AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
766
AS2( psubq mm2, mm1)
767
AS2( psubq mm2, mm0)
768
AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
769
AS2( psrlq mm2, 63)
770
771
ASL(1)
772
AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
773
AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
774
AS2( psubq mm0, mm1)
775
AS2( psubq mm0, mm2)
776
AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
777
AS2( psrlq mm0, 63)
778
779
AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
780
AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
781
AS2( psubq mm2, mm1)
782
AS2( psubq mm2, mm0)
783
AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
784
AS2( psrlq mm2, 63)
785
786
AS2( add ecx, 4)
787
ASJ( jnz, 0, b)
788
789
ASL(2)
790
AS2( movd eax, mm2)
791
AS1( emms)
792
793
AddEpilogue
794
}
795
#endif // #if CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE
796
#else
797
int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
798
{
799
assert (N%2 == 0);
800
801
Declare2Words(u);
802
AssignWord(u, 0);
803
for (size_t i=0; i<N; i+=2)
804
{
805
AddWithCarry(u, A[i], B[i]);
806
C[i] = LowWord(u);
807
AddWithCarry(u, A[i+1], B[i+1]);
808
C[i+1] = LowWord(u);
809
}
810
return int(GetCarry(u));
811
}
812
813
int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
814
{
815
assert (N%2 == 0);
816
817
Declare2Words(u);
818
AssignWord(u, 0);
819
for (size_t i=0; i<N; i+=2)
820
{
821
SubtractWithBorrow(u, A[i], B[i]);
822
C[i] = LowWord(u);
823
SubtractWithBorrow(u, A[i+1], B[i+1]);
824
C[i+1] = LowWord(u);
825
}
826
return int(GetBorrow(u));
827
}
828
#endif
829
830
static word LinearMultiply(word *C, const word *A, word B, size_t N)
831
{
832
word carry=0;
833
for(unsigned i=0; i<N; i++)
834
{
835
Declare2Words(p);
836
MultiplyWords(p, A[i], B);
837
Acc2WordsBy1(p, carry);
838
C[i] = LowWord(p);
839
carry = HighWord(p);
840
}
841
return carry;
842
}
843
844
#ifndef CRYPTOPP_DOXYGEN_PROCESSING
845
846
#define Mul_2 \
847
Mul_Begin(2) \
848
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
849
Mul_End(1, 1)
850
851
#define Mul_4 \
852
Mul_Begin(4) \
853
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
854
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
855
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
856
Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
857
Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \
858
Mul_End(5, 3)
859
860
#define Mul_8 \
861
Mul_Begin(8) \
862
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
863
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
864
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
865
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
866
Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
867
Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
868
Mul_SaveAcc(6, 0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
869
Mul_SaveAcc(7, 1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) \
870
Mul_SaveAcc(8, 2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) \
871
Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
872
Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
873
Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
874
Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \
875
Mul_End(13, 7)
876
877
#define Mul_16 \
878
Mul_Begin(16) \
879
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
880
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
881
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
882
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
883
Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
884
Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
885
Mul_SaveAcc(6, 0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
886
Mul_SaveAcc(7, 0, 8) Mul_Acc(1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) Mul_Acc(8, 0) \
887
Mul_SaveAcc(8, 0, 9) Mul_Acc(1, 8) Mul_Acc(2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) Mul_Acc(8, 1) Mul_Acc(9, 0) \
888
Mul_SaveAcc(9, 0, 10) Mul_Acc(1, 9) Mul_Acc(2, 8) Mul_Acc(3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) Mul_Acc(8, 2) Mul_Acc(9, 1) Mul_Acc(10, 0) \
889
Mul_SaveAcc(10, 0, 11) Mul_Acc(1, 10) Mul_Acc(2, 9) Mul_Acc(3, 8) Mul_Acc(4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) Mul_Acc(8, 3) Mul_Acc(9, 2) Mul_Acc(10, 1) Mul_Acc(11, 0) \
890
Mul_SaveAcc(11, 0, 12) Mul_Acc(1, 11) Mul_Acc(2, 10) Mul_Acc(3, 9) Mul_Acc(4, 8) Mul_Acc(5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) Mul_Acc(8, 4) Mul_Acc(9, 3) Mul_Acc(10, 2) Mul_Acc(11, 1) Mul_Acc(12, 0) \
891
Mul_SaveAcc(12, 0, 13) Mul_Acc(1, 12) Mul_Acc(2, 11) Mul_Acc(3, 10) Mul_Acc(4, 9) Mul_Acc(5, 8) Mul_Acc(6, 7) Mul_Acc(7, 6) Mul_Acc(8, 5) Mul_Acc(9, 4) Mul_Acc(10, 3) Mul_Acc(11, 2) Mul_Acc(12, 1) Mul_Acc(13, 0) \
892
Mul_SaveAcc(13, 0, 14) Mul_Acc(1, 13) Mul_Acc(2, 12) Mul_Acc(3, 11) Mul_Acc(4, 10) Mul_Acc(5, 9) Mul_Acc(6, 8) Mul_Acc(7, 7) Mul_Acc(8, 6) Mul_Acc(9, 5) Mul_Acc(10, 4) Mul_Acc(11, 3) Mul_Acc(12, 2) Mul_Acc(13, 1) Mul_Acc(14, 0) \
893
Mul_SaveAcc(14, 0, 15) Mul_Acc(1, 14) Mul_Acc(2, 13) Mul_Acc(3, 12) Mul_Acc(4, 11) Mul_Acc(5, 10) Mul_Acc(6, 9) Mul_Acc(7, 8) Mul_Acc(8, 7) Mul_Acc(9, 6) Mul_Acc(10, 5) Mul_Acc(11, 4) Mul_Acc(12, 3) Mul_Acc(13, 2) Mul_Acc(14, 1) Mul_Acc(15, 0) \
894
Mul_SaveAcc(15, 1, 15) Mul_Acc(2, 14) Mul_Acc(3, 13) Mul_Acc(4, 12) Mul_Acc(5, 11) Mul_Acc(6, 10) Mul_Acc(7, 9) Mul_Acc(8, 8) Mul_Acc(9, 7) Mul_Acc(10, 6) Mul_Acc(11, 5) Mul_Acc(12, 4) Mul_Acc(13, 3) Mul_Acc(14, 2) Mul_Acc(15, 1) \
895
Mul_SaveAcc(16, 2, 15) Mul_Acc(3, 14) Mul_Acc(4, 13) Mul_Acc(5, 12) Mul_Acc(6, 11) Mul_Acc(7, 10) Mul_Acc(8, 9) Mul_Acc(9, 8) Mul_Acc(10, 7) Mul_Acc(11, 6) Mul_Acc(12, 5) Mul_Acc(13, 4) Mul_Acc(14, 3) Mul_Acc(15, 2) \
896
Mul_SaveAcc(17, 3, 15) Mul_Acc(4, 14) Mul_Acc(5, 13) Mul_Acc(6, 12) Mul_Acc(7, 11) Mul_Acc(8, 10) Mul_Acc(9, 9) Mul_Acc(10, 8) Mul_Acc(11, 7) Mul_Acc(12, 6) Mul_Acc(13, 5) Mul_Acc(14, 4) Mul_Acc(15, 3) \
897
Mul_SaveAcc(18, 4, 15) Mul_Acc(5, 14) Mul_Acc(6, 13) Mul_Acc(7, 12) Mul_Acc(8, 11) Mul_Acc(9, 10) Mul_Acc(10, 9) Mul_Acc(11, 8) Mul_Acc(12, 7) Mul_Acc(13, 6) Mul_Acc(14, 5) Mul_Acc(15, 4) \
898
Mul_SaveAcc(19, 5, 15) Mul_Acc(6, 14) Mul_Acc(7, 13) Mul_Acc(8, 12) Mul_Acc(9, 11) Mul_Acc(10, 10) Mul_Acc(11, 9) Mul_Acc(12, 8) Mul_Acc(13, 7) Mul_Acc(14, 6) Mul_Acc(15, 5) \
899
Mul_SaveAcc(20, 6, 15) Mul_Acc(7, 14) Mul_Acc(8, 13) Mul_Acc(9, 12) Mul_Acc(10, 11) Mul_Acc(11, 10) Mul_Acc(12, 9) Mul_Acc(13, 8) Mul_Acc(14, 7) Mul_Acc(15, 6) \
900
Mul_SaveAcc(21, 7, 15) Mul_Acc(8, 14) Mul_Acc(9, 13) Mul_Acc(10, 12) Mul_Acc(11, 11) Mul_Acc(12, 10) Mul_Acc(13, 9) Mul_Acc(14, 8) Mul_Acc(15, 7) \
901
Mul_SaveAcc(22, 8, 15) Mul_Acc(9, 14) Mul_Acc(10, 13) Mul_Acc(11, 12) Mul_Acc(12, 11) Mul_Acc(13, 10) Mul_Acc(14, 9) Mul_Acc(15, 8) \
902
Mul_SaveAcc(23, 9, 15) Mul_Acc(10, 14) Mul_Acc(11, 13) Mul_Acc(12, 12) Mul_Acc(13, 11) Mul_Acc(14, 10) Mul_Acc(15, 9) \
903
Mul_SaveAcc(24, 10, 15) Mul_Acc(11, 14) Mul_Acc(12, 13) Mul_Acc(13, 12) Mul_Acc(14, 11) Mul_Acc(15, 10) \
904
Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
905
Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
906
Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
907
Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \
908
Mul_End(29, 15)
909
910
#define Squ_2 \
911
Squ_Begin(2) \
912
Squ_End(2)
913
914
#define Squ_4 \
915
Squ_Begin(4) \
916
Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
917
Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
918
Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \
919
Squ_SaveAcc(4, 2, 3) Squ_NonDiag \
920
Squ_End(4)
921
922
#define Squ_8 \
923
Squ_Begin(8) \
924
Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
925
Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
926
Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
927
Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
928
Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
929
Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
930
Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
931
Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
932
Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
933
Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \
934
Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \
935
Squ_SaveAcc(12, 6, 7) Squ_NonDiag \
936
Squ_End(8)
937
938
#define Squ_16 \
939
Squ_Begin(16) \
940
Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
941
Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
942
Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
943
Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
944
Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
945
Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
946
Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
947
Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
948
Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
949
Squ_SaveAcc(10, 0, 11) Squ_Acc(1, 10) Squ_Acc(2, 9) Squ_Acc(3, 8) Squ_Acc(4, 7) Squ_Acc(5, 6) Squ_NonDiag \
950
Squ_SaveAcc(11, 0, 12) Squ_Acc(1, 11) Squ_Acc(2, 10) Squ_Acc(3, 9) Squ_Acc(4, 8) Squ_Acc(5, 7) Squ_Diag(6) \
951
Squ_SaveAcc(12, 0, 13) Squ_Acc(1, 12) Squ_Acc(2, 11) Squ_Acc(3, 10) Squ_Acc(4, 9) Squ_Acc(5, 8) Squ_Acc(6, 7) Squ_NonDiag \
952
Squ_SaveAcc(13, 0, 14) Squ_Acc(1, 13) Squ_Acc(2, 12) Squ_Acc(3, 11) Squ_Acc(4, 10) Squ_Acc(5, 9) Squ_Acc(6, 8) Squ_Diag(7) \
953
Squ_SaveAcc(14, 0, 15) Squ_Acc(1, 14) Squ_Acc(2, 13) Squ_Acc(3, 12) Squ_Acc(4, 11) Squ_Acc(5, 10) Squ_Acc(6, 9) Squ_Acc(7, 8) Squ_NonDiag \
954
Squ_SaveAcc(15, 1, 15) Squ_Acc(2, 14) Squ_Acc(3, 13) Squ_Acc(4, 12) Squ_Acc(5, 11) Squ_Acc(6, 10) Squ_Acc(7, 9) Squ_Diag(8) \
955
Squ_SaveAcc(16, 2, 15) Squ_Acc(3, 14) Squ_Acc(4, 13) Squ_Acc(5, 12) Squ_Acc(6, 11) Squ_Acc(7, 10) Squ_Acc(8, 9) Squ_NonDiag \
956
Squ_SaveAcc(17, 3, 15) Squ_Acc(4, 14) Squ_Acc(5, 13) Squ_Acc(6, 12) Squ_Acc(7, 11) Squ_Acc(8, 10) Squ_Diag(9) \
957
Squ_SaveAcc(18, 4, 15) Squ_Acc(5, 14) Squ_Acc(6, 13) Squ_Acc(7, 12) Squ_Acc(8, 11) Squ_Acc(9, 10) Squ_NonDiag \
958
Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \
959
Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \
960
Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \
961
Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \
962
Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \
963
Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \
964
Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \
965
Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \
966
Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \
967
Squ_SaveAcc(28, 14, 15) Squ_NonDiag \
968
Squ_End(16)
969
970
#define Bot_2 \
971
Mul_Begin(2) \
972
Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \
973
Bot_End(2)
974
975
#define Bot_4 \
976
Mul_Begin(4) \
977
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
978
Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \
979
Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \
980
Bot_End(4)
981
982
#define Bot_8 \
983
Mul_Begin(8) \
984
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
985
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
986
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
987
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
988
Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
989
Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
990
Bot_SaveAcc(6, 0, 7) Bot_Acc(1, 6) Bot_Acc(2, 5) Bot_Acc(3, 4) Bot_Acc(4, 3) Bot_Acc(5, 2) Bot_Acc(6, 1) Bot_Acc(7, 0) \
991
Bot_End(8)
992
993
#define Bot_16 \
994
Mul_Begin(16) \
995
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
996
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
997
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
998
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
999
Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
1000
Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
1001
Mul_SaveAcc(6, 0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
1002
Mul_SaveAcc(7, 0, 8) Mul_Acc(1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) Mul_Acc(8, 0) \
1003
Mul_SaveAcc(8, 0, 9) Mul_Acc(1, 8) Mul_Acc(2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) Mul_Acc(8, 1) Mul_Acc(9, 0) \
1004
Mul_SaveAcc(9, 0, 10) Mul_Acc(1, 9) Mul_Acc(2, 8) Mul_Acc(3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) Mul_Acc(8, 2) Mul_Acc(9, 1) Mul_Acc(10, 0) \
1005
Mul_SaveAcc(10, 0, 11) Mul_Acc(1, 10) Mul_Acc(2, 9) Mul_Acc(3, 8) Mul_Acc(4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) Mul_Acc(8, 3) Mul_Acc(9, 2) Mul_Acc(10, 1) Mul_Acc(11, 0) \
1006
Mul_SaveAcc(11, 0, 12) Mul_Acc(1, 11) Mul_Acc(2, 10) Mul_Acc(3, 9) Mul_Acc(4, 8) Mul_Acc(5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) Mul_Acc(8, 4) Mul_Acc(9, 3) Mul_Acc(10, 2) Mul_Acc(11, 1) Mul_Acc(12, 0) \
1007
Mul_SaveAcc(12, 0, 13) Mul_Acc(1, 12) Mul_Acc(2, 11) Mul_Acc(3, 10) Mul_Acc(4, 9) Mul_Acc(5, 8) Mul_Acc(6, 7) Mul_Acc(7, 6) Mul_Acc(8, 5) Mul_Acc(9, 4) Mul_Acc(10, 3) Mul_Acc(11, 2) Mul_Acc(12, 1) Mul_Acc(13, 0) \
1008
Mul_SaveAcc(13, 0, 14) Mul_Acc(1, 13) Mul_Acc(2, 12) Mul_Acc(3, 11) Mul_Acc(4, 10) Mul_Acc(5, 9) Mul_Acc(6, 8) Mul_Acc(7, 7) Mul_Acc(8, 6) Mul_Acc(9, 5) Mul_Acc(10, 4) Mul_Acc(11, 3) Mul_Acc(12, 2) Mul_Acc(13, 1) Mul_Acc(14, 0) \
1009
Bot_SaveAcc(14, 0, 15) Bot_Acc(1, 14) Bot_Acc(2, 13) Bot_Acc(3, 12) Bot_Acc(4, 11) Bot_Acc(5, 10) Bot_Acc(6, 9) Bot_Acc(7, 8) Bot_Acc(8, 7) Bot_Acc(9, 6) Bot_Acc(10, 5) Bot_Acc(11, 4) Bot_Acc(12, 3) Bot_Acc(13, 2) Bot_Acc(14, 1) Bot_Acc(15, 0) \
1010
Bot_End(16)
1011
1012
#endif
1013
1014
#if 0
1015
#define Mul_Begin(n) \
1016
Declare2Words(p) \
1017
Declare2Words(c) \
1018
Declare2Words(d) \
1019
MultiplyWords(p, A[0], B[0]) \
1020
AssignWord(c, LowWord(p)) \
1021
AssignWord(d, HighWord(p))
1022
1023
#define Mul_Acc(i, j) \
1024
MultiplyWords(p, A[i], B[j]) \
1025
Acc2WordsBy1(c, LowWord(p)) \
1026
Acc2WordsBy1(d, HighWord(p))
1027
1028
#define Mul_SaveAcc(k, i, j) \
1029
R[k] = LowWord(c); \
1030
Add2WordsBy1(c, d, HighWord(c)) \
1031
MultiplyWords(p, A[i], B[j]) \
1032
AssignWord(d, HighWord(p)) \
1033
Acc2WordsBy1(c, LowWord(p))
1034
1035
#define Mul_End(n) \
1036
R[2*n-3] = LowWord(c); \
1037
Acc2WordsBy1(d, HighWord(c)) \
1038
MultiplyWords(p, A[n-1], B[n-1])\
1039
Acc2WordsBy2(d, p) \
1040
R[2*n-2] = LowWord(d); \
1041
R[2*n-1] = HighWord(d);
1042
1043
#define Bot_SaveAcc(k, i, j) \
1044
R[k] = LowWord(c); \
1045
word e = LowWord(d) + HighWord(c); \
1046
e += A[i] * B[j];
1047
1048
#define Bot_Acc(i, j) \
1049
e += A[i] * B[j];
1050
1051
#define Bot_End(n) \
1052
R[n-1] = e;
1053
#else
1054
#define Mul_Begin(n) \
1055
Declare2Words(p) \
1056
word c; \
1057
Declare2Words(d) \
1058
MultiplyWords(p, A[0], B[0]) \
1059
c = LowWord(p); \
1060
AssignWord(d, HighWord(p))
1061
1062
#define Mul_Acc(i, j) \
1063
MulAcc(c, d, A[i], B[j])
1064
1065
#define Mul_SaveAcc(k, i, j) \
1066
R[k] = c; \
1067
c = LowWord(d); \
1068
AssignWord(d, HighWord(d)) \
1069
MulAcc(c, d, A[i], B[j])
1070
1071
#define Mul_End(k, i) \
1072
R[k] = c; \
1073
MultiplyWords(p, A[i], B[i]) \
1074
Acc2WordsBy2(p, d) \
1075
R[k+1] = LowWord(p); \
1076
R[k+2] = HighWord(p);
1077
1078
#define Bot_SaveAcc(k, i, j) \
1079
R[k] = c; \
1080
c = LowWord(d); \
1081
c += A[i] * B[j];
1082
1083
#define Bot_Acc(i, j) \
1084
c += A[i] * B[j];
1085
1086
#define Bot_End(n) \
1087
R[n-1] = c;
1088
#endif
1089
1090
#define Squ_Begin(n) \
1091
Declare2Words(p) \
1092
word c; \
1093
Declare2Words(d) \
1094
Declare2Words(e) \
1095
MultiplyWords(p, A[0], A[0]) \
1096
R[0] = LowWord(p); \
1097
AssignWord(e, HighWord(p)) \
1098
MultiplyWords(p, A[0], A[1]) \
1099
c = LowWord(p); \
1100
AssignWord(d, HighWord(p)) \
1101
Squ_NonDiag \
1102
1103
#define Squ_NonDiag \
1104
Double3Words(c, d)
1105
1106
#define Squ_SaveAcc(k, i, j) \
1107
Acc3WordsBy2(c, d, e) \
1108
R[k] = c; \
1109
MultiplyWords(p, A[i], A[j]) \
1110
c = LowWord(p); \
1111
AssignWord(d, HighWord(p)) \
1112
1113
#define Squ_Acc(i, j) \
1114
MulAcc(c, d, A[i], A[j])
1115
1116
#define Squ_Diag(i) \
1117
Squ_NonDiag \
1118
MulAcc(c, d, A[i], A[i])
1119
1120
#define Squ_End(n) \
1121
Acc3WordsBy2(c, d, e) \
1122
R[2*n-3] = c; \
1123
MultiplyWords(p, A[n-1], A[n-1])\
1124
Acc2WordsBy2(p, e) \
1125
R[2*n-2] = LowWord(p); \
1126
R[2*n-1] = HighWord(p);
1127
1128
void Baseline_Multiply2(word *R, const word *A, const word *B)
1129
{
1130
Mul_2
1131
}
1132
1133
void Baseline_Multiply4(word *R, const word *A, const word *B)
1134
{
1135
Mul_4
1136
}
1137
1138
void Baseline_Multiply8(word *R, const word *A, const word *B)
1139
{
1140
Mul_8
1141
}
1142
1143
void Baseline_Square2(word *R, const word *A)
1144
{
1145
Squ_2
1146
}
1147
1148
void Baseline_Square4(word *R, const word *A)
1149
{
1150
Squ_4
1151
}
1152
1153
void Baseline_Square8(word *R, const word *A)
1154
{
1155
Squ_8
1156
}
1157
1158
void Baseline_MultiplyBottom2(word *R, const word *A, const word *B)
1159
{
1160
Bot_2
1161
}
1162
1163
void Baseline_MultiplyBottom4(word *R, const word *A, const word *B)
1164
{
1165
Bot_4
1166
}
1167
1168
void Baseline_MultiplyBottom8(word *R, const word *A, const word *B)
1169
{
1170
Bot_8
1171
}
1172
1173
#define Top_Begin(n) \
1174
Declare2Words(p) \
1175
word c; \
1176
Declare2Words(d) \
1177
MultiplyWords(p, A[0], B[n-2]);\
1178
AssignWord(d, HighWord(p));
1179
1180
#define Top_Acc(i, j) \
1181
MultiplyWords(p, A[i], B[j]);\
1182
Acc2WordsBy1(d, HighWord(p));
1183
1184
#define Top_SaveAcc0(i, j) \
1185
c = LowWord(d); \
1186
AssignWord(d, HighWord(d)) \
1187
MulAcc(c, d, A[i], B[j])
1188
1189
#define Top_SaveAcc1(i, j) \
1190
c = L<c; \
1191
Acc2WordsBy1(d, c); \
1192
c = LowWord(d); \
1193
AssignWord(d, HighWord(d)) \
1194
MulAcc(c, d, A[i], B[j])
1195
1196
void Baseline_MultiplyTop2(word *R, const word *A, const word *B, word L)
1197
{
1198
word T[4];
1199
Baseline_Multiply2(T, A, B);
1200
R[0] = T[2];
1201
R[1] = T[3];
1202
}
1203
1204
void Baseline_MultiplyTop4(word *R, const word *A, const word *B, word L)
1205
{
1206
Top_Begin(4)
1207
Top_Acc(1, 1) Top_Acc(2, 0) \
1208
Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1209
Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1210
Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1211
Mul_End(1, 3)
1212
}
1213
1214
void Baseline_MultiplyTop8(word *R, const word *A, const word *B, word L)
1215
{
1216
Top_Begin(8)
1217
Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1218
Top_SaveAcc0(0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
1219
Top_SaveAcc1(1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) \
1220
Mul_SaveAcc(0, 2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) \
1221
Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1222
Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1223
Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1224
Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1225
Mul_End(5, 7)
1226
}
1227
1228
#if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available
1229
void Baseline_Multiply16(word *R, const word *A, const word *B)
1230
{
1231
Mul_16
1232
}
1233
1234
void Baseline_Square16(word *R, const word *A)
1235
{
1236
Squ_16
1237
}
1238
1239
void Baseline_MultiplyBottom16(word *R, const word *A, const word *B)
1240
{
1241
Bot_16
1242
}
1243
1244
void Baseline_MultiplyTop16(word *R, const word *A, const word *B, word L)
1245
{
1246
Top_Begin(16)
1247
Top_Acc(1, 13) Top_Acc(2, 12) Top_Acc(3, 11) Top_Acc(4, 10) Top_Acc(5, 9) Top_Acc(6, 8) Top_Acc(7, 7) Top_Acc(8, 6) Top_Acc(9, 5) Top_Acc(10, 4) Top_Acc(11, 3) Top_Acc(12, 2) Top_Acc(13, 1) Top_Acc(14, 0) \
1248
Top_SaveAcc0(0, 15) Mul_Acc(1, 14) Mul_Acc(2, 13) Mul_Acc(3, 12) Mul_Acc(4, 11) Mul_Acc(5, 10) Mul_Acc(6, 9) Mul_Acc(7, 8) Mul_Acc(8, 7) Mul_Acc(9, 6) Mul_Acc(10, 5) Mul_Acc(11, 4) Mul_Acc(12, 3) Mul_Acc(13, 2) Mul_Acc(14, 1) Mul_Acc(15, 0) \
1249
Top_SaveAcc1(1, 15) Mul_Acc(2, 14) Mul_Acc(3, 13) Mul_Acc(4, 12) Mul_Acc(5, 11) Mul_Acc(6, 10) Mul_Acc(7, 9) Mul_Acc(8, 8) Mul_Acc(9, 7) Mul_Acc(10, 6) Mul_Acc(11, 5) Mul_Acc(12, 4) Mul_Acc(13, 3) Mul_Acc(14, 2) Mul_Acc(15, 1) \
1250
Mul_SaveAcc(0, 2, 15) Mul_Acc(3, 14) Mul_Acc(4, 13) Mul_Acc(5, 12) Mul_Acc(6, 11) Mul_Acc(7, 10) Mul_Acc(8, 9) Mul_Acc(9, 8) Mul_Acc(10, 7) Mul_Acc(11, 6) Mul_Acc(12, 5) Mul_Acc(13, 4) Mul_Acc(14, 3) Mul_Acc(15, 2) \
1251
Mul_SaveAcc(1, 3, 15) Mul_Acc(4, 14) Mul_Acc(5, 13) Mul_Acc(6, 12) Mul_Acc(7, 11) Mul_Acc(8, 10) Mul_Acc(9, 9) Mul_Acc(10, 8) Mul_Acc(11, 7) Mul_Acc(12, 6) Mul_Acc(13, 5) Mul_Acc(14, 4) Mul_Acc(15, 3) \
1252
Mul_SaveAcc(2, 4, 15) Mul_Acc(5, 14) Mul_Acc(6, 13) Mul_Acc(7, 12) Mul_Acc(8, 11) Mul_Acc(9, 10) Mul_Acc(10, 9) Mul_Acc(11, 8) Mul_Acc(12, 7) Mul_Acc(13, 6) Mul_Acc(14, 5) Mul_Acc(15, 4) \
1253
Mul_SaveAcc(3, 5, 15) Mul_Acc(6, 14) Mul_Acc(7, 13) Mul_Acc(8, 12) Mul_Acc(9, 11) Mul_Acc(10, 10) Mul_Acc(11, 9) Mul_Acc(12, 8) Mul_Acc(13, 7) Mul_Acc(14, 6) Mul_Acc(15, 5) \
1254
Mul_SaveAcc(4, 6, 15) Mul_Acc(7, 14) Mul_Acc(8, 13) Mul_Acc(9, 12) Mul_Acc(10, 11) Mul_Acc(11, 10) Mul_Acc(12, 9) Mul_Acc(13, 8) Mul_Acc(14, 7) Mul_Acc(15, 6) \
1255
Mul_SaveAcc(5, 7, 15) Mul_Acc(8, 14) Mul_Acc(9, 13) Mul_Acc(10, 12) Mul_Acc(11, 11) Mul_Acc(12, 10) Mul_Acc(13, 9) Mul_Acc(14, 8) Mul_Acc(15, 7) \
1256
Mul_SaveAcc(6, 8, 15) Mul_Acc(9, 14) Mul_Acc(10, 13) Mul_Acc(11, 12) Mul_Acc(12, 11) Mul_Acc(13, 10) Mul_Acc(14, 9) Mul_Acc(15, 8) \
1257
Mul_SaveAcc(7, 9, 15) Mul_Acc(10, 14) Mul_Acc(11, 13) Mul_Acc(12, 12) Mul_Acc(13, 11) Mul_Acc(14, 10) Mul_Acc(15, 9) \
1258
Mul_SaveAcc(8, 10, 15) Mul_Acc(11, 14) Mul_Acc(12, 13) Mul_Acc(13, 12) Mul_Acc(14, 11) Mul_Acc(15, 10) \
1259
Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1260
Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1261
Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1262
Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1263
Mul_End(13, 15)
1264
}
1265
#endif
1266
1267
// ********************************************************
1268
1269
#if CRYPTOPP_INTEGER_SSE2
1270
1271
CRYPTOPP_ALIGN_DATA(16) static const word32 s_maskLow16[4] CRYPTOPP_SECTION_ALIGN16 = {0xffff,0xffff,0xffff,0xffff};
1272
1273
#undef Mul_Begin
1274
#undef Mul_Acc
1275
#undef Top_Begin
1276
#undef Top_Acc
1277
#undef Squ_Acc
1278
#undef Squ_NonDiag
1279
#undef Squ_Diag
1280
#undef Squ_SaveAcc
1281
#undef Squ_Begin
1282
#undef Mul_SaveAcc
1283
#undef Bot_Acc
1284
#undef Bot_SaveAcc
1285
#undef Bot_End
1286
#undef Squ_End
1287
#undef Mul_End
1288
1289
#define SSE2_FinalSave(k) \
1290
AS2( psllq xmm5, 16) \
1291
AS2( paddq xmm4, xmm5) \
1292
AS2( movq QWORD PTR [ecx+8*(k)], xmm4)
1293
1294
#define SSE2_SaveShift(k) \
1295
AS2( movq xmm0, xmm6) \
1296
AS2( punpckhqdq xmm6, xmm0) \
1297
AS2( movq xmm1, xmm7) \
1298
AS2( punpckhqdq xmm7, xmm1) \
1299
AS2( paddd xmm6, xmm0) \
1300
AS2( pslldq xmm6, 4) \
1301
AS2( paddd xmm7, xmm1) \
1302
AS2( paddd xmm4, xmm6) \
1303
AS2( pslldq xmm7, 4) \
1304
AS2( movq xmm6, xmm4) \
1305
AS2( paddd xmm5, xmm7) \
1306
AS2( movq xmm7, xmm5) \
1307
AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1308
AS2( psrlq xmm6, 16) \
1309
AS2( paddq xmm6, xmm7) \
1310
AS2( punpckhqdq xmm4, xmm0) \
1311
AS2( punpckhqdq xmm5, xmm0) \
1312
AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \
1313
AS2( psrlq xmm6, 3*16) \
1314
AS2( paddd xmm4, xmm6) \
1315
1316
#define Squ_SSE2_SaveShift(k) \
1317
AS2( movq xmm0, xmm6) \
1318
AS2( punpckhqdq xmm6, xmm0) \
1319
AS2( movq xmm1, xmm7) \
1320
AS2( punpckhqdq xmm7, xmm1) \
1321
AS2( paddd xmm6, xmm0) \
1322
AS2( pslldq xmm6, 4) \
1323
AS2( paddd xmm7, xmm1) \
1324
AS2( paddd xmm4, xmm6) \
1325
AS2( pslldq xmm7, 4) \
1326
AS2( movhlps xmm6, xmm4) \
1327
AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1328
AS2( paddd xmm5, xmm7) \
1329
AS2( movhps QWORD PTR [esp+12], xmm5)\
1330
AS2( psrlq xmm4, 16) \
1331
AS2( paddq xmm4, xmm5) \
1332
AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \
1333
AS2( psrlq xmm4, 3*16) \
1334
AS2( paddd xmm4, xmm6) \
1335
AS2( movq QWORD PTR [esp+4], xmm4)\
1336
1337
#define SSE2_FirstMultiply(i) \
1338
AS2( movdqa xmm7, [esi+(i)*16])\
1339
AS2( movdqa xmm5, [edi-(i)*16])\
1340
AS2( pmuludq xmm5, xmm7) \
1341
AS2( movdqa xmm4, [ebx])\
1342
AS2( movdqa xmm6, xmm4) \
1343
AS2( pand xmm4, xmm5) \
1344
AS2( psrld xmm5, 16) \
1345
AS2( pmuludq xmm7, [edx-(i)*16])\
1346
AS2( pand xmm6, xmm7) \
1347
AS2( psrld xmm7, 16)
1348
1349
#define Squ_Begin(n) \
1350
SquPrologue \
1351
AS2( mov esi, esp)\
1352
AS2( and esp, 0xfffffff0)\
1353
AS2( lea edi, [esp-32*n])\
1354
AS2( sub esp, 32*n+16)\
1355
AS1( push esi)\
1356
AS2( mov esi, edi) \
1357
AS2( xor edx, edx) \
1358
ASL(1) \
1359
ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1360
ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1361
AS2( movdqa [edi+2*edx], xmm0) \
1362
AS2( psrlq xmm0, 32) \
1363
AS2( movdqa [edi+2*edx+16], xmm0) \
1364
AS2( movdqa [edi+16*n+2*edx], xmm1) \
1365
AS2( psrlq xmm1, 32) \
1366
AS2( movdqa [edi+16*n+2*edx+16], xmm1) \
1367
AS2( add edx, 16) \
1368
AS2( cmp edx, 8*(n)) \
1369
ASJ( jne, 1, b) \
1370
AS2( lea edx, [edi+16*n])\
1371
SSE2_FirstMultiply(0) \
1372
1373
#define Squ_Acc(i) \
1374
ASL(LSqu##i) \
1375
AS2( movdqa xmm1, [esi+(i)*16]) \
1376
AS2( movdqa xmm0, [edi-(i)*16]) \
1377
AS2( movdqa xmm2, [ebx]) \
1378
AS2( pmuludq xmm0, xmm1) \
1379
AS2( pmuludq xmm1, [edx-(i)*16]) \
1380
AS2( movdqa xmm3, xmm2) \
1381
AS2( pand xmm2, xmm0) \
1382
AS2( psrld xmm0, 16) \
1383
AS2( paddd xmm4, xmm2) \
1384
AS2( paddd xmm5, xmm0) \
1385
AS2( pand xmm3, xmm1) \
1386
AS2( psrld xmm1, 16) \
1387
AS2( paddd xmm6, xmm3) \
1388
AS2( paddd xmm7, xmm1) \
1389
1390
#define Squ_Acc1(i)
1391
#define Squ_Acc2(i) ASC(call, LSqu##i)
1392
#define Squ_Acc3(i) Squ_Acc2(i)
1393
#define Squ_Acc4(i) Squ_Acc2(i)
1394
#define Squ_Acc5(i) Squ_Acc2(i)
1395
#define Squ_Acc6(i) Squ_Acc2(i)
1396
#define Squ_Acc7(i) Squ_Acc2(i)
1397
#define Squ_Acc8(i) Squ_Acc2(i)
1398
1399
#define SSE2_End(E, n) \
1400
SSE2_SaveShift(2*(n)-3) \
1401
AS2( movdqa xmm7, [esi+16]) \
1402
AS2( movdqa xmm0, [edi]) \
1403
AS2( pmuludq xmm0, xmm7) \
1404
AS2( movdqa xmm2, [ebx]) \
1405
AS2( pmuludq xmm7, [edx]) \
1406
AS2( movdqa xmm6, xmm2) \
1407
AS2( pand xmm2, xmm0) \
1408
AS2( psrld xmm0, 16) \
1409
AS2( paddd xmm4, xmm2) \
1410
AS2( paddd xmm5, xmm0) \
1411
AS2( pand xmm6, xmm7) \
1412
AS2( psrld xmm7, 16) \
1413
SSE2_SaveShift(2*(n)-2) \
1414
SSE2_FinalSave(2*(n)-1) \
1415
AS1( pop esp)\
1416
E
1417
1418
#define Squ_End(n) SSE2_End(SquEpilogue, n)
1419
#define Mul_End(n) SSE2_End(MulEpilogue, n)
1420
#define Top_End(n) SSE2_End(TopEpilogue, n)
1421
1422
#define Squ_Column1(k, i) \
1423
Squ_SSE2_SaveShift(k) \
1424
AS2( add esi, 16) \
1425
SSE2_FirstMultiply(1)\
1426
Squ_Acc##i(i) \
1427
AS2( paddd xmm4, xmm4) \
1428
AS2( paddd xmm5, xmm5) \
1429
AS2( movdqa xmm3, [esi]) \
1430
AS2( movq xmm1, QWORD PTR [esi+8]) \
1431
AS2( pmuludq xmm1, xmm3) \
1432
AS2( pmuludq xmm3, xmm3) \
1433
AS2( movdqa xmm0, [ebx])\
1434
AS2( movdqa xmm2, xmm0) \
1435
AS2( pand xmm0, xmm1) \
1436
AS2( psrld xmm1, 16) \
1437
AS2( paddd xmm6, xmm0) \
1438
AS2( paddd xmm7, xmm1) \
1439
AS2( pand xmm2, xmm3) \
1440
AS2( psrld xmm3, 16) \
1441
AS2( paddd xmm6, xmm6) \
1442
AS2( paddd xmm7, xmm7) \
1443
AS2( paddd xmm4, xmm2) \
1444
AS2( paddd xmm5, xmm3) \
1445
AS2( movq xmm0, QWORD PTR [esp+4])\
1446
AS2( movq xmm1, QWORD PTR [esp+12])\
1447
AS2( paddd xmm4, xmm0)\
1448
AS2( paddd xmm5, xmm1)\
1449
1450
#define Squ_Column0(k, i) \
1451
Squ_SSE2_SaveShift(k) \
1452
AS2( add edi, 16) \
1453
AS2( add edx, 16) \
1454
SSE2_FirstMultiply(1)\
1455
Squ_Acc##i(i) \
1456
AS2( paddd xmm6, xmm6) \
1457
AS2( paddd xmm7, xmm7) \
1458
AS2( paddd xmm4, xmm4) \
1459
AS2( paddd xmm5, xmm5) \
1460
AS2( movq xmm0, QWORD PTR [esp+4])\
1461
AS2( movq xmm1, QWORD PTR [esp+12])\
1462
AS2( paddd xmm4, xmm0)\
1463
AS2( paddd xmm5, xmm1)\
1464
1465
#define SSE2_MulAdd45 \
1466
AS2( movdqa xmm7, [esi]) \
1467
AS2( movdqa xmm0, [edi]) \
1468
AS2( pmuludq xmm0, xmm7) \
1469
AS2( movdqa xmm2, [ebx]) \
1470
AS2( pmuludq xmm7, [edx]) \
1471
AS2( movdqa xmm6, xmm2) \
1472
AS2( pand xmm2, xmm0) \
1473
AS2( psrld xmm0, 16) \
1474
AS2( paddd xmm4, xmm2) \
1475
AS2( paddd xmm5, xmm0) \
1476
AS2( pand xmm6, xmm7) \
1477
AS2( psrld xmm7, 16)
1478
1479
#define Mul_Begin(n) \
1480
MulPrologue \
1481
AS2( mov esi, esp)\
1482
AS2( and esp, 0xfffffff0)\
1483
AS2( sub esp, 48*n+16)\
1484
AS1( push esi)\
1485
AS2( xor edx, edx) \
1486
ASL(1) \
1487
ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1488
ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1489
ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1490
AS2( movdqa [esp+20+2*edx], xmm0) \
1491
AS2( psrlq xmm0, 32) \
1492
AS2( movdqa [esp+20+2*edx+16], xmm0) \
1493
AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1494
AS2( psrlq xmm1, 32) \
1495
AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1496
AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1497
AS2( psrlq xmm2, 32) \
1498
AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1499
AS2( add edx, 16) \
1500
AS2( cmp edx, 8*(n)) \
1501
ASJ( jne, 1, b) \
1502
AS2( lea edi, [esp+20])\
1503
AS2( lea edx, [esp+20+16*n])\
1504
AS2( lea esi, [esp+20+32*n])\
1505
SSE2_FirstMultiply(0) \
1506
1507
#define Mul_Acc(i) \
1508
ASL(LMul##i) \
1509
AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1510
AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1511
AS2( movdqa xmm2, [ebx]) \
1512
AS2( pmuludq xmm0, xmm1) \
1513
AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1514
AS2( movdqa xmm3, xmm2) \
1515
AS2( pand xmm2, xmm0) \
1516
AS2( psrld xmm0, 16) \
1517
AS2( paddd xmm4, xmm2) \
1518
AS2( paddd xmm5, xmm0) \
1519
AS2( pand xmm3, xmm1) \
1520
AS2( psrld xmm1, 16) \
1521
AS2( paddd xmm6, xmm3) \
1522
AS2( paddd xmm7, xmm1) \
1523
1524
#define Mul_Acc1(i)
1525
#define Mul_Acc2(i) ASC(call, LMul##i)
1526
#define Mul_Acc3(i) Mul_Acc2(i)
1527
#define Mul_Acc4(i) Mul_Acc2(i)
1528
#define Mul_Acc5(i) Mul_Acc2(i)
1529
#define Mul_Acc6(i) Mul_Acc2(i)
1530
#define Mul_Acc7(i) Mul_Acc2(i)
1531
#define Mul_Acc8(i) Mul_Acc2(i)
1532
#define Mul_Acc9(i) Mul_Acc2(i)
1533
#define Mul_Acc10(i) Mul_Acc2(i)
1534
#define Mul_Acc11(i) Mul_Acc2(i)
1535
#define Mul_Acc12(i) Mul_Acc2(i)
1536
#define Mul_Acc13(i) Mul_Acc2(i)
1537
#define Mul_Acc14(i) Mul_Acc2(i)
1538
#define Mul_Acc15(i) Mul_Acc2(i)
1539
#define Mul_Acc16(i) Mul_Acc2(i)
1540
1541
#define Mul_Column1(k, i) \
1542
SSE2_SaveShift(k) \
1543
AS2( add esi, 16) \
1544
SSE2_MulAdd45\
1545
Mul_Acc##i(i) \
1546
1547
#define Mul_Column0(k, i) \
1548
SSE2_SaveShift(k) \
1549
AS2( add edi, 16) \
1550
AS2( add edx, 16) \
1551
SSE2_MulAdd45\
1552
Mul_Acc##i(i) \
1553
1554
#define Bot_Acc(i) \
1555
AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1556
AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1557
AS2( pmuludq xmm0, xmm1) \
1558
AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1559
AS2( paddq xmm4, xmm0) \
1560
AS2( paddd xmm6, xmm1)
1561
1562
#define Bot_SaveAcc(k) \
1563
SSE2_SaveShift(k) \
1564
AS2( add edi, 16) \
1565
AS2( add edx, 16) \
1566
AS2( movdqa xmm6, [esi]) \
1567
AS2( movdqa xmm0, [edi]) \
1568
AS2( pmuludq xmm0, xmm6) \
1569
AS2( paddq xmm4, xmm0) \
1570
AS2( psllq xmm5, 16) \
1571
AS2( paddq xmm4, xmm5) \
1572
AS2( pmuludq xmm6, [edx])
1573
1574
#define Bot_End(n) \
1575
AS2( movhlps xmm7, xmm6) \
1576
AS2( paddd xmm6, xmm7) \
1577
AS2( psllq xmm6, 32) \
1578
AS2( paddd xmm4, xmm6) \
1579
AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \
1580
AS1( pop esp)\
1581
MulEpilogue
1582
1583
#define Top_Begin(n) \
1584
TopPrologue \
1585
AS2( mov edx, esp)\
1586
AS2( and esp, 0xfffffff0)\
1587
AS2( sub esp, 48*n+16)\
1588
AS1( push edx)\
1589
AS2( xor edx, edx) \
1590
ASL(1) \
1591
ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1592
ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1593
ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1594
AS2( movdqa [esp+20+2*edx], xmm0) \
1595
AS2( psrlq xmm0, 32) \
1596
AS2( movdqa [esp+20+2*edx+16], xmm0) \
1597
AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1598
AS2( psrlq xmm1, 32) \
1599
AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1600
AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1601
AS2( psrlq xmm2, 32) \
1602
AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1603
AS2( add edx, 16) \
1604
AS2( cmp edx, 8*(n)) \
1605
ASJ( jne, 1, b) \
1606
AS2( mov eax, esi) \
1607
AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\
1608
AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\
1609
AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\
1610
AS2( pxor xmm4, xmm4)\
1611
AS2( pxor xmm5, xmm5)
1612
1613
#define Top_Acc(i) \
1614
AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \
1615
AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1616
AS2( psrlq xmm0, 48) \
1617
AS2( paddd xmm5, xmm0)\
1618
1619
#define Top_Column0(i) \
1620
AS2( psllq xmm5, 32) \
1621
AS2( add edi, 16) \
1622
AS2( add edx, 16) \
1623
SSE2_MulAdd45\
1624
Mul_Acc##i(i) \
1625
1626
#define Top_Column1(i) \
1627
SSE2_SaveShift(0) \
1628
AS2( add esi, 16) \
1629
SSE2_MulAdd45\
1630
Mul_Acc##i(i) \
1631
AS2( shr eax, 16) \
1632
AS2( movd xmm0, eax)\
1633
AS2( movd xmm1, [ecx+4])\
1634
AS2( psrld xmm1, 16)\
1635
AS2( pcmpgtd xmm1, xmm0)\
1636
AS2( psrld xmm1, 31)\
1637
AS2( paddd xmm4, xmm1)\
1638
1639
void SSE2_Square4(word *C, const word *A)
1640
{
1641
Squ_Begin(2)
1642
Squ_Column0(0, 1)
1643
Squ_End(2)
1644
}
1645
1646
void SSE2_Square8(word *C, const word *A)
1647
{
1648
Squ_Begin(4)
1649
#ifndef __GNUC__
1650
ASJ( jmp, 0, f)
1651
Squ_Acc(2)
1652
AS1( ret) ASL(0)
1653
#endif
1654
Squ_Column0(0, 1)
1655
Squ_Column1(1, 1)
1656
Squ_Column0(2, 2)
1657
Squ_Column1(3, 1)
1658
Squ_Column0(4, 1)
1659
Squ_End(4)
1660
}
1661
1662
void SSE2_Square16(word *C, const word *A)
1663
{
1664
Squ_Begin(8)
1665
#ifndef __GNUC__
1666
ASJ( jmp, 0, f)
1667
Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1668
AS1( ret) ASL(0)
1669
#endif
1670
Squ_Column0(0, 1)
1671
Squ_Column1(1, 1)
1672
Squ_Column0(2, 2)
1673
Squ_Column1(3, 2)
1674
Squ_Column0(4, 3)
1675
Squ_Column1(5, 3)
1676
Squ_Column0(6, 4)
1677
Squ_Column1(7, 3)
1678
Squ_Column0(8, 3)
1679
Squ_Column1(9, 2)
1680
Squ_Column0(10, 2)
1681
Squ_Column1(11, 1)
1682
Squ_Column0(12, 1)
1683
Squ_End(8)
1684
}
1685
1686
void SSE2_Square32(word *C, const word *A)
1687
{
1688
Squ_Begin(16)
1689
ASJ( jmp, 0, f)
1690
Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1691
AS1( ret) ASL(0)
1692
Squ_Column0(0, 1)
1693
Squ_Column1(1, 1)
1694
Squ_Column0(2, 2)
1695
Squ_Column1(3, 2)
1696
Squ_Column0(4, 3)
1697
Squ_Column1(5, 3)
1698
Squ_Column0(6, 4)
1699
Squ_Column1(7, 4)
1700
Squ_Column0(8, 5)
1701
Squ_Column1(9, 5)
1702
Squ_Column0(10, 6)
1703
Squ_Column1(11, 6)
1704
Squ_Column0(12, 7)
1705
Squ_Column1(13, 7)
1706
Squ_Column0(14, 8)
1707
Squ_Column1(15, 7)
1708
Squ_Column0(16, 7)
1709
Squ_Column1(17, 6)
1710
Squ_Column0(18, 6)
1711
Squ_Column1(19, 5)
1712
Squ_Column0(20, 5)
1713
Squ_Column1(21, 4)
1714
Squ_Column0(22, 4)
1715
Squ_Column1(23, 3)
1716
Squ_Column0(24, 3)
1717
Squ_Column1(25, 2)
1718
Squ_Column0(26, 2)
1719
Squ_Column1(27, 1)
1720
Squ_Column0(28, 1)
1721
Squ_End(16)
1722
}
1723
1724
void SSE2_Multiply4(word *C, const word *A, const word *B)
1725
{
1726
Mul_Begin(2)
1727
#ifndef __GNUC__
1728
ASJ( jmp, 0, f)
1729
Mul_Acc(2)
1730
AS1( ret) ASL(0)
1731
#endif
1732
Mul_Column0(0, 2)
1733
Mul_End(2)
1734
}
1735
1736
void SSE2_Multiply8(word *C, const word *A, const word *B)
1737
{
1738
Mul_Begin(4)
1739
#ifndef __GNUC__
1740
ASJ( jmp, 0, f)
1741
Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1742
AS1( ret) ASL(0)
1743
#endif
1744
Mul_Column0(0, 2)
1745
Mul_Column1(1, 3)
1746
Mul_Column0(2, 4)
1747
Mul_Column1(3, 3)
1748
Mul_Column0(4, 2)
1749
Mul_End(4)
1750
}
1751
1752
void SSE2_Multiply16(word *C, const word *A, const word *B)
1753
{
1754
Mul_Begin(8)
1755
#ifndef __GNUC__
1756
ASJ( jmp, 0, f)
1757
Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1758
AS1( ret) ASL(0)
1759
#endif
1760
Mul_Column0(0, 2)
1761
Mul_Column1(1, 3)
1762
Mul_Column0(2, 4)
1763
Mul_Column1(3, 5)
1764
Mul_Column0(4, 6)
1765
Mul_Column1(5, 7)
1766
Mul_Column0(6, 8)
1767
Mul_Column1(7, 7)
1768
Mul_Column0(8, 6)
1769
Mul_Column1(9, 5)
1770
Mul_Column0(10, 4)
1771
Mul_Column1(11, 3)
1772
Mul_Column0(12, 2)
1773
Mul_End(8)
1774
}
1775
1776
void SSE2_Multiply32(word *C, const word *A, const word *B)
1777
{
1778
Mul_Begin(16)
1779
ASJ( jmp, 0, f)
1780
Mul_Acc(16) Mul_Acc(15) Mul_Acc(14) Mul_Acc(13) Mul_Acc(12) Mul_Acc(11) Mul_Acc(10) Mul_Acc(9) Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1781
AS1( ret) ASL(0)
1782
Mul_Column0(0, 2)
1783
Mul_Column1(1, 3)
1784
Mul_Column0(2, 4)
1785
Mul_Column1(3, 5)
1786
Mul_Column0(4, 6)
1787
Mul_Column1(5, 7)
1788
Mul_Column0(6, 8)
1789
Mul_Column1(7, 9)
1790
Mul_Column0(8, 10)
1791
Mul_Column1(9, 11)
1792
Mul_Column0(10, 12)
1793
Mul_Column1(11, 13)
1794
Mul_Column0(12, 14)
1795
Mul_Column1(13, 15)
1796
Mul_Column0(14, 16)
1797
Mul_Column1(15, 15)
1798
Mul_Column0(16, 14)
1799
Mul_Column1(17, 13)
1800
Mul_Column0(18, 12)
1801
Mul_Column1(19, 11)
1802
Mul_Column0(20, 10)
1803
Mul_Column1(21, 9)
1804
Mul_Column0(22, 8)
1805
Mul_Column1(23, 7)
1806
Mul_Column0(24, 6)
1807
Mul_Column1(25, 5)
1808
Mul_Column0(26, 4)
1809
Mul_Column1(27, 3)
1810
Mul_Column0(28, 2)
1811
Mul_End(16)
1812
}
1813
1814
void SSE2_MultiplyBottom4(word *C, const word *A, const word *B)
1815
{
1816
Mul_Begin(2)
1817
Bot_SaveAcc(0) Bot_Acc(2)
1818
Bot_End(2)
1819
}
1820
1821
void SSE2_MultiplyBottom8(word *C, const word *A, const word *B)
1822
{
1823
Mul_Begin(4)
1824
#ifndef __GNUC__
1825
ASJ( jmp, 0, f)
1826
Mul_Acc(3) Mul_Acc(2)
1827
AS1( ret) ASL(0)
1828
#endif
1829
Mul_Column0(0, 2)
1830
Mul_Column1(1, 3)
1831
Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1832
Bot_End(4)
1833
}
1834
1835
void SSE2_MultiplyBottom16(word *C, const word *A, const word *B)
1836
{
1837
Mul_Begin(8)
1838
#ifndef __GNUC__
1839
ASJ( jmp, 0, f)
1840
Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1841
AS1( ret) ASL(0)
1842
#endif
1843
Mul_Column0(0, 2)
1844
Mul_Column1(1, 3)
1845
Mul_Column0(2, 4)
1846
Mul_Column1(3, 5)
1847
Mul_Column0(4, 6)
1848
Mul_Column1(5, 7)
1849
Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1850
Bot_End(8)
1851
}
1852
1853
void SSE2_MultiplyBottom32(word *C, const word *A, const word *B)
1854
{
1855
Mul_Begin(16)
1856
#ifndef __GNUC__
1857
ASJ( jmp, 0, f)
1858
Mul_Acc(15) Mul_Acc(14) Mul_Acc(13) Mul_Acc(12) Mul_Acc(11) Mul_Acc(10) Mul_Acc(9) Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1859
AS1( ret) ASL(0)
1860
#endif
1861
Mul_Column0(0, 2)
1862
Mul_Column1(1, 3)
1863
Mul_Column0(2, 4)
1864
Mul_Column1(3, 5)
1865
Mul_Column0(4, 6)
1866
Mul_Column1(5, 7)
1867
Mul_Column0(6, 8)
1868
Mul_Column1(7, 9)
1869
Mul_Column0(8, 10)
1870
Mul_Column1(9, 11)
1871
Mul_Column0(10, 12)
1872
Mul_Column1(11, 13)
1873
Mul_Column0(12, 14)
1874
Mul_Column1(13, 15)
1875
Bot_SaveAcc(14) Bot_Acc(16) Bot_Acc(15) Bot_Acc(14) Bot_Acc(13) Bot_Acc(12) Bot_Acc(11) Bot_Acc(10) Bot_Acc(9) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1876
Bot_End(16)
1877
}
1878
1879
void SSE2_MultiplyTop8(word *C, const word *A, const word *B, word L)
1880
{
1881
Top_Begin(4)
1882
Top_Acc(3) Top_Acc(2) Top_Acc(1)
1883
#ifndef __GNUC__
1884
ASJ( jmp, 0, f)
1885
Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1886
AS1( ret) ASL(0)
1887
#endif
1888
Top_Column0(4)
1889
Top_Column1(3)
1890
Mul_Column0(0, 2)
1891
Top_End(2)
1892
}
1893
1894
void SSE2_MultiplyTop16(word *C, const word *A, const word *B, word L)
1895
{
1896
Top_Begin(8)
1897
Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1898
#ifndef __GNUC__
1899
ASJ( jmp, 0, f)
1900
Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1901
AS1( ret) ASL(0)
1902
#endif
1903
Top_Column0(8)
1904
Top_Column1(7)
1905
Mul_Column0(0, 6)
1906
Mul_Column1(1, 5)
1907
Mul_Column0(2, 4)
1908
Mul_Column1(3, 3)
1909
Mul_Column0(4, 2)
1910
Top_End(4)
1911
}
1912
1913
void SSE2_MultiplyTop32(word *C, const word *A, const word *B, word L)
1914
{
1915
Top_Begin(16)
1916
Top_Acc(15) Top_Acc(14) Top_Acc(13) Top_Acc(12) Top_Acc(11) Top_Acc(10) Top_Acc(9) Top_Acc(8) Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1917
#ifndef __GNUC__
1918
ASJ( jmp, 0, f)
1919
Mul_Acc(16) Mul_Acc(15) Mul_Acc(14) Mul_Acc(13) Mul_Acc(12) Mul_Acc(11) Mul_Acc(10) Mul_Acc(9) Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1920
AS1( ret) ASL(0)
1921
#endif
1922
Top_Column0(16)
1923
Top_Column1(15)
1924
Mul_Column0(0, 14)
1925
Mul_Column1(1, 13)
1926
Mul_Column0(2, 12)
1927
Mul_Column1(3, 11)
1928
Mul_Column0(4, 10)
1929
Mul_Column1(5, 9)
1930
Mul_Column0(6, 8)
1931
Mul_Column1(7, 7)
1932
Mul_Column0(8, 6)
1933
Mul_Column1(9, 5)
1934
Mul_Column0(10, 4)
1935
Mul_Column1(11, 3)
1936
Mul_Column0(12, 2)
1937
Top_End(8)
1938
}
1939
1940
#endif // #if CRYPTOPP_INTEGER_SSE2
1941
1942
// ********************************************************
1943
1944
typedef int (CRYPTOPP_FASTCALL * PAdd)(size_t N, word *C, const word *A, const word *B);
1012
1945
typedef void (* PMul)(word *C, const word *A, const word *B);
1946
typedef void (* PSqu)(word *C, const word *A);
1947
typedef void (* PMulTop)(word *C, const word *A, const word *B, word L);
1013
1948
1014
static PAddSub s_pAdd, s_pSub;
1015
#ifdef SSE2_INTRINSICS_AVAILABLE
1016
static PMul s_pMul4, s_pMul8, s_pMul8B;
1949
#if CRYPTOPP_INTEGER_SSE2
1950
static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
1951
static size_t s_recursionLimit = 8;
1952
#else
1953
static const size_t s_recursionLimit = 16;
1017
1954
#endif
1018
1955
1019
static void SetPentiumFunctionPointers()
1956
static PMul s_pMul[9], s_pBot[9];
1957
static PSqu s_pSqu[9];
1958
static PMulTop s_pTop[9];
1959
1960
static void SetFunctionPointers()
1020
1961
{
1021
if (IsP4())
1022
{
1023
s_pAdd = &P4Optimized::Add;
1024
s_pSub = &P4Optimized::Subtract;
1025
}
1026
else
1027
{
1028
s_pAdd = &PentiumOptimized::Add;
1029
s_pSub = &PentiumOptimized::Subtract;
1030
}
1962
s_pMul[0] = &Baseline_Multiply2;
1963
s_pBot[0] = &Baseline_MultiplyBottom2;
1964
s_pSqu[0] = &Baseline_Square2;
1965
s_pTop[0] = &Baseline_MultiplyTop2;
1966
s_pTop[1] = &Baseline_MultiplyTop4;
1031
1967
1032
#ifdef SSE2_INTRINSICS_AVAILABLE
1968
#if CRYPTOPP_INTEGER_SSE2
1033
1969
if (HasSSE2())
1034
1970
{
1035
s_pMul4 = &P4Optimized::Multiply4;
1036
s_pMul8 = &P4Optimized::Multiply8;
1037
s_pMul8B = &P4Optimized::Multiply8Bottom;
1971
#if _MSC_VER != 1200 || defined(NDEBUG)
1972
if (IsP4())
1973
{
1974
s_pAdd = &SSE2_Add;
1975
s_pSub = &SSE2_Sub;
1976
}
1977
#endif
1978
1979
s_recursionLimit = 32;
1980
1981
s_pMul[1] = &SSE2_Multiply4;
1982
s_pMul[2] = &SSE2_Multiply8;
1983
s_pMul[4] = &SSE2_Multiply16;
1984
s_pMul[8] = &SSE2_Multiply32;
1985
1986
s_pBot[1] = &SSE2_MultiplyBottom4;
1987
s_pBot[2] = &SSE2_MultiplyBottom8;
1988
s_pBot[4] = &SSE2_MultiplyBottom16;
1989
s_pBot[8] = &SSE2_MultiplyBottom32;
1990
1991
s_pSqu[1] = &SSE2_Square4;
1992
s_pSqu[2] = &SSE2_Square8;
1993
s_pSqu[4] = &SSE2_Square16;
1994
s_pSqu[8] = &SSE2_Square32;
1995
1996
s_pTop[2] = &SSE2_MultiplyTop8;
1997
s_pTop[4] = &SSE2_MultiplyTop16;
1998
s_pTop[8] = &SSE2_MultiplyTop32;
1038
1999
}
1039
2000
else
2001
#endif
1040
2002
{
1041
s_pMul4 = &PentiumOptimized::Multiply4;
1042
s_pMul8 = &PentiumOptimized::Multiply8;
1043
s_pMul8B = &PentiumOptimized::Multiply8Bottom;
2003
s_pMul[1] = &Baseline_Multiply4;
2004
s_pMul[2] = &Baseline_Multiply8;
2005
2006
s_pBot[1] = &Baseline_MultiplyBottom4;
2007
s_pBot[2] = &Baseline_MultiplyBottom8;
2008
2009
s_pSqu[1] = &Baseline_Square4;
2010
s_pSqu[2] = &Baseline_Square8;
2011
2012
s_pTop[2] = &Baseline_MultiplyTop8;
2013
2014
#if !CRYPTOPP_INTEGER_SSE2
2015
s_pMul[4] = &Baseline_Multiply16;
2016
s_pBot[4] = &Baseline_MultiplyBottom16;
2017
s_pSqu[4] = &Baseline_Square16;
2018
s_pTop[4] = &Baseline_MultiplyTop16;
2019
#endif
1044
2020
}
1045
#endif
1046
}
1047
1048
void DisableSSE2()
1049
{
1050
s_sse2Enabled = false;
1051
SetPentiumFunctionPointers();
1052
}
1053
1054
class LowLevel : public PentiumOptimized
1055
{
1056
public:
1057
inline static int Add(word *C, const word *A, const word *B, size_t N)
1058
{return s_pAdd(C, A, B, N);}
1059
inline static int Subtract(word *C, const word *A, const word *B, size_t N)
1060
{return s_pSub(C, A, B, N);}
1061
inline static void Square4(word *R, const word *A)
1062
{Multiply4(R, A, A);}
1063
#ifdef SSE2_INTRINSICS_AVAILABLE
1064
inline static void Multiply4(word *C, const word *A, const word *B)
1065
{s_pMul4(C, A, B);}
1066
inline static void Multiply8(word *C, const word *A, const word *B)
1067
{s_pMul8(C, A, B);}
1068
inline static void Multiply8Bottom(word *C, const word *A, const word *B)
1069
{s_pMul8B(C, A, B);}
1070
#endif
1071
};
1072
1073
// use some tricks to share assembly code between MSVC and GCC
1074
#ifdef _MSC_VER
1075
#define CRYPTOPP_NAKED __declspec(naked)
1076
#define AS1(x) __asm x
1077
#define AS2(x, y) __asm x, y
1078
#define AddPrologue \
1079
__asm push ebp \
1080
__asm push ebx \
1081
__asm push esi \
1082
__asm push edi \
1083
__asm mov ecx, [esp+20] \
1084
__asm mov edx, [esp+24] \
1085
__asm mov ebx, [esp+28] \
1086
__asm mov esi, [esp+32]
1087
#define AddEpilogue \
1088
__asm pop edi \
1089
__asm pop esi \
1090
__asm pop ebx \
1091
__asm pop ebp \
1092
__asm ret
1093
#define MulPrologue \
1094
__asm push ebp \
1095
__asm push ebx \
1096
__asm push esi \
1097
__asm push edi \
1098
__asm mov ecx, [esp+28] \
1099
__asm mov esi, [esp+24] \
1100
__asm push [esp+20]
1101
#define MulEpilogue \
1102
__asm add esp, 4 \
1103
__asm pop edi \
1104
__asm pop esi \
1105
__asm pop ebx \
1106
__asm pop ebp \
1107
__asm ret
1108
#else
1109
#define CRYPTOPP_NAKED
1110
#define AS1(x) #x ";"
1111
#define AS2(x, y) #x ", " #y ";"
1112
#define AddPrologue \
1113
__asm__ __volatile__ \
1114
( \
1115
"push %%ebx;" /* save this manually, in case of -fPIC */ \
1116
"mov %2, %%ebx;" \
1117
".intel_syntax noprefix;" \
1118
"push ebp;"
1119
#define AddEpilogue \
1120
"pop ebp;" \
1121
".att_syntax prefix;" \
1122
"pop %%ebx;" \
1123
: \
1124
: "c" (C), "d" (A), "m" (B), "S" (N) \
1125
: "%edi", "memory", "cc" \
1126
);
1127
#define MulPrologue \
1128
__asm__ __volatile__ \
1129
( \
1130
"push %%ebx;" /* save this manually, in case of -fPIC */ \
1131
"push %%ebp;" \
1132
"push %0;" \
1133
".intel_syntax noprefix;"
1134
#define MulEpilogue \
1135
"add esp, 4;" \
1136
"pop ebp;" \
1137
"pop ebx;" \
1138
".att_syntax prefix;" \
1139
: \
1140
: "rm" (Z), "S" (X), "c" (Y) \
1141
: "%eax", "%edx", "%edi", "memory", "cc" \
1142
);
1143
#endif
1144
1145
CRYPTOPP_NAKED int PentiumOptimized::Add(word *C, const word *A, const word *B, size_t N)
1146
{
1147
AddPrologue
1148
1149
// now: ebx = B, ecx = C, edx = A, esi = N
1150
AS2( sub ecx, edx) // hold the distance between C & A so we can add this to A to get C
1151
AS2( xor eax, eax) // clear eax
1152
1153
AS2( sub eax, esi) // eax is a negative index from end of B
1154
AS2( lea ebx, [ebx+4*esi]) // ebx is end of B
1155
1156
AS2( sar eax, 1) // unit of eax is now dwords; this also clears the carry flag
1157
AS1( jz loopendAdd) // if no dwords then nothing to do
1158
1159
AS1(loopstartAdd:)
1160
AS2( mov esi,[edx]) // load lower word of A
1161
AS2( mov ebp,[edx+4]) // load higher word of A
1162
1163
AS2( mov edi,[ebx+8*eax]) // load lower word of B
1164
AS2( lea edx,[edx+8]) // advance A and C
1165
1166
AS2( adc esi,edi) // add lower words
1167
AS2( mov edi,[ebx+8*eax+4]) // load higher word of B
1168
1169
AS2( adc ebp,edi) // add higher words
1170
AS1( inc eax) // advance B
1171
1172
AS2( mov [edx+ecx-8],esi) // store lower word result
1173
AS2( mov [edx+ecx-4],ebp) // store higher word result
1174
1175
AS1( jnz loopstartAdd) // loop until eax overflows and becomes zero
1176
1177
AS1(loopendAdd:)
1178
AS2( adc eax, 0) // store carry into eax (return result register)
1179
1180
AddEpilogue
1181
}
1182
1183
CRYPTOPP_NAKED int PentiumOptimized::Subtract(word *C, const word *A, const word *B, size_t N)
1184
{
1185
AddPrologue
1186
1187
// now: ebx = B, ecx = C, edx = A, esi = N
1188
AS2( sub ecx, edx) // hold the distance between C & A so we can add this to A to get C
1189
AS2( xor eax, eax) // clear eax
1190
1191
AS2( sub eax, esi) // eax is a negative index from end of B
1192
AS2( lea ebx, [ebx+4*esi]) // ebx is end of B
1193
1194
AS2( sar eax, 1) // unit of eax is now dwords; this also clears the carry flag
1195
AS1( jz loopendSub) // if no dwords then nothing to do
1196
1197
AS1(loopstartSub:)
1198
AS2( mov esi,[edx]) // load lower word of A
1199
AS2( mov ebp,[edx+4]) // load higher word of A
1200
1201
AS2( mov edi,[ebx+8*eax]) // load lower word of B
1202
AS2( lea edx,[edx+8]) // advance A and C
1203
1204
AS2( sbb esi,edi) // subtract lower words
1205
AS2( mov edi,[ebx+8*eax+4]) // load higher word of B
1206
1207
AS2( sbb ebp,edi) // subtract higher words
1208
AS1( inc eax) // advance B
1209
1210
AS2( mov [edx+ecx-8],esi) // store lower word result
1211
AS2( mov [edx+ecx-4],ebp) // store higher word result
1212
1213
AS1( jnz loopstartSub) // loop until eax overflows and becomes zero
1214
1215
AS1(loopendSub:)
1216
AS2( adc eax, 0) // store carry into eax (return result register)
1217
1218
AddEpilogue
1219
}
1220
1221
// On Pentium 4, the adc and sbb instructions are very expensive, so avoid them.
1222
1223
CRYPTOPP_NAKED int P4Optimized::Add(word *C, const word *A, const word *B, size_t N)
1224
{
1225
AddPrologue
1226
1227
// now: ebx = B, ecx = C, edx = A, esi = N
1228
AS2( xor eax, eax)
1229
AS1( neg esi)
1230
AS1( jz loopendAddP4) // if no dwords then nothing to do
1231
1232
AS2( mov edi, [edx])
1233
AS2( mov ebp, [ebx])
1234
AS1( jmp carry1AddP4)
1235
1236
AS1(loopstartAddP4:)
1237
AS2( mov edi, [edx+8])
1238
AS2( add ecx, 8)
1239
AS2( add edx, 8)
1240
AS2( mov ebp, [ebx])
1241
AS2( add edi, eax)
1242
AS1( jc carry1AddP4)
1243
AS2( xor eax, eax)
1244
1245
AS1(carry1AddP4:)
1246
AS2( add edi, ebp)
1247
AS2( mov ebp, 1)
1248
AS2( mov [ecx], edi)
1249
AS2( mov edi, [edx+4])
1250
AS2( cmovc eax, ebp)
1251
AS2( mov ebp, [ebx+4])
1252
AS2( add ebx, 8)
1253
AS2( add edi, eax)
1254
AS1( jc carry2AddP4)
1255
AS2( xor eax, eax)
1256
1257
AS1(carry2AddP4:)
1258
AS2( add edi, ebp)
1259
AS2( mov ebp, 1)
1260
AS2( cmovc eax, ebp)
1261
AS2( mov [ecx+4], edi)
1262
AS2( add esi, 2)
1263
AS1( jnz loopstartAddP4)
1264
1265
AS1(loopendAddP4:)
1266
1267
AddEpilogue
1268
}
1269
1270
CRYPTOPP_NAKED int P4Optimized::Subtract(word *C, const word *A, const word *B, size_t N)
1271
{
1272
AddPrologue
1273
1274
// now: ebx = B, ecx = C, edx = A, esi = N
1275
AS2( xor eax, eax)
1276
AS1( neg esi)
1277
AS1( jz loopendSubP4) // if no dwords then nothing to do
1278
1279
AS2( mov edi, [edx])
1280
AS2( mov ebp, [ebx])
1281
AS1( jmp carry1SubP4)
1282
1283
AS1(loopstartSubP4:)
1284
AS2( mov edi, [edx+8])
1285
AS2( add edx, 8)
1286
AS2( add ecx, 8)
1287
AS2( mov ebp, [ebx])
1288
AS2( sub edi, eax)
1289
AS1( jc carry1SubP4)
1290
AS2( xor eax, eax)
1291
1292
AS1(carry1SubP4:)
1293
AS2( sub edi, ebp)
1294
AS2( mov ebp, 1)
1295
AS2( mov [ecx], edi)
1296
AS2( mov edi, [edx+4])
1297
AS2( cmovc eax, ebp)
1298
AS2( mov ebp, [ebx+4])
1299
AS2( add ebx, 8)
1300
AS2( sub edi, eax)
1301
AS1( jc carry2SubP4)
1302
AS2( xor eax, eax)
1303
1304
AS1(carry2SubP4:)
1305
AS2( sub edi, ebp)
1306
AS2( mov ebp, 1)
1307
AS2( cmovc eax, ebp)
1308
AS2( mov [ecx+4], edi)
1309
AS2( add esi, 2)
1310
AS1( jnz loopstartSubP4)
1311
1312
AS1(loopendSubP4:)
1313
1314
AddEpilogue
1315
}
1316
1317
// multiply assembly code originally contributed by Leonard Janke
1318
1319
#define MulStartup \
1320
AS2(xor ebp, ebp) \
1321
AS2(xor edi, edi) \
1322
AS2(xor ebx, ebx)
1323
1324
#define MulShiftCarry \
1325
AS2(mov ebp, edx) \
1326
AS2(mov edi, ebx) \
1327
AS2(xor ebx, ebx)
1328
1329
#define MulAccumulateBottom(i,j) \
1330
AS2(mov eax, [ecx+4*j]) \
1331
AS2(imul eax, dword ptr [esi+4*i]) \
1332
AS2(add ebp, eax)
1333
1334
#define MulAccumulate(i,j) \
1335
AS2(mov eax, [ecx+4*j]) \
1336
AS1(mul dword ptr [esi+4*i]) \
1337
AS2(add ebp, eax) \
1338
AS2(adc edi, edx) \
1339
AS2(adc bl, bh)
1340
1341
#define MulStoreDigit(i) \
1342
AS2(mov edx, edi) \
1343
AS2(mov edi, [esp]) \
1344
AS2(mov [edi+4*i], ebp)
1345
1346
#define MulLastDiagonal(digits) \
1347
AS2(mov eax, [ecx+4*(digits-1)]) \
1348
AS1(mul dword ptr [esi+4*(digits-1)]) \
1349
AS2(add ebp, eax) \
1350
AS2(adc edx, edi) \
1351
AS2(mov edi, [esp]) \
1352
AS2(mov [edi+4*(2*digits-2)], ebp) \
1353
AS2(mov [edi+4*(2*digits-1)], edx)
1354
1355
CRYPTOPP_NAKED void PentiumOptimized::Multiply4(word* Z, const word* X, const word* Y)
1356
{
1357
MulPrologue
1358
// now: [esp] = Z, esi = X, ecx = Y
1359
MulStartup
1360
MulAccumulate(0,0)
1361
MulStoreDigit(0)
1362
MulShiftCarry
1363
1364
MulAccumulate(1,0)
1365
MulAccumulate(0,1)
1366
MulStoreDigit(1)
1367
MulShiftCarry
1368
1369
MulAccumulate(2,0)
1370
MulAccumulate(1,1)
1371
MulAccumulate(0,2)
1372
MulStoreDigit(2)
1373
MulShiftCarry
1374
1375
MulAccumulate(3,0)
1376
MulAccumulate(2,1)
1377
MulAccumulate(1,2)
1378
MulAccumulate(0,3)
1379
MulStoreDigit(3)
1380
MulShiftCarry
1381
1382
MulAccumulate(3,1)
1383
MulAccumulate(2,2)
1384
MulAccumulate(1,3)
1385
MulStoreDigit(4)
1386
MulShiftCarry
1387
1388
MulAccumulate(3,2)
1389
MulAccumulate(2,3)
1390
MulStoreDigit(5)
1391
MulShiftCarry
1392
1393
MulLastDiagonal(4)
1394
MulEpilogue
1395
}
1396
1397
CRYPTOPP_NAKED void PentiumOptimized::Multiply8(word* Z, const word* X, const word* Y)
1398
{
1399
MulPrologue
1400
// now: [esp] = Z, esi = X, ecx = Y
1401
MulStartup
1402
MulAccumulate(0,0)
1403
MulStoreDigit(0)
1404
MulShiftCarry
1405
1406
MulAccumulate(1,0)
1407
MulAccumulate(0,1)
1408
MulStoreDigit(1)
1409
MulShiftCarry
1410
1411
MulAccumulate(2,0)
1412
MulAccumulate(1,1)
1413
MulAccumulate(0,2)
1414
MulStoreDigit(2)
1415
MulShiftCarry
1416
1417
MulAccumulate(3,0)
1418
MulAccumulate(2,1)
1419
MulAccumulate(1,2)
1420
MulAccumulate(0,3)
1421
MulStoreDigit(3)
1422
MulShiftCarry
1423
1424
MulAccumulate(4,0)
1425
MulAccumulate(3,1)
1426
MulAccumulate(2,2)
1427
MulAccumulate(1,3)
1428
MulAccumulate(0,4)
1429
MulStoreDigit(4)
1430
MulShiftCarry
1431
1432
MulAccumulate(5,0)
1433
MulAccumulate(4,1)
1434
MulAccumulate(3,2)
1435
MulAccumulate(2,3)
1436
MulAccumulate(1,4)
1437
MulAccumulate(0,5)
1438
MulStoreDigit(5)
1439
MulShiftCarry
1440
1441
MulAccumulate(6,0)
1442
MulAccumulate(5,1)
1443
MulAccumulate(4,2)
1444
MulAccumulate(3,3)
1445
MulAccumulate(2,4)
1446
MulAccumulate(1,5)
1447
MulAccumulate(0,6)
1448
MulStoreDigit(6)
1449
MulShiftCarry
1450
1451
MulAccumulate(7,0)
1452
MulAccumulate(6,1)
1453
MulAccumulate(5,2)
1454
MulAccumulate(4,3)
1455
MulAccumulate(3,4)
1456
MulAccumulate(2,5)
1457
MulAccumulate(1,6)
1458
MulAccumulate(0,7)
1459
MulStoreDigit(7)
1460
MulShiftCarry
1461
1462
MulAccumulate(7,1)
1463
MulAccumulate(6,2)
1464
MulAccumulate(5,3)
1465
MulAccumulate(4,4)
1466
MulAccumulate(3,5)
1467
MulAccumulate(2,6)
1468
MulAccumulate(1,7)
1469
MulStoreDigit(8)
1470
MulShiftCarry
1471
1472
MulAccumulate(7,2)
1473
MulAccumulate(6,3)
1474
MulAccumulate(5,4)
1475
MulAccumulate(4,5)
1476
MulAccumulate(3,6)
1477
MulAccumulate(2,7)
1478
MulStoreDigit(9)
1479
MulShiftCarry
1480
1481
MulAccumulate(7,3)
1482
MulAccumulate(6,4)
1483
MulAccumulate(5,5)
1484
MulAccumulate(4,6)
1485
MulAccumulate(3,7)
1486
MulStoreDigit(10)
1487
MulShiftCarry
1488
1489
MulAccumulate(7,4)
1490
MulAccumulate(6,5)
1491
MulAccumulate(5,6)
1492
MulAccumulate(4,7)
1493
MulStoreDigit(11)
1494
MulShiftCarry
1495
1496
MulAccumulate(7,5)
1497
MulAccumulate(6,6)
1498
MulAccumulate(5,7)
1499
MulStoreDigit(12)
1500
MulShiftCarry
1501
1502
MulAccumulate(7,6)
1503
MulAccumulate(6,7)
1504
MulStoreDigit(13)
1505
MulShiftCarry
1506
1507
MulLastDiagonal(8)
1508
MulEpilogue
1509
}
1510
1511
CRYPTOPP_NAKED void PentiumOptimized::Multiply8Bottom(word* Z, const word* X, const word* Y)
1512
{
1513
MulPrologue
1514
// now: [esp] = Z, esi = X, ecx = Y
1515
MulStartup
1516
MulAccumulate(0,0)
1517
MulStoreDigit(0)
1518
MulShiftCarry
1519
1520
MulAccumulate(1,0)
1521
MulAccumulate(0,1)
1522
MulStoreDigit(1)
1523
MulShiftCarry
1524
1525
MulAccumulate(2,0)
1526
MulAccumulate(1,1)
1527
MulAccumulate(0,2)
1528
MulStoreDigit(2)
1529
MulShiftCarry
1530
1531
MulAccumulate(3,0)
1532
MulAccumulate(2,1)
1533
MulAccumulate(1,2)
1534
MulAccumulate(0,3)
1535
MulStoreDigit(3)
1536
MulShiftCarry
1537
1538
MulAccumulate(4,0)
1539
MulAccumulate(3,1)
1540
MulAccumulate(2,2)
1541
MulAccumulate(1,3)
1542
MulAccumulate(0,4)
1543
MulStoreDigit(4)
1544
MulShiftCarry
1545
1546
MulAccumulate(5,0)
1547
MulAccumulate(4,1)
1548
MulAccumulate(3,2)
1549
MulAccumulate(2,3)
1550
MulAccumulate(1,4)
1551
MulAccumulate(0,5)
1552
MulStoreDigit(5)
1553
MulShiftCarry
1554
1555
MulAccumulate(6,0)
1556
MulAccumulate(5,1)
1557
MulAccumulate(4,2)
1558
MulAccumulate(3,3)
1559
MulAccumulate(2,4)
1560
MulAccumulate(1,5)
1561
MulAccumulate(0,6)
1562
MulStoreDigit(6)
1563
MulShiftCarry
1564
1565
MulAccumulateBottom(7,0)
1566
MulAccumulateBottom(6,1)
1567
MulAccumulateBottom(5,2)
1568
MulAccumulateBottom(4,3)
1569
MulAccumulateBottom(3,4)
1570
MulAccumulateBottom(2,5)
1571
MulAccumulateBottom(1,6)
1572
MulAccumulateBottom(0,7)
1573
MulStoreDigit(7)
1574
MulEpilogue
1575
}
1576
1577
#undef AS1
1578
#undef AS2
1579
1580
#else // not x86 - no processor specific code at this layer
1581
1582
typedef Portable LowLevel;
1583
1584
#endif
1585
1586
#ifdef SSE2_INTRINSICS_AVAILABLE
1587
1588
#ifdef __GNUC__
1589
#define CRYPTOPP_FASTCALL
1590
#else
1591
#define CRYPTOPP_FASTCALL __fastcall
1592
#endif
1593
1594
static void CRYPTOPP_FASTCALL P4_Mul(__m128i *C, const __m128i *A, const __m128i *B)
1595
{
1596
__m128i a3210 = _mm_load_si128(A);
1597
__m128i b3210 = _mm_load_si128(B);
1598
1599
__m128i sum;
1600
1601
__m128i z = _mm_setzero_si128();
1602
__m128i a2b2_a0b0 = _mm_mul_epu32(a3210, b3210);
1603
C[0] = a2b2_a0b0;
1604
1605
__m128i a3120 = _mm_shuffle_epi32(a3210, _MM_SHUFFLE(3, 1, 2, 0));
1606
__m128i b3021 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(3, 0, 2, 1));
1607
__m128i a1b0_a0b1 = _mm_mul_epu32(a3120, b3021);
1608
__m128i a1b0 = _mm_unpackhi_epi32(a1b0_a0b1, z);
1609
__m128i a0b1 = _mm_unpacklo_epi32(a1b0_a0b1, z);
1610
C[1] = _mm_add_epi64(a1b0, a0b1);
1611
1612
__m128i a31 = _mm_srli_epi64(a3210, 32);
1613
__m128i b31 = _mm_srli_epi64(b3210, 32);
1614
__m128i a3b3_a1b1 = _mm_mul_epu32(a31, b31);
1615
C[6] = a3b3_a1b1;
1616
1617
__m128i a1b1 = _mm_unpacklo_epi32(a3b3_a1b1, z);
1618
__m128i b3012 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(3, 0, 1, 2));
1619
__m128i a2b0_a0b2 = _mm_mul_epu32(a3210, b3012);
1620
__m128i a0b2 = _mm_unpacklo_epi32(a2b0_a0b2, z);
1621
__m128i a2b0 = _mm_unpackhi_epi32(a2b0_a0b2, z);
1622
sum = _mm_add_epi64(a1b1, a0b2);
1623
C[2] = _mm_add_epi64(sum, a2b0);
1624
1625
__m128i a2301 = _mm_shuffle_epi32(a3210, _MM_SHUFFLE(2, 3, 0, 1));
1626
__m128i b2103 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(2, 1, 0, 3));
1627
__m128i a3b0_a1b2 = _mm_mul_epu32(a2301, b3012);
1628
__m128i a2b1_a0b3 = _mm_mul_epu32(a3210, b2103);
1629
__m128i a3b0 = _mm_unpackhi_epi32(a3b0_a1b2, z);
1630
__m128i a1b2 = _mm_unpacklo_epi32(a3b0_a1b2, z);
1631
__m128i a2b1 = _mm_unpackhi_epi32(a2b1_a0b3, z);
1632
__m128i a0b3 = _mm_unpacklo_epi32(a2b1_a0b3, z);
1633
__m128i sum1 = _mm_add_epi64(a3b0, a1b2);
1634
sum = _mm_add_epi64(a2b1, a0b3);
1635
C[3] = _mm_add_epi64(sum, sum1);
1636
1637
__m128i a3b1_a1b3 = _mm_mul_epu32(a2301, b2103);
1638
__m128i a2b2 = _mm_unpackhi_epi32(a2b2_a0b0, z);
1639
__m128i a3b1 = _mm_unpackhi_epi32(a3b1_a1b3, z);
1640
__m128i a1b3 = _mm_unpacklo_epi32(a3b1_a1b3, z);
1641
sum = _mm_add_epi64(a2b2, a3b1);
1642
C[4] = _mm_add_epi64(sum, a1b3);
1643
1644
__m128i a1302 = _mm_shuffle_epi32(a3210, _MM_SHUFFLE(1, 3, 0, 2));
1645
__m128i b1203 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(1, 2, 0, 3));
1646
__m128i a3b2_a2b3 = _mm_mul_epu32(a1302, b1203);
1647
__m128i a3b2 = _mm_unpackhi_epi32(a3b2_a2b3, z);
1648
__m128i a2b3 = _mm_unpacklo_epi32(a3b2_a2b3, z);
1649
C[5] = _mm_add_epi64(a3b2, a2b3);
1650
}
1651
1652
void P4Optimized::Multiply4(word *C, const word *A, const word *B)
1653
{
1654
__m128i temp[7];
1655
const word *w = (word *)temp;
1656
const __m64 *mw = (__m64 *)w;
1657
1658
P4_Mul(temp, (__m128i *)A, (__m128i *)B);
1659
1660
C[0] = w[0];
1661
1662
__m64 s1, s2;
1663
1664
__m64 w1 = _mm_cvtsi32_si64(w[1]);
1665
__m64 w4 = mw[2];
1666
__m64 w6 = mw[3];
1667
__m64 w8 = mw[4];
1668
__m64 w10 = mw[5];
1669
__m64 w12 = mw[6];
1670
__m64 w14 = mw[7];
1671
__m64 w16 = mw[8];
1672
__m64 w18 = mw[9];
1673
__m64 w20 = mw[10];
1674
__m64 w22 = mw[11];
1675
__m64 w26 = _mm_cvtsi32_si64(w[26]);
1676
1677
s1 = _mm_add_si64(w1, w4);
1678
C[1] = _mm_cvtsi64_si32(s1);
1679
s1 = _mm_srli_si64(s1, 32);
1680
1681
s2 = _mm_add_si64(w6, w8);
1682
s1 = _mm_add_si64(s1, s2);
1683
C[2] = _mm_cvtsi64_si32(s1);
1684
s1 = _mm_srli_si64(s1, 32);
1685
1686
s2 = _mm_add_si64(w10, w12);
1687
s1 = _mm_add_si64(s1, s2);
1688
C[3] = _mm_cvtsi64_si32(s1);
1689
s1 = _mm_srli_si64(s1, 32);
1690
1691
s2 = _mm_add_si64(w14, w16);
1692
s1 = _mm_add_si64(s1, s2);
1693
C[4] = _mm_cvtsi64_si32(s1);
1694
s1 = _mm_srli_si64(s1, 32);
1695
1696
s2 = _mm_add_si64(w18, w20);
1697
s1 = _mm_add_si64(s1, s2);
1698
C[5] = _mm_cvtsi64_si32(s1);
1699
s1 = _mm_srli_si64(s1, 32);
1700
1701
s2 = _mm_add_si64(w22, w26);
1702
s1 = _mm_add_si64(s1, s2);
1703
C[6] = _mm_cvtsi64_si32(s1);
1704
s1 = _mm_srli_si64(s1, 32);
1705
1706
C[7] = _mm_cvtsi64_si32(s1) + w[27];
1707
_mm_empty();
1708
}
1709
1710
void P4Optimized::Multiply8(word *C, const word *A, const word *B)
1711
{
1712
__m128i temp[28];
1713
const word *w = (word *)temp;
1714
const __m64 *mw = (__m64 *)w;
1715
const word *x = (word *)temp+7*4;
1716
const __m64 *mx = (__m64 *)x;
1717
const word *y = (word *)temp+7*4*2;
1718
const __m64 *my = (__m64 *)y;
1719
const word *z = (word *)temp+7*4*3;
1720
const __m64 *mz = (__m64 *)z;
1721
1722
P4_Mul(temp, (__m128i *)A, (__m128i *)B);
1723
1724
P4_Mul(temp+7, (__m128i *)A+1, (__m128i *)B);
1725
1726
P4_Mul(temp+14, (__m128i *)A, (__m128i *)B+1);
1727
1728
P4_Mul(temp+21, (__m128i *)A+1, (__m128i *)B+1);
1729
1730
C[0] = w[0];
1731
1732
__m64 s1, s2, s3, s4;
1733
1734
__m64 w1 = _mm_cvtsi32_si64(w[1]);
1735
__m64 w4 = mw[2];
1736
__m64 w6 = mw[3];
1737
__m64 w8 = mw[4];
1738
__m64 w10 = mw[5];
1739
__m64 w12 = mw[6];
1740
__m64 w14 = mw[7];
1741
__m64 w16 = mw[8];
1742
__m64 w18 = mw[9];
1743
__m64 w20 = mw[10];
1744
__m64 w22 = mw[11];
1745
__m64 w26 = _mm_cvtsi32_si64(w[26]);
1746
__m64 w27 = _mm_cvtsi32_si64(w[27]);
1747
1748
__m64 x0 = _mm_cvtsi32_si64(x[0]);
1749
__m64 x1 = _mm_cvtsi32_si64(x[1]);
1750
__m64 x4 = mx[2];
1751
__m64 x6 = mx[3];
1752
__m64 x8 = mx[4];
1753
__m64 x10 = mx[5];
1754
__m64 x12 = mx[6];
1755
__m64 x14 = mx[7];
1756
__m64 x16 = mx[8];
1757
__m64 x18 = mx[9];
1758
__m64 x20 = mx[10];
1759
__m64 x22 = mx[11];
1760
__m64 x26 = _mm_cvtsi32_si64(x[26]);
1761
__m64 x27 = _mm_cvtsi32_si64(x[27]);
1762
1763
__m64 y0 = _mm_cvtsi32_si64(y[0]);
1764
__m64 y1 = _mm_cvtsi32_si64(y[1]);
1765
__m64 y4 = my[2];
1766
__m64 y6 = my[3];
1767
__m64 y8 = my[4];
1768
__m64 y10 = my[5];
1769
__m64 y12 = my[6];
1770
__m64 y14 = my[7];
1771
__m64 y16 = my[8];
1772
__m64 y18 = my[9];
1773
__m64 y20 = my[10];
1774
__m64 y22 = my[11];
1775
__m64 y26 = _mm_cvtsi32_si64(y[26]);
1776
__m64 y27 = _mm_cvtsi32_si64(y[27]);
1777
1778
__m64 z0 = _mm_cvtsi32_si64(z[0]);
1779
__m64 z1 = _mm_cvtsi32_si64(z[1]);
1780
__m64 z4 = mz[2];
1781
__m64 z6 = mz[3];
1782
__m64 z8 = mz[4];
1783
__m64 z10 = mz[5];
1784
__m64 z12 = mz[6];
1785
__m64 z14 = mz[7];
1786
__m64 z16 = mz[8];
1787
__m64 z18 = mz[9];
1788
__m64 z20 = mz[10];
1789
__m64 z22 = mz[11];
1790
__m64 z26 = _mm_cvtsi32_si64(z[26]);
1791
1792
s1 = _mm_add_si64(w1, w4);
1793
C[1] = _mm_cvtsi64_si32(s1);
1794
s1 = _mm_srli_si64(s1, 32);
1795
1796
s2 = _mm_add_si64(w6, w8);
1797
s1 = _mm_add_si64(s1, s2);
1798
C[2] = _mm_cvtsi64_si32(s1);
1799
s1 = _mm_srli_si64(s1, 32);
1800
1801
s2 = _mm_add_si64(w10, w12);
1802
s1 = _mm_add_si64(s1, s2);
1803
C[3] = _mm_cvtsi64_si32(s1);
1804
s1 = _mm_srli_si64(s1, 32);
1805
1806
s3 = _mm_add_si64(x0, y0);
1807
s2 = _mm_add_si64(w14, w16);
1808
s1 = _mm_add_si64(s1, s3);
1809
s1 = _mm_add_si64(s1, s2);
1810
C[4] = _mm_cvtsi64_si32(s1);
1811
s1 = _mm_srli_si64(s1, 32);
1812
1813
s3 = _mm_add_si64(x1, y1);
1814
s4 = _mm_add_si64(x4, y4);
1815
s1 = _mm_add_si64(s1, w18);
1816
s3 = _mm_add_si64(s3, s4);
1817
s1 = _mm_add_si64(s1, w20);
1818
s1 = _mm_add_si64(s1, s3);
1819
C[5] = _mm_cvtsi64_si32(s1);
1820
s1 = _mm_srli_si64(s1, 32);
1821
1822
s3 = _mm_add_si64(x6, y6);
1823
s4 = _mm_add_si64(x8, y8);
1824
s1 = _mm_add_si64(s1, w22);
1825
s3 = _mm_add_si64(s3, s4);
1826
s1 = _mm_add_si64(s1, w26);
1827
s1 = _mm_add_si64(s1, s3);
1828
C[6] = _mm_cvtsi64_si32(s1);
1829
s1 = _mm_srli_si64(s1, 32);
1830
1831
s3 = _mm_add_si64(x10, y10);
1832
s4 = _mm_add_si64(x12, y12);
1833
s1 = _mm_add_si64(s1, w27);
1834
s3 = _mm_add_si64(s3, s4);
1835
s1 = _mm_add_si64(s1, s3);
1836
C[7] = _mm_cvtsi64_si32(s1);
1837
s1 = _mm_srli_si64(s1, 32);
1838
1839
s3 = _mm_add_si64(x14, y14);
1840
s4 = _mm_add_si64(x16, y16);
1841
s1 = _mm_add_si64(s1, z0);
1842
s3 = _mm_add_si64(s3, s4);
1843
s1 = _mm_add_si64(s1, s3);
1844
C[8] = _mm_cvtsi64_si32(s1);
1845
s1 = _mm_srli_si64(s1, 32);
1846
1847
s3 = _mm_add_si64(x18, y18);
1848
s4 = _mm_add_si64(x20, y20);
1849
s1 = _mm_add_si64(s1, z1);
1850
s3 = _mm_add_si64(s3, s4);
1851
s1 = _mm_add_si64(s1, z4);
1852
s1 = _mm_add_si64(s1, s3);
1853
C[9] = _mm_cvtsi64_si32(s1);
1854
s1 = _mm_srli_si64(s1, 32);
1855
1856
s3 = _mm_add_si64(x22, y22);
1857
s4 = _mm_add_si64(x26, y26);
1858
s1 = _mm_add_si64(s1, z6);
1859
s3 = _mm_add_si64(s3, s4);
1860
s1 = _mm_add_si64(s1, z8);
1861
s1 = _mm_add_si64(s1, s3);
1862
C[10] = _mm_cvtsi64_si32(s1);
1863
s1 = _mm_srli_si64(s1, 32);
1864
1865
s3 = _mm_add_si64(x27, y27);
1866
s1 = _mm_add_si64(s1, z10);
1867
s1 = _mm_add_si64(s1, z12);
1868
s1 = _mm_add_si64(s1, s3);
1869
C[11] = _mm_cvtsi64_si32(s1);
1870
s1 = _mm_srli_si64(s1, 32);
1871
1872
s3 = _mm_add_si64(z14, z16);
1873
s1 = _mm_add_si64(s1, s3);
1874
C[12] = _mm_cvtsi64_si32(s1);
1875
s1 = _mm_srli_si64(s1, 32);
1876
1877
s3 = _mm_add_si64(z18, z20);
1878
s1 = _mm_add_si64(s1, s3);
1879
C[13] = _mm_cvtsi64_si32(s1);
1880
s1 = _mm_srli_si64(s1, 32);
1881
1882
s3 = _mm_add_si64(z22, z26);
1883
s1 = _mm_add_si64(s1, s3);
1884
C[14] = _mm_cvtsi64_si32(s1);
1885
s1 = _mm_srli_si64(s1, 32);
1886
1887
C[15] = z[27] + _mm_cvtsi64_si32(s1);
1888
_mm_empty();
1889
}
1890
1891
void P4Optimized::Multiply8Bottom(word *C, const word *A, const word *B)
1892
{
1893
__m128i temp[21];
1894
const word *w = (word *)temp;
1895
const __m64 *mw = (__m64 *)w;
1896
const word *x = (word *)temp+7*4;
1897
const __m64 *mx = (__m64 *)x;
1898
const word *y = (word *)temp+7*4*2;
1899
const __m64 *my = (__m64 *)y;
1900
1901
P4_Mul(temp, (__m128i *)A, (__m128i *)B);
1902
1903
P4_Mul(temp+7, (__m128i *)A+1, (__m128i *)B);
1904
1905
P4_Mul(temp+14, (__m128i *)A, (__m128i *)B+1);
1906
1907
C[0] = w[0];
1908
1909
__m64 s1, s2, s3, s4;
1910
1911
__m64 w1 = _mm_cvtsi32_si64(w[1]);
1912
__m64 w4 = mw[2];
1913
__m64 w6 = mw[3];
1914
__m64 w8 = mw[4];
1915
__m64 w10 = mw[5];
1916
__m64 w12 = mw[6];
1917
__m64 w14 = mw[7];
1918
__m64 w16 = mw[8];
1919
__m64 w18 = mw[9];
1920
__m64 w20 = mw[10];
1921
__m64 w22 = mw[11];
1922
__m64 w26 = _mm_cvtsi32_si64(w[26]);
1923
1924
__m64 x0 = _mm_cvtsi32_si64(x[0]);
1925
__m64 x1 = _mm_cvtsi32_si64(x[1]);
1926
__m64 x4 = mx[2];
1927
__m64 x6 = mx[3];
1928
__m64 x8 = mx[4];
1929
1930
__m64 y0 = _mm_cvtsi32_si64(y[0]);
1931
__m64 y1 = _mm_cvtsi32_si64(y[1]);
1932
__m64 y4 = my[2];
1933
__m64 y6 = my[3];
1934
__m64 y8 = my[4];
1935
1936
s1 = _mm_add_si64(w1, w4);
1937
C[1] = _mm_cvtsi64_si32(s1);
1938
s1 = _mm_srli_si64(s1, 32);
1939
1940
s2 = _mm_add_si64(w6, w8);
1941
s1 = _mm_add_si64(s1, s2);
1942
C[2] = _mm_cvtsi64_si32(s1);
1943
s1 = _mm_srli_si64(s1, 32);
1944
1945
s2 = _mm_add_si64(w10, w12);
1946
s1 = _mm_add_si64(s1, s2);
1947
C[3] = _mm_cvtsi64_si32(s1);
1948
s1 = _mm_srli_si64(s1, 32);
1949
1950
s3 = _mm_add_si64(x0, y0);
1951
s2 = _mm_add_si64(w14, w16);
1952
s1 = _mm_add_si64(s1, s3);
1953
s1 = _mm_add_si64(s1, s2);
1954
C[4] = _mm_cvtsi64_si32(s1);
1955
s1 = _mm_srli_si64(s1, 32);
1956
1957
s3 = _mm_add_si64(x1, y1);
1958
s4 = _mm_add_si64(x4, y4);
1959
s1 = _mm_add_si64(s1, w18);
1960
s3 = _mm_add_si64(s3, s4);
1961
s1 = _mm_add_si64(s1, w20);
1962
s1 = _mm_add_si64(s1, s3);
1963
C[5] = _mm_cvtsi64_si32(s1);
1964
s1 = _mm_srli_si64(s1, 32);
1965
1966
s3 = _mm_add_si64(x6, y6);
1967
s4 = _mm_add_si64(x8, y8);
1968
s1 = _mm_add_si64(s1, w22);
1969
s3 = _mm_add_si64(s3, s4);
1970
s1 = _mm_add_si64(s1, w26);
1971
s1 = _mm_add_si64(s1, s3);
1972
C[6] = _mm_cvtsi64_si32(s1);
1973
s1 = _mm_srli_si64(s1, 32);
1974
1975
C[7] = _mm_cvtsi64_si32(s1) + w[27] + x[10] + y[10] + x[12] + y[12];
1976
_mm_empty();
1977
}
1978
1979
#endif // #ifdef SSE2_INTRINSICS_AVAILABLE
2021
}
2022
2023
inline int Add(word *C, const word *A, const word *B, size_t N)
2024
{
2025
#if CRYPTOPP_INTEGER_SSE2
2026
return s_pAdd(N, C, A, B);
2027
#else
2028
return Baseline_Add(N, C, A, B);
2029
#endif
2030
}
2031
2032
inline int Subtract(word *C, const word *A, const word *B, size_t N)
2033
{
2034
#if CRYPTOPP_INTEGER_SSE2
2035
return s_pSub(N, C, A, B);
2036
#else
2037
return Baseline_Sub(N, C, A, B);
2038
#endif
2039
}
1980
2040
1981
2041
// ********************************************************
1982
2042
2043
1983
2044
#define A0 A
1984
2045
#define A1 (A+N2)
1985
2046
#define B0 B
2004
2065
{
2005
2066
assert(N>=2 && N%2==0);
2006
2067
2007
if (LowLevel::MultiplyRecursionLimit() >= 8 && N==8)
2008
LowLevel::Multiply8(R, A, B);
2009
else if (LowLevel::MultiplyRecursionLimit() >= 4 && N==4)
2010
LowLevel::Multiply4(R, A, B);
2011
else if (N==2)
2012
LowLevel::Multiply2(R, A, B);
2068
if (N <= s_recursionLimit)
2069
s_pMul[N/4](R, A, B);
2013
2070
else
2014
2071
{
2015
2072
const size_t N2 = N/2;
2016
int carry;
2017
2018
int aComp = Compare(A0, A1, N2);
2019
int bComp = Compare(B0, B1, N2);
2020
2021
switch (2*aComp + aComp + bComp)
2022
{
2023
case -4:
2024
LowLevel::Subtract(R0, A1, A0, N2);
2025
LowLevel::Subtract(R1, B0, B1, N2);
2026
RecursiveMultiply(T0, T2, R0, R1, N2);
2027
LowLevel::Subtract(T1, T1, R0, N2);
2028
carry = -1;
2029
break;
2030
case -2:
2031
LowLevel::Subtract(R0, A1, A0, N2);
2032
LowLevel::Subtract(R1, B0, B1, N2);
2033
RecursiveMultiply(T0, T2, R0, R1, N2);
2034
carry = 0;
2035
break;
2036
case 2:
2037
LowLevel::Subtract(R0, A0, A1, N2);
2038
LowLevel::Subtract(R1, B1, B0, N2);
2039
RecursiveMultiply(T0, T2, R0, R1, N2);
2040
carry = 0;
2041
break;
2042
case 4:
2043
LowLevel::Subtract(R0, A1, A0, N2);
2044
LowLevel::Subtract(R1, B0, B1, N2);
2045
RecursiveMultiply(T0, T2, R0, R1, N2);
2046
LowLevel::Subtract(T1, T1, R1, N2);
2047
carry = -1;
2048
break;
2049
default:
2050
SetWords(T0, 0, N);
2051
carry = 0;
2052
}
2053
2073
2074
size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2075
Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2076
2077
size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2078
Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2079
2080
RecursiveMultiply(R2, T2, A1, B1, N2);
2081
RecursiveMultiply(T0, T2, R0, R1, N2);
2054
2082
RecursiveMultiply(R0, T2, A0, B0, N2);
2055
RecursiveMultiply(R2, T2, A1, B1, N2);
2056
2083
2057
2084
// now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1
2058
2085
2059
carry += LowLevel::Add(T0, T0, R0, N);
2060
carry += LowLevel::Add(T0, T0, R2, N);
2061
carry += LowLevel::Add(R1, R1, T0, N);
2062
2063
assert (carry >= 0 && carry <= 2);
2064
Increment(R3, N2, carry);
2086
int c2 = Add(R2, R2, R1, N2);
2087
int c3 = c2;
2088
c2 += Add(R1, R2, R0, N2);
2089
c3 += Add(R2, R2, R3, N2);
2090
2091
if (AN2 == BN2)
2092
c3 -= Subtract(R1, R1, T0, N);
2093
else
2094
c3 += Add(R1, R1, T0, N);
2095
2096
c3 += Increment(R2, N2, c2);
2097
assert (c3 >= 0 && c3 <= 2);
2098
Increment(R3, N2, c3);
2065
2099
}
2066
2100
}
2067
2101
2072
2106
void RecursiveSquare(word *R, word *T, const word *A, size_t N)
2073
2107
{
2074
2108
assert(N && N%2==0);
2075
if (LowLevel::SquareRecursionLimit() >= 8 && N==8)
2076
LowLevel::Square8(R, A);
2077
if (LowLevel::SquareRecursionLimit() >= 4 && N==4)
2078
LowLevel::Square4(R, A);
2079
else if (N==2)
2080
LowLevel::Square2(R, A);
2109
2110
if (N <= s_recursionLimit)
2111
s_pSqu[N/4](R, A);
2081
2112
else
2082
2113
{
2083
2114
const size_t N2 = N/2;
2086
2117
RecursiveSquare(R2, T2, A1, N2);
2087
2118
RecursiveMultiply(T0, T2, A0, A1, N2);
2088
2119
2089
int carry = LowLevel::Add(R1, R1, T0, N);
2090
carry += LowLevel::Add(R1, R1, T0, N);
2120
int carry = Add(R1, R1, T0, N);
2121
carry += Add(R1, R1, T0, N);
2091
2122
Increment(R3, N2, carry);
2092
2123
}
2093
2124
}
2094
2125
2095
2126
// R[N] - bottom half of A*B
2096
// T[N] - temporary work space
2127
// T[3*N/2] - temporary work space
2097
2128
// A[N] - multiplier
2098
2129
// B[N] - multiplicant
2099
2130
2100
2131
void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N)
2101
2132
{
2102
2133
assert(N>=2 && N%2==0);
2103
if (LowLevel::MultiplyBottomRecursionLimit() >= 8 && N==8)
2104
LowLevel::Multiply8Bottom(R, A, B);
2105
else if (LowLevel::MultiplyBottomRecursionLimit() >= 4 && N==4)
2106
LowLevel::Multiply4Bottom(R, A, B);
2107
else if (N==2)
2108
LowLevel::Multiply2Bottom(R, A, B);
2134
2135
if (N <= s_recursionLimit)
2136
s_pBot[N/4](R, A, B);
2109
2137
else
2110
2138
{
2111
2139
const size_t N2 = N/2;
2112
2140
2113
2141
RecursiveMultiply(R, T, A0, B0, N2);
2114
2142
RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2115
LowLevel::Add(R1, R1, T0, N2);
2143
Add(R1, R1, T0, N2);
2116
2144
RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2117
LowLevel::Add(R1, R1, T0, N2);
2145
Add(R1, R1, T0, N2);
2118
2146
}
2119
2147
}
2120
2148
2124
2152
// A[N] --- multiplier
2125
2153
// B[N] --- multiplicant
2126
2154
2127
void RecursiveMultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
2155
void MultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
2128
2156
{
2129
2157
assert(N>=2 && N%2==0);
2130
2158
2131
if (N==4)
2132
{
2133
LowLevel::Multiply4(T, A, B);
2134
memcpy(R, T+4, 4*WORD_SIZE);
2135
}
2136
else if (N==2)
2137
{
2138
LowLevel::Multiply2(T, A, B);
2139
memcpy(R, T+2, 2*WORD_SIZE);
2140
}
2159
if (N <= s_recursionLimit)
2160
s_pTop[N/4](R, A, B, L[N-1]);
2141
2161
else
2142
2162
{
2143
2163
const size_t N2 = N/2;
2144
int carry;
2145
2146
int aComp = Compare(A0, A1, N2);
2147
int bComp = Compare(B0, B1, N2);
2148
2149
switch (2*aComp + aComp + bComp)
2150
{
2151
case -4:
2152
LowLevel::Subtract(R0, A1, A0, N2);
2153
LowLevel::Subtract(R1, B0, B1, N2);
2154
RecursiveMultiply(T0, T2, R0, R1, N2);
2155
LowLevel::Subtract(T1, T1, R0, N2);
2156
carry = -1;
2157
break;
2158
case -2:
2159
LowLevel::Subtract(R0, A1, A0, N2);
2160
LowLevel::Subtract(R1, B0, B1, N2);
2161
RecursiveMultiply(T0, T2, R0, R1, N2);
2162
carry = 0;
2163
break;
2164
case 2:
2165
LowLevel::Subtract(R0, A0, A1, N2);
2166
LowLevel::Subtract(R1, B1, B0, N2);
2167
RecursiveMultiply(T0, T2, R0, R1, N2);
2168
carry = 0;
2169
break;
2170
case 4:
2171
LowLevel::Subtract(R0, A1, A0, N2);
2172
LowLevel::Subtract(R1, B0, B1, N2);
2173
RecursiveMultiply(T0, T2, R0, R1, N2);
2174
LowLevel::Subtract(T1, T1, R1, N2);
2175
carry = -1;
2176
break;
2177
default:
2178
SetWords(T0, 0, N);
2179
carry = 0;
2180
}
2181
2182
RecursiveMultiply(T2, R0, A1, B1, N2);
2183
2184
// now T[01] holds (A1-A0)*(B0-B1), T[23] holds A1*B1
2185
2186
int c2 = LowLevel::Subtract(R0, L+N2, L, N2);
2187
c2 += LowLevel::Subtract(R0, R0, T0, N2);
2188
int t = (Compare(R0, T2, N2) == -1);
2189
2190
carry += t;
2191
carry += Increment(R0, N2, c2+t);
2192
carry += LowLevel::Add(R0, R0, T1, N2);
2193
carry += LowLevel::Add(R0, R0, T3, N2);
2194
assert (carry >= 0 && carry <= 2);
2195
2196
CopyWords(R1, T3, N2);
2197
Increment(R1, N2, carry);
2164
2165
size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2166
Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2167
2168
size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2169
Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2170
2171
RecursiveMultiply(T0, T2, R0, R1, N2);
2172
RecursiveMultiply(R0, T2, A1, B1, N2);
2173
2174
// now T[01] holds (A1-A0)*(B0-B1) = A1*B0+A0*B1-A1*B1-A0*B0, R[01] holds A1*B1
2175
2176
int t, c3;
2177
int c2 = Subtract(T2, L+N2, L, N2);
2178
2179
if (AN2 == BN2)
2180
{
2181
c2 -= Add(T2, T2, T0, N2);
2182
t = (Compare(T2, R0, N2) == -1);
2183
c3 = t - Subtract(T2, T2, T1, N2);
2184
}
2185
else
2186
{
2187
c2 += Subtract(T2, T2, T0, N2);
2188
t = (Compare(T2, R0, N2) == -1);
2189
c3 = t + Add(T2, T2, T1, N2);
2190
}
2191
2192
c2 += t;
2193
if (c2 >= 0)
2194
c3 += Increment(T2, N2, c2);
2195
else
2196
c3 -= Decrement(T2, N2, -c2);
2197
c3 += Add(R0, T2, R1, N2);
2198
2199
assert (c3 >= 0 && c3 <= 2);
2200
Increment(R1, N2, c3);
2198
2201
}
2199
2202
}
2200
2203
2201
inline int Add(word *C, const word *A, const word *B, size_t N)
2202
{
2203
return LowLevel::Add(C, A, B, N);
2204
}
2205
2206
inline int Subtract(word *C, const word *A, const word *B, size_t N)
2207
{
2208
return LowLevel::Subtract(C, A, B, N);
2209
}
2210
2211
2204
inline void Multiply(word *R, word *T, const word *A, const word *B, size_t N)
2212
2205
{
2213
2206
RecursiveMultiply(R, T, A, B, N);
2223
2216
RecursiveMultiplyBottom(R, T, A, B, N);
2224
2217
}
2225
2218
2226
inline void MultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
2227
{
2228
RecursiveMultiplyTop(R, T, L, A, B, N);
2229
}
2230
2231
static word LinearMultiply(word *C, const word *A, word B, size_t N)
2232
{
2233
word carry=0;
2234
for(unsigned i=0; i<N; i++)
2235
{
2236
DWord p = DWord::MultiplyAndAdd(A[i], B, carry);
2237
C[i] = p.GetLowHalf();
2238
carry = p.GetHighHalf();
2239
}
2240
return carry;
2241
}
2242
2243
2219
// R[NA+NB] - result = A*B
2244
2220
// T[NA+NB] - temporary work space
2245
2221
// A[NA] ---- multiplier
2264
2240
}
2265
2241
2266
2242
assert(NB % NA == 0);
2267
assert((NB/NA)%2 == 0); // NB is an even multiple of NA
2268
2243
2269
2244
if (NA==2 && !A[1])
2270
2245
{
2284
2259
}
2285
2260
}
2286
2261
2287
Multiply(R, T, A, B, NA);
2288
CopyWords(T+2*NA, R+NA, NA);
2289
2290
2262
size_t i;
2263
if ((NB/NA)%2 == 0)
2264
{
2265
Multiply(R, T, A, B, NA);
2266
CopyWords(T+2*NA, R+NA, NA);
2291
2267
2292
for (i=2*NA; i<NB; i+=2*NA)
2293
Multiply(T+NA+i, T, A, B+i, NA);
2294
for (i=NA; i<NB; i+=2*NA)
2295
Multiply(R+i, T, A, B+i, NA);
2268
for (i=2*NA; i<NB; i+=2*NA)
2269
Multiply(T+NA+i, T, A, B+i, NA);
2270
for (i=NA; i<NB; i+=2*NA)
2271
Multiply(R+i, T, A, B+i, NA);
2272
}
2273
else
2274
{
2275
for (i=0; i<NB; i+=2*NA)
2276
Multiply(R+i, T, A, B+i, NA);
2277
for (i=NA; i<NB; i+=2*NA)
2278
Multiply(T+NA+i, T, A, B+i, NA);
2279
}
2296
2280
2297
2281
if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2298
2282
Increment(R+NB, NA);
2308
2292
{
2309
2293
T[0] = AtomicInverseModPower2(A[0]);
2310
2294
T[1] = 0;
2311
LowLevel::Multiply2Bottom(T+2, T, A);
2295
s_pBot[0](T+2, T, A);
2312
2296
TwosComplement(T+2, 2);
2313
2297
Increment(T+2, 2, 2);
2314
LowLevel::Multiply2Bottom(R, T, T+2);
2298
s_pBot[0](R, T, T+2);
2315
2299
}
2316
2300
else
2317
2301
{
2333
2317
// M[N] --- modulus
2334
2318
// U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)
2335
2319
2336
void MontgomeryReduce(word *R, word *T, const word *X, const word *M, const word *U, size_t N)
2320
void MontgomeryReduce(word *R, word *T, word *X, const word *M, const word *U, size_t N)
2337
2321
{
2322
#if 1
2338
2323
MultiplyBottom(R, T, X, U, N);
2339
2324
MultiplyTop(T, T+N, X, R, M, N);
2340
2325
word borrow = Subtract(T, X+N, T, N);
2341
2326
// defend against timing attack by doing this Add even when not needed
2342
2327
word carry = Add(T+N, T, M, N);
2343
assert(carry || !borrow);
2344
CopyWords(R, T + (borrow ? N : 0), N);
2328
assert(carry | !borrow);
2329
CopyWords(R, T + ((0-borrow) & N), N);
2330
#elif 0
2331
const word u = 0-U[0];
2332
Declare2Words(p)
2333
for (size_t i=0; i<N; i++)
2334
{
2335
const word t = u * X[i];
2336
word c = 0;
2337
for (size_t j=0; j<N; j+=2)
2338
{
2339
MultiplyWords(p, t, M[j]);
2340
Acc2WordsBy1(p, X[i+j]);
2341
Acc2WordsBy1(p, c);
2342
X[i+j] = LowWord(p);
2343
c = HighWord(p);
2344
MultiplyWords(p, t, M[j+1]);
2345
Acc2WordsBy1(p, X[i+j+1]);
2346
Acc2WordsBy1(p, c);
2347
X[i+j+1] = LowWord(p);
2348
c = HighWord(p);
2349
}
2350
2351
if (Increment(X+N+i, N-i, c))
2352
while (!Subtract(X+N, X+N, M, N)) {}
2353
}
2354
2355
memcpy(R, X+N, N*WORD_SIZE);
2356
#else
2357
__m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2358
for (size_t i=0; i<N; i++)
2359
{
2360
__m64 t = _mm_cvtsi32_si64(X[i]);
2361
t = _mm_mul_su32(t, u);
2362
__m64 c = _mm_setzero_si64();
2363
for (size_t j=0; j<N; j+=2)
2364
{
2365
p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2366
p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2367
c = _mm_add_si64(c, p);
2368
X[i+j] = _mm_cvtsi64_si32(c);
2369
c = _mm_srli_si64(c, 32);
2370
p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2371
p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2372
c = _mm_add_si64(c, p);
2373
X[i+j+1] = _mm_cvtsi64_si32(c);
2374
c = _mm_srli_si64(c, 32);
2375
}
2376
2377
if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2378
while (!Subtract(X+N, X+N, M, N)) {}
2379
}
2380
2381
memcpy(R, X+N, N*WORD_SIZE);
2382
_mm_empty();
2383
#endif
2345
2384
}
2346
2385
2347
2386
// R[N] --- result = X/(2**(WORD_BITS*N/2)) mod M
2491
2530
// multiply quotient and divisor and add remainder, make sure it equals dividend
2492
2531
assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2493
2532
word P[4];
2494
Portable::Multiply2(P, Q, B);
2533
s_pMul[0](P, Q, B);
2495
2534
Add(P, P, T, 4);
2496
2535
assert(memcmp(P, A, 4*WORD_SIZE)==0);
2497
2536
}
2503
2542
{
2504
2543
assert(N && N%2==0);
2505
2544
2506
if (Q[1])
2507
{
2508
T[N] = T[N+1] = 0;
2509
unsigned i;
2510
for (i=0; i<N; i+=4)
2511
LowLevel::Multiply2(T+i, Q, B+i);
2512
for (i=2; i<N; i+=4)
2513
if (LowLevel::Multiply2Add(T+i, Q, B+i))
2514
T[i+5] += (++T[i+4]==0);
2515
}
2516
else
2517
{
2518
T[N] = LinearMultiply(T, B, Q[0], N);
2519
T[N+1] = 0;
2520
}
2545
AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2521
2546
2522
2547
word borrow = Subtract(R, R, T, N+2);
2523
2548
assert(!borrow && !R[N+1]);
2532
2557
2533
2558
// R[NB] -------- remainder = A%B
2534
2559
// Q[NA-NB+2] --- quotient = A/B
2535
// T[NA+2*NB+4] - temp work space
2560
// T[NA+3*(NB+2)] - temp work space
2536
2561
// A[NA] -------- dividend
2537
2562
// B[NB] -------- divisor
2538
2563
2613
2638
word *f = T+2*N;
2614
2639
word *g = T+3*N;
2615
2640
size_t bcLen=2, fgLen=EvenWordCount(M, N);
2616
unsigned int k=0, s=0;
2641
unsigned int k=0;
2642
bool s=false;
2617
2643
2618
2644
SetWords(T, 0, 3*N);
2619
2645
b[0]=1;
2632
2658
}
2633
2659
2634
2660
ShiftWordsRightByWords(f, fgLen, 1);
2635
if (c[bcLen-1]) bcLen+=2;
2661
bcLen += 2 * (c[bcLen-1] != 0);
2636
2662
assert(bcLen <= N);
2637
2663
ShiftWordsLeftByWords(c, bcLen, 1);
2638
2664
k+=WORD_BITS;
2639
2665
t=f[0];
2640
2666
}
2641
2667
2642
unsigned int i=0;
2643
while (t%2 == 0)
2644
{
2645
t>>=1;
2646
i++;
2647
}
2648
k+=i;
2668
unsigned int i = TrailingZeros(t);
2669
t >>= i;
2670
k += i;
2649
2671
2650
if (t==1 && f[1]==0 && EvenWordCount(f, fgLen)==2)
2672
if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0)
2651
2673
{
2652
if (s%2==0)
2674
if (s)
2675
Subtract(R, M, b, N);
2676
else
2653
2677
CopyWords(R, b, N);
2654
else
2655
Subtract(R, M, b, N);
2656
2678
return k;
2657
2679
}
2658
2680
2659
2681
ShiftWordsRightByBits(f, fgLen, i);
2660
t=ShiftWordsLeftByBits(c, bcLen, i);
2661
if (t)
2662
{
2663
c[bcLen] = t;
2664
bcLen+=2;
2665
assert(bcLen <= N);
2666
}
2667
2668
if (f[fgLen-2]==0 && g[fgLen-2]==0 && f[fgLen-1]==0 && g[fgLen-1]==0)
2669
fgLen-=2;
2670
2671
if (Compare(f, g, fgLen)==-1)
2672
{
2673
std::swap(f, g);
2674
std::swap(b, c);
2675
s++;
2676
}
2682
t = ShiftWordsLeftByBits(c, bcLen, i);
2683
c[bcLen] += t;
2684
bcLen += 2 * (t!=0);
2685
assert(bcLen <= N);
2686
2687
bool swap = Compare(f, g, fgLen)==-1;
2688
ConditionalSwapPointers(swap, f, g);
2689
ConditionalSwapPointers(swap, b, c);
2690
s ^= swap;
2691
2692
fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]);
2677
2693
2678
2694
Subtract(f, f, g, fgLen);
2679
2680
if (Add(b, b, c, bcLen))
2681
{
2682
b[bcLen] = 1;
2683
bcLen+=2;
2684
assert(bcLen <= N);
2685
}
2695
t = Add(b, b, c, bcLen);
2696
b[bcLen] += t;
2697
bcLen += 2*t;
2698
assert(bcLen <= N);
2686
2699
}
2687
2700
}
2688
2701
2726
2739
{
2727
2740
if (!g_pAssignIntToInteger)
2728
2741
{
2729
#ifdef CRYPTOPP_X86ASM_AVAILABLE
2730
SetPentiumFunctionPointers();
2731
#endif
2742
SetFunctionPointers();
2732
2743
g_pAssignIntToInteger = AssignIntToInteger;
2733
2744
}
2734
2745
}
2877
2888
{
2878
2889
if (this != &t)
2879
2890
{
2880
reg.New(RoundupSize(t.WordCount()));
2891
if (reg.size() != t.reg.size() || t.reg[t.reg.size()/2] == 0)
2892
reg.New(RoundupSize(t.WordCount()));
2881
2893
CopyWords(reg, t.reg, reg.size());
2882
2894
sign = t.sign;
2883
2895
}
3231
3243
memcpy(m_counterAndSeed + 4, seed, seedSize);
3232
3244
}
3233
3245
3234
byte GenerateByte()
3235
{
3236
byte b;
3237
GenerateBlock(&b, 1);
3238
return b;
3239
}
3240
3241
void GenerateBlock(byte *output, unsigned int size)
3242
{
3243
UnalignedPutWord(BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3246
void GenerateBlock(byte *output, size_t size)
3247
{
3248
PutWord(false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3244
3249
++m_counter;
3245
3250
P1363_KDF2<SHA1>::DeriveKey(output, size, m_counterAndSeed, m_counterAndSeed.size(), NULL, 0);
3246
3251
}
3275
3280
3276
3281
member_ptr<KDF2_RNG> kdf2Rng;
3277
3282
ConstByteArrayParameter seed;
3278
if (params.GetValue("Seed", seed))
3283
if (params.GetValue(Name::Seed(), seed))
3279
3284
{
3280
3285
ByteQueue bq;
3281
3286
DERSequenceEncoder seq(bq);
3392
3397
suffix = '.';
3393
3398
}
3394
3399
3395
SecBlock<char> s(a.BitCount() / (BitPrecision(base)-1) + 1);
3396
3400
Integer temp1=a, temp2;
3397
unsigned i=0;
3398
const char vec[]="0123456789ABCDEF";
3399
3401
3400
3402
if (a.IsNegative())
3401
3403
{
3402
3404
out << '-';
3406
3408
if (!a)
3407
3409
out << '0';
3408
3410
3411
static const char upper[]="0123456789ABCDEF";
3412
static const char lower[]="0123456789abcdef";
3413
3414
const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3415
unsigned i=0;
3416
SecBlock<char> s(a.BitCount() / (BitPrecision(base)-1) + 1);
3417
3409
3418
while (!!temp1)
3410
3419
{
3411
3420
word digit;
3412
3421
Integer::Divide(digit, temp2, temp1, base);
3413
3422
s[i++]=vec[digit];
3414
temp1=temp2;
3423
temp1.swap(temp2);
3415
3424
}
3416
3425
3417
3426
while (i--)
3657
3666
product.reg.CleanNew(RoundupSize(aSize+bSize));
3658
3667
product.sign = Integer::POSITIVE;
3659
3668
3660
SecAlignedWordBlock workspace(aSize + bSize);
3669
IntegerSecBlock workspace(aSize + bSize);
3661
3670
AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
3662
3671
}
3663
3672
3707
3716
if (!bSize)
3708
3717
throw Integer::DivideByZero();
3709
3718
3710
if (a.PositiveCompare(b) == -1)
3719
if (aSize < bSize)
3711
3720
{
3712
3721
remainder = a;
3713
3722
remainder.sign = Integer::POSITIVE;
3723
3732
quotient.reg.CleanNew(RoundupSize(aSize-bSize+2));
3724
3733
quotient.sign = Integer::POSITIVE;
3725
3734
3726
SecAlignedWordBlock T(aSize+2*bSize+4);
3735
IntegerSecBlock T(aSize+3*(bSize+2));
3727
3736
Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
3728
3737
}
3729
3738
3955
3964
{
3956
3965
assert(m.NotNegative());
3957
3966
3958
if (IsNegative() || *this>=m)
3959
return (*this%m).InverseMod(m);
3967
if (IsNegative())
3968
return Modulo(m).InverseMod(m);
3960
3969
3961
3970
if (m.IsEven())
3962
3971
{
3965
3974
if (*this == One())
3966
3975
return One();
3967
3976
3968
Integer u = m.InverseMod(*this);
3977
Integer u = m.Modulo(*this).InverseMod(*this);
3969
3978
return !u ? Zero() : (m*(*this-u)+1)/(*this);
3970
3979
}
3971
3980
3976
3985
return r;
3977
3986
}
3978
3987
3979
word Integer::InverseMod(const word mod) const
3988
word Integer::InverseMod(word mod) const
3980
3989
{
3981
3990
word g0 = mod, g1 = *this % mod;
3982
3991
word v0 = 0, v1 = 1;
Loggerhead is a web-based interface for Breezy
Version: 2.0.1