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