|
1
by weidai
Initial revision |
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 |
||
7 |
NAMESPACE_BEGIN(CryptoPP) |
|
8 |
||
9 |
GF2_32::Element GF2_32::Multiply(Element a, Element b) const |
|
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 |
||
|
284
by weidai
optimizations |
25 |
#if CRYPTOPP_FAST_ROTATE(32)
|
|
1
by weidai
Initial revision |
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 |
||
46 |
GF2_32::Element GF2_32::MultiplicativeInverse(Element a) const |
|
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
|
|
52 |
word32 g0=m_modulus, g1=a, g2=a; |
|
53 |
word32 v0=0, v1=1, v2=1; |
|
54 |
||
55 |
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 |
{
|
|
73 |
assert(BitPrecision(g1) <= BitPrecision(g0)); |
|
74 |
g2 = g1; |
|
75 |
v2 = v1; |
|
76 |
}
|
|
77 |
else
|
|
78 |
{
|
|
79 |
assert(BitPrecision(g1) > BitPrecision(g0)); |
|
80 |
g2 = g0; g0 = g1; g1 = g2; |
|
81 |
v2 = v0; v0 = v1; v1 = v2; |
|
82 |
}
|
|
83 |
||
84 |
while ((g0^g2) >= g2) |
|
85 |
{
|
|
86 |
assert(BitPrecision(g0) > BitPrecision(g2)); |
|
87 |
g2 <<= 1; |
|
88 |
v2 <<= 1; |
|
89 |
}
|
|
90 |
||
91 |
assert(BitPrecision(g0) == BitPrecision(g2)); |
|
92 |
g0 ^= g2; |
|
93 |
v0 ^= v2; |
|
94 |
}
|
|
95 |
||
96 |
return v0; |
|
97 |
}
|
|
98 |
||
99 |
NAMESPACE_END
|