Fabcoin Core  0.16.2
P2P Digital Currency
gf2_32.cpp
Go to the documentation of this file.
1 // gf2_32.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "misc.h"
5 #include "gf2_32.h"
6 
8 
10 {
11  word32 table[4];
12  table[0] = 0;
13  table[1] = m_modulus;
14  if (a & 0x80000000)
15  {
16  table[2] = m_modulus ^ (a<<1);
17  table[3] = a<<1;
18  }
19  else
20  {
21  table[2] = a<<1;
22  table[3] = m_modulus ^ (a<<1);
23  }
24 
25 #if CRYPTOPP_FAST_ROTATE(32)
26  b = rotrFixed(b, 30U);
27  word32 result = table[b&2];
28 
29  for (int i=29; i>=0; --i)
30  {
31  b = rotlFixed(b, 1U);
32  result = (result<<1) ^ table[(b&2) + (result>>31)];
33  }
34 
35  return (b&1) ? result ^ a : result;
36 #else
37  word32 result = table[(b>>30) & 2];
38 
39  for (int i=29; i>=0; --i)
40  result = (result<<1) ^ table[((b>>i)&2) + (result>>31)];
41 
42  return (b&1) ? result ^ a : result;
43 #endif
44 }
45 
47 {
48  if (a <= 1) // 1 is a special case
49  return a;
50 
51  // warning - don't try to adapt this algorithm for another situation
53  word32 v0=0, v1=1, v2=1;
54 
55  CRYPTOPP_ASSERT(g1);
56 
57  while (!(g2 & 0x80000000))
58  {
59  g2 <<= 1;
60  v2 <<= 1;
61  }
62 
63  g2 <<= 1;
64  v2 <<= 1;
65 
66  g0 ^= g2;
67  v0 ^= v2;
68 
69  while (g0 != 1)
70  {
71  if (g1 < g0 || ((g0^g1) < g0 && (g0^g1) < g1))
72  {
74  g2 = g1;
75  v2 = v1;
76  }
77  else
78  {
80  g2 = g0; g0 = g1; g1 = g2;
81  v2 = v0; v0 = v1; v1 = v2;
82  }
83 
84  while ((g0^g2) >= g2)
85  {
87  g2 <<= 1;
88  v2 <<= 1;
89  }
90 
92  g0 ^= g2;
93  v0 ^= v2;
94  }
95 
96  return v0;
97 }
98 
GF(2^32) with polynomial basis.
Definition: gf2_32.h:16
Utility functions for the Crypto++ library.
Element MultiplicativeInverse(Element a) const
Definition: gf2_32.cpp:46
T rotlFixed(T x, unsigned int y)
Performs a left rotate.
Definition: misc.h:1263
#define g1(tab, w)
Definition: skipjack.cpp:56
#define NAMESPACE_BEGIN(x)
Definition: config.h:200
#define a(i)
Classes and functions for schemes over GF(2^32)
word32 Element
Definition: gf2_32.h:19
#define g0(tab, w)
Definition: skipjack.cpp:55
#define b(i, j)
#define CRYPTOPP_ASSERT(exp)
Definition: trap.h:92
void Multiply(word *R, word *T, const word *A, const word *B, size_t N)
Definition: integer.cpp:2324
#define NAMESPACE_END
Definition: config.h:201
#define g2(tab, w)
Definition: skipjack.cpp:57
unsigned int word32
Definition: config.h:231
T rotrFixed(T x, unsigned int y)
Performs a right rotate.
Definition: misc.h:1285
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:654
word32 m_modulus
Definition: gf2_32.h:68