1  #include "share.h"
 2  
 3  // returns a * (x+1) in the Galois field
 4  // (since (x+1) is a primitive root)
 5  static constexpr std::uint8_t tpl(std::uint8_t a) {
 6      return a ^ (a<<1) // a * (x+1)
 7          ^ ((a & (1<<7)) != 0
 8             ? // would overflow (have an x^8 term); reduce by the AES polynomial,
 9               // x^8 + x^4 + x^3 + x + 1
10               0b00011011u
11             : 0
12            );
13  }
14  
15  // constexpr functions to compute exp/log
16  // these are not intended to be fast, but they must be constexpr to populate a
17  // table at compile time
18  static constexpr std::uint8_t gexp(unsigned k) {
19      return k > 0 ? tpl(gexp(k-1)) : 1;
20  }
21  static constexpr std::uint8_t glog(unsigned k, unsigned i = 0, unsigned v = 1) {
22      return k == v ? i : glog(k, i+1, tpl(v));
23  }
24  
25  // insane hack (courtesy of Xeo on stackoverflow): gen_seq<N> expands to a
26  // struct that derives from seq<0, 1, ..., N-1>
27  template<unsigned... I> struct seq{};
28  template<unsigned N, unsigned... I>
29  struct gen_seq : gen_seq<N-1, N-1, I...>{};
30  template<unsigned... I>
31  struct gen_seq<0, I...> : seq<I...>{};
32  
33  // produce the actual tables in array form...
34  template<unsigned... I>
35  constexpr std::array<Galois, 255> exptbl(seq<I...>) {
36      return { { Galois(gexp(I))... } };
37  }
38  template<unsigned... I>
39  constexpr std::array<std::uint8_t, 256> logtbl(seq<I...>) {
40      // manually populate entry zero, for two reasons:
41      // - it makes glog simpler
42      // - it avoids clang++'s default template instantiation depth limit of 256
43      return { { 0, glog(I+1)... } };
44  }
45  
46  // and initialize the static variables
47  const std::array<Galois, 255> Galois::exptable = exptbl(gen_seq<255>{});
48  const std::array<std::uint8_t, 256> Galois::logtable = logtbl(gen_seq<255>{});
49  
50  // by populating everything at compile-time, we avoid a static initialization
51  // step and any possible associated static initialization "races"