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