~zooko/cryptopp/trunk

« back to all changes in this revision

Viewing changes to integer.cpp

  • Committer: weidai
  • Date: 2007-05-04 15:36:15 UTC
  • Revision ID: svn-v4:57ff6487-cd31-0410-9ec3-f628ee90f5f0:trunk/c5:339
fix compile

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