30 #if CRYPTOPP_MSC_VERSION 31 # pragma warning(disable: 4100) 34 #if CRYPTOPP_GCC_DIAGNOSTIC_AVAILABLE 35 # pragma GCC diagnostic ignored "-Wunused" 36 #if !defined(__clang__) 37 # pragma GCC diagnostic ignored "-Wunused-but-set-variable" 42 #if CRYPTOPP_GCC_DIAGNOSTIC_AVAILABLE 43 # pragma GCC diagnostic ignored "-Wconversion" 44 # pragma GCC diagnostic ignored "-Wsign-conversion" 53 #ifndef CRYPTOPP_IMPORTS 73 #if (_MSC_VER >= 1400) && !defined(_M_ARM) 82 #if (__SUNPRO_CC >= 0x5130) 84 # define MAYBE_UNCONST_CAST(x) const_cast<word*>(x) 86 # define MAYBE_CONST const 87 # define MAYBE_UNCONST_CAST(x) x 92 #if CRYPTOPP_BOOL_X32 || defined(CRYPTOPP_DISABLE_INTEL_ASM) 93 # undef CRYPTOPP_X86_ASM_AVAILABLE 94 # undef CRYPTOPP_X32_ASM_AVAILABLE 95 # undef CRYPTOPP_X64_ASM_AVAILABLE 96 # undef CRYPTOPP_SSE2_ASM_AVAILABLE 97 # undef CRYPTOPP_SSSE3_ASM_AVAILABLE 99 # define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_SSE2_ASM_AVAILABLE && (CRYPTOPP_BOOL_X86)) 105 static void SetFunctionPointers();
106 InitializeInteger::InitializeInteger()
108 #if !(HAVE_GCC_INIT_PRIORITY || HAVE_MSC_INIT_PRIORITY) 109 #if defined(CRYPTOPP_CXX11_SYNCHRONIZATION) && defined(CRYPTOPP_CXX11_DYNAMIC_INIT) 110 static std::once_flag s_flag;
111 std::call_once(s_flag, []() {
112 SetFunctionPointers();
119 SetFunctionPointers();
123 #endif // C++11 or C++03 flag 124 #endif // not GCC and MSC init priorities 138 inline static int Compare(
const word *A,
const word *B,
size_t N)
143 else if (A[N] < B[N])
149 inline static int Increment(word *A,
size_t N, word B=1)
156 for (
unsigned i=1; i<N; i++)
162 inline static int Decrement(word *A,
size_t N, word B=1)
169 for (
unsigned i=1; i<N; i++)
175 static void TwosComplement(word *A,
size_t N)
178 for (
unsigned i=0; i<N; i++)
182 static word AtomicInverseModPower2(word A)
188 for (
unsigned i=3; i<WORD_BITS; i*=2)
197 #if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE)) 198 #define Declare2Words(x) word x##0, x##1; 199 #define AssignWord(a, b) a##0 = b; a##1 = 0; 200 #define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c); 201 #define LowWord(a) a##0 202 #define HighWord(a) a##1 204 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1); 205 #ifndef __INTEL_COMPILER 206 #define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2; 208 #elif defined(__DECCXX) 209 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b); 210 #elif defined(__x86_64__) 211 #if defined(__SUNPRO_CC) && __SUNPRO_CC < 0x5100 213 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc"); 215 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc"); 216 #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"); 217 #define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc"); 218 #define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc"); 219 #define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc"); 220 #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"); 223 #define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b) 225 #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; 228 #define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1; 230 #define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);} 231 #define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);} 232 #define GetCarry(u) u##1 233 #define GetBorrow(u) u##1 235 #define Declare2Words(x) dword x; 236 #if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER) && !defined(_M_ARM) 237 #define MultiplyWords(p, a, b) p = __emulu(a, b); 239 #define MultiplyWords(p, a, b) p = (dword)a*b; 241 #define AssignWord(a, b) a = b; 242 #define Add2WordsBy1(a, b, c) a = b + c; 243 #define Acc2WordsBy2(a, b) a += b; 244 #define LowWord(a) word(a) 245 #define HighWord(a) word(a>>WORD_BITS) 246 #define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2; 247 #define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u); 248 #define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u); 249 #define GetCarry(u) HighWord(u) 250 #define GetBorrow(u) word(u>>(WORD_BITS*2-1)) 253 #define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p)); 256 #define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b) 259 #define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e)); 265 #if defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 266 DWord() {std::memset(&m_whole, 0x00,
sizeof(m_whole));}
268 DWord() {std::memset(&m_halfs, 0x00,
sizeof(m_halfs));}
271 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 272 explicit DWord(word low) : m_whole(low) { }
274 explicit DWord(word low)
281 #if defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 282 DWord(word low, word high) : m_whole()
284 DWord(word low, word high) : m_halfs()
287 #if defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 288 # if defined(CRYPTOPP_LITTLE_ENDIAN) 289 const word t[2] = {low,high};
290 memcpy(&m_whole, t,
sizeof(m_whole));
292 const word t[2] = {high,low};
293 memcpy(&m_whole, t,
sizeof(m_whole));
301 static DWord Multiply(word a, word b)
304 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 305 r.m_whole = (dword)a * b;
306 #elif defined(MultiplyWordsLoHi) 307 MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
314 static DWord MultiplyAndAdd(word a, word b, word c)
316 DWord r = Multiply(a, b);
320 DWord & operator+=(word a)
322 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 323 m_whole = m_whole + a;
326 m_halfs.high += (m_halfs.low < a);
331 DWord operator+(word a)
334 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 335 r.m_whole = m_whole + a;
337 r.m_halfs.low = m_halfs.low + a;
338 r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a);
346 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 347 r.m_whole = m_whole - a.m_whole;
349 r.m_halfs.low = m_halfs.low - a.m_halfs.low;
350 r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low);
355 DWord operator-(word a)
358 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 359 r.m_whole = m_whole - a;
361 r.m_halfs.low = m_halfs.low - a;
362 r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low);
368 word operator/(word divisor);
370 word operator%(word a);
372 bool operator!()
const 374 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 377 return !m_halfs.high && !m_halfs.low;
383 word GetLowHalf()
const {
return m_halfs.low;}
384 word GetHighHalf()
const {
return m_halfs.high;}
385 word GetHighHalfAsBorrow()
const {
return 0-m_halfs.high;}
393 #ifdef CRYPTOPP_LITTLE_ENDIAN 403 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 413 Word() : m_whole(0) {}
414 Word(word value) : m_whole(value) {}
415 Word(hword low, hword high) : m_whole(low | (word(high) << (WORD_BITS/2))) {}
417 static Word Multiply(hword a, hword b)
420 r.m_whole = (word)a * b;
427 r.m_whole = m_whole - a.m_whole;
431 Word operator-(hword a)
434 r.m_whole = m_whole - a;
439 hword operator/(hword divisor)
441 return hword(m_whole / divisor);
444 bool operator!()
const 449 word GetWhole()
const {
return m_whole;}
450 hword GetLowHalf()
const {
return hword(m_whole);}
451 hword GetHighHalf()
const {
return hword(m_whole>>(WORD_BITS/2));}
452 hword GetHighHalfAsBorrow()
const {
return 0-hword(m_whole>>(WORD_BITS/2));}
459 template <
class S,
class D>
460 S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULLPTR)
462 CRYPTOPP_UNUSED(dummy);
471 S Q;
bool pre = (S(B1+1) == 0);
473 Q = D(A[1], A[2]) / S(B1+1);
477 Q = D(A[0], A[1]) / B0;
480 D p = D::Multiply(B0, Q);
481 D u = (D) A[0] - p.GetLowHalf();
482 A[0] = u.GetLowHalf();
483 u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q);
484 A[1] = u.GetLowHalf();
485 A[2] += u.GetHighHalf();
488 while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
491 A[0] = u.GetLowHalf();
492 u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
493 A[1] = u.GetLowHalf();
494 A[2] += u.GetHighHalf();
503 template <
class S,
class D>
504 inline D DivideFourWordsByTwo(S *T,
const D &Al,
const D &Ah,
const D &B)
512 T[0] = Al.GetLowHalf();
513 T[1] = Al.GetHighHalf();
514 T[2] = Ah.GetLowHalf();
515 T[3] = Ah.GetHighHalf();
516 Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(), B.GetHighHalf());
517 Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
518 return D(Q[0], Q[1]);
522 return D(Ah.GetLowHalf(), Ah.GetHighHalf());
527 inline word DWord::operator/(word a)
529 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 530 return word(m_whole / a);
533 return DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a).GetWhole();
537 inline word DWord::operator%(word a)
539 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 540 return word(m_whole % a);
542 if (a < (word(1) << (WORD_BITS/2)))
545 word r = m_halfs.high % h;
546 r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
547 return hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h);
552 DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a);
553 return Word(r[0], r[1]).GetWhole();
561 #if defined(__GNUC__) 562 #define AddPrologue \ 564 __asm__ __volatile__ \ 567 #define AddEpilogue \ 570 : "d" (C), "a" (A), "D" (B), "c" (N) \ 571 : "%esi", "memory", "cc" \ 574 #define MulPrologue \ 575 __asm__ __volatile__ \ 580 #define MulEpilogue \ 584 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \ 585 : "%esi", "memory", "cc" \ 587 #define SquPrologue MulPrologue 588 #define SquEpilogue \ 592 : "d" (s_maskLow16), "c" (C), "a" (A) \ 593 : "%esi", "%edi", "memory", "cc" \ 595 #define TopPrologue MulPrologue 596 #define TopEpilogue \ 600 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \ 604 #define AddPrologue \ 607 __asm mov eax, [esp+12] \ 608 __asm mov edi, [esp+16] 609 #define AddEpilogue \ 615 #define SquPrologue \ 619 AS2( lea ebx, s_maskLow16) 620 #define MulPrologue \ 625 AS2( lea ebx, s_maskLow16) 626 #define TopPrologue \ 632 AS2( lea ebx, s_maskLow16) 633 #define SquEpilogue RestoreEBX 634 #define MulEpilogue RestoreEBX 635 #define TopEpilogue RestoreEBX 638 #ifdef CRYPTOPP_X64_MASM_AVAILABLE 640 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B);
641 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B);
643 #elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE) 644 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
652 AS2( mov %0,[%3+8*%1])
653 AS2( add %0,[%4+8*%1])
654 AS2( mov [%2+8*%1],%0)
656 AS2( mov %0,[%3+8*%1+8])
657 AS2( adc %0,[%4+8*%1+8])
658 AS2( mov [%2+8*%1+8],%0)
661 AS2( mov %0,[%3+8*%1])
662 AS2( adc %0,[%4+8*%1])
663 AS2( mov [%2+8*%1],%0)
669 :
"=&r" (result),
"+c" (N)
670 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
676 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
684 AS2( mov %0,[%3+8*%1])
685 AS2( sub %0,[%4+8*%1])
686 AS2( mov [%2+8*%1],%0)
688 AS2( mov %0,[%3+8*%1+8])
689 AS2( sbb %0,[%4+8*%1+8])
690 AS2( mov [%2+8*%1+8],%0)
693 AS2( mov %0,[%3+8*%1])
694 AS2( sbb %0,[%4+8*%1])
695 AS2( mov [%2+8*%1],%0)
701 :
"=&r" (result),
"+c" (N)
702 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
707 #elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86 708 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
713 AS2( lea eax, [eax+4*ecx])
714 AS2( lea edi, [edi+4*ecx])
715 AS2( lea edx, [edx+4*ecx])
725 AS2( mov esi,[eax+4*ecx])
726 AS2( adc esi,[edi+4*ecx])
727 AS2( mov [edx+4*ecx],esi)
728 AS2( mov esi,[eax+4*ecx+4])
729 AS2( adc esi,[edi+4*ecx+4])
730 AS2( mov [edx+4*ecx+4],esi)
732 AS2( mov esi,[eax+4*ecx+8])
733 AS2( adc esi,[edi+4*ecx+8])
734 AS2( mov [edx+4*ecx+8],esi)
735 AS2( mov esi,[eax+4*ecx+12])
736 AS2( adc esi,[edi+4*ecx+12])
737 AS2( mov [edx+4*ecx+12],esi)
739 AS2( lea ecx,[ecx+4])
749 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C, const word *A, const word *B)
754 AS2( lea eax, [eax+4*ecx])
755 AS2( lea edi, [edi+4*ecx])
756 AS2( lea edx, [edx+4*ecx])
766 AS2( mov esi,[eax+4*ecx])
767 AS2( sbb esi,[edi+4*ecx])
768 AS2( mov [edx+4*ecx],esi)
769 AS2( mov esi,[eax+4*ecx+4])
770 AS2( sbb esi,[edi+4*ecx+4])
771 AS2( mov [edx+4*ecx+4],esi)
773 AS2( mov esi,[eax+4*ecx+8])
774 AS2( sbb esi,[edi+4*ecx+8])
775 AS2( mov [edx+4*ecx+8],esi)
776 AS2( mov esi,[eax+4*ecx+12])
777 AS2( sbb esi,[edi+4*ecx+12])
778 AS2( mov [edx+4*ecx+12],esi)
780 AS2( lea ecx,[ecx+4])
790 #if CRYPTOPP_INTEGER_SSE2 791 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Add(
size_t N, word *C,
const word *A,
const word *B)
796 AS2( lea eax, [eax+4*ecx])
797 AS2( lea edi, [edi+4*ecx])
798 AS2( lea edx, [edx+4*ecx])
809 AS2( movd mm0, DWORD PTR [eax+4*ecx])
810 AS2( movd mm1, DWORD PTR [edi+4*ecx])
813 AS2( movd DWORD PTR [edx+4*ecx], mm2)
816 AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
817 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
820 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
824 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
825 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
828 AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
831 AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
832 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
835 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
847 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Sub(
size_t N, word *C, const word *A, const word *B)
852 AS2( lea eax, [eax+4*ecx])
853 AS2( lea edi, [edi+4*ecx])
854 AS2( lea edx, [edx+4*ecx])
865 AS2( movd mm0, DWORD PTR [eax+4*ecx])
866 AS2( movd mm1, DWORD PTR [edi+4*ecx])
869 AS2( movd DWORD PTR [edx+4*ecx], mm0)
872 AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
873 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
876 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
880 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
881 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
884 AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
887 AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
888 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
891 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
903 #endif // CRYPTOPP_INTEGER_SSE2 904 #else // CRYPTOPP_SSE2_ASM_AVAILABLE 905 int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
911 for (
size_t i=0; i<N; i+=2)
913 AddWithCarry(u, A[i], B[i]);
915 AddWithCarry(u, A[i+1], B[i+1]);
918 return int(GetCarry(u));
921 int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
927 for (
size_t i=0; i<N; i+=2)
929 SubtractWithBorrow(u, A[i], B[i]);
931 SubtractWithBorrow(u, A[i+1], B[i+1]);
934 return int(GetBorrow(u));
938 static word LinearMultiply(word *C,
const word *AA, word B,
size_t N)
941 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
944 for(
unsigned i=0; i<N; i++)
947 MultiplyWords(p, A[i], B);
948 Acc2WordsBy1(p, carry);
955 #ifndef CRYPTOPP_DOXYGEN_PROCESSING 959 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 964 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 965 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 966 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 967 Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \ 968 Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \ 973 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 974 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 975 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 976 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 977 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) \ 978 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) \ 979 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) \ 980 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) \ 981 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) \ 982 Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \ 983 Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \ 984 Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \ 985 Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \ 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 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) \ 1005 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) \ 1006 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) \ 1007 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) \ 1008 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) \ 1009 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) \ 1010 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) \ 1011 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) \ 1012 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) \ 1013 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) \ 1014 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) \ 1015 Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \ 1016 Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \ 1017 Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \ 1018 Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \ 1027 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 1028 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 1029 Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \ 1030 Squ_SaveAcc(4, 2, 3) Squ_NonDiag \ 1035 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 1036 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 1037 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \ 1038 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \ 1039 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \ 1040 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \ 1041 Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \ 1042 Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \ 1043 Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \ 1044 Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \ 1045 Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \ 1046 Squ_SaveAcc(12, 6, 7) Squ_NonDiag \ 1051 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 1052 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 1053 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \ 1054 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \ 1055 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \ 1056 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \ 1057 Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \ 1058 Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \ 1059 Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \ 1060 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 \ 1061 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) \ 1062 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 \ 1063 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) \ 1064 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 \ 1065 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) \ 1066 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 \ 1067 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) \ 1068 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 \ 1069 Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \ 1070 Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \ 1071 Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \ 1072 Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \ 1073 Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \ 1074 Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \ 1075 Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \ 1076 Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \ 1077 Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \ 1078 Squ_SaveAcc(28, 14, 15) Squ_NonDiag \ 1083 Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \ 1088 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1089 Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \ 1090 Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \ 1095 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1096 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 1097 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 1098 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 1099 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) \ 1100 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) \ 1101 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) \ 1106 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1107 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 1108 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 1109 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 1110 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) \ 1111 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) \ 1112 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) \ 1113 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) \ 1114 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) \ 1115 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) \ 1116 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) \ 1117 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) \ 1118 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) \ 1119 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) \ 1120 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) \ 1126 #define Mul_Begin(n) \ 1130 MultiplyWords(p, A[0], B[0]) \ 1131 AssignWord(c, LowWord(p)) \ 1132 AssignWord(d, HighWord(p)) 1134 #define Mul_Acc(i, j) \ 1135 MultiplyWords(p, A[i], B[j]) \ 1136 Acc2WordsBy1(c, LowWord(p)) \ 1137 Acc2WordsBy1(d, HighWord(p)) 1139 #define Mul_SaveAcc(k, i, j) \ 1140 R[k] = LowWord(c); \ 1141 Add2WordsBy1(c, d, HighWord(c)) \ 1142 MultiplyWords(p, A[i], B[j]) \ 1143 AssignWord(d, HighWord(p)) \ 1144 Acc2WordsBy1(c, LowWord(p)) 1146 #define Mul_End(n) \ 1147 R[2*n-3] = LowWord(c); \ 1148 Acc2WordsBy1(d, HighWord(c)) \ 1149 MultiplyWords(p, A[n-1], B[n-1])\ 1150 Acc2WordsBy2(d, p) \ 1151 R[2*n-2] = LowWord(d); \ 1152 R[2*n-1] = HighWord(d); 1154 #define Bot_SaveAcc(k, i, j) \ 1155 R[k] = LowWord(c); \ 1156 word e = LowWord(d) + HighWord(c); \ 1159 #define Bot_Acc(i, j) \ 1162 #define Bot_End(n) \ 1165 #define Mul_Begin(n) \ 1169 MultiplyWords(p, A[0], B[0]) \ 1171 AssignWord(d, HighWord(p)) 1173 #define Mul_Acc(i, j) \ 1174 MulAcc(c, d, A[i], B[j]) 1176 #define Mul_SaveAcc(k, i, j) \ 1179 AssignWord(d, HighWord(d)) \ 1180 MulAcc(c, d, A[i], B[j]) 1182 #define Mul_End(k, i) \ 1184 MultiplyWords(p, A[i], B[i]) \ 1185 Acc2WordsBy2(p, d) \ 1186 R[k+1] = LowWord(p); \ 1187 R[k+2] = HighWord(p); 1189 #define Bot_SaveAcc(k, i, j) \ 1194 #define Bot_Acc(i, j) \ 1197 #define Bot_End(n) \ 1201 #define Squ_Begin(n) \ 1206 MultiplyWords(p, A[0], A[0]) \ 1207 R[0] = LowWord(p); \ 1208 AssignWord(e, HighWord(p)) \ 1209 MultiplyWords(p, A[0], A[1]) \ 1211 AssignWord(d, HighWord(p)) \ 1214 #define Squ_NonDiag \ 1217 #define Squ_SaveAcc(k, i, j) \ 1218 Acc3WordsBy2(c, d, e) \ 1220 MultiplyWords(p, A[i], A[j]) \ 1222 AssignWord(d, HighWord(p)) \ 1224 #define Squ_Acc(i, j) \ 1225 MulAcc(c, d, A[i], A[j]) 1227 #define Squ_Diag(i) \ 1229 MulAcc(c, d, A[i], A[i]) 1231 #define Squ_End(n) \ 1232 Acc3WordsBy2(c, d, e) \ 1234 MultiplyWords(p, A[n-1], A[n-1])\ 1235 Acc2WordsBy2(p, e) \ 1236 R[2*n-2] = LowWord(p); \ 1237 R[2*n-1] = HighWord(p); 1240 void Baseline_Multiply2(word *R,
const word *AA,
const word *BB)
1243 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1244 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1249 void Baseline_Multiply4(word *R,
const word *AA,
const word *BB)
1252 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1253 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1258 void Baseline_Multiply8(word *R,
const word *AA,
const word *BB)
1261 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1262 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1267 void Baseline_Square2(word *R,
const word *AA)
1270 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1275 void Baseline_Square4(word *R,
const word *AA)
1278 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1283 void Baseline_Square8(word *R,
const word *AA)
1286 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1291 void Baseline_MultiplyBottom2(word *R,
const word *AA,
const word *BB)
1294 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1295 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1300 void Baseline_MultiplyBottom4(word *R,
const word *AA,
const word *BB)
1303 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1304 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1309 void Baseline_MultiplyBottom8(word *R,
const word *AA,
const word *BB)
1312 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1313 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1318 #define Top_Begin(n) \ 1322 MultiplyWords(p, A[0], B[n-2]);\ 1323 AssignWord(d, HighWord(p)); 1325 #define Top_Acc(i, j) \ 1326 MultiplyWords(p, A[i], B[j]);\ 1327 Acc2WordsBy1(d, HighWord(p)); 1329 #define Top_SaveAcc0(i, j) \ 1331 AssignWord(d, HighWord(d)) \ 1332 MulAcc(c, d, A[i], B[j]) 1334 #define Top_SaveAcc1(i, j) \ 1336 Acc2WordsBy1(d, c); \ 1338 AssignWord(d, HighWord(d)) \ 1339 MulAcc(c, d, A[i], B[j]) 1341 void Baseline_MultiplyTop2(word *R,
const word *A,
const word *B, word L)
1345 Baseline_Multiply2(T, A, B);
1350 void Baseline_MultiplyTop4(word *R,
const word *AA,
const word *BB, word L)
1353 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1354 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1357 Top_Acc(1, 1) Top_Acc(2, 0) \
1358 Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1359 Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1360 Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1364 void Baseline_MultiplyTop8(word *R, const word *AA, const word *BB, word L)
1367 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1368 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1371 Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1372 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) \
1373 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) \
1374 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) \
1375 Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1376 Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1377 Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1378 Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1382 #if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available 1383 void Baseline_Multiply16(word *R,
const word *AA,
const word *BB)
1386 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1387 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1392 void Baseline_Square16(word *R,
const word *AA)
1395 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1400 void Baseline_MultiplyBottom16(word *R,
const word *AA,
const word *BB)
1403 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1404 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1409 void Baseline_MultiplyTop16(word *R,
const word *AA,
const word *BB, word L)
1412 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1413 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1416 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) \
1417 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) \
1418 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) \
1419 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) \
1420 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) \
1421 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) \
1422 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) \
1423 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) \
1424 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) \
1425 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) \
1426 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) \
1427 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) \
1428 Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1429 Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1430 Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1431 Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1438 #if CRYPTOPP_INTEGER_SSE2 1440 CRYPTOPP_ALIGN_DATA(16)
1442 const word32 s_maskLow16[4] = {
1443 0xffff,0xffff,0xffff,0xffff
1462 #define SSE2_FinalSave(k) \ 1463 AS2( psllq xmm5, 16) \ 1464 AS2( paddq xmm4, xmm5) \ 1465 AS2( movq QWORD PTR [ecx+8*(k)], xmm4) 1467 #define SSE2_SaveShift(k) \ 1468 AS2( movq xmm0, xmm6) \ 1469 AS2( punpckhqdq xmm6, xmm0) \ 1470 AS2( movq xmm1, xmm7) \ 1471 AS2( punpckhqdq xmm7, xmm1) \ 1472 AS2( paddd xmm6, xmm0) \ 1473 AS2( pslldq xmm6, 4) \ 1474 AS2( paddd xmm7, xmm1) \ 1475 AS2( paddd xmm4, xmm6) \ 1476 AS2( pslldq xmm7, 4) \ 1477 AS2( movq xmm6, xmm4) \ 1478 AS2( paddd xmm5, xmm7) \ 1479 AS2( movq xmm7, xmm5) \ 1480 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \ 1481 AS2( psrlq xmm6, 16) \ 1482 AS2( paddq xmm6, xmm7) \ 1483 AS2( punpckhqdq xmm4, xmm0) \ 1484 AS2( punpckhqdq xmm5, xmm0) \ 1485 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \ 1486 AS2( psrlq xmm6, 3*16) \ 1487 AS2( paddd xmm4, xmm6) \ 1489 #define Squ_SSE2_SaveShift(k) \ 1490 AS2( movq xmm0, xmm6) \ 1491 AS2( punpckhqdq xmm6, xmm0) \ 1492 AS2( movq xmm1, xmm7) \ 1493 AS2( punpckhqdq xmm7, xmm1) \ 1494 AS2( paddd xmm6, xmm0) \ 1495 AS2( pslldq xmm6, 4) \ 1496 AS2( paddd xmm7, xmm1) \ 1497 AS2( paddd xmm4, xmm6) \ 1498 AS2( pslldq xmm7, 4) \ 1499 AS2( movhlps xmm6, xmm4) \ 1500 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \ 1501 AS2( paddd xmm5, xmm7) \ 1502 AS2( movhps QWORD PTR [esp+12], xmm5)\ 1503 AS2( psrlq xmm4, 16) \ 1504 AS2( paddq xmm4, xmm5) \ 1505 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \ 1506 AS2( psrlq xmm4, 3*16) \ 1507 AS2( paddd xmm4, xmm6) \ 1508 AS2( movq QWORD PTR [esp+4], xmm4)\ 1510 #define SSE2_FirstMultiply(i) \ 1511 AS2( movdqa xmm7, [esi+(i)*16])\ 1512 AS2( movdqa xmm5, [edi-(i)*16])\ 1513 AS2( pmuludq xmm5, xmm7) \ 1514 AS2( movdqa xmm4, [ebx])\ 1515 AS2( movdqa xmm6, xmm4) \ 1516 AS2( pand xmm4, xmm5) \ 1517 AS2( psrld xmm5, 16) \ 1518 AS2( pmuludq xmm7, [edx-(i)*16])\ 1519 AS2( pand xmm6, xmm7) \ 1520 AS2( psrld xmm7, 16) 1522 #define Squ_Begin(n) \ 1525 AS2( and esp, 0xfffffff0)\ 1526 AS2( lea edi, [esp-32*n])\ 1527 AS2( sub esp, 32*n+16)\ 1529 AS2( mov esi, edi) \ 1530 AS2( xor edx, edx) \ 1532 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1533 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1534 AS2( movdqa [edi+2*edx], xmm0) \ 1535 AS2( psrlq xmm0, 32) \ 1536 AS2( movdqa [edi+2*edx+16], xmm0) \ 1537 AS2( movdqa [edi+16*n+2*edx], xmm1) \ 1538 AS2( psrlq xmm1, 32) \ 1539 AS2( movdqa [edi+16*n+2*edx+16], xmm1) \ 1541 AS2( cmp edx, 8*(n)) \ 1543 AS2( lea edx, [edi+16*n])\ 1544 SSE2_FirstMultiply(0) \ 1546 #define Squ_Acc(i) \ 1548 AS2( movdqa xmm1, [esi+(i)*16]) \ 1549 AS2( movdqa xmm0, [edi-(i)*16]) \ 1550 AS2( movdqa xmm2, [ebx]) \ 1551 AS2( pmuludq xmm0, xmm1) \ 1552 AS2( pmuludq xmm1, [edx-(i)*16]) \ 1553 AS2( movdqa xmm3, xmm2) \ 1554 AS2( pand xmm2, xmm0) \ 1555 AS2( psrld xmm0, 16) \ 1556 AS2( paddd xmm4, xmm2) \ 1557 AS2( paddd xmm5, xmm0) \ 1558 AS2( pand xmm3, xmm1) \ 1559 AS2( psrld xmm1, 16) \ 1560 AS2( paddd xmm6, xmm3) \ 1561 AS2( paddd xmm7, xmm1) \ 1564 #define Squ_Acc2(i) ASC(call, LSqu##i) 1565 #define Squ_Acc3(i) Squ_Acc2(i) 1566 #define Squ_Acc4(i) Squ_Acc2(i) 1567 #define Squ_Acc5(i) Squ_Acc2(i) 1568 #define Squ_Acc6(i) Squ_Acc2(i) 1569 #define Squ_Acc7(i) Squ_Acc2(i) 1570 #define Squ_Acc8(i) Squ_Acc2(i) 1572 #define SSE2_End(E, n) \ 1573 SSE2_SaveShift(2*(n)-3) \ 1574 AS2( movdqa xmm7, [esi+16]) \ 1575 AS2( movdqa xmm0, [edi]) \ 1576 AS2( pmuludq xmm0, xmm7) \ 1577 AS2( movdqa xmm2, [ebx]) \ 1578 AS2( pmuludq xmm7, [edx]) \ 1579 AS2( movdqa xmm6, xmm2) \ 1580 AS2( pand xmm2, xmm0) \ 1581 AS2( psrld xmm0, 16) \ 1582 AS2( paddd xmm4, xmm2) \ 1583 AS2( paddd xmm5, xmm0) \ 1584 AS2( pand xmm6, xmm7) \ 1585 AS2( psrld xmm7, 16) \ 1586 SSE2_SaveShift(2*(n)-2) \ 1587 SSE2_FinalSave(2*(n)-1) \ 1591 #define Squ_End(n) SSE2_End(SquEpilogue, n) 1592 #define Mul_End(n) SSE2_End(MulEpilogue, n) 1593 #define Top_End(n) SSE2_End(TopEpilogue, n) 1595 #define Squ_Column1(k, i) \ 1596 Squ_SSE2_SaveShift(k) \ 1598 SSE2_FirstMultiply(1)\ 1600 AS2( paddd xmm4, xmm4) \ 1601 AS2( paddd xmm5, xmm5) \ 1602 AS2( movdqa xmm3, [esi]) \ 1603 AS2( movq xmm1, QWORD PTR [esi+8]) \ 1604 AS2( pmuludq xmm1, xmm3) \ 1605 AS2( pmuludq xmm3, xmm3) \ 1606 AS2( movdqa xmm0, [ebx])\ 1607 AS2( movdqa xmm2, xmm0) \ 1608 AS2( pand xmm0, xmm1) \ 1609 AS2( psrld xmm1, 16) \ 1610 AS2( paddd xmm6, xmm0) \ 1611 AS2( paddd xmm7, xmm1) \ 1612 AS2( pand xmm2, xmm3) \ 1613 AS2( psrld xmm3, 16) \ 1614 AS2( paddd xmm6, xmm6) \ 1615 AS2( paddd xmm7, xmm7) \ 1616 AS2( paddd xmm4, xmm2) \ 1617 AS2( paddd xmm5, xmm3) \ 1618 AS2( movq xmm0, QWORD PTR [esp+4])\ 1619 AS2( movq xmm1, QWORD PTR [esp+12])\ 1620 AS2( paddd xmm4, xmm0)\ 1621 AS2( paddd xmm5, xmm1)\ 1623 #define Squ_Column0(k, i) \ 1624 Squ_SSE2_SaveShift(k) \ 1627 SSE2_FirstMultiply(1)\ 1629 AS2( paddd xmm6, xmm6) \ 1630 AS2( paddd xmm7, xmm7) \ 1631 AS2( paddd xmm4, xmm4) \ 1632 AS2( paddd xmm5, xmm5) \ 1633 AS2( movq xmm0, QWORD PTR [esp+4])\ 1634 AS2( movq xmm1, QWORD PTR [esp+12])\ 1635 AS2( paddd xmm4, xmm0)\ 1636 AS2( paddd xmm5, xmm1)\ 1638 #define SSE2_MulAdd45 \ 1639 AS2( movdqa xmm7, [esi]) \ 1640 AS2( movdqa xmm0, [edi]) \ 1641 AS2( pmuludq xmm0, xmm7) \ 1642 AS2( movdqa xmm2, [ebx]) \ 1643 AS2( pmuludq xmm7, [edx]) \ 1644 AS2( movdqa xmm6, xmm2) \ 1645 AS2( pand xmm2, xmm0) \ 1646 AS2( psrld xmm0, 16) \ 1647 AS2( paddd xmm4, xmm2) \ 1648 AS2( paddd xmm5, xmm0) \ 1649 AS2( pand xmm6, xmm7) \ 1650 AS2( psrld xmm7, 16) 1652 #define Mul_Begin(n) \ 1655 AS2( and esp, 0xfffffff0)\ 1656 AS2( sub esp, 48*n+16)\ 1658 AS2( xor edx, edx) \ 1660 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1661 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1662 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \ 1663 AS2( movdqa [esp+20+2*edx], xmm0) \ 1664 AS2( psrlq xmm0, 32) \ 1665 AS2( movdqa [esp+20+2*edx+16], xmm0) \ 1666 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \ 1667 AS2( psrlq xmm1, 32) \ 1668 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \ 1669 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \ 1670 AS2( psrlq xmm2, 32) \ 1671 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \ 1673 AS2( cmp edx, 8*(n)) \ 1675 AS2( lea edi, [esp+20])\ 1676 AS2( lea edx, [esp+20+16*n])\ 1677 AS2( lea esi, [esp+20+32*n])\ 1678 SSE2_FirstMultiply(0) \ 1680 #define Mul_Acc(i) \ 1682 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \ 1683 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \ 1684 AS2( movdqa xmm2, [ebx]) \ 1685 AS2( pmuludq xmm0, xmm1) \ 1686 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1687 AS2( movdqa xmm3, xmm2) \ 1688 AS2( pand xmm2, xmm0) \ 1689 AS2( psrld xmm0, 16) \ 1690 AS2( paddd xmm4, xmm2) \ 1691 AS2( paddd xmm5, xmm0) \ 1692 AS2( pand xmm3, xmm1) \ 1693 AS2( psrld xmm1, 16) \ 1694 AS2( paddd xmm6, xmm3) \ 1695 AS2( paddd xmm7, xmm1) \ 1698 #define Mul_Acc2(i) ASC(call, LMul##i) 1699 #define Mul_Acc3(i) Mul_Acc2(i) 1700 #define Mul_Acc4(i) Mul_Acc2(i) 1701 #define Mul_Acc5(i) Mul_Acc2(i) 1702 #define Mul_Acc6(i) Mul_Acc2(i) 1703 #define Mul_Acc7(i) Mul_Acc2(i) 1704 #define Mul_Acc8(i) Mul_Acc2(i) 1705 #define Mul_Acc9(i) Mul_Acc2(i) 1706 #define Mul_Acc10(i) Mul_Acc2(i) 1707 #define Mul_Acc11(i) Mul_Acc2(i) 1708 #define Mul_Acc12(i) Mul_Acc2(i) 1709 #define Mul_Acc13(i) Mul_Acc2(i) 1710 #define Mul_Acc14(i) Mul_Acc2(i) 1711 #define Mul_Acc15(i) Mul_Acc2(i) 1712 #define Mul_Acc16(i) Mul_Acc2(i) 1714 #define Mul_Column1(k, i) \ 1720 #define Mul_Column0(k, i) \ 1727 #define Bot_Acc(i) \ 1728 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \ 1729 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \ 1730 AS2( pmuludq xmm0, xmm1) \ 1731 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1732 AS2( paddq xmm4, xmm0) \ 1733 AS2( paddd xmm6, xmm1) 1735 #define Bot_SaveAcc(k) \ 1739 AS2( movdqa xmm6, [esi]) \ 1740 AS2( movdqa xmm0, [edi]) \ 1741 AS2( pmuludq xmm0, xmm6) \ 1742 AS2( paddq xmm4, xmm0) \ 1743 AS2( psllq xmm5, 16) \ 1744 AS2( paddq xmm4, xmm5) \ 1745 AS2( pmuludq xmm6, [edx]) 1747 #define Bot_End(n) \ 1748 AS2( movhlps xmm7, xmm6) \ 1749 AS2( paddd xmm6, xmm7) \ 1750 AS2( psllq xmm6, 32) \ 1751 AS2( paddd xmm4, xmm6) \ 1752 AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \ 1756 #define Top_Begin(n) \ 1759 AS2( and esp, 0xfffffff0)\ 1760 AS2( sub esp, 48*n+16)\ 1762 AS2( xor edx, edx) \ 1764 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1765 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1766 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \ 1767 AS2( movdqa [esp+20+2*edx], xmm0) \ 1768 AS2( psrlq xmm0, 32) \ 1769 AS2( movdqa [esp+20+2*edx+16], xmm0) \ 1770 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \ 1771 AS2( psrlq xmm1, 32) \ 1772 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \ 1773 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \ 1774 AS2( psrlq xmm2, 32) \ 1775 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \ 1777 AS2( cmp edx, 8*(n)) \ 1779 AS2( mov eax, esi) \ 1780 AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\ 1781 AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\ 1782 AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\ 1783 AS2( pxor xmm4, xmm4)\ 1784 AS2( pxor xmm5, xmm5) 1786 #define Top_Acc(i) \ 1787 AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \ 1788 AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1789 AS2( psrlq xmm0, 48) \ 1790 AS2( paddd xmm5, xmm0)\ 1792 #define Top_Column0(i) \ 1793 AS2( psllq xmm5, 32) \ 1799 #define Top_Column1(i) \ 1805 AS2( movd xmm0, eax)\ 1806 AS2( movd xmm1, [ecx+4])\ 1807 AS2( psrld xmm1, 16)\ 1808 AS2( pcmpgtd xmm1, xmm0)\ 1809 AS2( psrld xmm1, 31)\ 1810 AS2( paddd xmm4, xmm1)\ 1812 void SSE2_Square4(word *C,
const word *A)
1819 void SSE2_Square8(word *C, const word *A)
1835 void SSE2_Square16(word *C, const word *A)
1840 Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1859 void SSE2_Square32(word *C, const word *A)
1863 Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1897 void SSE2_Multiply4(word *C, const word *A, const word *B)
1909 void SSE2_Multiply8(word *C, const word *A, const word *B)
1914 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1925 void SSE2_Multiply16(word *C, const word *A, const word *B)
1930 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1949 void SSE2_Multiply32(word *C, const word *A, const word *B)
1953 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)
1987 void SSE2_MultiplyBottom4(word *C, const word *A, const word *B)
1990 Bot_SaveAcc(0) Bot_Acc(2)
1994 void SSE2_MultiplyBottom8(word *C, const word *A, const word *B)
1999 Mul_Acc(3) Mul_Acc(2)
2004 Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
2008 void SSE2_MultiplyBottom16(word *C, const word *A, const word *B)
2013 Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
2022 Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
2026 void SSE2_MultiplyBottom32(word *C, const word *A, const word *B)
2031 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)
2048 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)
2052 void SSE2_MultiplyTop8(word *C, const word *A, const word *B, word L)
2055 Top_Acc(3) Top_Acc(2) Top_Acc(1)
2058 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
2067 void SSE2_MultiplyTop16(word *C, const word *A, const word *B, word L)
2070 Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
2073 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
2086 void SSE2_MultiplyTop32(word *C, const word *A, const word *B, word L)
2089 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)
2092 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)
2113 #endif // #if CRYPTOPP_INTEGER_SSE2 2117 typedef int (CRYPTOPP_FASTCALL * PAdd)(
size_t N, word *C,
const word *A,
const word *B);
2118 typedef void (* PMul)(word *C,
const word *A,
const word *B);
2119 typedef void (* PSqu)(word *C,
const word *A);
2120 typedef void (* PMulTop)(word *C,
const word *A,
const word *B, word L);
2122 #if CRYPTOPP_INTEGER_SSE2 2123 static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
2124 static size_t s_recursionLimit = 8;
2126 static const size_t s_recursionLimit = 16;
2127 #endif // CRYPTOPP_INTEGER_SSE2 2129 static PMul s_pMul[9], s_pBot[9];
2130 static PSqu s_pSqu[9];
2131 static PMulTop s_pTop[9];
2133 void SetFunctionPointers()
2135 s_pMul[0] = &Baseline_Multiply2;
2136 s_pBot[0] = &Baseline_MultiplyBottom2;
2137 s_pSqu[0] = &Baseline_Square2;
2138 s_pTop[0] = &Baseline_MultiplyTop2;
2139 s_pTop[1] = &Baseline_MultiplyTop4;
2141 #if CRYPTOPP_INTEGER_SSE2 2150 s_recursionLimit = 32;
2152 s_pMul[1] = &SSE2_Multiply4;
2153 s_pMul[2] = &SSE2_Multiply8;
2154 s_pMul[4] = &SSE2_Multiply16;
2155 s_pMul[8] = &SSE2_Multiply32;
2157 s_pBot[1] = &SSE2_MultiplyBottom4;
2158 s_pBot[2] = &SSE2_MultiplyBottom8;
2159 s_pBot[4] = &SSE2_MultiplyBottom16;
2160 s_pBot[8] = &SSE2_MultiplyBottom32;
2162 s_pSqu[1] = &SSE2_Square4;
2163 s_pSqu[2] = &SSE2_Square8;
2164 s_pSqu[4] = &SSE2_Square16;
2165 s_pSqu[8] = &SSE2_Square32;
2167 s_pTop[2] = &SSE2_MultiplyTop8;
2168 s_pTop[4] = &SSE2_MultiplyTop16;
2169 s_pTop[8] = &SSE2_MultiplyTop32;
2172 #endif // CRYPTOPP_INTEGER_SSE2 2174 s_pMul[1] = &Baseline_Multiply4;
2175 s_pMul[2] = &Baseline_Multiply8;
2177 s_pBot[1] = &Baseline_MultiplyBottom4;
2178 s_pBot[2] = &Baseline_MultiplyBottom8;
2180 s_pSqu[1] = &Baseline_Square4;
2181 s_pSqu[2] = &Baseline_Square8;
2183 s_pTop[2] = &Baseline_MultiplyTop8;
2185 #if !CRYPTOPP_INTEGER_SSE2 2186 s_pMul[4] = &Baseline_Multiply16;
2187 s_pBot[4] = &Baseline_MultiplyBottom16;
2188 s_pSqu[4] = &Baseline_Square16;
2189 s_pTop[4] = &Baseline_MultiplyTop16;
2190 #endif // !CRYPTOPP_INTEGER_SSE2 2194 inline int Add(word *C,
const word *A,
const word *B,
size_t N)
2196 #if CRYPTOPP_INTEGER_SSE2 2197 return s_pAdd(N, C, A, B);
2199 return Baseline_Add(N, C, A, B);
2200 #endif // CRYPTOPP_INTEGER_SSE2 2203 inline int Subtract(word *C,
const word *A,
const word *B,
size_t N)
2205 #if CRYPTOPP_INTEGER_SSE2 2206 return s_pSub(N, C, A, B);
2208 return Baseline_Sub(N, C, A, B);
2209 #endif // CRYPTOPP_INTEGER_SSE2 2235 void RecursiveMultiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2239 if (N <= s_recursionLimit)
2240 s_pMul[N/4](R, A, B);
2243 const size_t N2 = N/2;
2245 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2246 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2248 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2249 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2251 RecursiveMultiply(R2, T2, A1, B1, N2);
2252 RecursiveMultiply(T0, T2, R0, R1, N2);
2253 RecursiveMultiply(R0, T2, A0, B0, N2);
2257 int c2 = Add(R2, R2, R1, N2);
2259 c2 += Add(R1, R2, R0, N2);
2260 c3 += Add(R2, R2, R3, N2);
2263 c3 -= Subtract(R1, R1, T0, N);
2265 c3 += Add(R1, R1, T0, N);
2267 c3 += Increment(R2, N2, c2);
2269 Increment(R3, N2, c3);
2277 void RecursiveSquare(word *R, word *T,
const word *A,
size_t N)
2281 if (N <= s_recursionLimit)
2285 const size_t N2 = N/2;
2287 RecursiveSquare(R0, T2, A0, N2);
2288 RecursiveSquare(R2, T2, A1, N2);
2289 RecursiveMultiply(T0, T2, A0, A1, N2);
2291 int carry = Add(R1, R1, T0, N);
2292 carry += Add(R1, R1, T0, N);
2293 Increment(R3, N2, carry);
2302 void RecursiveMultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2306 if (N <= s_recursionLimit)
2307 s_pBot[N/4](R, A, B);
2310 const size_t N2 = N/2;
2312 RecursiveMultiply(R, T, A0, B0, N2);
2313 RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2314 Add(R1, R1, T0, N2);
2315 RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2316 Add(R1, R1, T0, N2);
2326 void MultiplyTop(word *R, word *T,
const word *L,
const word *A,
const word *B,
size_t N)
2330 if (N <= s_recursionLimit)
2331 s_pTop[N/4](R, A, B, L[N-1]);
2334 const size_t N2 = N/2;
2336 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2337 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2339 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2340 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2342 RecursiveMultiply(T0, T2, R0, R1, N2);
2343 RecursiveMultiply(R0, T2, A1, B1, N2);
2348 int c2 = Subtract(T2, L+N2, L, N2);
2352 c2 -= Add(T2, T2, T0, N2);
2353 t = (Compare(T2, R0, N2) == -1);
2354 c3 = t - Subtract(T2, T2, T1, N2);
2358 c2 += Subtract(T2, T2, T0, N2);
2359 t = (Compare(T2, R0, N2) == -1);
2360 c3 = t + Add(T2, T2, T1, N2);
2365 c3 += Increment(T2, N2, c2);
2367 c3 -= Decrement(T2, N2, -c2);
2368 c3 += Add(R0, T2, R1, N2);
2371 Increment(R1, N2, c3);
2375 inline void Multiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2377 RecursiveMultiply(R, T, A, B, N);
2380 inline void Square(word *R, word *T,
const word *A,
size_t N)
2382 RecursiveSquare(R, T, A, N);
2385 inline void MultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2387 RecursiveMultiplyBottom(R, T, A, B, N);
2395 void AsymmetricMultiply(word *R, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2402 Multiply(R, T, A, B, NA);
2424 R[NB] = LinearMultiply(R, B, A[0], NB);
2428 SetWords(R, 0, NB+2);
2431 CopyWords(R, B, NB);
2432 R[NB] = R[NB+1] = 0;
2440 Multiply(R, T, A, B, NA);
2441 CopyWords(T+2*NA, R+NA, NA);
2443 for (i=2*NA; i<NB; i+=2*NA)
2444 Multiply(T+NA+i, T, A, B+i, NA);
2445 for (i=NA; i<NB; i+=2*NA)
2446 Multiply(R+i, T, A, B+i, NA);
2450 for (i=0; i<NB; i+=2*NA)
2451 Multiply(R+i, T, A, B+i, NA);
2452 for (i=NA; i<NB; i+=2*NA)
2453 Multiply(T+NA+i, T, A, B+i, NA);
2456 if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2457 Increment(R+NB, NA);
2464 void RecursiveInverseModPower2(word *R, word *T,
const word *A,
size_t N)
2470 const size_t N2 = N/2;
2471 RecursiveInverseModPower2(R0, T0, A0, N2);
2473 SetWords(T0+1, 0, N2-1);
2474 MultiplyTop(R1, T1, T0, R0, A0, N2);
2475 MultiplyBottom(T0, T1, R0, A1, N2);
2476 Add(T0, R1, T0, N2);
2477 TwosComplement(T0, N2);
2478 MultiplyBottom(R1, T1, R0, T0, N2);
2482 T[0] = AtomicInverseModPower2(A[0]);
2484 s_pBot[0](T+2, T, A);
2485 TwosComplement(T+2, 2);
2486 Increment(T+2, 2, 2);
2487 s_pBot[0](R, T, T+2);
2497 void MontgomeryReduce(word *R, word *T, word *X,
const word *M,
const word *U,
size_t N)
2500 MultiplyBottom(R, T, X, U, N);
2501 MultiplyTop(T, T+N, X, R, M, N);
2502 word borrow = Subtract(T, X+N, T, N);
2504 word carry = Add(T+N, T, M, N);
2506 CRYPTOPP_UNUSED(carry), CRYPTOPP_UNUSED(borrow);
2507 CopyWords(R, T + ((0-borrow) & N), N);
2509 const word u = 0-U[0];
2511 for (
size_t i=0; i<N; i++)
2513 const word t = u * X[i];
2515 for (
size_t j=0; j<N; j+=2)
2517 MultiplyWords(p, t, M[j]);
2518 Acc2WordsBy1(p, X[i+j]);
2520 X[i+j] = LowWord(p);
2522 MultiplyWords(p, t, M[j+1]);
2523 Acc2WordsBy1(p, X[i+j+1]);
2525 X[i+j+1] = LowWord(p);
2529 if (Increment(X+N+i, N-i, c))
2530 while (!Subtract(X+N, X+N, M, N)) {}
2533 memcpy(R, X+N, N*WORD_SIZE);
2535 __m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2536 for (
size_t i=0; i<N; i++)
2538 __m64 t = _mm_cvtsi32_si64(X[i]);
2539 t = _mm_mul_su32(t, u);
2540 __m64 c = _mm_setzero_si64();
2541 for (
size_t j=0; j<N; j+=2)
2543 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2544 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2545 c = _mm_add_si64(c, p);
2546 X[i+j] = _mm_cvtsi64_si32(c);
2547 c = _mm_srli_si64(c, 32);
2548 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2549 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2550 c = _mm_add_si64(c, p);
2551 X[i+j+1] = _mm_cvtsi64_si32(c);
2552 c = _mm_srli_si64(c, 32);
2555 if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2556 while (!Subtract(X+N, X+N, M, N)) {}
2559 memcpy(R, X+N, N*WORD_SIZE);
2571 void HalfMontgomeryReduce(word *R, word *T,
const word *X,
const word *M,
const word *U,
const word *V,
size_t N)
2585 const size_t N2 = N/2;
2586 Multiply(T0, T2, V0, X3, N2);
2587 int c2 = Add(T0, T0, X0, N);
2588 MultiplyBottom(T3, T2, T0, U, N2);
2589 MultiplyTop(T2, R, T0, T3, M0, N2);
2590 c2 -= Subtract(T2, T1, T2, N2);
2591 Multiply(T0, R, T3, M1, N2);
2592 c2 -= Subtract(T0, T2, T0, N2);
2593 int c3 = -(int)Subtract(T1, X2, T1, N2);
2594 Multiply(R0, T2, V1, X3, N2);
2595 c3 += Add(R, R, T, N);
2598 c3 += Increment(R1, N2);
2600 c3 -= Decrement(R1, N2, -c2);
2604 Subtract(R, R, M, N);
2698 static inline void AtomicDivide(word *Q,
const word *A,
const word *B)
2701 DWord q = DivideFourWordsByTwo<word, DWord>(T,
DWord(A[0], A[1]),
DWord(A[2], A[3]),
DWord(B[0], B[1]));
2702 Q[0] = q.GetLowHalf();
2703 Q[1] = q.GetHighHalf();
2705 #if defined(CRYPTOPP_DEBUG) 2709 CRYPTOPP_ASSERT(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2719 static void CorrectQuotientEstimate(word *R, word *T, word *Q,
const word *B,
size_t N)
2723 AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2725 word borrow = Subtract(R, R, T, N+2);
2727 CRYPTOPP_UNUSED(borrow);
2729 while (R[N] || Compare(R, B, N) >= 0)
2731 R[N] -= Subtract(R, R, B, N);
2732 Q[1] += (++Q[0]==0);
2743 void Divide(word *R, word *Q, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2751 word *
const TB=T+NA+2;
2752 word *
const TP=T+NA+2+NB;
2755 unsigned shiftWords = (B[NB-1]==0);
2756 TB[0] = TB[NB-1] = 0;
2757 CopyWords(TB+shiftWords, B, NB-shiftWords);
2758 unsigned shiftBits = WORD_BITS -
BitPrecision(TB[NB-1]);
2760 ShiftWordsLeftByBits(TB, NB, shiftBits);
2763 TA[0] = TA[NA] = TA[NA+1] = 0;
2764 CopyWords(TA+shiftWords, A, NA);
2765 ShiftWordsLeftByBits(TA, NA+2, shiftBits);
2767 if (TA[NA+1]==0 && TA[NA] <= 1)
2769 Q[NA-NB+1] = Q[NA-NB] = 0;
2770 while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
2772 TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
2783 BT[0] = TB[NB-2] + 1;
2784 BT[1] = TB[NB-1] + (BT[0]==0);
2787 for (
size_t i=NA-2; i>=NB; i-=2)
2789 AtomicDivide(Q+i-NB, TA+i-2, BT);
2790 CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
2794 CopyWords(R, TA+shiftWords, NB);
2795 ShiftWordsRightByBits(R, NB, shiftBits);
2798 static inline size_t EvenWordCount(
const word *X,
size_t N)
2800 while (N && X[N-2]==0 && X[N-1]==0)
2811 unsigned int AlmostInverse(word *R, word *T,
const word *A,
size_t NA,
const word *M,
size_t N)
2819 size_t bcLen=2, fgLen=EvenWordCount(M, N);
2823 SetWords(T, 0, 3*N);
2825 CopyWords(f, A, NA);
2833 if (EvenWordCount(f, fgLen)==0)
2839 ShiftWordsRightByWords(f, fgLen, 1);
2840 bcLen += 2 * (c[bcLen-1] != 0);
2842 ShiftWordsLeftByWords(c, bcLen, 1);
2852 if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0)
2855 Subtract(R, M, b, N);
2861 ShiftWordsRightByBits(f, fgLen, i);
2862 t = ShiftWordsLeftByBits(c, bcLen, i);
2864 bcLen += 2 * (t!=0);
2867 bool swap = Compare(f, g, fgLen)==-1;
2872 fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]);
2874 Subtract(f, f, g, fgLen);
2875 t = Add(b, b, c, bcLen);
2886 void DivideByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2893 ShiftWordsRightByBits(R, N, 1);
2896 word carry = Add(R, R, M, N);
2897 ShiftWordsRightByBits(R, N, 1);
2898 R[N-1] += carry<<(WORD_BITS-1);
2907 void MultiplyByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2912 if (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0)
2913 Subtract(R, R, M, N);
2918 static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
2920 static inline size_t RoundupSize(
size_t n)
2923 return RoundupSizeTable[n];
2935 : reg(2), sign(POSITIVE)
2937 reg[0] = reg[1] = 0;
2941 : reg(RoundupSize(t.WordCount())), sign(t.sign)
2943 CopyWords(reg, t.reg, reg.
size());
2949 reg[0] = word(value);
2950 reg[1] = word(SafeRightShift<WORD_BITS>(value));
2963 reg[0] = word(value);
2964 reg[1] = word(SafeRightShift<WORD_BITS>((
unsigned long)value));
2979 unsigned long value = (
unsigned long)reg[0];
2980 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2983 return (
signed long)value >= 0;
2985 return -(
signed long)value < 0;
2992 unsigned long value = (
unsigned long)reg[0];
2993 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2994 return sign==
POSITIVE ? value : -(
signed long)value;
3003 Decode(encodedInteger, byteCount, s);
3008 encodedInteger.
Get(block, block.
size());
3022 Decode(encodedInteger, byteCount, s);
3027 #if (_MSC_FULL_VER >= 140050727) 3028 std::reverse_copy(encodedInteger, encodedInteger+byteCount,
3029 stdext::make_checked_array_iterator(block.
begin(), block.
size()));
3031 std::reverse_copy(encodedInteger, encodedInteger+byteCount, block.
begin());
3051 if (!
Randomize(rng, min, max, rnType, equiv, mod))
3071 if (reg.
size() != t.reg.
size() || t.reg[t.reg.
size()/2] == 0)
3073 CopyWords(reg, t.reg, reg.
size());
3083 if (n/WORD_BITS < reg.
size())
3084 return bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1);
3094 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
3098 if (n/WORD_BITS < reg.
size())
3099 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
3107 if (n/WORD_SIZE < reg.
size())
3108 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
3116 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
3117 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
3124 for (
unsigned int j=0; j<n; j++)
3125 v |= lword(
GetBit(i+j)) << j;
3146 std::swap(sign, a.sign);
3150 : reg(RoundupSize(length)), sign(POSITIVE)
3153 SetWords(reg+1, 0, reg.
size()-1);
3161 int radix, sign = 1;
3164 unsigned int length;
3165 for (length = 0; str[length] != 0; length++) {}
3172 switch (str[length-1])
3194 str += 1, length -= 1;
3197 if (length > 2 && str[0] ==
'0' && (str[1] ==
'x' || str[1] ==
'X'))
3200 str += 2, length -= 2;
3205 for (
unsigned int i=0; i<length; i++)
3207 int digit, ch =
static_cast<int>(str[i]);
3211 if (ch >=
'0' && ch <=
'9')
3213 else if (ch >=
'a' && ch <=
'f')
3214 digit = ch -
'a' + 10;
3215 else if (ch >=
'A' && ch <=
'F')
3216 digit = ch -
'A' + 10;
3230 unsigned int nh = 0, nl = 0, nc = 0;
3233 for (
unsigned int i=0; i<length; i++)
3235 int digit, ch =
static_cast<int>(str[i]);
3237 if (ch >=
'0' && ch <=
'9')
3239 else if (ch >=
'a' && ch <=
'f')
3240 digit = ch -
'a' + 10;
3241 else if (ch >=
'A' && ch <=
'F')
3242 digit = ch -
'A' + 10;
3255 v += position * (nh << 4 | nl);
3256 nc = 0, position <<= 8;
3266 for (
int i=static_cast<int>(length)-1; i>=0; i--)
3268 int digit, ch =
static_cast<int>(str[i]);
3270 if (ch >=
'0' && ch <=
'9')
3272 else if (ch >=
'a' && ch <=
'f')
3273 digit = ch -
'a' + 10;
3274 else if (ch >=
'A' && ch <=
'F')
3275 digit = ch -
'A' + 10;
3294 : reg(2), sign(POSITIVE)
3296 *
this = StringToInteger(str,order);
3300 : reg(2), sign(POSITIVE)
3302 *
this = StringToInteger(str,order);
3307 return (
unsigned int)CountWords(reg, reg.
size());
3314 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
3323 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
3332 Decode(store, inputLen, s);
3345 while (inputLen>0 && (sign==
POSITIVE ? b==0 : b==0xff))
3353 for (
size_t i=inputLen; i > 0; i--)
3356 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
3361 for (
size_t i=inputLen; i<reg.
size()*WORD_SIZE; i++)
3362 reg[i/WORD_SIZE] |= word(0xff) << (i%WORD_SIZE)*8;
3363 TwosComplement(reg, reg.
size());
3372 const bool pre = (signedness ==
UNSIGNED);
3387 Encode(sink, outputLen, signedness);
3394 for (
size_t i=outputLen; i > 0; i--)
3422 if (!dec.IsDefiniteLength() || dec.
MaxRetrievable() < dec.RemainingLength())
3438 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
3454 word16 bitCount = word16(
BitCount());
3458 return 2 + byteCount;
3478 const size_t nbytes = nbits/8 + 1;
3482 buf[0] = (byte)
Crop(buf[0], nbits % 8);
3492 const unsigned int nbits = range.
BitCount();
3498 while (*
this > range);
3505 return GenerateRandomNoThrow(rng,
MakeParameters(
"Min", min)(
"Max", max)(
"RandomNumberType", rnType)(
"EquivalentTo", equiv)(
"Mod", mod));
3511 KDF2_RNG(
const byte *seed,
size_t seedSize)
3512 : m_counter(0), m_counterAndSeed(seedSize + 4)
3514 memcpy(m_counterAndSeed + 4, seed, seedSize);
3549 throw InvalidArgument(
"Integer: invalid EquivalentTo and/or Mod argument");
3568 bq.
Get(finalSeed, finalSeed.size());
3569 kdf2Rng.reset(
new KDF2_RNG(finalSeed.begin(), finalSeed.size()));
3580 Integer min1 = min + (equiv-min)%mod;
3601 if (
FirstPrime(first, max, equiv, mod, pSelector))
3605 if (!
FirstPrime(first, max, equiv, mod, pSelector))
3613 if (
FirstPrime(*
this,
STDMIN(*
this+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector))
3623 std::istream& operator>>(std::istream& in,
Integer &a)
3626 unsigned int length = 0;
3635 if (length >= str.
size())
3636 str.
Grow(length + 16);
3638 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==
'.'));
3642 str[length-1] =
'\0';
3649 inline int FlagToBase(
long f) {
3650 return f == std::ios::hex ? 16 : (f == std::ios::oct ? 8 : 10);
3653 inline char FlagToSuffix(
long f) {
3654 return f == std::ios::hex ?
'h' : (f == std::ios::oct ?
'o' :
'.');
3658 std::ostream& operator<<(std::ostream& out,
const Integer &a)
3661 const long f = out.flags() & std::ios::basefield;
3662 const int base = FlagToBase(f);
3663 const char suffix = FlagToSuffix(f);
3675 static const char upper[]=
"0123456789ABCDEF";
3676 static const char lower[]=
"0123456789abcdef";
3678 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3695 #ifdef CRYPTOPP_USE_STD_SHOWBASE 3696 if (out.flags() & std::ios_base::showbase)
3701 return out << suffix;
3709 if (Increment(reg, reg.
size()))
3712 reg[reg.
size()/2]=1;
3717 word borrow = Decrement(reg, reg.
size());
3730 if (Increment(reg, reg.
size()))
3733 reg[reg.
size()/2]=1;
3738 if (Decrement(reg, reg.
size()))
3752 else if (reg.
size() >= t.reg.
size())
3755 AndWords(result.reg, reg, t.reg.
size());
3763 AndWords(result.reg, t.reg, reg.
size());
3778 else if (reg.
size() >= t.reg.
size())
3781 OrWords(result.reg, t.reg, t.reg.
size());
3789 OrWords(result.reg, reg, reg.
size());
3804 else if (reg.
size() >= t.reg.
size())
3807 XorWords(result.reg, t.reg, t.reg.
size());
3815 XorWords(result.reg, reg, reg.
size());
3826 int carry;
const bool pre = (a.reg.size() == b.reg.size());
3827 if (!pre && a.reg.size() > b.reg.size())
3829 carry = Add(sum.reg, a.reg, b.reg, b.reg.size());
3830 CopyWords(sum.reg+b.reg.size(), a.reg+b.reg.size(), a.reg.size()-b.reg.size());
3831 carry = Increment(sum.reg+b.reg.size(), a.reg.size()-b.reg.size(), carry);
3835 carry = Add(sum.reg, a.reg, b.reg, a.reg.size());
3839 carry = Add(sum.reg, a.reg, b.reg, a.reg.size());
3840 CopyWords(sum.reg+a.reg.size(), b.reg+a.reg.size(), b.reg.size()-a.reg.size());
3841 carry = Increment(sum.reg+a.reg.size(), b.reg.size()-a.reg.size(), carry);
3847 sum.reg[sum.reg.
size()/2] = 1;
3854 unsigned aSize = a.WordCount();
3856 unsigned bSize = b.WordCount();
3863 word borrow = Subtract(diff.reg, a.reg, b.reg, bSize);
3864 CopyWords(diff.reg+bSize, a.reg+bSize, aSize-bSize);
3865 borrow = Decrement(diff.reg+bSize, aSize-bSize, borrow);
3869 else if (aSize == bSize)
3871 if (Compare(a.reg, b.reg, aSize) >= 0)
3873 Subtract(diff.reg, a.reg, b.reg, aSize);
3878 Subtract(diff.reg, b.reg, a.reg, aSize);
3884 word borrow = Subtract(diff.reg, b.reg, a.reg, aSize);
3885 CopyWords(diff.reg+aSize, b.reg+aSize, bSize-aSize);
3886 borrow = Decrement(diff.reg+aSize, bSize-aSize, borrow);
3893 template <
class T>
inline const T& STDMAX2(
const T& a,
const T& b)
3895 return a < b ? b : a;
3900 Integer sum((word)0, STDMAX2(reg.
size(), b.reg.size()));
3903 if (b.NotNegative())
3904 PositiveAdd(sum, *
this, b);
3906 PositiveSubtract(sum, *
this, b);
3910 if (b.NotNegative())
3911 PositiveSubtract(sum, b, *
this);
3914 PositiveAdd(sum, *
this, b);
3927 PositiveAdd(*
this, *
this, t);
3929 PositiveSubtract(*
this, *
this, t);
3934 PositiveSubtract(*
this, t, *
this);
3937 PositiveAdd(*
this, *
this, t);
3946 Integer diff((word)0, STDMAX2(reg.
size(), b.reg.size()));
3949 if (b.NotNegative())
3950 PositiveSubtract(diff, *
this, b);
3952 PositiveAdd(diff, *
this, b);
3956 if (b.NotNegative())
3958 PositiveAdd(diff, *
this, b);
3962 PositiveSubtract(diff, b, *
this);
3973 PositiveSubtract(*
this, *
this, t);
3975 PositiveAdd(*
this, *
this, t);
3981 PositiveAdd(*
this, *
this, t);
3985 PositiveSubtract(*
this, t, *
this);
3993 const size_t shiftWords = n / WORD_BITS;
3994 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3997 ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords);
3998 ShiftWordsLeftByBits(reg+shiftWords, wordCount+
BitsToWords(shiftBits), shiftBits);
4005 const size_t shiftWords = n / WORD_BITS;
4006 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
4008 ShiftWordsRightByWords(reg, wordCount, shiftWords);
4009 if (wordCount > shiftWords)
4010 ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits);
4022 AndWords(reg, t.reg, size);
4034 OrWords(reg, t.reg, t.reg.
size());
4038 const size_t head = reg.
size();
4039 const size_t tail = t.reg.
size() - reg.
size();
4041 OrWords(reg, t.reg, head);
4042 CopyWords(reg+head,t.reg+head,tail);
4059 XorWords(reg, t.reg, t.reg.
size());
4063 const size_t head = reg.
size();
4064 const size_t tail = t.reg.
size() - reg.
size();
4066 XorWords(reg, t.reg, head);
4067 CopyWords(reg+head,t.reg+head,tail);
4076 size_t aSize = RoundupSize(a.WordCount());
4077 size_t bSize = RoundupSize(b.WordCount());
4079 product.reg.
CleanNew(RoundupSize(aSize+bSize));
4083 AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
4088 PositiveMultiply(product, a, b);
4090 if (a.NotNegative() != b.NotNegative())
4097 Multiply(product, *
this, b);
4126 unsigned aSize = a.WordCount();
4127 unsigned bSize = b.WordCount();
4143 remainder.reg.
CleanNew(RoundupSize(bSize));
4145 quotient.reg.
CleanNew(RoundupSize(aSize-bSize+2));
4149 Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
4154 PositiveDivide(remainder, quotient, dividend, divisor);
4176 if (wordCount <= a.WordCount())
4178 r.reg.
resize(RoundupSize(wordCount));
4179 CopyWords(r.reg, a.reg, wordCount);
4180 SetWords(r.reg+wordCount, 0, r.reg.
size()-wordCount);
4181 if (n % WORD_BITS != 0)
4182 r.reg[wordCount-1] %= (word(1) << (n % WORD_BITS));
4186 r.reg.
resize(RoundupSize(a.WordCount()));
4187 CopyWords(r.reg, a.reg, r.reg.
size());
4191 if (a.IsNegative() && r.
NotZero())
4217 if ((divisor & (divisor-1)) == 0)
4220 remainder = dividend.reg[0] & (divisor-1);
4225 quotient.reg.
CleanNew(RoundupSize(i));
4229 quotient.reg[i] =
DWord(dividend.reg[i], remainder) / divisor;
4230 remainder =
DWord(dividend.reg[i], remainder) % divisor;
4241 remainder = divisor - remainder;
4263 if ((divisor & (divisor-1)) != 0)
4272 remainder =
DWord(reg[i], remainder) % divisor;
4279 remainder = sum % divisor;
4284 remainder = reg[0] & (divisor-1);
4288 remainder = divisor - remainder;
4296 sign =
Sign(1-sign);
4299 int Integer::PositiveCompare(
const Integer& t)
const 4305 return size > tSize ? 1 : -1;
4307 return CryptoPP::Compare(reg, t.reg, size);
4315 return PositiveCompare(t);
4324 return -PositiveCompare(t);
4340 y = (x + *
this/x) >> 1;
4354 return (
WordCount() == 1) && (reg[0] == 1);
4370 return mr.Exponentiate(x, e);
4393 return !u ?
Zero() : (m*(*
this-u)+1)/(*this);
4398 unsigned k = AlmostInverse(r.reg, T, reg, reg.
size(), m.reg, m.reg.
size());
4399 DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.
size());
4405 word g0 = mod, g1 = *
this % mod;
4406 word v0 = 0, v1 = 1;
4434 if (oid != ASN1::prime_field())
4444 ASN1::prime_field().DEREncode(seq);
4461 if (a.reg.size()==m_modulus.reg.
size())
4463 CryptoPP::DivideByPower2Mod(m_result.reg.
begin(), a.reg, 1, m_modulus.reg, a.reg.size());
4467 return m_result1 = (a.IsEven() ? (a >> 1) : ((a+m_modulus) >> 1));
4472 if (a.reg.size()==m_modulus.reg.
size() && b.reg.size()==m_modulus.reg.
size())
4474 if (CryptoPP::Add(m_result.reg.
begin(), a.reg, b.reg, a.reg.size())
4475 || Compare(m_result.reg, m_modulus.reg, a.reg.size()) >= 0)
4477 CryptoPP::Subtract(m_result.reg.
begin(), m_result.reg, m_modulus.reg, a.reg.size());
4484 if (m_result1 >= m_modulus)
4485 m_result1 -= m_modulus;
4492 if (a.reg.size()==m_modulus.reg.
size() && b.reg.size()==m_modulus.reg.
size())
4494 if (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.size())
4495 || Compare(a.reg, m_modulus.reg, a.reg.size()) >= 0)
4497 CryptoPP::Subtract(a.reg, a.reg, m_modulus.reg, a.reg.size());
4512 if (a.reg.size()==m_modulus.reg.
size() && b.reg.size()==m_modulus.reg.
size())
4514 if (CryptoPP::Subtract(m_result.reg.
begin(), a.reg, b.reg, a.reg.size()))
4515 CryptoPP::Add(m_result.reg.
begin(), m_result.reg, m_modulus.reg, a.reg.size());
4522 m_result1 += m_modulus;
4529 if (a.reg.size()==m_modulus.reg.
size() && b.reg.size()==m_modulus.reg.
size())
4531 if (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.size()))
4532 CryptoPP::Add(a.reg, a.reg, m_modulus.reg, a.reg.size());
4549 CopyWords(m_result.reg.
begin(), m_modulus.reg, m_modulus.reg.
size());
4550 if (CryptoPP::Subtract(m_result.reg.
begin(), m_result.reg, a.reg, a.reg.size()))
4551 Decrement(m_result.reg.
begin()+a.reg.size(), m_modulus.reg.
size()-a.reg.size());
4558 if (m_modulus.
IsOdd())
4569 if (m_modulus.
IsOdd())
4573 for (
unsigned int i=0; i<exponentsCount; i++)
4582 m_u((word)0, m_modulus.reg.size()),
4583 m_workspace(5*m_modulus.reg.size())
4585 if (!m_modulus.IsOdd())
4586 throw InvalidArgument(
"MontgomeryRepresentation: Montgomery representation requires an odd modulus");
4588 RecursiveInverseModPower2(m_u.reg, m_workspace, m_modulus.reg, m_modulus.reg.
size());
4593 word *
const T = m_workspace.
begin();
4594 word *
const R = m_result.reg.begin();
4595 const size_t N = m_modulus.reg.size();
4598 AsymmetricMultiply(T, T+2*N, a.reg, a.reg.size(), b.reg, b.reg.size());
4599 SetWords(T+a.reg.size()+b.reg.size(), 0, 2*N-a.reg.size()-b.reg.size());
4600 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4606 word *
const T = m_workspace.
begin();
4607 word *
const R = m_result.reg.begin();
4608 const size_t N = m_modulus.reg.size();
4611 CryptoPP::Square(T, T+2*N, a.reg, a.reg.size());
4612 SetWords(T+2*a.reg.size(), 0, 2*N-2*a.reg.size());
4613 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4619 word *
const T = m_workspace.
begin();
4620 word *
const R = m_result.reg.begin();
4621 const size_t N = m_modulus.reg.size();
4624 CopyWords(T, a.reg, a.reg.size());
4625 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
4626 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4633 word *
const T = m_workspace.
begin();
4634 word *
const R = m_result.reg.begin();
4635 const size_t N = m_modulus.reg.size();
4638 CopyWords(T, a.reg, a.reg.size());
4639 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
4640 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4641 unsigned k = AlmostInverse(R, T, R, N, m_modulus.reg, N);
4646 DivideByPower2Mod(R, R, k-N*WORD_BITS, m_modulus.reg, N);
4648 MultiplyByPower2Mod(R, R, N*WORD_BITS-k, m_modulus.reg, N);
4655 template <> CRYPTOPP_DLL
4659 static const unsigned int BIT_32 = (1U << 31);
4660 const bool UPPER = !!(base & BIT_32);
4661 static const unsigned int BIT_31 = (1U << 30);
4662 const bool BASE = !!(base & BIT_31);
4664 const char CH = UPPER ?
'A' :
'a';
4665 base &= ~(BIT_32|BIT_31);
4671 bool negative =
false, zero =
false;
4672 if (value.IsNegative())
4689 s[i++]=char((digit < 10 ?
'0' : (CH - 10)) + digit);
4694 result.reserve(i+2);
4709 else if (base == 16)
4721 template <> CRYPTOPP_DLL
4725 static const unsigned int HIGH_BIT = (1U << 31);
4726 const char CH = !!(base & HIGH_BIT) ?
'A' :
'a';
4736 word64 digit = value % base;
4737 result = char((digit < 10 ?
'0' : (CH - 10)) + digit) + result;
4743 #ifndef CRYPTOPP_NO_ASSIGN_TO_INTEGER 4746 bool AssignIntToInteger(
const std::type_info &valueType,
void *pInteger,
const void *pInt)
4748 if (valueType !=
typeid(
Integer))
4750 *
reinterpret_cast<Integer *
>(pInteger) = *reinterpret_cast<const int *>(pInt);
4753 #endif // CRYPTOPP_NO_ASSIGN_TO_INTEGER 4762 SetFunctionPointers();
4770 #if HAVE_GCC_INIT_PRIORITY 4772 #elif defined(HAVE_MSC_INIT_PRIORITY) 4773 #pragma warning(disable: 4075) 4774 #pragma init_seg(".CRT$XCU") 4776 # if defined(USE_MSC_INIT_PRIORITY) 4781 #pragma warning(default: 4075) 4790 #if defined(CRYPTOPP_CXX11_DYNAMIC_INIT) 4793 #elif defined(HAVE_MSC_INIT_PRIORITY) && defined(USE_MSC_INIT_PRIORITY) 4802 #if defined(CRYPTOPP_CXX11_DYNAMIC_INIT) 4805 #elif defined(HAVE_MSC_INIT_PRIORITY) && defined(USE_MSC_INIT_PRIORITY) 4814 #if defined(CRYPTOPP_CXX11_DYNAMIC_INIT) 4817 #elif defined(HAVE_MSC_INIT_PRIORITY) && defined(USE_MSC_INIT_PRIORITY) 4826 #endif // CRYPTOPP_IMPORTS Used to pass byte array input as part of a NameValuePairs object.
An invalid argument was detected.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
Integer MultiplicativeInverse() const
return inverse if 1 or -1, otherwise return 0
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
bool NotZero() const
Determines if the Integer is non-0.
Classes for working with NameValuePairs.
Integer Or(const Integer &t) const
Bitwise OR.
Integer & operator|=(const Integer &t)
Bitwise OR Assignment.
void swap(SecBlock< T, A > &b)
Swap contents with another SecBlock.
Integer And(const Integer &t) const
Bitwise AND.
a number which is probabilistically prime
Utility functions for the Crypto++ library.
Integer Plus(const Integer &b) const
Addition.
ByteOrder
Provides the byte ordering.
Restricts the instantiation of a class to one static object without locks.
void CleanNew(size_type newSize)
Change size without preserving contents.
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
bool IsSquare() const
Determine whether this integer is a perfect square.
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
size_t size() const
Length of the memory block.
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
This file contains helper classes/functions for implementing public key algorithms.
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
Encode absolute value as big-endian octet string.
Integer & operator=(const Integer &t)
Assignment.
bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
static Integer Gcd(const Integer &a, const Integer &n)
greatest common divisor
void resize(size_type newSize)
Change size and preserve contents.
Integer & operator+=(const Integer &t)
Addition Assignment.
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
void PutWord(bool assumeAligned, ByteOrder order, byte *block, T value, const byte *xorBlock=NULL)
Access a block of memory.
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
void CleanGrow(size_type newSize)
Change size and preserve contents.
Integer & operator--()
Pre-decrement.
virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Secure memory block with allocator and cleanup.
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
signed long ConvertToLong() const
Convert the Integer to Long.
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
void OpenPGPDecode(const byte *input, size_t inputLen)
Decode from OpenPGP format.
Signedness
Used when importing and exporting integers.
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
ASN.1 object identifiers for algorthms and schemes.
Classes for automatic resource management.
bool IsP4()
Determines if the CPU is an Intel P4.
bool IsNegative() const
Determines if the Integer is negative.
lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Library configuration file.
MontgomeryRepresentation(const Integer &modulus)
Construct a MontgomeryRepresentation.
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.
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
std::string IntToString< word64 >(word64 value, unsigned int base)
Converts an unsigned value to a string.
void New(size_type newSize)
Change size without preserving contents.
void SetByte(size_t n, byte value)
Set the n-th byte to value.
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
bool IsPositive() const
Determines if the Integer is positive.
bool NotNegative() const
Determines if the Integer is non-negative.
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
static const Integer & One()
Integer representing 1.
Integer & Accumulate(Integer &a, const Integer &b) const
TODO.
P1363 key derivation function.
byte order is little-endian
Sign
Used internally to represent the integer.
Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
bool operator!() const
Negation.
Pointer that overloads operator ->
bool IsUnit() const
is 1 or -1
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Classes and functions for secure memory allocations.
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Integer Modulo(const Integer &b) const
Remainder.
Copy input to a memory buffer.
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
size_t MinEncodedSize(Signedness sign=UNSIGNED) const
Minimum number of bytes to encode this integer.
Integer DividedBy(const Integer &b) const
Division.
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
Integer Times(const Integer &b) const
Multiplication.
a number with no special properties
const byte * begin() const
Pointer to the first byte in the memory block.
Integer & operator++()
Pre-increment.
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
void swap(Integer &a)
Swaps this Integer with another Integer.
Integer()
Creates the zero integer.
unsigned int TrailingZeros(word32 v)
Determines the number of trailing 0-bits in a value.
Integer & operator<<=(size_t n)
Left-shift Assignment.
Exception thrown when an error is encountered decoding an OpenPGP integer.
void Negate()
Reverse the Sign of the Integer.
int Compare(const Integer &a) const
Perform signed comparison.
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
Decode nonnegative value from big-endian octet string.
Application callback to signal suitability of a cabdidate prime.
void ConditionalSwapPointers(bool c, T &a, T &b)
Performs a branchless swap of pointers a and b if condition c is true.
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Multiple precision integer with arithmetic operations.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
size_t OpenPGPEncode(byte *output, size_t bufferSize) const
Encode absolute value in OpenPGP format.
const Integer & Half(const Integer &a) const
Divides an element by 2.
static const Integer & Two()
Integer representing 2.
const Integer & Square(const Integer &a) const
Square an element in the ring.
Integer & operator^=(const Integer &t)
Bitwise XOR Assignment.
#define MEMORY_BARRIER
A memory barrier.
RandomNumberType
Properties of a random integer.
const char * Seed()
ConstByteArrayParameter.
bool IsEven() const
Determines if the Integer is even parity.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
String-based implementation of Store interface.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
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))
ModularArithmetic(const Integer &modulus=Integer::One())
Construct a ModularArithmetic.
void BERDecodeError()
Raises a BERDecodeErr.
Data structure used to store byte strings.
Functions for CPU features and intrinsics.
Classes and functions for working with ANS.1 objects.
Classes for SHA-1 and SHA-2 family of message digests.
void SetBit(size_t n, bool value=1)
Set the n-th bit to value.
iterator begin()
Provides an iterator pointing to the first element in the memory block.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
const char * PointerToPrimeSelector()
const PrimeSelector *
Implementation of BufferedTransformation's attachment interface.
Classes and functions for number theoretic operations.
byte GetByte(size_t i) const
Provides the i-th byte of the Integer.
Exception thrown when division by 0 is encountered.
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
Integer Squared() const
Multiply this integer by itself.
T1 SaturatingSubtract1(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 1.
Exception thrown when a random number cannot be found that satisfies the condition.
Performs modular arithmetic in Montgomery representation for increased speed.
bool HasSSE2()
Determines SSE2 availability.
Integer Minus(const Integer &b) const
Subtraction.
void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the ring.
Multiple precision integer with arithmetic operations.
Integer Xor(const Integer &t) const
Bitwise XOR.
static const Integer & Zero()
Integer representing 0.
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
void Grow(size_type newSize)
Change size and preserve contents.
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
std::string IntToString< Integer >(Integer value, unsigned int base)
Converts an Integer to a string.
Class file for performing modular arithmetic.
Crypto++ library namespace.
bool GetValue(const char *name, T &value) const
Get a named value.
Integer & operator>>=(size_t n)
Right-shift Assignment.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Integer SquareRoot() const
Extract square root.
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
bool IsConvertableToLong() const
Determines if the Integer is convertable to Long.
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Integer AbsoluteValue() const
Retrieve the absolute value of this integer.
Integer & operator-=(const Integer &t)
Subtraction Assignment.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
size_type size() const
Provides the count of elements in the SecBlock.
Integer & operator &=(const Integer &t)
Bitwise AND Assignment.
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
lword GetBits(size_t i, size_t n) const
Provides the low order bits of the Integer.
Integer operator-() const
Subtraction.
the value is positive or 0
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the ring.
bool IsOdd() const
Determines if the Integer is odd parity.
virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the Ring.
Interface for retrieving values given their names.
Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.