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) 62 #if __ARMEL__ && (CRYPTOPP_GCC_VERSION >= 40900) && (CRYPTOPP_GCC_VERSION < 70000) && __OPTIMIZE__ 63 # define WORKAROUND_ARMEL_BUG 1 66 #if WORKAROUND_ARMEL_BUG 67 # pragma GCC push_options 68 # pragma GCC optimize("O1") 73 bool AssignIntToInteger(const
std::type_info &valueType,
void *pInteger, const
void *pInt)
75 if (valueType !=
typeid(
Integer))
77 *
reinterpret_cast<Integer *
>(pInteger) = *reinterpret_cast<const int *>(pInt);
81 inline static int Compare(
const word *A,
const word *B,
size_t N)
92 inline static int Increment(word *A,
size_t N, word B=1)
99 for (
unsigned i=1; i<N; i++)
105 inline static int Decrement(word *A,
size_t N, word B=1)
112 for (
unsigned i=1; i<N; i++)
118 static void TwosComplement(word *A,
size_t N)
121 for (
unsigned i=0; i<N; i++)
125 static word AtomicInverseModPower2(word A)
131 for (
unsigned i=3; i<WORD_BITS; i*=2)
140 #if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE)) 141 #define Declare2Words(x) word x##0, x##1; 142 #define AssignWord(a, b) a##0 = b; a##1 = 0; 143 #define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c); 144 #define LowWord(a) a##0 145 #define HighWord(a) a##1 147 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1); 148 #ifndef __INTEL_COMPILER 149 #define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2; 151 #elif defined(__DECCXX) 152 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b); 153 #elif defined(__x86_64__) 154 #if defined(__SUNPRO_CC) && __SUNPRO_CC < 0x5100 156 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc"); 158 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc"); 159 #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"); 160 #define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc"); 161 #define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc"); 162 #define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc"); 163 #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"); 166 #define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b) 168 #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; 171 #define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1; 173 #define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);} 174 #define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);} 175 #define GetCarry(u) u##1 176 #define GetBorrow(u) u##1 178 #define Declare2Words(x) dword x; 179 #if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER) 180 #define MultiplyWords(p, a, b) p = __emulu(a, b); 182 #define MultiplyWords(p, a, b) p = (dword)a*b; 184 #define AssignWord(a, b) a = b; 185 #define Add2WordsBy1(a, b, c) a = b + c; 186 #define Acc2WordsBy2(a, b) a += b; 187 #define LowWord(a) word(a) 188 #define HighWord(a) word(a>>WORD_BITS) 189 #define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2; 190 #define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u); 191 #define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u); 192 #define GetCarry(u) HighWord(u) 193 #define GetBorrow(u) word(u>>(WORD_BITS*2-1)) 196 #define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p)); 199 #define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b) 202 #define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e)); 210 #if (defined(__COVERITY__) || !defined(NDEBUG)) && defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 212 DWord() : m_whole(0) {memset(&m_whole, 0xa,
sizeof(m_whole));}
213 #elif (defined(__COVERITY__) || !defined(NDEBUG)) && !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) 215 DWord() : m_halfs() {memset(&m_halfs, 0xa,
sizeof(m_halfs));}
220 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 221 explicit DWord(word low) : m_whole(low) {}
223 explicit DWord(word low)
230 DWord(word low, word high)
236 static DWord Multiply(word a, word b)
239 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 240 r.m_whole = (dword)a * b;
241 #elif defined(MultiplyWordsLoHi) 242 MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
249 static DWord MultiplyAndAdd(word a, word b, word c)
251 DWord r = Multiply(a, b);
255 DWord & operator+=(word a)
257 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 258 m_whole = m_whole + a;
261 m_halfs.high += (m_halfs.low < a);
266 DWord operator+(word a)
269 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 270 r.m_whole = m_whole + a;
272 r.m_halfs.low = m_halfs.low + a;
273 r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a);
281 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 282 r.m_whole = m_whole - a.m_whole;
284 r.m_halfs.low = m_halfs.low - a.m_halfs.low;
285 r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low);
290 DWord operator-(word a)
293 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 294 r.m_whole = m_whole - a;
296 r.m_halfs.low = m_halfs.low - a;
297 r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low);
303 word operator/(word divisor);
305 word operator%(word a);
307 bool operator!()
const 309 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 312 return !m_halfs.high && !m_halfs.low;
316 word GetLowHalf()
const {
return m_halfs.low;}
317 word GetHighHalf()
const {
return m_halfs.high;}
318 word GetHighHalfAsBorrow()
const {
return 0-m_halfs.high;}
323 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 328 #ifdef IS_LITTLE_ENDIAN 344 #if defined(__COVERITY__) 345 Word() : m_whole(0) {}
346 #elif !defined(NDEBUG) 348 Word() : m_whole(0) {memset(&m_whole, 0xa,
sizeof(m_whole));}
353 Word(word value) : m_whole(value) {}
354 Word(hword low, hword high) : m_whole(low | (word(high) << (WORD_BITS/2))) {}
356 static Word Multiply(hword a, hword b)
359 r.m_whole = (word)a * b;
366 r.m_whole = m_whole - a.m_whole;
370 Word operator-(hword a)
373 r.m_whole = m_whole - a;
378 hword operator/(hword divisor)
380 return hword(m_whole / divisor);
383 bool operator!()
const 388 word GetWhole()
const {
return m_whole;}
389 hword GetLowHalf()
const {
return hword(m_whole);}
390 hword GetHighHalf()
const {
return hword(m_whole>>(WORD_BITS/2));}
391 hword GetHighHalfAsBorrow()
const {
return 0-hword(m_whole>>(WORD_BITS/2));}
398 template <
class S,
class D>
399 S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULL)
401 CRYPTOPP_UNUSED(dummy);
404 assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));
411 Q = D(A[1], A[2]) / S(B1+1);
413 Q = D(A[0], A[1]) / B0;
416 D p = D::Multiply(B0, Q);
417 D u = (D) A[0] - p.GetLowHalf();
418 A[0] = u.GetLowHalf();
419 u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q);
420 A[1] = u.GetLowHalf();
421 A[2] += u.GetHighHalf();
424 while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
427 A[0] = u.GetLowHalf();
428 u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
429 A[1] = u.GetLowHalf();
430 A[2] += u.GetHighHalf();
439 template <
class S,
class D>
440 inline D DivideFourWordsByTwo(S *T,
const D &Al,
const D &Ah,
const D &B)
443 return D(Ah.GetLowHalf(), Ah.GetHighHalf());
447 T[0] = Al.GetLowHalf();
448 T[1] = Al.GetHighHalf();
449 T[2] = Ah.GetLowHalf();
450 T[3] = Ah.GetHighHalf();
451 Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(), B.GetHighHalf());
452 Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
453 return D(Q[0], Q[1]);
458 inline word DWord::operator/(word a)
460 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 461 return word(m_whole / a);
464 return DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a).GetWhole();
468 inline word DWord::operator%(word a)
470 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE 471 return word(m_whole % a);
473 if (a < (word(1) << (WORD_BITS/2)))
476 word r = m_halfs.high % h;
477 r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
478 return hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h);
483 DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a);
484 return Word(r[0], r[1]).GetWhole();
492 #if defined(__GNUC__) 493 #define AddPrologue \ 495 __asm__ __volatile__ \ 498 #define AddEpilogue \ 499 ".att_syntax prefix;" \ 501 : "d" (C), "a" (A), "D" (B), "c" (N) \ 502 : "%esi", "memory", "cc" \ 505 #define MulPrologue \ 506 __asm__ __volatile__ \ 508 ".intel_syntax noprefix;" \ 511 #define MulEpilogue \ 513 ".att_syntax prefix;" \ 515 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \ 516 : "%esi", "memory", "cc" \ 518 #define SquPrologue MulPrologue 519 #define SquEpilogue \ 521 ".att_syntax prefix;" \ 523 : "d" (s_maskLow16), "c" (C), "a" (A) \ 524 : "%esi", "%edi", "memory", "cc" \ 526 #define TopPrologue MulPrologue 527 #define TopEpilogue \ 529 ".att_syntax prefix;" \ 531 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \ 535 #define AddPrologue \ 538 __asm mov eax, [esp+12] \ 539 __asm mov edi, [esp+16] 540 #define AddEpilogue \ 545 #define SaveEBX __asm push ebx 546 #define RestoreEBX __asm pop ebx 551 #define SquPrologue \ 555 AS2( lea ebx, s_maskLow16) 556 #define MulPrologue \ 561 AS2( lea ebx, s_maskLow16) 562 #define TopPrologue \ 568 AS2( lea ebx, s_maskLow16) 569 #define SquEpilogue RestoreEBX 570 #define MulEpilogue RestoreEBX 571 #define TopEpilogue RestoreEBX 574 #ifdef CRYPTOPP_X64_MASM_AVAILABLE 576 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B);
577 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B);
579 #elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE) 580 int Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
588 AS2( mov %0,[%3+8*%1])
589 AS2( add %0,[%4+8*%1])
590 AS2( mov [%2+8*%1],%0)
592 AS2( mov %0,[%3+8*%1+8])
593 AS2( adc %0,[%4+8*%1+8])
594 AS2( mov [%2+8*%1+8],%0)
597 AS2( mov %0,[%3+8*%1])
598 AS2( adc %0,[%4+8*%1])
599 AS2( mov [%2+8*%1],%0)
605 :
"=&r" (result),
"+c" (N)
606 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
612 int Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
620 AS2( mov %0,[%3+8*%1])
621 AS2( sub %0,[%4+8*%1])
622 AS2( mov [%2+8*%1],%0)
624 AS2( mov %0,[%3+8*%1+8])
625 AS2( sbb %0,[%4+8*%1+8])
626 AS2( mov [%2+8*%1+8],%0)
629 AS2( mov %0,[%3+8*%1])
630 AS2( sbb %0,[%4+8*%1])
631 AS2( mov [%2+8*%1],%0)
637 :
"=&r" (result),
"+c" (N)
638 :
"r" (C+N),
"r" (A+N),
"r" (B+N)
643 #elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86 644 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
649 AS2( lea eax, [eax+4*ecx])
650 AS2( lea edi, [edi+4*ecx])
651 AS2( lea edx, [edx+4*ecx])
661 AS2( mov esi,[eax+4*ecx])
662 AS2( adc esi,[edi+4*ecx])
663 AS2( mov [edx+4*ecx],esi)
664 AS2( mov esi,[eax+4*ecx+4])
665 AS2( adc esi,[edi+4*ecx+4])
666 AS2( mov [edx+4*ecx+4],esi)
668 AS2( mov esi,[eax+4*ecx+8])
669 AS2( adc esi,[edi+4*ecx+8])
670 AS2( mov [edx+4*ecx+8],esi)
671 AS2( mov esi,[eax+4*ecx+12])
672 AS2( adc esi,[edi+4*ecx+12])
673 AS2( mov [edx+4*ecx+12],esi)
675 AS2( lea ecx,[ecx+4])
685 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
690 AS2( lea eax, [eax+4*ecx])
691 AS2( lea edi, [edi+4*ecx])
692 AS2( lea edx, [edx+4*ecx])
702 AS2( mov esi,[eax+4*ecx])
703 AS2( sbb esi,[edi+4*ecx])
704 AS2( mov [edx+4*ecx],esi)
705 AS2( mov esi,[eax+4*ecx+4])
706 AS2( sbb esi,[edi+4*ecx+4])
707 AS2( mov [edx+4*ecx+4],esi)
709 AS2( mov esi,[eax+4*ecx+8])
710 AS2( sbb esi,[edi+4*ecx+8])
711 AS2( mov [edx+4*ecx+8],esi)
712 AS2( mov esi,[eax+4*ecx+12])
713 AS2( sbb esi,[edi+4*ecx+12])
714 AS2( mov [edx+4*ecx+12],esi)
716 AS2( lea ecx,[ecx+4])
726 #if CRYPTOPP_INTEGER_SSE2 727 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Add(
size_t N, word *C,
const word *A,
const word *B)
732 AS2( lea eax, [eax+4*ecx])
733 AS2( lea edi, [edi+4*ecx])
734 AS2( lea edx, [edx+4*ecx])
745 AS2( movd mm0, DWORD PTR [eax+4*ecx])
746 AS2( movd mm1, DWORD PTR [edi+4*ecx])
749 AS2( movd DWORD PTR [edx+4*ecx], mm2)
752 AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
753 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
756 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
760 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
761 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
764 AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
767 AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
768 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
771 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
783 CRYPTOPP_NAKED
int CRYPTOPP_FASTCALL SSE2_Sub(
size_t N, word *C,
const word *A,
const word *B)
788 AS2( lea eax, [eax+4*ecx])
789 AS2( lea edi, [edi+4*ecx])
790 AS2( lea edx, [edx+4*ecx])
801 AS2( movd mm0, DWORD PTR [eax+4*ecx])
802 AS2( movd mm1, DWORD PTR [edi+4*ecx])
805 AS2( movd DWORD PTR [edx+4*ecx], mm0)
808 AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
809 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
812 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
816 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
817 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
820 AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
823 AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
824 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
827 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
839 #endif // #if CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE 841 int CRYPTOPP_FASTCALL Baseline_Add(
size_t N, word *C,
const word *A,
const word *B)
847 for (
size_t i=0; i<N; i+=2)
849 AddWithCarry(u, A[i], B[i]);
851 AddWithCarry(u, A[i+1], B[i+1]);
854 return int(GetCarry(u));
857 int CRYPTOPP_FASTCALL Baseline_Sub(
size_t N, word *C,
const word *A,
const word *B)
863 for (
size_t i=0; i<N; i+=2)
865 SubtractWithBorrow(u, A[i], B[i]);
867 SubtractWithBorrow(u, A[i+1], B[i+1]);
870 return int(GetBorrow(u));
874 static word LinearMultiply(word *C,
const word *A, word B,
size_t N)
877 for(
unsigned i=0; i<N; i++)
880 MultiplyWords(p, A[i], B);
881 Acc2WordsBy1(p, carry);
888 #ifndef CRYPTOPP_DOXYGEN_PROCESSING 892 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 897 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 898 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 899 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 900 Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \ 901 Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \ 906 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 907 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 908 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 909 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 910 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) \ 911 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) \ 912 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) \ 913 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) \ 914 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) \ 915 Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \ 916 Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \ 917 Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \ 918 Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \ 923 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 924 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 925 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 926 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 927 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) \ 928 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) \ 929 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) \ 930 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) \ 931 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) \ 932 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) \ 933 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) \ 934 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) \ 935 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) \ 936 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) \ 937 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) \ 938 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) \ 939 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) \ 940 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) \ 941 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) \ 942 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) \ 943 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) \ 944 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) \ 945 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) \ 946 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) \ 947 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) \ 948 Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \ 949 Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \ 950 Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \ 951 Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \ 960 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 961 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 962 Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \ 963 Squ_SaveAcc(4, 2, 3) Squ_NonDiag \ 968 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 969 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 970 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \ 971 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \ 972 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \ 973 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \ 974 Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \ 975 Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \ 976 Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \ 977 Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \ 978 Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \ 979 Squ_SaveAcc(12, 6, 7) Squ_NonDiag \ 984 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \ 985 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \ 986 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \ 987 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \ 988 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \ 989 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \ 990 Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \ 991 Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \ 992 Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \ 993 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 \ 994 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) \ 995 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 \ 996 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) \ 997 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 \ 998 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) \ 999 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 \ 1000 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) \ 1001 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 \ 1002 Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \ 1003 Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \ 1004 Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \ 1005 Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \ 1006 Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \ 1007 Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \ 1008 Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \ 1009 Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \ 1010 Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \ 1011 Squ_SaveAcc(28, 14, 15) Squ_NonDiag \ 1016 Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \ 1021 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1022 Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \ 1023 Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \ 1028 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1029 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 1030 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 1031 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 1032 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) \ 1033 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) \ 1034 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) \ 1039 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \ 1040 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \ 1041 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \ 1042 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \ 1043 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) \ 1044 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) \ 1045 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) \ 1046 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) \ 1047 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) \ 1048 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) \ 1049 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) \ 1050 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) \ 1051 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) \ 1052 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) \ 1053 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) \ 1059 #define Mul_Begin(n) \ 1063 MultiplyWords(p, A[0], B[0]) \ 1064 AssignWord(c, LowWord(p)) \ 1065 AssignWord(d, HighWord(p)) 1067 #define Mul_Acc(i, j) \ 1068 MultiplyWords(p, A[i], B[j]) \ 1069 Acc2WordsBy1(c, LowWord(p)) \ 1070 Acc2WordsBy1(d, HighWord(p)) 1072 #define Mul_SaveAcc(k, i, j) \ 1073 R[k] = LowWord(c); \ 1074 Add2WordsBy1(c, d, HighWord(c)) \ 1075 MultiplyWords(p, A[i], B[j]) \ 1076 AssignWord(d, HighWord(p)) \ 1077 Acc2WordsBy1(c, LowWord(p)) 1079 #define Mul_End(n) \ 1080 R[2*n-3] = LowWord(c); \ 1081 Acc2WordsBy1(d, HighWord(c)) \ 1082 MultiplyWords(p, A[n-1], B[n-1])\ 1083 Acc2WordsBy2(d, p) \ 1084 R[2*n-2] = LowWord(d); \ 1085 R[2*n-1] = HighWord(d); 1087 #define Bot_SaveAcc(k, i, j) \ 1088 R[k] = LowWord(c); \ 1089 word e = LowWord(d) + HighWord(c); \ 1092 #define Bot_Acc(i, j) \ 1095 #define Bot_End(n) \ 1098 #define Mul_Begin(n) \ 1102 MultiplyWords(p, A[0], B[0]) \ 1104 AssignWord(d, HighWord(p)) 1106 #define Mul_Acc(i, j) \ 1107 MulAcc(c, d, A[i], B[j]) 1109 #define Mul_SaveAcc(k, i, j) \ 1112 AssignWord(d, HighWord(d)) \ 1113 MulAcc(c, d, A[i], B[j]) 1115 #define Mul_End(k, i) \ 1117 MultiplyWords(p, A[i], B[i]) \ 1118 Acc2WordsBy2(p, d) \ 1119 R[k+1] = LowWord(p); \ 1120 R[k+2] = HighWord(p); 1122 #define Bot_SaveAcc(k, i, j) \ 1127 #define Bot_Acc(i, j) \ 1130 #define Bot_End(n) \ 1134 #define Squ_Begin(n) \ 1139 MultiplyWords(p, A[0], A[0]) \ 1140 R[0] = LowWord(p); \ 1141 AssignWord(e, HighWord(p)) \ 1142 MultiplyWords(p, A[0], A[1]) \ 1144 AssignWord(d, HighWord(p)) \ 1147 #define Squ_NonDiag \ 1150 #define Squ_SaveAcc(k, i, j) \ 1151 Acc3WordsBy2(c, d, e) \ 1153 MultiplyWords(p, A[i], A[j]) \ 1155 AssignWord(d, HighWord(p)) \ 1157 #define Squ_Acc(i, j) \ 1158 MulAcc(c, d, A[i], A[j]) 1160 #define Squ_Diag(i) \ 1162 MulAcc(c, d, A[i], A[i]) 1164 #define Squ_End(n) \ 1165 Acc3WordsBy2(c, d, e) \ 1167 MultiplyWords(p, A[n-1], A[n-1])\ 1168 Acc2WordsBy2(p, e) \ 1169 R[2*n-2] = LowWord(p); \ 1170 R[2*n-1] = HighWord(p); 1173 void Baseline_Multiply2(word *R,
const word *A,
const word *B)
1178 void Baseline_Multiply4(word *R,
const word *A,
const word *B)
1183 void Baseline_Multiply8(word *R,
const word *A,
const word *B)
1188 void Baseline_Square2(word *R,
const word *A)
1193 void Baseline_Square4(word *R,
const word *A)
1198 void Baseline_Square8(word *R,
const word *A)
1203 void Baseline_MultiplyBottom2(word *R,
const word *A,
const word *B)
1208 void Baseline_MultiplyBottom4(word *R,
const word *A,
const word *B)
1213 void Baseline_MultiplyBottom8(word *R,
const word *A,
const word *B)
1218 #define Top_Begin(n) \ 1222 MultiplyWords(p, A[0], B[n-2]);\ 1223 AssignWord(d, HighWord(p)); 1225 #define Top_Acc(i, j) \ 1226 MultiplyWords(p, A[i], B[j]);\ 1227 Acc2WordsBy1(d, HighWord(p)); 1229 #define Top_SaveAcc0(i, j) \ 1231 AssignWord(d, HighWord(d)) \ 1232 MulAcc(c, d, A[i], B[j]) 1234 #define Top_SaveAcc1(i, j) \ 1236 Acc2WordsBy1(d, c); \ 1238 AssignWord(d, HighWord(d)) \ 1239 MulAcc(c, d, A[i], B[j]) 1241 void Baseline_MultiplyTop2(word *R,
const word *A,
const word *B, word L)
1245 Baseline_Multiply2(T, A, B);
1250 void Baseline_MultiplyTop4(word *R,
const word *A,
const word *B, word L)
1253 Top_Acc(1, 1) Top_Acc(2, 0) \
1254 Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1255 Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1256 Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1260 void Baseline_MultiplyTop8(word *R,
const word *A,
const word *B, word L)
1263 Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1264 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) \
1265 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) \
1266 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) \
1267 Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1268 Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1269 Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1270 Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1274 #if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available 1275 void Baseline_Multiply16(word *R,
const word *A,
const word *B)
1280 void Baseline_Square16(word *R,
const word *A)
1285 void Baseline_MultiplyBottom16(word *R,
const word *A,
const word *B)
1290 void Baseline_MultiplyTop16(word *R,
const word *A,
const word *B, word L)
1293 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) \
1294 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) \
1295 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) \
1296 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) \
1297 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) \
1298 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) \
1299 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) \
1300 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) \
1301 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) \
1302 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) \
1303 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) \
1304 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) \
1305 Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1306 Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1307 Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1308 Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1315 #if CRYPTOPP_INTEGER_SSE2 1317 CRYPTOPP_ALIGN_DATA(16)
static const word32 s_maskLow16[4] CRYPTOPP_SECTION_ALIGN16 = {0xffff,0xffff,0xffff,0xffff};
1335 #define SSE2_FinalSave(k) \ 1336 AS2( psllq xmm5, 16) \ 1337 AS2( paddq xmm4, xmm5) \ 1338 AS2( movq QWORD PTR [ecx+8*(k)], xmm4) 1340 #define SSE2_SaveShift(k) \ 1341 AS2( movq xmm0, xmm6) \ 1342 AS2( punpckhqdq xmm6, xmm0) \ 1343 AS2( movq xmm1, xmm7) \ 1344 AS2( punpckhqdq xmm7, xmm1) \ 1345 AS2( paddd xmm6, xmm0) \ 1346 AS2( pslldq xmm6, 4) \ 1347 AS2( paddd xmm7, xmm1) \ 1348 AS2( paddd xmm4, xmm6) \ 1349 AS2( pslldq xmm7, 4) \ 1350 AS2( movq xmm6, xmm4) \ 1351 AS2( paddd xmm5, xmm7) \ 1352 AS2( movq xmm7, xmm5) \ 1353 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \ 1354 AS2( psrlq xmm6, 16) \ 1355 AS2( paddq xmm6, xmm7) \ 1356 AS2( punpckhqdq xmm4, xmm0) \ 1357 AS2( punpckhqdq xmm5, xmm0) \ 1358 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \ 1359 AS2( psrlq xmm6, 3*16) \ 1360 AS2( paddd xmm4, xmm6) \ 1362 #define Squ_SSE2_SaveShift(k) \ 1363 AS2( movq xmm0, xmm6) \ 1364 AS2( punpckhqdq xmm6, xmm0) \ 1365 AS2( movq xmm1, xmm7) \ 1366 AS2( punpckhqdq xmm7, xmm1) \ 1367 AS2( paddd xmm6, xmm0) \ 1368 AS2( pslldq xmm6, 4) \ 1369 AS2( paddd xmm7, xmm1) \ 1370 AS2( paddd xmm4, xmm6) \ 1371 AS2( pslldq xmm7, 4) \ 1372 AS2( movhlps xmm6, xmm4) \ 1373 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \ 1374 AS2( paddd xmm5, xmm7) \ 1375 AS2( movhps QWORD PTR [esp+12], xmm5)\ 1376 AS2( psrlq xmm4, 16) \ 1377 AS2( paddq xmm4, xmm5) \ 1378 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \ 1379 AS2( psrlq xmm4, 3*16) \ 1380 AS2( paddd xmm4, xmm6) \ 1381 AS2( movq QWORD PTR [esp+4], xmm4)\ 1383 #define SSE2_FirstMultiply(i) \ 1384 AS2( movdqa xmm7, [esi+(i)*16])\ 1385 AS2( movdqa xmm5, [edi-(i)*16])\ 1386 AS2( pmuludq xmm5, xmm7) \ 1387 AS2( movdqa xmm4, [ebx])\ 1388 AS2( movdqa xmm6, xmm4) \ 1389 AS2( pand xmm4, xmm5) \ 1390 AS2( psrld xmm5, 16) \ 1391 AS2( pmuludq xmm7, [edx-(i)*16])\ 1392 AS2( pand xmm6, xmm7) \ 1393 AS2( psrld xmm7, 16) 1395 #define Squ_Begin(n) \ 1398 AS2( and esp, 0xfffffff0)\ 1399 AS2( lea edi, [esp-32*n])\ 1400 AS2( sub esp, 32*n+16)\ 1402 AS2( mov esi, edi) \ 1403 AS2( xor edx, edx) \ 1405 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1406 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1407 AS2( movdqa [edi+2*edx], xmm0) \ 1408 AS2( psrlq xmm0, 32) \ 1409 AS2( movdqa [edi+2*edx+16], xmm0) \ 1410 AS2( movdqa [edi+16*n+2*edx], xmm1) \ 1411 AS2( psrlq xmm1, 32) \ 1412 AS2( movdqa [edi+16*n+2*edx+16], xmm1) \ 1414 AS2( cmp edx, 8*(n)) \ 1416 AS2( lea edx, [edi+16*n])\ 1417 SSE2_FirstMultiply(0) \ 1419 #define Squ_Acc(i) \ 1421 AS2( movdqa xmm1, [esi+(i)*16]) \ 1422 AS2( movdqa xmm0, [edi-(i)*16]) \ 1423 AS2( movdqa xmm2, [ebx]) \ 1424 AS2( pmuludq xmm0, xmm1) \ 1425 AS2( pmuludq xmm1, [edx-(i)*16]) \ 1426 AS2( movdqa xmm3, xmm2) \ 1427 AS2( pand xmm2, xmm0) \ 1428 AS2( psrld xmm0, 16) \ 1429 AS2( paddd xmm4, xmm2) \ 1430 AS2( paddd xmm5, xmm0) \ 1431 AS2( pand xmm3, xmm1) \ 1432 AS2( psrld xmm1, 16) \ 1433 AS2( paddd xmm6, xmm3) \ 1434 AS2( paddd xmm7, xmm1) \ 1437 #define Squ_Acc2(i) ASC(call, LSqu##i) 1438 #define Squ_Acc3(i) Squ_Acc2(i) 1439 #define Squ_Acc4(i) Squ_Acc2(i) 1440 #define Squ_Acc5(i) Squ_Acc2(i) 1441 #define Squ_Acc6(i) Squ_Acc2(i) 1442 #define Squ_Acc7(i) Squ_Acc2(i) 1443 #define Squ_Acc8(i) Squ_Acc2(i) 1445 #define SSE2_End(E, n) \ 1446 SSE2_SaveShift(2*(n)-3) \ 1447 AS2( movdqa xmm7, [esi+16]) \ 1448 AS2( movdqa xmm0, [edi]) \ 1449 AS2( pmuludq xmm0, xmm7) \ 1450 AS2( movdqa xmm2, [ebx]) \ 1451 AS2( pmuludq xmm7, [edx]) \ 1452 AS2( movdqa xmm6, xmm2) \ 1453 AS2( pand xmm2, xmm0) \ 1454 AS2( psrld xmm0, 16) \ 1455 AS2( paddd xmm4, xmm2) \ 1456 AS2( paddd xmm5, xmm0) \ 1457 AS2( pand xmm6, xmm7) \ 1458 AS2( psrld xmm7, 16) \ 1459 SSE2_SaveShift(2*(n)-2) \ 1460 SSE2_FinalSave(2*(n)-1) \ 1464 #define Squ_End(n) SSE2_End(SquEpilogue, n) 1465 #define Mul_End(n) SSE2_End(MulEpilogue, n) 1466 #define Top_End(n) SSE2_End(TopEpilogue, n) 1468 #define Squ_Column1(k, i) \ 1469 Squ_SSE2_SaveShift(k) \ 1471 SSE2_FirstMultiply(1)\ 1473 AS2( paddd xmm4, xmm4) \ 1474 AS2( paddd xmm5, xmm5) \ 1475 AS2( movdqa xmm3, [esi]) \ 1476 AS2( movq xmm1, QWORD PTR [esi+8]) \ 1477 AS2( pmuludq xmm1, xmm3) \ 1478 AS2( pmuludq xmm3, xmm3) \ 1479 AS2( movdqa xmm0, [ebx])\ 1480 AS2( movdqa xmm2, xmm0) \ 1481 AS2( pand xmm0, xmm1) \ 1482 AS2( psrld xmm1, 16) \ 1483 AS2( paddd xmm6, xmm0) \ 1484 AS2( paddd xmm7, xmm1) \ 1485 AS2( pand xmm2, xmm3) \ 1486 AS2( psrld xmm3, 16) \ 1487 AS2( paddd xmm6, xmm6) \ 1488 AS2( paddd xmm7, xmm7) \ 1489 AS2( paddd xmm4, xmm2) \ 1490 AS2( paddd xmm5, xmm3) \ 1491 AS2( movq xmm0, QWORD PTR [esp+4])\ 1492 AS2( movq xmm1, QWORD PTR [esp+12])\ 1493 AS2( paddd xmm4, xmm0)\ 1494 AS2( paddd xmm5, xmm1)\ 1496 #define Squ_Column0(k, i) \ 1497 Squ_SSE2_SaveShift(k) \ 1500 SSE2_FirstMultiply(1)\ 1502 AS2( paddd xmm6, xmm6) \ 1503 AS2( paddd xmm7, xmm7) \ 1504 AS2( paddd xmm4, xmm4) \ 1505 AS2( paddd xmm5, xmm5) \ 1506 AS2( movq xmm0, QWORD PTR [esp+4])\ 1507 AS2( movq xmm1, QWORD PTR [esp+12])\ 1508 AS2( paddd xmm4, xmm0)\ 1509 AS2( paddd xmm5, xmm1)\ 1511 #define SSE2_MulAdd45 \ 1512 AS2( movdqa xmm7, [esi]) \ 1513 AS2( movdqa xmm0, [edi]) \ 1514 AS2( pmuludq xmm0, xmm7) \ 1515 AS2( movdqa xmm2, [ebx]) \ 1516 AS2( pmuludq xmm7, [edx]) \ 1517 AS2( movdqa xmm6, xmm2) \ 1518 AS2( pand xmm2, xmm0) \ 1519 AS2( psrld xmm0, 16) \ 1520 AS2( paddd xmm4, xmm2) \ 1521 AS2( paddd xmm5, xmm0) \ 1522 AS2( pand xmm6, xmm7) \ 1523 AS2( psrld xmm7, 16) 1525 #define Mul_Begin(n) \ 1528 AS2( and esp, 0xfffffff0)\ 1529 AS2( sub esp, 48*n+16)\ 1531 AS2( xor edx, edx) \ 1533 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1534 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1535 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \ 1536 AS2( movdqa [esp+20+2*edx], xmm0) \ 1537 AS2( psrlq xmm0, 32) \ 1538 AS2( movdqa [esp+20+2*edx+16], xmm0) \ 1539 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \ 1540 AS2( psrlq xmm1, 32) \ 1541 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \ 1542 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \ 1543 AS2( psrlq xmm2, 32) \ 1544 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \ 1546 AS2( cmp edx, 8*(n)) \ 1548 AS2( lea edi, [esp+20])\ 1549 AS2( lea edx, [esp+20+16*n])\ 1550 AS2( lea esi, [esp+20+32*n])\ 1551 SSE2_FirstMultiply(0) \ 1553 #define Mul_Acc(i) \ 1555 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \ 1556 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \ 1557 AS2( movdqa xmm2, [ebx]) \ 1558 AS2( pmuludq xmm0, xmm1) \ 1559 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1560 AS2( movdqa xmm3, xmm2) \ 1561 AS2( pand xmm2, xmm0) \ 1562 AS2( psrld xmm0, 16) \ 1563 AS2( paddd xmm4, xmm2) \ 1564 AS2( paddd xmm5, xmm0) \ 1565 AS2( pand xmm3, xmm1) \ 1566 AS2( psrld xmm1, 16) \ 1567 AS2( paddd xmm6, xmm3) \ 1568 AS2( paddd xmm7, xmm1) \ 1571 #define Mul_Acc2(i) ASC(call, LMul##i) 1572 #define Mul_Acc3(i) Mul_Acc2(i) 1573 #define Mul_Acc4(i) Mul_Acc2(i) 1574 #define Mul_Acc5(i) Mul_Acc2(i) 1575 #define Mul_Acc6(i) Mul_Acc2(i) 1576 #define Mul_Acc7(i) Mul_Acc2(i) 1577 #define Mul_Acc8(i) Mul_Acc2(i) 1578 #define Mul_Acc9(i) Mul_Acc2(i) 1579 #define Mul_Acc10(i) Mul_Acc2(i) 1580 #define Mul_Acc11(i) Mul_Acc2(i) 1581 #define Mul_Acc12(i) Mul_Acc2(i) 1582 #define Mul_Acc13(i) Mul_Acc2(i) 1583 #define Mul_Acc14(i) Mul_Acc2(i) 1584 #define Mul_Acc15(i) Mul_Acc2(i) 1585 #define Mul_Acc16(i) Mul_Acc2(i) 1587 #define Mul_Column1(k, i) \ 1593 #define Mul_Column0(k, i) \ 1600 #define Bot_Acc(i) \ 1601 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \ 1602 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \ 1603 AS2( pmuludq xmm0, xmm1) \ 1604 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1605 AS2( paddq xmm4, xmm0) \ 1606 AS2( paddd xmm6, xmm1) 1608 #define Bot_SaveAcc(k) \ 1612 AS2( movdqa xmm6, [esi]) \ 1613 AS2( movdqa xmm0, [edi]) \ 1614 AS2( pmuludq xmm0, xmm6) \ 1615 AS2( paddq xmm4, xmm0) \ 1616 AS2( psllq xmm5, 16) \ 1617 AS2( paddq xmm4, xmm5) \ 1618 AS2( pmuludq xmm6, [edx]) 1620 #define Bot_End(n) \ 1621 AS2( movhlps xmm7, xmm6) \ 1622 AS2( paddd xmm6, xmm7) \ 1623 AS2( psllq xmm6, 32) \ 1624 AS2( paddd xmm4, xmm6) \ 1625 AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \ 1629 #define Top_Begin(n) \ 1632 AS2( and esp, 0xfffffff0)\ 1633 AS2( sub esp, 48*n+16)\ 1635 AS2( xor edx, edx) \ 1637 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \ 1638 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \ 1639 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \ 1640 AS2( movdqa [esp+20+2*edx], xmm0) \ 1641 AS2( psrlq xmm0, 32) \ 1642 AS2( movdqa [esp+20+2*edx+16], xmm0) \ 1643 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \ 1644 AS2( psrlq xmm1, 32) \ 1645 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \ 1646 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \ 1647 AS2( psrlq xmm2, 32) \ 1648 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \ 1650 AS2( cmp edx, 8*(n)) \ 1652 AS2( mov eax, esi) \ 1653 AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\ 1654 AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\ 1655 AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\ 1656 AS2( pxor xmm4, xmm4)\ 1657 AS2( pxor xmm5, xmm5) 1659 #define Top_Acc(i) \ 1660 AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \ 1661 AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \ 1662 AS2( psrlq xmm0, 48) \ 1663 AS2( paddd xmm5, xmm0)\ 1665 #define Top_Column0(i) \ 1666 AS2( psllq xmm5, 32) \ 1672 #define Top_Column1(i) \ 1678 AS2( movd xmm0, eax)\ 1679 AS2( movd xmm1, [ecx+4])\ 1680 AS2( psrld xmm1, 16)\ 1681 AS2( pcmpgtd xmm1, xmm0)\ 1682 AS2( psrld xmm1, 31)\ 1683 AS2( paddd xmm4, xmm1)\ 1685 void SSE2_Square4(word *C,
const word *A)
1692 void SSE2_Square8(word *C,
const word *A)
1708 void SSE2_Square16(word *C,
const word *A)
1713 Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1732 void SSE2_Square32(word *C,
const word *A)
1736 Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1770 void SSE2_Multiply4(word *C,
const word *A,
const word *B)
1782 void SSE2_Multiply8(word *C,
const word *A,
const word *B)
1787 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1798 void SSE2_Multiply16(word *C,
const word *A,
const word *B)
1803 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1822 void SSE2_Multiply32(word *C,
const word *A,
const word *B)
1826 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)
1860 void SSE2_MultiplyBottom4(word *C,
const word *A,
const word *B)
1863 Bot_SaveAcc(0) Bot_Acc(2)
1867 void SSE2_MultiplyBottom8(word *C,
const word *A,
const word *B)
1872 Mul_Acc(3) Mul_Acc(2)
1877 Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1881 void SSE2_MultiplyBottom16(word *C,
const word *A,
const word *B)
1886 Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1895 Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
1899 void SSE2_MultiplyBottom32(word *C,
const word *A,
const word *B)
1904 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)
1921 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)
1925 void SSE2_MultiplyTop8(word *C,
const word *A,
const word *B, word L)
1928 Top_Acc(3) Top_Acc(2) Top_Acc(1)
1931 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1940 void SSE2_MultiplyTop16(word *C,
const word *A,
const word *B, word L)
1943 Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
1946 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1959 void SSE2_MultiplyTop32(word *C,
const word *A,
const word *B, word L)
1962 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)
1965 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)
1986 #endif // #if CRYPTOPP_INTEGER_SSE2 1990 typedef int (CRYPTOPP_FASTCALL * PAdd)(
size_t N, word *C,
const word *A,
const word *B);
1991 typedef void (* PMul)(word *C,
const word *A,
const word *B);
1992 typedef void (* PSqu)(word *C,
const word *A);
1993 typedef void (* PMulTop)(word *C,
const word *A,
const word *B, word L);
1995 #if CRYPTOPP_INTEGER_SSE2 1996 static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
1997 static size_t s_recursionLimit = 8;
1999 static const size_t s_recursionLimit = 16;
2002 static PMul s_pMul[9], s_pBot[9];
2003 static PSqu s_pSqu[9];
2004 static PMulTop s_pTop[9];
2006 static void SetFunctionPointers()
2008 s_pMul[0] = &Baseline_Multiply2;
2009 s_pBot[0] = &Baseline_MultiplyBottom2;
2010 s_pSqu[0] = &Baseline_Square2;
2011 s_pTop[0] = &Baseline_MultiplyTop2;
2012 s_pTop[1] = &Baseline_MultiplyTop4;
2014 #if CRYPTOPP_INTEGER_SSE2 2017 #if _MSC_VER != 1200 || defined(NDEBUG) 2025 s_recursionLimit = 32;
2027 s_pMul[1] = &SSE2_Multiply4;
2028 s_pMul[2] = &SSE2_Multiply8;
2029 s_pMul[4] = &SSE2_Multiply16;
2030 s_pMul[8] = &SSE2_Multiply32;
2032 s_pBot[1] = &SSE2_MultiplyBottom4;
2033 s_pBot[2] = &SSE2_MultiplyBottom8;
2034 s_pBot[4] = &SSE2_MultiplyBottom16;
2035 s_pBot[8] = &SSE2_MultiplyBottom32;
2037 s_pSqu[1] = &SSE2_Square4;
2038 s_pSqu[2] = &SSE2_Square8;
2039 s_pSqu[4] = &SSE2_Square16;
2040 s_pSqu[8] = &SSE2_Square32;
2042 s_pTop[2] = &SSE2_MultiplyTop8;
2043 s_pTop[4] = &SSE2_MultiplyTop16;
2044 s_pTop[8] = &SSE2_MultiplyTop32;
2049 s_pMul[1] = &Baseline_Multiply4;
2050 s_pMul[2] = &Baseline_Multiply8;
2052 s_pBot[1] = &Baseline_MultiplyBottom4;
2053 s_pBot[2] = &Baseline_MultiplyBottom8;
2055 s_pSqu[1] = &Baseline_Square4;
2056 s_pSqu[2] = &Baseline_Square8;
2058 s_pTop[2] = &Baseline_MultiplyTop8;
2060 #if !CRYPTOPP_INTEGER_SSE2 2061 s_pMul[4] = &Baseline_Multiply16;
2062 s_pBot[4] = &Baseline_MultiplyBottom16;
2063 s_pSqu[4] = &Baseline_Square16;
2064 s_pTop[4] = &Baseline_MultiplyTop16;
2069 inline int Add(word *C,
const word *A,
const word *B,
size_t N)
2071 #if CRYPTOPP_INTEGER_SSE2 2072 return s_pAdd(N, C, A, B);
2074 return Baseline_Add(N, C, A, B);
2078 inline int Subtract(word *C,
const word *A,
const word *B,
size_t N)
2080 #if CRYPTOPP_INTEGER_SSE2 2081 return s_pSub(N, C, A, B);
2083 return Baseline_Sub(N, C, A, B);
2110 void RecursiveMultiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2112 assert(N>=2 && N%2==0);
2114 if (N <= s_recursionLimit)
2115 s_pMul[N/4](R, A, B);
2118 const size_t N2 = N/2;
2120 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2121 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2123 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2124 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2126 RecursiveMultiply(R2, T2, A1, B1, N2);
2127 RecursiveMultiply(T0, T2, R0, R1, N2);
2128 RecursiveMultiply(R0, T2, A0, B0, N2);
2132 int c2 = Add(R2, R2, R1, N2);
2134 c2 += Add(R1, R2, R0, N2);
2135 c3 += Add(R2, R2, R3, N2);
2138 c3 -= Subtract(R1, R1, T0, N);
2140 c3 += Add(R1, R1, T0, N);
2142 c3 += Increment(R2, N2, c2);
2143 assert (c3 >= 0 && c3 <= 2);
2144 Increment(R3, N2, c3);
2152 void RecursiveSquare(word *R, word *T,
const word *A,
size_t N)
2154 assert(N && N%2==0);
2156 if (N <= s_recursionLimit)
2160 const size_t N2 = N/2;
2162 RecursiveSquare(R0, T2, A0, N2);
2163 RecursiveSquare(R2, T2, A1, N2);
2164 RecursiveMultiply(T0, T2, A0, A1, N2);
2166 int carry = Add(R1, R1, T0, N);
2167 carry += Add(R1, R1, T0, N);
2168 Increment(R3, N2, carry);
2177 void RecursiveMultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2179 assert(N>=2 && N%2==0);
2181 if (N <= s_recursionLimit)
2182 s_pBot[N/4](R, A, B);
2185 const size_t N2 = N/2;
2187 RecursiveMultiply(R, T, A0, B0, N2);
2188 RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2189 Add(R1, R1, T0, N2);
2190 RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2191 Add(R1, R1, T0, N2);
2201 void MultiplyTop(word *R, word *T,
const word *L,
const word *A,
const word *B,
size_t N)
2203 assert(N>=2 && N%2==0);
2205 if (N <= s_recursionLimit)
2206 s_pTop[N/4](R, A, B, L[N-1]);
2209 const size_t N2 = N/2;
2211 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2212 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2214 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2215 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2217 RecursiveMultiply(T0, T2, R0, R1, N2);
2218 RecursiveMultiply(R0, T2, A1, B1, N2);
2223 int c2 = Subtract(T2, L+N2, L, N2);
2227 c2 -= Add(T2, T2, T0, N2);
2228 t = (Compare(T2, R0, N2) == -1);
2229 c3 = t - Subtract(T2, T2, T1, N2);
2233 c2 += Subtract(T2, T2, T0, N2);
2234 t = (Compare(T2, R0, N2) == -1);
2235 c3 = t + Add(T2, T2, T1, N2);
2240 c3 += Increment(T2, N2, c2);
2242 c3 -= Decrement(T2, N2, -c2);
2243 c3 += Add(R0, T2, R1, N2);
2245 assert (c3 >= 0 && c3 <= 2);
2246 Increment(R1, N2, c3);
2250 inline void Multiply(word *R, word *T,
const word *A,
const word *B,
size_t N)
2252 RecursiveMultiply(R, T, A, B, N);
2255 inline void Square(word *R, word *T,
const word *A,
size_t N)
2257 RecursiveSquare(R, T, A, N);
2260 inline void MultiplyBottom(word *R, word *T,
const word *A,
const word *B,
size_t N)
2262 RecursiveMultiplyBottom(R, T, A, B, N);
2270 void AsymmetricMultiply(word *R, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2277 Multiply(R, T, A, B, NA);
2288 assert(NB % NA == 0);
2295 SetWords(R, 0, NB+2);
2298 CopyWords(R, B, NB);
2299 R[NB] = R[NB+1] = 0;
2302 R[NB] = LinearMultiply(R, B, A[0], NB);
2311 Multiply(R, T, A, B, NA);
2312 CopyWords(T+2*NA, R+NA, NA);
2314 for (i=2*NA; i<NB; i+=2*NA)
2315 Multiply(T+NA+i, T, A, B+i, NA);
2316 for (i=NA; i<NB; i+=2*NA)
2317 Multiply(R+i, T, A, B+i, NA);
2321 for (i=0; i<NB; i+=2*NA)
2322 Multiply(R+i, T, A, B+i, NA);
2323 for (i=NA; i<NB; i+=2*NA)
2324 Multiply(T+NA+i, T, A, B+i, NA);
2327 if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2328 Increment(R+NB, NA);
2335 void RecursiveInverseModPower2(word *R, word *T,
const word *A,
size_t N)
2339 T[0] = AtomicInverseModPower2(A[0]);
2341 s_pBot[0](T+2, T, A);
2342 TwosComplement(T+2, 2);
2343 Increment(T+2, 2, 2);
2344 s_pBot[0](R, T, T+2);
2348 const size_t N2 = N/2;
2349 RecursiveInverseModPower2(R0, T0, A0, N2);
2351 SetWords(T0+1, 0, N2-1);
2352 MultiplyTop(R1, T1, T0, R0, A0, N2);
2353 MultiplyBottom(T0, T1, R0, A1, N2);
2354 Add(T0, R1, T0, N2);
2355 TwosComplement(T0, N2);
2356 MultiplyBottom(R1, T1, R0, T0, N2);
2366 void MontgomeryReduce(word *R, word *T, word *X,
const word *M,
const word *U,
size_t N)
2369 MultiplyBottom(R, T, X, U, N);
2370 MultiplyTop(T, T+N, X, R, M, N);
2371 word borrow = Subtract(T, X+N, T, N);
2373 word carry = Add(T+N, T, M, N);
2374 assert(carry | !borrow);
2375 CRYPTOPP_UNUSED(carry), CRYPTOPP_UNUSED(borrow);
2376 CopyWords(R, T + ((0-borrow) & N), N);
2378 const word u = 0-U[0];
2380 for (
size_t i=0; i<N; i++)
2382 const word t = u * X[i];
2384 for (
size_t j=0; j<N; j+=2)
2386 MultiplyWords(p, t, M[j]);
2387 Acc2WordsBy1(p, X[i+j]);
2389 X[i+j] = LowWord(p);
2391 MultiplyWords(p, t, M[j+1]);
2392 Acc2WordsBy1(p, X[i+j+1]);
2394 X[i+j+1] = LowWord(p);
2398 if (Increment(X+N+i, N-i, c))
2399 while (!Subtract(X+N, X+N, M, N)) {}
2402 memcpy(R, X+N, N*WORD_SIZE);
2404 __m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2405 for (
size_t i=0; i<N; i++)
2407 __m64 t = _mm_cvtsi32_si64(X[i]);
2408 t = _mm_mul_su32(t, u);
2409 __m64 c = _mm_setzero_si64();
2410 for (
size_t j=0; j<N; j+=2)
2412 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2413 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2414 c = _mm_add_si64(c, p);
2415 X[i+j] = _mm_cvtsi64_si32(c);
2416 c = _mm_srli_si64(c, 32);
2417 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2418 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2419 c = _mm_add_si64(c, p);
2420 X[i+j+1] = _mm_cvtsi64_si32(c);
2421 c = _mm_srli_si64(c, 32);
2424 if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2425 while (!Subtract(X+N, X+N, M, N)) {}
2428 memcpy(R, X+N, N*WORD_SIZE);
2440 void HalfMontgomeryReduce(word *R, word *T,
const word *X,
const word *M,
const word *U,
const word *V,
size_t N)
2442 assert(N%2==0 && N>=4);
2454 const size_t N2 = N/2;
2455 Multiply(T0, T2, V0, X3, N2);
2456 int c2 = Add(T0, T0, X0, N);
2457 MultiplyBottom(T3, T2, T0, U, N2);
2458 MultiplyTop(T2, R, T0, T3, M0, N2);
2459 c2 -= Subtract(T2, T1, T2, N2);
2460 Multiply(T0, R, T3, M1, N2);
2461 c2 -= Subtract(T0, T2, T0, N2);
2462 int c3 = -(int)Subtract(T1, X2, T1, N2);
2463 Multiply(R0, T2, V1, X3, N2);
2464 c3 += Add(R, R, T, N);
2467 c3 += Increment(R1, N2);
2469 c3 -= Decrement(R1, N2, -c2);
2471 assert(c3>=-1 && c3<=1);
2473 Subtract(R, R, M, N);
2567 static inline void AtomicDivide(word *Q,
const word *A,
const word *B)
2570 DWord q = DivideFourWordsByTwo<word, DWord>(T,
DWord(A[0], A[1]),
DWord(A[2], A[3]),
DWord(B[0], B[1]));
2571 Q[0] = q.GetLowHalf();
2572 Q[1] = q.GetHighHalf();
2578 assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2582 assert(memcmp(P, A, 4*WORD_SIZE)==0);
2588 static void CorrectQuotientEstimate(word *R, word *T, word *Q,
const word *B,
size_t N)
2590 assert(N && N%2==0);
2592 AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2594 word borrow = Subtract(R, R, T, N+2);
2595 assert(!borrow && !R[N+1]);
2596 CRYPTOPP_UNUSED(borrow);
2598 while (R[N] || Compare(R, B, N) >= 0)
2600 R[N] -= Subtract(R, R, B, N);
2601 Q[1] += (++Q[0]==0);
2602 assert(Q[0] || Q[1]);
2612 void Divide(word *R, word *Q, word *T,
const word *A,
size_t NA,
const word *B,
size_t NB)
2614 assert(NA && NB && NA%2==0 && NB%2==0);
2615 assert(B[NB-1] || B[NB-2]);
2620 word *
const TB=T+NA+2;
2621 word *
const TP=T+NA+2+NB;
2624 unsigned shiftWords = (B[NB-1]==0);
2625 TB[0] = TB[NB-1] = 0;
2626 CopyWords(TB+shiftWords, B, NB-shiftWords);
2627 unsigned shiftBits = WORD_BITS -
BitPrecision(TB[NB-1]);
2628 assert(shiftBits < WORD_BITS);
2629 ShiftWordsLeftByBits(TB, NB, shiftBits);
2632 TA[0] = TA[NA] = TA[NA+1] = 0;
2633 CopyWords(TA+shiftWords, A, NA);
2634 ShiftWordsLeftByBits(TA, NA+2, shiftBits);
2636 if (TA[NA+1]==0 && TA[NA] <= 1)
2638 Q[NA-NB+1] = Q[NA-NB] = 0;
2639 while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
2641 TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
2648 assert(Compare(TA+NA-NB, TB, NB) < 0);
2652 BT[0] = TB[NB-2] + 1;
2653 BT[1] = TB[NB-1] + (BT[0]==0);
2656 for (
size_t i=NA-2; i>=NB; i-=2)
2658 AtomicDivide(Q+i-NB, TA+i-2, BT);
2659 CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
2663 CopyWords(R, TA+shiftWords, NB);
2664 ShiftWordsRightByBits(R, NB, shiftBits);
2667 static inline size_t EvenWordCount(
const word *X,
size_t N)
2669 while (N && X[N-2]==0 && X[N-1]==0)
2680 unsigned int AlmostInverse(word *R, word *T,
const word *A,
size_t NA,
const word *M,
size_t N)
2682 assert(NA<=N && N && N%2==0);
2688 size_t bcLen=2, fgLen=EvenWordCount(M, N);
2692 SetWords(T, 0, 3*N);
2694 CopyWords(f, A, NA);
2702 if (EvenWordCount(f, fgLen)==0)
2708 ShiftWordsRightByWords(f, fgLen, 1);
2709 bcLen += 2 * (c[bcLen-1] != 0);
2711 ShiftWordsLeftByWords(c, bcLen, 1);
2721 if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0)
2724 Subtract(R, M, b, N);
2730 ShiftWordsRightByBits(f, fgLen, i);
2731 t = ShiftWordsLeftByBits(c, bcLen, i);
2733 bcLen += 2 * (t!=0);
2736 bool swap = Compare(f, g, fgLen)==-1;
2741 fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]);
2743 Subtract(f, f, g, fgLen);
2744 t = Add(b, b, c, bcLen);
2755 void DivideByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2762 ShiftWordsRightByBits(R, N, 1);
2765 word carry = Add(R, R, M, N);
2766 ShiftWordsRightByBits(R, N, 1);
2767 R[N-1] += carry<<(WORD_BITS-1);
2776 void MultiplyByPower2Mod(word *R,
const word *A,
size_t k,
const word *M,
size_t N)
2781 if (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0)
2782 Subtract(R, R, M, N);
2787 InitializeInteger::InitializeInteger()
2789 if (!g_pAssignIntToInteger)
2791 SetFunctionPointers();
2792 g_pAssignIntToInteger = AssignIntToInteger;
2796 static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
2798 static inline size_t RoundupSize(
size_t n)
2801 return RoundupSizeTable[n];
2812 : reg(2), sign(POSITIVE)
2814 reg[0] = reg[1] = 0;
2818 : reg(RoundupSize(t.
WordCount())), sign(t.sign)
2820 CopyWords(reg, t.reg, reg.
size());
2826 reg[0] = word(value);
2827 reg[1] = word(SafeRightShift<WORD_BITS>(value));
2840 reg[0] = word(value);
2841 reg[1] = word(SafeRightShift<WORD_BITS>((
unsigned long)value));
2856 unsigned long value = (
unsigned long)reg[0];
2857 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2860 return (
signed long)value >= 0;
2862 return -(
signed long)value < 0;
2869 unsigned long value = (
unsigned long)reg[0];
2870 value += SafeLeftShift<WORD_BITS, unsigned long>((
unsigned long)reg[1]);
2871 return sign==
POSITIVE ? value : -(
signed long)value;
2876 Decode(encodedInteger, byteCount, s);
2881 Decode(encodedInteger, byteCount, s);
2896 if (!
Randomize(rng, min, max, rnType, equiv, mod))
2931 bool Integer::operator!()
const 2933 return IsNegative() ?
false : (reg[0]==0 &&
WordCount()==0);
2940 if (reg.size() != t.reg.
size() || t.reg[t.reg.
size()/2] == 0)
2942 CopyWords(reg, t.reg, reg.
size());
2950 if (n/WORD_BITS >= reg.size())
2953 return bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1);
2961 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
2965 if (n/WORD_BITS < reg.size())
2966 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
2972 if (n/WORD_SIZE >= reg.size())
2975 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
2981 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
2982 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
2988 assert(n <=
sizeof(v)*8);
2989 for (
unsigned int j=0; j<n; j++)
2990 v |= lword(
GetBit(i+j)) << j;
2994 Integer Integer::operator-()
const 3001 Integer Integer::AbsoluteValue()
const 3011 std::swap(sign, a.sign);
3015 : reg(RoundupSize(length)), sign(
POSITIVE)
3018 SetWords(reg+1, 0, reg.size()-1);
3022 static Integer StringToInteger(
const T *str)
3027 unsigned int length;
3028 for (length = 0; str[length] != 0; length++) {}
3035 switch (str[length-1])
3053 if (length > 2 && str[0] ==
'0' && str[1] ==
'x')
3056 for (
unsigned i=0; i<length; i++)
3060 if (str[i] >=
'0' && str[i] <=
'9')
3061 digit = str[i] -
'0';
3062 else if (str[i] >=
'A' && str[i] <=
'F')
3063 digit = str[i] -
'A' + 10;
3064 else if (str[i] >=
'a' && str[i] <=
'f')
3065 digit = str[i] -
'a' + 10;
3085 *
this = StringToInteger(str);
3091 *
this = StringToInteger(str);
3096 return (
unsigned int)CountWords(reg, reg.
size());
3103 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
3112 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
3120 Decode(store, inputLen, s);
3131 while (inputLen>0 && (sign==
POSITIVE ? b==0 : b==0xff))
3139 const size_t size = RoundupSize(
BytesToWords(inputLen));
3143 for (
size_t i=inputLen; i > 0; i--)
3146 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
3151 for (
size_t i=inputLen; i<reg.
size()*WORD_SIZE; i++)
3152 reg[i/WORD_SIZE] |= word(0xff) << (i%WORD_SIZE)*8;
3153 TwosComplement(reg, reg.
size());
3162 if (NotNegative() && (
GetByte(outputLen-1) & 0x80))
3164 if (IsNegative() && *
this < -
Power2(outputLen*8-1))
3171 assert(output && outputLen);
3173 Encode(sink, outputLen, signedness);
3178 if (signedness ==
UNSIGNED || NotNegative())
3180 for (
size_t i=outputLen; i > 0; i--)
3207 if (!dec.IsDefiniteLength() || dec.
MaxRetrievable() < dec.RemainingLength())
3223 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
3237 word16 bitCount = word16(
BitCount());
3241 return 2 + byteCount;
3260 const size_t nbytes = nbits/8 + 1;
3264 buf[0] = (byte)
Crop(buf[0], nbits % 8);
3274 const unsigned int nbits = range.
BitCount();
3280 while (*
this > range);
3287 return GenerateRandomNoThrow(rng,
MakeParameters(
"Min", min)(
"Max", max)(
"RandomNumberType", rnType)(
"EquivalentTo", equiv)(
"Mod", mod));
3293 KDF2_RNG(
const byte *seed,
size_t seedSize)
3294 : m_counter(0), m_counterAndSeed(seedSize + 4)
3296 memcpy(m_counterAndSeed + 4, seed, seedSize);
3301 PutWord(
false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3329 if (equiv.IsNegative() || equiv >= mod)
3330 throw InvalidArgument(
"Integer: invalid EquivalentTo and/or Mod argument");
3349 bq.
Get(finalSeed, finalSeed.size());
3350 kdf2Rng.reset(
new KDF2_RNG(finalSeed.begin(), finalSeed.size()));
3361 Integer min1 = min + (equiv-min)%mod;
3382 if (
FirstPrime(first, max, equiv, mod, pSelector))
3386 if (!
FirstPrime(first, max, equiv, mod, pSelector))
3394 if (
FirstPrime(*
this,
STDMIN(*
this+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector))
3404 std::istream& operator>>(std::istream& in,
Integer &a)
3407 unsigned int length = 0;
3416 if (length >= str.
size())
3417 str.
Grow(length + 16);
3419 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==
'.'));
3423 str[length-1] =
'\0';
3429 std::ostream& operator<<(std::ostream& out,
const Integer &a)
3432 const long f = out.flags() & std::ios::basefield;
3437 case std::ios::oct :
3442 case std::ios::hex :
3464 static const char upper[]=
"0123456789ABCDEF";
3465 static const char lower[]=
"0123456789abcdef";
3467 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3486 return out << suffix;
3489 Integer& Integer::operator++()
3493 if (Increment(reg, reg.size()))
3495 reg.CleanGrow(2*reg.size());
3496 reg[reg.size()/2]=1;
3501 word borrow = Decrement(reg, reg.size());
3503 CRYPTOPP_UNUSED(borrow);
3511 Integer& Integer::operator--()
3515 if (Increment(reg, reg.size()))
3517 reg.CleanGrow(2*reg.size());
3518 reg[reg.size()/2]=1;
3523 if (Decrement(reg, reg.size()))
3533 carry = Add(sum.reg, a.reg, b.reg, a.reg.
size());
3534 else if (a.reg.
size() > b.reg.
size())
3536 carry = Add(sum.reg, a.reg, b.reg, b.reg.
size());
3537 CopyWords(sum.reg+b.reg.
size(), a.reg+b.reg.
size(), a.reg.
size()-b.reg.
size());
3538 carry = Increment(sum.reg+b.reg.
size(), a.reg.
size()-b.reg.
size(), carry);
3542 carry = Add(sum.reg, a.reg, b.reg, a.reg.
size());
3543 CopyWords(sum.reg+a.reg.
size(), b.reg+a.reg.
size(), b.reg.
size()-a.reg.
size());
3544 carry = Increment(sum.reg+a.reg.
size(), b.reg.
size()-a.reg.
size(), carry);
3550 sum.reg[sum.reg.
size()/2] = 1;
3564 if (
Compare(a.reg, b.reg, aSize) >= 0)
3566 Subtract(diff.reg, a.reg, b.reg, aSize);
3571 Subtract(diff.reg, b.reg, a.reg, aSize);
3575 else if (aSize > bSize)
3577 word borrow = Subtract(diff.reg, a.reg, b.reg, bSize);
3578 CopyWords(diff.reg+bSize, a.reg+bSize, aSize-bSize);
3579 borrow = Decrement(diff.reg+bSize, aSize-bSize, borrow);
3585 word borrow = Subtract(diff.reg, b.reg, a.reg, aSize);
3586 CopyWords(diff.reg+aSize, b.reg+aSize, bSize-aSize);
3587 borrow = Decrement(diff.reg+aSize, bSize-aSize, borrow);
3594 template <
class T>
inline const T& STDMAX2(
const T& a,
const T& b)
3596 return a < b ? b : a;
3601 Integer sum((word)0, STDMAX2(reg.size(), b.reg.
size()));
3604 if (b.NotNegative())
3605 PositiveAdd(sum, *
this, b);
3607 PositiveSubtract(sum, *
this, b);
3611 if (b.NotNegative())
3612 PositiveSubtract(sum, b, *
this);
3615 PositiveAdd(sum, *
this, b);
3624 reg.CleanGrow(t.reg.
size());
3627 if (t.NotNegative())
3628 PositiveAdd(*
this, *
this, t);
3630 PositiveSubtract(*
this, *
this, t);
3634 if (t.NotNegative())
3635 PositiveSubtract(*
this, t, *
this);
3638 PositiveAdd(*
this, *
this, t);
3647 Integer diff((word)0, STDMAX2(reg.size(), b.reg.
size()));
3650 if (b.NotNegative())
3651 PositiveSubtract(diff, *
this, b);
3653 PositiveAdd(diff, *
this, b);
3657 if (b.NotNegative())
3659 PositiveAdd(diff, *
this, b);
3663 PositiveSubtract(diff, b, *
this);
3670 reg.CleanGrow(t.reg.
size());
3673 if (t.NotNegative())
3674 PositiveSubtract(*
this, *
this, t);
3676 PositiveAdd(*
this, *
this, t);
3680 if (t.NotNegative())
3682 PositiveAdd(*
this, *
this, t);
3686 PositiveSubtract(*
this, t, *
this);
3691 Integer& Integer::operator<<=(
size_t n)
3694 const size_t shiftWords = n / WORD_BITS;
3695 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3697 reg.CleanGrow(RoundupSize(wordCount+
BitsToWords(n)));
3698 ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords);
3699 ShiftWordsLeftByBits(reg+shiftWords, wordCount+
BitsToWords(shiftBits), shiftBits);
3703 Integer& Integer::operator>>=(
size_t n)
3706 const size_t shiftWords = n / WORD_BITS;
3707 const unsigned int shiftBits = (
unsigned int)(n % WORD_BITS);
3709 ShiftWordsRightByWords(reg, wordCount, shiftWords);
3710 if (wordCount > shiftWords)
3711 ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits);
3719 size_t aSize = RoundupSize(a.
WordCount());
3720 size_t bSize = RoundupSize(b.
WordCount());
3722 product.reg.
CleanNew(RoundupSize(aSize+bSize));
3726 AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
3731 PositiveMultiply(product, a, b);
3733 if (a.NotNegative() != b.NotNegative())
3740 Multiply(product, *
this, b);
3786 remainder.reg.
CleanNew(RoundupSize(bSize));
3788 quotient.reg.
CleanNew(RoundupSize(aSize-bSize+2));
3792 Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
3797 PositiveDivide(remainder, quotient, dividend, divisor);
3799 if (dividend.IsNegative())
3802 if (remainder.NotZero())
3805 remainder = divisor.AbsoluteValue() - remainder;
3809 if (divisor.IsNegative())
3821 r.reg.
resize(RoundupSize(wordCount));
3822 CopyWords(r.reg, a.reg, wordCount);
3823 SetWords(r.reg+wordCount, 0, r.reg.
size()-wordCount);
3824 if (n % WORD_BITS != 0)
3825 r.reg[wordCount-1] %= (word(1) << (n % WORD_BITS));
3830 CopyWords(r.reg, a.reg, r.reg.
size());
3834 if (a.IsNegative() && r.NotZero())
3862 if ((divisor & (divisor-1)) == 0)
3865 remainder = dividend.reg[0] & (divisor-1);
3870 quotient.reg.
CleanNew(RoundupSize(i));
3874 quotient.reg[i] =
DWord(dividend.reg[i], remainder) / divisor;
3875 remainder =
DWord(dividend.reg[i], remainder) % divisor;
3878 if (dividend.NotNegative())
3886 remainder = divisor - remainder;
3891 Integer Integer::DividedBy(word b)
const 3908 if ((divisor & (divisor-1)) == 0)
3909 remainder = reg[0] & (divisor-1);
3919 remainder = sum % divisor;
3925 remainder =
DWord(reg[i], remainder) % divisor;
3929 if (IsNegative() && remainder)
3930 remainder = divisor - remainder;
3938 sign =
Sign(1-sign);
3941 int Integer::PositiveCompare(
const Integer& t)
const 3946 return CryptoPP::Compare(reg, t.reg, size);
3948 return size > tSize ? 1 : -1;
3955 if (t.NotNegative())
3956 return PositiveCompare(t);
3962 if (t.NotNegative())
3965 return -PositiveCompare(t);
3976 assert(y*y >= *
this);
3981 y = (x + *
this/x) >> 1;
3995 return (
WordCount() == 1) && (reg[0] == 1);
4011 return mr.Exponentiate(x, e);
4021 assert(m.NotNegative());
4034 return !u ?
Zero() : (m*(*
this-u)+1)/(*this);
4039 unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.
size());
4040 DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.
size());
4046 word g0 = mod, g1 = *
this % mod;
4047 word v0 = 0, v1 = 1;
4075 if (oid != ASN1::prime_field())
4077 m_modulus.BERDecode(seq);
4079 m_result.reg.resize(m_modulus.reg.size());
4085 ASN1::prime_field().DEREncode(seq);
4086 m_modulus.DEREncode(seq);
4092 a.DEREncodeAsOctetString(out, MaxElementByteLength());
4097 a.BERDecodeAsOctetString(in, MaxElementByteLength());
4102 if (a.reg.
size()==m_modulus.reg.size())
4104 CryptoPP::DivideByPower2Mod(m_result.reg.begin(), a.reg, 1, m_modulus.reg, a.reg.
size());
4108 return m_result1 = (a.IsEven() ? (a >> 1) : ((a+m_modulus) >> 1));
4113 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4115 if (CryptoPP::Add(m_result.reg.begin(), a.reg, b.reg, a.reg.
size())
4116 ||
Compare(m_result.reg, m_modulus.reg, a.reg.
size()) >= 0)
4118 CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.
size());
4125 if (m_result1 >= m_modulus)
4126 m_result1 -= m_modulus;
4133 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4135 if (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.
size())
4136 ||
Compare(a.reg, m_modulus.reg, a.reg.
size()) >= 0)
4138 CryptoPP::Subtract(a.reg, a.reg, m_modulus.reg, a.reg.
size());
4153 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4155 if (CryptoPP::Subtract(m_result.reg.begin(), a.reg, b.reg, a.reg.
size()))
4156 CryptoPP::Add(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.
size());
4162 if (m_result1.IsNegative())
4163 m_result1 += m_modulus;
4170 if (a.reg.
size()==m_modulus.reg.size() && b.reg.
size()==m_modulus.reg.size())
4172 if (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.
size()))
4173 CryptoPP::Add(a.reg, a.reg, m_modulus.reg, a.reg.
size());
4185 const Integer& ModularArithmetic::Inverse(
const Integer &a)
const 4190 CopyWords(m_result.reg.begin(), m_modulus.reg, m_modulus.reg.size());
4191 if (CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, a.reg, a.reg.
size()))
4192 Decrement(m_result.reg.begin()+a.reg.
size(), m_modulus.reg.size()-a.reg.
size());
4199 if (m_modulus.IsOdd())
4202 return dr.ConvertOut(dr.CascadeExponentiate(dr.ConvertIn(x), e1, dr.ConvertIn(y), e2));
4208 void ModularArithmetic::SimultaneousExponentiate(
Integer *results,
const Integer &base,
const Integer *exponents,
unsigned int exponentsCount)
const 4210 if (m_modulus.IsOdd())
4213 dr.SimultaneousExponentiate(results, dr.ConvertIn(base), exponents, exponentsCount);
4214 for (
unsigned int i=0; i<exponentsCount; i++)
4215 results[i] = dr.ConvertOut(results[i]);
4221 MontgomeryRepresentation::MontgomeryRepresentation(
const Integer &m)
4223 m_u((word)0, m_modulus.reg.size()),
4224 m_workspace(5*m_modulus.reg.size())
4226 if (!m_modulus.IsOdd())
4227 throw InvalidArgument(
"MontgomeryRepresentation: Montgomery representation requires an odd modulus");
4229 RecursiveInverseModPower2(m_u.reg, m_workspace, m_modulus.reg, m_modulus.reg.size());
4234 word *
const T = m_workspace.begin();
4235 word *
const R = m_result.reg.begin();
4236 const size_t N = m_modulus.reg.size();
4237 assert(a.reg.
size()<=N && b.reg.
size()<=N);
4239 AsymmetricMultiply(T, T+2*N, a.reg, a.reg.
size(), b.reg, b.reg.
size());
4241 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4245 const Integer& MontgomeryRepresentation::Square(
const Integer &a)
const 4247 word *
const T = m_workspace.begin();
4248 word *
const R = m_result.reg.begin();
4249 const size_t N = m_modulus.reg.size();
4250 assert(a.reg.
size()<=N);
4252 CryptoPP::Square(T, T+2*N, a.reg, a.reg.
size());
4253 SetWords(T+2*a.reg.
size(), 0, 2*N-2*a.reg.
size());
4254 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4258 Integer MontgomeryRepresentation::ConvertOut(
const Integer &a)
const 4260 word *
const T = m_workspace.begin();
4261 word *
const R = m_result.reg.begin();
4262 const size_t N = m_modulus.reg.size();
4263 assert(a.reg.
size()<=N);
4265 CopyWords(T, a.reg, a.reg.
size());
4266 SetWords(T+a.reg.
size(), 0, 2*N-a.reg.
size());
4267 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4271 const Integer& MontgomeryRepresentation::MultiplicativeInverse(
const Integer &a)
const 4274 word *
const T = m_workspace.begin();
4275 word *
const R = m_result.reg.begin();
4276 const size_t N = m_modulus.reg.size();
4277 assert(a.reg.
size()<=N);
4279 CopyWords(T, a.reg, a.reg.
size());
4280 SetWords(T+a.reg.
size(), 0, 2*N-a.reg.
size());
4281 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4282 unsigned k = AlmostInverse(R, T, R, N, m_modulus.reg, N);
4287 DivideByPower2Mod(R, R, k-N*WORD_BITS, m_modulus.reg, N);
4289 MultiplyByPower2Mod(R, R, N*WORD_BITS-k, m_modulus.reg, N);
4296 template <> CRYPTOPP_DLL
4300 static const unsigned int BIT_32 = (1U << 31);
4301 const bool UPPER = !!(base & BIT_32);
4302 static const unsigned int BIT_31 = (1U << 30);
4303 const bool BASE = !!(base & BIT_31);
4305 const char CH = UPPER ?
'A' :
'a';
4306 base &= ~(BIT_32|BIT_31);
4307 assert(base >= 2 && base <= 32);
4312 bool negative =
false, zero =
false;
4313 if (value.IsNegative())
4330 s[i++]=char((digit < 10 ?
'0' : (CH - 10)) + digit);
4335 result.reserve(i+2);
4350 else if (base == 16)
4362 template <> CRYPTOPP_DLL
4366 static const unsigned int HIGH_BIT = (1U << 31);
4367 const char CH = !!(base & HIGH_BIT) ?
'A' :
'a';
4377 unsigned long long digit = value % base;
4378 result = char((digit < 10 ?
'0' : (CH - 10)) + digit) + result;
4386 #if WORKAROUND_ARMEL_BUG 4387 # 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.