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
7NAMESPACE_BEGIN(CryptoPP)
8
9GF2_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
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
46GF2_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
99NAMESPACE_END
100