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