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          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            0 :         t -= mod;
      84              : 
      85          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            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