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 
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 
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 
258  {
259  DWord r = Multiply(a, b);
260  return r += c;
261  }
262 
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 
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 
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;
294  #endif
295  return r;
296  }
297 
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;
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
339  #else
340  word high;
341  word low;
342  #endif
343  };
344  union
345  {
346  #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
348  #endif
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 
371  {
372  Word r;
373  r.m_whole = (word)a * b;
374  return r;
375  }
376 
378  {
379  Word r;
380  r.m_whole = m_whole - a.m_whole;
381  return r;
382  }
383 
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
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:
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
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 
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  (
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)
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  (
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)
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 {
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 
700 }
701 
702 CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
703 {
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 
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 {
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 
799 }
800 CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Sub(size_t N, word *C, const word *A, const word *B)
801 {
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 
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
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
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
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
1216 
1217  Mul_8
1218 }
1219 
1220 void Baseline_Square2(word *R, const word *AA)
1221 {
1222  // http://github.com/weidai11/cryptopp/issues/188
1224 
1225  Squ_2
1226 }
1227 
1228 void Baseline_Square4(word *R, const word *AA)
1229 {
1230  // http://github.com/weidai11/cryptopp/issues/188
1232 
1233  Squ_4
1234 }
1235 
1236 void Baseline_Square8(word *R, const word *AA)
1237 {
1238  // http://github.com/weidai11/cryptopp/issues/188
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
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
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
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
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
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
1341 
1342  Mul_16
1343 }
1344 
1345 void Baseline_Square16(word *R, const word *AA)
1346 {
1347  // http://github.com/weidai11/cryptopp/issues/188
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
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
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)
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;
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 
2868 {
2869  if (!g_pAssignIntToInteger)
2870  {
2871  SetFunctionPointers();
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 
2893  : reg(2), sign(POSITIVE)
2894 {
2895  reg[0] = reg[1] = 0;
2896 }
2897 
2899  : reg(RoundupSize(t.WordCount())), sign(t.sign)
2900 {
2901  CopyWords(reg, t.reg, reg.size());
2902 }
2903 
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 
2926  : reg(2), sign(s)
2927 {
2928  reg[0] = low;
2929  reg[1] = high;
2930 }
2931 
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 {
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 {
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 {
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 
2993 {
2994  BERDecode(bt);
2995 }
2996 
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))
3006 }
3007 
3009 {
3010  Integer r((word)0, BitsToWords(e+1));
3011  r.SetBit(e);
3012  return r;
3013 }
3014 
3015 template <long i>
3017 {
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(); }
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(); }
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(); }
3044 {
3045  return s_two;
3046 }
3047 
3049 {
3050  return IsNegative() ? false : (reg[0]==0 && WordCount()==0);
3051 }
3052 
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 
3116 {
3117  Integer result(*this);
3118  result.Negate();
3119  return result;
3120 }
3121 
3123 {
3124  Integer result(*this);
3125  result.sign = POSITIVE;
3126  return result;
3127 }
3128 
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 
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 
3392 {
3393  DERGeneralEncoder enc(bt, INTEGER);
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 
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 
3414 {
3416  Encode(enc, length);
3417  enc.MessageEnd();
3418 }
3419 
3421 {
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 
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 
3451 {
3452  word16 bitCount;
3453  if (bt.GetWord16(bitCount) != 2 || bt.MaxRetrievable() < BitsToBytes(bitCount))
3454  throw OpenPGPDecodeErr();
3455  Decode(bt, BitsToBytes(bitCount));
3456 }
3457 
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 
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 
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:
3509 };
3510 
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;
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 
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 
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.
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.
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 
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 
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 
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);
3931  }
3932  }
3933  return *this;
3934 }
3935 
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 
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);
3975  }
3976  else
3977  PositiveSubtract(*this, t, *this);
3978  }
3979  return *this;
3980 }
3981 
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 
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 
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 
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 
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 
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 
4191 {
4192  Integer remainder, quotient;
4193  Integer::Divide(remainder, quotient, *this, b);
4194  return quotient;
4195 }
4196 
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 
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 
4286 {
4287  if (!!(*this)) // don't flip sign if *this==0
4288  sign = Sign(1-sign);
4289 }
4290 
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 
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 
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 
4366 {
4367  return EuclideanDomainOf<Integer>().Gcd(a, b);
4368 }
4369 
4371 {
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 
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 
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 
4434 {
4435  DERSequenceEncoder seq(bt);
4436  ASN1::prime_field().DEREncode(seq);
4437  m_modulus.DEREncode(seq);
4438  seq.MessageEnd();
4439 }
4440 
4442 {
4443  a.DEREncodeAsOctetString(out, MaxElementByteLength());
4444 }
4445 
4447 {
4448  a.BERDecodeAsOctetString(in, MaxElementByteLength());
4449 }
4450 
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 
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 
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 
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 
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 
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 
4581 }
4582 
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 
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 
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 
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 
4736 
4737 #endif
#define Mul_16
Definition: integer.cpp:941
Used to pass byte array input as part of a NameValuePairs object.
Definition: algparam.h:29
#define T1
Definition: integer.cpp:2170
#define AddWithCarry(u, a, b)
Definition: integer.cpp:191
Integer Minus(const Integer &b) const
Subtraction.
Definition: integer.cpp:3936
An invalid argument was detected.
Definition: cryptlib.h:184
lword RemainingLength() const
Definition: asn.h:255
void MultiplyByPower2Mod(word *R, const word *A, size_t k, const word *M, size_t N)
Definition: integer.cpp:2856
Integer And(const Integer &) const
Bitwise AND.
Definition: integer.cpp:3738
void Baseline_Square16(word *R, const word *AA)
Definition: integer.cpp:1345
#define M1
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Definition: integer.cpp:4433
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
Definition: integer.cpp:4548
void RecursiveMultiply(word *R, word *T, const word *A, const word *B, size_t N)
Definition: integer.cpp:2184
#define AddPrologue
Definition: integer.cpp:557
#define Mul_8
Definition: integer.cpp:924
unsigned int PrimeSearchInterval(const Integer &max)
Definition: nbtheory.cpp:257
Classes for working with NameValuePairs.
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: integer.cpp:4596
Integer & operator|=(const Integer &t)
Bitwise OR Assignment.
Definition: integer.cpp:4020
void CopyWords(word *r, const word *a, size_t n)
Definition: words.h:22
uint8_t byte
Definition: Common.h:57
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition: integer.cpp:4622
friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b)
Definition: integer.cpp:3814
void swap(SecBlock< T, A > &b)
Swap contents with another SecBlock.
Definition: secblock.h:714
#define T2
Definition: integer.cpp:2171
a number which is probabilistically prime
Definition: integer.h:89
word16 hword
Definition: config.h:307
#define Mul_End(k, i)
Definition: integer.cpp:1135
Utility functions for the Crypto++ library.
word operator/(word divisor)
Definition: integer.cpp:480
bool(CRYPTOPP_API * PAssignIntToInteger)(const std::type_info &valueType, void *pInteger, const void *pInt)
Definition: algparam.h:302
ByteOrder
Provides the byte ordering.
Definition: cryptlib.h:124
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:274
#define Bot_16
Definition: integer.cpp:1057
bool NotZero() const
Determines if the Integer is non-0.
Definition: integer.h:327
Integer m_result
Definition: modarith.h:256
unsigned int AlmostInverse(word *R, word *T, const word *A, size_t NA, const word *M, size_t N)
Definition: integer.cpp:2760
bool AssignIntToInteger(const std::type_info &valueType, void *pInteger, const void *pInt)
Definition: integer.cpp:74
size_t CountWords(const word *X, size_t N)
Definition: words.h:9
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Definition: integer.cpp:3065
void CleanNew(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:660
void swap(dev::eth::Watch &_a, dev::eth::Watch &_b)
Definition: Interface.h:284
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
Definition: integer.cpp:3369
an unsigned value
Definition: integer.h:79
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
unsigned short word16
Definition: config.h:230
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4519
virtual size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Definition: cryptlib.cpp:534
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:345
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:350
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
Definition: asn.h:455
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: cryptlib.cpp:326
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
const T & STDMAX2(const T &a, const T &b)
Definition: integer.cpp:3885
#define Squ_4
Definition: integer.cpp:978
Definition: asn.h:30
Integer & operator=(const Integer &t)
Assignment.
Definition: integer.cpp:3053
bool operator!() const
Negation.
Definition: integer.cpp:3048
static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n)
greatest common divisor
Definition: integer.cpp:4365
void resize(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:705
Integer & operator+=(const Integer &t)
Addition Assignment.
Definition: integer.cpp:3913
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
Definition: misc.h:769
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Definition: integer.cpp:4502
#define g1(tab, w)
Definition: skipjack.cpp:56
#define T(i, x)
word64 dword
Definition: config.h:309
void MessageEnd()
Definition: asn.cpp:524
void PutWord(bool assumeAligned, ByteOrder order, byte *block, T value, const byte *xorBlock=NULL)
Access a block of memory.
Definition: misc.h:2123
#define Mul_Acc(i, j)
Definition: integer.cpp:1126
void Baseline_Square8(word *R, const word *AA)
Definition: integer.cpp:1236
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
Definition: misc.h:632
int PositiveCompare(const Integer &t) const
Definition: integer.cpp:4291
void CleanGrow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:689
#define NAMESPACE_BEGIN(x)
Definition: config.h:200
#define Squ_End(n)
Definition: integer.cpp:1184
void Baseline_Multiply4(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1202
#define Squ_8
Definition: integer.cpp:986
#define h(i)
Definition: sha.cpp:736
Integer & operator--()
Pre-decrement.
Definition: integer.cpp:3718
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:373
#define Bot_2
Definition: integer.cpp:1034
half_words m_halfs
Definition: integer.cpp:349
#define R1
Definition: integer.cpp:2175
#define Declare2Words(x)
Definition: integer.cpp:179
void Baseline_Multiply2(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1193
#define V1
#define Q(i)
Definition: cast.cpp:199
friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b)
Definition: integer.cpp:4066
Integer * operator()() const
Definition: integer.cpp:3018
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:342
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
Definition: integer.cpp:3291
void Baseline_MultiplyBottom2(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1244
void MontgomeryReduce(word *R, word *T, word *X, const word *M, const word *U, size_t N)
Definition: integer.cpp:2446
CRYPTOPP_DLL std::string IntToString< word64 >(word64 value, unsigned int base)
Converts an unsigned value to a string.
Definition: integer.cpp:4714
#define R(a, b)
Word operator-(Word a)
Definition: integer.cpp:377
void OpenPGPDecode(const byte *input, size_t inputLen)
Decode from OpenPGP format.
Definition: integer.cpp:3444
Signedness
Used when importing and exporting integers.
Definition: integer.h:77
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:524
#define g(i)
Definition: sha.cpp:735
int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B)
Definition: integer.cpp:858
ASN.1 object identifiers for algorthms and schemes.
#define Bot_4
Definition: integer.cpp:1039
Classes for automatic resource management.
size_t size() const
Length of the memory block.
Definition: algparam.h:93
void RecursiveInverseModPower2(word *R, word *T, const word *A, size_t N)
Definition: integer.cpp:2413
#define c(i)
byte GetByte(size_t i) const
Provides the i-th byte of the Integer.
Definition: integer.cpp:3089
Library configuration file.
MontgomeryRepresentation(const Integer &modulus)
Construct a MontgomeryRepresentation.
Definition: integer.cpp:4572
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
Ring of congruence classes modulo n.
Definition: modarith.h:34
std::hash for asio::adress
Definition: Common.h:323
#define X2
Interface for random number generators.
Definition: cryptlib.h:1188
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
Definition: misc.h:759
DWord(word low)
Definition: integer.cpp:216
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3458
KDF2_RNG(const byte *seed, size_t seedSize)
Definition: integer.cpp:3493
#define SubtractWithBorrow(u, a, b)
Definition: integer.cpp:192
size_t MinEncodedSize(Signedness sign=UNSIGNED) const
Minimum number of bytes to encode this integer.
Definition: integer.cpp:3354
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:647
#define AddEpilogue
Definition: integer.cpp:562
int Add(word *C, const word *A, const word *B, size_t N)
Definition: integer.cpp:2143
void Baseline_MultiplyBottom4(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1253
void SetByte(size_t n, byte value)
Set the n-th byte to value.
Definition: integer.cpp:3099
the value is negative
Definition: integer.h:71
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
BER Sequence Decoder.
Definition: asn.h:303
ExecStats::duration min
Definition: ExecStats.cpp:35
Interface for buffered transformations.
Definition: cryptlib.h:1352
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
Encode absolute value as big-endian octet string.
Definition: integer.cpp:3413
#define INTEL_NOPREFIX
Definition: cpu.h:85
lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: queue.h:35
const byte * begin() const
Pointer to the first byte in the memory block.
Definition: algparam.h:89
bool IsConvertableToLong() const
Determines if the Integer is convertable to Long.
Definition: integer.cpp:2932
Integer MultiplicativeInverse() const
return inverse if 1 or -1, otherwise return 0
Definition: integer.cpp:4349
if(a.IndicesBefore(b, len, lenIndices))
Definition: equihash.cpp:243
void(* PMul)(word *C, const word *A, const word *B)
Definition: integer.cpp:2067
word operator%(word a)
Definition: integer.cpp:490
DWord operator+(word a)
Definition: integer.cpp:274
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition: integer.cpp:3035
IntegerSecBlock reg
Definition: integer.h:632
#define Squ_Begin(n)
Definition: integer.cpp:1154
#define Mul_4
Definition: integer.cpp:915
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
Definition: integer.cpp:4462
byte order is little-endian
Definition: cryptlib.h:126
Sign
Used internally to represent the integer.
Definition: integer.h:67
word32 m_counter
Definition: integer.cpp:3507
void Baseline_MultiplyBottom16(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1353
Pointer that overloads operator ->
Definition: smartptr.h:39
#define GetBorrow(u)
Definition: integer.cpp:194
bool IsSquare() const
Determine whether this integer is a perfect square.
Definition: integer.cpp:4338
size_t OpenPGPEncode(byte *output, size_t bufferSize) const
Encode absolute value in OpenPGP format.
Definition: integer.cpp:3429
#define Mul_SaveAcc(k, i, j)
Definition: integer.cpp:1129
Classes and functions for secure memory allocations.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3305
SecByteBlock m_counterAndSeed
Definition: integer.cpp:3508
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
Definition: integer.cpp:4446
bool IsUnit() const
is 1 or -1
Definition: integer.cpp:4344
Copy input to a memory buffer.
Definition: filters.h:1101
void MultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N)
Definition: integer.cpp:2275
Integer operator<<(size_t n) const
Left-shift.
Definition: integer.h:559
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
ASN Strings.
Definition: asn.cpp:104
#define a(i)
#define X0
void ShiftWordsLeftByWords(word *r, size_t n, size_t shiftWords)
Definition: words.h:96
CRYPTOPP_DLL std::string IntToString< Integer >(Integer value, unsigned int base)
Converts an Integer to a string.
Definition: integer.cpp:4648
PAssignIntToInteger g_pAssignIntToInteger
Definition: algparam.cpp:12
#define CRYPTOPP_ALIGN_DATA(x)
Definition: config.h:338
void(* PSqu)(word *C, const word *A)
Definition: integer.cpp:2068
Integer SquareRoot() const
Extract square root.
Definition: integer.cpp:4320
#define x(i)
IntegerSecBlock m_workspace
Definition: modarith.h:311
const unsigned int WORD_BITS
Definition: config.h:317
#define Acc2WordsBy1(a, b)
Definition: integer.cpp:200
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:336
int(CRYPTOPP_FASTCALL * PAdd)(size_t N, word *C, const word *A, const word *B)
Definition: integer.cpp:2066
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:337
#define R3
Definition: integer.cpp:2177
a number with no special properties
Definition: integer.h:87
Integer Squared() const
Multiply this integer by itself.
Definition: integer.h:570
void Baseline_Square2(word *R, const word *AA)
Definition: integer.cpp:1220
#define B0
Definition: integer.cpp:2166
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1376
Integer & operator++()
Pre-increment.
Definition: integer.cpp:3696
bool IsNegative() const
Determines if the Integer is negative.
Definition: integer.h:330
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:498
void swap(Integer &a)
Swaps this Integer with another Integer.
Definition: integer.cpp:3129
Integer()
Creates the zero integer.
Definition: integer.cpp:2892
unsigned int TrailingZeros(word32 v)
Determines the number of trailing 0-bits in a value.
Definition: misc.h:679
#define HighWord(a)
Definition: integer.cpp:189
friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b)
Definition: integer.cpp:3844
Word(hword low, hword high)
Definition: integer.cpp:368
Integer & operator<<=(size_t n)
Left-shift Assignment.
Definition: integer.cpp:3982
signed long ConvertToLong() const
Convert the Integer to Long.
Definition: integer.cpp:2946
#define AssignWord(a, b)
Definition: integer.cpp:185
D DivideFourWordsByTwo(S *T, const D &Al, const D &Ah, const D &B)
Definition: integer.cpp:457
Exception thrown when an error is encountered decoding an OpenPGP integer.
Definition: integer.h:276
void Negate()
Reverse the Sign of the Integer.
Definition: integer.cpp:4285
else
Definition: equihash.cpp:246
#define Top_SaveAcc1(i, j)
Definition: integer.cpp:1287
#define g0(tab, w)
Definition: skipjack.cpp:55
ExecStats::duration max
Definition: ExecStats.cpp:36
hword GetHighHalf() const
Definition: integer.cpp:404
#define Bot_Acc(i, j)
Definition: integer.cpp:1147
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition: misc.h:737
Integer m_modulus
Definition: modarith.h:255
Integer Times(const Integer &b) const
Multiplication.
Definition: integer.cpp:4086
bool IsDefiniteLength() const
Definition: asn.h:254
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
Decode nonnegative value from big-endian octet string.
Definition: integer.cpp:3420
#define Squ_2
Definition: integer.cpp:974
#define GetCarry(u)
Definition: integer.cpp:193
static DWord Multiply(word a, word b)
Definition: integer.cpp:244
Word()
Definition: integer.cpp:364
Application callback to signal suitability of a cabdidate prime.
Definition: nbtheory.h:80
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
#define LowWord(a)
Definition: integer.cpp:188
#define Squ_Acc(i, j)
Definition: integer.cpp:1177
static Integer CRYPTOPP_API Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:3008
DWord(word low, word high)
Definition: integer.cpp:225
void AsymmetricMultiply(word *R, word *T, const word *A, size_t NA, const word *B, size_t NB)
Definition: integer.cpp:2344
#define Bot_End(n)
Definition: integer.cpp:1150
Multiple precision integer with arithmetic operations.
Definition: integer.h:43
#define V0
hword GetHighHalfAsBorrow() const
Definition: integer.cpp:405
#define R2
Definition: integer.cpp:2176
void SetWords(word *r, word a, size_t n)
Definition: words.h:16
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
void Divide(word *R, word *Q, word *T, const word *A, size_t NA, const word *B, size_t NB)
Definition: integer.cpp:2692
void MultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N)
Definition: integer.cpp:2334
DWord & operator+=(word a)
Definition: integer.cpp:263
#define X3
void Baseline_MultiplyBottom8(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1262
unsigned long long word64
Definition: config.h:240
a signed value
Definition: integer.h:81
#define Top_Begin(n)
Definition: integer.cpp:1271
void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N)
Definition: integer.cpp:2251
#define R0
Definition: integer.cpp:2174
#define MAYBE_CONST
Definition: integer.cpp:54
bool operator!() const
Definition: integer.cpp:315
static const Integer &CRYPTOPP_API Two()
Integer representing 2.
Definition: integer.cpp:3043
Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
Definition: integer.cpp:4609
virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition: algebra.cpp:323
virtual lword Skip(lword skipMax=LWORD_MAX)
Discard skipMax bytes from the output buffer.
Definition: cryptlib.cpp:553
Integer DividedBy(const Integer &b) const
Division.
Definition: integer.cpp:4190
void Baseline_MultiplyTop2(word *R, const word *A, const word *B, word L)
Definition: integer.cpp:1294
void Baseline_Multiply8(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1211
Integer & operator^=(const Integer &t)
Bitwise XOR Assignment.
Definition: integer.cpp:4041
RandomNumberType
Properties of a random integer.
Definition: integer.h:85
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
Definition: integer.cpp:4536
void ShiftWordsRightByWords(word *r, size_t n, size_t shiftWords)
Definition: words.h:107
const T * get() const
Definition: smartptr.h:52
byte order is big-endian
Definition: cryptlib.h:128
const unsigned int WORD_SIZE
Definition: config.h:316
volatile double sum
Definition: Examples.cpp:23
hword operator/(hword divisor)
Definition: integer.cpp:392
#define b(i, j)
Safely right shift values when undefined behavior could occur.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:477
String-based implementation of Store interface.
Definition: filters.h:1155
#define CRYPTOPP_ASSERT(exp)
Definition: trap.h:92
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
void RecursiveSquare(word *R, word *T, const word *A, size_t N)
Definition: integer.cpp:2226
ModularArithmetic(const Integer &modulus=Integer::One())
Construct a ModularArithmetic.
Definition: modarith.h:45
#define Mul_Begin(n)
Definition: integer.cpp:1118
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:69
Data structure used to store byte strings.
Definition: queue.h:20
Functions for CPU features and intrinsics.
Classes and functions for working with ANS.1 objects.
Classes for SHA-1 and SHA-2 family of message digests.
void SetBit(size_t n, bool value=1)
Set the n-th bit to value.
Definition: integer.cpp:3075
size_t GetWord16(word16 &value, ByteOrder order=BIG_ENDIAN_ORDER)
Retrieve a 16-bit word.
Definition: cryptlib.cpp:762
#define X(name)
Definition: net.cpp:642
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:499
#define Top_SaveAcc0(i, j)
Definition: integer.cpp:1282
Signature sign(Secret const &_k, h256 const &_hash)
Returns siganture of message hash.
Definition: Common.cpp:233
Integer & Accumulate(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4482
Implementation of BufferedTransformation&#39;s attachment interface.
void MessageEnd()
Definition: asn.cpp:456
Classes and functions for number theoretic operations.
#define f(x)
Definition: gost.cpp:57
void Baseline_MultiplyTop4(word *R, const word *AA, const word *BB, word L)
Definition: integer.cpp:1303
Word(word value)
Definition: integer.cpp:367
#define A0
Definition: integer.cpp:2164
const Integer & Half(const Integer &a) const
Divides an element by 2.
Definition: integer.cpp:4451
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3391
Exception thrown when division by 0 is encountered.
Definition: integer.h:49
void XorWords(word *r, const word *a, const word *b, size_t n)
Definition: words.h:32
DER Sequence Encoder.
Definition: asn.h:313
bool operator!() const
Definition: integer.cpp:397
#define Bot_8
Definition: integer.cpp:1046
#define T0
Definition: integer.cpp:2169
T1 SaturatingSubtract1(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 1.
Definition: misc.h:862
#define ATT_NOPREFIX
Definition: cpu.h:87
void Baseline_MultiplyTop16(word *R, const word *AA, const word *BB, word L)
Definition: integer.cpp:1362
Exception thrown when a random number cannot be found that satisfies the condition.
Definition: integer.h:57
bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Definition: integer.cpp:3511
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:271
void Baseline_MultiplyTop8(word *R, const word *AA, const word *BB, word L)
Definition: integer.cpp:1317
DER General Encoder.
Definition: asn.h:284
uint8_t const size_t const size
Definition: sha3.h:20
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
void * memcpy(void *a, const void *b, size_t c)
void Baseline_Square4(word *R, const word *AA)
Definition: integer.cpp:1228
#define CRYPTOPP_UNUSED(x)
Definition: config.h:741
static DWord MultiplyAndAdd(word a, word b, word c)
Definition: integer.cpp:257
#define P
#define Bot_SaveAcc(k, i, j)
Definition: integer.cpp:1142
word GetHighHalf() const
Definition: integer.cpp:327
#define B1
Definition: integer.cpp:2167
void Multiply(word *R, word *T, const word *A, const word *B, size_t N)
Definition: integer.cpp:2324
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
Definition: modarith.h:303
Integer Plus(const Integer &b) const
Addition.
Definition: integer.cpp:3890
void(* PMulTop)(word *C, const word *A, const word *B, word L)
Definition: integer.cpp:2069
uint8_t byte
Definition: Common.h:10
N diff(N const &_a, N const &_b)
Definition: Common.h:212
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: integer.cpp:4583
void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: integer.cpp:3499
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:4370
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
Definition: integer.cpp:3314
Word operator-(hword a)
Definition: integer.cpp:384
Sign sign
Definition: integer.h:633
size_t PutWord16(word16 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 16-bit word for processing.
Definition: cryptlib.cpp:714
word GetLowHalf() const
Definition: integer.cpp:326
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:496
word ShiftWordsRightByBits(word *r, size_t n, unsigned int shiftBits)
Definition: words.h:82
Multiple precision integer with arithmetic operations.
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Definition: integer.cpp:4441
#define CRYPTOPP_FASTCALL
Definition: config.h:363
void Square(word *R, word *T, const word *A, size_t N)
Definition: integer.cpp:2329
Safely left shift values when undefined behavior could occur.
static const Integer &CRYPTOPP_API Zero()
Integer representing 0.
Definition: integer.cpp:3027
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:487
Euclidean domain.
Definition: algebra.h:315
#define NAMESPACE_END
Definition: config.h:201
hword GetLowHalf() const
Definition: integer.cpp:403
int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B)
Definition: integer.cpp:874
void Grow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:673
#define e(i)
Definition: sha.cpp:733
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3398
lword GetBits(size_t i, size_t n) const
Provides the low order bits of the Integer.
Definition: integer.cpp:3106
#define MultiplyWords(p, a, b)
Definition: integer.cpp:183
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:515
Class file for performing modular arithmetic.
Integer Xor(const Integer &) const
Bitwise XOR.
Definition: integer.cpp:3790
int Subtract(word *C, const word *A, const word *B, size_t N)
Definition: integer.cpp:2152
Integer operator>>(size_t n) const
Right-shift.
Definition: integer.h:557
word64 lword
Definition: config.h:245
Integer & operator>>=(size_t n)
Right-shift Assignment.
Definition: integer.cpp:3994
#define S(a)
Definition: mars.cpp:50
Integer Or(const Integer &) const
Bitwise OR.
Definition: integer.cpp:3764
word GetHighHalfAsBorrow() const
Definition: integer.cpp:328
friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor)
Definition: integer.cpp:4115
#define Squ_16
Definition: integer.cpp:1002
#define CRYPTOPP_DLL
Definition: config.h:704
size_type SizeInBytes() const
Provides the number of bytes in the SecBlock.
Definition: secblock.h:538
BER General Decoder.
Definition: asn.h:246
Integer operator-() const
Subtraction.
Definition: integer.cpp:3115
unsigned int word32
Definition: config.h:231
#define T3
Definition: integer.cpp:2172
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()
Definition: integer.cpp:210
word ShiftWordsLeftByBits(word *r, size_t n, unsigned int shiftBits)
Definition: words.h:68
dword m_whole
Definition: integer.cpp:347
uint32_t ch(uint32_t x, uint32_t y, uint32_t z)
Definition: picosha2.h:73
int Compare(const Integer &a) const
Perform signed comparison.
Definition: integer.cpp:4302
#define M0
#define Top_Acc(i, j)
Definition: integer.cpp:1278
#define A1
Definition: integer.cpp:2165
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
void Baseline_Multiply16(word *R, const word *AA, const word *BB)
Definition: integer.cpp:1336
Object Identifier.
Definition: asn.h:166
Integer Modulo(const Integer &b) const
Remainder.
Definition: integer.cpp:4197
void DivideByPower2Mod(word *R, const word *A, size_t k, const word *M, size_t N)
Definition: integer.cpp:2835
evm_result m_result
Definition: JitVM.cpp:271
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: queue.cpp:300
void OrWords(word *r, const word *a, const word *b, size_t n)
Definition: words.h:56
void reset(T *p=0)
Definition: smartptr.h:72
static Word Multiply(hword a, hword b)
Definition: integer.cpp:370
Integer & operator&=(const Integer &t)
Bitwise AND Assignment.
Definition: integer.cpp:4008
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 a)
Definition: integer.cpp:286
word m_whole
Definition: integer.cpp:408
#define MAYBE_UNCONST_CAST
Definition: integer.cpp:55
S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULL)
Definition: integer.cpp:413
Integer & operator-=(const Integer &t)
Subtraction Assignment.
Definition: integer.cpp:3959
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:654
word32 word
Definition: config.h:308
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition: integer.cpp:3296
DWord operator-(word a)
Definition: integer.cpp:298
virtual Element Exponentiate(const Element &a, const Integer &e) const
Raises a base to an exponent in the group.
Definition: algebra.cpp:316
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() const
Definition: integer.cpp:402
Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition: modarith.h:289
the value is positive or 0
Definition: integer.h:69
Integer AbsoluteValue() const
Retrieve the absolute value of this integer.
Definition: integer.cpp:3122
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:333
#define Mul_2
Definition: integer.cpp:910
Interface for retrieving values given their names.
Definition: cryptlib.h:279
#define CRYPTOPP_SECTION_ALIGN16
Definition: config.h:347
void AndWords(word *r, const word *a, const word *b, size_t n)
Definition: words.h:44