7 #if CRYPTOPP_MSC_VERSION 8 # pragma warning(disable: 4100) 11 #if CRYPTOPP_GCC_DIAGNOSTIC_AVAILABLE 12 # pragma GCC diagnostic ignored "-Wunused" 13 # pragma GCC diagnostic ignored "-Wunused-but-set-variable" 16 #ifndef CRYPTOPP_IMPORTS 43 #ifdef CRYPTOPP_MSVC6_NO_PP 44 #pragma message("You do not seem to have the Visual C++ Processor Pack installed, so use of SSE2 instructions will be disabled.") 49 #if CRYPTOPP_BOOL_X32 || defined(CRYPTOPP_DISABLE_INTEL_ASM) 50 # undef CRYPTOPP_X86_ASM_AVAILABLE 51 # undef CRYPTOPP_X32_ASM_AVAILABLE 52 # undef CRYPTOPP_X64_ASM_AVAILABLE 53 # undef CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE 54 # undef CRYPTOPP_BOOL_SSSE3_ASM_AVAILABLE 55 # define CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE 0 56 # define CRYPTOPP_BOOL_SSSE3_ASM_AVAILABLE 0 58 # define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE && CRYPTOPP_BOOL_X86) 64 #if __ARMEL__ && (CRYPTOPP_GCC_VERSION >= 50200) && (CRYPTOPP_GCC_VERSION < 50300) && __OPTIMIZE__ 65 # define WORKAROUND_ARMEL_BUG 1 69 #if (__aarch64__ || __AARCH64EL__) && (CRYPTOPP_GCC_VERSION >= 50200) && (CRYPTOPP_GCC_VERSION < 50300) 70 # define WORKAROUND_ARM64_BUG 1 73 #if WORKAROUND_ARMEL_BUG 74 # pragma GCC push_options 75 # pragma GCC optimize("O1") 78 #if WORKAROUND_ARM64_BUG 79 # pragma GCC push_options 80 # pragma GCC optimize("no-devirtualize") 83 bool AssignIntToInteger(
const std::type_info &valueType,
void *pInteger,
const void *pInt)
85 if (valueType !=
typeid(
Integer))
87 *
reinterpret_cast<Integer *
>(pInteger) = *reinterpret_cast<const int *>(pInt);
91 inline static int Compare(
const word *A,
const word *B,
size_t N)
102 inline static int Increment(word *A,
size_t N, word B=1)
109 for (
unsigned i=1; i<N; i++)
115 inline static int Decrement(word *A,
size_t N, word B=1)
122 for (
unsigned i=1; i<N; i++)
128 static void TwosComplement(word *A,
size_t N)
131 for (
unsigned i=0; i<N; i++)
135 static word AtomicInverseModPower2(word A)
141 for (
unsigned i=3; i<WORD_BITS; i*=2)
150 #if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE)) 151 #define Declare2Words(x) word x##0, x##1; 152 #define AssignWord(a, b) a##0 = b; a##1 = 0; 153 #define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c); 154 #define LowWord(a) a##0 155 #define HighWord(a) a##1 157 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1); 158 #ifndef __INTEL_COMPILER 159 #define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2; 161 #elif defined(__DECCXX) 162 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b); 163 #elif defined(__x86_64__) 164 #if defined(__SUNPRO_CC) && __SUNPRO_CC < 0x5100 166 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc"); 168 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc"); 169 #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"); 170 #define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc"); 171 #define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc"); 172 #define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc"); 173 #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"); 176 #define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b) 178 #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; 181 #define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1; 183 #define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);} 184 #define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);} 185 #define GetCarry(u) u##1 186 #define GetBorrow(u) u##1 188 #define Declare2Words(x) dword x; 189 #if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER) 190 #define MultiplyWords(p, a, b) p = __emulu(a, b); 192 #define MultiplyWords(p, a, b) p = (dword)a*b; 194 #define AssignWord(a, b) a = b; 195 #define Add2WordsBy1(a, b, c) a = b + c; 196 #define Acc2WordsBy2(a, b) a += b; 197 #define LowWord(a) word(a) 198 #define HighWord(a) word(a>>WORD_BITS) 199 #define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2; 200 #define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u); 201 #define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u); 202 #define GetCarry(u) HighWord(u) 203 #define GetBorrow(u) word(u>>(WORD_BITS*2-1)) 206 #define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p)); 209 #define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b) 212 #define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e)); 220 #if (defined(__COVERITY__) || !defined(NDEBUG)) && defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 222 DWord() : m_whole(0) {memset(&m_whole, 0xa,
sizeof(m_whole));}
223 #elif (defined(__COVERITY__) || !defined(NDEBUG)) && !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 225 DWord() : m_halfs() {memset(&m_halfs, 0xa,
sizeof(m_halfs));}
230 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 231 explicit DWord(word low) : m_whole(low) {}
233 explicit DWord(word low)
240 DWord(word low, word high)
246 static DWord Multiply(word a, word b)
249 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 250 r.m_whole = (dword)a * b;
251 #elif defined(MultiplyWordsLoHi) 252 MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
259 static DWord MultiplyAndAdd(word a, word b, word c)
261 DWord r = Multiply(a, b);
265 DWord & operator+=(word a)
267 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 268 m_whole = m_whole + a;
271 m_halfs.high += (m_halfs.low < a);
276 DWord operator+(word a)
279 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 280 r.m_whole = m_whole + a;
282 r.m_halfs.low = m_halfs.low + a;
283 r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a);
291 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 292 r.m_whole = m_whole - a.m_whole;
294 r.m_halfs.low = m_halfs.low - a.m_halfs.low;
295 r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low);
300 DWord operator-(word a)
303 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 304 r.m_whole = m_whole - a;
306 r.m_halfs.low = m_halfs.low - a;
307 r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low);
313 word operator/(word divisor);
315 word operator%(word a);
317 bool operator!()
const 319 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 322 return !m_halfs.high && !m_halfs.low;
326 word GetLowHalf()
const {
return m_halfs.low;}
327 word GetHighHalf()
const {
return m_halfs.high;}
328 word GetHighHalfAsBorrow()
const {
return 0-m_halfs.high;}
333 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 338 #ifdef IS_LITTLE_ENDIAN 354 #if defined(__COVERITY__) 355 Word() : m_whole(0) {}
356 #elif !defined(NDEBUG) 358 Word() : m_whole(0) {memset(&m_whole, 0xa,
sizeof(m_whole));}
363 Word(word value) : m_whole(value) {}
364 Word(hword low, hword high) : m_whole(low | (word(high) << (WORD_BITS/2))) {}
366 static Word Multiply(hword a, hword b)
369 r.m_whole = (word)a * b;
376 r.m_whole = m_whole - a.m_whole;
380 Word operator-(hword a)
383 r.m_whole = m_whole - a;
388 hword operator/(hword divisor)
390 return hword(m_whole / divisor);
393 bool operator!()
const 398 word GetWhole()
const {
return m_whole;}
399 hword GetLowHalf()
const {
return hword(m_whole);}
400 hword GetHighHalf()
const {
return hword(m_whole>>(WORD_BITS/2));}
401 hword GetHighHalfAsBorrow()
const {
return 0-hword(m_whole>>(WORD_BITS/2));}
408 template <
class S,
class D>
409 S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULL)
411 CRYPTOPP_UNUSED(dummy);
414 assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));
421 Q = D(A[1], A[2]) / S(B1+1);
423 Q = D(A[0], A[1]) / B0;
426 D p = D::Multiply(B0, Q);
427 D u = (D) A[0] - p.GetLowHalf();
428 A[0] = u.GetLowHalf();
429 u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q);
430 A[1] = u.GetLowHalf();
431 A[2] += u.GetHighHalf();
434 while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
437 A[0] = u.GetLowHalf();
438 u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
439 A[1] = u.GetLowHalf();
440 A[2] += u.GetHighHalf();
449 template <
class S,
class D>
450 inline D DivideFourWordsByTwo(S *T,
const D &Al,
const D &Ah,
const D &B)
453 return D(Ah.GetLowHalf(), Ah.GetHighHalf());
457 T[0] = Al.GetLowHalf();
458 T[1] = Al.GetHighHalf();
459 T[2] = Ah.GetLowHalf();
460 T[3] = Ah.GetHighHalf();
461 Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(), B.GetHighHalf());
462 Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
463 return D(Q[0], Q[1]);
468 inline word DWord::operator/(word a)
470 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 471 return word(m_whole / a);
474 return DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a).GetWhole();
478 inline word DWord::operator%(word a)
480 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 481 return word(m_whole % a);
483 if (a < (word(1) << (WORD_BITS/2)))
486 word r = m_halfs.high % h;
487 r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
488 return hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h);
493 DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a);
494 return Word(r[0], r[1]).GetWhole();
502 #if defined(__GNUC__) 503 #define AddPrologue \ 505 __asm__ __volatile__ \ 508 #define AddEpilogue \ 509 ".att_syntax prefix;" \ 511 : "d" (C), "a" (A), "D" (B), "c" (N) \ 512 : "%esi", "memory", "cc" \ 515 #define MulPrologue \ 516 __asm__ __volatile__ \ 518 ".intel_syntax noprefix;" \ 521 #define MulEpilogue \ 523 ".att_syntax prefix;" \ 525 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \ 526 : "%esi", "memory", "cc" \ 528 #define SquPrologue MulPrologue 529 #define SquEpilogue \ 531 ".att_syntax prefix;" \ 533 : "d" (s_maskLow16), "c" (C), "a" (A) \ 534 : "%esi", "%edi", "memory", "cc" \ 536 #define TopPrologue MulPrologue 537 #define TopEpilogue \ 539 ".att_syntax prefix;" \ 541 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \ 545 #define AddPrologue \ 548 __asm mov eax, [esp+12] \ 549 __asm mov edi, [esp+16] 550 #define AddEpilogue \ 555 #define SaveEBX __asm push ebx 556 #define RestoreEBX __asm pop ebx 561 #define SquPrologue \ 565 AS2( lea ebx, s_maskLow16) 566 #define MulPrologue \ 571 AS2( lea ebx, s_maskLow16) 572 #define TopPrologue \ 578 AS2( lea ebx, s_maskLow16) 579 #define SquEpilogue RestoreEBX 580 #define MulEpilogue RestoreEBX 581 #define TopEpilogue RestoreEBX 584 #ifdef CRYPTOPP_X64_MASM_AVAILABLE 586 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B);
587 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B);
589 #elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE) 590 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
598 AS2( mov %0,[%3+8*%1])
599 AS2( add %0,[%4+8*%1])
600 AS2( mov [%2+8*%1],%0)
602 AS2( mov %0,[%3+8*%1+8])
603 AS2( adc %0,[%4+8*%1+8])
604 AS2( mov [%2+8*%1+8],%0)
607 AS2( mov %0,[%3+8*%1])
608 AS2( adc %0,[%4+8*%1])
609 AS2( mov [%2+8*%1],%0)
615 :
"=&r" (result),
"+c" (N)
616 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
622 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
630 AS2( mov %0,[%3+8*%1])
631 AS2( sub %0,[%4+8*%1])
632 AS2( mov [%2+8*%1],%0)
634 AS2( mov %0,[%3+8*%1+8])
635 AS2( sbb %0,[%4+8*%1+8])
636 AS2( mov [%2+8*%1+8],%0)
639 AS2( mov %0,[%3+8*%1])
640 AS2( sbb %0,[%4+8*%1])
641 AS2( mov [%2+8*%1],%0)
647 :
"=&r" (result),
"+c" (N)
648 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
653 #elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86 654 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
659 AS2( lea eax, [eax+4*ecx])
660 AS2( lea edi, [edi+4*ecx])
661 AS2( lea edx, [edx+4*ecx])
671 AS2( mov esi,[eax+4*ecx])
672 AS2( adc esi,[edi+4*ecx])
673 AS2( mov [edx+4*ecx],esi)
674 AS2( mov esi,[eax+4*ecx+4])
675 AS2( adc esi,[edi+4*ecx+4])
676 AS2( mov [edx+4*ecx+4],esi)
678 AS2( mov esi,[eax+4*ecx+8])
679 AS2( adc esi,[edi+4*ecx+8])
680 AS2( mov [edx+4*ecx+8],esi)
681 AS2( mov esi,[eax+4*ecx+12])
682 AS2( adc esi,[edi+4*ecx+12])
683 AS2( mov [edx+4*ecx+12],esi)
685 AS2( lea ecx,[ecx+4])
695 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
700 AS2( lea eax, [eax+4*ecx])
701 AS2( lea edi, [edi+4*ecx])
702 AS2( lea edx, [edx+4*ecx])
712 AS2( mov esi,[eax+4*ecx])
713 AS2( sbb esi,[edi+4*ecx])
714 AS2( mov [edx+4*ecx],esi)
715 AS2( mov esi,[eax+4*ecx+4])
716 AS2( sbb esi,[edi+4*ecx+4])
717 AS2( mov [edx+4*ecx+4],esi)
719 AS2( mov esi,[eax+4*ecx+8])
720 AS2( sbb esi,[edi+4*ecx+8])
721 AS2( mov [edx+4*ecx+8],esi)
722 AS2( mov esi,[eax+4*ecx+12])
723 AS2( sbb esi,[edi+4*ecx+12])
724 AS2( mov [edx+4*ecx+12],esi)
726 AS2( lea ecx,[ecx+4])
736 #if CRYPTOPP_INTEGER_SSE2 737 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Add(
size_t N, word *C,
const word *A,
const word *B)
742 AS2( lea eax, [eax+4*ecx])
743 AS2( lea edi, [edi+4*ecx])
744 AS2( lea edx, [edx+4*ecx])
755 AS2( movd mm0, DWORD PTR [eax+4*ecx])
756 AS2( movd mm1, DWORD PTR [edi+4*ecx])
759 AS2( movd DWORD PTR [edx+4*ecx], mm2)
762 AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
763 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
766 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
770 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
771 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
774 AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
777 AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
778 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
781 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
793 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Sub(
size_t N, word *C,
const word *A,
const word *B)
798 AS2( lea eax, [eax+4*ecx])
799 AS2( lea edi, [edi+4*ecx])
800 AS2( lea edx, [edx+4*ecx])
811 AS2( movd mm0, DWORD PTR [eax+4*ecx])
812 AS2( movd mm1, DWORD PTR [edi+4*ecx])
815 AS2( movd DWORD PTR [edx+4*ecx], mm0)
818 AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
819 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
822 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
826 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
827 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
830 AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
833 AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
834 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
837 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
849 #endif // #if CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE 851 int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
857 for (
size_t i=0; i<N; i+=2)
859 AddWithCarry(u, A[i], B[i]);
861 AddWithCarry(u, A[i+1], B[i+1]);
864 return int(GetCarry(u));
867 int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
873 for (
size_t i=0; i<N; i+=2)
875 SubtractWithBorrow(u, A[i], B[i]);
877 SubtractWithBorrow(u, A[i+1], B[i+1]);
880 return int(GetBorrow(u));
884 static word LinearMultiply(word *C,
const word *A, word B,
size_t N)
887 for(
unsigned i=0; i<N; i++)
890 MultiplyWords(p, A[i], B);
891 Acc2WordsBy1(p, carry);
898 #ifndef CRYPTOPP_DOXYGEN_PROCESSING 902 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 907 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 908 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 909 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 910 Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \ 911 Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \ 916 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 917 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 918 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 919 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 920 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) \ 921 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) \ 922 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) \ 923 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) \ 924 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) \ 925 Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \ 926 Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \ 927 Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \ 928 Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \ 933 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 934 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 935 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 936 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 937 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) \ 938 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) \ 939 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) \ 940 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) \ 941 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) \ 942 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) \ 943 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) \ 944 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) \ 945 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) \ 946 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) \ 947 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) \ 948 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) \ 949 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) \ 950 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) \ 951 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) \ 952 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) \ 953 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) \ 954 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) \ 955 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) \ 956 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) \ 957 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) \ 958 Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \ 959 Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \ 960 Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \ 961 Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \ 970 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 971 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 972 Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \ 973 Squ_SaveAcc(4, 2, 3) Squ_NonDiag \ 978 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 979 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 980 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \ 981 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \ 982 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \ 983 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \ 984 Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \ 985 Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \ 986 Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \ 987 Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \ 988 Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \ 989 Squ_SaveAcc(12, 6, 7) Squ_NonDiag \ 994 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 995 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 996 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \ 997 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \ 998 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \ 999 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \ 1000 Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \ 1001 Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \ 1002 Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \ 1003 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 \ 1004 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) \ 1005 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 \ 1006 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) \ 1007 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 \ 1008 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) \ 1009 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 \ 1010 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) \ 1011 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 \ 1012 Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \ 1013 Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \ 1014 Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \ 1015 Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \ 1016 Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \ 1017 Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \ 1018 Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \ 1019 Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \ 1020 Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \ 1021 Squ_SaveAcc(28, 14, 15) Squ_NonDiag \ 1026 Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \ 1031 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1032 Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \ 1033 Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \ 1038 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1039 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 1040 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 1041 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 1042 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) \ 1043 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) \ 1044 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) \ 1049 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1050 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 1051 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 1052 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 1053 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) \ 1054 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) \ 1055 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) \ 1056 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) \ 1057 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) \ 1058 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) \ 1059 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) \ 1060 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) \ 1061 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) \ 1062 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) \ 1063 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) \ 1069 #define Mul_Begin(n) \ 1073 MultiplyWords(p, A[0], B[0]) \ 1074 AssignWord(c, LowWord(p)) \ 1075 AssignWord(d, HighWord(p)) 1077 #define Mul_Acc(i, j) \ 1078 MultiplyWords(p, A[i], B[j]) \ 1079 Acc2WordsBy1(c, LowWord(p)) \ 1080 Acc2WordsBy1(d, HighWord(p)) 1082 #define Mul_SaveAcc(k, i, j) \ 1083 R[k] = LowWord(c); \ 1084 Add2WordsBy1(c, d, HighWord(c)) \ 1085 MultiplyWords(p, A[i], B[j]) \ 1086 AssignWord(d, HighWord(p)) \ 1087 Acc2WordsBy1(c, LowWord(p)) 1089 #define Mul_End(n) \ 1090 R[2*n-3] = LowWord(c); \ 1091 Acc2WordsBy1(d, HighWord(c)) \ 1092 MultiplyWords(p, A[n-1], B[n-1])\ 1093 Acc2WordsBy2(d, p) \ 1094 R[2*n-2] = LowWord(d); \ 1095 R[2*n-1] = HighWord(d); 1097 #define Bot_SaveAcc(k, i, j) \ 1098 R[k] = LowWord(c); \ 1099 word e = LowWord(d) + HighWord(c); \ 1102 #define Bot_Acc(i, j) \ 1105 #define Bot_End(n) \ 1108 #define Mul_Begin(n) \ 1112 MultiplyWords(p, A[0], B[0]) \ 1114 AssignWord(d, HighWord(p)) 1116 #define Mul_Acc(i, j) \ 1117 MulAcc(c, d, A[i], B[j]) 1119 #define Mul_SaveAcc(k, i, j) \ 1122 AssignWord(d, HighWord(d)) \ 1123 MulAcc(c, d, A[i], B[j]) 1125 #define Mul_End(k, i) \ 1127 MultiplyWords(p, A[i], B[i]) \ 1128 Acc2WordsBy2(p, d) \ 1129 R[k+1] = LowWord(p); \ 1130 R[k+2] = HighWord(p); 1132 #define Bot_SaveAcc(k, i, j) \ 1137 #define Bot_Acc(i, j) \ 1140 #define Bot_End(n) \ 1144 #define Squ_Begin(n) \ 1149 MultiplyWords(p, A[0], A[0]) \ 1150 R[0] = LowWord(p); \ 1151 AssignWord(e, HighWord(p)) \ 1152 MultiplyWords(p, A[0], A[1]) \ 1154 AssignWord(d, HighWord(p)) \ 1157 #define Squ_NonDiag \ 1160 #define Squ_SaveAcc(k, i, j) \ 1161 Acc3WordsBy2(c, d, e) \ 1163 MultiplyWords(p, A[i], A[j]) \ 1165 AssignWord(d, HighWord(p)) \ 1167 #define Squ_Acc(i, j) \ 1168 MulAcc(c, d, A[i], A[j]) 1170 #define Squ_Diag(i) \ 1172 MulAcc(c, d, A[i], A[i]) 1174 #define Squ_End(n) \ 1175 Acc3WordsBy2(c, d, e) \ 1177 MultiplyWords(p, A[n-1], A[n-1])\ 1178 Acc2WordsBy2(p, e) \ 1179 R[2*n-2] = LowWord(p); \ 1180 R[2*n-1] = HighWord(p); 1183 void Baseline_Multiply2(word *R,
const word *A,
const word *B)
1188 void Baseline_Multiply4(word *R,
const word *A,
const word *B)
1193 void Baseline_Multiply8(word *R,
const word *A,
const word *B)
1198 void Baseline_Square2(word *R,
const word *A)
1203 void Baseline_Square4(word *R,
const word *A)
1208 void Baseline_Square8(word *R,
const word *A)
1213 void Baseline_MultiplyBottom2(word *R,
const word *A,
const word *B)
1218 void Baseline_MultiplyBottom4(word *R,
const word *A,
const word *B)
1223 void Baseline_MultiplyBottom8(word *R,
const word *A,
const word *B)
1228 #define Top_Begin(n) \ 1232 MultiplyWords(p, A[0], B[n-2]);\ 1233 AssignWord(d, HighWord(p)); 1235 #define Top_Acc(i, j) \ 1236 MultiplyWords(p, A[i], B[j]);\ 1237 Acc2WordsBy1(d, HighWord(p)); 1239 #define Top_SaveAcc0(i, j) \ 1241 AssignWord(d, HighWord(d)) \ 1242 MulAcc(c, d, A[i], B[j]) 1244 #define Top_SaveAcc1(i, j) \ 1246 Acc2WordsBy1(d, c); \ 1248 AssignWord(d, HighWord(d)) \ 1249 MulAcc(c, d, A[i], B[j]) 1251 void Baseline_MultiplyTop2(word *R,
const word *A,
const word *B, word L)
1255 Baseline_Multiply2(T, A, B);
1260 void Baseline_MultiplyTop4(word *R,
const word *A,
const word *B, word L)
1263 Top_Acc(1, 1) Top_Acc(2, 0) \
1264 Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1265 Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1266 Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1270 void Baseline_MultiplyTop8(word *R,
const word *A,
const word *B, word L)
1273 Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1274 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) \
1275 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) \
1276 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) \
1277 Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1278 Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1279 Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1280 Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1284 #if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available 1285 void Baseline_Multiply16(word *R,
const word *A,
const word *B)
1290 void Baseline_Square16(word *R,
const word *A)
1295 void Baseline_MultiplyBottom16(word *R,
const word *A,
const word *B)
1300 void Baseline_MultiplyTop16(word *R,
const word *A,
const word *B, word L)
1303 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) \
1304 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) \
1305 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) \
1306 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) \
1307 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) \
1308 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) \
1309 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) \
1310 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) \
1311 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) \
1312 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) \
1313 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) \
1314 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) \
1315 Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1316 Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1317 Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1318 Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1325 #if CRYPTOPP_INTEGER_SSE2 1327 CRYPTOPP_ALIGN_DATA(16)
static const word32 s_maskLow16[4] CRYPTOPP_SECTION_ALIGN16 = {0xffff,0xffff,0xffff,0xffff};
1345 #define SSE2_FinalSave(k) \ 1346 AS2( psllq xmm5, 16) \ 1347 AS2( paddq xmm4, xmm5) \ 1348 AS2( movq QWORD PTR [ecx+8*(k)], xmm4) 1350 #define SSE2_SaveShift(k) \ 1351 AS2( movq xmm0, xmm6) \ 1352 AS2( punpckhqdq xmm6, xmm0) \ 1353 AS2( movq xmm1, xmm7) \ 1354 AS2( punpckhqdq xmm7, xmm1) \ 1355 AS2( paddd xmm6, xmm0) \ 1356 AS2( pslldq xmm6, 4) \ 1357 AS2( paddd xmm7, xmm1) \ 1358 AS2( paddd xmm4, xmm6) \ 1359 AS2( pslldq xmm7, 4) \ 1360 AS2( movq xmm6, xmm4) \ 1361 AS2( paddd xmm5, xmm7) \ 1362 AS2( movq xmm7, xmm5) \ 1363 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \ 1364 AS2( psrlq xmm6, 16) \ 1365 AS2( paddq xmm6, xmm7) \ 1366 AS2( punpckhqdq xmm4, xmm0) \ 1367 AS2( punpckhqdq xmm5, xmm0) \ 1368 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \ 1369 AS2( psrlq xmm6, 3*16) \ 1370 AS2( paddd xmm4, xmm6) \ 1372 #define Squ_SSE2_SaveShift(k) \ 1373 AS2( movq xmm0, xmm6) \ 1374 AS2( punpckhqdq xmm6, xmm0) \ 1375 AS2( movq xmm1, xmm7) \ 1376 AS2( punpckhqdq xmm7, xmm1) \ 1377 AS2( paddd xmm6, xmm0) \ 1378 AS2( pslldq xmm6, 4) \ 1379 AS2( paddd xmm7, xmm1) \ 1380 AS2( paddd xmm4, xmm6) \ 1381 AS2( pslldq xmm7, 4) \ 1382 AS2( movhlps xmm6, xmm4) \ 1383 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \ 1384 AS2( paddd xmm5, xmm7) \ 1385 AS2( movhps QWORD PTR [esp+12], xmm5)\ 1386 AS2( psrlq xmm4, 16) \ 1387 AS2( paddq xmm4, xmm5) \ 1388 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \ 1389 AS2( psrlq xmm4, 3*16) \ 1390 AS2( paddd xmm4, xmm6) \ 1391 AS2( movq QWORD PTR [esp+4], xmm4)\ 1393 #define SSE2_FirstMultiply(i) \ 1394 AS2( movdqa xmm7, [esi+(i)*16])\ 1395 AS2( movdqa xmm5, [edi-(i)*16])\ 1396 AS2( pmuludq xmm5, xmm7) \ 1397 AS2( movdqa xmm4, [ebx])\ 1398 AS2( movdqa xmm6, xmm4) \ 1399 AS2( pand xmm4, xmm5) \ 1400 AS2( psrld xmm5, 16) \ 1401 AS2( pmuludq xmm7, [edx-(i)*16])\ 1402 AS2( pand xmm6, xmm7) \ 1403 AS2( psrld xmm7, 16) 1405 #define Squ_Begin(n) \ 1408 AS2( and esp, 0xfffffff0)\ 1409 AS2( lea edi, [esp-32*n])\ 1410 AS2( sub esp, 32*n+16)\ 1412 AS2( mov esi, edi) \ 1413 AS2( xor edx, edx) \ 1415 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1416 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1417 AS2( movdqa [edi+2*edx], xmm0) \ 1418 AS2( psrlq xmm0, 32) \ 1419 AS2( movdqa [edi+2*edx+16], xmm0) \ 1420 AS2( movdqa [edi+16*n+2*edx], xmm1) \ 1421 AS2( psrlq xmm1, 32) \ 1422 AS2( movdqa [edi+16*n+2*edx+16], xmm1) \ 1424 AS2( cmp edx, 8*(n)) \ 1426 AS2( lea edx, [edi+16*n])\ 1427 SSE2_FirstMultiply(0) \ 1429 #define Squ_Acc(i) \ 1431 AS2( movdqa xmm1, [esi+(i)*16]) \ 1432 AS2( movdqa xmm0, [edi-(i)*16]) \ 1433 AS2( movdqa xmm2, [ebx]) \ 1434 AS2( pmuludq xmm0, xmm1) \ 1435 AS2( pmuludq xmm1, [edx-(i)*16]) \ 1436 AS2( movdqa xmm3, xmm2) \ 1437 AS2( pand xmm2, xmm0) \ 1438 AS2( psrld xmm0, 16) \ 1439 AS2( paddd xmm4, xmm2) \ 1440 AS2( paddd xmm5, xmm0) \ 1441 AS2( pand xmm3, xmm1) \ 1442 AS2( psrld xmm1, 16) \ 1443 AS2( paddd xmm6, xmm3) \ 1444 AS2( paddd xmm7, xmm1) \ 1447 #define Squ_Acc2(i) ASC(call, LSqu##i) 1448 #define Squ_Acc3(i) Squ_Acc2(i) 1449 #define Squ_Acc4(i) Squ_Acc2(i) 1450 #define Squ_Acc5(i) Squ_Acc2(i) 1451 #define Squ_Acc6(i) Squ_Acc2(i) 1452 #define Squ_Acc7(i) Squ_Acc2(i) 1453 #define Squ_Acc8(i) Squ_Acc2(i) 1455 #define SSE2_End(E, n) \ 1456 SSE2_SaveShift(2*(n)-3) \ 1457 AS2( movdqa xmm7, [esi+16]) \ 1458 AS2( movdqa xmm0, [edi]) \ 1459 AS2( pmuludq xmm0, xmm7) \ 1460 AS2( movdqa xmm2, [ebx]) \ 1461 AS2( pmuludq xmm7, [edx]) \ 1462 AS2( movdqa xmm6, xmm2) \ 1463 AS2( pand xmm2, xmm0) \ 1464 AS2( psrld xmm0, 16) \ 1465 AS2( paddd xmm4, xmm2) \ 1466 AS2( paddd xmm5, xmm0) \ 1467 AS2( pand xmm6, xmm7) \ 1468 AS2( psrld xmm7, 16) \ 1469 SSE2_SaveShift(2*(n)-2) \ 1470 SSE2_FinalSave(2*(n)-1) \ 1474 #define Squ_End(n) SSE2_End(SquEpilogue, n) 1475 #define Mul_End(n) SSE2_End(MulEpilogue, n) 1476 #define Top_End(n) SSE2_End(TopEpilogue, n) 1478 #define Squ_Column1(k, i) \ 1479 Squ_SSE2_SaveShift(k) \ 1481 SSE2_FirstMultiply(1)\ 1483 AS2( paddd xmm4, xmm4) \ 1484 AS2( paddd xmm5, xmm5) \ 1485 AS2( movdqa xmm3, [esi]) \ 1486 AS2( movq xmm1, QWORD PTR [esi+8]) \ 1487 AS2( pmuludq xmm1, xmm3) \ 1488 AS2( pmuludq xmm3, xmm3) \ 1489 AS2( movdqa xmm0, [ebx])\ 1490 AS2( movdqa xmm2, xmm0) \ 1491 AS2( pand xmm0, xmm1) \ 1492 AS2( psrld xmm1, 16) \ 1493 AS2( paddd xmm6, xmm0) \ 1494 AS2( paddd xmm7, xmm1) \ 1495 AS2( pand xmm2, xmm3) \ 1496 AS2( psrld xmm3, 16) \ 1497 AS2( paddd xmm6, xmm6) \ 1498 AS2( paddd xmm7, xmm7) \ 1499 AS2( paddd xmm4, xmm2) \ 1500 AS2( paddd xmm5, xmm3) \ 1501 AS2( movq xmm0, QWORD PTR [esp+4])\ 1502 AS2( movq xmm1, QWORD PTR [esp+12])\ 1503 AS2( paddd xmm4, xmm0)\ 1504 AS2( paddd xmm5, xmm1)\ 1506 #define Squ_Column0(k, i) \ 1507 Squ_SSE2_SaveShift(k) \ 1510 SSE2_FirstMultiply(1)\ 1512 AS2( paddd xmm6, xmm6) \ 1513 AS2( paddd xmm7, xmm7) \ 1514 AS2( paddd xmm4, xmm4) \ 1515 AS2( paddd xmm5, xmm5) \ 1516 AS2( movq xmm0, QWORD PTR [esp+4])\ 1517 AS2( movq xmm1, QWORD PTR [esp+12])\ 1518 AS2( paddd xmm4, xmm0)\ 1519 AS2( paddd xmm5, xmm1)\ 1521 #define SSE2_MulAdd45 \ 1522 AS2( movdqa xmm7, [esi]) \ 1523 AS2( movdqa xmm0, [edi]) \ 1524 AS2( pmuludq xmm0, xmm7) \ 1525 AS2( movdqa xmm2, [ebx]) \ 1526 AS2( pmuludq xmm7, [edx]) \ 1527 AS2( movdqa xmm6, xmm2) \ 1528 AS2( pand xmm2, xmm0) \ 1529 AS2( psrld xmm0, 16) \ 1530 AS2( paddd xmm4, xmm2) \ 1531 AS2( paddd xmm5, xmm0) \ 1532 AS2( pand xmm6, xmm7) \ 1533 AS2( psrld xmm7, 16) 1535 #define Mul_Begin(n) \ 1538 AS2( and esp, 0xfffffff0)\ 1539 AS2( sub esp, 48*n+16)\ 1541 AS2( xor edx, edx) \ 1543 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1544 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1545 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \ 1546 AS2( movdqa [esp+20+2*edx], xmm0) \ 1547 AS2( psrlq xmm0, 32) \ 1548 AS2( movdqa [esp+20+2*edx+16], xmm0) \ 1549 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \ 1550 AS2( psrlq xmm1, 32) \ 1551 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \ 1552 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \ 1553 AS2( psrlq xmm2, 32) \ 1554 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \ 1556 AS2( cmp edx, 8*(n)) \ 1558 AS2( lea edi, [esp+20])\ 1559 AS2( lea edx, [esp+20+16*n])\ 1560 AS2( lea esi, [esp+20+32*n])\ 1561 SSE2_FirstMultiply(0) \ 1563 #define Mul_Acc(i) \ 1565 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \ 1566 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \ 1567 AS2( movdqa xmm2, [ebx]) \ 1568 AS2( pmuludq xmm0, xmm1) \ 1569 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1570 AS2( movdqa xmm3, xmm2) \ 1571 AS2( pand xmm2, xmm0) \ 1572 AS2( psrld xmm0, 16) \ 1573 AS2( paddd xmm4, xmm2) \ 1574 AS2( paddd xmm5, xmm0) \ 1575 AS2( pand xmm3, xmm1) \ 1576 AS2( psrld xmm1, 16) \ 1577 AS2( paddd xmm6, xmm3) \ 1578 AS2( paddd xmm7, xmm1) \ 1581 #define Mul_Acc2(i) ASC(call, LMul##i) 1582 #define Mul_Acc3(i) Mul_Acc2(i) 1583 #define Mul_Acc4(i) Mul_Acc2(i) 1584 #define Mul_Acc5(i) Mul_Acc2(i) 1585 #define Mul_Acc6(i) Mul_Acc2(i) 1586 #define Mul_Acc7(i) Mul_Acc2(i) 1587 #define Mul_Acc8(i) Mul_Acc2(i) 1588 #define Mul_Acc9(i) Mul_Acc2(i) 1589 #define Mul_Acc10(i) Mul_Acc2(i) 1590 #define Mul_Acc11(i) Mul_Acc2(i) 1591 #define Mul_Acc12(i) Mul_Acc2(i) 1592 #define Mul_Acc13(i) Mul_Acc2(i) 1593 #define Mul_Acc14(i) Mul_Acc2(i) 1594 #define Mul_Acc15(i) Mul_Acc2(i) 1595 #define Mul_Acc16(i) Mul_Acc2(i) 1597 #define Mul_Column1(k, i) \ 1603 #define Mul_Column0(k, i) \ 1610 #define Bot_Acc(i) \ 1611 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \ 1612 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \ 1613 AS2( pmuludq xmm0, xmm1) \ 1614 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1615 AS2( paddq xmm4, xmm0) \ 1616 AS2( paddd xmm6, xmm1) 1618 #define Bot_SaveAcc(k) \ 1622 AS2( movdqa xmm6, [esi]) \ 1623 AS2( movdqa xmm0, [edi]) \ 1624 AS2( pmuludq xmm0, xmm6) \ 1625 AS2( paddq xmm4, xmm0) \ 1626 AS2( psllq xmm5, 16) \ 1627 AS2( paddq xmm4, xmm5) \ 1628 AS2( pmuludq xmm6, [edx]) 1630 #define Bot_End(n) \ 1631 AS2( movhlps xmm7, xmm6) \ 1632 AS2( paddd xmm6, xmm7) \ 1633 AS2( psllq xmm6, 32) \ 1634 AS2( paddd xmm4, xmm6) \ 1635 AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \ 1639 #define Top_Begin(n) \ 1642 AS2( and esp, 0xfffffff0)\ 1643 AS2( sub esp, 48*n+16)\ 1645 AS2( xor edx, edx) \ 1647 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1648 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1649 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \ 1650 AS2( movdqa [esp+20+2*edx], xmm0) \ 1651 AS2( psrlq xmm0, 32) \ 1652 AS2( movdqa [esp+20+2*edx+16], xmm0) \ 1653 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \ 1654 AS2( psrlq xmm1, 32) \ 1655 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \ 1656 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \ 1657 AS2( psrlq xmm2, 32) \ 1658 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \ 1660 AS2( cmp edx, 8*(n)) \ 1662 AS2( mov eax, esi) \ 1663 AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\ 1664 AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\ 1665 AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\ 1666 AS2( pxor xmm4, xmm4)\ 1667 AS2( pxor xmm5, xmm5) 1669 #define Top_Acc(i) \ 1670 AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \ 1671 AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1672 AS2( psrlq xmm0, 48) \ 1673 AS2( paddd xmm5, xmm0)\ 1675 #define Top_Column0(i) \ 1676 AS2( psllq xmm5, 32) \ 1682 #define Top_Column1(i) \ 1688 AS2( movd xmm0, eax)\ 1689 AS2( movd xmm1, [ecx+4])\ 1690 AS2( psrld xmm1, 16)\ 1691 AS2( pcmpgtd xmm1, xmm0)\ 1692 AS2( psrld xmm1, 31)\ 1693 AS2( paddd xmm4, xmm1)\ 1695 void SSE2_Square4(word *C,
const word *A)
1702 void SSE2_Square8(word *C,
const word *A)
1718 void SSE2_Square16(word *C,
const word *A)
1723 Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1742 void SSE2_Square32(word *C,
const word *A)
1746 Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1780 void SSE2_Multiply4(word *C,
const word *A,
const word *B)
1792 void SSE2_Multiply8(word *C,
const word *A,
const word *B)
1797 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1808 void SSE2_Multiply16(word *C,
const word *A,
const word *B)
1813 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1832 void SSE2_Multiply32(word *C,
const word *A,
const word *B)
1836 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)
1870 void SSE2_MultiplyBottom4(word *C,
const word *A,
const word *B)
1873 Bot_SaveAcc(0) Bot_Acc(2)
1877 void SSE2_MultiplyBottom8(word *C,
const word *A,
const word *B)
1882 Mul_Acc(3) Mul_Acc(2)
1887 Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1891 void SSE2_MultiplyBottom16(word *C,
const word *A,
const word *B)
1896 Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1905 Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1909 void SSE2_MultiplyBottom32(word *C,
const word *A,
const word *B)
1914 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)
1931 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)
1935 void SSE2_MultiplyTop8(word *C,
const word *A,
const word *B, word L)
1938 Top_Acc(3) Top_Acc(2) Top_Acc(1)
1941 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1950 void SSE2_MultiplyTop16(word *C,
const word *A,
const word *B, word L)
1953 Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1956 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1969 void SSE2_MultiplyTop32(word *C,
const word *A,
const word *B, word L)
1972 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)
1975 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)
1996 #endif // #if CRYPTOPP_INTEGER_SSE2 2000 typedef int (CRYPTOPP_FASTCALL * PAdd)(
size_t N, word *C,
const word *A,
const word *B);
2001 typedef void (* PMul)(word *C,
const word *A,
const word *B);
2002 typedef void (* PSqu)(word *C,
const word *A);
2003 typedef void (* PMulTop)(word *C,
const word *A,
const word *B, word L);
2005 #if CRYPTOPP_INTEGER_SSE2 2006 static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
2007 static size_t s_recursionLimit = 8;
2009 static const size_t s_recursionLimit = 16;
2012 static PMul s_pMul[9], s_pBot[9];
2013 static PSqu s_pSqu[9];
2014 static PMulTop s_pTop[9];
2016 static void SetFunctionPointers()
2018 s_pMul[0] = &Baseline_Multiply2;
2019 s_pBot[0] = &Baseline_MultiplyBottom2;
2020 s_pSqu[0] = &Baseline_Square2;
2021 s_pTop[0] = &Baseline_MultiplyTop2;
2022 s_pTop[1] = &Baseline_MultiplyTop4;
2024 #if CRYPTOPP_INTEGER_SSE2 2027 #if _MSC_VER != 1200 || defined(NDEBUG) 2035 s_recursionLimit = 32;
2037 s_pMul[1] = &SSE2_Multiply4;
2038 s_pMul[2] = &SSE2_Multiply8;
2039 s_pMul[4] = &SSE2_Multiply16;
2040 s_pMul[8] = &SSE2_Multiply32;
2042 s_pBot[1] = &SSE2_MultiplyBottom4;
2043 s_pBot[2] = &SSE2_MultiplyBottom8;
2044 s_pBot[4] = &SSE2_MultiplyBottom16;
2045 s_pBot[8] = &SSE2_MultiplyBottom32;
2047 s_pSqu[1] = &SSE2_Square4;
2048 s_pSqu[2] = &SSE2_Square8;
2049 s_pSqu[4] = &SSE2_Square16;
2050 s_pSqu[8] = &SSE2_Square32;
2052 s_pTop[2] = &SSE2_MultiplyTop8;
2053 s_pTop[4] = &SSE2_MultiplyTop16;
2054 s_pTop[8] = &SSE2_MultiplyTop32;
2059 s_pMul[1] = &Baseline_Multiply4;
2060 s_pMul[2] = &Baseline_Multiply8;
2062 s_pBot[1] = &Baseline_MultiplyBottom4;
2063 s_pBot[2] = &Baseline_MultiplyBottom8;
2065 s_pSqu[1] = &Baseline_Square4;
2066 s_pSqu[2] = &Baseline_Square8;
2068 s_pTop[2] = &Baseline_MultiplyTop8;
2070 #if !CRYPTOPP_INTEGER_SSE2 2071 s_pMul[4] = &Baseline_Multiply16;
2072 s_pBot[4] = &Baseline_MultiplyBottom16;
2073 s_pSqu[4] = &Baseline_Square16;
2074 s_pTop[4] = &Baseline_MultiplyTop16;
2079 inline int Add(word *C,
const word *A,
const word *B,
size_t N)
2081 #if CRYPTOPP_INTEGER_SSE2 2082 return s_pAdd(N, C, A, B);
2084 return Baseline_Add(N, C, A, B);
2088 inline int Subtract(word *C,
const word *A,
const word *B,
size_t N)
2090 #if CRYPTOPP_INTEGER_SSE2 2091 return s_pSub(N, C, A, B);
2093 return Baseline_Sub(N, C, A, B);
2120 void RecursiveMultiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2122 assert(N>=2 && N%2==0);
2124 if (N <= s_recursionLimit)
2125 s_pMul[N/4](R, A, B);
2128 const size_t N2 = N/2;
2130 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2131 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2133 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2134 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2136 RecursiveMultiply(R2, T2, A1, B1, N2);
2137 RecursiveMultiply(T0, T2, R0, R1, N2);
2138 RecursiveMultiply(R0, T2, A0, B0, N2);
2142 int c2 = Add(R2, R2, R1, N2);
2144 c2 += Add(R1, R2, R0, N2);
2145 c3 += Add(R2, R2, R3, N2);
2148 c3 -= Subtract(R1, R1, T0, N);
2150 c3 += Add(R1, R1, T0, N);
2152 c3 += Increment(R2, N2, c2);
2153 assert (c3 >= 0 && c3 <= 2);
2154 Increment(R3, N2, c3);
2162 void RecursiveSquare(word *R, word *T,
const word *A,
size_t N)
2164 assert(N && N%2==0);
2166 if (N <= s_recursionLimit)
2170 const size_t N2 = N/2;
2172 RecursiveSquare(R0, T2, A0, N2);
2173 RecursiveSquare(R2, T2, A1, N2);
2174 RecursiveMultiply(T0, T2, A0, A1, N2);
2176 int carry = Add(R1, R1, T0, N);
2177 carry += Add(R1, R1, T0, N);
2178 Increment(R3, N2, carry);
2187 void RecursiveMultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2189 assert(N>=2 && N%2==0);
2191 if (N <= s_recursionLimit)
2192 s_pBot[N/4](R, A, B);
2195 const size_t N2 = N/2;
2197 RecursiveMultiply(R, T, A0, B0, N2);
2198 RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2199 Add(R1, R1, T0, N2);
2200 RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2201 Add(R1, R1, T0, N2);
2211 void MultiplyTop(word *R, word *T,
const word *L,
const word *A,
const word *B,
size_t N)
2213 assert(N>=2 && N%2==0);
2215 if (N <= s_recursionLimit)
2216 s_pTop[N/4](R, A, B, L[N-1]);
2219 const size_t N2 = N/2;
2221 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2222 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2224 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2225 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2227 RecursiveMultiply(T0, T2, R0, R1, N2);
2228 RecursiveMultiply(R0, T2, A1, B1, N2);
2233 int c2 = Subtract(T2, L+N2, L, N2);
2237 c2 -= Add(T2, T2, T0, N2);
2238 t = (Compare(T2, R0, N2) == -1);
2239 c3 = t - Subtract(T2, T2, T1, N2);
2243 c2 += Subtract(T2, T2, T0, N2);
2244 t = (Compare(T2, R0, N2) == -1);
2245 c3 = t + Add(T2, T2, T1, N2);
2250 c3 += Increment(T2, N2, c2);
2252 c3 -= Decrement(T2, N2, -c2);
2253 c3 += Add(R0, T2, R1, N2);
2255 assert (c3 >= 0 && c3 <= 2);
2256 Increment(R1, N2, c3);
2260 inline void Multiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2262 RecursiveMultiply(R, T, A, B, N);
2265 inline void Square(word *R, word *T,
const word *A,
size_t N)
2267 RecursiveSquare(R, T, A, N);
2270 inline void MultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2272 RecursiveMultiplyBottom(R, T, A, B, N);
2280 void AsymmetricMultiply(word *R, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2287 Multiply(R, T, A, B, NA);
2298 assert(NB % NA == 0);
2305 SetWords(R, 0, NB+2);
2308 CopyWords(R, B, NB);
2309 R[NB] = R[NB+1] = 0;
2312 R[NB] = LinearMultiply(R, B, A[0], NB);
2321 Multiply(R, T, A, B, NA);
2322 CopyWords(T+2*NA, R+NA, NA);
2324 for (i=2*NA; i<NB; i+=2*NA)
2325 Multiply(T+NA+i, T, A, B+i, NA);
2326 for (i=NA; i<NB; i+=2*NA)
2327 Multiply(R+i, T, A, B+i, NA);
2331 for (i=0; i<NB; i+=2*NA)
2332 Multiply(R+i, T, A, B+i, NA);
2333 for (i=NA; i<NB; i+=2*NA)
2334 Multiply(T+NA+i, T, A, B+i, NA);
2337 if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2338 Increment(R+NB, NA);
2345 void RecursiveInverseModPower2(word *R, word *T,
const word *A,
size_t N)
2349 T[0] = AtomicInverseModPower2(A[0]);
2351 s_pBot[0](T+2, T, A);
2352 TwosComplement(T+2, 2);
2353 Increment(T+2, 2, 2);
2354 s_pBot[0](R, T, T+2);
2358 const size_t N2 = N/2;
2359 RecursiveInverseModPower2(R0, T0, A0, N2);
2361 SetWords(T0+1, 0, N2-1);
2362 MultiplyTop(R1, T1, T0, R0, A0, N2);
2363 MultiplyBottom(T0, T1, R0, A1, N2);
2364 Add(T0, R1, T0, N2);
2365 TwosComplement(T0, N2);
2366 MultiplyBottom(R1, T1, R0, T0, N2);
2376 void MontgomeryReduce(word *R, word *T, word *X,
const word *M,
const word *U,
size_t N)
2379 MultiplyBottom(R, T, X, U, N);
2380 MultiplyTop(T, T+N, X, R, M, N);
2381 word borrow = Subtract(T, X+N, T, N);
2383 word carry = Add(T+N, T, M, N);
2384 assert(carry | !borrow);
2385 CRYPTOPP_UNUSED(carry), CRYPTOPP_UNUSED(borrow);
2386 CopyWords(R, T + ((0-borrow) & N), N);
2388 const word u = 0-U[0];
2390 for (
size_t i=0; i<N; i++)
2392 const word t = u * X[i];
2394 for (
size_t j=0; j<N; j+=2)
2396 MultiplyWords(p, t, M[j]);
2397 Acc2WordsBy1(p, X[i+j]);
2399 X[i+j] = LowWord(p);
2401 MultiplyWords(p, t, M[j+1]);
2402 Acc2WordsBy1(p, X[i+j+1]);
2404 X[i+j+1] = LowWord(p);
2408 if (Increment(X+N+i, N-i, c))
2409 while (!Subtract(X+N, X+N, M, N)) {}
2412 memcpy(R, X+N, N*WORD_SIZE);
2414 __m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2415 for (
size_t i=0; i<N; i++)
2417 __m64 t = _mm_cvtsi32_si64(X[i]);
2418 t = _mm_mul_su32(t, u);
2419 __m64 c = _mm_setzero_si64();
2420 for (
size_t j=0; j<N; j+=2)
2422 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2423 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2424 c = _mm_add_si64(c, p);
2425 X[i+j] = _mm_cvtsi64_si32(c);
2426 c = _mm_srli_si64(c, 32);
2427 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2428 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2429 c = _mm_add_si64(c, p);
2430 X[i+j+1] = _mm_cvtsi64_si32(c);
2431 c = _mm_srli_si64(c, 32);
2434 if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2435 while (!Subtract(X+N, X+N, M, N)) {}
2438 memcpy(R, X+N, N*WORD_SIZE);
2450 void HalfMontgomeryReduce(word *R, word *T,
const word *X,
const word *M,
const word *U,
const word *V,
size_t N)
2452 assert(N%2==0 && N>=4);
2464 const size_t N2 = N/2;
2465 Multiply(T0, T2, V0, X3, N2);
2466 int c2 = Add(T0, T0, X0, N);
2467 MultiplyBottom(T3, T2, T0, U, N2);
2468 MultiplyTop(T2, R, T0, T3, M0, N2);
2469 c2 -= Subtract(T2, T1, T2, N2);
2470 Multiply(T0, R, T3, M1, N2);
2471 c2 -= Subtract(T0, T2, T0, N2);
2472 int c3 = -(int)Subtract(T1, X2, T1, N2);
2473 Multiply(R0, T2, V1, X3, N2);
2474 c3 += Add(R, R, T, N);
2477 c3 += Increment(R1, N2);
2479 c3 -= Decrement(R1, N2, -c2);
2481 assert(c3>=-1 && c3<=1);
2483 Subtract(R, R, M, N);
2577 static inline void AtomicDivide(word *Q,
const word *A,
const word *B)
2580 DWord q = DivideFourWordsByTwo<word, DWord>(T,
DWord(A[0], A[1]),
DWord(A[2], A[3]),
DWord(B[0], B[1]));
2581 Q[0] = q.GetLowHalf();
2582 Q[1] = q.GetHighHalf();
2588 assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2592 assert(memcmp(P, A, 4*WORD_SIZE)==0);
2598 static void CorrectQuotientEstimate(word *R, word *T, word *Q,
const word *B,
size_t N)
2600 assert(N && N%2==0);
2602 AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2604 word borrow = Subtract(R, R, T, N+2);
2605 assert(!borrow && !R[N+1]);
2606 CRYPTOPP_UNUSED(borrow);
2608 while (R[N] || Compare(R, B, N) >= 0)
2610 R[N] -= Subtract(R, R, B, N);
2611 Q[1] += (++Q[0]==0);
2612 assert(Q[0] || Q[1]);
2622 void Divide(word *R, word *Q, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2624 assert(NA && NB && NA%2==0 && NB%2==0);
2625 assert(B[NB-1] || B[NB-2]);
2630 word *
const TB=T+NA+2;
2631 word *
const TP=T+NA+2+NB;
2634 unsigned shiftWords = (B[NB-1]==0);
2635 TB[0] = TB[NB-1] = 0;
2636 CopyWords(TB+shiftWords, B, NB-shiftWords);
2637 unsigned shiftBits = WORD_BITS -
BitPrecision(TB[NB-1]);
2638 assert(shiftBits < WORD_BITS);
2639 ShiftWordsLeftByBits(TB, NB, shiftBits);
2642 TA[0] = TA[NA] = TA[NA+1] = 0;
2643 CopyWords(TA+shiftWords, A, NA);
2644 ShiftWordsLeftByBits(TA, NA+2, shiftBits);
2646 if (TA[NA+1]==0 && TA[NA] <= 1)
2648 Q[NA-NB+1] = Q[NA-NB] = 0;
2649 while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
2651 TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
2658 assert(Compare(TA+NA-NB, TB, NB) < 0);
2662 BT[0] = TB[NB-2] + 1;
2663 BT[1] = TB[NB-1] + (BT[0]==0);
2666 for (
size_t i=NA-2; i>=NB; i-=2)
2668 AtomicDivide(Q+i-NB, TA+i-2, BT);
2669 CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
2673 CopyWords(R, TA+shiftWords, NB);
2674 ShiftWordsRightByBits(R, NB, shiftBits);
2677 static inline size_t EvenWordCount(
const word *X,
size_t N)
2679 while (N && X[N-2]==0 && X[N-1]==0)
2690 unsigned int AlmostInverse(word *R, word *T,
const word *A,
size_t NA,
const word *M,
size_t N)
2692 assert(NA<=N && N && N%2==0);
2698 size_t bcLen=2, fgLen=EvenWordCount(M, N);
2702 SetWords(T, 0, 3*N);
2704 CopyWords(f, A, NA);
2712 if (EvenWordCount(f, fgLen)==0)
2718 ShiftWordsRightByWords(f, fgLen, 1);
2719 bcLen += 2 * (c[bcLen-1] != 0);
2721 ShiftWordsLeftByWords(c, bcLen, 1);
2731 if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0)
2734 Subtract(R, M, b, N);
2740 ShiftWordsRightByBits(f, fgLen, i);
2741 t = ShiftWordsLeftByBits(c, bcLen, i);
2743 bcLen += 2 * (t!=0);
2746 bool swap = Compare(f, g, fgLen)==-1;
2751 fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]);
2753 Subtract(f, f, g, fgLen);
2754 t = Add(b, b, c, bcLen);
2765 void DivideByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2772 ShiftWordsRightByBits(R, N, 1);
2775 word carry = Add(R, R, M, N);
2776 ShiftWordsRightByBits(R, N, 1);
2777 R[N-1] += carry<<(WORD_BITS-1);
2786 void MultiplyByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2791 if (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0)
2792 Subtract(R, R, M, N);
2797 InitializeInteger::InitializeInteger()
2799 if (!g_pAssignIntToInteger)
2801 SetFunctionPointers();
2802 g_pAssignIntToInteger = AssignIntToInteger;
2806 static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
2808 static inline size_t RoundupSize(
size_t n)
2811 return RoundupSizeTable[n];
2822 : reg(2), sign(POSITIVE)
2824 reg[0] = reg[1] = 0;
2828 : reg(RoundupSize(t.
WordCount())), sign(t.sign)
2830 CopyWords(reg, t.reg, reg.
size());
2836 reg[0] = word(value);
2837 reg[1] = word(SafeRightShift<WORD_BITS>(value));
2850 reg[0] = word(value);
2851 reg[1] = word(SafeRightShift<WORD_BITS>((
unsigned long)value));
2866 unsigned long value = (
unsigned long)reg[0];
2867 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2870 return (
signed long)value >= 0;
2872 return -(
signed long)value < 0;
2879 unsigned long value = (
unsigned long)reg[0];
2880 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2881 return sign==
POSITIVE ? value : -(
signed long)value;
2886 Decode(encodedInteger, byteCount, s);
2891 Decode(encodedInteger, byteCount, s);
2906 if (!
Randomize(rng, min, max, rnType, equiv, mod))
2941 bool Integer::operator!()
const 2943 return IsNegative() ?
false : (reg[0]==0 &&
WordCount()==0);
2950 if (reg.size() != t.reg.
size() || t.reg[t.reg.
size()/2] == 0)
2952 CopyWords(reg, t.reg, reg.
size());
2960 if (n/WORD_BITS >= reg.size())
2963 return bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1);
2971 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
2975 if (n/WORD_BITS < reg.size())
2976 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
2982 if (n/WORD_SIZE >= reg.size())
2985 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
2991 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
2992 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
2998 assert(n <=
sizeof(v)*8);
2999 for (
unsigned int j=0; j<n; j++)
3000 v |= lword(
GetBit(i+j)) << j;
3004 Integer Integer::operator-()
const 3011 Integer Integer::AbsoluteValue()
const 3021 std::swap(sign, a.sign);
3025 : reg(RoundupSize(length)), sign(
POSITIVE)
3028 SetWords(reg+1, 0, reg.size()-1);
3032 static Integer StringToInteger(
const T *str)
3037 unsigned int length;
3038 for (length = 0; str[length] != 0; length++) {}
3045 switch (str[length-1])
3063 if (length > 2 && str[0] ==
'0' && str[1] ==
'x')
3066 for (
unsigned i=0; i<length; i++)
3070 if (str[i] >=
'0' && str[i] <=
'9')
3071 digit = str[i] -
'0';
3072 else if (str[i] >=
'A' && str[i] <=
'F')
3073 digit = str[i] -
'A' + 10;
3074 else if (str[i] >=
'a' && str[i] <=
'f')
3075 digit = str[i] -
'a' + 10;
3095 *
this = StringToInteger(str);
3101 *
this = StringToInteger(str);
3106 return (
unsigned int)CountWords(reg, reg.
size());
3113 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
3122 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
3130 Decode(store, inputLen, s);
3141 while (inputLen>0 && (sign==
POSITIVE ? b==0 : b==0xff))
3149 const size_t size = RoundupSize(
BytesToWords(inputLen));
3153 for (
size_t i=inputLen; i > 0; i--)
3156 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
3161 for (
size_t i=inputLen; i<reg.
size()*WORD_SIZE; i++)
3162 reg[i/WORD_SIZE] |= word(0xff) << (i%WORD_SIZE)*8;
3163 TwosComplement(reg, reg.
size());
3172 if (NotNegative() && (
GetByte(outputLen-1) & 0x80))
3174 if (IsNegative() && *
this < -
Power2(outputLen*8-1))
3181 assert(output && outputLen);
3183 Encode(sink, outputLen, signedness);
3188 if (signedness ==
UNSIGNED || NotNegative())
3190 for (
size_t i=outputLen; i > 0; i--)
3217 if (!dec.IsDefiniteLength() || dec.
MaxRetrievable() < dec.RemainingLength())
3233 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
3247 word16 bitCount = word16(
BitCount());
3251 return 2 + byteCount;
3270 const size_t nbytes = nbits/8 + 1;
3274 buf[0] = (byte)
Crop(buf[0], nbits % 8);
3284 const unsigned int nbits = range.
BitCount();
3290 while (*
this > range);
3297 return GenerateRandomNoThrow(rng,
MakeParameters(
"Min", min)(
"Max", max)(
"RandomNumberType", rnType)(
"EquivalentTo", equiv)(
"Mod", mod));
3303 KDF2_RNG(
const byte *seed,
size_t seedSize)
3304 : m_counter(0), m_counterAndSeed(seedSize + 4)
3306 memcpy(m_counterAndSeed + 4, seed, seedSize);
3311 PutWord(
false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3339 if (equiv.IsNegative() || equiv >= mod)
3340 throw InvalidArgument(
"Integer: invalid EquivalentTo and/or Mod argument");
3359 bq.
Get(finalSeed, finalSeed.size());
3360 kdf2Rng.reset(
new KDF2_RNG(finalSeed.begin(), finalSeed.size()));
3371 Integer min1 = min + (equiv-min)%mod;
3392 if (
FirstPrime(first, max, equiv, mod, pSelector))
3396 if (!
FirstPrime(first, max, equiv, mod, pSelector))
3404 if (
FirstPrime(*
this,
STDMIN(*
this+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector))
3414 std::istream& operator>>(std::istream& in,
Integer &a)
3417 unsigned int length = 0;
3426 if (length >= str.
size())
3427 str.
Grow(length + 16);
3429 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==
'.'));
3433 str[length-1] =
'\0';
3439 std::ostream& operator<<(std::ostream& out,
const Integer &a)
3442 const long f = out.flags() & std::ios::basefield;
3447 case std::ios::oct :
3452 case std::ios::hex :
3474 static const char upper[]=
"0123456789ABCDEF";
3475 static const char lower[]=
"0123456789abcdef";
3477 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3496 return out << suffix;
3499 Integer& Integer::operator++()
3503 if (Increment(reg, reg.size()))
3505 reg.CleanGrow(2*reg.size());
3506 reg[reg.size()/2]=1;
3511 word borrow = Decrement(reg, reg.size());
3513 CRYPTOPP_UNUSED(borrow);
3521 Integer& Integer::operator--()
3525 if (Increment(reg, reg.size()))
3527 reg.CleanGrow(2*reg.size());
3528 reg[reg.size()/2]=1;
3533 if (Decrement(reg, reg.size()))
3543 carry = Add(sum.reg, a.reg, b.reg, a.reg.
size());
3544 else if (a.reg.
size() > b.reg.
size())
3546 carry = Add(sum.reg, a.reg, b.reg, b.reg.
size());
3547 CopyWords(sum.reg+b.reg.
size(), a.reg+b.reg.
size(), a.reg.
size()-b.reg.
size());
3548 carry = Increment(sum.reg+b.reg.
size(), a.reg.
size()-b.reg.
size(), carry);
3552 carry = Add(sum.reg, a.reg, b.reg, a.reg.
size());
3553 CopyWords(sum.reg+a.reg.
size(), b.reg+a.reg.
size(), b.reg.
size()-a.reg.
size());
3554 carry = Increment(sum.reg+a.reg.
size(), b.reg.
size()-a.reg.
size(), carry);
3560 sum.reg[sum.reg.
size()/2] = 1;
3574 if (
Compare(a.reg, b.reg, aSize) >= 0)
3576 Subtract(diff.reg, a.reg, b.reg, aSize);
3581 Subtract(diff.reg, b.reg, a.reg, aSize);
3585 else if (aSize > bSize)
3587 word borrow = Subtract(diff.reg, a.reg, b.reg, bSize);
3588 CopyWords(diff.reg+bSize, a.reg+bSize, aSize-bSize);
3589 borrow = Decrement(diff.reg+bSize, aSize-bSize, borrow);
3595 word borrow = Subtract(diff.reg, b.reg, a.reg, aSize);
3596 CopyWords(diff.reg+aSize, b.reg+aSize, bSize-aSize);
3597 borrow = Decrement(diff.reg+aSize, bSize-aSize, borrow);
3604 template <
class T>
inline const T& STDMAX2(
const T& a,
const T& b)
3606 return a < b ? b : a;
3611 Integer sum((word)0, STDMAX2(reg.size(), b.reg.
size()));
3614 if (b.NotNegative())
3615 PositiveAdd(sum, *
this, b);
3617 PositiveSubtract(sum, *
this, b);
3621 if (b.NotNegative())
3622 PositiveSubtract(sum, b, *
this);
3625 PositiveAdd(sum, *
this, b);
3634 reg.CleanGrow(t.reg.
size());
3637 if (t.NotNegative())
3638 PositiveAdd(*
this, *
this, t);
3640 PositiveSubtract(*
this, *
this, t);
3644 if (t.NotNegative())
3645 PositiveSubtract(*
this, t, *
this);
3648 PositiveAdd(*
this, *
this, t);
3657 Integer diff((word)0, STDMAX2(reg.size(), b.reg.
size()));
3660 if (b.NotNegative())
3661 PositiveSubtract(diff, *
this, b);
3663 PositiveAdd(diff, *
this, b);
3667 if (b.NotNegative())
3669 PositiveAdd(diff, *
this, b);
3673 PositiveSubtract(diff, b, *
this);
3680 reg.CleanGrow(t.reg.
size());
3683 if (t.NotNegative())
3684 PositiveSubtract(*
this, *
this, t);
3686 PositiveAdd(*
this, *
this, t);
3690 if (t.NotNegative())
3692 PositiveAdd(*
this, *
this, t);
3696 PositiveSubtract(*
this, t, *
this);
3701 Integer& Integer::operator<<=(
size_t n)
3704 const size_t shiftWords = n / WORD_BITS;
3705 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3707 reg.CleanGrow(RoundupSize(wordCount+
BitsToWords(n)));
3708 ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords);
3709 ShiftWordsLeftByBits(reg+shiftWords, wordCount+
BitsToWords(shiftBits), shiftBits);
3713 Integer& Integer::operator>>=(
size_t n)
3716 const size_t shiftWords = n / WORD_BITS;
3717 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3719 ShiftWordsRightByWords(reg, wordCount, shiftWords);
3720 if (wordCount > shiftWords)
3721 ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits);
3729 size_t aSize = RoundupSize(a.
WordCount());
3730 size_t bSize = RoundupSize(b.
WordCount());
3732 product.reg.
CleanNew(RoundupSize(aSize+bSize));
3736 AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
3741 PositiveMultiply(product, a, b);
3743 if (a.NotNegative() != b.NotNegative())
3750 Multiply(product, *
this, b);
3796 remainder.reg.
CleanNew(RoundupSize(bSize));
3798 quotient.reg.
CleanNew(RoundupSize(aSize-bSize+2));
3802 Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
3807 PositiveDivide(remainder, quotient, dividend, divisor);
3809 if (dividend.IsNegative())
3812 if (remainder.NotZero())
3815 remainder = divisor.AbsoluteValue() - remainder;
3819 if (divisor.IsNegative())
3831 r.reg.
resize(RoundupSize(wordCount));
3832 CopyWords(r.reg, a.reg, wordCount);
3833 SetWords(r.reg+wordCount, 0, r.reg.
size()-wordCount);
3834 if (n % WORD_BITS != 0)
3835 r.reg[wordCount-1] %= (word(1) << (n % WORD_BITS));
3840 CopyWords(r.reg, a.reg, r.reg.
size());
3844 if (a.IsNegative() && r.NotZero())
3872 if ((divisor & (divisor-1)) == 0)
3875 remainder = dividend.reg[0] & (divisor-1);
3880 quotient.reg.
CleanNew(RoundupSize(i));
3884 quotient.reg[i] =
DWord(dividend.reg[i], remainder) / divisor;
3885 remainder =
DWord(dividend.reg[i], remainder) % divisor;
3888 if (dividend.NotNegative())
3896 remainder = divisor - remainder;
3901 Integer Integer::DividedBy(word b)
const 3918 if ((divisor & (divisor-1)) == 0)
3919 remainder = reg[0] & (divisor-1);
3929 remainder = sum % divisor;
3935 remainder =
DWord(reg[i], remainder) % divisor;
3939 if (IsNegative() && remainder)
3940 remainder = divisor - remainder;
3948 sign =
Sign(1-sign);
3951 int Integer::PositiveCompare(
const Integer& t)
const 3956 return CryptoPP::Compare(reg, t.reg, size);
3958 return size > tSize ? 1 : -1;
3965 if (t.NotNegative())
3966 return PositiveCompare(t);
3972 if (t.NotNegative())
3975 return -PositiveCompare(t);
3986 assert(y*y >= *
this);
3991 y = (x + *
this/x) >> 1;
4005 return (
WordCount() == 1) && (reg[0] == 1);
4021 return mr.Exponentiate(x, e);
4031 assert(m.NotNegative());
4044 return !u ?
Zero() : (m*(*
this-u)+1)/(*this);
4049 unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.
size());
4050 DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.
size());
4056 word g0 = mod, g1 = *
this % mod;
4057 word v0 = 0, v1 = 1;
4085 if (oid != ASN1::prime_field())
4087 m_modulus.BERDecode(seq);
4089 m_result.reg.resize(m_modulus.reg.size());
4095 ASN1::prime_field().DEREncode(seq);
4096 m_modulus.DEREncode(seq);
4102 a.DEREncodeAsOctetString(out, MaxElementByteLength());
4107 a.BERDecodeAsOctetString(in, MaxElementByteLength());
4112 if (a.reg.
size()==m_modulus.reg.size())
4114 CryptoPP::DivideByPower2Mod(m_result.reg.begin(), a.reg, 1, m_modulus.reg, a.reg.
size());
4118 return m_result1 = (a.IsEven() ? (a >> 1) : ((a+m_modulus) >> 1));
4123 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4125 if (CryptoPP::Add(m_result.reg.begin(), a.reg, b.reg, a.reg.
size())
4126 ||
Compare(m_result.reg, m_modulus.reg, a.reg.
size()) >= 0)
4128 CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.
size());
4135 if (m_result1 >= m_modulus)
4136 m_result1 -= m_modulus;
4143 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4145 if (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.
size())
4146 ||
Compare(a.reg, m_modulus.reg, a.reg.
size()) >= 0)
4148 CryptoPP::Subtract(a.reg, a.reg, m_modulus.reg, a.reg.
size());
4163 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4165 if (CryptoPP::Subtract(m_result.reg.begin(), a.reg, b.reg, a.reg.
size()))
4166 CryptoPP::Add(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.
size());
4172 if (m_result1.IsNegative())
4173 m_result1 += m_modulus;
4180 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4182 if (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.
size()))
4183 CryptoPP::Add(a.reg, a.reg, m_modulus.reg, a.reg.
size());
4195 const Integer& ModularArithmetic::Inverse(
const Integer &a)
const 4200 CopyWords(m_result.reg.begin(), m_modulus.reg, m_modulus.reg.size());
4201 if (CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, a.reg, a.reg.
size()))
4202 Decrement(m_result.reg.begin()+a.reg.
size(), m_modulus.reg.size()-a.reg.
size());
4209 if (m_modulus.IsOdd())
4212 return dr.ConvertOut(dr.CascadeExponentiate(dr.ConvertIn(x), e1, dr.ConvertIn(y), e2));
4218 void ModularArithmetic::SimultaneousExponentiate(
Integer *results,
const Integer &base,
const Integer *exponents,
unsigned int exponentsCount)
const 4220 if (m_modulus.IsOdd())
4223 dr.SimultaneousExponentiate(results, dr.ConvertIn(base), exponents, exponentsCount);
4224 for (
unsigned int i=0; i<exponentsCount; i++)
4225 results[i] = dr.ConvertOut(results[i]);
4231 MontgomeryRepresentation::MontgomeryRepresentation(
const Integer &m)
4233 m_u((word)0, m_modulus.reg.size()),
4234 m_workspace(5*m_modulus.reg.size())
4236 if (!m_modulus.IsOdd())
4237 throw InvalidArgument(
"MontgomeryRepresentation: Montgomery representation requires an odd modulus");
4239 RecursiveInverseModPower2(m_u.reg, m_workspace, m_modulus.reg, m_modulus.reg.size());
4244 word *
const T = m_workspace.begin();
4245 word *
const R = m_result.reg.begin();
4246 const size_t N = m_modulus.reg.size();
4247 assert(a.reg.
size()<=N && b.reg.
size()<=N);
4249 AsymmetricMultiply(T, T+2*N, a.reg, a.reg.
size(), b.reg, b.reg.
size());
4251 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4255 const Integer& MontgomeryRepresentation::Square(
const Integer &a)
const 4257 word *
const T = m_workspace.begin();
4258 word *
const R = m_result.reg.begin();
4259 const size_t N = m_modulus.reg.size();
4260 assert(a.reg.
size()<=N);
4262 CryptoPP::Square(T, T+2*N, a.reg, a.reg.
size());
4263 SetWords(T+2*a.reg.
size(), 0, 2*N-2*a.reg.
size());
4264 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4268 Integer MontgomeryRepresentation::ConvertOut(
const Integer &a)
const 4270 word *
const T = m_workspace.begin();
4271 word *
const R = m_result.reg.begin();
4272 const size_t N = m_modulus.reg.size();
4273 assert(a.reg.
size()<=N);
4275 CopyWords(T, a.reg, a.reg.
size());
4276 SetWords(T+a.reg.
size(), 0, 2*N-a.reg.
size());
4277 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4281 const Integer& MontgomeryRepresentation::MultiplicativeInverse(
const Integer &a)
const 4284 word *
const T = m_workspace.begin();
4285 word *
const R = m_result.reg.begin();
4286 const size_t N = m_modulus.reg.size();
4287 assert(a.reg.
size()<=N);
4289 CopyWords(T, a.reg, a.reg.
size());
4290 SetWords(T+a.reg.
size(), 0, 2*N-a.reg.
size());
4291 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4292 unsigned k = AlmostInverse(R, T, R, N, m_modulus.reg, N);
4297 DivideByPower2Mod(R, R, k-N*WORD_BITS, m_modulus.reg, N);
4299 MultiplyByPower2Mod(R, R, N*WORD_BITS-k, m_modulus.reg, N);
4306 template <> CRYPTOPP_DLL
4310 static const unsigned int BIT_32 = (1U << 31);
4311 const bool UPPER = !!(base & BIT_32);
4312 static const unsigned int BIT_31 = (1U << 30);
4313 const bool BASE = !!(base & BIT_31);
4315 const char CH = UPPER ?
'A' :
'a';
4316 base &= ~(BIT_32|BIT_31);
4317 assert(base >= 2 && base <= 32);
4322 bool negative =
false, zero =
false;
4323 if (value.IsNegative())
4340 s[i++]=char((digit < 10 ?
'0' : (CH - 10)) + digit);
4345 result.reserve(i+2);
4360 else if (base == 16)
4372 template <> CRYPTOPP_DLL
4376 static const unsigned int HIGH_BIT = (1U << 31);
4377 const char CH = !!(base & HIGH_BIT) ?
'A' :
'a';
4387 unsigned long long digit = value % base;
4388 result = char((digit < 10 ?
'0' : (CH - 10)) + digit) + result;
4396 #if WORKAROUND_ARMEL_BUG 4397 # pragma GCC pop_options 4400 #if WORKAROUND_ARM64_BUG 4401 # pragma GCC pop_options used to pass byte array input as part of a NameValuePairs object
An invalid argument was detected.
Classes for working with NameValuePairs.
a number which is probabilistically prime
Utility functions for the Crypto++ library.
Restricts the instantiation of a class to one static object without locks.
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 without preserving contents.
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode Unsigned.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
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.
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.
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
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.
Secure memory block with allocator and cleanup.
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
void OpenPGPDecode(const byte *input, size_t inputLen)
Decode from OpenPGP format.
Signedness
Used when importing and exporting integers.
size_type size() const
Provides the count of elements in the SecBlock.
Object identifiers for algorthms and schemes.
Classes for automatic resource management.
byte GetByte(size_t i) const
return the i-th byte
Library configuration file.
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.
size_t MinEncodedSize(Signedness sign=UNSIGNED) const
The minimum number of bytes to encode this integer.
void SetByte(size_t n, byte value)
Set the n-th byte to value.
SecByteBlock is a SecBlock<byte> typedef.
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode absolute value as big-endian octet string
lword MaxRetrievable() const
Provides the number of bytes 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()
Integer representing 1.
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Sign
Used internally to represent the integer.
Pointer that overloads operator→
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.
Classes and functions for secure memory allocations.
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.
a number with no special properties
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.
signed long ConvertToLong() const
return equivalent signed long if possible, otherwise undefined
Exception thrown when an error is encountered decoding an OpenPGP integer.
void Negate()
Reverse the Sign of the Integer.
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Integer Times(const Integer &b) const
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.
static const Integer & Two()
Integer representing 2.
RandomNumberType
Properties of a random integer.
const char * Seed()
ConstByteArrayParameter.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
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))
Classes, functions, intrinsics and features for X86, X32 nd X64 assembly.
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.
const char * PointerToPrimeSelector()
const PrimeSelector *
Implementation of BufferedTransformation's attachment interface in cryptlib.h.
Classes and functions for number theoretic operations.
std::string IntToString< unsigned long long >(unsigned long long value, unsigned int base)
Converts an unsigned value to a string.
size_t DEREncodeOctetString(BufferedTransformation &out, const byte *str, size_t strLen)
ASN Strings.
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Exception thrown when division by 0 is encountered.
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.
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
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
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.
lword GetBits(size_t i, size_t n) const
return n lowest bits of *this >> i
Class file for performing modular arithmetic.
Crypto++ library namespace.
size_type SizeInBytes() const
Provides the number of bytes in the SecBlock.
int Compare(const Integer &a) const
Perform signed comparison.
Integer Modulo(const Integer &b) const
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
the value is positive or 0
Interface for retrieving values given their names.