« back to all changes in this revision
Viewing changes to integer.cpp
- browse files at revision 463
- compare with another revision
- download diff
- download tarball
- view history from revision 463
- Committer: weidai
- Date: 2010-06-18 01:52:34 UTC
- Revision ID: svn-v4:57ff6487-cd31-0410-9ec3-f628ee90f5f0:trunk/c5:485
avoid SecBlock of arrays
- files added:
- 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
#define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE && CRYPTOPP_BOOL_X86)
42
34
43
35
NAMESPACE_BEGIN(CryptoPP)
44
36
50
42
return true;
51
43
}
52
44
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)
45
inline static int Compare(const word *A, const word *B, size_t N)
114
46
{
115
47
while (N--)
116
48
if (A[N] > B[N])
121
53
return 0;
122
54
}
123
55
124
static int Increment(word *A, size_t N, word B=1)
56
inline static int Increment(word *A, size_t N, word B=1)
125
57
{
126
58
assert(N);
127
59
word t = A[0];
134
66
return 1;
135
67
}
136
68
137
static int Decrement(word *A, size_t N, word B=1)
69
inline static int Decrement(word *A, size_t N, word B=1)
138
70
{
139
71
assert(N);
140
72
word t = A[0];
169
101
170
102
// ********************************************************
171
103
104
#if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE))
105
#define Declare2Words(x) word x##0, x##1;
106
#define AssignWord(a, b) a##0 = b; a##1 = 0;
107
#define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c);
108
#define LowWord(a) a##0
109
#define HighWord(a) a##1
110
#ifdef _MSC_VER
111
#define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1);
112
#ifndef __INTEL_COMPILER
113
#define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2;
114
#endif
115
#elif defined(__DECCXX)
116
#define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b);
117
#elif defined(__x86_64__)
118
#ifdef __SUNPRO_CC
119
// 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
120
#define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc");
121
#else
122
#define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
123
#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");
124
#define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc");
125
#define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc");
126
#define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc");
127
#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");
128
#endif
129
#endif
130
#define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b)
131
#ifndef Double3Words
132
#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;
133
#endif
134
#ifndef Acc2WordsBy2
135
#define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1;
136
#endif
137
#define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);}
138
#define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);}
139
#define GetCarry(u) u##1
140
#define GetBorrow(u) u##1
141
#else
142
#define Declare2Words(x) dword x;
143
#if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER)
144
#define MultiplyWords(p, a, b) p = __emulu(a, b);
145
#else
146
#define MultiplyWords(p, a, b) p = (dword)a*b;
147
#endif
148
#define AssignWord(a, b) a = b;
149
#define Add2WordsBy1(a, b, c) a = b + c;
150
#define Acc2WordsBy2(a, b) a += b;
151
#define LowWord(a) word(a)
152
#define HighWord(a) word(a>>WORD_BITS)
153
#define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2;
154
#define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u);
155
#define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u);
156
#define GetCarry(u) HighWord(u)
157
#define GetBorrow(u) word(u>>(WORD_BITS*2-1))
158
#endif
159
#ifndef MulAcc
160
#define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p));
161
#endif
162
#ifndef Acc2WordsBy1
163
#define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b)
164
#endif
165
#ifndef Acc3WordsBy2
166
#define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e));
167
#endif
168
172
169
class DWord
173
170
{
174
171
public:
198
195
DWord r;
199
196
#ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
200
197
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
198
#elif defined(MultiplyWordsLoHi)
199
MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
220
200
#endif
221
201
return r;
222
202
}
378
358
S Q;
379
359
if (S(B1+1) == 0)
380
360
Q = A[2];
381
else
361
else if (B1 > 0)
382
362
Q = D(A[1], A[2]) / S(B1+1);
363
else
364
Q = D(A[0], A[1]) / B0;
383
365
384
366
// now subtract Q*B from A
385
367
D p = D::Multiply(B0, Q);
457
439
458
440
// ********************************************************
459
441
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);
442
// use some tricks to share assembly code between MSVC and GCC
443
#if defined(__GNUC__)
444
#define AddPrologue \
445
int result; \
446
__asm__ __volatile__ \
447
( \
448
".intel_syntax noprefix;"
449
#define AddEpilogue \
450
".att_syntax prefix;" \
451
: "=a" (result)\
452
: "d" (C), "a" (A), "D" (B), "c" (N) \
453
: "%esi", "memory", "cc" \
454
);\
455
return result;
456
#define MulPrologue \
457
__asm__ __volatile__ \
458
( \
459
".intel_syntax noprefix;" \
460
AS1( push ebx) \
461
AS2( mov ebx, edx)
462
#define MulEpilogue \
463
AS1( pop ebx) \
464
".att_syntax prefix;" \
465
: \
466
: "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \
467
: "%esi", "memory", "cc" \
468
);
469
#define SquPrologue MulPrologue
470
#define SquEpilogue \
471
AS1( pop ebx) \
472
".att_syntax prefix;" \
473
: \
474
: "d" (s_maskLow16), "c" (C), "a" (A) \
475
: "%esi", "%edi", "memory", "cc" \
476
);
477
#define TopPrologue MulPrologue
478
#define TopEpilogue \
479
AS1( pop ebx) \
480
".att_syntax prefix;" \
481
: \
482
: "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \
483
: "memory", "cc" \
484
);
485
#else
486
#define AddPrologue \
487
__asm push edi \
488
__asm push esi \
489
__asm mov eax, [esp+12] \
490
__asm mov edi, [esp+16]
491
#define AddEpilogue \
492
__asm pop esi \
493
__asm pop edi \
494
__asm ret 8
495
#if _MSC_VER < 1300
496
#define SaveEBX __asm push ebx
497
#define RestoreEBX __asm pop ebx
498
#else
499
#define SaveEBX
500
#define RestoreEBX
501
#endif
502
#define SquPrologue \
503
AS2( mov eax, A) \
504
AS2( mov ecx, C) \
505
SaveEBX \
506
AS2( lea ebx, s_maskLow16)
507
#define MulPrologue \
508
AS2( mov eax, A) \
509
AS2( mov edi, B) \
510
AS2( mov ecx, C) \
511
SaveEBX \
512
AS2( lea ebx, s_maskLow16)
513
#define TopPrologue \
514
AS2( mov eax, A) \
515
AS2( mov edi, B) \
516
AS2( mov ecx, C) \
517
AS2( mov esi, L) \
518
SaveEBX \
519
AS2( lea ebx, s_maskLow16)
520
#define SquEpilogue RestoreEBX
521
#define MulEpilogue RestoreEBX
522
#define TopEpilogue RestoreEBX
523
#endif
524
525
#ifdef CRYPTOPP_X64_MASM_AVAILABLE
526
extern "C" {
527
int Baseline_Add(size_t N, word *C, const word *A, const word *B);
528
int Baseline_Sub(size_t N, word *C, const word *A, const word *B);
529
}
530
#elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE)
531
int Baseline_Add(size_t N, word *C, const word *A, const word *B)
532
{
533
word result;
534
__asm__ __volatile__
535
(
536
".intel_syntax;"
537
AS1( neg %1)
538
ASJ( jz, 1, f)
539
AS2( mov %0,[%3+8*%1])
540
AS2( add %0,[%4+8*%1])
541
AS2( mov [%2+8*%1],%0)
542
ASL(0)
543
AS2( mov %0,[%3+8*%1+8])
544
AS2( adc %0,[%4+8*%1+8])
545
AS2( mov [%2+8*%1+8],%0)
546
AS2( lea %1,[%1+2])
547
ASJ( jrcxz, 1, f)
548
AS2( mov %0,[%3+8*%1])
549
AS2( adc %0,[%4+8*%1])
550
AS2( mov [%2+8*%1],%0)
551
ASJ( jmp, 0, b)
552
ASL(1)
553
AS2( mov %0, 0)
554
AS2( adc %0, %0)
555
".att_syntax;"
556
: "=&r" (result), "+c" (N)
557
: "r" (C+N), "r" (A+N), "r" (B+N)
558
: "memory", "cc"
559
);
560
return (int)result;
561
}
562
563
int Baseline_Sub(size_t N, word *C, const word *A, const word *B)
564
{
565
word result;
566
__asm__ __volatile__
567
(
568
".intel_syntax;"
569
AS1( neg %1)
570
ASJ( jz, 1, f)
571
AS2( mov %0,[%3+8*%1])
572
AS2( sub %0,[%4+8*%1])
573
AS2( mov [%2+8*%1],%0)
574
ASL(0)
575
AS2( mov %0,[%3+8*%1+8])
576
AS2( sbb %0,[%4+8*%1+8])
577
AS2( mov [%2+8*%1+8],%0)
578
AS2( lea %1,[%1+2])
579
ASJ( jrcxz, 1, f)
580
AS2( mov %0,[%3+8*%1])
581
AS2( sbb %0,[%4+8*%1])
582
AS2( mov [%2+8*%1],%0)
583
ASJ( jmp, 0, b)
584
ASL(1)
585
AS2( mov %0, 0)
586
AS2( adc %0, %0)
587
".att_syntax;"
588
: "=&r" (result), "+c" (N)
589
: "r" (C+N), "r" (A+N), "r" (B+N)
590
: "memory", "cc"
591
);
592
return (int)result;
593
}
594
#elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86
595
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
596
{
597
AddPrologue
598
599
// now: eax = A, edi = B, edx = C, ecx = N
600
AS2( lea eax, [eax+4*ecx])
601
AS2( lea edi, [edi+4*ecx])
602
AS2( lea edx, [edx+4*ecx])
603
604
AS1( neg ecx) // ecx is negative index
605
AS2( test ecx, 2) // this clears carry flag
606
ASJ( jz, 0, f)
607
AS2( sub ecx, 2)
608
ASJ( jmp, 1, f)
609
610
ASL(0)
611
ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero
612
AS2( mov esi,[eax+4*ecx])
613
AS2( adc esi,[edi+4*ecx])
614
AS2( mov [edx+4*ecx],esi)
615
AS2( mov esi,[eax+4*ecx+4])
616
AS2( adc esi,[edi+4*ecx+4])
617
AS2( mov [edx+4*ecx+4],esi)
618
ASL(1)
619
AS2( mov esi,[eax+4*ecx+8])
620
AS2( adc esi,[edi+4*ecx+8])
621
AS2( mov [edx+4*ecx+8],esi)
622
AS2( mov esi,[eax+4*ecx+12])
623
AS2( adc esi,[edi+4*ecx+12])
624
AS2( mov [edx+4*ecx+12],esi)
625
626
AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2
627
ASJ( jmp, 0, b)
628
629
ASL(2)
630
AS2( mov eax, 0)
631
AS1( setc al) // store carry into eax (return result register)
632
633
AddEpilogue
634
}
635
636
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
637
{
638
AddPrologue
639
640
// now: eax = A, edi = B, edx = C, ecx = N
641
AS2( lea eax, [eax+4*ecx])
642
AS2( lea edi, [edi+4*ecx])
643
AS2( lea edx, [edx+4*ecx])
644
645
AS1( neg ecx) // ecx is negative index
646
AS2( test ecx, 2) // this clears carry flag
647
ASJ( jz, 0, f)
648
AS2( sub ecx, 2)
649
ASJ( jmp, 1, f)
650
651
ASL(0)
652
ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero
653
AS2( mov esi,[eax+4*ecx])
654
AS2( sbb esi,[edi+4*ecx])
655
AS2( mov [edx+4*ecx],esi)
656
AS2( mov esi,[eax+4*ecx+4])
657
AS2( sbb esi,[edi+4*ecx+4])
658
AS2( mov [edx+4*ecx+4],esi)
659
ASL(1)
660
AS2( mov esi,[eax+4*ecx+8])
661
AS2( sbb esi,[edi+4*ecx+8])
662
AS2( mov [edx+4*ecx+8],esi)
663
AS2( mov esi,[eax+4*ecx+12])
664
AS2( sbb esi,[edi+4*ecx+12])
665
AS2( mov [edx+4*ecx+12],esi)
666
667
AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2
668
ASJ( jmp, 0, b)
669
670
ASL(2)
671
AS2( mov eax, 0)
672
AS1( setc al) // store carry into eax (return result register)
673
674
AddEpilogue
675
}
676
677
#if CRYPTOPP_INTEGER_SSE2
678
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Add(size_t N, word *C, const word *A, const word *B)
679
{
680
AddPrologue
681
682
// now: eax = A, edi = B, edx = C, ecx = N
683
AS2( lea eax, [eax+4*ecx])
684
AS2( lea edi, [edi+4*ecx])
685
AS2( lea edx, [edx+4*ecx])
686
687
AS1( neg ecx) // ecx is negative index
688
AS2( pxor mm2, mm2)
689
ASJ( jz, 2, f)
690
AS2( test ecx, 2) // this clears carry flag
691
ASJ( jz, 0, f)
692
AS2( sub ecx, 2)
693
ASJ( jmp, 1, f)
694
695
ASL(0)
696
AS2( movd mm0, DWORD PTR [eax+4*ecx])
697
AS2( movd mm1, DWORD PTR [edi+4*ecx])
698
AS2( paddq mm0, mm1)
699
AS2( paddq mm2, mm0)
700
AS2( movd DWORD PTR [edx+4*ecx], mm2)
701
AS2( psrlq mm2, 32)
702
703
AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
704
AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
705
AS2( paddq mm0, mm1)
706
AS2( paddq mm2, mm0)
707
AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
708
AS2( psrlq mm2, 32)
709
710
ASL(1)
711
AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
712
AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
713
AS2( paddq mm0, mm1)
714
AS2( paddq mm2, mm0)
715
AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
716
AS2( psrlq mm2, 32)
717
718
AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
719
AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
720
AS2( paddq mm0, mm1)
721
AS2( paddq mm2, mm0)
722
AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
723
AS2( psrlq mm2, 32)
724
725
AS2( add ecx, 4)
726
ASJ( jnz, 0, b)
727
728
ASL(2)
729
AS2( movd eax, mm2)
730
AS1( emms)
731
732
AddEpilogue
733
}
734
CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Sub(size_t N, word *C, const word *A, const word *B)
735
{
736
AddPrologue
737
738
// now: eax = A, edi = B, edx = C, ecx = N
739
AS2( lea eax, [eax+4*ecx])
740
AS2( lea edi, [edi+4*ecx])
741
AS2( lea edx, [edx+4*ecx])
742
743
AS1( neg ecx) // ecx is negative index
744
AS2( pxor mm2, mm2)
745
ASJ( jz, 2, f)
746
AS2( test ecx, 2) // this clears carry flag
747
ASJ( jz, 0, f)
748
AS2( sub ecx, 2)
749
ASJ( jmp, 1, f)
750
751
ASL(0)
752
AS2( movd mm0, DWORD PTR [eax+4*ecx])
753
AS2( movd mm1, DWORD PTR [edi+4*ecx])
754
AS2( psubq mm0, mm1)
755
AS2( psubq mm0, mm2)
756
AS2( movd DWORD PTR [edx+4*ecx], mm0)
757
AS2( psrlq mm0, 63)
758
759
AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
760
AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
761
AS2( psubq mm2, mm1)
762
AS2( psubq mm2, mm0)
763
AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
764
AS2( psrlq mm2, 63)
765
766
ASL(1)
767
AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
768
AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
769
AS2( psubq mm0, mm1)
770
AS2( psubq mm0, mm2)
771
AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
772
AS2( psrlq mm0, 63)
773
774
AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
775
AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
776
AS2( psubq mm2, mm1)
777
AS2( psubq mm2, mm0)
778
AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
779
AS2( psrlq mm2, 63)
780
781
AS2( add ecx, 4)
782
ASJ( jnz, 0, b)
783
784
ASL(2)
785
AS2( movd eax, mm2)
786
AS1( emms)
787
788
AddEpilogue
789
}
790
#endif // #if CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE
791
#else
792
int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
793
{
794
assert (N%2 == 0);
795
796
Declare2Words(u);
797
AssignWord(u, 0);
798
for (size_t i=0; i<N; i+=2)
799
{
800
AddWithCarry(u, A[i], B[i]);
801
C[i] = LowWord(u);
802
AddWithCarry(u, A[i+1], B[i+1]);
803
C[i+1] = LowWord(u);
804
}
805
return int(GetCarry(u));
806
}
807
808
int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
809
{
810
assert (N%2 == 0);
811
812
Declare2Words(u);
813
AssignWord(u, 0);
814
for (size_t i=0; i<N; i+=2)
815
{
816
SubtractWithBorrow(u, A[i], B[i]);
817
C[i] = LowWord(u);
818
SubtractWithBorrow(u, A[i+1], B[i+1]);
819
C[i+1] = LowWord(u);
820
}
821
return int(GetBorrow(u));
822
}
823
#endif
824
825
static word LinearMultiply(word *C, const word *A, word B, size_t N)
826
{
827
word carry=0;
828
for(unsigned i=0; i<N; i++)
829
{
830
Declare2Words(p);
831
MultiplyWords(p, A[i], B);
832
Acc2WordsBy1(p, carry);
833
C[i] = LowWord(p);
834
carry = HighWord(p);
835
}
836
return carry;
837
}
838
839
#ifndef CRYPTOPP_DOXYGEN_PROCESSING
840
841
#define Mul_2 \
842
Mul_Begin(2) \
843
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
844
Mul_End(1, 1)
845
846
#define Mul_4 \
847
Mul_Begin(4) \
848
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
849
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
850
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
851
Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
852
Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \
853
Mul_End(5, 3)
854
855
#define Mul_8 \
856
Mul_Begin(8) \
857
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
858
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
859
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
860
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
861
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) \
862
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) \
863
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) \
864
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) \
865
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) \
866
Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
867
Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
868
Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
869
Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \
870
Mul_End(13, 7)
871
872
#define Mul_16 \
873
Mul_Begin(16) \
874
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
875
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
876
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
877
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
878
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) \
879
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) \
880
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) \
881
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) \
882
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) \
883
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) \
884
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) \
885
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) \
886
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) \
887
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) \
888
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) \
889
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) \
890
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) \
891
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) \
892
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) \
893
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) \
894
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) \
895
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) \
896
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) \
897
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) \
898
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) \
899
Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
900
Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
901
Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
902
Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \
903
Mul_End(29, 15)
904
905
#define Squ_2 \
906
Squ_Begin(2) \
907
Squ_End(2)
908
909
#define Squ_4 \
910
Squ_Begin(4) \
911
Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
912
Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
913
Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \
914
Squ_SaveAcc(4, 2, 3) Squ_NonDiag \
915
Squ_End(4)
916
917
#define Squ_8 \
918
Squ_Begin(8) \
919
Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
920
Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
921
Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
922
Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
923
Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
924
Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
925
Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
926
Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
927
Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
928
Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \
929
Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \
930
Squ_SaveAcc(12, 6, 7) Squ_NonDiag \
931
Squ_End(8)
932
933
#define Squ_16 \
934
Squ_Begin(16) \
935
Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
936
Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
937
Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
938
Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
939
Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
940
Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
941
Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
942
Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
943
Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
944
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 \
945
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) \
946
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 \
947
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) \
948
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 \
949
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) \
950
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 \
951
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) \
952
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 \
953
Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \
954
Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \
955
Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \
956
Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \
957
Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \
958
Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \
959
Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \
960
Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \
961
Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \
962
Squ_SaveAcc(28, 14, 15) Squ_NonDiag \
963
Squ_End(16)
964
965
#define Bot_2 \
966
Mul_Begin(2) \
967
Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \
968
Bot_End(2)
969
970
#define Bot_4 \
971
Mul_Begin(4) \
972
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
973
Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \
974
Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \
975
Bot_End(4)
976
977
#define Bot_8 \
978
Mul_Begin(8) \
979
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
980
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
981
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
982
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
983
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) \
984
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) \
985
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) \
986
Bot_End(8)
987
988
#define Bot_16 \
989
Mul_Begin(16) \
990
Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
991
Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
992
Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
993
Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
994
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) \
995
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) \
996
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) \
997
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) \
998
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) \
999
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) \
1000
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) \
1001
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) \
1002
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) \
1003
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) \
1004
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) \
1005
Bot_End(16)
1006
1007
#endif
1008
1009
#if 0
1010
#define Mul_Begin(n) \
1011
Declare2Words(p) \
1012
Declare2Words(c) \
1013
Declare2Words(d) \
1014
MultiplyWords(p, A[0], B[0]) \
1015
AssignWord(c, LowWord(p)) \
1016
AssignWord(d, HighWord(p))
1017
1018
#define Mul_Acc(i, j) \
1019
MultiplyWords(p, A[i], B[j]) \
1020
Acc2WordsBy1(c, LowWord(p)) \
1021
Acc2WordsBy1(d, HighWord(p))
1022
1023
#define Mul_SaveAcc(k, i, j) \
1024
R[k] = LowWord(c); \
1025
Add2WordsBy1(c, d, HighWord(c)) \
1026
MultiplyWords(p, A[i], B[j]) \
1027
AssignWord(d, HighWord(p)) \
1028
Acc2WordsBy1(c, LowWord(p))
1029
1030
#define Mul_End(n) \
1031
R[2*n-3] = LowWord(c); \
1032
Acc2WordsBy1(d, HighWord(c)) \
1033
MultiplyWords(p, A[n-1], B[n-1])\
1034
Acc2WordsBy2(d, p) \
1035
R[2*n-2] = LowWord(d); \
1036
R[2*n-1] = HighWord(d);
1037
1038
#define Bot_SaveAcc(k, i, j) \
1039
R[k] = LowWord(c); \
1040
word e = LowWord(d) + HighWord(c); \
1041
e += A[i] * B[j];
1042
1043
#define Bot_Acc(i, j) \
1044
e += A[i] * B[j];
1045
1046
#define Bot_End(n) \
1047
R[n-1] = e;
1048
#else
1049
#define Mul_Begin(n) \
1050
Declare2Words(p) \
1051
word c; \
1052
Declare2Words(d) \
1053
MultiplyWords(p, A[0], B[0]) \
1054
c = LowWord(p); \
1055
AssignWord(d, HighWord(p))
1056
1057
#define Mul_Acc(i, j) \
1058
MulAcc(c, d, A[i], B[j])
1059
1060
#define Mul_SaveAcc(k, i, j) \
1061
R[k] = c; \
1062
c = LowWord(d); \
1063
AssignWord(d, HighWord(d)) \
1064
MulAcc(c, d, A[i], B[j])
1065
1066
#define Mul_End(k, i) \
1067
R[k] = c; \
1068
MultiplyWords(p, A[i], B[i]) \
1069
Acc2WordsBy2(p, d) \
1070
R[k+1] = LowWord(p); \
1071
R[k+2] = HighWord(p);
1072
1073
#define Bot_SaveAcc(k, i, j) \
1074
R[k] = c; \
1075
c = LowWord(d); \
1076
c += A[i] * B[j];
1077
1078
#define Bot_Acc(i, j) \
1079
c += A[i] * B[j];
1080
1081
#define Bot_End(n) \
1082
R[n-1] = c;
1083
#endif
1084
1085
#define Squ_Begin(n) \
1086
Declare2Words(p) \
1087
word c; \
1088
Declare2Words(d) \
1089
Declare2Words(e) \
1090
MultiplyWords(p, A[0], A[0]) \
1091
R[0] = LowWord(p); \
1092
AssignWord(e, HighWord(p)) \
1093
MultiplyWords(p, A[0], A[1]) \
1094
c = LowWord(p); \
1095
AssignWord(d, HighWord(p)) \
1096
Squ_NonDiag \
1097
1098
#define Squ_NonDiag \
1099
Double3Words(c, d)
1100
1101
#define Squ_SaveAcc(k, i, j) \
1102
Acc3WordsBy2(c, d, e) \
1103
R[k] = c; \
1104
MultiplyWords(p, A[i], A[j]) \
1105
c = LowWord(p); \
1106
AssignWord(d, HighWord(p)) \
1107
1108
#define Squ_Acc(i, j) \
1109
MulAcc(c, d, A[i], A[j])
1110
1111
#define Squ_Diag(i) \
1112
Squ_NonDiag \
1113
MulAcc(c, d, A[i], A[i])
1114
1115
#define Squ_End(n) \
1116
Acc3WordsBy2(c, d, e) \
1117
R[2*n-3] = c; \
1118
MultiplyWords(p, A[n-1], A[n-1])\
1119
Acc2WordsBy2(p, e) \
1120
R[2*n-2] = LowWord(p); \
1121
R[2*n-1] = HighWord(p);
1122
1123
void Baseline_Multiply2(word *R, const word *A, const word *B)
1124
{
1125
Mul_2
1126
}
1127
1128
void Baseline_Multiply4(word *R, const word *A, const word *B)
1129
{
1130
Mul_4
1131
}
1132
1133
void Baseline_Multiply8(word *R, const word *A, const word *B)
1134
{
1135
Mul_8
1136
}
1137
1138
void Baseline_Square2(word *R, const word *A)
1139
{
1140
Squ_2
1141
}
1142
1143
void Baseline_Square4(word *R, const word *A)
1144
{
1145
Squ_4
1146
}
1147
1148
void Baseline_Square8(word *R, const word *A)
1149
{
1150
Squ_8
1151
}
1152
1153
void Baseline_MultiplyBottom2(word *R, const word *A, const word *B)
1154
{
1155
Bot_2
1156
}
1157
1158
void Baseline_MultiplyBottom4(word *R, const word *A, const word *B)
1159
{
1160
Bot_4
1161
}
1162
1163
void Baseline_MultiplyBottom8(word *R, const word *A, const word *B)
1164
{
1165
Bot_8
1166
}
1167
1168
#define Top_Begin(n) \
1169
Declare2Words(p) \
1170
word c; \
1171
Declare2Words(d) \
1172
MultiplyWords(p, A[0], B[n-2]);\
1173
AssignWord(d, HighWord(p));
1174
1175
#define Top_Acc(i, j) \
1176
MultiplyWords(p, A[i], B[j]);\
1177
Acc2WordsBy1(d, HighWord(p));
1178
1179
#define Top_SaveAcc0(i, j) \
1180
c = LowWord(d); \
1181
AssignWord(d, HighWord(d)) \
1182
MulAcc(c, d, A[i], B[j])
1183
1184
#define Top_SaveAcc1(i, j) \
1185
c = L<c; \
1186
Acc2WordsBy1(d, c); \
1187
c = LowWord(d); \
1188
AssignWord(d, HighWord(d)) \
1189
MulAcc(c, d, A[i], B[j])
1190
1191
void Baseline_MultiplyTop2(word *R, const word *A, const word *B, word L)
1192
{
1193
word T[4];
1194
Baseline_Multiply2(T, A, B);
1195
R[0] = T[2];
1196
R[1] = T[3];
1197
}
1198
1199
void Baseline_MultiplyTop4(word *R, const word *A, const word *B, word L)
1200
{
1201
Top_Begin(4)
1202
Top_Acc(1, 1) Top_Acc(2, 0) \
1203
Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1204
Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1205
Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1206
Mul_End(1, 3)
1207
}
1208
1209
void Baseline_MultiplyTop8(word *R, const word *A, const word *B, word L)
1210
{
1211
Top_Begin(8)
1212
Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1213
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) \
1214
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) \
1215
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) \
1216
Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1217
Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1218
Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1219
Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1220
Mul_End(5, 7)
1221
}
1222
1223
#if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available
1224
void Baseline_Multiply16(word *R, const word *A, const word *B)
1225
{
1226
Mul_16
1227
}
1228
1229
void Baseline_Square16(word *R, const word *A)
1230
{
1231
Squ_16
1232
}
1233
1234
void Baseline_MultiplyBottom16(word *R, const word *A, const word *B)
1235
{
1236
Bot_16
1237
}
1238
1239
void Baseline_MultiplyTop16(word *R, const word *A, const word *B, word L)
1240
{
1241
Top_Begin(16)
1242
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) \
1243
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) \
1244
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) \
1245
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) \
1246
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) \
1247
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) \
1248
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) \
1249
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) \
1250
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) \
1251
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) \
1252
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) \
1253
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) \
1254
Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1255
Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1256
Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1257
Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1258
Mul_End(13, 15)
1259
}
1260
#endif
1261
1262
// ********************************************************
1263
1264
#if CRYPTOPP_INTEGER_SSE2
1265
1266
CRYPTOPP_ALIGN_DATA(16) static const word32 s_maskLow16[4] CRYPTOPP_SECTION_ALIGN16 = {0xffff,0xffff,0xffff,0xffff};
1267
1268
#undef Mul_Begin
1269
#undef Mul_Acc
1270
#undef Top_Begin
1271
#undef Top_Acc
1272
#undef Squ_Acc
1273
#undef Squ_NonDiag
1274
#undef Squ_Diag
1275
#undef Squ_SaveAcc
1276
#undef Squ_Begin
1277
#undef Mul_SaveAcc
1278
#undef Bot_Acc
1279
#undef Bot_SaveAcc
1280
#undef Bot_End
1281
#undef Squ_End
1282
#undef Mul_End
1283
1284
#define SSE2_FinalSave(k) \
1285
AS2( psllq xmm5, 16) \
1286
AS2( paddq xmm4, xmm5) \
1287
AS2( movq QWORD PTR [ecx+8*(k)], xmm4)
1288
1289
#define SSE2_SaveShift(k) \
1290
AS2( movq xmm0, xmm6) \
1291
AS2( punpckhqdq xmm6, xmm0) \
1292
AS2( movq xmm1, xmm7) \
1293
AS2( punpckhqdq xmm7, xmm1) \
1294
AS2( paddd xmm6, xmm0) \
1295
AS2( pslldq xmm6, 4) \
1296
AS2( paddd xmm7, xmm1) \
1297
AS2( paddd xmm4, xmm6) \
1298
AS2( pslldq xmm7, 4) \
1299
AS2( movq xmm6, xmm4) \
1300
AS2( paddd xmm5, xmm7) \
1301
AS2( movq xmm7, xmm5) \
1302
AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1303
AS2( psrlq xmm6, 16) \
1304
AS2( paddq xmm6, xmm7) \
1305
AS2( punpckhqdq xmm4, xmm0) \
1306
AS2( punpckhqdq xmm5, xmm0) \
1307
AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \
1308
AS2( psrlq xmm6, 3*16) \
1309
AS2( paddd xmm4, xmm6) \
1310
1311
#define Squ_SSE2_SaveShift(k) \
1312
AS2( movq xmm0, xmm6) \
1313
AS2( punpckhqdq xmm6, xmm0) \
1314
AS2( movq xmm1, xmm7) \
1315
AS2( punpckhqdq xmm7, xmm1) \
1316
AS2( paddd xmm6, xmm0) \
1317
AS2( pslldq xmm6, 4) \
1318
AS2( paddd xmm7, xmm1) \
1319
AS2( paddd xmm4, xmm6) \
1320
AS2( pslldq xmm7, 4) \
1321
AS2( movhlps xmm6, xmm4) \
1322
AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1323
AS2( paddd xmm5, xmm7) \
1324
AS2( movhps QWORD PTR [esp+12], xmm5)\
1325
AS2( psrlq xmm4, 16) \
1326
AS2( paddq xmm4, xmm5) \
1327
AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \
1328
AS2( psrlq xmm4, 3*16) \
1329
AS2( paddd xmm4, xmm6) \
1330
AS2( movq QWORD PTR [esp+4], xmm4)\
1331
1332
#define SSE2_FirstMultiply(i) \
1333
AS2( movdqa xmm7, [esi+(i)*16])\
1334
AS2( movdqa xmm5, [edi-(i)*16])\
1335
AS2( pmuludq xmm5, xmm7) \
1336
AS2( movdqa xmm4, [ebx])\
1337
AS2( movdqa xmm6, xmm4) \
1338
AS2( pand xmm4, xmm5) \
1339
AS2( psrld xmm5, 16) \
1340
AS2( pmuludq xmm7, [edx-(i)*16])\
1341
AS2( pand xmm6, xmm7) \
1342
AS2( psrld xmm7, 16)
1343
1344
#define Squ_Begin(n) \
1345
SquPrologue \
1346
AS2( mov esi, esp)\
1347
AS2( and esp, 0xfffffff0)\
1348
AS2( lea edi, [esp-32*n])\
1349
AS2( sub esp, 32*n+16)\
1350
AS1( push esi)\
1351
AS2( mov esi, edi) \
1352
AS2( xor edx, edx) \
1353
ASL(1) \
1354
ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1355
ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1356
AS2( movdqa [edi+2*edx], xmm0) \
1357
AS2( psrlq xmm0, 32) \
1358
AS2( movdqa [edi+2*edx+16], xmm0) \
1359
AS2( movdqa [edi+16*n+2*edx], xmm1) \
1360
AS2( psrlq xmm1, 32) \
1361
AS2( movdqa [edi+16*n+2*edx+16], xmm1) \
1362
AS2( add edx, 16) \
1363
AS2( cmp edx, 8*(n)) \
1364
ASJ( jne, 1, b) \
1365
AS2( lea edx, [edi+16*n])\
1366
SSE2_FirstMultiply(0) \
1367
1368
#define Squ_Acc(i) \
1369
ASL(LSqu##i) \
1370
AS2( movdqa xmm1, [esi+(i)*16]) \
1371
AS2( movdqa xmm0, [edi-(i)*16]) \
1372
AS2( movdqa xmm2, [ebx]) \
1373
AS2( pmuludq xmm0, xmm1) \
1374
AS2( pmuludq xmm1, [edx-(i)*16]) \
1375
AS2( movdqa xmm3, xmm2) \
1376
AS2( pand xmm2, xmm0) \
1377
AS2( psrld xmm0, 16) \
1378
AS2( paddd xmm4, xmm2) \
1379
AS2( paddd xmm5, xmm0) \
1380
AS2( pand xmm3, xmm1) \
1381
AS2( psrld xmm1, 16) \
1382
AS2( paddd xmm6, xmm3) \
1383
AS2( paddd xmm7, xmm1) \
1384
1385
#define Squ_Acc1(i)
1386
#define Squ_Acc2(i) ASC(call, LSqu##i)
1387
#define Squ_Acc3(i) Squ_Acc2(i)
1388
#define Squ_Acc4(i) Squ_Acc2(i)
1389
#define Squ_Acc5(i) Squ_Acc2(i)
1390
#define Squ_Acc6(i) Squ_Acc2(i)
1391
#define Squ_Acc7(i) Squ_Acc2(i)
1392
#define Squ_Acc8(i) Squ_Acc2(i)
1393
1394
#define SSE2_End(E, n) \
1395
SSE2_SaveShift(2*(n)-3) \
1396
AS2( movdqa xmm7, [esi+16]) \
1397
AS2( movdqa xmm0, [edi]) \
1398
AS2( pmuludq xmm0, xmm7) \
1399
AS2( movdqa xmm2, [ebx]) \
1400
AS2( pmuludq xmm7, [edx]) \
1401
AS2( movdqa xmm6, xmm2) \
1402
AS2( pand xmm2, xmm0) \
1403
AS2( psrld xmm0, 16) \
1404
AS2( paddd xmm4, xmm2) \
1405
AS2( paddd xmm5, xmm0) \
1406
AS2( pand xmm6, xmm7) \
1407
AS2( psrld xmm7, 16) \
1408
SSE2_SaveShift(2*(n)-2) \
1409
SSE2_FinalSave(2*(n)-1) \
1410
AS1( pop esp)\
1411
E
1412
1413
#define Squ_End(n) SSE2_End(SquEpilogue, n)
1414
#define Mul_End(n) SSE2_End(MulEpilogue, n)
1415
#define Top_End(n) SSE2_End(TopEpilogue, n)
1416
1417
#define Squ_Column1(k, i) \
1418
Squ_SSE2_SaveShift(k) \
1419
AS2( add esi, 16) \
1420
SSE2_FirstMultiply(1)\
1421
Squ_Acc##i(i) \
1422
AS2( paddd xmm4, xmm4) \
1423
AS2( paddd xmm5, xmm5) \
1424
AS2( movdqa xmm3, [esi]) \
1425
AS2( movq xmm1, QWORD PTR [esi+8]) \
1426
AS2( pmuludq xmm1, xmm3) \
1427
AS2( pmuludq xmm3, xmm3) \
1428
AS2( movdqa xmm0, [ebx])\
1429
AS2( movdqa xmm2, xmm0) \
1430
AS2( pand xmm0, xmm1) \
1431
AS2( psrld xmm1, 16) \
1432
AS2( paddd xmm6, xmm0) \
1433
AS2( paddd xmm7, xmm1) \
1434
AS2( pand xmm2, xmm3) \
1435
AS2( psrld xmm3, 16) \
1436
AS2( paddd xmm6, xmm6) \
1437
AS2( paddd xmm7, xmm7) \
1438
AS2( paddd xmm4, xmm2) \
1439
AS2( paddd xmm5, xmm3) \
1440
AS2( movq xmm0, QWORD PTR [esp+4])\
1441
AS2( movq xmm1, QWORD PTR [esp+12])\
1442
AS2( paddd xmm4, xmm0)\
1443
AS2( paddd xmm5, xmm1)\
1444
1445
#define Squ_Column0(k, i) \
1446
Squ_SSE2_SaveShift(k) \
1447
AS2( add edi, 16) \
1448
AS2( add edx, 16) \
1449
SSE2_FirstMultiply(1)\
1450
Squ_Acc##i(i) \
1451
AS2( paddd xmm6, xmm6) \
1452
AS2( paddd xmm7, xmm7) \
1453
AS2( paddd xmm4, xmm4) \
1454
AS2( paddd xmm5, xmm5) \
1455
AS2( movq xmm0, QWORD PTR [esp+4])\
1456
AS2( movq xmm1, QWORD PTR [esp+12])\
1457
AS2( paddd xmm4, xmm0)\
1458
AS2( paddd xmm5, xmm1)\
1459
1460
#define SSE2_MulAdd45 \
1461
AS2( movdqa xmm7, [esi]) \
1462
AS2( movdqa xmm0, [edi]) \
1463
AS2( pmuludq xmm0, xmm7) \
1464
AS2( movdqa xmm2, [ebx]) \
1465
AS2( pmuludq xmm7, [edx]) \
1466
AS2( movdqa xmm6, xmm2) \
1467
AS2( pand xmm2, xmm0) \
1468
AS2( psrld xmm0, 16) \
1469
AS2( paddd xmm4, xmm2) \
1470
AS2( paddd xmm5, xmm0) \
1471
AS2( pand xmm6, xmm7) \
1472
AS2( psrld xmm7, 16)
1473
1474
#define Mul_Begin(n) \
1475
MulPrologue \
1476
AS2( mov esi, esp)\
1477
AS2( and esp, 0xfffffff0)\
1478
AS2( sub esp, 48*n+16)\
1479
AS1( push esi)\
1480
AS2( xor edx, edx) \
1481
ASL(1) \
1482
ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1483
ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1484
ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1485
AS2( movdqa [esp+20+2*edx], xmm0) \
1486
AS2( psrlq xmm0, 32) \
1487
AS2( movdqa [esp+20+2*edx+16], xmm0) \
1488
AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1489
AS2( psrlq xmm1, 32) \
1490
AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1491
AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1492
AS2( psrlq xmm2, 32) \
1493
AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1494
AS2( add edx, 16) \
1495
AS2( cmp edx, 8*(n)) \
1496
ASJ( jne, 1, b) \
1497
AS2( lea edi, [esp+20])\
1498
AS2( lea edx, [esp+20+16*n])\
1499
AS2( lea esi, [esp+20+32*n])\
1500
SSE2_FirstMultiply(0) \
1501
1502
#define Mul_Acc(i) \
1503
ASL(LMul##i) \
1504
AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1505
AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1506
AS2( movdqa xmm2, [ebx]) \
1507
AS2( pmuludq xmm0, xmm1) \
1508
AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1509
AS2( movdqa xmm3, xmm2) \
1510
AS2( pand xmm2, xmm0) \
1511
AS2( psrld xmm0, 16) \
1512
AS2( paddd xmm4, xmm2) \
1513
AS2( paddd xmm5, xmm0) \
1514
AS2( pand xmm3, xmm1) \
1515
AS2( psrld xmm1, 16) \
1516
AS2( paddd xmm6, xmm3) \
1517
AS2( paddd xmm7, xmm1) \
1518
1519
#define Mul_Acc1(i)
1520
#define Mul_Acc2(i) ASC(call, LMul##i)
1521
#define Mul_Acc3(i) Mul_Acc2(i)
1522
#define Mul_Acc4(i) Mul_Acc2(i)
1523
#define Mul_Acc5(i) Mul_Acc2(i)
1524
#define Mul_Acc6(i) Mul_Acc2(i)
1525
#define Mul_Acc7(i) Mul_Acc2(i)
1526
#define Mul_Acc8(i) Mul_Acc2(i)
1527
#define Mul_Acc9(i) Mul_Acc2(i)
1528
#define Mul_Acc10(i) Mul_Acc2(i)
1529
#define Mul_Acc11(i) Mul_Acc2(i)
1530
#define Mul_Acc12(i) Mul_Acc2(i)
1531
#define Mul_Acc13(i) Mul_Acc2(i)
1532
#define Mul_Acc14(i) Mul_Acc2(i)
1533
#define Mul_Acc15(i) Mul_Acc2(i)
1534
#define Mul_Acc16(i) Mul_Acc2(i)
1535
1536
#define Mul_Column1(k, i) \
1537
SSE2_SaveShift(k) \
1538
AS2( add esi, 16) \
1539
SSE2_MulAdd45\
1540
Mul_Acc##i(i) \
1541
1542
#define Mul_Column0(k, i) \
1543
SSE2_SaveShift(k) \
1544
AS2( add edi, 16) \
1545
AS2( add edx, 16) \
1546
SSE2_MulAdd45\
1547
Mul_Acc##i(i) \
1548
1549
#define Bot_Acc(i) \
1550
AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1551
AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1552
AS2( pmuludq xmm0, xmm1) \
1553
AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1554
AS2( paddq xmm4, xmm0) \
1555
AS2( paddd xmm6, xmm1)
1556
1557
#define Bot_SaveAcc(k) \
1558
SSE2_SaveShift(k) \
1559
AS2( add edi, 16) \
1560
AS2( add edx, 16) \
1561
AS2( movdqa xmm6, [esi]) \
1562
AS2( movdqa xmm0, [edi]) \
1563
AS2( pmuludq xmm0, xmm6) \
1564
AS2( paddq xmm4, xmm0) \
1565
AS2( psllq xmm5, 16) \
1566
AS2( paddq xmm4, xmm5) \
1567
AS2( pmuludq xmm6, [edx])
1568
1569
#define Bot_End(n) \
1570
AS2( movhlps xmm7, xmm6) \
1571
AS2( paddd xmm6, xmm7) \
1572
AS2( psllq xmm6, 32) \
1573
AS2( paddd xmm4, xmm6) \
1574
AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \
1575
AS1( pop esp)\
1576
MulEpilogue
1577
1578
#define Top_Begin(n) \
1579
TopPrologue \
1580
AS2( mov edx, esp)\
1581
AS2( and esp, 0xfffffff0)\
1582
AS2( sub esp, 48*n+16)\
1583
AS1( push edx)\
1584
AS2( xor edx, edx) \
1585
ASL(1) \
1586
ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1587
ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1588
ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1589
AS2( movdqa [esp+20+2*edx], xmm0) \
1590
AS2( psrlq xmm0, 32) \
1591
AS2( movdqa [esp+20+2*edx+16], xmm0) \
1592
AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1593
AS2( psrlq xmm1, 32) \
1594
AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1595
AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1596
AS2( psrlq xmm2, 32) \
1597
AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1598
AS2( add edx, 16) \
1599
AS2( cmp edx, 8*(n)) \
1600
ASJ( jne, 1, b) \
1601
AS2( mov eax, esi) \
1602
AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\
1603
AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\
1604
AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\
1605
AS2( pxor xmm4, xmm4)\
1606
AS2( pxor xmm5, xmm5)
1607
1608
#define Top_Acc(i) \
1609
AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \
1610
AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1611
AS2( psrlq xmm0, 48) \
1612
AS2( paddd xmm5, xmm0)\
1613
1614
#define Top_Column0(i) \
1615
AS2( psllq xmm5, 32) \
1616
AS2( add edi, 16) \
1617
AS2( add edx, 16) \
1618
SSE2_MulAdd45\
1619
Mul_Acc##i(i) \
1620
1621
#define Top_Column1(i) \
1622
SSE2_SaveShift(0) \
1623
AS2( add esi, 16) \
1624
SSE2_MulAdd45\
1625
Mul_Acc##i(i) \
1626
AS2( shr eax, 16) \
1627
AS2( movd xmm0, eax)\
1628
AS2( movd xmm1, [ecx+4])\
1629
AS2( psrld xmm1, 16)\
1630
AS2( pcmpgtd xmm1, xmm0)\
1631
AS2( psrld xmm1, 31)\
1632
AS2( paddd xmm4, xmm1)\
1633
1634
void SSE2_Square4(word *C, const word *A)
1635
{
1636
Squ_Begin(2)
1637
Squ_Column0(0, 1)
1638
Squ_End(2)
1639
}
1640
1641
void SSE2_Square8(word *C, const word *A)
1642
{
1643
Squ_Begin(4)
1644
#ifndef __GNUC__
1645
ASJ( jmp, 0, f)
1646
Squ_Acc(2)
1647
AS1( ret) ASL(0)
1648
#endif
1649
Squ_Column0(0, 1)
1650
Squ_Column1(1, 1)
1651
Squ_Column0(2, 2)
1652
Squ_Column1(3, 1)
1653
Squ_Column0(4, 1)
1654
Squ_End(4)
1655
}
1656
1657
void SSE2_Square16(word *C, const word *A)
1658
{
1659
Squ_Begin(8)
1660
#ifndef __GNUC__
1661
ASJ( jmp, 0, f)
1662
Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1663
AS1( ret) ASL(0)
1664
#endif
1665
Squ_Column0(0, 1)
1666
Squ_Column1(1, 1)
1667
Squ_Column0(2, 2)
1668
Squ_Column1(3, 2)
1669
Squ_Column0(4, 3)
1670
Squ_Column1(5, 3)
1671
Squ_Column0(6, 4)
1672
Squ_Column1(7, 3)
1673
Squ_Column0(8, 3)
1674
Squ_Column1(9, 2)
1675
Squ_Column0(10, 2)
1676
Squ_Column1(11, 1)
1677
Squ_Column0(12, 1)
1678
Squ_End(8)
1679
}
1680
1681
void SSE2_Square32(word *C, const word *A)
1682
{
1683
Squ_Begin(16)
1684
ASJ( jmp, 0, f)
1685
Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1686
AS1( ret) ASL(0)
1687
Squ_Column0(0, 1)
1688
Squ_Column1(1, 1)
1689
Squ_Column0(2, 2)
1690
Squ_Column1(3, 2)
1691
Squ_Column0(4, 3)
1692
Squ_Column1(5, 3)
1693
Squ_Column0(6, 4)
1694
Squ_Column1(7, 4)
1695
Squ_Column0(8, 5)
1696
Squ_Column1(9, 5)
1697
Squ_Column0(10, 6)
1698
Squ_Column1(11, 6)
1699
Squ_Column0(12, 7)
1700
Squ_Column1(13, 7)
1701
Squ_Column0(14, 8)
1702
Squ_Column1(15, 7)
1703
Squ_Column0(16, 7)
1704
Squ_Column1(17, 6)
1705
Squ_Column0(18, 6)
1706
Squ_Column1(19, 5)
1707
Squ_Column0(20, 5)
1708
Squ_Column1(21, 4)
1709
Squ_Column0(22, 4)
1710
Squ_Column1(23, 3)
1711
Squ_Column0(24, 3)
1712
Squ_Column1(25, 2)
1713
Squ_Column0(26, 2)
1714
Squ_Column1(27, 1)
1715
Squ_Column0(28, 1)
1716
Squ_End(16)
1717
}
1718
1719
void SSE2_Multiply4(word *C, const word *A, const word *B)
1720
{
1721
Mul_Begin(2)
1722
#ifndef __GNUC__
1723
ASJ( jmp, 0, f)
1724
Mul_Acc(2)
1725
AS1( ret) ASL(0)
1726
#endif
1727
Mul_Column0(0, 2)
1728
Mul_End(2)
1729
}
1730
1731
void SSE2_Multiply8(word *C, const word *A, const word *B)
1732
{
1733
Mul_Begin(4)
1734
#ifndef __GNUC__
1735
ASJ( jmp, 0, f)
1736
Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1737
AS1( ret) ASL(0)
1738
#endif
1739
Mul_Column0(0, 2)
1740
Mul_Column1(1, 3)
1741
Mul_Column0(2, 4)
1742
Mul_Column1(3, 3)
1743
Mul_Column0(4, 2)
1744
Mul_End(4)
1745
}
1746
1747
void SSE2_Multiply16(word *C, const word *A, const word *B)
1748
{
1749
Mul_Begin(8)
1750
#ifndef __GNUC__
1751
ASJ( jmp, 0, f)
1752
Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1753
AS1( ret) ASL(0)
1754
#endif
1755
Mul_Column0(0, 2)
1756
Mul_Column1(1, 3)
1757
Mul_Column0(2, 4)
1758
Mul_Column1(3, 5)
1759
Mul_Column0(4, 6)
1760
Mul_Column1(5, 7)
1761
Mul_Column0(6, 8)
1762
Mul_Column1(7, 7)
1763
Mul_Column0(8, 6)
1764
Mul_Column1(9, 5)
1765
Mul_Column0(10, 4)
1766
Mul_Column1(11, 3)
1767
Mul_Column0(12, 2)
1768
Mul_End(8)
1769
}
1770
1771
void SSE2_Multiply32(word *C, const word *A, const word *B)
1772
{
1773
Mul_Begin(16)
1774
ASJ( jmp, 0, f)
1775
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)
1776
AS1( ret) ASL(0)
1777
Mul_Column0(0, 2)
1778
Mul_Column1(1, 3)
1779
Mul_Column0(2, 4)
1780
Mul_Column1(3, 5)
1781
Mul_Column0(4, 6)
1782
Mul_Column1(5, 7)
1783
Mul_Column0(6, 8)
1784
Mul_Column1(7, 9)
1785
Mul_Column0(8, 10)
1786
Mul_Column1(9, 11)
1787
Mul_Column0(10, 12)
1788
Mul_Column1(11, 13)
1789
Mul_Column0(12, 14)
1790
Mul_Column1(13, 15)
1791
Mul_Column0(14, 16)
1792
Mul_Column1(15, 15)
1793
Mul_Column0(16, 14)
1794
Mul_Column1(17, 13)
1795
Mul_Column0(18, 12)
1796
Mul_Column1(19, 11)
1797
Mul_Column0(20, 10)
1798
Mul_Column1(21, 9)
1799
Mul_Column0(22, 8)
1800
Mul_Column1(23, 7)
1801
Mul_Column0(24, 6)
1802
Mul_Column1(25, 5)
1803
Mul_Column0(26, 4)
1804
Mul_Column1(27, 3)
1805
Mul_Column0(28, 2)
1806
Mul_End(16)
1807
}
1808
1809
void SSE2_MultiplyBottom4(word *C, const word *A, const word *B)
1810
{
1811
Mul_Begin(2)
1812
Bot_SaveAcc(0) Bot_Acc(2)
1813
Bot_End(2)
1814
}
1815
1816
void SSE2_MultiplyBottom8(word *C, const word *A, const word *B)
1817
{
1818
Mul_Begin(4)
1819
#ifndef __GNUC__
1820
ASJ( jmp, 0, f)
1821
Mul_Acc(3) Mul_Acc(2)
1822
AS1( ret) ASL(0)
1823
#endif
1824
Mul_Column0(0, 2)
1825
Mul_Column1(1, 3)
1826
Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1827
Bot_End(4)
1828
}
1829
1830
void SSE2_MultiplyBottom16(word *C, const word *A, const word *B)
1831
{
1832
Mul_Begin(8)
1833
#ifndef __GNUC__
1834
ASJ( jmp, 0, f)
1835
Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1836
AS1( ret) ASL(0)
1837
#endif
1838
Mul_Column0(0, 2)
1839
Mul_Column1(1, 3)
1840
Mul_Column0(2, 4)
1841
Mul_Column1(3, 5)
1842
Mul_Column0(4, 6)
1843
Mul_Column1(5, 7)
1844
Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1845
Bot_End(8)
1846
}
1847
1848
void SSE2_MultiplyBottom32(word *C, const word *A, const word *B)
1849
{
1850
Mul_Begin(16)
1851
#ifndef __GNUC__
1852
ASJ( jmp, 0, f)
1853
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)
1854
AS1( ret) ASL(0)
1855
#endif
1856
Mul_Column0(0, 2)
1857
Mul_Column1(1, 3)
1858
Mul_Column0(2, 4)
1859
Mul_Column1(3, 5)
1860
Mul_Column0(4, 6)
1861
Mul_Column1(5, 7)
1862
Mul_Column0(6, 8)
1863
Mul_Column1(7, 9)
1864
Mul_Column0(8, 10)
1865
Mul_Column1(9, 11)
1866
Mul_Column0(10, 12)
1867
Mul_Column1(11, 13)
1868
Mul_Column0(12, 14)
1869
Mul_Column1(13, 15)
1870
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)
1871
Bot_End(16)
1872
}
1873
1874
void SSE2_MultiplyTop8(word *C, const word *A, const word *B, word L)
1875
{
1876
Top_Begin(4)
1877
Top_Acc(3) Top_Acc(2) Top_Acc(1)
1878
#ifndef __GNUC__
1879
ASJ( jmp, 0, f)
1880
Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1881
AS1( ret) ASL(0)
1882
#endif
1883
Top_Column0(4)
1884
Top_Column1(3)
1885
Mul_Column0(0, 2)
1886
Top_End(2)
1887
}
1888
1889
void SSE2_MultiplyTop16(word *C, const word *A, const word *B, word L)
1890
{
1891
Top_Begin(8)
1892
Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1893
#ifndef __GNUC__
1894
ASJ( jmp, 0, f)
1895
Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1896
AS1( ret) ASL(0)
1897
#endif
1898
Top_Column0(8)
1899
Top_Column1(7)
1900
Mul_Column0(0, 6)
1901
Mul_Column1(1, 5)
1902
Mul_Column0(2, 4)
1903
Mul_Column1(3, 3)
1904
Mul_Column0(4, 2)
1905
Top_End(4)
1906
}
1907
1908
void SSE2_MultiplyTop32(word *C, const word *A, const word *B, word L)
1909
{
1910
Top_Begin(16)
1911
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)
1912
#ifndef __GNUC__
1913
ASJ( jmp, 0, f)
1914
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)
1915
AS1( ret) ASL(0)
1916
#endif
1917
Top_Column0(16)
1918
Top_Column1(15)
1919
Mul_Column0(0, 14)
1920
Mul_Column1(1, 13)
1921
Mul_Column0(2, 12)
1922
Mul_Column1(3, 11)
1923
Mul_Column0(4, 10)
1924
Mul_Column1(5, 9)
1925
Mul_Column0(6, 8)
1926
Mul_Column1(7, 7)
1927
Mul_Column0(8, 6)
1928
Mul_Column1(9, 5)
1929
Mul_Column0(10, 4)
1930
Mul_Column1(11, 3)
1931
Mul_Column0(12, 2)
1932
Top_End(8)
1933
}
1934
1935
#endif // #if CRYPTOPP_INTEGER_SSE2
1936
1937
// ********************************************************
1938
1939
typedef int (CRYPTOPP_FASTCALL * PAdd)(size_t N, word *C, const word *A, const word *B);
1012
1940
typedef void (* PMul)(word *C, const word *A, const word *B);
1941
typedef void (* PSqu)(word *C, const word *A);
1942
typedef void (* PMulTop)(word *C, const word *A, const word *B, word L);
1013
1943
1014
static PAddSub s_pAdd, s_pSub;
1015
#ifdef SSE2_INTRINSICS_AVAILABLE
1016
static PMul s_pMul4, s_pMul8, s_pMul8B;
1944
#if CRYPTOPP_INTEGER_SSE2
1945
static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
1946
static size_t s_recursionLimit = 8;
1947
#else
1948
static const size_t s_recursionLimit = 16;
1017
1949
#endif
1018
1950
1019
static void SetPentiumFunctionPointers()
1951
static PMul s_pMul[9], s_pBot[9];
1952
static PSqu s_pSqu[9];
1953
static PMulTop s_pTop[9];
1954
1955
static void SetFunctionPointers()
1020
1956
{
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
}
1957
s_pMul[0] = &Baseline_Multiply2;
1958
s_pBot[0] = &Baseline_MultiplyBottom2;
1959
s_pSqu[0] = &Baseline_Square2;
1960
s_pTop[0] = &Baseline_MultiplyTop2;
1961
s_pTop[1] = &Baseline_MultiplyTop4;
1031
1962
1032
#ifdef SSE2_INTRINSICS_AVAILABLE
1963
#if CRYPTOPP_INTEGER_SSE2
1033
1964
if (HasSSE2())
1034
1965
{
1035
s_pMul4 = &P4Optimized::Multiply4;
1036
s_pMul8 = &P4Optimized::Multiply8;
1037
s_pMul8B = &P4Optimized::Multiply8Bottom;
1966
#if _MSC_VER != 1200 || defined(NDEBUG)
1967
if (IsP4())
1968
{
1969
s_pAdd = &SSE2_Add;
1970
s_pSub = &SSE2_Sub;
1971
}
1972
#endif
1973
1974
s_recursionLimit = 32;
1975
1976
s_pMul[1] = &SSE2_Multiply4;
1977
s_pMul[2] = &SSE2_Multiply8;
1978
s_pMul[4] = &SSE2_Multiply16;
1979
s_pMul[8] = &SSE2_Multiply32;
1980
1981
s_pBot[1] = &SSE2_MultiplyBottom4;
1982
s_pBot[2] = &SSE2_MultiplyBottom8;
1983
s_pBot[4] = &SSE2_MultiplyBottom16;
1984
s_pBot[8] = &SSE2_MultiplyBottom32;
1985
1986
s_pSqu[1] = &SSE2_Square4;
1987
s_pSqu[2] = &SSE2_Square8;
1988
s_pSqu[4] = &SSE2_Square16;
1989
s_pSqu[8] = &SSE2_Square32;
1990
1991
s_pTop[2] = &SSE2_MultiplyTop8;
1992
s_pTop[4] = &SSE2_MultiplyTop16;
1993
s_pTop[8] = &SSE2_MultiplyTop32;
1038
1994
}
1039
1995
else
1996
#endif
1040
1997
{
1041
s_pMul4 = &PentiumOptimized::Multiply4;
1042
s_pMul8 = &PentiumOptimized::Multiply8;
1043
s_pMul8B = &PentiumOptimized::Multiply8Bottom;
1998
s_pMul[1] = &Baseline_Multiply4;
1999
s_pMul[2] = &Baseline_Multiply8;
2000
2001
s_pBot[1] = &Baseline_MultiplyBottom4;
2002
s_pBot[2] = &Baseline_MultiplyBottom8;
2003
2004
s_pSqu[1] = &Baseline_Square4;
2005
s_pSqu[2] = &Baseline_Square8;
2006
2007
s_pTop[2] = &Baseline_MultiplyTop8;
2008
2009
#if !CRYPTOPP_INTEGER_SSE2
2010
s_pMul[4] = &Baseline_Multiply16;
2011
s_pBot[4] = &Baseline_MultiplyBottom16;
2012
s_pSqu[4] = &Baseline_Square16;
2013
s_pTop[4] = &Baseline_MultiplyTop16;
2014
#endif
1044
2015
}
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
2016
}
2017
2018
inline int Add(word *C, const word *A, const word *B, size_t N)
2019
{
2020
#if CRYPTOPP_INTEGER_SSE2
2021
return s_pAdd(N, C, A, B);
2022
#else
2023
return Baseline_Add(N, C, A, B);
2024
#endif
2025
}
2026
2027
inline int Subtract(word *C, const word *A, const word *B, size_t N)
2028
{
2029
#if CRYPTOPP_INTEGER_SSE2
2030
return s_pSub(N, C, A, B);
2031
#else
2032
return Baseline_Sub(N, C, A, B);
2033
#endif
2034
}
1980
2035
1981
2036
// ********************************************************
1982
2037
2038
1983
2039
#define A0 A
1984
2040
#define A1 (A+N2)
1985
2041
#define B0 B
2004
2060
{
2005
2061
assert(N>=2 && N%2==0);
2006
2062
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);
2063
if (N <= s_recursionLimit)
2064
s_pMul[N/4](R, A, B);
2013
2065
else
2014
2066
{
2015
2067
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
2068
2069
size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2070
Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2071
2072
size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2073
Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2074
2075
RecursiveMultiply(R2, T2, A1, B1, N2);
2076
RecursiveMultiply(T0, T2, R0, R1, N2);
2054
2077
RecursiveMultiply(R0, T2, A0, B0, N2);
2055
RecursiveMultiply(R2, T2, A1, B1, N2);
2056
2078
2057
2079
// now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1
2058
2080
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);
2081
int c2 = Add(R2, R2, R1, N2);
2082
int c3 = c2;
2083
c2 += Add(R1, R2, R0, N2);
2084
c3 += Add(R2, R2, R3, N2);
2085
2086
if (AN2 == BN2)
2087
c3 -= Subtract(R1, R1, T0, N);
2088
else
2089
c3 += Add(R1, R1, T0, N);
2090
2091
c3 += Increment(R2, N2, c2);
2092
assert (c3 >= 0 && c3 <= 2);
2093
Increment(R3, N2, c3);
2065
2094
}
2066
2095
}
2067
2096
2072
2101
void RecursiveSquare(word *R, word *T, const word *A, size_t N)
2073
2102
{
2074
2103
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);
2104
2105
if (N <= s_recursionLimit)
2106
s_pSqu[N/4](R, A);
2081
2107
else
2082
2108
{
2083
2109
const size_t N2 = N/2;
2086
2112
RecursiveSquare(R2, T2, A1, N2);
2087
2113
RecursiveMultiply(T0, T2, A0, A1, N2);
2088
2114
2089
int carry = LowLevel::Add(R1, R1, T0, N);
2090
carry += LowLevel::Add(R1, R1, T0, N);
2115
int carry = Add(R1, R1, T0, N);
2116
carry += Add(R1, R1, T0, N);
2091
2117
Increment(R3, N2, carry);
2092
2118
}
2093
2119
}
2094
2120
2095
2121
// R[N] - bottom half of A*B
2096
// T[N] - temporary work space
2122
// T[3*N/2] - temporary work space
2097
2123
// A[N] - multiplier
2098
2124
// B[N] - multiplicant
2099
2125
2100
2126
void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N)
2101
2127
{
2102
2128
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);
2129
2130
if (N <= s_recursionLimit)
2131
s_pBot[N/4](R, A, B);
2109
2132
else
2110
2133
{
2111
2134
const size_t N2 = N/2;
2112
2135
2113
2136
RecursiveMultiply(R, T, A0, B0, N2);
2114
2137
RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2115
LowLevel::Add(R1, R1, T0, N2);
2138
Add(R1, R1, T0, N2);
2116
2139
RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2117
LowLevel::Add(R1, R1, T0, N2);
2140
Add(R1, R1, T0, N2);
2118
2141
}
2119
2142
}
2120
2143
2124
2147
// A[N] --- multiplier
2125
2148
// B[N] --- multiplicant
2126
2149
2127
void RecursiveMultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
2150
void MultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
2128
2151
{
2129
2152
assert(N>=2 && N%2==0);
2130
2153
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
}
2154
if (N <= s_recursionLimit)
2155
s_pTop[N/4](R, A, B, L[N-1]);
2141
2156
else
2142
2157
{
2143
2158
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);
2159
2160
size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2161
Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2162
2163
size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2164
Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2165
2166
RecursiveMultiply(T0, T2, R0, R1, N2);
2167
RecursiveMultiply(R0, T2, A1, B1, N2);
2168
2169
// now T[01] holds (A1-A0)*(B0-B1) = A1*B0+A0*B1-A1*B1-A0*B0, R[01] holds A1*B1
2170
2171
int t, c3;
2172
int c2 = Subtract(T2, L+N2, L, N2);
2173
2174
if (AN2 == BN2)
2175
{
2176
c2 -= Add(T2, T2, T0, N2);
2177
t = (Compare(T2, R0, N2) == -1);
2178
c3 = t - Subtract(T2, T2, T1, N2);
2179
}
2180
else
2181
{
2182
c2 += Subtract(T2, T2, T0, N2);
2183
t = (Compare(T2, R0, N2) == -1);
2184
c3 = t + Add(T2, T2, T1, N2);
2185
}
2186
2187
c2 += t;
2188
if (c2 >= 0)
2189
c3 += Increment(T2, N2, c2);
2190
else
2191
c3 -= Decrement(T2, N2, -c2);
2192
c3 += Add(R0, T2, R1, N2);
2193
2194
assert (c3 >= 0 && c3 <= 2);
2195
Increment(R1, N2, c3);
2198
2196
}
2199
2197
}
2200
2198
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
2199
inline void Multiply(word *R, word *T, const word *A, const word *B, size_t N)
2212
2200
{
2213
2201
RecursiveMultiply(R, T, A, B, N);
2223
2211
RecursiveMultiplyBottom(R, T, A, B, N);
2224
2212
}
2225
2213
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
2214
// R[NA+NB] - result = A*B
2244
2215
// T[NA+NB] - temporary work space
2245
2216
// A[NA] ---- multiplier
2264
2235
}
2265
2236
2266
2237
assert(NB % NA == 0);
2267
assert((NB/NA)%2 == 0); // NB is an even multiple of NA
2268
2238
2269
2239
if (NA==2 && !A[1])
2270
2240
{
2284
2254
}
2285
2255
}
2286
2256
2287
Multiply(R, T, A, B, NA);
2288
CopyWords(T+2*NA, R+NA, NA);
2289
2290
2257
size_t i;
2258
if ((NB/NA)%2 == 0)
2259
{
2260
Multiply(R, T, A, B, NA);
2261
CopyWords(T+2*NA, R+NA, NA);
2291
2262
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);
2263
for (i=2*NA; i<NB; i+=2*NA)
2264
Multiply(T+NA+i, T, A, B+i, NA);
2265
for (i=NA; i<NB; i+=2*NA)
2266
Multiply(R+i, T, A, B+i, NA);
2267
}
2268
else
2269
{
2270
for (i=0; i<NB; i+=2*NA)
2271
Multiply(R+i, T, A, B+i, NA);
2272
for (i=NA; i<NB; i+=2*NA)
2273
Multiply(T+NA+i, T, A, B+i, NA);
2274
}
2296
2275
2297
2276
if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2298
2277
Increment(R+NB, NA);
2308
2287
{
2309
2288
T[0] = AtomicInverseModPower2(A[0]);
2310
2289
T[1] = 0;
2311
LowLevel::Multiply2Bottom(T+2, T, A);
2290
s_pBot[0](T+2, T, A);
2312
2291
TwosComplement(T+2, 2);
2313
2292
Increment(T+2, 2, 2);
2314
LowLevel::Multiply2Bottom(R, T, T+2);
2293
s_pBot[0](R, T, T+2);
2315
2294
}
2316
2295
else
2317
2296
{
2333
2312
// M[N] --- modulus
2334
2313
// U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)
2335
2314
2336
void MontgomeryReduce(word *R, word *T, const word *X, const word *M, const word *U, size_t N)
2315
void MontgomeryReduce(word *R, word *T, word *X, const word *M, const word *U, size_t N)
2337
2316
{
2317
#if 1
2338
2318
MultiplyBottom(R, T, X, U, N);
2339
2319
MultiplyTop(T, T+N, X, R, M, N);
2340
2320
word borrow = Subtract(T, X+N, T, N);
2341
2321
// defend against timing attack by doing this Add even when not needed
2342
2322
word carry = Add(T+N, T, M, N);
2343
assert(carry || !borrow);
2344
CopyWords(R, T + (borrow ? N : 0), N);
2323
assert(carry | !borrow);
2324
CopyWords(R, T + ((0-borrow) & N), N);
2325
#elif 0
2326
const word u = 0-U[0];
2327
Declare2Words(p)
2328
for (size_t i=0; i<N; i++)
2329
{
2330
const word t = u * X[i];
2331
word c = 0;
2332
for (size_t j=0; j<N; j+=2)
2333
{
2334
MultiplyWords(p, t, M[j]);
2335
Acc2WordsBy1(p, X[i+j]);
2336
Acc2WordsBy1(p, c);
2337
X[i+j] = LowWord(p);
2338
c = HighWord(p);
2339
MultiplyWords(p, t, M[j+1]);
2340
Acc2WordsBy1(p, X[i+j+1]);
2341
Acc2WordsBy1(p, c);
2342
X[i+j+1] = LowWord(p);
2343
c = HighWord(p);
2344
}
2345
2346
if (Increment(X+N+i, N-i, c))
2347
while (!Subtract(X+N, X+N, M, N)) {}
2348
}
2349
2350
memcpy(R, X+N, N*WORD_SIZE);
2351
#else
2352
__m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2353
for (size_t i=0; i<N; i++)
2354
{
2355
__m64 t = _mm_cvtsi32_si64(X[i]);
2356
t = _mm_mul_su32(t, u);
2357
__m64 c = _mm_setzero_si64();
2358
for (size_t j=0; j<N; j+=2)
2359
{
2360
p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2361
p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2362
c = _mm_add_si64(c, p);
2363
X[i+j] = _mm_cvtsi64_si32(c);
2364
c = _mm_srli_si64(c, 32);
2365
p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2366
p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2367
c = _mm_add_si64(c, p);
2368
X[i+j+1] = _mm_cvtsi64_si32(c);
2369
c = _mm_srli_si64(c, 32);
2370
}
2371
2372
if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2373
while (!Subtract(X+N, X+N, M, N)) {}
2374
}
2375
2376
memcpy(R, X+N, N*WORD_SIZE);
2377
_mm_empty();
2378
#endif
2345
2379
}
2346
2380
2347
2381
// R[N] --- result = X/(2**(WORD_BITS*N/2)) mod M
2491
2525
// multiply quotient and divisor and add remainder, make sure it equals dividend
2492
2526
assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2493
2527
word P[4];
2494
Portable::Multiply2(P, Q, B);
2528
s_pMul[0](P, Q, B);
2495
2529
Add(P, P, T, 4);
2496
2530
assert(memcmp(P, A, 4*WORD_SIZE)==0);
2497
2531
}
2503
2537
{
2504
2538
assert(N && N%2==0);
2505
2539
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
}
2540
AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2521
2541
2522
2542
word borrow = Subtract(R, R, T, N+2);
2523
2543
assert(!borrow && !R[N+1]);
2532
2552
2533
2553
// R[NB] -------- remainder = A%B
2534
2554
// Q[NA-NB+2] --- quotient = A/B
2535
// T[NA+2*NB+4] - temp work space
2555
// T[NA+3*(NB+2)] - temp work space
2536
2556
// A[NA] -------- dividend
2537
2557
// B[NB] -------- divisor
2538
2558
2726
2746
{
2727
2747
if (!g_pAssignIntToInteger)
2728
2748
{
2729
#ifdef CRYPTOPP_X86ASM_AVAILABLE
2730
SetPentiumFunctionPointers();
2731
#endif
2749
SetFunctionPointers();
2732
2750
g_pAssignIntToInteger = AssignIntToInteger;
2733
2751
}
2734
2752
}
2877
2895
{
2878
2896
if (this != &t)
2879
2897
{
2880
reg.New(RoundupSize(t.WordCount()));
2898
if (reg.size() != t.reg.size() || t.reg[t.reg.size()/2] == 0)
2899
reg.New(RoundupSize(t.WordCount()));
2881
2900
CopyWords(reg, t.reg, reg.size());
2882
2901
sign = t.sign;
2883
2902
}
3231
3250
memcpy(m_counterAndSeed + 4, seed, seedSize);
3232
3251
}
3233
3252
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);
3253
void GenerateBlock(byte *output, size_t size)
3254
{
3255
PutWord(false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3244
3256
++m_counter;
3245
3257
P1363_KDF2<SHA1>::DeriveKey(output, size, m_counterAndSeed, m_counterAndSeed.size(), NULL, 0);
3246
3258
}
3275
3287
3276
3288
member_ptr<KDF2_RNG> kdf2Rng;
3277
3289
ConstByteArrayParameter seed;
3278
if (params.GetValue("Seed", seed))
3290
if (params.GetValue(Name::Seed(), seed))
3279
3291
{
3280
3292
ByteQueue bq;
3281
3293
DERSequenceEncoder seq(bq);
3392
3404
suffix = '.';
3393
3405
}
3394
3406
3395
SecBlock<char> s(a.BitCount() / (BitPrecision(base)-1) + 1);
3396
3407
Integer temp1=a, temp2;
3397
unsigned i=0;
3398
const char vec[]="0123456789ABCDEF";
3399
3408
3400
3409
if (a.IsNegative())
3401
3410
{
3402
3411
out << '-';
3406
3415
if (!a)
3407
3416
out << '0';
3408
3417
3418
static const char upper[]="0123456789ABCDEF";
3419
static const char lower[]="0123456789abcdef";
3420
3421
const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3422
unsigned i=0;
3423
SecBlock<char> s(a.BitCount() / (BitPrecision(base)-1) + 1);
3424
3409
3425
while (!!temp1)
3410
3426
{
3411
3427
word digit;
3412
3428
Integer::Divide(digit, temp2, temp1, base);
3413
3429
s[i++]=vec[digit];
3414
temp1=temp2;
3430
temp1.swap(temp2);
3415
3431
}
3416
3432
3417
3433
while (i--)
3657
3673
product.reg.CleanNew(RoundupSize(aSize+bSize));
3658
3674
product.sign = Integer::POSITIVE;
3659
3675
3660
SecAlignedWordBlock workspace(aSize + bSize);
3676
IntegerSecBlock workspace(aSize + bSize);
3661
3677
AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
3662
3678
}
3663
3679
3707
3723
if (!bSize)
3708
3724
throw Integer::DivideByZero();
3709
3725
3710
if (a.PositiveCompare(b) == -1)
3726
if (aSize < bSize)
3711
3727
{
3712
3728
remainder = a;
3713
3729
remainder.sign = Integer::POSITIVE;
3723
3739
quotient.reg.CleanNew(RoundupSize(aSize-bSize+2));
3724
3740
quotient.sign = Integer::POSITIVE;
3725
3741
3726
SecAlignedWordBlock T(aSize+2*bSize+4);
3742
IntegerSecBlock T(aSize+3*(bSize+2));
3727
3743
Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
3728
3744
}
3729
3745
3955
3971
{
3956
3972
assert(m.NotNegative());
3957
3973
3958
if (IsNegative() || *this>=m)
3959
return (*this%m).InverseMod(m);
3974
if (IsNegative())
3975
return Modulo(m).InverseMod(m);
3960
3976
3961
3977
if (m.IsEven())
3962
3978
{
3965
3981
if (*this == One())
3966
3982
return One();
3967
3983
3968
Integer u = m.InverseMod(*this);
3984
Integer u = m.Modulo(*this).InverseMod(*this);
3969
3985
return !u ? Zero() : (m*(*this-u)+1)/(*this);
3970
3986
}
3971
3987
3976
3992
return r;
3977
3993
}
3978
3994
3979
word Integer::InverseMod(const word mod) const
3995
word Integer::InverseMod(word mod) const
3980
3996
{
3981
3997
word g0 = mod, g1 = *this % mod;
3982
3998
word v0 = 0, v1 = 1;
Loggerhead is a web-based interface for Breezy
Version: 2.0.1