1  /**********************************************************************
 2   * Copyright (c) 2018 Pieter Wuille, Greg Maxwell, Gleb Naumenko      *
 3   * Distributed under the MIT software license, see the accompanying   *
 4   * file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
 5   **********************************************************************/
 6  
 7  #ifndef _MINISKETCH_FIELDS_GENERIC_COMMON_IMPL_H_
 8  #define _MINISKETCH_FIELDS_GENERIC_COMMON_IMPL_H_ 1
 9  
10  #include <stdint.h>
11  
12  #include "../int_utils.h"
13  #include "../lintrans.h"
14  
15  namespace {
16  
17  /** Generic implementation for fields whose elements can be represented by an integer type. */
18  template<typename I, int B, uint32_t MOD, typename F, typename T, const F* SQR, const F* QRT> class Field
19  {
20      typedef BitsInt<I, B> O;
21      typedef LFSR<O, MOD> L;
22  
23  public:
24      typedef I Elem;
25      constexpr int Bits() const { return B; }
26  
27      constexpr inline Elem Mul2(Elem val) const { return L::Call(val); }
28  
29      class Multiplier
30      {
31          T table;
32      public:
33          explicit Multiplier(const Field&, Elem a) { table.template Build<L::Call>(a); }
34          constexpr inline Elem operator()(Elem a) const { return table.template Map<O>(a); }
35      };
36  
37      Elem Mul(Elem a, Elem b) const { return GFMul<I, B, L, O>(a, b); }
38  
39      /** Compute the square of a. */
40      inline constexpr Elem Sqr(Elem a) const { return SQR->template Map<O>(a); }
41  
42      /** Compute x such that x^2 + x = a (undefined result if no solution exists). */
43      inline constexpr Elem Qrt(Elem a) const { return QRT->template Map<O>(a); }
44  
45      /** Compute the inverse of x1. */
46      Elem Inv(Elem a) const { return InvExtGCD<I, O, B, MOD>(a); }
47  
48      /** Generate a random field element. */
49      Elem FromSeed(uint64_t seed) const {
50          uint64_t k0 = 0x496e744669656c64ull; // "IntField"
51          uint64_t k1 = seed;
52          uint64_t count = ((uint64_t)B) << 32;
53          Elem ret;
54          do {
55              ret = O::Mask(I(SipHash(k0, k1, count++)));
56          } while(ret == 0);
57          return ret;
58      }
59  
60      Elem Deserialize(BitReader& in) const { return in.template Read<B, I>(); }
61  
62      void Serialize(BitWriter& out, Elem val) const { out.template Write<B, I>(val); }
63  
64      constexpr Elem FromUint64(uint64_t x) const { return O::Mask(I(x)); }
65      constexpr uint64_t ToUint64(Elem val) const { return uint64_t(val); }
66  };
67  
68  }
69  
70  #endif