~zooko/cryptopp/trunk

« back to all changes in this revision

Viewing changes to integer.cpp

  • Committer: weidai
  • Date: 2010-06-18 01:52:34 UTC
  • Revision ID: svn-v4:57ff6487-cd31-0410-9ec3-f628ee90f5f0:trunk/c5:485
avoid SecBlock of arrays

Show diffs side-by-side

added added

removed removed

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