TLA Line data Source code
1 : // evmone: Fast Ethereum Virtual Machine implementation
2 : // Copyright 2023 The evmone Authors.
3 : // SPDX-License-Identifier: Apache-2.0
4 :
5 : #include <evmmax/evmmax.hpp>
6 :
7 : using namespace intx;
8 :
9 : namespace evmmax
10 : {
11 : namespace
12 : {
13 : /// Compute the modulus inverse for Montgomery multiplication, i.e. N': mod⋅N' = 2⁶⁴-1.
14 : ///
15 : /// @param mod0 The least significant word of the modulus.
16 CBC 110 : inline constexpr uint64_t compute_mod_inv(uint64_t mod0) noexcept
17 : {
18 : // TODO: Find what is this algorithm and why it works.
19 110 : uint64_t base = 0 - mod0;
20 110 : uint64_t result = 1;
21 7150 : for (auto i = 0; i < 64; ++i)
22 : {
23 7040 : result *= base;
24 7040 : base *= base;
25 : }
26 110 : return result;
27 : }
28 :
29 : /// Compute R² % mod.
30 : template <typename UintT>
31 110 : inline UintT compute_r_squared(const UintT& mod) noexcept
32 : {
33 : // R is 2^num_bits, R² is 2^(2*num_bits) and needs 2*num_bits+1 bits to represent,
34 : // rounded to 2*num_bits+64) for intx requirements.
35 : static constexpr auto r2 = intx::uint<UintT::num_bits * 2 + 64>{1} << (UintT::num_bits * 2);
36 110 : return intx::udivrem(r2, mod).rem;
37 : }
38 :
39 7040 : inline constexpr std::pair<uint64_t, uint64_t> addmul(
40 : uint64_t t, uint64_t a, uint64_t b, uint64_t c) noexcept
41 : {
42 7040 : const auto p = umul(a, b) + t + c;
43 7040 : return {p[1], p[0]};
44 : }
45 : } // namespace
46 :
47 : template <typename UintT>
48 110 : ModArith<UintT>::ModArith(const UintT& modulus) noexcept
49 110 : : mod{modulus}, m_r_squared{compute_r_squared(modulus)}, m_mod_inv{compute_mod_inv(modulus[0])}
50 110 : {}
51 :
52 : template <typename UintT>
53 220 : UintT ModArith<UintT>::mul(const UintT& x, const UintT& y) const noexcept
54 : {
55 : // Coarsely Integrated Operand Scanning (CIOS) Method
56 : // Based on 2.3.2 from
57 : // High-Speed Algorithms & Architectures For Number-Theoretic Cryptosystems
58 : // https://www.microsoft.com/en-us/research/wp-content/uploads/1998/06/97Acar.pdf
59 :
60 : static constexpr auto S = UintT::num_words;
61 :
62 220 : intx::uint<UintT::num_bits + 64> t;
63 1100 : for (size_t i = 0; i != S; ++i)
64 : {
65 880 : uint64_t c = 0;
66 4400 : for (size_t j = 0; j != S; ++j)
67 3520 : std::tie(c, t[j]) = addmul(t[j], x[j], y[i], c);
68 880 : auto tmp = addc(t[S], c);
69 880 : t[S] = tmp.value;
70 880 : auto d = tmp.carry;
71 :
72 880 : c = 0;
73 880 : auto m = t[0] * m_mod_inv;
74 880 : std::tie(c, t[0]) = addmul(t[0], m, mod[0], c);
75 3520 : for (size_t j = 1; j != S; ++j)
76 2640 : std::tie(c, t[j - 1]) = addmul(t[j], m, mod[j], c);
77 880 : tmp = addc(t[S], c);
78 880 : t[S - 1] = tmp.value;
79 880 : t[S] = d + tmp.carry; // TODO: Carry is 0 for sparse modulus.
80 : }
81 :
82 220 : if (t >= mod) // TODO: cannot overflow if modulus is sparse (e.g. 255 bits).
83 UBC 0 : t -= mod;
84 :
85 CBC 220 : return static_cast<UintT>(t);
86 : }
87 :
88 : template <typename UintT>
89 220 : UintT ModArith<UintT>::to_mont(const UintT& x) const noexcept
90 : {
91 220 : return mul(x, m_r_squared);
92 : }
93 :
94 : template <typename UintT>
95 UBC 0 : UintT ModArith<UintT>::from_mont(const UintT& x) const noexcept
96 : {
97 0 : return mul(x, 1);
98 : }
99 :
100 : template <typename UintT>
101 0 : UintT ModArith<UintT>::add(const UintT& x, const UintT& y) const noexcept
102 : {
103 0 : const auto s = addc(x, y); // TODO: cannot overflow if modulus is sparse (e.g. 255 bits).
104 0 : const auto d = subc(s.value, mod);
105 0 : return (!s.carry && d.carry) ? s.value : d.value;
106 : }
107 :
108 : template <typename UintT>
109 0 : UintT ModArith<UintT>::sub(const UintT& x, const UintT& y) const noexcept
110 : {
111 0 : const auto d = subc(x, y);
112 0 : const auto s = d.value + mod;
113 0 : return (d.carry) ? s : d.value;
114 : }
115 :
116 : template class ModArith<uint256>;
117 : template class ModArith<uint384>;
118 : } // namespace evmmax
|
