Crypto++ 7.0 Free C++ class library of cryptographic schemes

integer.cpp
1 // integer.cpp - originally written and placed in the public domain by Wei Dai
2 // contains public domain code contributed by Alister Lee and Leonard Janke
3
4 // Notes by JW: The Integer class needs to do two things. First, it needs
5 // to set function pointers on some platforms, like X86 and X64. The
6 // function pointers select a fast multiply and addition based on the cpu.
7 // Second, it wants to create Integer::Zero(), Integer::One() and
8 // Integer::Two().
9 // The function pointers are initialized in the InitializeInteger class by
10 // calling SetFunctionPointers(). The call to SetFunctionPointers() is
11 // guarded to run once using a double-checked pattern. We don't use C++
12 // std::call_once due to bad interactions between libstdc++, glibc and
13 // pthreads. The bad interactions were causing crashes for us on platforms
14 // like Sparc and PowerPC. Since we are only setting function pointers we
15 // don't have to worry about leaking memory. The worst case seems to be the
16 // pointers gets written twice until the init flag is set and visible to
17 // all threads.
18 // For Integer::Zero(), Integer::One() and Integer::Two(), we use one of three
19 // strategies. First, if initialization priorities are available then we use
20 // them. Initialization priorities are init_priority() on Linux and init_seg()
21 // on Windows. AIX, OS X and several other platforms lack them. Initialization
22 // priorities are platform specific but they are also the most trouble free
23 // with determisitic destruction.
24 // Second, if C++11 dynamic initialization is available, then we use it. After
25 // the std::call_once fiasco we dropped the priority dynamic initialization
26 // to avoid unknown troubles platforms that are tested less frequently. In
27 // addition Microsoft platforms mostly do not provide dynamic initialization.
28 // The MSDN docs claim they do but they don't in practice because we need
29 // Visual Studio 2017 and Windows 10 or above.
30 // Third, we fall back to Wei's original code of a Singleton. Wei's original
31 // code was much simpler. It simply used the Singleton pattern, but it always
32 // produced memory findings on some platforms. The Singleton generates memory
33 // findings because it uses a Create On First Use pattern (a dumb Nifty
34 // Counter) and the compiler had to be smart enough to fold them to return
35 // the same object. Unix and Linux compilers do a good job of folding objects,
36 // but Microsoft compilers do a rather poor job for some versions of the
37 // compiler.
38 // Another problem with the Singleton is resource destruction requires running
39 // resource acquisition in reverse. For resources provided through the
40 // Singletons, there is no way to express the dependency order to safely
41 // destroy resources. (That's one of the problems C++11 dynamic
42 // intitialization with concurrent execution is supposed to solve).
43 // The final problem with Singletons is resource/memory exhaustion in languages
44 // like Java and .Net. Java and .Net load and unload a native DLL hundreds or
45 // thousands of times during the life of a program. Each load produces a
46 // memory leak and they can add up quickly. If they library is being used in
47 // Java or .Net then Singleton must be avoided at all costs.
48
49 #include "pch.h"
50 #include "config.h"
51
52 #ifndef CRYPTOPP_IMPORTS
53
54 #include "integer.h"
55 #include "secblock.h"
56 #include "modarith.h"
57 #include "nbtheory.h"
58 #include "smartptr.h"
59 #include "algparam.h"
60 #include "filters.h"
61 #include "stdcpp.h"
62 #include "asn.h"
63 #include "oids.h"
64 #include "words.h"
65 #include "pubkey.h" // for P1363_KDF2
66 #include "sha.h"
67 #include "cpu.h"
68 #include "misc.h"
69
70 #include <iostream>
71
72 #if (_MSC_VER >= 1400) && !defined(_M_ARM)
73 #include <intrin.h>
74 #endif
75
76 #ifdef __DECCXX
77 #include <c_asm.h>
78 #endif
79
80 // "Error: The operand ___LKDB cannot be assigned to", http://github.com/weidai11/cryptopp/issues/188
81 #if (__SUNPRO_CC >= 0x5130)
82 # define MAYBE_CONST
83 # define MAYBE_UNCONST_CAST(x) const_cast<word*>(x)
84 #else
85 # define MAYBE_CONST const
86 # define MAYBE_UNCONST_CAST(x) x
87 #endif
88
89 // "Inline assembly operands don't work with .intel_syntax",
90 // http://llvm.org/bugs/show_bug.cgi?id=24232
91 #if CRYPTOPP_BOOL_X32 || defined(CRYPTOPP_DISABLE_MIXED_ASM)
92 # undef CRYPTOPP_X86_ASM_AVAILABLE
93 # undef CRYPTOPP_X32_ASM_AVAILABLE
94 # undef CRYPTOPP_X64_ASM_AVAILABLE
95 # undef CRYPTOPP_SSE2_ASM_AVAILABLE
96 # undef CRYPTOPP_SSSE3_ASM_AVAILABLE
97 #else
98 # define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_SSE2_ASM_AVAILABLE && (CRYPTOPP_BOOL_X86))
99 #endif
100
101 // ***************** C++ Static Initialization ********************
102
103 NAMESPACE_BEGIN(CryptoPP)
104
105 // Function body near the middle of the file
106 static void SetFunctionPointers();
107
108 // Use a double-checked pattern. We are not leaking anything so it
109 // does not matter if a pointer is written twice during a race.
110 // Avoid std::call_once due to too many problems on platforms like
111 // Solaris and Sparc. Also see
112 // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=66146 and
113 // http://github.com/weidai11/cryptopp/issues/707.
114 InitializeInteger::InitializeInteger()
115 {
116 static bool s_flag;
117 MEMORY_BARRIER();
118 if (s_flag == false)
119 {
120 SetFunctionPointers();
121 s_flag = true;
122 MEMORY_BARRIER();
123 }
124 }
125
126 template <long i>
127 struct NewInteger
128 {
129 Integer * operator()() const
130 {
131 return new Integer(i);
132 }
133 };
134
135 // ***************** Library code ********************
136
137 inline static int Compare(const word *A, const word *B, size_t N)
138 {
139 while (N--)
140 if (A[N] > B[N])
141 return 1;
142 else if (A[N] < B[N])
143 return -1;
144
145 return 0;
146 }
147
148 inline static int Increment(word *A, size_t N, word B=1)
149 {
150 CRYPTOPP_ASSERT(N);
151 word t = A[0];
152 A[0] = t+B;
153 if (A[0] >= t)
154 return 0;
155 for (unsigned i=1; i<N; i++)
156 if (++A[i])
157 return 0;
158 return 1;
159 }
160
161 inline static int Decrement(word *A, size_t N, word B=1)
162 {
163 CRYPTOPP_ASSERT(N);
164 word t = A[0];
165 A[0] = t-B;
166 if (A[0] <= t)
167 return 0;
168 for (unsigned i=1; i<N; i++)
169 if (A[i]--)
170 return 0;
171 return 1;
172 }
173
174 static void TwosComplement(word *A, size_t N)
175 {
176 Decrement(A, N);
177 for (unsigned i=0; i<N; i++)
178 A[i] = ~A[i];
179 }
180
181 static word AtomicInverseModPower2(word A)
182 {
183 CRYPTOPP_ASSERT(A%2==1);
184
185 word R=A%8;
186
187 for (unsigned i=3; i<WORD_BITS; i*=2)
188 R = R*(2-R*A);
189
190 CRYPTOPP_ASSERT(R*A==1);
191 return R;
192 }
193
194 // ********************************************************
195
196 #if !defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE) || (defined(__x86_64__) && defined(CRYPTOPP_WORD128_AVAILABLE))
197 #define TWO_64_BIT_WORDS 1
198 #define Declare2Words(x) word x##0, x##1;
199 #define AssignWord(a, b) a##0 = b; a##1 = 0;
200 #define Add2WordsBy1(a, b, c) a##0 = b##0 + c; a##1 = b##1 + (a##0 < c);
201 #define LowWord(a) a##0
202 #define HighWord(a) a##1
203 #ifdef _MSC_VER
204 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = _umul128(a, b, &p1);
205 #ifndef __INTEL_COMPILER
206 #define Double3Words(c, d) d##1 = __shiftleft128(d##0, d##1, 1); d##0 = __shiftleft128(c, d##0, 1); c *= 2;
207 #endif
208 #elif defined(__DECCXX)
209 #define MultiplyWordsLoHi(p0, p1, a, b) p0 = a*b; p1 = asm("umulh %a0, %a1, %v0", a, b);
210 #elif defined(__x86_64__)
211 #if defined(__SUNPRO_CC) && __SUNPRO_CC < 0x5100
212 // Sun Studio's gcc-style inline assembly is heavily bugged as of version 5.9 Patch 124864-09 2008/12/16, but this one works
213 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "r"(b) : "cc");
214 #else
215 #define MultiplyWordsLoHi(p0, p1, a, b) asm ("mulq %3" : "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
216 #define MulAcc(c, d, a, b) asm ("mulq %6; addq %3, %0; adcq %4, %1; adcq $0, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1), "=a"(p0), "=d"(p1) : "a"(a), "g"(b) : "cc");
217 #define Double3Words(c, d) asm ("addq %0, %0; adcq %1, %1; adcq %2, %2;" : "+r"(c), "+r"(d##0), "+r"(d##1) : : "cc");
218 #define Acc2WordsBy1(a, b) asm ("addq %2, %0; adcq $0, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b) : "cc");
219 #define Acc2WordsBy2(a, b) asm ("addq %2, %0; adcq %3, %1;" : "+r"(a##0), "+r"(a##1) : "r"(b##0), "r"(b##1) : "cc");
220 #define Acc3WordsBy2(c, d, e) asm ("addq %5, %0; adcq %6, %1; adcq $0, %2;" : "+r"(c), "=r"(e##0), "=r"(e##1) : "1"(d##0), "2"(d##1), "r"(e##0), "r"(e##1) : "cc");
221 #endif
222 #endif
223 #define MultiplyWords(p, a, b) MultiplyWordsLoHi(p##0, p##1, a, b)
224 #ifndef Double3Words
225 #define Double3Words(c, d) d##1 = 2*d##1 + (d##0>>(WORD_BITS-1)); d##0 = 2*d##0 + (c>>(WORD_BITS-1)); c *= 2;
226 #endif
227 #ifndef Acc2WordsBy2
228 #define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1;
229 #endif
230 #define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (t<a) + (u##0<t);}
231 #define SubtractWithBorrow(u, a, b) {word t = a-b; u##0 = t - u##1; u##1 = (t>a) + (u##0>t);}
232 #define GetCarry(u) u##1
233 #define GetBorrow(u) u##1
234 #else
235 #define Declare2Words(x) dword x;
236 #if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER) && !defined(_M_ARM)
237 #define MultiplyWords(p, a, b) p = __emulu(a, b);
238 #else
239 #define MultiplyWords(p, a, b) p = (dword)a*b;
240 #endif
241 #define AssignWord(a, b) a = b;
242 #define Add2WordsBy1(a, b, c) a = b + c;
243 #define Acc2WordsBy2(a, b) a += b;
244 #define LowWord(a) word(a)
245 #define HighWord(a) word(a>>WORD_BITS)
246 #define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2;
247 #define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u);
248 #define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u);
249 #define GetCarry(u) HighWord(u)
250 #define GetBorrow(u) word(u>>(WORD_BITS*2-1))
251 #endif
252 #ifndef MulAcc
253 #define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p));
254 #endif
255 #ifndef Acc2WordsBy1
256 #define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b)
257 #endif
258 #ifndef Acc3WordsBy2
259 #define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e));
260 #endif
261
262 class DWord
263 {
264 public:
265 #if defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE)
266 DWord() {std::memset(&m_whole, 0x00, sizeof(m_whole));}
267 #else
268 DWord() {std::memset(&m_halfs, 0x00, sizeof(m_halfs));}
269 #endif
270
271 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
272 explicit DWord(word low) : m_whole(low) { }
273 #else
274 explicit DWord(word low)
275 {
276 m_halfs.high = 0;
277 m_halfs.low = low;
278 }
279 #endif
280
281 #if defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE)
282 DWord(word low, word high) : m_whole()
283 #else
284 DWord(word low, word high) : m_halfs()
285 #endif
286 {
287 #if defined(CRYPTOPP_NATIVE_DWORD_AVAILABLE)
288 # if (CRYPTOPP_LITTLE_ENDIAN)
289 const word t[2] = {low,high};
290 memcpy(&m_whole, t, sizeof(m_whole));
291 # else
292 const word t[2] = {high,low};
293 memcpy(&m_whole, t, sizeof(m_whole));
294 # endif
295 #else
296 m_halfs.low = low;
297 m_halfs.high = high;
298 #endif
299 }
300
301 static DWord Multiply(word a, word b)
302 {
303 DWord r;
304 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
305 r.m_whole = (dword)a * b;
306 #elif defined(MultiplyWordsLoHi)
307 MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b);
308 #else
309 CRYPTOPP_ASSERT(0);
310 #endif
311 return r;
312 }
313
314 static DWord MultiplyAndAdd(word a, word b, word c)
315 {
316 DWord r = Multiply(a, b);
317 return r += c;
318 }
319
320 DWord & operator+=(word a)
321 {
322 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
323 m_whole = m_whole + a;
324 #else
325 m_halfs.low += a;
326 m_halfs.high += (m_halfs.low < a);
327 #endif
328 return *this;
329 }
330
331 DWord operator+(word a)
332 {
333 DWord r;
334 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
335 r.m_whole = m_whole + a;
336 #else
337 r.m_halfs.low = m_halfs.low + a;
338 r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a);
339 #endif
340 return r;
341 }
342
343 DWord operator-(DWord a)
344 {
345 DWord r;
346 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
347 r.m_whole = m_whole - a.m_whole;
348 #else
349 r.m_halfs.low = m_halfs.low - a.m_halfs.low;
350 r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low);
351 #endif
352 return r;
353 }
354
355 DWord operator-(word a)
356 {
357 DWord r;
358 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
359 r.m_whole = m_whole - a;
360 #else
361 r.m_halfs.low = m_halfs.low - a;
362 r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low);
363 #endif
364 return r;
365 }
366
367 // returns quotient, which must fit in a word
368 word operator/(word divisor);
369
370 word operator%(word a);
371
372 bool operator!() const
373 {
374 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
375 return !m_whole;
376 #else
377 return !m_halfs.high && !m_halfs.low;
378 #endif
379 }
380
381 // TODO: When NATIVE_DWORD is in effect, we access high and low, which are inactive
382 // union members, and that's UB. Also see http://stackoverflow.com/q/11373203.
383 word GetLowHalf() const {return m_halfs.low;}
384 word GetHighHalf() const {return m_halfs.high;}
385 word GetHighHalfAsBorrow() const {return 0-m_halfs.high;}
386
387 private:
388 // Issue 274, "Types cannot be declared in anonymous union",
389 // http://github.com/weidai11/cryptopp/issues/274
390 // Thanks to Martin Bonner at http://stackoverflow.com/a/39507183
391 struct half_words
392 {
393 #if (CRYPTOPP_LITTLE_ENDIAN)
394 word low;
395 word high;
396 #else
397 word high;
398 word low;
399 #endif
400 };
401 union
402 {
403 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
404 dword m_whole;
405 #endif
406 half_words m_halfs;
407 };
408 };
409
410 class Word
411 {
412 public:
413 Word() : m_whole(0) {}
414 Word(word value) : m_whole(value) {}
415 Word(hword low, hword high) : m_whole(low | (word(high) << (WORD_BITS/2))) {}
416
417 static Word Multiply(hword a, hword b)
418 {
419 Word r;
420 r.m_whole = (word)a * b;
421 return r;
422 }
423
424 Word operator-(Word a)
425 {
426 Word r;
427 r.m_whole = m_whole - a.m_whole;
428 return r;
429 }
430
431 Word operator-(hword a)
432 {
433 Word r;
434 r.m_whole = m_whole - a;
435 return r;
436 }
437
438 // returns quotient, which must fit in a word
439 hword operator/(hword divisor)
440 {
441 return hword(m_whole / divisor);
442 }
443
444 bool operator!() const
445 {
446 return !m_whole;
447 }
448
449 word GetWhole() const {return m_whole;}
450 hword GetLowHalf() const {return hword(m_whole);}
451 hword GetHighHalf() const {return hword(m_whole>>(WORD_BITS/2));}
452 hword GetHighHalfAsBorrow() const {return 0-hword(m_whole>>(WORD_BITS/2));}
453
454 private:
455 word m_whole;
456 };
457
458 // do a 3 word by 2 word divide, returns quotient and leaves remainder in A
459 template <class S, class D>
460 S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULLPTR)
461 {
462 CRYPTOPP_UNUSED(dummy);
463
464 // Assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a S
465 CRYPTOPP_ASSERT(A[2] < B1 || (A[2]==B1 && A[1] < B0));
466
467 // estimate the quotient: do a 2 S by 1 S divide.
468 // Profiling tells us the original second case was dominant, so it was promoted to the first If statement.
469 // The code change occurred at Commit dc99266599a0e72d.
470
471 S Q; bool pre = (S(B1+1) == 0);
472 if (B1 > 0 && !pre)
473 Q = D(A[1], A[2]) / S(B1+1);
474 else if (pre)
475 Q = A[2];
476 else
477 Q = D(A[0], A[1]) / B0;
478
479 // now subtract Q*B from A
480 D p = D::Multiply(B0, Q);
481 D u = (D) A[0] - p.GetLowHalf();
482 A[0] = u.GetLowHalf();
483 u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q);
484 A[1] = u.GetLowHalf();
485 A[2] += u.GetHighHalf();
486
487 // Q <= actual quotient, so fix it
488 while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
489 {
490 u = (D) A[0] - B0;
491 A[0] = u.GetLowHalf();
492 u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
493 A[1] = u.GetLowHalf();
494 A[2] += u.GetHighHalf();
495 Q++;
496 CRYPTOPP_ASSERT(Q); // shouldn't overflow
497 }
498
499 return Q;
500 }
501
502 // do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
503 template <class S, class D>
504 inline D DivideFourWordsByTwo(S *T, const D &Al, const D &Ah, const D &B)
505 {
506 // Profiling tells us the original second case was dominant, so it was promoted to the first If statement.
507 // The code change occurred at Commit dc99266599a0e72d.
508
509 if (!!B)
510 {
511 S Q[2];
512 T[0] = Al.GetLowHalf();
513 T[1] = Al.GetHighHalf();
514 T[2] = Ah.GetLowHalf();
515 T[3] = Ah.GetHighHalf();
516 Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(), B.GetHighHalf());
517 Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
518 return D(Q[0], Q[1]);
519 }
520 else // if divisor is 0, we assume divisor==2**(2*WORD_BITS)
521 {
522 return D(Ah.GetLowHalf(), Ah.GetHighHalf());
523 }
524 }
525
526 // returns quotient, which must fit in a word
527 inline word DWord::operator/(word a)
528 {
529 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
530 return word(m_whole / a);
531 #else
532 hword r[4];
533 return DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a).GetWhole();
534 #endif
535 }
536
537 inline word DWord::operator%(word a)
538 {
539 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
540 return word(m_whole % a);
541 #else
542 if (a < (word(1) << (WORD_BITS/2)))
543 {
544 hword h = hword(a);
545 word r = m_halfs.high % h;
546 r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
547 return hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h);
548 }
549 else
550 {
551 hword r[4];
552 DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a);
553 return Word(r[0], r[1]).GetWhole();
554 }
555 #endif
556 }
557
558 // ********************************************************
559
560 // Use some tricks to share assembly code between MSVC, GCC, Clang and Sun CC.
561 #if defined(__GNUC__)
562 #define AddPrologue \
563 int result; \
564 __asm__ __volatile__ \
565 ( \
566 INTEL_NOPREFIX
567 #define AddEpilogue \
568 ATT_PREFIX \
569 : "=a" (result)\
570 : "d" (C), "a" (A), "D" (B), "c" (N) \
571 : "%esi", "memory", "cc" \
572 );\
573 return result;
574 #define MulPrologue \
575 __asm__ __volatile__ \
576 ( \
577 INTEL_NOPREFIX \
578 AS1( push ebx) \
579 AS2( mov ebx, edx)
580 #define MulEpilogue \
581 AS1( pop ebx) \
582 ATT_PREFIX \
583 : \
584 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \
585 : "%esi", "memory", "cc" \
586 );
587 #define SquPrologue MulPrologue
588 #define SquEpilogue \
589 AS1( pop ebx) \
590 ATT_PREFIX \
591 : \
592 : "d" (s_maskLow16), "c" (C), "a" (A) \
593 : "%esi", "%edi", "memory", "cc" \
594 );
595 #define TopPrologue MulPrologue
596 #define TopEpilogue \
597 AS1( pop ebx) \
598 ATT_PREFIX \
599 : \
600 : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \
601 : "memory", "cc" \
602 );
603 #else
604 #define AddPrologue \
605 __asm push edi \
606 __asm push esi \
607 __asm mov eax, [esp+12] \
608 __asm mov edi, [esp+16]
609 #define AddEpilogue \
610 __asm pop esi \
611 __asm pop edi \
612 __asm ret 8
613 #define SaveEBX
614 #define RestoreEBX
615 #define SquPrologue \
616 AS2( mov eax, A) \
617 AS2( mov ecx, C) \
618 SaveEBX \
619 AS2( lea ebx, s_maskLow16)
620 #define MulPrologue \
621 AS2( mov eax, A) \
622 AS2( mov edi, B) \
623 AS2( mov ecx, C) \
624 SaveEBX \
625 AS2( lea ebx, s_maskLow16)
626 #define TopPrologue \
627 AS2( mov eax, A) \
628 AS2( mov edi, B) \
629 AS2( mov ecx, C) \
630 AS2( mov esi, L) \
631 SaveEBX \
632 AS2( lea ebx, s_maskLow16)
633 #define SquEpilogue RestoreEBX
634 #define MulEpilogue RestoreEBX
635 #define TopEpilogue RestoreEBX
636 #endif
637
638 #ifdef CRYPTOPP_X64_MASM_AVAILABLE
639 extern "C" {
640 int Baseline_Add(size_t N, word *C, const word *A, const word *B);
641 int Baseline_Sub(size_t N, word *C, const word *A, const word *B);
642 }
643 #elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE)
644 int Baseline_Add(size_t N, word *C, const word *A, const word *B)
645 {
646 word result;
647 __asm__ __volatile__
648 (
649 INTEL_NOPREFIX
650 AS1( neg %1)
651 ASJ( jz, 1, f)
652 AS2( mov %0,[%3+8*%1])
653 AS2( add %0,[%4+8*%1])
654 AS2( mov [%2+8*%1],%0)
655 ASL(0)
656 AS2( mov %0,[%3+8*%1+8])
657 AS2( adc %0,[%4+8*%1+8])
658 AS2( mov [%2+8*%1+8],%0)
659 AS2( lea %1,[%1+2])
660 ASJ( jrcxz, 1, f)
661 AS2( mov %0,[%3+8*%1])
662 AS2( adc %0,[%4+8*%1])
663 AS2( mov [%2+8*%1],%0)
664 ASJ( jmp, 0, b)
665 ASL(1)
666 AS2( mov %0, 0)
667 AS2( adc %0, %0)
668 ATT_NOPREFIX
669 : "=&r" (result), "+c" (N)
670 : "r" (C+N), "r" (A+N), "r" (B+N)
671 : "memory", "cc"
672 );
673 return (int)result;
674 }
675
676 int Baseline_Sub(size_t N, word *C, const word *A, const word *B)
677 {
678 word result;
679 __asm__ __volatile__
680 (
681 INTEL_NOPREFIX
682 AS1( neg %1)
683 ASJ( jz, 1, f)
684 AS2( mov %0,[%3+8*%1])
685 AS2( sub %0,[%4+8*%1])
686 AS2( mov [%2+8*%1],%0)
687 ASL(0)
688 AS2( mov %0,[%3+8*%1+8])
689 AS2( sbb %0,[%4+8*%1+8])
690 AS2( mov [%2+8*%1+8],%0)
691 AS2( lea %1,[%1+2])
692 ASJ( jrcxz, 1, f)
693 AS2( mov %0,[%3+8*%1])
694 AS2( sbb %0,[%4+8*%1])
695 AS2( mov [%2+8*%1],%0)
696 ASJ( jmp, 0, b)
697 ASL(1)
698 AS2( mov %0, 0)
699 AS2( adc %0, %0)
700 ATT_NOPREFIX
701 : "=&r" (result), "+c" (N)
702 : "r" (C+N), "r" (A+N), "r" (B+N)
703 : "memory", "cc"
704 );
705 return (int)result;
706 }
707 #elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86
708 CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
709 {
710 AddPrologue
711
712 // now: eax = A, edi = B, edx = C, ecx = N
713 AS2( lea eax, [eax+4*ecx])
714 AS2( lea edi, [edi+4*ecx])
715 AS2( lea edx, [edx+4*ecx])
716
717 AS1( neg ecx) // ecx is negative index
718 AS2( test ecx, 2) // this clears carry flag
719 ASJ( jz, 0, f)
720 AS2( sub ecx, 2)
721 ASJ( jmp, 1, f)
722
723 ASL(0)
724 ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero
725 AS2( mov esi,[eax+4*ecx])
726 AS2( adc esi,[edi+4*ecx])
727 AS2( mov [edx+4*ecx],esi)
728 AS2( mov esi,[eax+4*ecx+4])
729 AS2( adc esi,[edi+4*ecx+4])
730 AS2( mov [edx+4*ecx+4],esi)
731 ASL(1)
732 AS2( mov esi,[eax+4*ecx+8])
733 AS2( adc esi,[edi+4*ecx+8])
734 AS2( mov [edx+4*ecx+8],esi)
735 AS2( mov esi,[eax+4*ecx+12])
736 AS2( adc esi,[edi+4*ecx+12])
737 AS2( mov [edx+4*ecx+12],esi)
738
739 AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2
740 ASJ( jmp, 0, b)
741
742 ASL(2)
743 AS2( mov eax, 0)
744 AS1( setc al) // store carry into eax (return result register)
745
746 AddEpilogue
747
748 // http://github.com/weidai11/cryptopp/issues/340
749 CRYPTOPP_UNUSED(A); CRYPTOPP_UNUSED(B);
750 CRYPTOPP_UNUSED(C); CRYPTOPP_UNUSED(N);
751 }
752
753 CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
754 {
755 AddPrologue
756
757 // now: eax = A, edi = B, edx = C, ecx = N
758 AS2( lea eax, [eax+4*ecx])
759 AS2( lea edi, [edi+4*ecx])
760 AS2( lea edx, [edx+4*ecx])
761
762 AS1( neg ecx) // ecx is negative index
763 AS2( test ecx, 2) // this clears carry flag
764 ASJ( jz, 0, f)
765 AS2( sub ecx, 2)
766 ASJ( jmp, 1, f)
767
768 ASL(0)
769 ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero
770 AS2( mov esi,[eax+4*ecx])
771 AS2( sbb esi,[edi+4*ecx])
772 AS2( mov [edx+4*ecx],esi)
773 AS2( mov esi,[eax+4*ecx+4])
774 AS2( sbb esi,[edi+4*ecx+4])
775 AS2( mov [edx+4*ecx+4],esi)
776 ASL(1)
777 AS2( mov esi,[eax+4*ecx+8])
778 AS2( sbb esi,[edi+4*ecx+8])
779 AS2( mov [edx+4*ecx+8],esi)
780 AS2( mov esi,[eax+4*ecx+12])
781 AS2( sbb esi,[edi+4*ecx+12])
782 AS2( mov [edx+4*ecx+12],esi)
783
784 AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2
785 ASJ( jmp, 0, b)
786
787 ASL(2)
788 AS2( mov eax, 0)
789 AS1( setc al) // store carry into eax (return result register)
790
791 AddEpilogue
792
793 // http://github.com/weidai11/cryptopp/issues/340
794 CRYPTOPP_UNUSED(A); CRYPTOPP_UNUSED(B);
795 CRYPTOPP_UNUSED(C); CRYPTOPP_UNUSED(N);
796 }
797
798 #if CRYPTOPP_INTEGER_SSE2
799 CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Add(size_t N, word *C, const word *A, const word *B)
800 {
801 AddPrologue
802
803 // now: eax = A, edi = B, edx = C, ecx = N
804 AS2( lea eax, [eax+4*ecx])
805 AS2( lea edi, [edi+4*ecx])
806 AS2( lea edx, [edx+4*ecx])
807
808 AS1( neg ecx) // ecx is negative index
809 AS2( pxor mm2, mm2)
810 ASJ( jz, 2, f)
811 AS2( test ecx, 2) // this clears carry flag
812 ASJ( jz, 0, f)
813 AS2( sub ecx, 2)
814 ASJ( jmp, 1, f)
815
816 ASL(0)
817 AS2( movd mm0, DWORD PTR [eax+4*ecx])
818 AS2( movd mm1, DWORD PTR [edi+4*ecx])
819 AS2( paddq mm0, mm1)
820 AS2( paddq mm2, mm0)
821 AS2( movd DWORD PTR [edx+4*ecx], mm2)
822 AS2( psrlq mm2, 32)
823
824 AS2( movd mm0, DWORD PTR [eax+4*ecx+4])
825 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
826 AS2( paddq mm0, mm1)
827 AS2( paddq mm2, mm0)
828 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
829 AS2( psrlq mm2, 32)
830
831 ASL(1)
832 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
833 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
834 AS2( paddq mm0, mm1)
835 AS2( paddq mm2, mm0)
836 AS2( movd DWORD PTR [edx+4*ecx+8], mm2)
837 AS2( psrlq mm2, 32)
838
839 AS2( movd mm0, DWORD PTR [eax+4*ecx+12])
840 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
841 AS2( paddq mm0, mm1)
842 AS2( paddq mm2, mm0)
843 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
844 AS2( psrlq mm2, 32)
845
846 AS2( add ecx, 4)
847 ASJ( jnz, 0, b)
848
849 ASL(2)
850 AS2( movd eax, mm2)
851 AS1( emms)
852
853 AddEpilogue
854
855 // http://github.com/weidai11/cryptopp/issues/340
856 CRYPTOPP_UNUSED(A); CRYPTOPP_UNUSED(B);
857 CRYPTOPP_UNUSED(C); CRYPTOPP_UNUSED(N);
858 }
859 CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Sub(size_t N, word *C, const word *A, const word *B)
860 {
861 AddPrologue
862
863 // now: eax = A, edi = B, edx = C, ecx = N
864 AS2( lea eax, [eax+4*ecx])
865 AS2( lea edi, [edi+4*ecx])
866 AS2( lea edx, [edx+4*ecx])
867
868 AS1( neg ecx) // ecx is negative index
869 AS2( pxor mm2, mm2)
870 ASJ( jz, 2, f)
871 AS2( test ecx, 2) // this clears carry flag
872 ASJ( jz, 0, f)
873 AS2( sub ecx, 2)
874 ASJ( jmp, 1, f)
875
876 ASL(0)
877 AS2( movd mm0, DWORD PTR [eax+4*ecx])
878 AS2( movd mm1, DWORD PTR [edi+4*ecx])
879 AS2( psubq mm0, mm1)
880 AS2( psubq mm0, mm2)
881 AS2( movd DWORD PTR [edx+4*ecx], mm0)
882 AS2( psrlq mm0, 63)
883
884 AS2( movd mm2, DWORD PTR [eax+4*ecx+4])
885 AS2( movd mm1, DWORD PTR [edi+4*ecx+4])
886 AS2( psubq mm2, mm1)
887 AS2( psubq mm2, mm0)
888 AS2( movd DWORD PTR [edx+4*ecx+4], mm2)
889 AS2( psrlq mm2, 63)
890
891 ASL(1)
892 AS2( movd mm0, DWORD PTR [eax+4*ecx+8])
893 AS2( movd mm1, DWORD PTR [edi+4*ecx+8])
894 AS2( psubq mm0, mm1)
895 AS2( psubq mm0, mm2)
896 AS2( movd DWORD PTR [edx+4*ecx+8], mm0)
897 AS2( psrlq mm0, 63)
898
899 AS2( movd mm2, DWORD PTR [eax+4*ecx+12])
900 AS2( movd mm1, DWORD PTR [edi+4*ecx+12])
901 AS2( psubq mm2, mm1)
902 AS2( psubq mm2, mm0)
903 AS2( movd DWORD PTR [edx+4*ecx+12], mm2)
904 AS2( psrlq mm2, 63)
905
906 AS2( add ecx, 4)
907 ASJ( jnz, 0, b)
908
909 ASL(2)
910 AS2( movd eax, mm2)
911 AS1( emms)
912
913 AddEpilogue
914
915 // http://github.com/weidai11/cryptopp/issues/340
916 CRYPTOPP_UNUSED(A); CRYPTOPP_UNUSED(B);
917 CRYPTOPP_UNUSED(C); CRYPTOPP_UNUSED(N);
918 }
919 #endif // CRYPTOPP_INTEGER_SSE2
920 #else // CRYPTOPP_SSE2_ASM_AVAILABLE
921 int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
922 {
923 CRYPTOPP_ASSERT (N%2 == 0);
924
925 Declare2Words(u);
926 AssignWord(u, 0);
927 for (size_t i=0; i<N; i+=2)
928 {
929 AddWithCarry(u, A[i], B[i]);
930 C[i] = LowWord(u);
931 AddWithCarry(u, A[i+1], B[i+1]);
932 C[i+1] = LowWord(u);
933 }
934 return int(GetCarry(u));
935 }
936
937 int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
938 {
939 CRYPTOPP_ASSERT (N%2 == 0);
940
941 Declare2Words(u);
942 AssignWord(u, 0);
943 for (size_t i=0; i<N; i+=2)
944 {
945 SubtractWithBorrow(u, A[i], B[i]);
946 C[i] = LowWord(u);
947 SubtractWithBorrow(u, A[i+1], B[i+1]);
948 C[i+1] = LowWord(u);
949 }
950 return int(GetBorrow(u));
951 }
952 #endif
953
954 static word LinearMultiply(word *C, const word *AA, word B, size_t N)
955 {
956 // http://github.com/weidai11/cryptopp/issues/188
957 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
958
959 word carry=0;
960 for(unsigned i=0; i<N; i++)
961 {
962 Declare2Words(p);
963 MultiplyWords(p, A[i], B);
964 Acc2WordsBy1(p, carry);
965 C[i] = LowWord(p);
966 carry = HighWord(p);
967 }
968 return carry;
969 }
970
971 #ifndef CRYPTOPP_DOXYGEN_PROCESSING
972
973 #define Mul_2 \
974 Mul_Begin(2) \
975 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
976 Mul_End(1, 1)
977
978 #define Mul_4 \
979 Mul_Begin(4) \
980 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
981 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
982 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
983 Mul_SaveAcc(3, 1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
984 Mul_SaveAcc(4, 2, 3) Mul_Acc(3, 2) \
985 Mul_End(5, 3)
986
987 #define Mul_8 \
988 Mul_Begin(8) \
989 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
990 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
991 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
992 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
993 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) \
994 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) \
995 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) \
996 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) \
997 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) \
998 Mul_SaveAcc(9, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
999 Mul_SaveAcc(10, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1000 Mul_SaveAcc(11, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1001 Mul_SaveAcc(12, 6, 7) Mul_Acc(7, 6) \
1002 Mul_End(13, 7)
1003
1004 #define Mul_16 \
1005 Mul_Begin(16) \
1006 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
1007 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
1008 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1009 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
1010 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) \
1011 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) \
1012 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) \
1013 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) \
1014 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) \
1015 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) \
1016 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) \
1017 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) \
1018 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) \
1019 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) \
1020 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) \
1021 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) \
1022 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) \
1023 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) \
1024 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) \
1025 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) \
1026 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) \
1027 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) \
1028 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) \
1029 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) \
1030 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) \
1031 Mul_SaveAcc(25, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1032 Mul_SaveAcc(26, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1033 Mul_SaveAcc(27, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1034 Mul_SaveAcc(28, 14, 15) Mul_Acc(15, 14) \
1035 Mul_End(29, 15)
1036
1037 #define Squ_2 \
1038 Squ_Begin(2) \
1039 Squ_End(2)
1040
1041 #define Squ_4 \
1042 Squ_Begin(4) \
1043 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
1044 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
1045 Squ_SaveAcc(3, 1, 3) Squ_Diag(2) \
1046 Squ_SaveAcc(4, 2, 3) Squ_NonDiag \
1047 Squ_End(4)
1048
1049 #define Squ_8 \
1050 Squ_Begin(8) \
1051 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
1052 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
1053 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
1054 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
1055 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
1056 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
1057 Squ_SaveAcc(7, 1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
1058 Squ_SaveAcc(8, 2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
1059 Squ_SaveAcc(9, 3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
1060 Squ_SaveAcc(10, 4, 7) Squ_Acc(5, 6) Squ_NonDiag \
1061 Squ_SaveAcc(11, 5, 7) Squ_Diag(6) \
1062 Squ_SaveAcc(12, 6, 7) Squ_NonDiag \
1063 Squ_End(8)
1064
1065 #define Squ_16 \
1066 Squ_Begin(16) \
1067 Squ_SaveAcc(1, 0, 2) Squ_Diag(1) \
1068 Squ_SaveAcc(2, 0, 3) Squ_Acc(1, 2) Squ_NonDiag \
1069 Squ_SaveAcc(3, 0, 4) Squ_Acc(1, 3) Squ_Diag(2) \
1070 Squ_SaveAcc(4, 0, 5) Squ_Acc(1, 4) Squ_Acc(2, 3) Squ_NonDiag \
1071 Squ_SaveAcc(5, 0, 6) Squ_Acc(1, 5) Squ_Acc(2, 4) Squ_Diag(3) \
1072 Squ_SaveAcc(6, 0, 7) Squ_Acc(1, 6) Squ_Acc(2, 5) Squ_Acc(3, 4) Squ_NonDiag \
1073 Squ_SaveAcc(7, 0, 8) Squ_Acc(1, 7) Squ_Acc(2, 6) Squ_Acc(3, 5) Squ_Diag(4) \
1074 Squ_SaveAcc(8, 0, 9) Squ_Acc(1, 8) Squ_Acc(2, 7) Squ_Acc(3, 6) Squ_Acc(4, 5) Squ_NonDiag \
1075 Squ_SaveAcc(9, 0, 10) Squ_Acc(1, 9) Squ_Acc(2, 8) Squ_Acc(3, 7) Squ_Acc(4, 6) Squ_Diag(5) \
1076 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 \
1077 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) \
1078 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 \
1079 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) \
1080 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 \
1081 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) \
1082 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 \
1083 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) \
1084 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 \
1085 Squ_SaveAcc(19, 5, 15) Squ_Acc(6, 14) Squ_Acc(7, 13) Squ_Acc(8, 12) Squ_Acc(9, 11) Squ_Diag(10) \
1086 Squ_SaveAcc(20, 6, 15) Squ_Acc(7, 14) Squ_Acc(8, 13) Squ_Acc(9, 12) Squ_Acc(10, 11) Squ_NonDiag \
1087 Squ_SaveAcc(21, 7, 15) Squ_Acc(8, 14) Squ_Acc(9, 13) Squ_Acc(10, 12) Squ_Diag(11) \
1088 Squ_SaveAcc(22, 8, 15) Squ_Acc(9, 14) Squ_Acc(10, 13) Squ_Acc(11, 12) Squ_NonDiag \
1089 Squ_SaveAcc(23, 9, 15) Squ_Acc(10, 14) Squ_Acc(11, 13) Squ_Diag(12) \
1090 Squ_SaveAcc(24, 10, 15) Squ_Acc(11, 14) Squ_Acc(12, 13) Squ_NonDiag \
1091 Squ_SaveAcc(25, 11, 15) Squ_Acc(12, 14) Squ_Diag(13) \
1092 Squ_SaveAcc(26, 12, 15) Squ_Acc(13, 14) Squ_NonDiag \
1093 Squ_SaveAcc(27, 13, 15) Squ_Diag(14) \
1094 Squ_SaveAcc(28, 14, 15) Squ_NonDiag \
1095 Squ_End(16)
1096
1097 #define Bot_2 \
1098 Mul_Begin(2) \
1099 Bot_SaveAcc(0, 0, 1) Bot_Acc(1, 0) \
1100 Bot_End(2)
1101
1102 #define Bot_4 \
1103 Mul_Begin(4) \
1104 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
1105 Mul_SaveAcc(1, 2, 0) Mul_Acc(1, 1) Mul_Acc(0, 2) \
1106 Bot_SaveAcc(2, 0, 3) Bot_Acc(1, 2) Bot_Acc(2, 1) Bot_Acc(3, 0) \
1107 Bot_End(4)
1108
1109 #define Bot_8 \
1110 Mul_Begin(8) \
1111 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
1112 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
1113 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1114 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
1115 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) \
1116 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) \
1117 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) \
1118 Bot_End(8)
1119
1120 #define Bot_16 \
1121 Mul_Begin(16) \
1122 Mul_SaveAcc(0, 0, 1) Mul_Acc(1, 0) \
1123 Mul_SaveAcc(1, 0, 2) Mul_Acc(1, 1) Mul_Acc(2, 0) \
1124 Mul_SaveAcc(2, 0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1125 Mul_SaveAcc(3, 0, 4) Mul_Acc(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) Mul_Acc(4, 0) \
1126 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) \
1127 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) \
1128 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) \
1129 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) \
1130 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) \
1131 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) \
1132 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) \
1133 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) \
1134 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) \
1135 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) \
1136 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) \
1137 Bot_End(16)
1138
1139 #endif
1140
1141 #if 0
1142 #define Mul_Begin(n) \
1143 Declare2Words(p) \
1144 Declare2Words(c) \
1145 Declare2Words(d) \
1146 MultiplyWords(p, A[0], B[0]) \
1147 AssignWord(c, LowWord(p)) \
1148 AssignWord(d, HighWord(p))
1149
1150 #define Mul_Acc(i, j) \
1151 MultiplyWords(p, A[i], B[j]) \
1152 Acc2WordsBy1(c, LowWord(p)) \
1153 Acc2WordsBy1(d, HighWord(p))
1154
1155 #define Mul_SaveAcc(k, i, j) \
1156 R[k] = LowWord(c); \
1157 Add2WordsBy1(c, d, HighWord(c)) \
1158 MultiplyWords(p, A[i], B[j]) \
1159 AssignWord(d, HighWord(p)) \
1160 Acc2WordsBy1(c, LowWord(p))
1161
1162 #define Mul_End(n) \
1163 R[2*n-3] = LowWord(c); \
1164 Acc2WordsBy1(d, HighWord(c)) \
1165 MultiplyWords(p, A[n-1], B[n-1])\
1166 Acc2WordsBy2(d, p) \
1167 R[2*n-2] = LowWord(d); \
1168 R[2*n-1] = HighWord(d);
1169
1170 #define Bot_SaveAcc(k, i, j) \
1171 R[k] = LowWord(c); \
1172 word e = LowWord(d) + HighWord(c); \
1173 e += A[i] * B[j];
1174
1175 #define Bot_Acc(i, j) \
1176 e += A[i] * B[j];
1177
1178 #define Bot_End(n) \
1179 R[n-1] = e;
1180 #else
1181 #define Mul_Begin(n) \
1182 Declare2Words(p) \
1183 word c; \
1184 Declare2Words(d) \
1185 MultiplyWords(p, A[0], B[0]) \
1186 c = LowWord(p); \
1187 AssignWord(d, HighWord(p))
1188
1189 #define Mul_Acc(i, j) \
1190 MulAcc(c, d, A[i], B[j])
1191
1192 #define Mul_SaveAcc(k, i, j) \
1193 R[k] = c; \
1194 c = LowWord(d); \
1195 AssignWord(d, HighWord(d)) \
1196 MulAcc(c, d, A[i], B[j])
1197
1198 #define Mul_End(k, i) \
1199 R[k] = c; \
1200 MultiplyWords(p, A[i], B[i]) \
1201 Acc2WordsBy2(p, d) \
1202 R[k+1] = LowWord(p); \
1203 R[k+2] = HighWord(p);
1204
1205 #define Bot_SaveAcc(k, i, j) \
1206 R[k] = c; \
1207 c = LowWord(d); \
1208 c += A[i] * B[j];
1209
1210 #define Bot_Acc(i, j) \
1211 c += A[i] * B[j];
1212
1213 #define Bot_End(n) \
1214 R[n-1] = c;
1215 #endif
1216
1217 #define Squ_Begin(n) \
1218 Declare2Words(p) \
1219 word c; \
1220 Declare2Words(d) \
1221 Declare2Words(e) \
1222 MultiplyWords(p, A[0], A[0]) \
1223 R[0] = LowWord(p); \
1224 AssignWord(e, HighWord(p)) \
1225 MultiplyWords(p, A[0], A[1]) \
1226 c = LowWord(p); \
1227 AssignWord(d, HighWord(p)) \
1228 Squ_NonDiag \
1229
1230 #define Squ_NonDiag \
1231 Double3Words(c, d)
1232
1233 #define Squ_SaveAcc(k, i, j) \
1234 Acc3WordsBy2(c, d, e) \
1235 R[k] = c; \
1236 MultiplyWords(p, A[i], A[j]) \
1237 c = LowWord(p); \
1238 AssignWord(d, HighWord(p)) \
1239
1240 #define Squ_Acc(i, j) \
1241 MulAcc(c, d, A[i], A[j])
1242
1243 #define Squ_Diag(i) \
1244 Squ_NonDiag \
1245 MulAcc(c, d, A[i], A[i])
1246
1247 #define Squ_End(n) \
1248 Acc3WordsBy2(c, d, e) \
1249 R[2*n-3] = c; \
1250 MultiplyWords(p, A[n-1], A[n-1])\
1251 Acc2WordsBy2(p, e) \
1252 R[2*n-2] = LowWord(p); \
1253 R[2*n-1] = HighWord(p);
1254
1255
1256 void Baseline_Multiply2(word *R, const word *AA, const word *BB)
1257 {
1258 // http://github.com/weidai11/cryptopp/issues/188
1259 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1260 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1261
1262 Mul_2
1263 }
1264
1265 void Baseline_Multiply4(word *R, const word *AA, const word *BB)
1266 {
1267 // http://github.com/weidai11/cryptopp/issues/188
1268 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1269 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1270
1271 Mul_4
1272 }
1273
1274 void Baseline_Multiply8(word *R, const word *AA, const word *BB)
1275 {
1276 // http://github.com/weidai11/cryptopp/issues/188
1277 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1278 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1279
1280 Mul_8
1281 }
1282
1283 void Baseline_Square2(word *R, const word *AA)
1284 {
1285 // http://github.com/weidai11/cryptopp/issues/188
1286 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1287
1288 Squ_2
1289 }
1290
1291 void Baseline_Square4(word *R, const word *AA)
1292 {
1293 // http://github.com/weidai11/cryptopp/issues/188
1294 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1295
1296 Squ_4
1297 }
1298
1299 void Baseline_Square8(word *R, const word *AA)
1300 {
1301 // http://github.com/weidai11/cryptopp/issues/188
1302 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1303
1304 Squ_8
1305 }
1306
1307 void Baseline_MultiplyBottom2(word *R, const word *AA, const word *BB)
1308 {
1309 // http://github.com/weidai11/cryptopp/issues/188
1310 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1311 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1312
1313 Bot_2
1314
1315 // http://github.com/weidai11/cryptopp/issues/340
1316 #if defined(TWO_64_BIT_WORDS)
1317 CRYPTOPP_UNUSED(d0); CRYPTOPP_UNUSED(d1);
1318 #endif
1319 }
1320
1321 void Baseline_MultiplyBottom4(word *R, const word *AA, const word *BB)
1322 {
1323 // http://github.com/weidai11/cryptopp/issues/188
1324 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1325 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1326
1327 Bot_4
1328 }
1329
1330 void Baseline_MultiplyBottom8(word *R, const word *AA, const word *BB)
1331 {
1332 // http://github.com/weidai11/cryptopp/issues/188
1333 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1334 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1335
1336 Bot_8
1337 }
1338
1339 #define Top_Begin(n) \
1340 Declare2Words(p) \
1341 word c; \
1342 Declare2Words(d) \
1343 MultiplyWords(p, A[0], B[n-2]);\
1344 AssignWord(d, HighWord(p));
1345
1346 #define Top_Acc(i, j) \
1347 MultiplyWords(p, A[i], B[j]);\
1348 Acc2WordsBy1(d, HighWord(p));
1349
1350 #define Top_SaveAcc0(i, j) \
1351 c = LowWord(d); \
1352 AssignWord(d, HighWord(d)) \
1353 MulAcc(c, d, A[i], B[j])
1354
1355 #define Top_SaveAcc1(i, j) \
1356 c = L<c; \
1357 Acc2WordsBy1(d, c); \
1358 c = LowWord(d); \
1359 AssignWord(d, HighWord(d)) \
1360 MulAcc(c, d, A[i], B[j])
1361
1362 void Baseline_MultiplyTop2(word *R, const word *A, const word *B, word L)
1363 {
1364 CRYPTOPP_UNUSED(L);
1365 word T[4];
1366 Baseline_Multiply2(T, A, B);
1367 R[0] = T[2];
1368 R[1] = T[3];
1369 }
1370
1371 void Baseline_MultiplyTop4(word *R, const word *AA, const word *BB, word L)
1372 {
1373 // http://github.com/weidai11/cryptopp/issues/188
1374 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1375 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1376
1377 Top_Begin(4)
1378 Top_Acc(1, 1) Top_Acc(2, 0) \
1379 Top_SaveAcc0(0, 3) Mul_Acc(1, 2) Mul_Acc(2, 1) Mul_Acc(3, 0) \
1380 Top_SaveAcc1(1, 3) Mul_Acc(2, 2) Mul_Acc(3, 1) \
1381 Mul_SaveAcc(0, 2, 3) Mul_Acc(3, 2) \
1382 Mul_End(1, 3)
1383 }
1384
1385 void Baseline_MultiplyTop8(word *R, const word *AA, const word *BB, word L)
1386 {
1387 // http://github.com/weidai11/cryptopp/issues/188
1388 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1389 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1390
1391 Top_Begin(8)
1392 Top_Acc(1, 5) Top_Acc(2, 4) Top_Acc(3, 3) Top_Acc(4, 2) Top_Acc(5, 1) Top_Acc(6, 0) \
1393 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) \
1394 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) \
1395 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) \
1396 Mul_SaveAcc(1, 3, 7) Mul_Acc(4, 6) Mul_Acc(5, 5) Mul_Acc(6, 4) Mul_Acc(7, 3) \
1397 Mul_SaveAcc(2, 4, 7) Mul_Acc(5, 6) Mul_Acc(6, 5) Mul_Acc(7, 4) \
1398 Mul_SaveAcc(3, 5, 7) Mul_Acc(6, 6) Mul_Acc(7, 5) \
1399 Mul_SaveAcc(4, 6, 7) Mul_Acc(7, 6) \
1400 Mul_End(5, 7)
1401 }
1402
1403 #if !CRYPTOPP_INTEGER_SSE2 // save memory by not compiling these functions when SSE2 is available
1404 void Baseline_Multiply16(word *R, const word *AA, const word *BB)
1405 {
1406 // http://github.com/weidai11/cryptopp/issues/188
1407 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1408 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1409
1410 Mul_16
1411 }
1412
1413 void Baseline_Square16(word *R, const word *AA)
1414 {
1415 // http://github.com/weidai11/cryptopp/issues/188
1416 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1417
1418 Squ_16
1419 }
1420
1421 void Baseline_MultiplyBottom16(word *R, const word *AA, const word *BB)
1422 {
1423 // http://github.com/weidai11/cryptopp/issues/188
1424 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1425 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1426
1427 Bot_16
1428 }
1429
1430 void Baseline_MultiplyTop16(word *R, const word *AA, const word *BB, word L)
1431 {
1432 // http://github.com/weidai11/cryptopp/issues/188
1433 MAYBE_CONST word* A = MAYBE_UNCONST_CAST(AA);
1434 MAYBE_CONST word* B = MAYBE_UNCONST_CAST(BB);
1435
1436 Top_Begin(16)
1437 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) \
1438 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) \
1439 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) \
1440 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) \
1441 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) \
1442 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) \
1443 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) \
1444 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) \
1445 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) \
1446 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) \
1447 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) \
1448 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) \
1449 Mul_SaveAcc(9, 11, 15) Mul_Acc(12, 14) Mul_Acc(13, 13) Mul_Acc(14, 12) Mul_Acc(15, 11) \
1450 Mul_SaveAcc(10, 12, 15) Mul_Acc(13, 14) Mul_Acc(14, 13) Mul_Acc(15, 12) \
1451 Mul_SaveAcc(11, 13, 15) Mul_Acc(14, 14) Mul_Acc(15, 13) \
1452 Mul_SaveAcc(12, 14, 15) Mul_Acc(15, 14) \
1453 Mul_End(13, 15)
1454 }
1455 #endif
1456
1457 // ********************************************************
1458
1459 #if CRYPTOPP_INTEGER_SSE2
1460
1461 CRYPTOPP_ALIGN_DATA(16)
1462 CRYPTOPP_TABLE
1463 const word32 s_maskLow16[4] = {
1464 0xffff,0xffff,0xffff,0xffff
1465 };
1466
1467 #undef Mul_Begin
1468 #undef Mul_Acc
1469 #undef Top_Begin
1470 #undef Top_Acc
1471 #undef Squ_Acc
1472 #undef Squ_NonDiag
1473 #undef Squ_Diag
1474 #undef Squ_SaveAcc
1475 #undef Squ_Begin
1476 #undef Mul_SaveAcc
1477 #undef Bot_Acc
1478 #undef Bot_SaveAcc
1479 #undef Bot_End
1480 #undef Squ_End
1481 #undef Mul_End
1482
1483 #define SSE2_FinalSave(k) \
1484 AS2( psllq xmm5, 16) \
1485 AS2( paddq xmm4, xmm5) \
1486 AS2( movq QWORD PTR [ecx+8*(k)], xmm4)
1487
1488 #define SSE2_SaveShift(k) \
1489 AS2( movq xmm0, xmm6) \
1490 AS2( punpckhqdq xmm6, xmm0) \
1491 AS2( movq xmm1, xmm7) \
1492 AS2( punpckhqdq xmm7, xmm1) \
1493 AS2( paddd xmm6, xmm0) \
1494 AS2( pslldq xmm6, 4) \
1495 AS2( paddd xmm7, xmm1) \
1496 AS2( paddd xmm4, xmm6) \
1497 AS2( pslldq xmm7, 4) \
1498 AS2( movq xmm6, xmm4) \
1499 AS2( paddd xmm5, xmm7) \
1500 AS2( movq xmm7, xmm5) \
1501 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1502 AS2( psrlq xmm6, 16) \
1503 AS2( paddq xmm6, xmm7) \
1504 AS2( punpckhqdq xmm4, xmm0) \
1505 AS2( punpckhqdq xmm5, xmm0) \
1506 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm6) \
1507 AS2( psrlq xmm6, 3*16) \
1508 AS2( paddd xmm4, xmm6) \
1509
1510 #define Squ_SSE2_SaveShift(k) \
1511 AS2( movq xmm0, xmm6) \
1512 AS2( punpckhqdq xmm6, xmm0) \
1513 AS2( movq xmm1, xmm7) \
1514 AS2( punpckhqdq xmm7, xmm1) \
1515 AS2( paddd xmm6, xmm0) \
1516 AS2( pslldq xmm6, 4) \
1517 AS2( paddd xmm7, xmm1) \
1518 AS2( paddd xmm4, xmm6) \
1519 AS2( pslldq xmm7, 4) \
1520 AS2( movhlps xmm6, xmm4) \
1521 AS2( movd DWORD PTR [ecx+8*(k)], xmm4) \
1522 AS2( paddd xmm5, xmm7) \
1523 AS2( movhps QWORD PTR [esp+12], xmm5)\
1524 AS2( psrlq xmm4, 16) \
1525 AS2( paddq xmm4, xmm5) \
1526 AS2( movq QWORD PTR [ecx+8*(k)+2], xmm4) \
1527 AS2( psrlq xmm4, 3*16) \
1528 AS2( paddd xmm4, xmm6) \
1529 AS2( movq QWORD PTR [esp+4], xmm4)\
1530
1531 #define SSE2_FirstMultiply(i) \
1532 AS2( movdqa xmm7, [esi+(i)*16])\
1533 AS2( movdqa xmm5, [edi-(i)*16])\
1534 AS2( pmuludq xmm5, xmm7) \
1535 AS2( movdqa xmm4, [ebx])\
1536 AS2( movdqa xmm6, xmm4) \
1537 AS2( pand xmm4, xmm5) \
1538 AS2( psrld xmm5, 16) \
1539 AS2( pmuludq xmm7, [edx-(i)*16])\
1540 AS2( pand xmm6, xmm7) \
1541 AS2( psrld xmm7, 16)
1542
1543 #define Squ_Begin(n) \
1544 SquPrologue \
1545 AS2( mov esi, esp)\
1546 AS2( and esp, 0xfffffff0)\
1547 AS2( lea edi, [esp-32*n])\
1548 AS2( sub esp, 32*n+16)\
1549 AS1( push esi)\
1550 AS2( mov esi, edi) \
1551 AS2( xor edx, edx) \
1552 ASL(1) \
1553 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1554 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1555 AS2( movdqa [edi+2*edx], xmm0) \
1556 AS2( psrlq xmm0, 32) \
1557 AS2( movdqa [edi+2*edx+16], xmm0) \
1558 AS2( movdqa [edi+16*n+2*edx], xmm1) \
1559 AS2( psrlq xmm1, 32) \
1560 AS2( movdqa [edi+16*n+2*edx+16], xmm1) \
1561 AS2( add edx, 16) \
1562 AS2( cmp edx, 8*(n)) \
1563 ASJ( jne, 1, b) \
1564 AS2( lea edx, [edi+16*n])\
1565 SSE2_FirstMultiply(0) \
1566
1567 #define Squ_Acc(i) \
1568 ASL(LSqu##i) \
1569 AS2( movdqa xmm1, [esi+(i)*16]) \
1570 AS2( movdqa xmm0, [edi-(i)*16]) \
1571 AS2( movdqa xmm2, [ebx]) \
1572 AS2( pmuludq xmm0, xmm1) \
1573 AS2( pmuludq xmm1, [edx-(i)*16]) \
1574 AS2( movdqa xmm3, xmm2) \
1575 AS2( pand xmm2, xmm0) \
1576 AS2( psrld xmm0, 16) \
1577 AS2( paddd xmm4, xmm2) \
1578 AS2( paddd xmm5, xmm0) \
1579 AS2( pand xmm3, xmm1) \
1580 AS2( psrld xmm1, 16) \
1581 AS2( paddd xmm6, xmm3) \
1582 AS2( paddd xmm7, xmm1) \
1583
1584 #define Squ_Acc1(i)
1585 #define Squ_Acc2(i) ASC(call, LSqu##i)
1586 #define Squ_Acc3(i) Squ_Acc2(i)
1587 #define Squ_Acc4(i) Squ_Acc2(i)
1588 #define Squ_Acc5(i) Squ_Acc2(i)
1589 #define Squ_Acc6(i) Squ_Acc2(i)
1590 #define Squ_Acc7(i) Squ_Acc2(i)
1591 #define Squ_Acc8(i) Squ_Acc2(i)
1592
1593 #define SSE2_End(E, n) \
1594 SSE2_SaveShift(2*(n)-3) \
1595 AS2( movdqa xmm7, [esi+16]) \
1596 AS2( movdqa xmm0, [edi]) \
1597 AS2( pmuludq xmm0, xmm7) \
1598 AS2( movdqa xmm2, [ebx]) \
1599 AS2( pmuludq xmm7, [edx]) \
1600 AS2( movdqa xmm6, xmm2) \
1601 AS2( pand xmm2, xmm0) \
1602 AS2( psrld xmm0, 16) \
1603 AS2( paddd xmm4, xmm2) \
1604 AS2( paddd xmm5, xmm0) \
1605 AS2( pand xmm6, xmm7) \
1606 AS2( psrld xmm7, 16) \
1607 SSE2_SaveShift(2*(n)-2) \
1608 SSE2_FinalSave(2*(n)-1) \
1609 AS1( pop esp)\
1610 E
1611
1612 #define Squ_End(n) SSE2_End(SquEpilogue, n)
1613 #define Mul_End(n) SSE2_End(MulEpilogue, n)
1614 #define Top_End(n) SSE2_End(TopEpilogue, n)
1615
1616 #define Squ_Column1(k, i) \
1617 Squ_SSE2_SaveShift(k) \
1618 AS2( add esi, 16) \
1619 SSE2_FirstMultiply(1)\
1620 Squ_Acc##i(i) \
1621 AS2( paddd xmm4, xmm4) \
1622 AS2( paddd xmm5, xmm5) \
1623 AS2( movdqa xmm3, [esi]) \
1624 AS2( movq xmm1, QWORD PTR [esi+8]) \
1625 AS2( pmuludq xmm1, xmm3) \
1626 AS2( pmuludq xmm3, xmm3) \
1627 AS2( movdqa xmm0, [ebx])\
1628 AS2( movdqa xmm2, xmm0) \
1629 AS2( pand xmm0, xmm1) \
1630 AS2( psrld xmm1, 16) \
1631 AS2( paddd xmm6, xmm0) \
1632 AS2( paddd xmm7, xmm1) \
1633 AS2( pand xmm2, xmm3) \
1634 AS2( psrld xmm3, 16) \
1635 AS2( paddd xmm6, xmm6) \
1636 AS2( paddd xmm7, xmm7) \
1637 AS2( paddd xmm4, xmm2) \
1638 AS2( paddd xmm5, xmm3) \
1639 AS2( movq xmm0, QWORD PTR [esp+4])\
1640 AS2( movq xmm1, QWORD PTR [esp+12])\
1641 AS2( paddd xmm4, xmm0)\
1642 AS2( paddd xmm5, xmm1)\
1643
1644 #define Squ_Column0(k, i) \
1645 Squ_SSE2_SaveShift(k) \
1646 AS2( add edi, 16) \
1647 AS2( add edx, 16) \
1648 SSE2_FirstMultiply(1)\
1649 Squ_Acc##i(i) \
1650 AS2( paddd xmm6, xmm6) \
1651 AS2( paddd xmm7, xmm7) \
1652 AS2( paddd xmm4, xmm4) \
1653 AS2( paddd xmm5, xmm5) \
1654 AS2( movq xmm0, QWORD PTR [esp+4])\
1655 AS2( movq xmm1, QWORD PTR [esp+12])\
1656 AS2( paddd xmm4, xmm0)\
1657 AS2( paddd xmm5, xmm1)\
1658
1659 #define SSE2_MulAdd45 \
1660 AS2( movdqa xmm7, [esi]) \
1661 AS2( movdqa xmm0, [edi]) \
1662 AS2( pmuludq xmm0, xmm7) \
1663 AS2( movdqa xmm2, [ebx]) \
1664 AS2( pmuludq xmm7, [edx]) \
1665 AS2( movdqa xmm6, xmm2) \
1666 AS2( pand xmm2, xmm0) \
1667 AS2( psrld xmm0, 16) \
1668 AS2( paddd xmm4, xmm2) \
1669 AS2( paddd xmm5, xmm0) \
1670 AS2( pand xmm6, xmm7) \
1671 AS2( psrld xmm7, 16)
1672
1673 #define Mul_Begin(n) \
1674 MulPrologue \
1675 AS2( mov esi, esp)\
1676 AS2( and esp, 0xfffffff0)\
1677 AS2( sub esp, 48*n+16)\
1678 AS1( push esi)\
1679 AS2( xor edx, edx) \
1680 ASL(1) \
1681 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1682 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1683 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1684 AS2( movdqa [esp+20+2*edx], xmm0) \
1685 AS2( psrlq xmm0, 32) \
1686 AS2( movdqa [esp+20+2*edx+16], xmm0) \
1687 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1688 AS2( psrlq xmm1, 32) \
1689 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1690 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1691 AS2( psrlq xmm2, 32) \
1692 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1693 AS2( add edx, 16) \
1694 AS2( cmp edx, 8*(n)) \
1695 ASJ( jne, 1, b) \
1696 AS2( lea edi, [esp+20])\
1697 AS2( lea edx, [esp+20+16*n])\
1698 AS2( lea esi, [esp+20+32*n])\
1699 SSE2_FirstMultiply(0) \
1700
1701 #define Mul_Acc(i) \
1702 ASL(LMul##i) \
1703 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1704 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1705 AS2( movdqa xmm2, [ebx]) \
1706 AS2( pmuludq xmm0, xmm1) \
1707 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1708 AS2( movdqa xmm3, xmm2) \
1709 AS2( pand xmm2, xmm0) \
1710 AS2( psrld xmm0, 16) \
1711 AS2( paddd xmm4, xmm2) \
1712 AS2( paddd xmm5, xmm0) \
1713 AS2( pand xmm3, xmm1) \
1714 AS2( psrld xmm1, 16) \
1715 AS2( paddd xmm6, xmm3) \
1716 AS2( paddd xmm7, xmm1) \
1717
1718 #define Mul_Acc1(i)
1719 #define Mul_Acc2(i) ASC(call, LMul##i)
1720 #define Mul_Acc3(i) Mul_Acc2(i)
1721 #define Mul_Acc4(i) Mul_Acc2(i)
1722 #define Mul_Acc5(i) Mul_Acc2(i)
1723 #define Mul_Acc6(i) Mul_Acc2(i)
1724 #define Mul_Acc7(i) Mul_Acc2(i)
1725 #define Mul_Acc8(i) Mul_Acc2(i)
1726 #define Mul_Acc9(i) Mul_Acc2(i)
1727 #define Mul_Acc10(i) Mul_Acc2(i)
1728 #define Mul_Acc11(i) Mul_Acc2(i)
1729 #define Mul_Acc12(i) Mul_Acc2(i)
1730 #define Mul_Acc13(i) Mul_Acc2(i)
1731 #define Mul_Acc14(i) Mul_Acc2(i)
1732 #define Mul_Acc15(i) Mul_Acc2(i)
1733 #define Mul_Acc16(i) Mul_Acc2(i)
1734
1735 #define Mul_Column1(k, i) \
1736 SSE2_SaveShift(k) \
1737 AS2( add esi, 16) \
1738 SSE2_MulAdd45\
1739 Mul_Acc##i(i) \
1740
1741 #define Mul_Column0(k, i) \
1742 SSE2_SaveShift(k) \
1743 AS2( add edi, 16) \
1744 AS2( add edx, 16) \
1745 SSE2_MulAdd45\
1746 Mul_Acc##i(i) \
1747
1748 #define Bot_Acc(i) \
1749 AS2( movdqa xmm1, [esi+i/2*(1-(i-2*(i/2))*2)*16]) \
1750 AS2( movdqa xmm0, [edi-i/2*(1-(i-2*(i/2))*2)*16]) \
1751 AS2( pmuludq xmm0, xmm1) \
1752 AS2( pmuludq xmm1, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1753 AS2( paddq xmm4, xmm0) \
1754 AS2( paddd xmm6, xmm1)
1755
1756 #define Bot_SaveAcc(k) \
1757 SSE2_SaveShift(k) \
1758 AS2( add edi, 16) \
1759 AS2( add edx, 16) \
1760 AS2( movdqa xmm6, [esi]) \
1761 AS2( movdqa xmm0, [edi]) \
1762 AS2( pmuludq xmm0, xmm6) \
1763 AS2( paddq xmm4, xmm0) \
1764 AS2( psllq xmm5, 16) \
1765 AS2( paddq xmm4, xmm5) \
1766 AS2( pmuludq xmm6, [edx])
1767
1768 #define Bot_End(n) \
1769 AS2( movhlps xmm7, xmm6) \
1770 AS2( paddd xmm6, xmm7) \
1771 AS2( psllq xmm6, 32) \
1772 AS2( paddd xmm4, xmm6) \
1773 AS2( movq QWORD PTR [ecx+8*((n)-1)], xmm4) \
1774 AS1( pop esp)\
1775 MulEpilogue
1776
1777 #define Top_Begin(n) \
1778 TopPrologue \
1779 AS2( mov edx, esp)\
1780 AS2( and esp, 0xfffffff0)\
1781 AS2( sub esp, 48*n+16)\
1782 AS1( push edx)\
1783 AS2( xor edx, edx) \
1784 ASL(1) \
1785 ASS( pshufd xmm0, [eax+edx], 3,1,2,0) \
1786 ASS( pshufd xmm1, [eax+edx], 2,0,3,1) \
1787 ASS( pshufd xmm2, [edi+edx], 3,1,2,0) \
1788 AS2( movdqa [esp+20+2*edx], xmm0) \
1789 AS2( psrlq xmm0, 32) \
1790 AS2( movdqa [esp+20+2*edx+16], xmm0) \
1791 AS2( movdqa [esp+20+16*n+2*edx], xmm1) \
1792 AS2( psrlq xmm1, 32) \
1793 AS2( movdqa [esp+20+16*n+2*edx+16], xmm1) \
1794 AS2( movdqa [esp+20+32*n+2*edx], xmm2) \
1795 AS2( psrlq xmm2, 32) \
1796 AS2( movdqa [esp+20+32*n+2*edx+16], xmm2) \
1797 AS2( add edx, 16) \
1798 AS2( cmp edx, 8*(n)) \
1799 ASJ( jne, 1, b) \
1800 AS2( mov eax, esi) \
1801 AS2( lea edi, [esp+20+00*n+16*(n/2-1)])\
1802 AS2( lea edx, [esp+20+16*n+16*(n/2-1)])\
1803 AS2( lea esi, [esp+20+32*n+16*(n/2-1)])\
1804 AS2( pxor xmm4, xmm4)\
1805 AS2( pxor xmm5, xmm5)
1806
1807 #define Top_Acc(i) \
1808 AS2( movq xmm0, QWORD PTR [esi+i/2*(1-(i-2*(i/2))*2)*16+8]) \
1809 AS2( pmuludq xmm0, [edx-i/2*(1-(i-2*(i/2))*2)*16]) \
1810 AS2( psrlq xmm0, 48) \
1811 AS2( paddd xmm5, xmm0)\
1812
1813 #define Top_Column0(i) \
1814 AS2( psllq xmm5, 32) \
1815 AS2( add edi, 16) \
1816 AS2( add edx, 16) \
1817 SSE2_MulAdd45\
1818 Mul_Acc##i(i) \
1819
1820 #define Top_Column1(i) \
1821 SSE2_SaveShift(0) \
1822 AS2( add esi, 16) \
1823 SSE2_MulAdd45\
1824 Mul_Acc##i(i) \
1825 AS2( shr eax, 16) \
1826 AS2( movd xmm0, eax)\
1827 AS2( movd xmm1, [ecx+4])\
1828 AS2( psrld xmm1, 16)\
1829 AS2( pcmpgtd xmm1, xmm0)\
1830 AS2( psrld xmm1, 31)\
1831 AS2( paddd xmm4, xmm1)\
1832
1833 void SSE2_Square4(word *C, const word *A)
1834 {
1835 Squ_Begin(2)
1836 Squ_Column0(0, 1)
1837 Squ_End(2)
1838 }
1839
1840 void SSE2_Square8(word *C, const word *A)
1841 {
1842 Squ_Begin(4)
1843 #ifndef __GNUC__
1844 ASJ( jmp, 0, f)
1845 Squ_Acc(2)
1846 AS1( ret) ASL(0)
1847 #endif
1848 Squ_Column0(0, 1)
1849 Squ_Column1(1, 1)
1850 Squ_Column0(2, 2)
1851 Squ_Column1(3, 1)
1852 Squ_Column0(4, 1)
1853 Squ_End(4)
1854 }
1855
1856 void SSE2_Square16(word *C, const word *A)
1857 {
1858 Squ_Begin(8)
1859 #ifndef __GNUC__
1860 ASJ( jmp, 0, f)
1861 Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1862 AS1( ret) ASL(0)
1863 #endif
1864 Squ_Column0(0, 1)
1865 Squ_Column1(1, 1)
1866 Squ_Column0(2, 2)
1867 Squ_Column1(3, 2)
1868 Squ_Column0(4, 3)
1869 Squ_Column1(5, 3)
1870 Squ_Column0(6, 4)
1871 Squ_Column1(7, 3)
1872 Squ_Column0(8, 3)
1873 Squ_Column1(9, 2)
1874 Squ_Column0(10, 2)
1875 Squ_Column1(11, 1)
1876 Squ_Column0(12, 1)
1877 Squ_End(8)
1878 }
1879
1880 void SSE2_Square32(word *C, const word *A)
1881 {
1882 Squ_Begin(16)
1883 ASJ( jmp, 0, f)
1884 Squ_Acc(8) Squ_Acc(7) Squ_Acc(6) Squ_Acc(5) Squ_Acc(4) Squ_Acc(3) Squ_Acc(2)
1885 AS1( ret) ASL(0)
1886 Squ_Column0(0, 1)
1887 Squ_Column1(1, 1)
1888 Squ_Column0(2, 2)
1889 Squ_Column1(3, 2)
1890 Squ_Column0(4, 3)
1891 Squ_Column1(5, 3)
1892 Squ_Column0(6, 4)
1893 Squ_Column1(7, 4)
1894 Squ_Column0(8, 5)
1895 Squ_Column1(9, 5)
1896 Squ_Column0(10, 6)
1897 Squ_Column1(11, 6)
1898 Squ_Column0(12, 7)
1899 Squ_Column1(13, 7)
1900 Squ_Column0(14, 8)
1901 Squ_Column1(15, 7)
1902 Squ_Column0(16, 7)
1903 Squ_Column1(17, 6)
1904 Squ_Column0(18, 6)
1905 Squ_Column1(19, 5)
1906 Squ_Column0(20, 5)
1907 Squ_Column1(21, 4)
1908 Squ_Column0(22, 4)
1909 Squ_Column1(23, 3)
1910 Squ_Column0(24, 3)
1911 Squ_Column1(25, 2)
1912 Squ_Column0(26, 2)
1913 Squ_Column1(27, 1)
1914 Squ_Column0(28, 1)
1915 Squ_End(16)
1916 }
1917
1918 void SSE2_Multiply4(word *C, const word *A, const word *B)
1919 {
1920 Mul_Begin(2)
1921 #ifndef __GNUC__
1922 ASJ( jmp, 0, f)
1923 Mul_Acc(2)
1924 AS1( ret) ASL(0)
1925 #endif
1926 Mul_Column0(0, 2)
1927 Mul_End(2)
1928 }
1929
1930 void SSE2_Multiply8(word *C, const word *A, const word *B)
1931 {
1932 Mul_Begin(4)
1933 #ifndef __GNUC__
1934 ASJ( jmp, 0, f)
1935 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1936 AS1( ret) ASL(0)
1937 #endif
1938 Mul_Column0(0, 2)
1939 Mul_Column1(1, 3)
1940 Mul_Column0(2, 4)
1941 Mul_Column1(3, 3)
1942 Mul_Column0(4, 2)
1943 Mul_End(4)
1944 }
1945
1946 void SSE2_Multiply16(word *C, const word *A, const word *B)
1947 {
1948 Mul_Begin(8)
1949 #ifndef __GNUC__
1950 ASJ( jmp, 0, f)
1951 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
1952 AS1( ret) ASL(0)
1953 #endif
1954 Mul_Column0(0, 2)
1955 Mul_Column1(1, 3)
1956 Mul_Column0(2, 4)
1957 Mul_Column1(3, 5)
1958 Mul_Column0(4, 6)
1959 Mul_Column1(5, 7)
1960 Mul_Column0(6, 8)
1961 Mul_Column1(7, 7)
1962 Mul_Column0(8, 6)
1963 Mul_Column1(9, 5)
1964 Mul_Column0(10, 4)
1965 Mul_Column1(11, 3)
1966 Mul_Column0(12, 2)
1967 Mul_End(8)
1968 }
1969
1970 void SSE2_Multiply32(word *C, const word *A, const word *B)
1971 {
1972 Mul_Begin(16)
1973 ASJ( jmp, 0, f)
1974 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)
1975 AS1( ret) ASL(0)
1976 Mul_Column0(0, 2)
1977 Mul_Column1(1, 3)
1978 Mul_Column0(2, 4)
1979 Mul_Column1(3, 5)
1980 Mul_Column0(4, 6)
1981 Mul_Column1(5, 7)
1982 Mul_Column0(6, 8)
1983 Mul_Column1(7, 9)
1984 Mul_Column0(8, 10)
1985 Mul_Column1(9, 11)
1986 Mul_Column0(10, 12)
1987 Mul_Column1(11, 13)
1988 Mul_Column0(12, 14)
1989 Mul_Column1(13, 15)
1990 Mul_Column0(14, 16)
1991 Mul_Column1(15, 15)
1992 Mul_Column0(16, 14)
1993 Mul_Column1(17, 13)
1994 Mul_Column0(18, 12)
1995 Mul_Column1(19, 11)
1996 Mul_Column0(20, 10)
1997 Mul_Column1(21, 9)
1998 Mul_Column0(22, 8)
1999 Mul_Column1(23, 7)
2000 Mul_Column0(24, 6)
2001 Mul_Column1(25, 5)
2002 Mul_Column0(26, 4)
2003 Mul_Column1(27, 3)
2004 Mul_Column0(28, 2)
2005 Mul_End(16)
2006 }
2007
2008 void SSE2_MultiplyBottom4(word *C, const word *A, const word *B)
2009 {
2010 Mul_Begin(2)
2011 Bot_SaveAcc(0) Bot_Acc(2)
2012 Bot_End(2)
2013 }
2014
2015 void SSE2_MultiplyBottom8(word *C, const word *A, const word *B)
2016 {
2017 Mul_Begin(4)
2018 #ifndef __GNUC__
2019 ASJ( jmp, 0, f)
2020 Mul_Acc(3) Mul_Acc(2)
2021 AS1( ret) ASL(0)
2022 #endif
2023 Mul_Column0(0, 2)
2024 Mul_Column1(1, 3)
2025 Bot_SaveAcc(2) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
2026 Bot_End(4)
2027 }
2028
2029 void SSE2_MultiplyBottom16(word *C, const word *A, const word *B)
2030 {
2031 Mul_Begin(8)
2032 #ifndef __GNUC__
2033 ASJ( jmp, 0, f)
2034 Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
2035 AS1( ret) ASL(0)
2036 #endif
2037 Mul_Column0(0, 2)
2038 Mul_Column1(1, 3)
2039 Mul_Column0(2, 4)
2040 Mul_Column1(3, 5)
2041 Mul_Column0(4, 6)
2042 Mul_Column1(5, 7)
2043 Bot_SaveAcc(6) Bot_Acc(8) Bot_Acc(7) Bot_Acc(6) Bot_Acc(5) Bot_Acc(4) Bot_Acc(3) Bot_Acc(2)
2044 Bot_End(8)
2045 }
2046
2047 void SSE2_MultiplyBottom32(word *C, const word *A, const word *B)
2048 {
2049 Mul_Begin(16)
2050 #ifndef __GNUC__
2051 ASJ( jmp, 0, f)
2052 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)
2053 AS1( ret) ASL(0)
2054 #endif
2055 Mul_Column0(0, 2)
2056 Mul_Column1(1, 3)
2057 Mul_Column0(2, 4)
2058 Mul_Column1(3, 5)
2059 Mul_Column0(4, 6)
2060 Mul_Column1(5, 7)
2061 Mul_Column0(6, 8)
2062 Mul_Column1(7, 9)
2063 Mul_Column0(8, 10)
2064 Mul_Column1(9, 11)
2065 Mul_Column0(10, 12)
2066 Mul_Column1(11, 13)
2067 Mul_Column0(12, 14)
2068 Mul_Column1(13, 15)
2069 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)
2070 Bot_End(16)
2071 }
2072
2073 void SSE2_MultiplyTop8(word *C, const word *A, const word *B, word L)
2074 {
2075 Top_Begin(4)
2076 Top_Acc(3) Top_Acc(2) Top_Acc(1)
2077 #ifndef __GNUC__
2078 ASJ( jmp, 0, f)
2079 Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
2080 AS1( ret) ASL(0)
2081 #endif
2082 Top_Column0(4)
2083 Top_Column1(3)
2084 Mul_Column0(0, 2)
2085 Top_End(2)
2086 }
2087
2088 void SSE2_MultiplyTop16(word *C, const word *A, const word *B, word L)
2089 {
2090 Top_Begin(8)
2091 Top_Acc(7) Top_Acc(6) Top_Acc(5) Top_Acc(4) Top_Acc(3) Top_Acc(2) Top_Acc(1)
2092 #ifndef __GNUC__
2093 ASJ( jmp, 0, f)
2094 Mul_Acc(8) Mul_Acc(7) Mul_Acc(6) Mul_Acc(5) Mul_Acc(4) Mul_Acc(3) Mul_Acc(2)
2095 AS1( ret) ASL(0)
2096 #endif
2097 Top_Column0(8)
2098 Top_Column1(7)
2099 Mul_Column0(0, 6)
2100 Mul_Column1(1, 5)
2101 Mul_Column0(2, 4)
2102 Mul_Column1(3, 3)
2103 Mul_Column0(4, 2)
2104 Top_End(4)
2105 }
2106
2107 void SSE2_MultiplyTop32(word *C, const word *A, const word *B, word L)
2108 {
2109 Top_Begin(16)
2110 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)
2111 #ifndef __GNUC__
2112 ASJ( jmp, 0, f)
2113 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)
2114 AS1( ret) ASL(0)
2115 #endif
2116 Top_Column0(16)
2117 Top_Column1(15)
2118 Mul_Column0(0, 14)
2119 Mul_Column1(1, 13)
2120 Mul_Column0(2, 12)
2121 Mul_Column1(3, 11)
2122 Mul_Column0(4, 10)
2123 Mul_Column1(5, 9)
2124 Mul_Column0(6, 8)
2125 Mul_Column1(7, 7)
2126 Mul_Column0(8, 6)
2127 Mul_Column1(9, 5)
2128 Mul_Column0(10, 4)
2129 Mul_Column1(11, 3)
2130 Mul_Column0(12, 2)
2131 Top_End(8)
2132 }
2133
2134 #endif // #if CRYPTOPP_INTEGER_SSE2
2135
2136 // ********************************************************
2137
2138 typedef int (CRYPTOPP_FASTCALL * PAdd)(size_t N, word *C, const word *A, const word *B);
2139 typedef void (* PMul)(word *C, const word *A, const word *B);
2140 typedef void (* PSqu)(word *C, const word *A);
2141 typedef void (* PMulTop)(word *C, const word *A, const word *B, word L);
2142
2143 #if CRYPTOPP_INTEGER_SSE2
2144 static PAdd s_pAdd = &Baseline_Add, s_pSub = &Baseline_Sub;
2145 static size_t s_recursionLimit = 8;
2146 #else
2147 static const size_t s_recursionLimit = 16;
2148 #endif // CRYPTOPP_INTEGER_SSE2
2149
2150 static PMul s_pMul[9], s_pBot[9];
2151 static PSqu s_pSqu[9];
2152 static PMulTop s_pTop[9];
2153
2154 void SetFunctionPointers()
2155 {
2156 s_pMul[0] = &Baseline_Multiply2;
2157 s_pBot[0] = &Baseline_MultiplyBottom2;
2158 s_pSqu[0] = &Baseline_Square2;
2159 s_pTop[0] = &Baseline_MultiplyTop2;
2160 s_pTop[1] = &Baseline_MultiplyTop4;
2161
2162 #if CRYPTOPP_INTEGER_SSE2
2163 if (HasSSE2())
2164 {
2165 if (IsP4())
2166 {
2167 s_pAdd = &SSE2_Add;
2168 s_pSub = &SSE2_Sub;
2169 }
2170
2171 s_recursionLimit = 32;
2172
2173 s_pMul[1] = &SSE2_Multiply4;
2174 s_pMul[2] = &SSE2_Multiply8;
2175 s_pMul[4] = &SSE2_Multiply16;
2176 s_pMul[8] = &SSE2_Multiply32;
2177
2178 s_pBot[1] = &SSE2_MultiplyBottom4;
2179 s_pBot[2] = &SSE2_MultiplyBottom8;
2180 s_pBot[4] = &SSE2_MultiplyBottom16;
2181 s_pBot[8] = &SSE2_MultiplyBottom32;
2182
2183 s_pSqu[1] = &SSE2_Square4;
2184 s_pSqu[2] = &SSE2_Square8;
2185 s_pSqu[4] = &SSE2_Square16;
2186 s_pSqu[8] = &SSE2_Square32;
2187
2188 s_pTop[2] = &SSE2_MultiplyTop8;
2189 s_pTop[4] = &SSE2_MultiplyTop16;
2190 s_pTop[8] = &SSE2_MultiplyTop32;
2191 }
2192 else
2193 #endif // CRYPTOPP_INTEGER_SSE2
2194 {
2195 s_pMul[1] = &Baseline_Multiply4;
2196 s_pMul[2] = &Baseline_Multiply8;
2197
2198 s_pBot[1] = &Baseline_MultiplyBottom4;
2199 s_pBot[2] = &Baseline_MultiplyBottom8;
2200
2201 s_pSqu[1] = &Baseline_Square4;
2202 s_pSqu[2] = &Baseline_Square8;
2203
2204 s_pTop[2] = &Baseline_MultiplyTop8;
2205
2206 #if !CRYPTOPP_INTEGER_SSE2
2207 s_pMul[4] = &Baseline_Multiply16;
2208 s_pBot[4] = &Baseline_MultiplyBottom16;
2209 s_pSqu[4] = &Baseline_Square16;
2210 s_pTop[4] = &Baseline_MultiplyTop16;
2211 #endif // !CRYPTOPP_INTEGER_SSE2
2212 }
2213 }
2214
2215 inline int Add(word *C, const word *A, const word *B, size_t N)
2216 {
2217 #if CRYPTOPP_INTEGER_SSE2
2218 return s_pAdd(N, C, A, B);
2219 #else
2220 return Baseline_Add(N, C, A, B);
2221 #endif // CRYPTOPP_INTEGER_SSE2
2222 }
2223
2224 inline int Subtract(word *C, const word *A, const word *B, size_t N)
2225 {
2226 #if CRYPTOPP_INTEGER_SSE2
2227 return s_pSub(N, C, A, B);
2228 #else
2229 return Baseline_Sub(N, C, A, B);
2230 #endif // CRYPTOPP_INTEGER_SSE2
2231 }
2232
2233 // ********************************************************
2234
2235
2236 #define A0 A
2237 #define A1 (A+N2)
2238 #define B0 B
2239 #define B1 (B+N2)
2240
2241 #define T0 T
2242 #define T1 (T+N2)
2243 #define T2 (T+N)
2244 #define T3 (T+N+N2)
2245
2246 #define R0 R
2247 #define R1 (R+N2)
2248 #define R2 (R+N)
2249 #define R3 (R+N+N2)
2250
2251 // R[2*N] - result = A*B
2252 // T[2*N] - temporary work space
2253 // A[N] --- multiplier
2254 // B[N] --- multiplicant
2255
2256 void RecursiveMultiply(word *R, word *T, const word *A, const word *B, size_t N)
2257 {
2258 CRYPTOPP_ASSERT(N>=2 && N%2==0);
2259
2260 if (N <= s_recursionLimit)
2261 s_pMul[N/4](R, A, B);
2262 else
2263 {
2264 const size_t N2 = N/2;
2265
2266 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2267 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2268
2269 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2270 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2271
2272 RecursiveMultiply(R2, T2, A1, B1, N2);
2273 RecursiveMultiply(T0, T2, R0, R1, N2);
2274 RecursiveMultiply(R0, T2, A0, B0, N2);
2275
2276 // now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1
2277
2278 int c2 = Add(R2, R2, R1, N2);
2279 int c3 = c2;
2280 c2 += Add(R1, R2, R0, N2);
2281 c3 += Add(R2, R2, R3, N2);
2282
2283 if (AN2 == BN2)
2284 c3 -= Subtract(R1, R1, T0, N);
2285 else
2286 c3 += Add(R1, R1, T0, N);
2287
2288 c3 += Increment(R2, N2, c2);
2289 CRYPTOPP_ASSERT (c3 >= 0 && c3 <= 2);
2290 Increment(R3, N2, c3);
2291 }
2292 }
2293
2294 // R[2*N] - result = A*A
2295 // T[2*N] - temporary work space
2296 // A[N] --- number to be squared
2297
2298 void RecursiveSquare(word *R, word *T, const word *A, size_t N)
2299 {
2300 CRYPTOPP_ASSERT(N && N%2==0);
2301
2302 if (N <= s_recursionLimit)
2303 s_pSqu[N/4](R, A);
2304 else
2305 {
2306 const size_t N2 = N/2;
2307
2308 RecursiveSquare(R0, T2, A0, N2);
2309 RecursiveSquare(R2, T2, A1, N2);
2310 RecursiveMultiply(T0, T2, A0, A1, N2);
2311
2312 int carry = Add(R1, R1, T0, N);
2313 carry += Add(R1, R1, T0, N);
2314 Increment(R3, N2, carry);
2315 }
2316 }
2317
2318 // R[N] - bottom half of A*B
2319 // T[3*N/2] - temporary work space
2320 // A[N] - multiplier
2321 // B[N] - multiplicant
2322
2323 void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N)
2324 {
2325 CRYPTOPP_ASSERT(N>=2 && N%2==0);
2326
2327 if (N <= s_recursionLimit)
2328 s_pBot[N/4](R, A, B);
2329 else
2330 {
2331 const size_t N2 = N/2;
2332
2333 RecursiveMultiply(R, T, A0, B0, N2);
2334 RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
2335 Add(R1, R1, T0, N2);
2336 RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
2337 Add(R1, R1, T0, N2);
2338 }
2339 }
2340
2341 // R[N] --- upper half of A*B
2342 // T[2*N] - temporary work space
2343 // L[N] --- lower half of A*B
2344 // A[N] --- multiplier
2345 // B[N] --- multiplicant
2346
2347 void MultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
2348 {
2349 CRYPTOPP_ASSERT(N>=2 && N%2==0);
2350
2351 if (N <= s_recursionLimit)
2352 s_pTop[N/4](R, A, B, L[N-1]);
2353 else
2354 {
2355 const size_t N2 = N/2;
2356
2357 size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2;
2358 Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);
2359
2360 size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2;
2361 Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);
2362
2363 RecursiveMultiply(T0, T2, R0, R1, N2);
2364 RecursiveMultiply(R0, T2, A1, B1, N2);
2365
2366 // now T[01] holds (A1-A0)*(B0-B1) = A1*B0+A0*B1-A1*B1-A0*B0, R[01] holds A1*B1
2367
2368 int t, c3;
2369 int c2 = Subtract(T2, L+N2, L, N2);
2370
2371 if (AN2 == BN2)
2372 {
2373 c2 -= Add(T2, T2, T0, N2);
2374 t = (Compare(T2, R0, N2) == -1);
2375 c3 = t - Subtract(T2, T2, T1, N2);
2376 }
2377 else
2378 {
2379 c2 += Subtract(T2, T2, T0, N2);
2380 t = (Compare(T2, R0, N2) == -1);
2381 c3 = t + Add(T2, T2, T1, N2);
2382 }
2383
2384 c2 += t;
2385 if (c2 >= 0)
2386 c3 += Increment(T2, N2, c2);
2387 else
2388 c3 -= Decrement(T2, N2, -c2);
2389 c3 += Add(R0, T2, R1, N2);
2390
2391 CRYPTOPP_ASSERT (c3 >= 0 && c3 <= 2);
2392 Increment(R1, N2, c3);
2393 }
2394 }
2395
2396 inline void Multiply(word *R, word *T, const word *A, const word *B, size_t N)
2397 {
2398 RecursiveMultiply(R, T, A, B, N);
2399 }
2400
2401 inline void Square(word *R, word *T, const word *A, size_t N)
2402 {
2403 RecursiveSquare(R, T, A, N);
2404 }
2405
2406 inline void MultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N)
2407 {
2408 RecursiveMultiplyBottom(R, T, A, B, N);
2409 }
2410
2411 // R[NA+NB] - result = A*B
2412 // T[NA+NB] - temporary work space
2413 // A[NA] ---- multiplier
2414 // B[NB] ---- multiplicant
2415
2416 void AsymmetricMultiply(word *R, word *T, const word *A, size_t NA, const word *B, size_t NB)
2417 {
2418 if (NA == NB)
2419 {
2420 // Profiling tells us the original second case was dominant, so it was promoted to the first If statement.
2421 // The code change occurred at Commit dc99266599a0e72d.
2422 if (A != B)
2423 Multiply(R, T, A, B, NA);
2424 else
2425 Square(R, T, A, NA);
2426
2427 return;
2428 }
2429
2430 if (NA > NB)
2431 {
2432 std::swap(A, B);
2433 std::swap(NA, NB);
2434 }
2435
2436 CRYPTOPP_ASSERT(NB % NA == 0);
2437
2438 if (NA==2 && !A[1])
2439 {
2440 // Profiling tells us the original Default case was dominant, so it was promoted to the first Case statement.
2441 // The code change occurred at Commit dc99266599a0e72d.
2442 switch (A[0])
2443 {
2444 default:
2445 R[NB] = LinearMultiply(R, B, A[0], NB);
2446 R[NB+1] = 0;
2447 return;
2448 case 0:
2449 SetWords(R, 0, NB+2);
2450 return;
2451 case 1:
2452 CopyWords(R, B, NB);
2453 R[NB] = R[NB+1] = 0;
2454 return;
2455 }
2456 }
2457
2458 size_t i;
2459 if ((NB/NA)%2 == 0)
2460 {
2461 Multiply(R, T, A, B, NA);
2462 CopyWords(T+2*NA, R+NA, NA);
2463
2464 for (i=2*NA; i<NB; i+=2*NA)
2465 Multiply(T+NA+i, T, A, B+i, NA);
2466 for (i=NA; i<NB; i+=2*NA)
2467 Multiply(R+i, T, A, B+i, NA);
2468 }
2469 else
2470 {
2471 for (i=0; i<NB; i+=2*NA)
2472 Multiply(R+i, T, A, B+i, NA);
2473 for (i=NA; i<NB; i+=2*NA)
2474 Multiply(T+NA+i, T, A, B+i, NA);
2475 }
2476
2477 if (Add(R+NA, R+NA, T+2*NA, NB-NA))
2478 Increment(R+NB, NA);
2479 }
2480
2481 // R[N] ----- result = A inverse mod 2**(WORD_BITS*N)
2482 // T[3*N/2] - temporary work space
2483 // A[N] ----- an odd number as input
2484
2485 void RecursiveInverseModPower2(word *R, word *T, const word *A, size_t N)
2486 {
2487 // Profiling tells us the original Else was dominant, so it was promoted to the first If statement.
2488 // The code change occurred at Commit dc99266599a0e72d.
2489 if (N!=2)
2490 {
2491 const size_t N2 = N/2;
2492 RecursiveInverseModPower2(R0, T0, A0, N2);
2493 T0[0] = 1;
2494 SetWords(T0+1, 0, N2-1);
2495 MultiplyTop(R1, T1, T0, R0, A0, N2);
2496 MultiplyBottom(T0, T1, R0, A1, N2);
2497 Add(T0, R1, T0, N2);
2498 TwosComplement(T0, N2);
2499 MultiplyBottom(R1, T1, R0, T0, N2);
2500 }
2501 else
2502 {
2503 T[0] = AtomicInverseModPower2(A[0]);
2504 T[1] = 0;
2505 s_pBot[0](T+2, T, A);
2506 TwosComplement(T+2, 2);
2507 Increment(T+2, 2, 2);
2508 s_pBot[0](R, T, T+2);
2509 }
2510 }
2511
2512 // R[N] --- result = X/(2**(WORD_BITS*N)) mod M
2513 // T[3*N] - temporary work space
2514 // X[2*N] - number to be reduced
2515 // M[N] --- modulus
2516 // U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)
2517
2518 void MontgomeryReduce(word *R, word *T, word *X, const word *M, const word *U, size_t N)
2519 {
2520 #if 1
2521 MultiplyBottom(R, T, X, U, N);
2522 MultiplyTop(T, T+N, X, R, M, N);
2523 word borrow = Subtract(T, X+N, T, N);
2524 // defend against timing attack by doing this Add even when not needed
2525 word carry = Add(T+N, T, M, N);
2526 CRYPTOPP_ASSERT(carry | !borrow);
2527 CRYPTOPP_UNUSED(carry), CRYPTOPP_UNUSED(borrow);
2528 CopyWords(R, T + ((0-borrow) & N), N);
2529 #elif 0
2530 const word u = 0-U[0];
2531 Declare2Words(p)
2532 for (size_t i=0; i<N; i++)
2533 {
2534 const word t = u * X[i];
2535 word c = 0;
2536 for (size_t j=0; j<N; j+=2)
2537 {
2538 MultiplyWords(p, t, M[j]);
2539 Acc2WordsBy1(p, X[i+j]);
2540 Acc2WordsBy1(p, c);
2541 X[i+j] = LowWord(p);
2542 c = HighWord(p);
2543 MultiplyWords(p, t, M[j+1]);
2544 Acc2WordsBy1(p, X[i+j+1]);
2545 Acc2WordsBy1(p, c);
2546 X[i+j+1] = LowWord(p);
2547 c = HighWord(p);
2548 }
2549
2550 if (Increment(X+N+i, N-i, c))
2551 while (!Subtract(X+N, X+N, M, N)) {}
2552 }
2553
2554 memcpy(R, X+N, N*WORD_SIZE);
2555 #else
2556 __m64 u = _mm_cvtsi32_si64(0-U[0]), p;
2557 for (size_t i=0; i<N; i++)
2558 {
2559 __m64 t = _mm_cvtsi32_si64(X[i]);
2560 t = _mm_mul_su32(t, u);
2561 __m64 c = _mm_setzero_si64();
2562 for (size_t j=0; j<N; j+=2)
2563 {
2564 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j]));
2565 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j]));
2566 c = _mm_add_si64(c, p);
2567 X[i+j] = _mm_cvtsi64_si32(c);
2568 c = _mm_srli_si64(c, 32);
2569 p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1]));
2570 p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1]));
2571 c = _mm_add_si64(c, p);
2572 X[i+j+1] = _mm_cvtsi64_si32(c);
2573 c = _mm_srli_si64(c, 32);
2574 }
2575
2576 if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c)))
2577 while (!Subtract(X+N, X+N, M, N)) {}
2578 }
2579
2580 memcpy(R, X+N, N*WORD_SIZE);
2581 _mm_empty();
2582 #endif
2583 }
2584
2585 // R[N] --- result = X/(2**(WORD_BITS*N/2)) mod M
2586 // T[2*N] - temporary work space
2587 // X[2*N] - number to be reduced
2588 // M[N] --- modulus
2589 // U[N/2] - multiplicative inverse of M mod 2**(WORD_BITS*N/2)
2590 // V[N] --- 2**(WORD_BITS*3*N/2) mod M
2591
2592 void HalfMontgomeryReduce(word *R, word *T, const word *X, const word *M, const word *U, const word *V, size_t N)
2593 {
2594 CRYPTOPP_ASSERT(N%2==0 && N>=4);
2595
2596 #define M0 M
2597 #define M1 (M+N2)
2598 #define V0 V
2599 #define V1 (V+N2)
2600
2601 #define X0 X
2602 #define X1 (X+N2)
2603 #define X2 (X+N)
2604 #define X3 (X+N+N2)
2605
2606 const size_t N2 = N/2;
2607 Multiply(T0, T2, V0, X3, N2);
2608 int c2 = Add(T0, T0, X0, N);
2609 MultiplyBottom(T3, T2, T0, U, N2);
2610 MultiplyTop(T2, R, T0, T3, M0, N2);
2611 c2 -= Subtract(T2, T1, T2, N2);
2612 Multiply(T0, R, T3, M1, N2);
2613 c2 -= Subtract(T0, T2, T0, N2);
2614 int c3 = -(int)Subtract(T1, X2, T1, N2);
2615 Multiply(R0, T2, V1, X3, N2);
2616 c3 += Add(R, R, T, N);
2617
2618 if (c2>0)
2619 c3 += Increment(R1, N2);
2620 else if (c2<0)
2621 c3 -= Decrement(R1, N2, -c2);
2622
2623 CRYPTOPP_ASSERT(c3>=-1 && c3<=1);
2624 if (c3>0)
2625 Subtract(R, R, M, N);
2626 else if (c3<0)
2627 Add(R, R, M, N);
2628
2629 #undef M0
2630 #undef M1
2631 #undef V0
2632 #undef V1
2633
2634 #undef X0
2635 #undef X1
2636 #undef X2
2637 #undef X3
2638 }
2639
2640 #undef A0
2641 #undef A1
2642 #undef B0
2643 #undef B1
2644
2645 #undef T0
2646 #undef T1
2647 #undef T2
2648 #undef T3
2649
2650 #undef R0
2651 #undef R1
2652 #undef R2
2653 #undef R3
2654
2655 /*
2656 // do a 3 word by 2 word divide, returns quotient and leaves remainder in A
2657 static word SubatomicDivide(word *A, word B0, word B1)
2658 {
2659 // Assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a word
2660 CRYPTOPP_ASSERT(A[2] < B1 || (A[2]==B1 && A[1] < B0));
2661
2662 // estimate the quotient: do a 2 word by 1 word divide
2663 word Q;
2664 if (B1+1 == 0)
2665 Q = A[2];
2666 else
2667 Q = DWord(A[1], A[2]).DividedBy(B1+1);
2668
2669 // now subtract Q*B from A
2670 DWord p = DWord::Multiply(B0, Q);
2671 DWord u = (DWord) A[0] - p.GetLowHalf();
2672 A[0] = u.GetLowHalf();
2673 u = (DWord) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - DWord::Multiply(B1, Q);
2674 A[1] = u.GetLowHalf();
2675 A[2] += u.GetHighHalf();
2676
2677 // Q <= actual quotient, so fix it
2678 while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
2679 {
2680 u = (DWord) A[0] - B0;
2681 A[0] = u.GetLowHalf();
2682 u = (DWord) A[1] - B1 - u.GetHighHalfAsBorrow();
2683 A[1] = u.GetLowHalf();
2684 A[2] += u.GetHighHalf();
2685 Q++;
2686 CRYPTOPP_ASSERT(Q); // shouldn't overflow
2687 }
2688
2689 return Q;
2690 }
2691
2692 // do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
2693 static inline void AtomicDivide(word *Q, const word *A, const word *B)
2694 {
2695 if (!B[0] && !B[1]) // if divisor is 0, we assume divisor==2**(2*WORD_BITS)
2696 {
2697 Q[0] = A[2];
2698 Q[1] = A[3];
2699 }
2700 else
2701 {
2702 word T[4];
2703 T[0] = A[0]; T[1] = A[1]; T[2] = A[2]; T[3] = A[3];
2704 Q[1] = SubatomicDivide(T+1, B[0], B[1]);
2705 Q[0] = SubatomicDivide(T, B[0], B[1]);
2706
2707 #if defined(CRYPTOPP_DEBUG)
2708 // multiply quotient and divisor and add remainder, make sure it equals dividend
2709 CRYPTOPP_ASSERT(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2710 word P[4];
2711 LowLevel::Multiply2(P, Q, B);
2712 Add(P, P, T, 4);
2713 CRYPTOPP_ASSERT(memcmp(P, A, 4*WORD_SIZE)==0);
2714 #endif
2715 }
2716 }
2717 */
2718
2719 static inline void AtomicDivide(word *Q, const word *A, const word *B)
2720 {
2721 word T[4];
2722 DWord q = DivideFourWordsByTwo<word, DWord>(T, DWord(A[0], A[1]), DWord(A[2], A[3]), DWord(B[0], B[1]));
2723 Q[0] = q.GetLowHalf();
2724 Q[1] = q.GetHighHalf();
2725
2726 #if defined(CRYPTOPP_DEBUG)
2727 if (B[0] || B[1])
2728 {
2729 // multiply quotient and divisor and add remainder, make sure it equals dividend
2730 CRYPTOPP_ASSERT(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
2731 word P[4];
2732 s_pMul[0](P, Q, B);
2733 Add(P, P, T, 4);
2734 CRYPTOPP_ASSERT(memcmp(P, A, 4*WORD_SIZE)==0);
2735 }
2736 #endif
2737 }
2738
2739 // for use by Divide(), corrects the underestimated quotient {Q1,Q0}
2740 static void CorrectQuotientEstimate(word *R, word *T, word *Q, const word *B, size_t N)
2741 {
2742 CRYPTOPP_ASSERT(N && N%2==0);
2743
2744 AsymmetricMultiply(T, T+N+2, Q, 2, B, N);
2745
2746 word borrow = Subtract(R, R, T, N+2);
2747 CRYPTOPP_ASSERT(!borrow && !R[N+1]);
2748 CRYPTOPP_UNUSED(borrow);
2749
2750 while (R[N] || Compare(R, B, N) >= 0)
2751 {
2752 R[N] -= Subtract(R, R, B, N);
2753 Q[1] += (++Q[0]==0);
2754 CRYPTOPP_ASSERT(Q[0] || Q[1]); // no overflow
2755 }
2756 }
2757
2758 // R[NB] -------- remainder = A%B
2759 // Q[NA-NB+2] --- quotient = A/B
2760 // T[NA+3*(NB+2)] - temp work space
2761 // A[NA] -------- dividend
2762 // B[NB] -------- divisor
2763
2764 void Divide(word *R, word *Q, word *T, const word *A, size_t NA, const word *B, size_t NB)
2765 {
2766 CRYPTOPP_ASSERT(NA && NB && NA%2==0 && NB%2==0);
2767 CRYPTOPP_ASSERT(B[NB-1] || B[NB-2]);
2768 CRYPTOPP_ASSERT(NB <= NA);
2769
2770 // set up temporary work space
2771 word *const TA=T;
2772 word *const TB=T+NA+2;
2773 word *const TP=T+NA+2+NB;
2774
2775 // copy B into TB and normalize it so that TB has highest bit set to 1
2776 unsigned shiftWords = (B[NB-1]==0);
2777 TB[0] = TB[NB-1] = 0;
2778 CopyWords(TB+shiftWords, B, NB-shiftWords);
2779 unsigned shiftBits = WORD_BITS - BitPrecision(TB[NB-1]);
2780 CRYPTOPP_ASSERT(shiftBits < WORD_BITS);
2781 ShiftWordsLeftByBits(TB, NB, shiftBits);
2782
2783 // copy A into TA and normalize it
2784 TA[0] = TA[NA] = TA[NA+1] = 0;
2785 CopyWords(TA+shiftWords, A, NA);
2786 ShiftWordsLeftByBits(TA, NA+2, shiftBits);
2787
2788 if (TA[NA+1]==0 && TA[NA] <= 1)
2789 {
2790 Q[NA-NB+1] = Q[NA-NB] = 0;
2791 while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
2792 {
2793 TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
2794 ++Q[NA-NB];
2795 }
2796 }
2797 else
2798 {
2799 NA+=2;
2800 CRYPTOPP_ASSERT(Compare(TA+NA-NB, TB, NB) < 0);
2801 }
2802
2803 word BT[2];
2804 BT[0] = TB[NB-2] + 1;
2805 BT[1] = TB[NB-1] + (BT[0]==0);
2806
2807 // start reducing TA mod TB, 2 words at a time
2808 for (size_t i=NA-2; i>=NB; i-=2)
2809 {
2810 AtomicDivide(Q+i-NB, TA+i-2, BT);
2811 CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
2812 }
2813
2814 // copy TA into R, and denormalize it
2815 CopyWords(R, TA+shiftWords, NB);
2816 ShiftWordsRightByBits(R, NB, shiftBits);
2817 }
2818
2819 static inline size_t EvenWordCount(const word *X, size_t N)
2820 {
2821 while (N && X[N-2]==0 && X[N-1]==0)
2822 N-=2;
2823 return N;
2824 }
2825
2826 // return k
2827 // R[N] --- result = A^(-1) * 2^k mod M
2828 // T[4*N] - temporary work space
2829 // A[NA] -- number to take inverse of
2830 // M[N] --- modulus
2831
2832 unsigned int AlmostInverse(word *R, word *T, const word *A, size_t NA, const word *M, size_t N)
2833 {
2834 CRYPTOPP_ASSERT(NA<=N && N && N%2==0);
2835
2836 word *b = T;
2837 word *c = T+N;
2838 word *f = T+2*N;
2839 word *g = T+3*N;
2840 size_t bcLen=2, fgLen=EvenWordCount(M, N);
2841 unsigned int k=0;
2842 bool s=false;
2843
2844 SetWords(T, 0, 3*N);
2845 b[0]=1;
2846 CopyWords(f, A, NA);
2847 CopyWords(g, M, N);
2848
2849 while (1)
2850 {
2851 word t=f[0];
2852 while (!t)
2853 {
2854 if (EvenWordCount(f, fgLen)==0)
2855 {
2856 SetWords(R, 0, N);
2857 return 0;
2858 }
2859
2860 ShiftWordsRightByWords(f, fgLen, 1);
2861 bcLen += 2 * (c[bcLen-1] != 0);
2862 CRYPTOPP_ASSERT(bcLen <= N);
2863 ShiftWordsLeftByWords(c, bcLen, 1);
2864 k+=WORD_BITS;
2865 t=f[0];
2866 }
2867
2868 // t must be non-0; otherwise undefined.
2869 unsigned int i = TrailingZeros(t);
2870 t >>= i;
2871 k += i;
2872
2873 if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0)
2874 {
2875 if (s)
2876 Subtract(R, M, b, N);
2877 else
2878 CopyWords(R, b, N);
2879 return k;
2880 }
2881
2882 ShiftWordsRightByBits(f, fgLen, i);
2883 t = ShiftWordsLeftByBits(c, bcLen, i);
2884 c[bcLen] += t;
2885 bcLen += 2 * (t!=0);
2886 CRYPTOPP_ASSERT(bcLen <= N);
2887
2888 bool swap = Compare(f, g, fgLen)==-1;
2889 ConditionalSwapPointers(swap, f, g);
2890 ConditionalSwapPointers(swap, b, c);
2891 s ^= swap;
2892
2893 fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]);
2894
2895 Subtract(f, f, g, fgLen);
2896 t = Add(b, b, c, bcLen);
2897 b[bcLen] += t;
2898 bcLen += 2*t;
2899 CRYPTOPP_ASSERT(bcLen <= N);
2900 }
2901 }
2902
2903 // R[N] - result = A/(2^k) mod M
2904 // A[N] - input
2905 // M[N] - modulus
2906
2907 void DivideByPower2Mod(word *R, const word *A, size_t k, const word *M, size_t N)
2908 {
2909 CopyWords(R, A, N);
2910
2911 while (k--)
2912 {
2913 if (R[0]%2==0)
2914 ShiftWordsRightByBits(R, N, 1);
2915 else
2916 {
2917 word carry = Add(R, R, M, N);
2918 ShiftWordsRightByBits(R, N, 1);
2919 R[N-1] += carry<<(WORD_BITS-1);
2920 }
2921 }
2922 }
2923
2924 // R[N] - result = A*(2^k) mod M
2925 // A[N] - input
2926 // M[N] - modulus
2927
2928 void MultiplyByPower2Mod(word *R, const word *A, size_t k, const word *M, size_t N)
2929 {
2930 CopyWords(R, A, N);
2931
2932 while (k--)
2933 if (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0)
2934 Subtract(R, R, M, N);
2935 }
2936
2937 // ******************************************************************
2938
2939 static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
2940
2941 static inline size_t RoundupSize(size_t n)
2942 {
2943 if (n<=8)
2944 return RoundupSizeTable[n];
2945 else if (n<=16)
2946 return 16;
2947 else if (n<=32)
2948 return 32;
2949 else if (n<=64)
2950 return 64;
2951 else
2952 return size_t(1) << BitPrecision(n-1);
2953 }
2954
2955 Integer::Integer()
2956 : reg(2), sign(POSITIVE)
2957 {
2958 reg[0] = reg[1] = 0;
2959 }
2960
2961 Integer::Integer(const Integer& t)
2962 : reg(RoundupSize(t.WordCount())), sign(t.sign)
2963 {
2964 CopyWords(reg, t.reg, reg.size());
2965 }
2966
2967 Integer::Integer(Sign s, lword value)
2968 : reg(2), sign(s)
2969 {
2970 reg[0] = word(value);
2971 reg[1] = word(SafeRightShift<WORD_BITS>(value));
2972 }
2973
2974 Integer::Integer(signed long value)
2975 : reg(2)
2976 {
2977 if (value >= 0)
2978 sign = POSITIVE;
2979 else
2980 {
2981 sign = NEGATIVE;
2982 value = -value;
2983 }
2984 reg[0] = word(value);
2985 reg[1] = word(SafeRightShift<WORD_BITS>((unsigned long)value));
2986 }
2987
2988 Integer::Integer(Sign s, word high, word low)
2989 : reg(2), sign(s)
2990 {
2991 reg[0] = low;
2992 reg[1] = high;
2993 }
2994
2995 bool Integer::IsConvertableToLong() const
2996 {
2997 if (ByteCount() > sizeof(long))
2998 return false;
2999
3000 unsigned long value = (unsigned long)reg[0];
3001 value += SafeLeftShift<WORD_BITS, unsigned long>((unsigned long)reg[1]);
3002
3003 if (sign==POSITIVE)
3004 return (signed long)value >= 0;
3005 else
3006 return -(signed long)value < 0;
3007 }
3008
3009 signed long Integer::ConvertToLong() const
3010 {
3011 CRYPTOPP_ASSERT(IsConvertableToLong());
3012
3013 unsigned long value = (unsigned long)reg[0];
3014 value += SafeLeftShift<WORD_BITS, unsigned long>((unsigned long)reg[1]);
3015 return sign==POSITIVE ? value : -(signed long)value;
3016 }
3017
3018 Integer::Integer(BufferedTransformation &encodedInteger, size_t byteCount, Signedness s, ByteOrder o)
3019 {
3020 CRYPTOPP_ASSERT(o == BIG_ENDIAN_ORDER || o == LITTLE_ENDIAN_ORDER);
3021
3022 if (o != LITTLE_ENDIAN_ORDER)
3023 {
3024 Decode(encodedInteger, byteCount, s);
3025 }
3026 else
3027 {
3028 SecByteBlock block(byteCount);
3029 encodedInteger.Get(block, block.size());
3030 std::reverse(block.begin(), block.begin()+block.size());
3031
3032 Decode(block.begin(), block.size(), s);
3033 }
3034 }
3035
3036 Integer::Integer(const byte *encodedInteger, size_t byteCount, Signedness s, ByteOrder o)
3037 {
3038 CRYPTOPP_ASSERT(encodedInteger && byteCount); // NULL buffer
3039 CRYPTOPP_ASSERT(o == BIG_ENDIAN_ORDER || o == LITTLE_ENDIAN_ORDER);
3040
3041 if (o != LITTLE_ENDIAN_ORDER)
3042 {
3043 Decode(encodedInteger, byteCount, s);
3044 }
3045 else
3046 {
3047 SecByteBlock block(byteCount);
3048 #if (_MSC_VER >= 1500)
3049 std::reverse_copy(encodedInteger, encodedInteger+byteCount,
3050 stdext::make_checked_array_iterator(block.begin(), block.size()));
3051 #else
3052 std::reverse_copy(encodedInteger, encodedInteger+byteCount, block.begin());
3053 #endif
3054 Decode(block.begin(), block.size(), s);
3055 return;
3056 }
3057 }
3058
3059 Integer::Integer(BufferedTransformation &bt)
3060 {
3061 // Make explicit call to avoid virtual-dispatch findings in ctor
3062 Integer::BERDecode(bt);
3063 }
3064
3065 Integer::Integer(RandomNumberGenerator &rng, size_t bitcount)
3066 {
3067 Randomize(rng, bitcount);
3068 }
3069
3070 Integer::Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv, const Integer &mod)
3071 {
3072 if (!Randomize(rng, min, max, rnType, equiv, mod))
3073 throw Integer::RandomNumberNotFound();
3074 }
3075
3076 Integer Integer::Power2(size_t e)
3077 {
3078 Integer r((word)0, BitsToWords(e+1));
3079 r.SetBit(e);
3080 return r;
3081 }
3082
3083 bool Integer::operator!() const
3084 {
3085 return IsNegative() ? false : (reg[0]==0 && WordCount()==0);
3086 }
3087
3088 Integer& Integer::operator=(const Integer& t)
3089 {
3090 if (this != &t)
3091 {
3092 if (reg.size() != t.reg.size() || t.reg[t.reg.size()/2] == 0)
3093 reg.New(RoundupSize(t.WordCount()));
3094 CopyWords(reg, t.reg, reg.size());
3095 sign = t.sign;
3096 }
3097 return *this;
3098 }
3099
3100 bool Integer::GetBit(size_t n) const
3101 {
3102 // Profiling tells us the original Else was dominant, so it was promoted to the first If statement.
3103 // The code change occurred at Commit dc99266599a0e72d.
3104 if (n/WORD_BITS < reg.size())
3105 return bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1);
3106 else
3107 return 0;
3108 }
3109
3110 void Integer::SetBit(size_t n, bool value)
3111 {
3112 if (value)
3113 {
3114 reg.CleanGrow(RoundupSize(BitsToWords(n+1)));
3115 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
3116 }
3117 else
3118 {
3119 if (n/WORD_BITS < reg.size())
3120 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
3121 }
3122 }
3123
3124 byte Integer::GetByte(size_t n) const
3125 {
3126 // Profiling tells us the original Else was dominant, so it was promoted to the first If statement.
3127 // The code change occurred at Commit dc99266599a0e72d.
3128 if (n/WORD_SIZE < reg.size())
3129 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
3130 else
3131 return 0;
3132 }
3133
3134 void Integer::SetByte(size_t n, byte value)
3135 {
3136 reg.CleanGrow(RoundupSize(BytesToWords(n+1)));
3137 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
3138 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
3139 }
3140
3141 lword Integer::GetBits(size_t i, size_t n) const
3142 {
3143 lword v = 0;
3144 CRYPTOPP_ASSERT(n <= sizeof(v)*8);
3145 for (unsigned int j=0; j<n; j++)
3146 v |= lword(GetBit(i+j)) << j;
3147 return v;
3148 }
3149
3150 Integer Integer::operator-() const
3151 {
3152 Integer result(*this);
3153 result.Negate();
3154 return result;
3155 }
3156
3157 Integer Integer::AbsoluteValue() const
3158 {
3159 Integer result(*this);
3160 result.sign = POSITIVE;
3161 return result;
3162 }
3163
3164 void Integer::swap(Integer &a)
3165 {
3166 reg.swap(a.reg);
3167 std::swap(sign, a.sign);
3168 }
3169
3170 Integer::Integer(word value, size_t length)
3171 : reg(RoundupSize(length)), sign(POSITIVE)
3172 {
3173 reg[0] = value;
3174 SetWords(reg+1, 0, reg.size()-1);
3175 }
3176
3177 template <class T>
3178 static Integer StringToInteger(const T *str, ByteOrder order)
3179 {
3180 CRYPTOPP_ASSERT( order == BIG_ENDIAN_ORDER || order == LITTLE_ENDIAN_ORDER );
3181
3182 int radix, sign = 1;
3183 // GCC workaround
3184 // std::char_traits<wchar_t>::length() not defined in GCC 3.2 and STLport 4.5.3
3185 unsigned int length;
3186 for (length = 0; str[length] != 0; length++) {}
3187
3188 Integer v;
3189
3190 if (length == 0)
3191 return Integer::Zero();
3192
3193 switch (str[length-1])
3194 {
3195 case 'h':
3196 case 'H':
3197 radix=16;
3198 break;
3199 case 'o':
3200 case 'O':
3201 radix=8;
3202 break;
3203 case 'b':
3204 case 'B':
3205 radix=2;
3206 break;
3207 default:
3208 radix=10;
3209 }
3210
3211 // 'str' is of length 1 or more
3212 if (str[0] == '-')
3213 {
3214 sign = -1;
3215 str += 1, length -= 1;
3216 }
3217
3218 if (length > 2 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
3219 {
3220 radix = 16;
3221 str += 2, length -= 2;
3222 }
3223
3224 if (order == BIG_ENDIAN_ORDER)
3225 {
3226 for (unsigned int i=0; i<length; i++)
3227 {
3228 int digit, ch = static_cast<int>(str[i]);
3229
3230 // Profiling showd the second and third Else needed to be swapped
3231 // The code change occurred at Commit dc99266599a0e72d.
3232 if (ch >= '0' && ch <= '9')
3233 digit = ch - '0';
3234 else if (ch >= 'a' && ch <= 'f')
3235 digit = ch - 'a' + 10;
3236 else if (ch >= 'A' && ch <= 'F')
3237 digit = ch - 'A' + 10;
3238 else
3239 digit = radix;
3240
3241 if (digit < radix)
3242 {
3243 v *= radix;
3244 v += digit;
3245 }
3246 }
3247 }
3248 else if (radix == 16 && order == LITTLE_ENDIAN_ORDER)
3249 {
3250 // Nibble high, low and count
3251 unsigned int nh = 0, nl = 0, nc = 0;
3252 Integer position(Integer::One());
3253
3254 for (unsigned int i=0; i<length; i++)
3255 {
3256 int digit, ch = static_cast<int>(str[i]);
3257
3258 if (ch >= '0' && ch <= '9')
3259 digit = ch - '0';
3260 else if (ch >= 'a' && ch <= 'f')
3261 digit = ch - 'a' + 10;
3262 else if (ch >= 'A' && ch <= 'F')
3263 digit = ch - 'A' + 10;
3264 else
3265 digit = radix;
3266
3267 if (digit < radix)
3268 {
3269 if (nc++ == 0)
3270 nh = digit;
3271 else
3272 nl = digit;
3273
3274 if (nc == 2)
3275 {
3276 v += position * (nh << 4 | nl);
3277 nc = 0, position <<= 8;
3278 }
3279 }
3280 }
3281
3282 if (nc == 1)
3283 v += nh * position;
3284 }
3285 else // LITTLE_ENDIAN_ORDER && radix != 16
3286 {
3287 for (int i=static_cast<int>(length)-1; i>=0; i--)
3288 {
3289 int digit, ch = static_cast<int>(str[i]);
3290
3291 if (ch >= '0' && ch <= '9')
3292 digit = ch - '0';
3293 else if (ch >= 'a' && ch <= 'f')
3294 digit = ch - 'a' + 10;
3295 else if (ch >= 'A' && ch <= 'F')
3296 digit = ch - 'A' + 10;
3297 else
3298 digit = radix;
3299
3300 if (digit < radix)
3301 {
3302 v *= radix;
3303 v += digit;
3304 }
3305 }
3306 }
3307
3308 if (sign == -1)
3309 v.Negate();
3310
3311 return v;
3312 }
3313
3314 Integer::Integer(const char *str, ByteOrder order)
3315 : reg(2), sign(POSITIVE)
3316 {
3317 *this = StringToInteger(str,order);
3318 }
3319
3320 Integer::Integer(const wchar_t *str, ByteOrder order)
3321 : reg(2), sign(POSITIVE)
3322 {
3323 *this = StringToInteger(str,order);
3324 }
3325
3326 unsigned int Integer::WordCount() const
3327 {
3328 return (unsigned int)CountWords(reg, reg.size());
3329 }
3330
3331 unsigned int Integer::ByteCount() const
3332 {
3333 unsigned wordCount = WordCount();
3334 if (wordCount)
3335 return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
3336 else
3337 return 0;
3338 }
3339
3340 unsigned int Integer::BitCount() const
3341 {
3342 unsigned wordCount = WordCount();
3343 if (wordCount)
3344 return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
3345 else
3346 return 0;
3347 }
3348
3349 void Integer::Decode(const byte *input, size_t inputLen, Signedness s)
3350 {
3351 CRYPTOPP_ASSERT(input && inputLen); // NULL buffer
3352 StringStore store(input, inputLen);
3353 Decode(store, inputLen, s);
3354 }
3355
3356 void Integer::Decode(BufferedTransformation &bt, size_t inputLen, Signedness s)
3357 {
3358 CRYPTOPP_ASSERT(bt.MaxRetrievable() >= inputLen);
3359 if (bt.MaxRetrievable() < inputLen)
3360 throw InvalidArgument("Integer: input length is too small");
3361
3362 byte b;
3363 bt.Peek(b);
3364 sign = ((s==SIGNED) && (b & 0x80)) ? NEGATIVE : POSITIVE;
3365
3366 while (inputLen>0 && (sign==POSITIVE ? b==0 : b==0xff))
3367 {
3368 bt.Skip(1);
3369 inputLen--;
3370 bt.Peek(b);
3371 }
3372
3373 reg.CleanNew(RoundupSize(BytesToWords(inputLen)));
3374 for (size_t i=inputLen; i > 0; i--)
3375 {
3376 (void)bt.Get(b);
3377 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
3378 }
3379
3380 if (sign == NEGATIVE)
3381 {
3382 for (size_t i=inputLen; i<reg.size()*WORD_SIZE; i++)
3383 reg[i/WORD_SIZE] |= word(0xff) << (i%WORD_SIZE)*8;
3384 TwosComplement(reg, reg.size());
3385 }
3386 }
3387
3388 size_t Integer::MinEncodedSize(Signedness signedness) const
3389 {
3390 // Profiling tells us the original second If was dominant, so it was promoted to the first If statement.
3391 // The code change occurred at Commit dc99266599a0e72d.
3392 unsigned int outputLen = STDMAX(1U, ByteCount());
3393 const bool pre = (signedness == UNSIGNED);
3394 if (!pre && NotNegative() && (GetByte(outputLen-1) & 0x80))
3395 outputLen++;
3396 if (pre)
3397 return outputLen;
3398 if (IsNegative() && *this < -Power2(outputLen*8-1))
3399 outputLen++;
3400 return outputLen;
3401 }
3402
3403 // PKCS12_PBKDF and other classes use undersized buffers
3404 void Integer::Encode(byte *output, size_t outputLen, Signedness signedness) const
3405 {
3406 CRYPTOPP_ASSERT(output && outputLen); // NULL buffer
3407 ArraySink sink(output, outputLen);
3408 Encode(sink, outputLen, signedness);
3409 }
3410
3411 void Integer::Encode(BufferedTransformation &bt, size_t outputLen, Signedness signedness) const
3412 {
3413 if (signedness == UNSIGNED || NotNegative())
3414 {
3415 for (size_t i=outputLen; i > 0; i--)
3416 bt.Put(GetByte(i-1));
3417 }
3418 else
3419 {
3420 // take two's complement of *this
3421 Integer temp = Integer::Power2(8*STDMAX((size_t)ByteCount(), outputLen)) + *this;
3422 temp.Encode(bt, outputLen, UNSIGNED);
3423 }
3424 }
3425
3426 void Integer::DEREncode(BufferedTransformation &bt) const
3427 {
3428 DERGeneralEncoder enc(bt, INTEGER);
3429 Encode(enc, MinEncodedSize(SIGNED), SIGNED);
3430 enc.MessageEnd();
3431 }
3432
3433 void Integer::BERDecode(const byte *input, size_t len)
3434 {
3435 CRYPTOPP_ASSERT(input && len); // NULL buffer
3436 StringStore store(input, len);
3437 BERDecode(store);
3438 }
3439
3440 void Integer::BERDecode(BufferedTransformation &bt)
3441 {
3442 BERGeneralDecoder dec(bt, INTEGER);
3443 if (!dec.IsDefiniteLength() || dec.MaxRetrievable() < dec.RemainingLength())
3444 BERDecodeError();
3445 Decode(dec, (size_t)dec.RemainingLength(), SIGNED);
3446 dec.MessageEnd();
3447 }
3448
3449 void Integer::DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
3450 {
3451 DERGeneralEncoder enc(bt, OCTET_STRING);
3452 Encode(enc, length);
3453 enc.MessageEnd();
3454 }
3455
3456 void Integer::BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
3457 {
3458 BERGeneralDecoder dec(bt, OCTET_STRING);
3459 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
3460 BERDecodeError();
3461 Decode(dec, length);
3462 dec.MessageEnd();
3463 }
3464
3465 size_t Integer::OpenPGPEncode(byte *output, size_t bufferSize) const
3466 {
3467 CRYPTOPP_ASSERT(output && bufferSize); // NULL buffer
3468 CRYPTOPP_ASSERT(bufferSize >= MinEncodedSize()); // Undersized buffer
3469 ArraySink sink(output, bufferSize);
3470 return OpenPGPEncode(sink);
3471 }
3472
3473 size_t Integer::OpenPGPEncode(BufferedTransformation &bt) const
3474 {
3475 word16 bitCount = word16(BitCount());
3476 bt.PutWord16(bitCount);
3477 size_t byteCount = BitsToBytes(bitCount);
3478 Encode(bt, byteCount);
3479 return 2 + byteCount;
3480 }
3481
3482 void Integer::OpenPGPDecode(const byte *input, size_t len)
3483 {
3484 CRYPTOPP_ASSERT(input && len); // NULL buffer
3485 StringStore store(input, len);
3486 OpenPGPDecode(store);
3487 }
3488
3489 void Integer::OpenPGPDecode(BufferedTransformation &bt)
3490 {
3491 word16 bitCount;
3492 if (bt.GetWord16(bitCount) != 2 || bt.MaxRetrievable() < BitsToBytes(bitCount))
3493 throw OpenPGPDecodeErr();
3494 Decode(bt, BitsToBytes(bitCount));
3495 }
3496
3497 void Integer::Randomize(RandomNumberGenerator &rng, size_t nbits)
3498 {
3499 const size_t nbytes = nbits/8 + 1;
3500 SecByteBlock buf(nbytes);
3501 rng.GenerateBlock(buf, nbytes);
3502 if (nbytes)
3503 buf[0] = (byte)Crop(buf[0], nbits % 8);
3504 Decode(buf, nbytes, UNSIGNED);
3505 }
3506
3507 void Integer::Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max)
3508 {
3509 if (min > max)
3510 throw InvalidArgument("Integer: Min must be no greater than Max");
3511
3512 Integer range = max - min;
3513 const unsigned int nbits = range.BitCount();
3514
3515 do
3516 {
3517 Randomize(rng, nbits);
3518 }
3519 while (*this > range);
3520
3521 *this += min;
3522 }
3523
3524 bool Integer::Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv, const Integer &mod)
3525 {
3526 return GenerateRandomNoThrow(rng, MakeParameters("Min", min)("Max", max)("RandomNumberType", rnType)("EquivalentTo", equiv)("Mod", mod));
3527 }
3528
3529 class KDF2_RNG : public RandomNumberGenerator
3530 {
3531 public:
3532 KDF2_RNG(const byte *seed, size_t seedSize)
3533 : m_counter(0), m_counterAndSeed(seedSize + 4)
3534 {
3535 memcpy(m_counterAndSeed + 4, seed, seedSize);
3536 }
3537
3538 void GenerateBlock(byte *output, size_t size)
3539 {
3540 CRYPTOPP_ASSERT(output && size); // NULL buffer
3541 PutWord(false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
3542 ++m_counter;
3543 P1363_KDF2<SHA1>::DeriveKey(output, size, m_counterAndSeed, m_counterAndSeed.size(), NULLPTR, 0);
3544 }
3545
3546 private:
3547 word32 m_counter;
3548 SecByteBlock m_counterAndSeed;
3549 };
3550
3551 bool Integer::GenerateRandomNoThrow(RandomNumberGenerator &i_rng, const NameValuePairs &params)
3552 {
3553 Integer min = params.GetValueWithDefault("Min", Integer::Zero());
3554 Integer max;
3555 if (!params.GetValue("Max", max))
3556 {
3557 int bitLength;
3558 if (params.GetIntValue("BitLength", bitLength))
3559 max = Integer::Power2(bitLength);
3560 else
3561 throw InvalidArgument("Integer: missing Max argument");
3562 }
3563 if (min > max)
3564 throw InvalidArgument("Integer: Min must be no greater than Max");
3565
3566 Integer equiv = params.GetValueWithDefault("EquivalentTo", Integer::Zero());
3567 Integer mod = params.GetValueWithDefault("Mod", Integer::One());
3568
3569 if (equiv.IsNegative() || equiv >= mod)
3570 throw InvalidArgument("Integer: invalid EquivalentTo and/or Mod argument");
3571
3572 Integer::RandomNumberType rnType = params.GetValueWithDefault("RandomNumberType", Integer::ANY);
3573
3574 member_ptr<KDF2_RNG> kdf2Rng;
3575 ConstByteArrayParameter seed;
3576 if (params.GetValue(Name::Seed(), seed))
3577 {
3578 ByteQueue bq;
3579 DERSequenceEncoder seq(bq);
3580 min.DEREncode(seq);
3581 max.DEREncode(seq);
3582 equiv.DEREncode(seq);
3583 mod.DEREncode(seq);
3584 DEREncodeUnsigned(seq, rnType);
3585 DEREncodeOctetString(seq, seed.begin(), seed.size());
3586 seq.MessageEnd();
3587
3588 SecByteBlock finalSeed((size_t)bq.MaxRetrievable());
3589 bq.Get(finalSeed, finalSeed.size());
3590 kdf2Rng.reset(new KDF2_RNG(finalSeed.begin(), finalSeed.size()));
3591 }
3592 RandomNumberGenerator &rng = kdf2Rng.get() ? (RandomNumberGenerator &)*kdf2Rng : i_rng;
3593
3594 switch (rnType)
3595 {
3596 case ANY:
3597 if (mod == One())
3598 Randomize(rng, min, max);
3599 else
3600 {
3601 Integer min1 = min + (equiv-min)%mod;
3602 if (max < min1)
3603 return false;
3604 Randomize(rng, Zero(), (max - min1) / mod);
3605 *this *= mod;
3606 *this += min1;
3607 }
3608 return true;
3609
3610 case PRIME:
3611 {
3612 const PrimeSelector *pSelector = params.GetValueWithDefault(Name::PointerToPrimeSelector(), (const PrimeSelector *)NULLPTR);
3613
3614 int i;
3615 i = 0;
3616 while (1)
3617 {
3618 if (++i==16)
3619 {
3620 // check if there are any suitable primes in [min, max]
3621 Integer first = min;
3622 if (FirstPrime(first, max, equiv, mod, pSelector))
3623 {
3624 // if there is only one suitable prime, we're done
3625 *this = first;
3626 if (!FirstPrime(first, max, equiv, mod, pSelector))
3627 return true;
3628 }
3629 else
3630 return false;
3631 }
3632
3633 Randomize(rng, min, max);
3634 if (FirstPrime(*this, STDMIN(*this+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector))
3635 return true;
3636 }
3637 }
3638
3639 default:
3640 throw InvalidArgument("Integer: invalid RandomNumberType argument");
3641 }
3642 }
3643
3644 std::istream& operator>>(std::istream& in, Integer &a)
3645 {
3646 char c;
3647 unsigned int length = 0;
3648 SecBlock<char> str(length + 16);
3649
3650 std::ws(in);
3651
3652 do
3653 {
3654 in.read(&c, 1);
3655 str[length++] = c;
3656 if (length >= str.size())
3657 str.Grow(length + 16);
3658 }
3659 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=='.'));
3660
3661 if (in.gcount())
3662 in.putback(c);
3663 str[length-1] = '\0';
3664 a = Integer(str);
3665
3666 return in;
3667 }
3668
3669 // Ensure base 10 is default
3670 inline int FlagToBase(long f) {
3671 return f == std::ios::hex ? 16 : (f == std::ios::oct ? 8 : 10);
3672 }
3673
3674 inline char FlagToSuffix(long f) {
3675 return f == std::ios::hex ? 'h' : (f == std::ios::oct ? 'o' : '.');
3676 }
3677
3678 // Ensure base 10 is default
3679 std::ostream& operator<<(std::ostream& out, const Integer &a)
3680 {
3681 // Get relevant conversion specifications from ostream.
3682 const long f = out.flags() & std::ios::basefield;
3683 const int base = FlagToBase(f);
3684 const char suffix = FlagToSuffix(f);
3685
3686 Integer temp1=a, temp2;
3687 if (a.IsNegative())
3688 {
3689 out << '-';
3690 temp1.Negate();
3691 }
3692
3693 if (!a)
3694 out << '0';
3695
3696 static const char upper[]="0123456789ABCDEF";
3697 static const char lower[]="0123456789abcdef";
3698
3699 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
3700 unsigned int i=0;
3701 SecBlock<char> s(a.BitCount() / (SaturatingSubtract1(BitPrecision(base),1U)) + 1);
3702
3703 while (!!temp1)
3704 {
3705 word digit;
3706 Integer::Divide(digit, temp2, temp1, base);
3707 s[i++]=vec[digit];
3708 temp1.swap(temp2);
3709 }
3710
3711 while (i--)
3712 {
3713 out << s[i];
3714 }
3715
3716 #ifdef CRYPTOPP_USE_STD_SHOWBASE
3717 if (out.flags() & std::ios_base::showbase)
3718 out << suffix;
3719
3720 return out;
3721 #else
3722 return out << suffix;
3723 #endif
3724 }
3725
3726 Integer& Integer::operator++()
3727 {
3728 if (NotNegative())
3729 {
3730 if (Increment(reg, reg.size()))
3731 {
3732 reg.CleanGrow(2*reg.size());
3733 reg[reg.size()/2]=1;
3734 }
3735 }
3736 else
3737 {
3738 word borrow = Decrement(reg, reg.size());
3739 CRYPTOPP_ASSERT(!borrow); CRYPTOPP_UNUSED(borrow);
3740
3741 if (WordCount()==0)
3742 *this = Zero();
3743 }
3744 return *this;
3745 }
3746
3747 Integer& Integer::operator--()
3748 {
3749 if (IsNegative())
3750 {
3751 if (Increment(reg, reg.size()))
3752 {
3753 reg.CleanGrow(2*reg.size());
3754 reg[reg.size()/2]=1;
3755 }
3756 }
3757 else
3758 {
3759 if (Decrement(reg, reg.size()))
3760 *this = -One();
3761 }
3762 return *this;
3763 }
3764
3765 // This is a bit operation. We set sign to POSITIVE, so there's no need to
3766 // worry about negative zero. Also see http://stackoverflow.com/q/11644362.
3767 Integer Integer::And(const Integer& t) const
3768 {
3769 if (this == &t)
3770 {
3771 return AbsoluteValue();
3772 }
3773 else if (reg.size() >= t.reg.size())
3774 {
3775 Integer result(t);
3776 AndWords(result.reg, reg, t.reg.size());
3777
3778 result.sign = POSITIVE;
3779 return result;
3780 }
3781 else // reg.size() < t.reg.size()
3782 {
3783 Integer result(*this);
3784 AndWords(result.reg, t.reg, reg.size());
3785
3786 result.sign = POSITIVE;
3787 return result;
3788 }
3789 }
3790
3791 // This is a bit operation. We set sign to POSITIVE, so there's no need to
3792 // worry about negative zero. Also see http://stackoverflow.com/q/11644362.
3793 Integer Integer::Or(const Integer& t) const
3794 {
3795 if (this == &t)
3796 {
3797 return AbsoluteValue();
3798 }
3799 else if (reg.size() >= t.reg.size())
3800 {
3801 Integer result(*this);
3802 OrWords(result.reg, t.reg, t.reg.size());
3803
3804 result.sign = POSITIVE;
3805 return result;
3806 }
3807 else // reg.size() < t.reg.size()
3808 {
3809 Integer result(t);
3810 OrWords(result.reg, reg, reg.size());
3811
3812 result.sign = POSITIVE;
3813 return result;
3814 }
3815 }
3816
3817 // This is a bit operation. We set sign to POSITIVE, so there's no need to
3818 // worry about negative zero. Also see http://stackoverflow.com/q/11644362.
3819 Integer Integer::Xor(const Integer& t) const
3820 {
3821 if (this == &t)
3822 {
3823 return Integer::Zero();
3824 }
3825 else if (reg.size() >= t.reg.size())
3826 {
3827 Integer result(*this);
3828 XorWords(result.reg, t.reg, t.reg.size());
3829
3830 result.sign = POSITIVE;
3831 return result;
3832 }
3833 else // reg.size() < t.reg.size()
3834 {
3835 Integer result(t);
3836 XorWords(result.reg, reg, reg.size());
3837
3838 result.sign = POSITIVE;
3839 return result;
3840 }
3841 }
3842
3843 void PositiveAdd(Integer &sum, const Integer &a, const Integer& b)
3844 {
3845 // Profiling tells us the original second Else If was dominant, so it was promoted to the first If statement.
3846 // The code change occurred at Commit dc99266599a0e72d.
3847 int carry; const bool pre = (a.reg.size() == b.reg.size());
3848 if (!pre && a.reg.size() > b.reg.size())
3849 {
3850 carry = Add(sum.reg, a.reg, b.reg, b.reg.size());
3851 CopyWords(sum.reg+b.reg.size(), a.reg+b.reg.size(), a.reg.size()-b.reg.size());
3852 carry = Increment(sum.reg+b.reg.size(), a.reg.size()-b.reg.size(), carry);
3853 }
3854 else if (pre)
3855 {
3856 carry = Add(sum.reg, a.reg, b.reg, a.reg.size());
3857 }
3858 else
3859 {
3860 carry = Add(sum.reg, a.reg, b.reg, a.reg.size());
3861 CopyWords(sum.reg+a.reg.size(), b.reg+a.reg.size(), b.reg.size()-a.reg.size());
3862 carry = Increment(sum.reg+a.reg.size(), b.reg.size()-a.reg.size(), carry);
3863 }
3864
3865 if (carry)
3866 {
3867 sum.reg.CleanGrow(2*sum.reg.size());
3868 sum.reg[sum.reg.size()/2] = 1;
3869 }
3870 sum.sign = Integer::POSITIVE;
3871 }
3872
3873 void PositiveSubtract(Integer &diff, const Integer &a, const Integer& b)
3874 {
3875 unsigned aSize = a.WordCount();
3876 aSize += aSize%2;
3877 unsigned bSize = b.WordCount();
3878 bSize += bSize%2;
3879
3880 // Profiling tells us the original second Else If was dominant, so it was promoted to the first If statement.
3881 // The code change occurred at Commit dc99266599a0e72d.
3882 if (aSize > bSize)
3883 {
3884 word borrow = Subtract(diff.reg, a.reg, b.reg, bSize);
3885 CopyWords(diff.reg+bSize, a.reg+bSize, aSize-bSize);
3886 borrow = Decrement(diff.reg+bSize, aSize-bSize, borrow);
3887 CRYPTOPP_ASSERT(!borrow); CRYPTOPP_UNUSED(borrow);
3888 diff.sign = Integer::POSITIVE;
3889 }
3890 else if (aSize == bSize)
3891 {
3892 if (Compare(a.reg, b.reg, aSize) >= 0)
3893 {
3894 Subtract(diff.reg, a.reg, b.reg, aSize);
3895 diff.sign = Integer::POSITIVE;
3896 }
3897 else
3898 {
3899 Subtract(diff.reg, b.reg, a.reg, aSize);
3900 diff.sign = Integer::NEGATIVE;
3901 }
3902 }
3903 else
3904 {
3905 word borrow = Subtract(diff.reg, b.reg, a.reg, aSize);
3906 CopyWords(diff.reg+aSize, b.reg+aSize, bSize-aSize);
3907 borrow = Decrement(diff.reg+aSize, bSize-aSize, borrow);
3908 CRYPTOPP_ASSERT(!borrow); CRYPTOPP_UNUSED(borrow);
3909 diff.sign = Integer::NEGATIVE;
3910 }
3911 }
3912
3913 // MSVC .NET 2003 workaround
3914 template <class T> inline const T& STDMAX2(const T& a, const T& b)
3915 {
3916 return a < b ? b : a;
3917 }
3918
3919 Integer Integer::Plus(const Integer& b) const
3920 {
3921 Integer sum((word)0, STDMAX2(reg.size(), b.reg.size()));
3922 if (NotNegative())
3923 {
3924 if (b.NotNegative())
3925 PositiveAdd(sum, *this, b);
3926 else
3927 PositiveSubtract(sum, *this, b);
3928 }
3929 else
3930 {
3931 if (b.NotNegative())
3932 PositiveSubtract(sum, b, *this);
3933 else
3934 {
3935 PositiveAdd(sum, *this, b);
3936 sum.sign = Integer::NEGATIVE;
3937 }
3938 }
3939 return sum;
3940 }
3941
3942 Integer& Integer::operator+=(const Integer& t)
3943 {
3944 reg.CleanGrow(t.reg.size());
3945 if (NotNegative())
3946 {
3947 if (t.NotNegative())
3948 PositiveAdd(*this, *this, t);
3949 else
3950 PositiveSubtract(*this, *this, t);
3951 }
3952 else
3953 {
3954 if (t.NotNegative())
3955 PositiveSubtract(*this, t, *this);
3956 else
3957 {
3958 PositiveAdd(*this, *this, t);
3959 sign = Integer::NEGATIVE;
3960 }
3961 }
3962 return *this;
3963 }
3964
3965 Integer Integer::Minus(const Integer& b) const
3966 {
3967 Integer diff((word)0, STDMAX2(reg.size(), b.reg.size()));
3968 if (NotNegative())
3969 {
3970 if (b.NotNegative())
3971 PositiveSubtract(diff, *this, b);
3972 else
3973 PositiveAdd(diff, *this, b);
3974 }
3975 else
3976 {
3977 if (b.NotNegative())
3978 {
3979 PositiveAdd(diff, *this, b);
3980 diff.sign = Integer::NEGATIVE;
3981 }
3982 else
3983 PositiveSubtract(diff, b, *this);
3984 }
3985 return diff;
3986 }
3987
3988 Integer& Integer::operator-=(const Integer& t)
3989 {
3990 reg.CleanGrow(t.reg.size());
3991 if (NotNegative())
3992 {
3993 if (t.NotNegative())
3994 PositiveSubtract(*this, *this, t);
3995 else
3996 PositiveAdd(*this, *this, t);
3997 }
3998 else
3999 {
4000 if (t.NotNegative())
4001 {
4002 PositiveAdd(*this, *this, t);
4003 sign = Integer::NEGATIVE;
4004 }
4005 else
4006 PositiveSubtract(*this, t, *this);
4007 }
4008 return *this;
4009 }
4010
4011 Integer& Integer::operator<<=(size_t n)
4012 {
4013 const size_t wordCount = WordCount();
4014 const size_t shiftWords = n / WORD_BITS;
4015 const unsigned int shiftBits = (unsigned int)(n % WORD_BITS);
4016
4017 reg.CleanGrow(RoundupSize(wordCount+BitsToWords(n)));
4018 ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords);
4019 ShiftWordsLeftByBits(reg+shiftWords, wordCount+BitsToWords(shiftBits), shiftBits);
4020 return *this;
4021 }
4022
4023 Integer& Integer::operator>>=(size_t n)
4024 {
4025 const size_t wordCount = WordCount();
4026 const size_t shiftWords = n / WORD_BITS;
4027 const unsigned int shiftBits = (unsigned int)(n % WORD_BITS);
4028
4029 ShiftWordsRightByWords(reg, wordCount, shiftWords);
4030 if (wordCount > shiftWords)
4031 ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits);
4032 if (IsNegative() && WordCount()==0) // avoid -0
4033 *this = Zero();
4034 return *this;
4035 }
4036
4037 Integer& Integer::operator&=(const Integer& t)
4038 {
4039 if (this != &t)
4040 {
4041 const size_t size = STDMIN(reg.size(), t.reg.size());
4042 reg.resize(size);
4043 AndWords(reg, t.reg, size);
4044 }
4045 sign = POSITIVE;
4046 return *this;
4047 }
4048
4049 Integer& Integer::operator|=(const Integer& t)
4050 {
4051 if (this != &t)
4052 {
4053 if (reg.size() >= t.reg.size())
4054 {
4055 OrWords(reg, t.reg, t.reg.size());
4056 }
4057 else // reg.size() < t.reg.size()
4058 {
4059 const size_t head = reg.size();
4060 const size_t tail = t.reg.size() - reg.size();
4061 reg.resize(head+tail);
4062 OrWords(reg, t.reg, head);
4063 CopyWords(reg+head,t.reg+head,tail);
4064 }
4065 }
4066 sign = POSITIVE;
4067 return *this;
4068 }
4069
4070 Integer& Integer::operator^=(const Integer& t)
4071 {
4072 if (this == &t)
4073 {
4074 *this = Zero();
4075 }
4076 else
4077 {
4078 if (reg.size() >= t.reg.size())
4079 {
4080 XorWords(reg, t.reg, t.reg.size());
4081 }
4082 else // reg.size() < t.reg.size()
4083 {
4084 const size_t head = reg.size();
4085 const size_t tail = t.reg.size() - reg.size();
4086 reg.resize(head+tail);
4087 XorWords(reg, t.reg, head);
4088 CopyWords(reg+head,t.reg+head,tail);
4089 }
4090 }
4091 sign = POSITIVE;
4092 return *this;
4093 }
4094
4095 void PositiveMultiply(Integer &product, const Integer &a, const Integer &b)
4096 {
4097 size_t aSize = RoundupSize(a.WordCount());
4098 size_t bSize = RoundupSize(b.WordCount());
4099
4100 product.reg.CleanNew(RoundupSize(aSize+bSize));
4101 product.sign = Integer::POSITIVE;
4102
4103 IntegerSecBlock workspace(aSize + bSize);
4104 AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize);
4105 }
4106
4107 void Multiply(Integer &product, const Integer &a, const Integer &b)
4108 {
4109 PositiveMultiply(product, a, b);
4110
4111 if (a.NotNegative() != b.NotNegative())
4112 product.Negate();
4113 }
4114
4115 Integer Integer::Times(const Integer &b) const
4116 {
4117 Integer product;
4118 Multiply(product, *this, b);
4119 return product;
4120 }
4121
4122 /*
4123 void PositiveDivide(Integer &remainder, Integer &quotient,
4124 const Integer &dividend, const Integer &divisor)
4125 {
4126 remainder.reg.CleanNew(divisor.reg.size());
4127 remainder.sign = Integer::POSITIVE;
4128 quotient.reg.New(0);
4129 quotient.sign = Integer::POSITIVE;
4130 unsigned i=dividend.BitCount();
4131 while (i--)
4132 {
4133 word overflow = ShiftWordsLeftByBits(remainder.reg, remainder.reg.size(), 1);
4134 remainder.reg[0] |= dividend[i];
4135 if (overflow || remainder >= divisor)
4136 {
4137 Subtract(remainder.reg, remainder.reg, divisor.reg, remainder.reg.size());
4138 quotient.SetBit(i);
4139 }
4140 }
4141 }
4142 */
4143
4144 void PositiveDivide(Integer &remainder, Integer &quotient,
4145 const Integer &a, const Integer &b)
4146 {
4147 unsigned aSize = a.WordCount();
4148 unsigned bSize = b.WordCount();
4149
4150 if (!bSize)
4151 throw Integer::DivideByZero();
4152
4153 if (aSize < bSize)
4154 {
4155 remainder = a;
4156 remainder.sign = Integer::POSITIVE;
4157 quotient = Integer::Zero();
4158 return;
4159 }
4160
4161 aSize += aSize%2; // round up to next even number
4162 bSize += bSize%2;
4163
4164 remainder.reg.CleanNew(RoundupSize(bSize));
4165 remainder.sign = Integer::POSITIVE;
4166 quotient.reg.CleanNew(RoundupSize(aSize-bSize+2));
4167 quotient.sign = Integer::POSITIVE;
4168
4169 IntegerSecBlock T(aSize+3*(bSize+2));
4170 Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize);
4171 }
4172
4173 void Integer::Divide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor)
4174 {
4175 PositiveDivide(remainder, quotient, dividend, divisor);
4176
4177 if (dividend.IsNegative())
4178 {
4179 quotient.Negate();
4180 if (remainder.NotZero())
4181 {
4182 --quotient;
4183 remainder = divisor.AbsoluteValue() - remainder;
4184 }
4185 }
4186
4187 if (divisor.IsNegative())
4188 quotient.Negate();
4189 }
4190
4191 void Integer::DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n)
4192 {
4193 q = a;
4194 q >>= n;
4195
4196 const size_t wordCount = BitsToWords(n);
4197 if (wordCount <= a.WordCount())
4198 {
4199 r.reg.resize(RoundupSize(wordCount));
4200 CopyWords(r.reg, a.reg, wordCount);
4201 SetWords(r.reg+wordCount, 0, r.reg.size()-wordCount);
4202 if (n % WORD_BITS != 0)
4203 r.reg[wordCount-1] %= (word(1) << (n % WORD_BITS));
4204 }
4205 else
4206 {
4207 r.reg.resize(RoundupSize(a.WordCount()));
4208 CopyWords(r.reg, a.reg, r.reg.size());
4209 }
4210 r.sign = POSITIVE;
4211
4212 if (a.IsNegative() && r.NotZero())
4213 {
4214 --q;
4215 r = Power2(n) - r;
4216 }
4217 }
4218
4219 Integer Integer::DividedBy(const Integer &b) const
4220 {
4221 Integer remainder, quotient;
4222 Integer::Divide(remainder, quotient, *this, b);
4223 return quotient;
4224 }
4225
4226 Integer Integer::Modulo(const Integer &b) const
4227 {
4228 Integer remainder, quotient;
4229 Integer::Divide(remainder, quotient, *this, b);
4230 return remainder;
4231 }
4232
4233 void Integer::Divide(word &remainder, Integer &quotient, const Integer &dividend, word divisor)
4234 {
4235 if (!divisor)
4236 throw Integer::DivideByZero();
4237
4238 if ((divisor & (divisor-1)) == 0) // divisor is a power of 2
4239 {
4240 quotient = dividend >> (BitPrecision(divisor)-1);
4241 remainder = dividend.reg[0] & (divisor-1);
4242 return;
4243 }
4244
4245 unsigned int i = dividend.WordCount();
4246 quotient.reg.CleanNew(RoundupSize(i));
4247 remainder = 0;
4248 while (i--)
4249 {
4250 quotient.reg[i] = DWord(dividend.reg[i], remainder) / divisor;
4251 remainder = DWord(dividend.reg[i], remainder) % divisor;
4252 }
4253
4254 if (dividend.NotNegative())
4255 quotient.sign = POSITIVE;
4256 else
4257 {
4258 quotient.sign = NEGATIVE;
4259 if (remainder)
4260 {
4261 --quotient;
4262 remainder = divisor - remainder;
4263 }
4264 }
4265 }
4266
4267 Integer Integer::DividedBy(word b) const
4268 {
4269 word remainder;
4270 Integer quotient;
4271 Integer::Divide(remainder, quotient, *this, b);
4272 return quotient;
4273 }
4274
4275 word Integer::Modulo(word divisor) const
4276 {
4277 if (!divisor)
4278 throw Integer::DivideByZero();
4279
4280 word remainder;
4281
4282 // Profiling tells us the original Else was dominant, so it was promoted to the first If statement.
4283 // The code change occurred at Commit dc99266599a0e72d.
4284 if ((divisor & (divisor-1)) != 0) // divisor is not a power of 2
4285 {
4286 // Profiling tells us the original Else was dominant, so it was promoted to the first If statement.
4287 // The code change occurred at Commit dc99266599a0e72d.
4288 unsigned int i = WordCount();
4289 if (divisor > 5)
4290 {
4291 remainder = 0;
4292 while (i--)
4293 remainder = DWord(reg[i], remainder) % divisor;
4294 }
4295 else
4296 {
4297 DWord sum(0, 0);
4298 while (i--)
4299 sum += reg[i];
4300 remainder = sum % divisor;
4301 }
4302 }
4303 else // divisor is a power of 2
4304 {
4305 remainder = reg[0] & (divisor-1);
4306 }
4307
4308 if (IsNegative() && remainder)
4309 remainder = divisor - remainder;
4310
4311 return remainder;
4312 }
4313
4314 void Integer::Negate()
4315 {
4316 if (!!(*this)) // don't flip sign if *this==0
4317 sign = Sign(1-sign);
4318 }
4319
4320 int Integer::PositiveCompare(const Integer& t) const
4321 {
4322 // Profiling tells us the original Else was dominant, so it was promoted to the first If statement.
4323 // The code change occurred at Commit dc99266599a0e72d.
4324 const unsigned size = WordCount(), tSize = t.WordCount();
4325 if (size != tSize)
4326 return size > tSize ? 1 : -1;
4327 else
4328 return CryptoPP::Compare(reg, t.reg, size);
4329 }
4330
4331 int Integer::Compare(const Integer& t) const
4332 {
4333 if (NotNegative())
4334 {
4335 if (t.NotNegative())
4336 return PositiveCompare(t);
4337 else
4338 return 1;
4339 }
4340 else
4341 {
4342 if (t.NotNegative())
4343 return -1;
4344 else
4345 return -PositiveCompare(t);
4346 }
4347 }
4348
4349 Integer Integer::SquareRoot() const
4350 {
4351 if (!IsPositive())
4352 return Zero();
4353
4354 // overestimate square root
4355 Integer x, y = Power2((BitCount()+1)/2);
4356 CRYPTOPP_ASSERT(y*y >= *this);
4357
4358 do
4359 {
4360 x = y;
4361 y = (x + *this/x) >> 1;
4362 } while (y<x);
4363
4364 return x;
4365 }
4366
4367 bool Integer::IsSquare() const
4368 {
4369 Integer r = SquareRoot();
4370 return *this == r.Squared();
4371 }
4372
4373 bool Integer::IsUnit() const
4374 {
4375 return (WordCount() == 1) && (reg[0] == 1);
4376 }
4377
4378 Integer Integer::MultiplicativeInverse() const
4379 {
4380 return IsUnit() ? *this : Zero();
4381 }
4382
4383 Integer a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m)
4384 {
4385 CRYPTOPP_ASSERT(m.NotZero());
4386 if (m.IsZero())
4387 throw Integer::DivideByZero();
4388
4389 return x*y%m;
4390 }
4391
4392 Integer a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m)
4393 {
4394 CRYPTOPP_ASSERT(m.NotZero());
4395 if (m.IsZero())
4396 throw Integer::DivideByZero();
4397
4398 ModularArithmetic mr(m);
4399 return mr.Exponentiate(x, e);
4400 }
4401
4402 Integer Integer::Gcd(const Integer &a, const Integer &b)
4403 {
4404 return EuclideanDomainOf<Integer>().Gcd(a, b);
4405 }
4406
4407 Integer Integer::InverseMod(const Integer &m) const
4408 {
4409 CRYPTOPP_ASSERT(m.NotNegative());
4410 CRYPTOPP_ASSERT(m.NotZero());
4411
4412 if (IsNegative())
4413 return Modulo(m).InverseModNext(m);
4414
4415 // http://github.com/weidai11/cryptopp/issues/602
4416 if (*this >= m)
4417 return Modulo(m).InverseModNext(m);
4418
4419 return InverseModNext(m);
4420 }
4421
4422 Integer Integer::InverseModNext(const Integer &m) const
4423 {
4424 CRYPTOPP_ASSERT(m.NotNegative());
4425 CRYPTOPP_ASSERT(m.NotZero());
4426
4427 if (m.IsEven())
4428 {
4429 if (!m || IsEven())
4430 return Zero(); // no inverse
4431 if (*this == One())
4432 return One();
4433
4434 Integer u = m.Modulo(*this).InverseModNext(*this);
4435 return !u ? Zero() : (m*(*this-u)+1)/(*this);
4436 }
4437
4438 // AlmostInverse requires a 4x workspace
4439 IntegerSecBlock T(m.reg.size() * 4);
4440 Integer r((word)0, m.reg.size());
4441 unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
4442 DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
4443 return r;
4444 }
4445
4446 word Integer::InverseMod(word mod) const
4447 {
4448 CRYPTOPP_ASSERT(mod != 0);
4449
4450 word g0 = mod, g1 = *this % mod;
4451 word v0 = 0, v1 = 1;
4452 word y;
4453
4454 while (g1)
4455 {
4456 if (g1 == 1)
4457 return v1;
4458 y = g0 / g1;
4459 g0 = g0 % g1;
4460 v0 += y * v1;
4461
4462 if (!g0)
4463 break;
4464 if (g0 == 1)
4465 return mod-v0;
4466 y = g1 / g0;
4467 g1 = g1 % g0;
4468 v1 += y * v0;
4469 }
4470 return 0;
4471 }
4472
4473 // ********************************************************
4474
4475 ModularArithmetic::ModularArithmetic(BufferedTransformation &bt)
4476 {
4477 BERSequenceDecoder seq(bt);
4478 OID oid(seq);
4479 if (oid != ASN1::prime_field())
4480 BERDecodeError();
4481 m_modulus.BERDecode(seq);
4482 seq.MessageEnd();
4483 m_result.reg.resize(m_modulus.reg.size());
4484 }
4485
4486 void ModularArithmetic::DEREncode(BufferedTransformation &bt) const
4487 {
4488 DERSequenceEncoder seq(bt);
4489 ASN1::prime_field().DEREncode(seq);
4490 m_modulus.DEREncode(seq);
4491 seq.MessageEnd();
4492 }
4493
4494 void ModularArithmetic::DEREncodeElement(BufferedTransformation &out, const Element &a) const
4495 {
4496 a.DEREncodeAsOctetString(out, MaxElementByteLength());
4497 }
4498
4499 void ModularArithmetic::BERDecodeElement(BufferedTransformation &in, Element &a) const
4500 {
4501 a.BERDecodeAsOctetString(in, MaxElementByteLength());
4502 }
4503
4504 const Integer& ModularArithmetic::Half(const Integer &a) const
4505 {
4506 if (a.reg.size()==m_modulus.reg.size())
4507 {
4508 CryptoPP::DivideByPower2Mod(m_result.reg.begin(), a.reg, 1, m_modulus.reg, a.reg.size());
4509 return m_result;
4510 }
4511 else
4512 return m_result1 = (a.IsEven() ? (a >> 1) : ((a+m_modulus) >> 1));
4513 }
4514
4515 const Integer& ModularArithmetic::Add(const Integer &a, const Integer &b) const
4516 {
4517 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4518 {
4519 if (CryptoPP::Add(m_result.reg.begin(), a.reg, b.reg, a.reg.size())
4520 || Compare(m_result.reg, m_modulus.reg, a.reg.size()) >= 0)
4521 {
4522 CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.size());
4523 }
4524 return m_result;
4525 }
4526 else
4527 {
4528 m_result1 = a+b;
4529 if (m_result1 >= m_modulus)
4530 m_result1 -= m_modulus;
4531 return m_result1;
4532 }
4533 }
4534
4535 Integer& ModularArithmetic::Accumulate(Integer &a, const Integer &b) const
4536 {
4537 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4538 {
4539 if (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.size())
4540 || Compare(a.reg, m_modulus.reg, a.reg.size()) >= 0)
4541 {
4542 CryptoPP::Subtract(a.reg, a.reg, m_modulus.reg, a.reg.size());
4543 }
4544 }
4545 else
4546 {
4547 a+=b;
4548 if (a>=m_modulus)
4549 a-=m_modulus;
4550 }
4551
4552 return a;
4553 }
4554
4555 const Integer& ModularArithmetic::Subtract(const Integer &a, const Integer &b) const
4556 {
4557 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4558 {
4559 if (CryptoPP::Subtract(m_result.reg.begin(), a.reg, b.reg, a.reg.size()))
4560 CryptoPP::Add(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.size());
4561 return m_result;
4562 }
4563 else
4564 {
4565 m_result1 = a-b;
4566 if (m_result1.IsNegative())
4567 m_result1 += m_modulus;
4568 return m_result1;
4569 }
4570 }
4571
4572 Integer& ModularArithmetic::Reduce(Integer &a, const Integer &b) const
4573 {
4574 if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size())
4575 {
4576 if (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.size()))
4577 CryptoPP::Add(a.reg, a.reg, m_modulus.reg, a.reg.size());
4578 }
4579 else
4580 {
4581 a-=b;
4582 if (a.IsNegative())
4583 a+=m_modulus;
4584 }
4585
4586 return a;
4587 }
4588
4589 const Integer& ModularArithmetic::Inverse(const Integer &a) const
4590 {
4591 if (!a)
4592 return a;
4593
4594 CopyWords(m_result.reg.begin(), m_modulus.reg, m_modulus.reg.size());
4595 if (CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, a.reg, a.reg.size()))
4596 Decrement(m_result.reg.begin()+a.reg.size(), m_modulus.reg.size()-a.reg.size());
4597
4598 return m_result;
4599 }
4600
4601 Integer ModularArithmetic::CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
4602 {
4603 if (m_modulus.IsOdd())
4604 {
4605 MontgomeryRepresentation dr(m_modulus);
4606 return dr.ConvertOut(dr.CascadeExponentiate(dr.ConvertIn(x), e1, dr.ConvertIn(y), e2));
4607 }
4608 else
4609 return AbstractRing<Integer>::CascadeExponentiate(x, e1, y, e2);
4610 }
4611
4612 void ModularArithmetic::SimultaneousExponentiate(Integer *results, const Integer &base, const Integer *exponents, unsigned int exponentsCount) const
4613 {
4614 if (m_modulus.IsOdd())
4615 {
4616 MontgomeryRepresentation dr(m_modulus);
4617 dr.SimultaneousExponentiate(results, dr.ConvertIn(base), exponents, exponentsCount);
4618 for (unsigned int i=0; i<exponentsCount; i++)
4619 results[i] = dr.ConvertOut(results[i]);
4620 }
4621 else
4622 AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);
4623 }
4624
4625 MontgomeryRepresentation::MontgomeryRepresentation(const Integer &m) // modulus must be odd
4626 : ModularArithmetic(m),
4627 m_u((word)0, m_modulus.reg.size()),
4628 m_workspace(5*m_modulus.reg.size())
4629 {
4630 if (!m_modulus.IsOdd())
4631 throw InvalidArgument("MontgomeryRepresentation: Montgomery representation requires an odd modulus");
4632
4633 RecursiveInverseModPower2(m_u.reg, m_workspace, m_modulus.reg, m_modulus.reg.size());
4634 }
4635
4636 const Integer& MontgomeryRepresentation::Multiply(const Integer &a, const Integer &b) const
4637 {
4638 word *const T = m_workspace.begin();
4639 word *const R = m_result.reg.begin();
4640 const size_t N = m_modulus.reg.size();
4641 CRYPTOPP_ASSERT(a.reg.size()<=N && b.reg.size()<=N);
4642
4643 AsymmetricMultiply(T, T+2*N, a.reg, a.reg.size(), b.reg, b.reg.size());
4644 SetWords(T+a.reg.size()+b.reg.size(), 0, 2*N-a.reg.size()-b.reg.size());
4645 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4646 return m_result;
4647 }
4648
4649 const Integer& MontgomeryRepresentation::Square(const Integer &a) const
4650 {
4651 word *const T = m_workspace.begin();
4652 word *const R = m_result.reg.begin();
4653 const size_t N = m_modulus.reg.size();
4654 CRYPTOPP_ASSERT(a.reg.size()<=N);
4655
4656 CryptoPP::Square(T, T+2*N, a.reg, a.reg.size());
4657 SetWords(T+2*a.reg.size(), 0, 2*N-2*a.reg.size());
4658 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4659 return m_result;
4660 }
4661
4662 Integer MontgomeryRepresentation::ConvertOut(const Integer &a) const
4663 {
4664 word *const T = m_workspace.begin();
4665 word *const R = m_result.reg.begin();
4666 const size_t N = m_modulus.reg.size();
4667 CRYPTOPP_ASSERT(a.reg.size()<=N);
4668
4669 CopyWords(T, a.reg, a.reg.size());
4670 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
4671 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4672 return m_result;
4673 }
4674
4675 const Integer& MontgomeryRepresentation::MultiplicativeInverse(const Integer &a) const
4676 {
4677 // return (EuclideanMultiplicativeInverse(a, modulus)<<(2*WORD_BITS*modulus.reg.size()))%modulus;
4678 word *const T = m_workspace.begin();
4679 word *const R = m_result.reg.begin();
4680 const size_t N = m_modulus.reg.size();
4681 CRYPTOPP_ASSERT(a.reg.size()<=N);
4682
4683 CopyWords(T, a.reg, a.reg.size());
4684 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
4685 MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N);
4686 unsigned k = AlmostInverse(R, T, R, N, m_modulus.reg, N);
4687
4688 // cout << "k=" << k << " N*32=" << 32*N << endl;
4689
4690 if (k>N*WORD_BITS)
4691 DivideByPower2Mod(R, R, k-N*WORD_BITS, m_modulus.reg, N);
4692 else
4693 MultiplyByPower2Mod(R, R, N*WORD_BITS-k, m_modulus.reg, N);
4694
4695 return m_result;
4696 }
4697
4698 // Specialization declared in misc.h to allow us to print integers
4699 // with additional control options, like arbirary bases and uppercase.
4700 template <> CRYPTOPP_DLL
4701 std::string IntToString<Integer>(Integer value, unsigned int base)
4702 {
4703 // Hack... set the high bit for uppercase. Set the next bit fo a suffix.
4704 static const unsigned int BIT_32 = (1U << 31);
4705 const bool UPPER = !!(base & BIT_32);
4706 static const unsigned int BIT_31 = (1U << 30);
4707 const bool BASE = !!(base & BIT_31);
4708
4709 const char CH = UPPER ? 'A' : 'a';
4710 base &= ~(BIT_32|BIT_31);
4711 CRYPTOPP_ASSERT(base >= 2 && base <= 32);
4712
4713 if (value == 0)
4714 return "0";
4715
4716 bool negative = false, zero = false;
4717 if (value.IsNegative())
4718 {
4719 negative = true;
4720 value.Negate();
4721 }
4722
4723 if (!value)
4724 zero = true;
4725
4726 SecBlock<char> s(value.BitCount() / (SaturatingSubtract1(BitPrecision(base),1U)) + 1);
4727 Integer temp;
4728
4729 unsigned int i=0;
4730 while (!!value)
4731 {
4732 word digit;
4733 Integer::Divide(digit, temp, value, word(base));
4734 s[i++]=char((digit < 10 ? '0' : (CH - 10)) + digit);
4735 value.swap(temp);
4736 }
4737
4738 std::string result;
4739 result.reserve(i+2);
4740
4741 if (negative)
4742 result += '-';
4743
4744 if (zero)
4745 result += '0';
4746
4747 while (i--)
4748 result += s[i];
4749
4750 if (BASE)
4751 {
4752 if (base == 10)
4753 result += '.';
4754 else if (base == 16)
4755 result += 'h';
4756 else if (base == 8)
4757 result += 'o';
4758 else if (base == 2)
4759 result += 'b';
4760 }
4761
4762 return result;
4763 }
4764
4765 // Specialization declared in misc.h to avoid Coverity findings.
4766 template <> CRYPTOPP_DLL
4767 std::string IntToString<word64>(word64 value, unsigned int base)
4768 {
4769 // Hack... set the high bit for uppercase.
4770 static const unsigned int HIGH_BIT = (1U << 31);
4771 const char CH = !!(base & HIGH_BIT) ? 'A' : 'a';
4772 base &= ~HIGH_BIT;
4773
4774 CRYPTOPP_ASSERT(base >= 2);
4775 if (value == 0)
4776 return "0";
4777
4778 std::string result;
4779 while (value > 0)
4780 {
4781 word64 digit = value % base;
4782 result = char((digit < 10 ? '0' : (CH - 10)) + digit) + result;
4783 value /= base;
4784 }
4785 return result;
4786 }
4787
4788 #ifndef CRYPTOPP_NO_ASSIGN_TO_INTEGER
4789 // Allow the linker to discard Integer code if not needed.
4790 // Also see http://github.com/weidai11/cryptopp/issues/389.
4791 bool AssignIntToInteger(const std::type_info &valueType, void *pInteger, const void *pInt)
4792 {
4793 if (valueType != typeid(Integer))
4794 return false;
4795 *reinterpret_cast<Integer *>(pInteger) = *reinterpret_cast<const int *>(pInt);
4796 return true;
4797 }
4798 #endif // CRYPTOPP_NO_ASSIGN_TO_INTEGER
4799
4800 // *************************** C++ Static Initialization ***************************
4801
4802 class InitInteger
4803 {
4804 public:
4805 InitInteger()
4806 {
4807 SetFunctionPointers();
4808 }
4809 };
4810
4811 // This is not really needed because each Integer can dynamically initialize
4812 // itself, but we take a peephole optimization and initialize the class once
4813 // if init priorities are available. Dynamic initialization will be used if
4814 // init priorities are not available.
4815
4816 #if defined(HAVE_GCC_INIT_PRIORITY)
4817 const InitInteger s_init __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 10))) = InitInteger();
4818 const Integer g_zero __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 11))) = Integer(0L);
4819 const Integer g_one __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 12))) = Integer(1L);
4820 const Integer g_two __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 13))) = Integer(2L);
4821 #elif defined(HAVE_MSC_INIT_PRIORITY)
4822 #pragma warning(disable: 4075)
4823 #pragma init_seg(".CRT$XCU")
4824 const InitInteger s_init;
4825 const Integer g_zero(0L);
4826 const Integer g_one(1L);
4827 const Integer g_two(2L);
4828 #pragma warning(default: 4075)
4829 #elif HAVE_XLC_INIT_PRIORITY
4830 // XLC needs constant, not a define
4831 #pragma priority(280)
4832 const InitInteger s_init;
4833 const Integer g_zero(0L);
4834 const Integer g_one(1L);
4835 const Integer g_two(2L);
4836 #else
4837 const InitInteger s_init;
4838 #endif
4839
4840 // ***************** Library code ********************
4841
4842 const Integer &Integer::Zero()
4843 {
4844 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
4845 return g_zero;
4846 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
4847 static const Integer s_zero(0L);
4848 return s_zero;
4849 #else // Potential memory leak. Avoid if possible.
4850 return Singleton<Integer, NewInteger<0L> >().Ref();
4851 #endif
4852 }
4853
4854 const Integer &Integer::One()
4855 {
4856 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
4857 return g_one;
4858 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
4859 static const Integer s_one(1L);
4860 return s_one;
4861 #else // Potential memory leak. Avoid if possible.
4862 return Singleton<Integer, NewInteger<1L> >().Ref();
4863 #endif
4864 }
4865
4866 const Integer &Integer::Two()
4867 {
4868 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
4869 return g_two;
4870 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
4871 static const Integer s_two(2L);
4872 return s_two;
4873 #else // Potential memory leak. Avoid if possible.
4874 return Singleton<Integer, NewInteger<2L> >().Ref();
4875 #endif
4876 }
4877
4878 NAMESPACE_END
4879
4880 #endif // CRYPTOPP_IMPORTS
ConstByteArrayParameter
Used to pass byte array input as part of a NameValuePairs object.
Definition: algparam.h:20
InitInteger
Definition: integer.cpp:4802
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:202
Integer::WordCount
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
Definition: integer.cpp:3326
Integer::MultiplicativeInverse
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
Definition: integer.cpp:4378
ModularArithmetic::Reduce
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4572
Integer::NotZero
bool NotZero() const
Determines if the Integer is non-0.
Definition: integer.h:333
algparam.h
Classes for working with NameValuePairs.
Integer::Or
Integer Or(const Integer &t) const
Bitwise OR.
Definition: integer.cpp:3793
Integer::operator|=
Integer & operator|=(const Integer &t)
Bitwise OR Assignment.
Definition: integer.cpp:4049
SecBlock::swap
void swap(SecBlock< T, A > &b)
Swap contents with another SecBlock.
Definition: secblock.h:1035
Integer::And
Integer And(const Integer &t) const
Bitwise AND.
Definition: integer.cpp:3767
Integer::PRIME
a number which is probabilistically prime
Definition: integer.h:95
misc.h
Utility functions for the Crypto++ library.
Integer::Plus
Integer Plus(const Integer &b) const
Addition.
Definition: integer.cpp:3919
BufferedTransformation::Peek
virtual size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Definition: cryptlib.cpp:550
ByteOrder
ByteOrder
Provides the byte ordering.
Definition: cryptlib.h:143
Singleton
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:291
SecBlock::CleanNew
void CleanNew(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:974
Integer::UNSIGNED
an unsigned value
Definition: integer.h:85
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:363
Integer::IsSquare
bool IsSquare() const
Determine whether this integer is a perfect square.
Definition: integer.cpp:4367
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3426
DEREncodeUnsigned
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
Definition: asn.h:461
RandomNumberGenerator::GenerateBlock
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: cryptlib.cpp:311
ConstByteArrayParameter::size
size_t size() const
Length of the memory block.
Definition: algparam.h:84
BitsToBytes
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
Definition: misc.h:846
pubkey.h
This file contains helper classes/functions for implementing public key algorithms.
Integer::DEREncodeAsOctetString
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
Encode absolute value as big-endian octet string.
Definition: integer.cpp:3449
Integer::operator=
Integer & operator=(const Integer &t)
Assignment.
Definition: integer.cpp:3088
FirstPrime
bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
Definition: nbtheory.cpp:379
KDF2_RNG
Definition: integer.cpp:3529
Integer::Gcd
static Integer Gcd(const Integer &a, const Integer &n)
Calculate greatest common divisor.
Definition: integer.cpp:4402
SecBlock::resize
void resize(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:1025
Integer::operator+=
Integer & operator+=(const Integer &t)
Addition Assignment.
Definition: integer.cpp:3942
BitsToWords
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
Definition: misc.h:866
NewInteger
Definition: integer.cpp:127
PutWord
void PutWord(bool assumeAligned, ByteOrder order, byte *block, T value, const byte *xorBlock=NULL)
Access a block of memory.
Definition: misc.h:2362
BytePrecision
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
Definition: misc.h:727
SecBlock::CleanGrow
void CleanGrow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:1007
Integer::operator--
Integer & operator--()
Pre-decrement.
Definition: integer.cpp:3747
AbstractRing::CascadeExponentiate
virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition: algebra.cpp:323
SecBlock
Secure memory block with allocator and cleanup.
Definition: secblock.h:682
ModularArithmetic::Inverse
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
Definition: integer.cpp:4589
Integer::ConvertToLong
signed long ConvertToLong() const
Convert the Integer to Long.
Definition: integer.cpp:3009
ModularArithmetic::Subtract
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Definition: integer.cpp:4555
Integer::OpenPGPDecode
void OpenPGPDecode(const byte *input, size_t inputLen)
Decode from OpenPGP format.
Definition: integer.cpp:3482
Integer::Signedness
Signedness
Used when importing and exporting integers.
Definition: integer.h:83
ModularArithmetic::MaxElementByteLength
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
Definition: modarith.h:232
oids.h
ASN.1 object identifiers for algorthms and schemes.
Square
Square block cipher.
Definition: square.h:24
smartptr.h
Classes for automatic resource management.
IsP4
bool IsP4()
Determines if the CPU is an Intel P4.
Definition: cpu.h:236
Integer::IsNegative
bool IsNegative() const
Determines if the Integer is negative.
Definition: integer.h:336
ByteQueue::MaxRetrievable
lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: queue.h:33
config.h
Library configuration file.
MontgomeryRepresentation::MontgomeryRepresentation
MontgomeryRepresentation(const Integer &modulus)
Construct a MontgomeryRepresentation.
Definition: integer.cpp:4625
Integer::DivideByPowerOf2
static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n)
Extended Division.
Definition: integer.cpp:4191
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:38
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1349
BytesToWords
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
Definition: misc.h:856
stdcpp.h
Common C++ header files.
Integer::Randomize
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3497
IntToString< word64 >
std::string IntToString< word64 >(word64 value, unsigned int base)
Converts an unsigned value to a string.
Definition: integer.cpp:4767
SecBlock::New
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:959
Integer::SetByte
void SetByte(size_t n, byte value)
Set the n-th byte to value.
Definition: integer.cpp:3134
Integer::InverseMod
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
Definition: integer.cpp:4407
Integer::NEGATIVE
the value is negative
Definition: integer.h:77
SecByteBlock
SecBlock<byte> typedef.
Definition: secblock.h:1052
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:309
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1564
Integer::IsPositive
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:342
Integer::NotNegative
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:339
ModularArithmetic::Add
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
Definition: integer.cpp:4515
Integer::One
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:4854
ModularArithmetic::Accumulate
Integer & Accumulate(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4535
P1363_KDF2
P1363 key derivation function.
Definition: pubkey.h:729
LITTLE_ENDIAN_ORDER
byte order is little-endian
Definition: cryptlib.h:145
Integer::Sign
Sign
Used internally to represent the integer.
Definition: integer.h:73
MontgomeryRepresentation::ConvertIn
Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition: modarith.h:292
Integer::operator!
bool operator!() const
Negation.
Definition: integer.cpp:3083
member_ptr
Pointer that overloads operator ->
Definition: smartptr.h:36
Integer::IsUnit
bool IsUnit() const
Determine if 1 or -1.
Definition: integer.cpp:4373
Integer::ByteCount
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition: integer.cpp:3331
secblock.h
Classes and functions for secure memory allocations.
ModularArithmetic::DEREncodeElement
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Definition: integer.cpp:4494
Integer::Modulo
Integer Modulo(const Integer &b) const
Remainder.
Definition: integer.cpp:4226
ArraySink
Copy input to a memory buffer.
Definition: filters.h:1136
ModularArithmetic::BERDecodeElement
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
Definition: integer.cpp:4499
Integer::MinEncodedSize
size_t MinEncodedSize(Signedness sign=UNSIGNED) const
Minimum number of bytes to encode this integer.
Definition: integer.cpp:3388
Integer::DividedBy
Integer DividedBy(const Integer &b) const
Division.
Definition: integer.cpp:4219
ModularArithmetic::CascadeExponentiate
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
Definition: integer.cpp:4601
Integer::Times
Integer Times(const Integer &b) const
Multiplication.
Definition: integer.cpp:4115
Integer::ANY
a number with no special properties
Definition: integer.h:93
ConstByteArrayParameter::begin
const byte * begin() const
Pointer to the first byte in the memory block.
Definition: algparam.h:80
BufferedTransformation::Put
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1586
Integer::operator++
Integer & operator++()
Pre-increment.
Definition: integer.cpp:3726
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:502
Integer::swap
void swap(Integer &a)
Swaps this Integer with another Integer.
Definition: integer.cpp:3164
Integer::Integer
Integer()
Creates the zero integer.
Definition: integer.cpp:2955
TrailingZeros
unsigned int TrailingZeros(word32 v)
Determines the number of trailing 0-bits in a value.
Definition: misc.h:775
Integer::operator<<=
Integer & operator<<=(size_t n)
Left-shift Assignment.
Definition: integer.cpp:4011
Integer::IsZero
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:330
Integer::OpenPGPDecodeErr
Exception thrown when an error is encountered decoding an OpenPGP integer.
Definition: integer.h:282
Integer::Negate
void Negate()
Reverse the Sign of the Integer.
Definition: integer.cpp:4314
Integer::Compare
int Compare(const Integer &a) const
Perform signed comparison.
Definition: integer.cpp:4331
Crop
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition: misc.h:834
Integer::BERDecodeAsOctetString
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
Decode nonnegative value from big-endian octet string.
Definition: integer.cpp:3456
PrimeSelector
Application callback to signal suitability of a cabdidate prime.
Definition: nbtheory.h:113
ConditionalSwapPointers
void ConditionalSwapPointers(bool c, T &a, T &b)
Performs a branchless swap of pointers a and b if condition c is true.
Definition: misc.h:1210
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:3076
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
pch.h
Precompiled header file.
AbstractRing::Exponentiate
virtual Element Exponentiate(const Element &a, const Integer &e) const
Raises a base to an exponent in the group.
Definition: algebra.cpp:316
MontgomeryRepresentation::Multiply
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: integer.cpp:4636
Integer::SIGNED
a signed value
Definition: integer.h:87
Integer::OpenPGPEncode
size_t OpenPGPEncode(byte *output, size_t bufferSize) const
Encode absolute value in OpenPGP format.
Definition: integer.cpp:3465
ModularArithmetic::Half
const Integer & Half(const Integer &a) const
Divides an element by 2.
Definition: integer.cpp:4504
Integer::Two
static const Integer & Two()
Integer representing 2.
Definition: integer.cpp:4866
BufferedTransformation::Skip
virtual lword Skip(lword skipMax=LWORD_MAX)
Discard skipMax bytes from the output buffer.
Definition: cryptlib.cpp:573
DWord
Definition: integer.cpp:262
MontgomeryRepresentation::Square
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: integer.cpp:4649
Integer::operator^=
Integer & operator^=(const Integer &t)
Bitwise XOR Assignment.
Definition: integer.cpp:4070
MEMORY_BARRIER
#define MEMORY_BARRIER
A memory barrier.
Definition: misc.h:255
Integer::RandomNumberType
RandomNumberType
Properties of a random integer.
Definition: integer.h:91
Name::Seed
const char * Seed()
ConstByteArrayParameter.
Definition: argnames.h:19
Integer::IsEven
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:348
BIG_ENDIAN_ORDER
byte order is big-endian
Definition: cryptlib.h:147
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:563
StringStore
String-based implementation of Store interface.
Definition: filters.h:1195
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:60
Integer::Divide
static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d)
Extended Division.
Definition: integer.cpp:4173
ModularArithmetic::ModularArithmetic
ModularArithmetic(const Integer &modulus=Integer::One())
Construct a ModularArithmetic.
Definition: modarith.h:49
BERDecodeError
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:69
ByteQueue
Data structure used to store byte strings.
Definition: queue.h:18
cpu.h
Functions for CPU features and intrinsics.
asn.h
Classes and functions for working with ANS.1 objects.
sha.h
Classes for SHA-1 and SHA-2 family of message digests.
Integer::SetBit
void SetBit(size_t n, bool value=1)
Set the n-th bit to value.
Definition: integer.cpp:3110
BufferedTransformation::GetWord16
size_t GetWord16(word16 &value, ByteOrder order=BIG_ENDIAN_ORDER)
Retrieve a 16-bit word.
Definition: cryptlib.cpp:793
SecBlock::begin
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:766
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3340
Name::PointerToPrimeSelector
const char * PointerToPrimeSelector()
const PrimeSelector *
Definition: argnames.h:42
filters.h
Implementation of BufferedTransformation&#39;s attachment interface.
nbtheory.h
Classes and functions for number theoretic operations.
Integer::GetByte
byte GetByte(size_t i) const
Provides the i-th byte of the Integer.
Definition: integer.cpp:3124
Integer::DivideByZero
Exception thrown when division by 0 is encountered.
Definition: integer.h:55
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:319
Integer::Encode
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
Definition: integer.cpp:3404
Integer::Squared
Integer Squared() const
Multiply this integer by itself.
Definition: integer.h:609
SaturatingSubtract1
T1 SaturatingSubtract1(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 1.
Definition: misc.h:963
BufferedTransformation::MaxRetrievable
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:504
Integer::RandomNumberNotFound
Exception thrown when a random number cannot be found that satisfies the condition.
Definition: integer.h:63
Integer::GenerateRandomNoThrow
bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition: integer.cpp:3551
MontgomeryRepresentation
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:274
DERGeneralEncoder
DER General Encoder.
Definition: asn.h:291
HasSSE2
bool HasSSE2()
Determines SSE2 availability.
Definition: cpu.h:116
Integer::Minus
Integer Minus(const Integer &b) const
Subtraction.
Definition: integer.cpp:3965
KDF2_RNG::GenerateBlock
void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: integer.cpp:3538
Integer::Decode
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
Definition: integer.cpp:3349
BufferedTransformation::PutWord16
size_t PutWord16(word16 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 16-bit word for processing.
Definition: cryptlib.cpp:745
MontgomeryRepresentation::CascadeExponentiate
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
Definition: modarith.h:306
DEREncodeOctetString
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
Definition: asn.cpp:104
ModularArithmetic::SimultaneousExponentiate
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the ring.
Definition: integer.cpp:4612
integer.h
Multiple precision integer with arithmetic operations.
Integer::Xor
Integer Xor(const Integer &t) const
Bitwise XOR.
Definition: integer.cpp:3819
Integer::Zero
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:4842
STDMAX
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:574
EuclideanDomainOf
Euclidean domain.
Definition: algebra.h:315
SecBlock::Grow
void Grow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:989
Integer::BERDecode
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3433
IntToString< Integer >
std::string IntToString< Integer >(Integer value, unsigned int base)
Converts an Integer to a string.
Definition: integer.cpp:4701
BufferedTransformation::Get
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:527
modarith.h
Class file for performing modular arithmetic.
CryptoPP
Crypto++ library namespace.
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:350
Integer::operator>>=
Integer & operator>>=(size_t n)
Right-shift Assignment.
Definition: integer.cpp:4023
Integer::GetBit
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Definition: integer.cpp:3100
Integer::SquareRoot
Integer SquareRoot() const
Extract square root.
Definition: integer.cpp:4349
BERGeneralDecoder
BER General Decoder.
Definition: asn.h:258
NameValuePairs::GetIntValue
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:386
Integer::IsConvertableToLong
bool IsConvertableToLong() const
Determines if the Integer is convertable to Long.
Definition: integer.cpp:2995
OID
Object Identifier.
Definition: asn.h:166
ByteQueue::Get
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: queue.cpp:301
Integer::AbsoluteValue
Integer AbsoluteValue() const
Retrieve the absolute value of this integer.
Definition: integer.cpp:3157
Integer::operator-=
Integer & operator-=(const Integer &t)
Subtraction Assignment.
Definition: integer.cpp:3988
BitPrecision
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:750
SecBlock::size
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:791
Word
Definition: integer.cpp:410
Integer::operator &=
Integer & operator &=(const Integer &t)
Bitwise AND Assignment.
ModularArithmetic::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Definition: integer.cpp:4486
Integer::GetBits
lword GetBits(size_t i, size_t n) const
Provides the low order bits of the Integer.
Definition: integer.cpp:3141
Integer::operator-
Integer operator-() const
Subtraction.
Definition: integer.cpp:3150
Integer::POSITIVE
the value is positive or 0
Definition: integer.h:75
MontgomeryRepresentation::MultiplicativeInverse
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition: integer.cpp:4675
MontgomeryRepresentation::SimultaneousExponentiate
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the ring.
Definition: modarith.h:309
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:351
AbstractRing::SimultaneousExponentiate
virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the Ring.
Definition: algebra.cpp:334
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:293
MontgomeryRepresentation::ConvertOut
Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
Definition: integer.cpp:4662