6 #ifndef CRYPTOPP_IMPORTS
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.")
33 #define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE && CRYPTOPP_BOOL_X86)
35 NAMESPACE_BEGIN(CryptoPP)
37 bool AssignIntToInteger(const std::type_info &valueType,
void *pInteger, const
void *pInt)
39 if (valueType !=
typeid(
Integer))
41 *
reinterpret_cast<Integer *
>(pInteger) = *reinterpret_cast<const int *>(pInt);
45 inline static int Compare(
const word *A,
const word *B,
size_t N)
56 inline static int Increment(word *A,
size_t N, word B=1)
63 for (
unsigned i=1; i<N; i++)
69 inline static int Decrement(word *A,
size_t N, word B=1)
76 for (
unsigned i=1; i<N; i++)
82 static void TwosComplement(word *A,
size_t N)
85 for (
unsigned i=0; i<N; i++)
89 static word AtomicInverseModPower2(word A)
95 for (
unsigned i=3; i<WORD_BITS; i*=2)
104 #if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE))
105 #define Declare2Words(x) word x##0, x##1;
106 #define AssignWord(a, b) a##0 = b; a##1 = 0;
107 #define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c);
108 #define LowWord(a) a##0
109 #define HighWord(a) a##1
111 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1);
112 #ifndef __INTEL_COMPILER
113 #define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2;
115 #elif defined(__DECCXX)
116 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b);
117 #elif defined(__x86_64__)
118 #if defined(__SUNPRO_CC) && __SUNPRO_CC < 0x5100
120 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc");
122 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
123 #define MulAcc(c, d, a, b) asm ("mulq %6; addq %3, %0; adcq %4, %1; adcq $0, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1), "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
124 #define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc");
125 #define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc");
126 #define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc");
127 #define Acc3WordsBy2(c, d, e) asm ("addq %5, %0; adcq %6, %1; adcq $0, %2;" : "+r"(c), "=r"(e##0), "=r"(e##1) : "1"(d##0), "2"(d##1), "r"(e##0), "r"(e##1) : "cc");
130 #define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b)
132 #define Double3Words(c, d) d##1 = 2*d##1 + (d##0>>(WORD_BITS-1)); d##0 = 2*d##0 + (c>>(WORD_BITS-1)); c *= 2;
135 #define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1;
137 #define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);}
138 #define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);}
139 #define GetCarry(u) u##1
140 #define GetBorrow(u) u##1
142 #define Declare2Words(x) dword x;
143 #if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER)
144 #define MultiplyWords(p, a, b) p = __emulu(a, b);
146 #define MultiplyWords(p, a, b) p = (dword)a*b;
148 #define AssignWord(a, b) a = b;
149 #define Add2WordsBy1(a, b, c) a = b + c;
150 #define Acc2WordsBy2(a, b) a += b;
151 #define LowWord(a) word(a)
152 #define HighWord(a) word(a>>WORD_BITS)
153 #define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2;
154 #define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u);
155 #define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u);
156 #define GetCarry(u) HighWord(u)
157 #define GetBorrow(u) word(u>>(WORD_BITS*2-1))
160 #define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p));
163 #define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b)
166 #define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e));
174 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
175 explicit DWord(word low)
180 explicit DWord(word low)
187 DWord(word low, word high)
193 static DWord Multiply(word a, word b)
196 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
197 r.m_whole = (dword)a * b;
198 #elif defined(MultiplyWordsLoHi)
199 MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
204 static DWord MultiplyAndAdd(word a, word b, word c)
206 DWord r = Multiply(a, b);
210 DWord & operator+=(word a)
212 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
213 m_whole = m_whole + a;
216 m_halfs.high += (m_halfs.low < a);
221 DWord operator+(word a)
224 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
225 r.m_whole = m_whole + a;
227 r.m_halfs.low = m_halfs.low + a;
228 r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a);
236 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
237 r.m_whole = m_whole - a.m_whole;
239 r.m_halfs.low = m_halfs.low - a.m_halfs.low;
240 r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low);
245 DWord operator-(word a)
248 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
249 r.m_whole = m_whole - a;
251 r.m_halfs.low = m_halfs.low - a;
252 r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low);
258 word operator/(word divisor);
260 word operator%(word a);
262 bool operator!()
const
264 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
267 return !m_halfs.high && !m_halfs.low;
271 word GetLowHalf()
const {
return m_halfs.low;}
272 word GetHighHalf()
const {
return m_halfs.high;}
273 word GetHighHalfAsBorrow()
const {
return 0-m_halfs.high;}
278 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
283 #ifdef IS_LITTLE_ENDIAN
304 Word(hword low, hword high)
306 m_whole = low | (word(high) << (WORD_BITS/2));
309 static Word Multiply(hword a, hword b)
312 r.m_whole = (word)a * b;
319 r.m_whole = m_whole - a.m_whole;
323 Word operator-(hword a)
326 r.m_whole = m_whole - a;
331 hword operator/(hword divisor)
333 return hword(m_whole / divisor);
336 bool operator!()
const
341 word GetWhole()
const {
return m_whole;}
342 hword GetLowHalf()
const {
return hword(m_whole);}
343 hword GetHighHalf()
const {
return hword(m_whole>>(WORD_BITS/2));}
344 hword GetHighHalfAsBorrow()
const {
return 0-hword(m_whole>>(WORD_BITS/2));}
351 template <
class S,
class D>
352 S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULL)
355 assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));
362 Q = D(A[1], A[2]) / S(B1+1);
364 Q = D(A[0], A[1]) / B0;
367 D p = D::Multiply(B0, Q);
368 D u = (D) A[0] - p.GetLowHalf();
369 A[0] = u.GetLowHalf();
370 u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q);
371 A[1] = u.GetLowHalf();
372 A[2] += u.GetHighHalf();
375 while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
378 A[0] = u.GetLowHalf();
379 u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
380 A[1] = u.GetLowHalf();
381 A[2] += u.GetHighHalf();
390 template <
class S,
class D>
391 inline D DivideFourWordsByTwo(S *T,
const D &Al,
const D &Ah,
const D &B)
394 return D(Ah.GetLowHalf(), Ah.GetHighHalf());
398 T[0] = Al.GetLowHalf();
399 T[1] = Al.GetHighHalf();
400 T[2] = Ah.GetLowHalf();
401 T[3] = Ah.GetHighHalf();
402 Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(), B.GetHighHalf());
403 Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
404 return D(Q[0], Q[1]);
409 inline word DWord::operator/(word a)
411 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
412 return word(m_whole / a);
415 return DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a).GetWhole();
419 inline word DWord::operator%(word a)
421 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
422 return word(m_whole % a);
424 if (a < (word(1) << (WORD_BITS/2)))
427 word r = m_halfs.high % h;
428 r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
429 return hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h);
434 DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a);
435 return Word(r[0], r[1]).GetWhole();
443 #if defined(__GNUC__)
444 #define AddPrologue \
446 __asm__ __volatile__ \
448 ".intel_syntax noprefix;"
449 #define AddEpilogue \
450 ".att_syntax prefix;" \
452 : "d" (C), "a" (A), "D" (B), "c" (N) \
453 : "%esi", "memory", "cc" \
456 #define MulPrologue \
457 __asm__ __volatile__ \
459 ".intel_syntax noprefix;" \
462 #define MulEpilogue \
464 ".att_syntax prefix;" \
466 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \
467 : "%esi", "memory", "cc" \
469 #define SquPrologue MulPrologue
470 #define SquEpilogue \
472 ".att_syntax prefix;" \
474 : "d" (s_maskLow16), "c" (C), "a" (A) \
475 : "%esi", "%edi", "memory", "cc" \
477 #define TopPrologue MulPrologue
478 #define TopEpilogue \
480 ".att_syntax prefix;" \
482 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \
486 #define AddPrologue \
489 __asm mov eax, [esp+12] \
490 __asm mov edi, [esp+16]
491 #define AddEpilogue \
496 #define SaveEBX __asm push ebx
497 #define RestoreEBX __asm pop ebx
502 #define SquPrologue \
506 AS2( lea ebx, s_maskLow16)
507 #define MulPrologue \
512 AS2( lea ebx, s_maskLow16)
513 #define TopPrologue \
519 AS2( lea ebx, s_maskLow16)
520 #define SquEpilogue RestoreEBX
521 #define MulEpilogue RestoreEBX
522 #define TopEpilogue RestoreEBX
525 #ifdef CRYPTOPP_X64_MASM_AVAILABLE
527 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B);
528 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B);
530 #elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE)
531 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
539 AS2( mov %0,[%3+8*%1])
540 AS2( add %0,[%4+8*%1])
541 AS2( mov [%2+8*%1],%0)
543 AS2( mov %0,[%3+8*%1+8])
544 AS2( adc %0,[%4+8*%1+8])
545 AS2( mov [%2+8*%1+8],%0)
548 AS2( mov %0,[%3+8*%1])
549 AS2( adc %0,[%4+8*%1])
550 AS2( mov [%2+8*%1],%0)
556 :
"=&r" (result),
"+c" (N)
557 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
563 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
571 AS2( mov %0,[%3+8*%1])
572 AS2( sub %0,[%4+8*%1])
573 AS2( mov [%2+8*%1],%0)
575 AS2( mov %0,[%3+8*%1+8])
576 AS2( sbb %0,[%4+8*%1+8])
577 AS2( mov [%2+8*%1+8],%0)
580 AS2( mov %0,[%3+8*%1])
581 AS2( sbb %0,[%4+8*%1])
582 AS2( mov [%2+8*%1],%0)
588 :
"=&r" (result),
"+c" (N)
589 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
594 #elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86
595 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
600 AS2( lea eax, [eax+4*ecx])
601 AS2( lea edi, [edi+4*ecx])
602 AS2( lea edx, [edx+4*ecx])
612 AS2( mov esi,[eax+4*ecx])
613 AS2( adc esi,[edi+4*ecx])
614 AS2( mov [edx+4*ecx],esi)
615 AS2( mov esi,[eax+4*ecx+4])
616 AS2( adc esi,[edi+4*ecx+4])
617 AS2( mov [edx+4*ecx+4],esi)
619 AS2( mov esi,[eax+4*ecx+8])
620 AS2( adc esi,[edi+4*ecx+8])
621 AS2( mov [edx+4*ecx+8],esi)
622 AS2( mov esi,[eax+4*ecx+12])
623 AS2( adc esi,[edi+4*ecx+12])
624 AS2( mov [edx+4*ecx+12],esi)
626 AS2( lea ecx,[ecx+4])
636 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C, const word *A, const word *B)
641 AS2( lea eax, [eax+4*ecx])
642 AS2( lea edi, [edi+4*ecx])
643 AS2( lea edx, [edx+4*ecx])
653 AS2( mov esi,[eax+4*ecx])
654 AS2( sbb esi,[edi+4*ecx])
655 AS2( mov [edx+4*ecx],esi)
656 AS2( mov esi,[eax+4*ecx+4])
657 AS2( sbb esi,[edi+4*ecx+4])
658 AS2( mov [edx+4*ecx+4],esi)
660 AS2( mov esi,[eax+4*ecx+8])
661 AS2( sbb esi,[edi+4*ecx+8])
662 AS2( mov [edx+4*ecx+8],esi)
663 AS2( mov esi,[eax+4*ecx+12])
664 AS2( sbb esi,[edi+4*ecx+12])
665 AS2( mov [edx+4*ecx+12],esi)
667 AS2( lea ecx,[ecx+4])
677 #if CRYPTOPP_INTEGER_SSE2
678 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Add(
size_t N, word *C,
const word *A,
const word *B)
683 AS2( lea eax, [eax+4*ecx])
684 AS2( lea edi, [edi+4*ecx])
685 AS2( lea edx, [edx+4*ecx])
696 AS2( movd mm0, DWORD PTR [eax+4*ecx])
697 AS2( movd mm1, DWORD PTR [edi+4*ecx])
700 AS2( movd DWORD PTR [edx+4*ecx], mm2)
703 AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
704 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
707 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
711 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
712 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
715 AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
718 AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
719 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
722 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
734 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Sub(
size_t N, word *C, const word *A, const word *B)
739 AS2( lea eax, [eax+4*ecx])
740 AS2( lea edi, [edi+4*ecx])
741 AS2( lea edx, [edx+4*ecx])
752 AS2( movd mm0, DWORD PTR [eax+4*ecx])
753 AS2( movd mm1, DWORD PTR [edi+4*ecx])
756 AS2( movd DWORD PTR [edx+4*ecx], mm0)
759 AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
760 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
763 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
767 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
768 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
771 AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
774 AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
775 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
778 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
790 #endif // #if CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE
792 int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
798 for (
size_t i=0; i<N; i+=2)
800 AddWithCarry(u, A[i], B[i]);
802 AddWithCarry(u, A[i+1], B[i+1]);
805 return int(GetCarry(u));
808 int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
814 for (
size_t i=0; i<N; i+=2)
816 SubtractWithBorrow(u, A[i], B[i]);
818 SubtractWithBorrow(u, A[i+1], B[i+1]);
821 return int(GetBorrow(u));
825 static word LinearMultiply(word *C,
const word *A, word B,
size_t N)
828 for(
unsigned i=0; i<N; i++)
831 MultiplyWords(p, A[i], B);
832 Acc2WordsBy1(p, carry);
839 #ifndef CRYPTOPP_DOXYGEN_PROCESSING
843 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
848 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
849 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
850 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
851 Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
852 Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \
857 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
858 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
859 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
860 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
861 Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
862 Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
863 Mul_SaveAcc(6, 0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
864 Mul_SaveAcc(7, 1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) \
865 Mul_SaveAcc(8, 2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) \
866 Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
867 Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
868 Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
869 Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \
874 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
875 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
876 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
877 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
878 Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
879 Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
880 Mul_SaveAcc(6, 0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
881 Mul_SaveAcc(7, 0, 8) Mul_Acc(1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) Mul_Acc(8, 0) \
882 Mul_SaveAcc(8, 0, 9) Mul_Acc(1, 8) Mul_Acc(2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) Mul_Acc(8, 1) Mul_Acc(9, 0) \
883 Mul_SaveAcc(9, 0, 10) Mul_Acc(1, 9) Mul_Acc(2, 8) Mul_Acc(3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) Mul_Acc(8, 2) Mul_Acc(9, 1) Mul_Acc(10, 0) \
884 Mul_SaveAcc(10, 0, 11) Mul_Acc(1, 10) Mul_Acc(2, 9) Mul_Acc(3, 8) Mul_Acc(4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) Mul_Acc(8, 3) Mul_Acc(9, 2) Mul_Acc(10, 1) Mul_Acc(11, 0) \
885 Mul_SaveAcc(11, 0, 12) Mul_Acc(1, 11) Mul_Acc(2, 10) Mul_Acc(3, 9) Mul_Acc(4, 8) Mul_Acc(5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) Mul_Acc(8, 4) Mul_Acc(9, 3) Mul_Acc(10, 2) Mul_Acc(11, 1) Mul_Acc(12, 0) \
886 Mul_SaveAcc(12, 0, 13) Mul_Acc(1, 12) Mul_Acc(2, 11) Mul_Acc(3, 10) Mul_Acc(4, 9) Mul_Acc(5, 8) Mul_Acc(6, 7) Mul_Acc(7, 6) Mul_Acc(8, 5) Mul_Acc(9, 4) Mul_Acc(10, 3) Mul_Acc(11, 2) Mul_Acc(12, 1) Mul_Acc(13, 0) \
887 Mul_SaveAcc(13, 0, 14) Mul_Acc(1, 13) Mul_Acc(2, 12) Mul_Acc(3, 11) Mul_Acc(4, 10) Mul_Acc(5, 9) Mul_Acc(6, 8) Mul_Acc(7, 7) Mul_Acc(8, 6) Mul_Acc(9, 5) Mul_Acc(10, 4) Mul_Acc(11, 3) Mul_Acc(12, 2) Mul_Acc(13, 1) Mul_Acc(14, 0) \
888 Mul_SaveAcc(14, 0, 15) Mul_Acc(1, 14) Mul_Acc(2, 13) Mul_Acc(3, 12) Mul_Acc(4, 11) Mul_Acc(5, 10) Mul_Acc(6, 9) Mul_Acc(7, 8) Mul_Acc(8, 7) Mul_Acc(9, 6) Mul_Acc(10, 5) Mul_Acc(11, 4) Mul_Acc(12, 3) Mul_Acc(13, 2) Mul_Acc(14, 1) Mul_Acc(15, 0) \
889 Mul_SaveAcc(15, 1, 15) Mul_Acc(2, 14) Mul_Acc(3, 13) Mul_Acc(4, 12) Mul_Acc(5, 11) Mul_Acc(6, 10) Mul_Acc(7, 9) Mul_Acc(8, 8) Mul_Acc(9, 7) Mul_Acc(10, 6) Mul_Acc(11, 5) Mul_Acc(12, 4) Mul_Acc(13, 3) Mul_Acc(14, 2) Mul_Acc(15, 1) \
890 Mul_SaveAcc(16, 2, 15) Mul_Acc(3, 14) Mul_Acc(4, 13) Mul_Acc(5, 12) Mul_Acc(6, 11) Mul_Acc(7, 10) Mul_Acc(8, 9) Mul_Acc(9, 8) Mul_Acc(10, 7) Mul_Acc(11, 6) Mul_Acc(12, 5) Mul_Acc(13, 4) Mul_Acc(14, 3) Mul_Acc(15, 2) \
891 Mul_SaveAcc(17, 3, 15) Mul_Acc(4, 14) Mul_Acc(5, 13) Mul_Acc(6, 12) Mul_Acc(7, 11) Mul_Acc(8, 10) Mul_Acc(9, 9) Mul_Acc(10, 8) Mul_Acc(11, 7) Mul_Acc(12, 6) Mul_Acc(13, 5) Mul_Acc(14, 4) Mul_Acc(15, 3) \
892 Mul_SaveAcc(18, 4, 15) Mul_Acc(5, 14) Mul_Acc(6, 13) Mul_Acc(7, 12) Mul_Acc(8, 11) Mul_Acc(9, 10) Mul_Acc(10, 9) Mul_Acc(11, 8) Mul_Acc(12, 7) Mul_Acc(13, 6) Mul_Acc(14, 5) Mul_Acc(15, 4) \
893 Mul_SaveAcc(19, 5, 15) Mul_Acc(6, 14) Mul_Acc(7, 13) Mul_Acc(8, 12) Mul_Acc(9, 11) Mul_Acc(10, 10) Mul_Acc(11, 9) Mul_Acc(12, 8) Mul_Acc(13, 7) Mul_Acc(14, 6) Mul_Acc(15, 5) \
894 Mul_SaveAcc(20, 6, 15) Mul_Acc(7, 14) Mul_Acc(8, 13) Mul_Acc(9, 12) Mul_Acc(10, 11) Mul_Acc(11, 10) Mul_Acc(12, 9) Mul_Acc(13, 8) Mul_Acc(14, 7) Mul_Acc(15, 6) \
895 Mul_SaveAcc(21, 7, 15) Mul_Acc(8, 14) Mul_Acc(9, 13) Mul_Acc(10, 12) Mul_Acc(11, 11) Mul_Acc(12, 10) Mul_Acc(13, 9) Mul_Acc(14, 8) Mul_Acc(15, 7) \
896 Mul_SaveAcc(22, 8, 15) Mul_Acc(9, 14) Mul_Acc(10, 13) Mul_Acc(11, 12) Mul_Acc(12, 11) Mul_Acc(13, 10) Mul_Acc(14, 9) Mul_Acc(15, 8) \
897 Mul_SaveAcc(23, 9, 15) Mul_Acc(10, 14) Mul_Acc(11, 13) Mul_Acc(12, 12) Mul_Acc(13, 11) Mul_Acc(14, 10) Mul_Acc(15, 9) \
898 Mul_SaveAcc(24, 10, 15) Mul_Acc(11, 14) Mul_Acc(12, 13) Mul_Acc(13, 12) Mul_Acc(14, 11) Mul_Acc(15, 10) \
899 Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
900 Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
901 Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
902 Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \
911 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
912 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
913 Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \
914 Squ_SaveAcc(4, 2, 3) Squ_NonDiag \
919 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
920 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
921 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
922 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
923 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
924 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
925 Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
926 Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
927 Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
928 Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \
929 Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \
930 Squ_SaveAcc(12, 6, 7) Squ_NonDiag \
935 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
936 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
937 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
938 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
939 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
940 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
941 Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
942 Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
943 Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
944 Squ_SaveAcc(10, 0, 11) Squ_Acc(1, 10) Squ_Acc(2, 9) Squ_Acc(3, 8) Squ_Acc(4, 7) Squ_Acc(5, 6) Squ_NonDiag \
945 Squ_SaveAcc(11, 0, 12) Squ_Acc(1, 11) Squ_Acc(2, 10) Squ_Acc(3, 9) Squ_Acc(4, 8) Squ_Acc(5, 7) Squ_Diag(6) \
946 Squ_SaveAcc(12, 0, 13) Squ_Acc(1, 12) Squ_Acc(2, 11) Squ_Acc(3, 10) Squ_Acc(4, 9) Squ_Acc(5, 8) Squ_Acc(6, 7) Squ_NonDiag \
947 Squ_SaveAcc(13, 0, 14) Squ_Acc(1, 13) Squ_Acc(2, 12) Squ_Acc(3, 11) Squ_Acc(4, 10) Squ_Acc(5, 9) Squ_Acc(6, 8) Squ_Diag(7) \
948 Squ_SaveAcc(14, 0, 15) Squ_Acc(1, 14) Squ_Acc(2, 13) Squ_Acc(3, 12) Squ_Acc(4, 11) Squ_Acc(5, 10) Squ_Acc(6, 9) Squ_Acc(7, 8) Squ_NonDiag \
949 Squ_SaveAcc(15, 1, 15) Squ_Acc(2, 14) Squ_Acc(3, 13) Squ_Acc(4, 12) Squ_Acc(5, 11) Squ_Acc(6, 10) Squ_Acc(7, 9) Squ_Diag(8) \
950 Squ_SaveAcc(16, 2, 15) Squ_Acc(3, 14) Squ_Acc(4, 13) Squ_Acc(5, 12) Squ_Acc(6, 11) Squ_Acc(7, 10) Squ_Acc(8, 9) Squ_NonDiag \
951 Squ_SaveAcc(17, 3, 15) Squ_Acc(4, 14) Squ_Acc(5, 13) Squ_Acc(6, 12) Squ_Acc(7, 11) Squ_Acc(8, 10) Squ_Diag(9) \
952 Squ_SaveAcc(18, 4, 15) Squ_Acc(5, 14) Squ_Acc(6, 13) Squ_Acc(7, 12) Squ_Acc(8, 11) Squ_Acc(9, 10) Squ_NonDiag \
953 Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \
954 Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \
955 Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \
956 Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \
957 Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \
958 Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \
959 Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \
960 Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \
961 Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \
962 Squ_SaveAcc(28, 14, 15) Squ_NonDiag \
967 Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \
972 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
973 Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \
974 Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \
979 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
980 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
981 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
982 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
983 Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
984 Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
985 Bot_SaveAcc(6, 0, 7) Bot_Acc(1, 6) Bot_Acc(2, 5) Bot_Acc(3, 4) Bot_Acc(4, 3) Bot_Acc(5, 2) Bot_Acc(6, 1) Bot_Acc(7, 0) \
990 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
991 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
992 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
993 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
994 Mul_SaveAcc(4, 0, 5) Mul_Acc(1, 4) Mul_Acc(2, 3) Mul_Acc(3, 2) Mul_Acc(4, 1) Mul_Acc(5, 0) \
995 Mul_SaveAcc(5, 0, 6) Mul_Acc(1, 5) Mul_Acc(2, 4) Mul_Acc(3, 3) Mul_Acc(4, 2) Mul_Acc(5, 1) Mul_Acc(6, 0) \
996 Mul_SaveAcc(6, 0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
997 Mul_SaveAcc(7, 0, 8) Mul_Acc(1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) Mul_Acc(8, 0) \
998 Mul_SaveAcc(8, 0, 9) Mul_Acc(1, 8) Mul_Acc(2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) Mul_Acc(8, 1) Mul_Acc(9, 0) \
999 Mul_SaveAcc(9, 0, 10) Mul_Acc(1, 9) Mul_Acc(2, 8) Mul_Acc(3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) Mul_Acc(8, 2) Mul_Acc(9, 1) Mul_Acc(10, 0) \
1000 Mul_SaveAcc(10, 0, 11) Mul_Acc(1, 10) Mul_Acc(2, 9) Mul_Acc(3, 8) Mul_Acc(4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) Mul_Acc(8, 3) Mul_Acc(9, 2) Mul_Acc(10, 1) Mul_Acc(11, 0) \
1001 Mul_SaveAcc(11, 0, 12) Mul_Acc(1, 11) Mul_Acc(2, 10) Mul_Acc(3, 9) Mul_Acc(4, 8) Mul_Acc(5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) Mul_Acc(8, 4) Mul_Acc(9, 3) Mul_Acc(10, 2) Mul_Acc(11, 1) Mul_Acc(12, 0) \
1002 Mul_SaveAcc(12, 0, 13) Mul_Acc(1, 12) Mul_Acc(2, 11) Mul_Acc(3, 10) Mul_Acc(4, 9) Mul_Acc(5, 8) Mul_Acc(6, 7) Mul_Acc(7, 6) Mul_Acc(8, 5) Mul_Acc(9, 4) Mul_Acc(10, 3) Mul_Acc(11, 2) Mul_Acc(12, 1) Mul_Acc(13, 0) \
1003 Mul_SaveAcc(13, 0, 14) Mul_Acc(1, 13) Mul_Acc(2, 12) Mul_Acc(3, 11) Mul_Acc(4, 10) Mul_Acc(5, 9) Mul_Acc(6, 8) Mul_Acc(7, 7) Mul_Acc(8, 6) Mul_Acc(9, 5) Mul_Acc(10, 4) Mul_Acc(11, 3) Mul_Acc(12, 2) Mul_Acc(13, 1) Mul_Acc(14, 0) \
1004 Bot_SaveAcc(14, 0, 15) Bot_Acc(1, 14) Bot_Acc(2, 13) Bot_Acc(3, 12) Bot_Acc(4, 11) Bot_Acc(5, 10) Bot_Acc(6, 9) Bot_Acc(7, 8) Bot_Acc(8, 7) Bot_Acc(9, 6) Bot_Acc(10, 5) Bot_Acc(11, 4) Bot_Acc(12, 3) Bot_Acc(13, 2) Bot_Acc(14, 1) Bot_Acc(15, 0) \
1010 #define Mul_Begin(n) \
1014 MultiplyWords(p, A[0], B[0]) \
1015 AssignWord(c, LowWord(p)) \
1016 AssignWord(d, HighWord(p))
1018 #define Mul_Acc(i, j) \
1019 MultiplyWords(p, A[i], B[j]) \
1020 Acc2WordsBy1(c, LowWord(p)) \
1021 Acc2WordsBy1(d, HighWord(p))
1023 #define Mul_SaveAcc(k, i, j) \
1024 R[k] = LowWord(c); \
1025 Add2WordsBy1(c, d, HighWord(c)) \
1026 MultiplyWords(p, A[i], B[j]) \
1027 AssignWord(d, HighWord(p)) \
1028 Acc2WordsBy1(c, LowWord(p))
1030 #define Mul_End(n) \
1031 R[2*n-3] = LowWord(c); \
1032 Acc2WordsBy1(d, HighWord(c)) \
1033 MultiplyWords(p, A[n-1], B[n-1])\
1034 Acc2WordsBy2(d, p) \
1035 R[2*n-2] = LowWord(d); \
1036 R[2*n-1] = HighWord(d);
1038 #define Bot_SaveAcc(k, i, j) \
1039 R[k] = LowWord(c); \
1040 word e = LowWord(d) + HighWord(c); \
1043 #define Bot_Acc(i, j) \
1046 #define Bot_End(n) \
1049 #define Mul_Begin(n) \
1053 MultiplyWords(p, A[0], B[0]) \
1055 AssignWord(d, HighWord(p))
1057 #define Mul_Acc(i, j) \
1058 MulAcc(c, d, A[i], B[j])
1060 #define Mul_SaveAcc(k, i, j) \
1063 AssignWord(d, HighWord(d)) \
1064 MulAcc(c, d, A[i], B[j])
1066 #define Mul_End(k, i) \
1068 MultiplyWords(p, A[i], B[i]) \
1069 Acc2WordsBy2(p, d) \
1070 R[k+1] = LowWord(p); \
1071 R[k+2] = HighWord(p);
1073 #define Bot_SaveAcc(k, i, j) \
1078 #define Bot_Acc(i, j) \
1081 #define Bot_End(n) \
1085 #define Squ_Begin(n) \
1090 MultiplyWords(p, A[0], A[0]) \
1091 R[0] = LowWord(p); \
1092 AssignWord(e, HighWord(p)) \
1093 MultiplyWords(p, A[0], A[1]) \
1095 AssignWord(d, HighWord(p)) \
1098 #define Squ_NonDiag \
1101 #define Squ_SaveAcc(k, i, j) \
1102 Acc3WordsBy2(c, d, e) \
1104 MultiplyWords(p, A[i], A[j]) \
1106 AssignWord(d, HighWord(p)) \
1108 #define Squ_Acc(i, j) \
1109 MulAcc(c, d, A[i], A[j])
1111 #define Squ_Diag(i) \
1113 MulAcc(c, d, A[i], A[i])
1115 #define Squ_End(n) \
1116 Acc3WordsBy2(c, d, e) \
1118 MultiplyWords(p, A[n-1], A[n-1])\
1119 Acc2WordsBy2(p, e) \
1120 R[2*n-2] = LowWord(p); \
1121 R[2*n-1] = HighWord(p);
1123 void Baseline_Multiply2(word *R,
const word *A,
const word *B)
1128 void Baseline_Multiply4(word *R,
const word *A,
const word *B)
1133 void Baseline_Multiply8(word *R,
const word *A,
const word *B)
1138 void Baseline_Square2(word *R,
const word *A)
1143 void Baseline_Square4(word *R,
const word *A)
1148 void Baseline_Square8(word *R,
const word *A)
1153 void Baseline_MultiplyBottom2(word *R,
const word *A,
const word *B)
1158 void Baseline_MultiplyBottom4(word *R,
const word *A,
const word *B)
1163 void Baseline_MultiplyBottom8(word *R,
const word *A,
const word *B)
1168 #define Top_Begin(n) \
1172 MultiplyWords(p, A[0], B[n-2]);\
1173 AssignWord(d, HighWord(p));
1175 #define Top_Acc(i, j) \
1176 MultiplyWords(p, A[i], B[j]);\
1177 Acc2WordsBy1(d, HighWord(p));
1179 #define Top_SaveAcc0(i, j) \
1181 AssignWord(d, HighWord(d)) \
1182 MulAcc(c, d, A[i], B[j])
1184 #define Top_SaveAcc1(i, j) \
1186 Acc2WordsBy1(d, c); \
1188 AssignWord(d, HighWord(d)) \
1189 MulAcc(c, d, A[i], B[j])
1191 void Baseline_MultiplyTop2(word *R,
const word *A,
const word *B, word L)
1194 Baseline_Multiply2(T, A, B);
1199 void Baseline_MultiplyTop4(word *R,
const word *A,
const word *B, word L)
1202 Top_Acc(1, 1) Top_Acc(2, 0) \
1203 Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1204 Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1205 Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1209 void Baseline_MultiplyTop8(word *R, const word *A, const word *B, word L)
1212 Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1213 Top_SaveAcc0(0, 7) Mul_Acc(1, 6) Mul_Acc(2, 5) Mul_Acc(3, 4) Mul_Acc(4, 3) Mul_Acc(5, 2) Mul_Acc(6, 1) Mul_Acc(7, 0) \
1214 Top_SaveAcc1(1, 7) Mul_Acc(2, 6) Mul_Acc(3, 5) Mul_Acc(4, 4) Mul_Acc(5, 3) Mul_Acc(6, 2) Mul_Acc(7, 1) \
1215 Mul_SaveAcc(0, 2, 7) Mul_Acc(3, 6) Mul_Acc(4, 5) Mul_Acc(5, 4) Mul_Acc(6, 3) Mul_Acc(7, 2) \
1216 Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1217 Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1218 Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1219 Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1223 #if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available
1224 void Baseline_Multiply16(word *R,
const word *A,
const word *B)
1229 void Baseline_Square16(word *R,
const word *A)
1234 void Baseline_MultiplyBottom16(word *R,
const word *A,
const word *B)
1239 void Baseline_MultiplyTop16(word *R,
const word *A,
const word *B, word L)
1242 Top_Acc(1, 13) Top_Acc(2, 12) Top_Acc(3, 11) Top_Acc(4, 10) Top_Acc(5, 9) Top_Acc(6, 8) Top_Acc(7, 7) Top_Acc(8, 6) Top_Acc(9, 5) Top_Acc(10, 4) Top_Acc(11, 3) Top_Acc(12, 2) Top_Acc(13, 1) Top_Acc(14, 0) \
1243 Top_SaveAcc0(0, 15) Mul_Acc(1, 14) Mul_Acc(2, 13) Mul_Acc(3, 12) Mul_Acc(4, 11) Mul_Acc(5, 10) Mul_Acc(6, 9) Mul_Acc(7, 8) Mul_Acc(8, 7) Mul_Acc(9, 6) Mul_Acc(10, 5) Mul_Acc(11, 4) Mul_Acc(12, 3) Mul_Acc(13, 2) Mul_Acc(14, 1) Mul_Acc(15, 0) \
1244 Top_SaveAcc1(1, 15) Mul_Acc(2, 14) Mul_Acc(3, 13) Mul_Acc(4, 12) Mul_Acc(5, 11) Mul_Acc(6, 10) Mul_Acc(7, 9) Mul_Acc(8, 8) Mul_Acc(9, 7) Mul_Acc(10, 6) Mul_Acc(11, 5) Mul_Acc(12, 4) Mul_Acc(13, 3) Mul_Acc(14, 2) Mul_Acc(15, 1) \
1245 Mul_SaveAcc(0, 2, 15) Mul_Acc(3, 14) Mul_Acc(4, 13) Mul_Acc(5, 12) Mul_Acc(6, 11) Mul_Acc(7, 10) Mul_Acc(8, 9) Mul_Acc(9, 8) Mul_Acc(10, 7) Mul_Acc(11, 6) Mul_Acc(12, 5) Mul_Acc(13, 4) Mul_Acc(14, 3) Mul_Acc(15, 2) \
1246 Mul_SaveAcc(1, 3, 15) Mul_Acc(4, 14) Mul_Acc(5, 13) Mul_Acc(6, 12) Mul_Acc(7, 11) Mul_Acc(8, 10) Mul_Acc(9, 9) Mul_Acc(10, 8) Mul_Acc(11, 7) Mul_Acc(12, 6) Mul_Acc(13, 5) Mul_Acc(14, 4) Mul_Acc(15, 3) \
1247 Mul_SaveAcc(2, 4, 15) Mul_Acc(5, 14) Mul_Acc(6, 13) Mul_Acc(7, 12) Mul_Acc(8, 11) Mul_Acc(9, 10) Mul_Acc(10, 9) Mul_Acc(11, 8) Mul_Acc(12, 7) Mul_Acc(13, 6) Mul_Acc(14, 5) Mul_Acc(15, 4) \
1248 Mul_SaveAcc(3, 5, 15) Mul_Acc(6, 14) Mul_Acc(7, 13) Mul_Acc(8, 12) Mul_Acc(9, 11) Mul_Acc(10, 10) Mul_Acc(11, 9) Mul_Acc(12, 8) Mul_Acc(13, 7) Mul_Acc(14, 6) Mul_Acc(15, 5) \
1249 Mul_SaveAcc(4, 6, 15) Mul_Acc(7, 14) Mul_Acc(8, 13) Mul_Acc(9, 12) Mul_Acc(10, 11) Mul_Acc(11, 10) Mul_Acc(12, 9) Mul_Acc(13, 8) Mul_Acc(14, 7) Mul_Acc(15, 6) \
1250 Mul_SaveAcc(5, 7, 15) Mul_Acc(8, 14) Mul_Acc(9, 13) Mul_Acc(10, 12) Mul_Acc(11, 11) Mul_Acc(12, 10) Mul_Acc(13, 9) Mul_Acc(14, 8) Mul_Acc(15, 7) \
1251 Mul_SaveAcc(6, 8, 15) Mul_Acc(9, 14) Mul_Acc(10, 13) Mul_Acc(11, 12) Mul_Acc(12, 11) Mul_Acc(13, 10) Mul_Acc(14, 9) Mul_Acc(15, 8) \
1252 Mul_SaveAcc(7, 9, 15) Mul_Acc(10, 14) Mul_Acc(11, 13) Mul_Acc(12, 12) Mul_Acc(13, 11) Mul_Acc(14, 10) Mul_Acc(15, 9) \
1253 Mul_SaveAcc(8, 10, 15) Mul_Acc(11, 14) Mul_Acc(12, 13) Mul_Acc(13, 12) Mul_Acc(14, 11) Mul_Acc(15, 10) \
1254 Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1255 Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1256 Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1257 Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1264 #if CRYPTOPP_INTEGER_SSE2
1266 CRYPTOPP_ALIGN_DATA(16) static const word32 s_maskLow16[4] CRYPTOPP_SECTION_ALIGN16 = {0xffff,0xffff,0xffff,0xffff};
1284 #define SSE2_FinalSave(k) \
1285 AS2( psllq xmm5, 16) \
1286 AS2( paddq xmm4, xmm5) \
1287 AS2( movq QWORD PTR [ecx+8*(k)], xmm4)
1289 #define SSE2_SaveShift(k) \
1290 AS2( movq xmm0, xmm6) \
1291 AS2( punpckhqdq xmm6, xmm0) \
1292 AS2( movq xmm1, xmm7) \
1293 AS2( punpckhqdq xmm7, xmm1) \
1294 AS2( paddd xmm6, xmm0) \
1295 AS2( pslldq xmm6, 4) \
1296 AS2( paddd xmm7, xmm1) \
1297 AS2( paddd xmm4, xmm6) \
1298 AS2( pslldq xmm7, 4) \
1299 AS2( movq xmm6, xmm4) \
1300 AS2( paddd xmm5, xmm7) \
1301 AS2( movq xmm7, xmm5) \
1302 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1303 AS2( psrlq xmm6, 16) \
1304 AS2( paddq xmm6, xmm7) \
1305 AS2( punpckhqdq xmm4, xmm0) \
1306 AS2( punpckhqdq xmm5, xmm0) \
1307 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \
1308 AS2( psrlq xmm6, 3*16) \
1309 AS2( paddd xmm4, xmm6) \
1311 #define Squ_SSE2_SaveShift(k) \
1312 AS2( movq xmm0, xmm6) \
1313 AS2( punpckhqdq xmm6, xmm0) \
1314 AS2( movq xmm1, xmm7) \
1315 AS2( punpckhqdq xmm7, xmm1) \
1316 AS2( paddd xmm6, xmm0) \
1317 AS2( pslldq xmm6, 4) \
1318 AS2( paddd xmm7, xmm1) \
1319 AS2( paddd xmm4, xmm6) \
1320 AS2( pslldq xmm7, 4) \
1321 AS2( movhlps xmm6, xmm4) \
1322 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1323 AS2( paddd xmm5, xmm7) \
1324 AS2( movhps QWORD PTR [esp+12], xmm5)\
1325 AS2( psrlq xmm4, 16) \
1326 AS2( paddq xmm4, xmm5) \
1327 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \
1328 AS2( psrlq xmm4, 3*16) \
1329 AS2( paddd xmm4, xmm6) \
1330 AS2( movq QWORD PTR [esp+4], xmm4)\
1332 #define SSE2_FirstMultiply(i) \
1333 AS2( movdqa xmm7, [esi+(i)*16])\
1334 AS2( movdqa xmm5, [edi-(i)*16])\
1335 AS2( pmuludq xmm5, xmm7) \
1336 AS2( movdqa xmm4, [ebx])\
1337 AS2( movdqa xmm6, xmm4) \
1338 AS2( pand xmm4, xmm5) \
1339 AS2( psrld xmm5, 16) \
1340 AS2( pmuludq xmm7, [edx-(i)*16])\
1341 AS2( pand xmm6, xmm7) \
1342 AS2( psrld xmm7, 16)
1344 #define Squ_Begin(n) \
1347 AS2( and esp, 0xfffffff0)\
1348 AS2( lea edi, [esp-32*n])\
1349 AS2( sub esp, 32*n+16)\
1351 AS2( mov esi, edi) \
1352 AS2( xor edx, edx) \
1354 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1355 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1356 AS2( movdqa [edi+2*edx], xmm0) \
1357 AS2( psrlq xmm0, 32) \
1358 AS2( movdqa [edi+2*edx+16], xmm0) \
1359 AS2( movdqa [edi+16*n+2*edx], xmm1) \
1360 AS2( psrlq xmm1, 32) \
1361 AS2( movdqa [edi+16*n+2*edx+16], xmm1) \
1363 AS2( cmp edx, 8*(n)) \
1365 AS2( lea edx, [edi+16*n])\
1366 SSE2_FirstMultiply(0) \
1368 #define Squ_Acc(i) \
1370 AS2( movdqa xmm1, [esi+(i)*16]) \
1371 AS2( movdqa xmm0, [edi-(i)*16]) \
1372 AS2( movdqa xmm2, [ebx]) \
1373 AS2( pmuludq xmm0, xmm1) \
1374 AS2( pmuludq xmm1, [edx-(i)*16]) \
1375 AS2( movdqa xmm3, xmm2) \
1376 AS2( pand xmm2, xmm0) \
1377 AS2( psrld xmm0, 16) \
1378 AS2( paddd xmm4, xmm2) \
1379 AS2( paddd xmm5, xmm0) \
1380 AS2( pand xmm3, xmm1) \
1381 AS2( psrld xmm1, 16) \
1382 AS2( paddd xmm6, xmm3) \
1383 AS2( paddd xmm7, xmm1) \
1386 #define Squ_Acc2(i) ASC(call, LSqu##i)
1387 #define Squ_Acc3(i) Squ_Acc2(i)
1388 #define Squ_Acc4(i) Squ_Acc2(i)
1389 #define Squ_Acc5(i) Squ_Acc2(i)
1390 #define Squ_Acc6(i) Squ_Acc2(i)
1391 #define Squ_Acc7(i) Squ_Acc2(i)
1392 #define Squ_Acc8(i) Squ_Acc2(i)
1394 #define SSE2_End(E, n) \
1395 SSE2_SaveShift(2*(n)-3) \
1396 AS2( movdqa xmm7, [esi+16]) \
1397 AS2( movdqa xmm0, [edi]) \
1398 AS2( pmuludq xmm0, xmm7) \
1399 AS2( movdqa xmm2, [ebx]) \
1400 AS2( pmuludq xmm7, [edx]) \
1401 AS2( movdqa xmm6, xmm2) \
1402 AS2( pand xmm2, xmm0) \
1403 AS2( psrld xmm0, 16) \
1404 AS2( paddd xmm4, xmm2) \
1405 AS2( paddd xmm5, xmm0) \
1406 AS2( pand xmm6, xmm7) \
1407 AS2( psrld xmm7, 16) \
1408 SSE2_SaveShift(2*(n)-2) \
1409 SSE2_FinalSave(2*(n)-1) \
1413 #define Squ_End(n) SSE2_End(SquEpilogue, n)
1414 #define Mul_End(n) SSE2_End(MulEpilogue, n)
1415 #define Top_End(n) SSE2_End(TopEpilogue, n)
1417 #define Squ_Column1(k, i) \
1418 Squ_SSE2_SaveShift(k) \
1420 SSE2_FirstMultiply(1)\
1422 AS2( paddd xmm4, xmm4) \
1423 AS2( paddd xmm5, xmm5) \
1424 AS2( movdqa xmm3, [esi]) \
1425 AS2( movq xmm1, QWORD PTR [esi+8]) \
1426 AS2( pmuludq xmm1, xmm3) \
1427 AS2( pmuludq xmm3, xmm3) \
1428 AS2( movdqa xmm0, [ebx])\
1429 AS2( movdqa xmm2, xmm0) \
1430 AS2( pand xmm0, xmm1) \
1431 AS2( psrld xmm1, 16) \
1432 AS2( paddd xmm6, xmm0) \
1433 AS2( paddd xmm7, xmm1) \
1434 AS2( pand xmm2, xmm3) \
1435 AS2( psrld xmm3, 16) \
1436 AS2( paddd xmm6, xmm6) \
1437 AS2( paddd xmm7, xmm7) \
1438 AS2( paddd xmm4, xmm2) \
1439 AS2( paddd xmm5, xmm3) \
1440 AS2( movq xmm0, QWORD PTR [esp+4])\
1441 AS2( movq xmm1, QWORD PTR [esp+12])\
1442 AS2( paddd xmm4, xmm0)\
1443 AS2( paddd xmm5, xmm1)\
1445 #define Squ_Column0(k, i) \
1446 Squ_SSE2_SaveShift(k) \
1449 SSE2_FirstMultiply(1)\
1451 AS2( paddd xmm6, xmm6) \
1452 AS2( paddd xmm7, xmm7) \
1453 AS2( paddd xmm4, xmm4) \
1454 AS2( paddd xmm5, xmm5) \
1455 AS2( movq xmm0, QWORD PTR [esp+4])\
1456 AS2( movq xmm1, QWORD PTR [esp+12])\
1457 AS2( paddd xmm4, xmm0)\
1458 AS2( paddd xmm5, xmm1)\
1460 #define SSE2_MulAdd45 \
1461 AS2( movdqa xmm7, [esi]) \
1462 AS2( movdqa xmm0, [edi]) \
1463 AS2( pmuludq xmm0, xmm7) \
1464 AS2( movdqa xmm2, [ebx]) \
1465 AS2( pmuludq xmm7, [edx]) \
1466 AS2( movdqa xmm6, xmm2) \
1467 AS2( pand xmm2, xmm0) \
1468 AS2( psrld xmm0, 16) \
1469 AS2( paddd xmm4, xmm2) \
1470 AS2( paddd xmm5, xmm0) \
1471 AS2( pand xmm6, xmm7) \
1472 AS2( psrld xmm7, 16)
1474 #define Mul_Begin(n) \
1477 AS2( and esp, 0xfffffff0)\
1478 AS2( sub esp, 48*n+16)\
1480 AS2( xor edx, edx) \
1482 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1483 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1484 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1485 AS2( movdqa [esp+20+2*edx], xmm0) \
1486 AS2( psrlq xmm0, 32) \
1487 AS2( movdqa [esp+20+2*edx+16], xmm0) \
1488 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1489 AS2( psrlq xmm1, 32) \
1490 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1491 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1492 AS2( psrlq xmm2, 32) \
1493 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1495 AS2( cmp edx, 8*(n)) \
1497 AS2( lea edi, [esp+20])\
1498 AS2( lea edx, [esp+20+16*n])\
1499 AS2( lea esi, [esp+20+32*n])\
1500 SSE2_FirstMultiply(0) \
1502 #define Mul_Acc(i) \
1504 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1505 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1506 AS2( movdqa xmm2, [ebx]) \
1507 AS2( pmuludq xmm0, xmm1) \
1508 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1509 AS2( movdqa xmm3, xmm2) \
1510 AS2( pand xmm2, xmm0) \
1511 AS2( psrld xmm0, 16) \
1512 AS2( paddd xmm4, xmm2) \
1513 AS2( paddd xmm5, xmm0) \
1514 AS2( pand xmm3, xmm1) \
1515 AS2( psrld xmm1, 16) \
1516 AS2( paddd xmm6, xmm3) \
1517 AS2( paddd xmm7, xmm1) \
1520 #define Mul_Acc2(i) ASC(call, LMul##i)
1521 #define Mul_Acc3(i) Mul_Acc2(i)
1522 #define Mul_Acc4(i) Mul_Acc2(i)
1523 #define Mul_Acc5(i) Mul_Acc2(i)
1524 #define Mul_Acc6(i) Mul_Acc2(i)
1525 #define Mul_Acc7(i) Mul_Acc2(i)
1526 #define Mul_Acc8(i) Mul_Acc2(i)
1527 #define Mul_Acc9(i) Mul_Acc2(i)
1528 #define Mul_Acc10(i) Mul_Acc2(i)
1529 #define Mul_Acc11(i) Mul_Acc2(i)
1530 #define Mul_Acc12(i) Mul_Acc2(i)
1531 #define Mul_Acc13(i) Mul_Acc2(i)
1532 #define Mul_Acc14(i) Mul_Acc2(i)
1533 #define Mul_Acc15(i) Mul_Acc2(i)
1534 #define Mul_Acc16(i) Mul_Acc2(i)
1536 #define Mul_Column1(k, i) \
1542 #define Mul_Column0(k, i) \
1549 #define Bot_Acc(i) \
1550 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1551 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1552 AS2( pmuludq xmm0, xmm1) \
1553 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1554 AS2( paddq xmm4, xmm0) \
1555 AS2( paddd xmm6, xmm1)
1557 #define Bot_SaveAcc(k) \
1561 AS2( movdqa xmm6, [esi]) \
1562 AS2( movdqa xmm0, [edi]) \
1563 AS2( pmuludq xmm0, xmm6) \
1564 AS2( paddq xmm4, xmm0) \
1565 AS2( psllq xmm5, 16) \
1566 AS2( paddq xmm4, xmm5) \
1567 AS2( pmuludq xmm6, [edx])
1569 #define Bot_End(n) \
1570 AS2( movhlps xmm7, xmm6) \
1571 AS2( paddd xmm6, xmm7) \
1572 AS2( psllq xmm6, 32) \
1573 AS2( paddd xmm4, xmm6) \
1574 AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \
1578 #define Top_Begin(n) \
1581 AS2( and esp, 0xfffffff0)\
1582 AS2( sub esp, 48*n+16)\
1584 AS2( xor edx, edx) \
1586 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1587 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1588 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1589 AS2( movdqa [esp+20+2*edx], xmm0) \
1590 AS2( psrlq xmm0, 32) \
1591 AS2( movdqa [esp+20+2*edx+16], xmm0) \
1592 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1593 AS2( psrlq xmm1, 32) \
1594 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1595 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1596 AS2( psrlq xmm2, 32) \
1597 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1599 AS2( cmp edx, 8*(n)) \
1601 AS2( mov eax, esi) \
1602 AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\
1603 AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\
1604 AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\
1605 AS2( pxor xmm4, xmm4)\
1606 AS2( pxor xmm5, xmm5)
1608 #define Top_Acc(i) \
1609 AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \
1610 AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1611 AS2( psrlq xmm0, 48) \
1612 AS2( paddd xmm5, xmm0)\
1614 #define Top_Column0(i) \
1615 AS2( psllq xmm5, 32) \
1621 #define Top_Column1(i) \
1627 AS2( movd xmm0, eax)\
1628 AS2( movd xmm1, [ecx+4])\
1629 AS2( psrld xmm1, 16)\
1630 AS2( pcmpgtd xmm1, xmm0)\
1631 AS2( psrld xmm1, 31)\
1632 AS2( paddd xmm4, xmm1)\
1634 void SSE2_Square4(word *C,
const word *A)
1641 void SSE2_Square8(word *C, const word *A)
1657 void SSE2_Square16(word *C, const word *A)
1662 Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1681 void SSE2_Square32(word *C, const word *A)
1685 Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1719 void SSE2_Multiply4(word *C, const word *A, const word *B)
1731 void SSE2_Multiply8(word *C, const word *A, const word *B)
1736 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1747 void SSE2_Multiply16(word *C, const word *A, const word *B)
1752 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1771 void SSE2_Multiply32(word *C, const word *A, const word *B)
1775 Mul_Acc(16) Mul_Acc(15) Mul_Acc(14) Mul_Acc(13) Mul_Acc(12) Mul_Acc(11) Mul_Acc(10) Mul_Acc(9) Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1809 void SSE2_MultiplyBottom4(word *C, const word *A, const word *B)
1812 Bot_SaveAcc(0) Bot_Acc(2)
1816 void SSE2_MultiplyBottom8(word *C, const word *A, const word *B)
1821 Mul_Acc(3) Mul_Acc(2)
1826 Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1830 void SSE2_MultiplyBottom16(word *C, const word *A, const word *B)
1835 Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1844 Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1848 void SSE2_MultiplyBottom32(word *C, const word *A, const word *B)
1853 Mul_Acc(15) Mul_Acc(14) Mul_Acc(13) Mul_Acc(12) Mul_Acc(11) Mul_Acc(10) Mul_Acc(9) Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1870 Bot_SaveAcc(14) Bot_Acc(16) Bot_Acc(15) Bot_Acc(14) Bot_Acc(13) Bot_Acc(12) Bot_Acc(11) Bot_Acc(10) Bot_Acc(9) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1874 void SSE2_MultiplyTop8(word *C, const word *A, const word *B, word L)
1877 Top_Acc(3) Top_Acc(2) Top_Acc(1)
1880 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1889 void SSE2_MultiplyTop16(word *C, const word *A, const word *B, word L)
1892 Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1895 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1908 void SSE2_MultiplyTop32(word *C, const word *A, const word *B, word L)
1911 Top_Acc(15) Top_Acc(14) Top_Acc(13) Top_Acc(12) Top_Acc(11) Top_Acc(10) Top_Acc(9) Top_Acc(8) Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1914 Mul_Acc(16) Mul_Acc(15) Mul_Acc(14) Mul_Acc(13) Mul_Acc(12) Mul_Acc(11) Mul_Acc(10) Mul_Acc(9) Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1935 #endif // #if CRYPTOPP_INTEGER_SSE2
1939 typedef int (CRYPTOPP_FASTCALL * PAdd)(
size_t N, word *C,
const word *A,
const word *B);
1940 typedef void (* PMul)(word *C,
const word *A,
const word *B);
1941 typedef void (* PSqu)(word *C,
const word *A);
1942 typedef void (* PMulTop)(word *C,
const word *A,
const word *B, word L);
1944 #if CRYPTOPP_INTEGER_SSE2
1945 static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
1946 static size_t s_recursionLimit = 8;
1948 static const size_t s_recursionLimit = 16;
1951 static PMul s_pMul[9], s_pBot[9];
1952 static PSqu s_pSqu[9];
1953 static PMulTop s_pTop[9];
1955 static void SetFunctionPointers()
1957 s_pMul[0] = &Baseline_Multiply2;
1958 s_pBot[0] = &Baseline_MultiplyBottom2;
1959 s_pSqu[0] = &Baseline_Square2;
1960 s_pTop[0] = &Baseline_MultiplyTop2;
1961 s_pTop[1] = &Baseline_MultiplyTop4;
1963 #if CRYPTOPP_INTEGER_SSE2
1966 #if _MSC_VER != 1200 || defined(NDEBUG)
1974 s_recursionLimit = 32;
1976 s_pMul[1] = &SSE2_Multiply4;
1977 s_pMul[2] = &SSE2_Multiply8;
1978 s_pMul[4] = &SSE2_Multiply16;
1979 s_pMul[8] = &SSE2_Multiply32;
1981 s_pBot[1] = &SSE2_MultiplyBottom4;
1982 s_pBot[2] = &SSE2_MultiplyBottom8;
1983 s_pBot[4] = &SSE2_MultiplyBottom16;
1984 s_pBot[8] = &SSE2_MultiplyBottom32;
1986 s_pSqu[1] = &SSE2_Square4;
1987 s_pSqu[2] = &SSE2_Square8;
1988 s_pSqu[4] = &SSE2_Square16;
1989 s_pSqu[8] = &SSE2_Square32;
1991 s_pTop[2] = &SSE2_MultiplyTop8;
1992 s_pTop[4] = &SSE2_MultiplyTop16;
1993 s_pTop[8] = &SSE2_MultiplyTop32;
1998 s_pMul[1] = &Baseline_Multiply4;
1999 s_pMul[2] = &Baseline_Multiply8;
2001 s_pBot[1] = &Baseline_MultiplyBottom4;
2002 s_pBot[2] = &Baseline_MultiplyBottom8;
2004 s_pSqu[1] = &Baseline_Square4;
2005 s_pSqu[2] = &Baseline_Square8;
2007 s_pTop[2] = &Baseline_MultiplyTop8;
2009 #if !CRYPTOPP_INTEGER_SSE2
2010 s_pMul[4] = &Baseline_Multiply16;
2011 s_pBot[4] = &Baseline_MultiplyBottom16;
2012 s_pSqu[4] = &Baseline_Square16;
2013 s_pTop[4] = &Baseline_MultiplyTop16;
2018 inline int Add(word *C,
const word *A,
const word *B,
size_t N)
2020 #if CRYPTOPP_INTEGER_SSE2
2021 return s_pAdd(N, C, A, B);
2023 return Baseline_Add(N, C, A, B);
2027 inline int Subtract(word *C,
const word *A,
const word *B,
size_t N)
2029 #if CRYPTOPP_INTEGER_SSE2
2030 return s_pSub(N, C, A, B);
2032 return Baseline_Sub(N, C, A, B);
2059 void RecursiveMultiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2061 assert(N>=2 && N%2==0);
2063 if (N <= s_recursionLimit)
2064 s_pMul[N/4](R, A, B);
2067 const size_t N2 = N/2;
2069 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2070 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2072 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2073 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2075 RecursiveMultiply(R2, T2, A1, B1, N2);
2076 RecursiveMultiply(T0, T2, R0, R1, N2);
2077 RecursiveMultiply(R0, T2, A0, B0, N2);
2081 int c2 = Add(R2, R2, R1, N2);
2083 c2 += Add(R1, R2, R0, N2);
2084 c3 += Add(R2, R2, R3, N2);
2087 c3 -= Subtract(R1, R1, T0, N);
2089 c3 += Add(R1, R1, T0, N);
2091 c3 += Increment(R2, N2, c2);
2092 assert (c3 >= 0 && c3 <= 2);
2093 Increment(R3, N2, c3);
2101 void RecursiveSquare(word *R, word *T,
const word *A,
size_t N)
2103 assert(N && N%2==0);
2105 if (N <= s_recursionLimit)
2109 const size_t N2 = N/2;
2111 RecursiveSquare(R0, T2, A0, N2);
2112 RecursiveSquare(R2, T2, A1, N2);
2113 RecursiveMultiply(T0, T2, A0, A1, N2);
2115 int carry = Add(R1, R1, T0, N);
2116 carry += Add(R1, R1, T0, N);
2117 Increment(R3, N2, carry);
2126 void RecursiveMultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2128 assert(N>=2 && N%2==0);
2130 if (N <= s_recursionLimit)
2131 s_pBot[N/4](R, A, B);
2134 const size_t N2 = N/2;
2136 RecursiveMultiply(R, T, A0, B0, N2);
2137 RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2138 Add(R1, R1, T0, N2);
2139 RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2140 Add(R1, R1, T0, N2);
2150 void MultiplyTop(word *R, word *T,
const word *L,
const word *A,
const word *B,
size_t N)
2152 assert(N>=2 && N%2==0);
2154 if (N <= s_recursionLimit)
2155 s_pTop[N/4](R, A, B, L[N-1]);
2158 const size_t N2 = N/2;
2160 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2161 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2163 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2164 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2166 RecursiveMultiply(T0, T2, R0, R1, N2);
2167 RecursiveMultiply(R0, T2, A1, B1, N2);
2172 int c2 = Subtract(T2, L+N2, L, N2);
2176 c2 -= Add(T2, T2, T0, N2);
2177 t = (Compare(T2, R0, N2) == -1);
2178 c3 = t - Subtract(T2, T2, T1, N2);
2182 c2 += Subtract(T2, T2, T0, N2);
2183 t = (Compare(T2, R0, N2) == -1);
2184 c3 = t + Add(T2, T2, T1, N2);
2189 c3 += Increment(T2, N2, c2);
2191 c3 -= Decrement(T2, N2, -c2);
2192 c3 += Add(R0, T2, R1, N2);
2194 assert (c3 >= 0 && c3 <= 2);
2195 Increment(R1, N2, c3);
2199 inline void Multiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2201 RecursiveMultiply(R, T, A, B, N);
2204 inline void Square(word *R, word *T,
const word *A,
size_t N)
2206 RecursiveSquare(R, T, A, N);
2209 inline void MultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2211 RecursiveMultiplyBottom(R, T, A, B, N);
2219 void AsymmetricMultiply(word *R, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2226 Multiply(R, T, A, B, NA);
2237 assert(NB % NA == 0);
2244 SetWords(R, 0, NB+2);
2247 CopyWords(R, B, NB);
2248 R[NB] = R[NB+1] = 0;
2251 R[NB] = LinearMultiply(R, B, A[0], NB);
2260 Multiply(R, T, A, B, NA);
2261 CopyWords(T+2*NA, R+NA, NA);
2263 for (i=2*NA; i<NB; i+=2*NA)
2264 Multiply(T+NA+i, T, A, B+i, NA);
2265 for (i=NA; i<NB; i+=2*NA)
2266 Multiply(R+i, T, A, B+i, NA);
2270 for (i=0; i<NB; i+=2*NA)
2271 Multiply(R+i, T, A, B+i, NA);
2272 for (i=NA; i<NB; i+=2*NA)
2273 Multiply(T+NA+i, T, A, B+i, NA);
2276 if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2277 Increment(R+NB, NA);
2284 void RecursiveInverseModPower2(word *R, word *T,
const word *A,
size_t N)
2288 T[0] = AtomicInverseModPower2(A[0]);
2290 s_pBot[0](T+2, T, A);
2291 TwosComplement(T+2, 2);
2292 Increment(T+2, 2, 2);
2293 s_pBot[0](R, T, T+2);
2297 const size_t N2 = N/2;
2298 RecursiveInverseModPower2(R0, T0, A0, N2);
2300 SetWords(T0+1, 0, N2-1);
2301 MultiplyTop(R1, T1, T0, R0, A0, N2);
2302 MultiplyBottom(T0, T1, R0, A1, N2);
2303 Add(T0, R1, T0, N2);
2304 TwosComplement(T0, N2);
2305 MultiplyBottom(R1, T1, R0, T0, N2);
2315 void MontgomeryReduce(word *R, word *T, word *X,
const word *M,
const word *U,
size_t N)
2318 MultiplyBottom(R, T, X, U, N);
2319 MultiplyTop(T, T+N, X, R, M, N);
2320 word borrow = Subtract(T, X+N, T, N);
2322 word carry = Add(T+N, T, M, N);
2323 assert(carry | !borrow);
2324 CopyWords(R, T + ((0-borrow) & N), N);
2326 const word u = 0-U[0];
2328 for (
size_t i=0; i<N; i++)
2330 const word t = u * X[i];
2332 for (
size_t j=0; j<N; j+=2)
2334 MultiplyWords(p, t, M[j]);
2335 Acc2WordsBy1(p, X[i+j]);
2337 X[i+j] = LowWord(p);
2339 MultiplyWords(p, t, M[j+1]);
2340 Acc2WordsBy1(p, X[i+j+1]);
2342 X[i+j+1] = LowWord(p);
2346 if (Increment(X+N+i, N-i, c))
2347 while (!Subtract(X+N, X+N, M, N)) {}
2350 memcpy(R, X+N, N*WORD_SIZE);
2352 __m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2353 for (
size_t i=0; i<N; i++)
2355 __m64 t = _mm_cvtsi32_si64(X[i]);
2356 t = _mm_mul_su32(t, u);
2357 __m64 c = _mm_setzero_si64();
2358 for (
size_t j=0; j<N; j+=2)
2360 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2361 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2362 c = _mm_add_si64(c, p);
2363 X[i+j] = _mm_cvtsi64_si32(c);
2364 c = _mm_srli_si64(c, 32);
2365 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2366 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2367 c = _mm_add_si64(c, p);
2368 X[i+j+1] = _mm_cvtsi64_si32(c);
2369 c = _mm_srli_si64(c, 32);
2372 if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2373 while (!Subtract(X+N, X+N, M, N)) {}
2376 memcpy(R, X+N, N*WORD_SIZE);
2388 void HalfMontgomeryReduce(word *R, word *T,
const word *X,
const word *M,
const word *U,
const word *V,
size_t N)
2390 assert(N%2==0 && N>=4);
2402 const size_t N2 = N/2;
2403 Multiply(T0, T2, V0, X3, N2);
2404 int c2 = Add(T0, T0, X0, N);
2405 MultiplyBottom(T3, T2, T0, U, N2);
2406 MultiplyTop(T2, R, T0, T3, M0, N2);
2407 c2 -= Subtract(T2, T1, T2, N2);
2408 Multiply(T0, R, T3, M1, N2);
2409 c2 -= Subtract(T0, T2, T0, N2);
2410 int c3 = -(int)Subtract(T1, X2, T1, N2);
2411 Multiply(R0, T2, V1, X3, N2);
2412 c3 += Add(R, R, T, N);
2415 c3 += Increment(R1, N2);
2417 c3 -= Decrement(R1, N2, -c2);
2419 assert(c3>=-1 && c3<=1);
2421 Subtract(R, R, M, N);
2515 static inline void AtomicDivide(word *Q,
const word *A,
const word *B)
2518 DWord q = DivideFourWordsByTwo<word, DWord>(T,
DWord(A[0], A[1]),
DWord(A[2], A[3]),
DWord(B[0], B[1]));
2519 Q[0] = q.GetLowHalf();
2520 Q[1] = q.GetHighHalf();
2526 assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2530 assert(memcmp(P, A, 4*WORD_SIZE)==0);
2536 static void CorrectQuotientEstimate(word *R, word *T, word *Q,
const word *B,
size_t N)
2538 assert(N && N%2==0);
2540 AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2542 word borrow = Subtract(R, R, T, N+2);
2543 assert(!borrow && !R[N+1]);
2545 while (R[N] || Compare(R, B, N) >= 0)
2547 R[N] -= Subtract(R, R, B, N);
2548 Q[1] += (++Q[0]==0);
2549 assert(Q[0] || Q[1]);
2559 void Divide(word *R, word *Q, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2561 assert(NA && NB && NA%2==0 && NB%2==0);
2562 assert(B[NB-1] || B[NB-2]);
2567 word *
const TB=T+NA+2;
2568 word *
const TP=T+NA+2+NB;
2571 unsigned shiftWords = (B[NB-1]==0);
2572 TB[0] = TB[NB-1] = 0;
2573 CopyWords(TB+shiftWords, B, NB-shiftWords);
2574 unsigned shiftBits = WORD_BITS - BitPrecision(TB[NB-1]);
2575 assert(shiftBits < WORD_BITS);
2576 ShiftWordsLeftByBits(TB, NB, shiftBits);
2579 TA[0] = TA[NA] = TA[NA+1] = 0;
2580 CopyWords(TA+shiftWords, A, NA);
2581 ShiftWordsLeftByBits(TA, NA+2, shiftBits);
2583 if (TA[NA+1]==0 && TA[NA] <= 1)
2585 Q[NA-NB+1] = Q[NA-NB] = 0;
2586 while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
2588 TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
2595 assert(Compare(TA+NA-NB, TB, NB) < 0);
2599 BT[0] = TB[NB-2] + 1;
2600 BT[1] = TB[NB-1] + (BT[0]==0);
2603 for (
size_t i=NA-2; i>=NB; i-=2)
2605 AtomicDivide(Q+i-NB, TA+i-2, BT);
2606 CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
2610 CopyWords(R, TA+shiftWords, NB);
2611 ShiftWordsRightByBits(R, NB, shiftBits);
2614 static inline size_t EvenWordCount(
const word *X,
size_t N)
2616 while (N && X[N-2]==0 && X[N-1]==0)
2627 unsigned int AlmostInverse(word *R, word *T,
const word *A,
size_t NA,
const word *M,
size_t N)
2629 assert(NA<=N && N && N%2==0);
2635 size_t bcLen=2, fgLen=EvenWordCount(M, N);
2639 SetWords(T, 0, 3*N);
2641 CopyWords(f, A, NA);
2649 if (EvenWordCount(f, fgLen)==0)
2655 ShiftWordsRightByWords(f, fgLen, 1);
2656 bcLen += 2 * (c[bcLen-1] != 0);
2658 ShiftWordsLeftByWords(c, bcLen, 1);
2663 unsigned int i = TrailingZeros(t);
2667 if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0)
2670 Subtract(R, M, b, N);
2676 ShiftWordsRightByBits(f, fgLen, i);
2677 t = ShiftWordsLeftByBits(c, bcLen, i);
2679 bcLen += 2 * (t!=0);
2682 bool swap = Compare(f, g, fgLen)==-1;
2683 ConditionalSwapPointers(swap, f, g);
2684 ConditionalSwapPointers(swap, b, c);
2687 fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]);
2689 Subtract(f, f, g, fgLen);
2690 t = Add(b, b, c, bcLen);
2701 void DivideByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2708 ShiftWordsRightByBits(R, N, 1);
2711 word carry = Add(R, R, M, N);
2712 ShiftWordsRightByBits(R, N, 1);
2713 R[N-1] += carry<<(WORD_BITS-1);
2722 void MultiplyByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2727 if (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0)
2728 Subtract(R, R, M, N);
2733 InitializeInteger::InitializeInteger()
2735 if (!g_pAssignIntToInteger)
2737 SetFunctionPointers();
2738 g_pAssignIntToInteger = AssignIntToInteger;
2742 static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
2744 static inline size_t RoundupSize(
size_t n)
2747 return RoundupSizeTable[n];
2754 else return size_t(1) << BitPrecision(n-1);
2758 : reg(2), sign(POSITIVE)
2760 reg[0] = reg[1] = 0;
2764 : reg(RoundupSize(t.WordCount())), sign(t.sign)
2766 CopyWords(reg, t.reg, reg.size());
2772 reg[0] = word(value);
2773 reg[1] = word(SafeRightShift<WORD_BITS>(value));
2786 reg[0] = word(value);
2787 reg[1] = word(SafeRightShift<WORD_BITS>((
unsigned long)value));
2802 unsigned long value = (
unsigned long)reg[0];
2803 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2806 return (
signed long)value >= 0;
2808 return -(
signed long)value < 0;
2815 unsigned long value = (
unsigned long)reg[0];
2816 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2817 return sign==POSITIVE ? value : -(
signed long)value;
2822 Decode(encodedInteger, byteCount, s);
2827 Decode(encodedInteger, byteCount, s);
2837 Randomize(rng, bitcount);
2842 if (!Randomize(rng, min, max, rnType, equiv, mod))
2848 Integer r((word)0, BitsToWords(e+1));
2877 bool Integer::operator!()
const
2879 return IsNegative() ?
false : (reg[0]==0 &&
WordCount()==0);
2886 if (reg.size() != t.reg.size() || t.reg[t.reg.size()/2] == 0)
2888 CopyWords(reg, t.reg, reg.size());
2896 if (n/WORD_BITS >= reg.size())
2899 return bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1);
2906 reg.
CleanGrow(RoundupSize(BitsToWords(n+1)));
2907 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
2911 if (n/WORD_BITS < reg.size())
2912 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
2918 if (n/WORD_SIZE >= reg.size())
2921 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
2926 reg.
CleanGrow(RoundupSize(BytesToWords(n+1)));
2927 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
2928 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
2934 assert(n <=
sizeof(v)*8);
2935 for (
unsigned int j=0; j<n; j++)
2936 v |= lword(
GetBit(i+j)) << j;
2940 Integer Integer::operator-()
const
2947 Integer Integer::AbsoluteValue()
const
2950 result.sign = POSITIVE;
2954 void Integer::swap(
Integer &a)
2957 std::swap(sign, a.sign);
2961 : reg(RoundupSize(length)), sign(POSITIVE)
2964 SetWords(reg+1, 0, reg.size()-1);
2968 static Integer StringToInteger(
const T *str)
2973 unsigned int length;
2974 for (length = 0; str[length] != 0; length++) {}
2981 switch (str[length-1])
2999 if (length > 2 && str[0] ==
'0' && str[1] ==
'x')
3002 for (
unsigned i=0; i<length; i++)
3006 if (str[i] >=
'0' && str[i] <=
'9')
3007 digit = str[i] -
'0';
3008 else if (str[i] >=
'A' && str[i] <=
'F')
3009 digit = str[i] -
'A' + 10;
3010 else if (str[i] >=
'a' && str[i] <=
'f')
3011 digit = str[i] -
'a' + 10;
3029 : reg(2), sign(POSITIVE)
3031 *
this = StringToInteger(str);
3035 : reg(2), sign(POSITIVE)
3037 *
this = StringToInteger(str);
3042 return (
unsigned int)CountWords(reg, reg.size());
3049 return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
3058 return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
3063 void Integer::Decode(
const byte *input,
size_t inputLen, Signedness s)
3066 Decode(store, inputLen, s);
3075 sign = ((s==SIGNED) && (b & 0x80)) ? NEGATIVE : POSITIVE;
3077 while (inputLen>0 && (sign==POSITIVE ? b==0 : b==0xff))
3084 reg.
CleanNew(RoundupSize(BytesToWords(inputLen)));
3086 for (
size_t i=inputLen; i > 0; i--)
3089 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
3092 if (sign == NEGATIVE)
3094 for (
size_t i=inputLen; i<reg.size()*WORD_SIZE; i++)
3095 reg[i/WORD_SIZE] |= word(0xff) << (i%WORD_SIZE)*8;
3096 TwosComplement(reg, reg.size());
3102 unsigned int outputLen = STDMAX(1U,
ByteCount());
3103 if (signedness == UNSIGNED)
3105 if (NotNegative() && (
GetByte(outputLen-1) & 0x80))
3107 if (IsNegative() && *
this < -
Power2(outputLen*8-1))
3115 Encode(sink, outputLen, signedness);
3120 if (signedness == UNSIGNED || NotNegative())
3122 for (
size_t i=outputLen; i > 0; i--)
3129 temp.
Encode(bt, outputLen, UNSIGNED);
3140 void Integer::BERDecode(
const byte *input,
size_t len)
3149 if (!dec.IsDefiniteLength() || dec.
MaxRetrievable() < dec.RemainingLength())
3151 Decode(dec, (
size_t)dec.RemainingLength(), SIGNED);
3165 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
3167 Decode(dec, length);
3181 size_t byteCount = BitsToBytes(bitCount);
3183 return 2 + byteCount;
3186 void Integer::OpenPGPDecode(
const byte *input,
size_t len)
3189 OpenPGPDecode(store);
3196 throw OpenPGPDecodeErr();
3197 Decode(bt, BitsToBytes(bitCount));
3202 const size_t nbytes = nbits/8 + 1;
3206 buf[0] = (byte)Crop(buf[0], nbits % 8);
3207 Decode(buf, nbytes, UNSIGNED);
3216 const unsigned int nbits = range.
BitCount();
3220 Randomize(rng, nbits);
3222 while (*
this > range);
3229 return GenerateRandomNoThrow(rng, MakeParameters(
"Min", min)(
"Max", max)(
"RandomNumberType", rnType)(
"EquivalentTo", equiv)(
"Mod", mod));
3235 KDF2_RNG(
const byte *seed,
size_t seedSize)
3236 : m_counter(0), m_counterAndSeed(seedSize + 4)
3238 memcpy(m_counterAndSeed + 4, seed, seedSize);
3243 PutWord(
false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3271 if (equiv.IsNegative() || equiv >= mod)
3272 throw InvalidArgument(
"Integer: invalid EquivalentTo and/or Mod argument");
3274 Integer::RandomNumberType rnType = params.
GetValueWithDefault(
"RandomNumberType", Integer::ANY);
3286 DEREncodeUnsigned(seq, rnType);
3287 DEREncodeOctetString(seq, seed.begin(), seed.size());
3291 bq.
Get(finalSeed, finalSeed.size());
3292 kdf2Rng.reset(
new KDF2_RNG(finalSeed.begin(), finalSeed.size()));
3300 Randomize(rng, min, max);
3303 Integer min1 = min + (equiv-min)%mod;
3306 Randomize(rng,
Zero(), (max - min1) / mod);
3324 if (FirstPrime(first, max, equiv, mod, pSelector))
3328 if (!FirstPrime(first, max, equiv, mod, pSelector))
3335 Randomize(rng, min, max);
3336 if (FirstPrime(*
this, STDMIN(*
this+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector))
3346 std::istream& operator>>(std::istream& in,
Integer &a)
3349 unsigned int length = 0;
3358 if (length >= str.size())
3359 str.Grow(length + 16);
3361 while (in && (c==
'-' || c==
'x' || (c>=
'0' && c<=
'9') || (c>=
'a' && c<=
'f') || (c>=
'A' && c<=
'F') || c==
'h' || c==
'H' || c==
'o' || c==
'O' || c==
',' || c==
'.'));
3365 str[length-1] =
'\0';
3371 std::ostream& operator<<(std::ostream& out,
const Integer &a)
3374 long f = out.flags() & std::ios::basefield;
3379 case std::ios::oct :
3384 case std::ios::hex :
3406 static const char upper[]=
"0123456789ABCDEF";
3407 static const char lower[]=
"0123456789abcdef";
3409 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3427 return out << suffix;
3430 Integer& Integer::operator++()
3434 if (Increment(reg, reg.size()))
3437 reg[reg.size()/2]=1;
3442 word borrow = Decrement(reg, reg.size());
3450 Integer& Integer::operator--()
3454 if (Increment(reg, reg.size()))
3457 reg[reg.size()/2]=1;
3462 if (Decrement(reg, reg.size()))
3471 if (a.reg.size() == b.reg.size())
3472 carry = Add(sum.reg, a.reg, b.reg, a.reg.size());
3473 else if (a.reg.size() > b.reg.size())
3475 carry = Add(sum.reg, a.reg, b.reg, b.reg.size());
3476 CopyWords(sum.reg+b.reg.size(), a.reg+b.reg.size(), a.reg.size()-b.reg.size());
3477 carry = Increment(sum.reg+b.reg.size(), a.reg.size()-b.reg.size(), carry);
3481 carry = Add(sum.reg, a.reg, b.reg, a.reg.size());
3482 CopyWords(sum.reg+a.reg.size(), b.reg+a.reg.size(), b.reg.size()-a.reg.size());
3483 carry = Increment(sum.reg+a.reg.size(), b.reg.size()-a.reg.size(), carry);
3489 sum.reg[sum.reg.size()/2] = 1;
3491 sum.sign = Integer::POSITIVE;
3503 if (Compare(a.reg, b.reg, aSize) >= 0)
3505 Subtract(diff.reg, a.reg, b.reg, aSize);
3506 diff.sign = Integer::POSITIVE;
3510 Subtract(diff.reg, b.reg, a.reg, aSize);
3511 diff.sign = Integer::NEGATIVE;
3514 else if (aSize > bSize)
3516 word borrow = Subtract(diff.reg, a.reg, b.reg, bSize);
3517 CopyWords(diff.reg+bSize, a.reg+bSize, aSize-bSize);
3518 borrow = Decrement(diff.reg+bSize, aSize-bSize, borrow);
3520 diff.sign = Integer::POSITIVE;
3524 word borrow = Subtract(diff.reg, b.reg, a.reg, aSize);
3525 CopyWords(diff.reg+aSize, b.reg+aSize, bSize-aSize);
3526 borrow = Decrement(diff.reg+aSize, bSize-aSize, borrow);
3528 diff.sign = Integer::NEGATIVE;
3533 template <
class T>
inline const T& STDMAX2(
const T& a,
const T& b)
3535 return a < b ? b : a;
3540 Integer sum((word)0, STDMAX2(reg.size(), b.reg.size()));
3543 if (b.NotNegative())
3544 PositiveAdd(sum, *
this, b);
3546 PositiveSubtract(sum, *
this, b);
3550 if (b.NotNegative())
3551 PositiveSubtract(sum, b, *
this);
3554 PositiveAdd(sum, *
this, b);
3555 sum.sign = Integer::NEGATIVE;
3566 if (t.NotNegative())
3567 PositiveAdd(*
this, *
this, t);
3569 PositiveSubtract(*
this, *
this, t);
3573 if (t.NotNegative())
3574 PositiveSubtract(*
this, t, *
this);
3577 PositiveAdd(*
this, *
this, t);
3578 sign = Integer::NEGATIVE;
3586 Integer diff((word)0, STDMAX2(reg.size(), b.reg.size()));
3589 if (b.NotNegative())
3590 PositiveSubtract(diff, *
this, b);
3592 PositiveAdd(diff, *
this, b);
3596 if (b.NotNegative())
3598 PositiveAdd(diff, *
this, b);
3599 diff.sign = Integer::NEGATIVE;
3602 PositiveSubtract(diff, b, *
this);
3612 if (t.NotNegative())
3613 PositiveSubtract(*
this, *
this, t);
3615 PositiveAdd(*
this, *
this, t);
3619 if (t.NotNegative())
3621 PositiveAdd(*
this, *
this, t);
3622 sign = Integer::NEGATIVE;
3625 PositiveSubtract(*
this, t, *
this);
3630 Integer& Integer::operator<<=(
size_t n)
3633 const size_t shiftWords = n / WORD_BITS;
3634 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3636 reg.
CleanGrow(RoundupSize(wordCount+BitsToWords(n)));
3637 ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords);
3638 ShiftWordsLeftByBits(reg+shiftWords, wordCount+BitsToWords(shiftBits), shiftBits);
3642 Integer& Integer::operator>>=(
size_t n)
3645 const size_t shiftWords = n / WORD_BITS;
3646 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3648 ShiftWordsRightByWords(reg, wordCount, shiftWords);
3649 if (wordCount > shiftWords)
3650 ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits);
3658 size_t aSize = RoundupSize(a.
WordCount());
3659 size_t bSize = RoundupSize(b.
WordCount());
3661 product.reg.
CleanNew(RoundupSize(aSize+bSize));
3662 product.sign = Integer::POSITIVE;
3665 AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
3670 PositiveMultiply(product, a, b);
3672 if (a.NotNegative() != b.NotNegative())
3679 Multiply(product, *
this, b);
3717 remainder.sign = Integer::POSITIVE;
3725 remainder.reg.
CleanNew(RoundupSize(bSize));
3726 remainder.sign = Integer::POSITIVE;
3727 quotient.reg.
CleanNew(RoundupSize(aSize-bSize+2));
3728 quotient.sign = Integer::POSITIVE;
3731 Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
3736 PositiveDivide(remainder, quotient, dividend, divisor);
3738 if (dividend.IsNegative())
3741 if (remainder.NotZero())
3744 remainder = divisor.AbsoluteValue() - remainder;
3748 if (divisor.IsNegative())
3757 const size_t wordCount = BitsToWords(n);
3760 r.reg.
resize(RoundupSize(wordCount));
3761 CopyWords(r.reg, a.reg, wordCount);
3762 SetWords(r.reg+wordCount, 0, r.reg.size()-wordCount);
3763 if (n % WORD_BITS != 0)
3764 r.reg[wordCount-1] %= (word(1) << (n % WORD_BITS));
3769 CopyWords(r.reg, a.reg, r.reg.size());
3773 if (a.IsNegative() && r.NotZero())
3801 if ((divisor & (divisor-1)) == 0)
3803 quotient = dividend >> (BitPrecision(divisor)-1);
3804 remainder = dividend.reg[0] & (divisor-1);
3809 quotient.reg.
CleanNew(RoundupSize(i));
3813 quotient.reg[i] =
DWord(dividend.reg[i], remainder) / divisor;
3814 remainder =
DWord(dividend.reg[i], remainder) % divisor;
3817 if (dividend.NotNegative())
3818 quotient.sign = POSITIVE;
3821 quotient.sign = NEGATIVE;
3825 remainder = divisor - remainder;
3830 Integer Integer::DividedBy(word b)
const
3838 word Integer::Modulo(word divisor)
const
3847 if ((divisor & (divisor-1)) == 0)
3848 remainder = reg[0] & (divisor-1);
3858 remainder = sum % divisor;
3864 remainder =
DWord(reg[i], remainder) % divisor;
3868 if (IsNegative() && remainder)
3869 remainder = divisor - remainder;
3874 void Integer::Negate()
3877 sign = Sign(1-sign);
3880 int Integer::PositiveCompare(
const Integer& t)
const
3885 return CryptoPP::Compare(reg, t.reg, size);
3887 return size > tSize ? 1 : -1;
3894 if (t.NotNegative())
3895 return PositiveCompare(t);
3901 if (t.NotNegative())
3904 return -PositiveCompare(t);
3915 assert(y*y >= *
this);
3920 y = (x + *
this/x) >> 1;
3929 return *
this == r.Squared();
3934 return (
WordCount() == 1) && (reg[0] == 1);
3950 return mr.Exponentiate(x, e);
3960 assert(m.NotNegative());
3973 return !u ?
Zero() : (m*(*
this-u)+1)/(*this);
3977 Integer r((word)0, m.reg.size());
3978 unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
3979 DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
3985 word g0 = mod, g1 = *
this % mod;
3986 word v0 = 0, v1 = 1;
4014 if (oid != ASN1::prime_field())
4016 m_modulus.BERDecode(seq);
4018 m_result.reg.
resize(m_modulus.reg.size());
4024 ASN1::prime_field().DEREncode(seq);
4031 a.DEREncodeAsOctetString(out, MaxElementByteLength());
4036 a.BERDecodeAsOctetString(in, MaxElementByteLength());
4041 if (a.reg.size()==m_modulus.reg.size())
4043 CryptoPP::DivideByPower2Mod(m_result.reg.begin(), a.reg, 1, m_modulus.reg, a.reg.size());
4047 return m_result1 = (a.IsEven() ? (a >> 1) : ((a+m_modulus) >> 1));
4052 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4054 if (CryptoPP::Add(m_result.reg.begin(), a.reg, b.reg, a.reg.size())
4055 || Compare(m_result.reg, m_modulus.reg, a.reg.size()) >= 0)
4057 CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.size());
4064 if (m_result1 >= m_modulus)
4065 m_result1 -= m_modulus;
4072 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4074 if (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.size())
4075 || Compare(a.reg, m_modulus.reg, a.reg.size()) >= 0)
4077 CryptoPP::Subtract(a.reg, a.reg, m_modulus.reg, a.reg.size());
4092 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4094 if (CryptoPP::Subtract(m_result.reg.begin(), a.reg, b.reg, a.reg.size()))
4095 CryptoPP::Add(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.size());
4101 if (m_result1.IsNegative())
4102 m_result1 += m_modulus;
4109 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4111 if (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.size()))
4112 CryptoPP::Add(a.reg, a.reg, m_modulus.reg, a.reg.size());
4124 const Integer& ModularArithmetic::Inverse(
const Integer &a)
const
4129 CopyWords(m_result.reg.begin(), m_modulus.reg, m_modulus.reg.size());
4130 if (CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, a.reg, a.reg.size()))
4131 Decrement(m_result.reg.begin()+a.reg.size(), m_modulus.reg.size()-a.reg.size());
4138 if (m_modulus.IsOdd())
4141 return dr.ConvertOut(dr.CascadeExponentiate(dr.ConvertIn(x), e1, dr.ConvertIn(y), e2));
4147 void ModularArithmetic::SimultaneousExponentiate(
Integer *results,
const Integer &base,
const Integer *exponents,
unsigned int exponentsCount)
const
4149 if (m_modulus.IsOdd())
4152 dr.SimultaneousExponentiate(results, dr.ConvertIn(base), exponents, exponentsCount);
4153 for (
unsigned int i=0; i<exponentsCount; i++)
4154 results[i] = dr.ConvertOut(results[i]);
4160 MontgomeryRepresentation::MontgomeryRepresentation(
const Integer &m)
4162 m_u((word)0, m_modulus.reg.size()),
4163 m_workspace(5*m_modulus.reg.size())
4165 if (!m_modulus.IsOdd())
4166 throw InvalidArgument(
"MontgomeryRepresentation: Montgomery representation requires an odd modulus");
4168 RecursiveInverseModPower2(m_u.reg, m_workspace, m_modulus.reg, m_modulus.reg.size());
4173 word *
const T = m_workspace.begin();
4174 word *
const R = m_result.reg.begin();
4175 const size_t N = m_modulus.reg.size();
4176 assert(a.reg.size()<=N && b.reg.size()<=N);
4178 AsymmetricMultiply(T, T+2*N, a.reg, a.reg.size(), b.reg, b.reg.size());
4179 SetWords(T+a.reg.size()+b.reg.size(), 0, 2*N-a.reg.size()-b.reg.size());
4180 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4184 const Integer& MontgomeryRepresentation::Square(
const Integer &a)
const
4186 word *
const T = m_workspace.begin();
4187 word *
const R = m_result.reg.begin();
4188 const size_t N = m_modulus.reg.size();
4189 assert(a.reg.size()<=N);
4191 CryptoPP::Square(T, T+2*N, a.reg, a.reg.size());
4192 SetWords(T+2*a.reg.size(), 0, 2*N-2*a.reg.size());
4193 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4197 Integer MontgomeryRepresentation::ConvertOut(
const Integer &a)
const
4199 word *
const T = m_workspace.begin();
4200 word *
const R = m_result.reg.begin();
4201 const size_t N = m_modulus.reg.size();
4202 assert(a.reg.size()<=N);
4204 CopyWords(T, a.reg, a.reg.size());
4205 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
4206 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4210 const Integer& MontgomeryRepresentation::MultiplicativeInverse(
const Integer &a)
const
4213 word *
const T = m_workspace.begin();
4214 word *
const R = m_result.reg.begin();
4215 const size_t N = m_modulus.reg.size();
4216 assert(a.reg.size()<=N);
4218 CopyWords(T, a.reg, a.reg.size());
4219 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
4220 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4221 unsigned k = AlmostInverse(R, T, R, N, m_modulus.reg, N);
4226 DivideByPower2Mod(R, R, k-N*WORD_BITS, m_modulus.reg, N);
4228 MultiplyByPower2Mod(R, R, N*WORD_BITS-k, m_modulus.reg, N);
used to pass byte array input as part of a NameValuePairs object
exception thrown when an invalid argument is detected
void swap(SecBlock< T, A > &b)
swap contents and size with another SecBlock
bool GetBit(size_t i) const
return the i-th bit, i=0 being the least significant bit
void CleanNew(size_type newSize)
change size and set contents to 0
T GetValueWithDefault(const char *name, T defaultValue) const
get a named value, returns the default if the name doesn't exist
virtual void GenerateBlock(byte *output, size_t size)
generate random array of bytes
This file contains helper classes/functions for implementing public key algorithms.
static Integer Gcd(const Integer &a, const Integer &n)
greatest common divisor
void resize(size_type newSize)
change size and preserve contents
void CleanGrow(size_type newSize)
change size only if newSize > current size. contents are preserved and additional area is set to 0 ...
a block of memory allocated using A
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
byte GetByte(size_t i) const
return the i-th byte
static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n)
returns same result as Divide(r, q, a, Power2(n)), but faster
ring of congruence classes modulo n
interface for random number generators
void New(size_type newSize)
change size, without preserving contents
void SetByte(size_t n, byte value)
set the n-th byte to value
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode absolute value as big-endian octet string
lword MaxRetrievable() const
returns number of bytes that is currently ready for retrieval
bool IsConvertableToLong() const
return true if *this can be represented as a signed long
Integer MultiplicativeInverse() const
return inverse if 1 or -1, otherwise return 0
static const Integer & One()
avoid calling constructors for these frequently used integers
bool GetIntValue(const char *name, int &value) const
get a named value with type int
bool IsSquare() const
return whether this integer is a perfect square
size_t OpenPGPEncode(byte *output, size_t bufferSize) const
encode absolute value in OpenPGP format, return length of output
unsigned int BitCount() const
number of significant bits = floor(log2(abs(*this))) + 1
bool IsUnit() const
is 1 or -1
Copy input to a memory buffer.
Integer SquareRoot() const
extract square root, if negative return 0, else return floor of square root
bool GetValue(const char *name, T &value) const
get a named value, returns true if the name exists
Integer()
creates the zero integer
signed long ConvertToLong() const
return equivalent signed long if possible, otherwise undefined
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode nonnegative value as big-endian octet string
static Integer Power2(size_t e)
return the integer 2**e
multiple precision integer and basic arithmetics
static const Integer & Two()
avoid calling constructors for these frequently used integers
const char * Seed()
ConstByteArrayParameter.
string-based implementation of Store interface
static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d)
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
void SetBit(size_t n, bool value=1)
set the n-th bit to value
void Encode(byte *output, size_t outputLen, Signedness=UNSIGNED) const
encode in big-endian format
const char * PointerToPrimeSelector()
const PrimeSelector *
void DEREncode(BufferedTransformation &bt) const
encode using Distinguished Encoding Rules, put result into a BufferedTransformation object ...
division by zero exception
do modular arithmetics in Montgomery representation for increased speed
void GenerateBlock(byte *output, size_t size)
generate random array of bytes
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
static const Integer & Zero()
avoid calling constructors for these frequently used integers
lword GetBits(size_t i, size_t n) const
return n lowest bits of *this >> i
size_t MinEncodedSize(Signedness=UNSIGNED) const
minimum number of bytes to encode this integer
int Compare(const Integer &a) const
signed comparison
size_t Get(byte &outByte)
try to retrieve a single byte
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
interface for retrieving values given their names