1 #ifndef NFL_PERMUT_HPP 2 #define NFL_PERMUT_HPP 3 4 #define PERMUT_LIMIT_UNROLL 1024 5 6 #include <limits> 7 8 namespace nfl { 9 10 namespace details { 11 12 // meta-compilation of the bit-reversing permutation 13 template<size_t H, size_t degree, size_t R, size_t I> 14 struct r_loop { 15 static constexpr size_t value = r_loop<(H << 1), degree, (R << 1) | (I & 1), (I >> 1)>::value; 16 }; 17 template<size_t degree, size_t R, size_t I> 18 struct r_loop<degree, degree, R, I> { 19 static constexpr size_t value = R; 20 }; 21 template <size_t I, size_t J, size_t degree> 22 struct r_set { 23 template<class value_type> operator ()nfl::details::r_set24 void operator()(value_type *y, value_type const *x) { 25 r_set<2*I,2*J, degree>{}(y, x); 26 r_set<2*I + 1,2*J, degree>{}(y, x); 27 } 28 }; 29 template <size_t I, size_t degree> 30 struct r_set<I, degree, degree> { 31 template<class value_type> operator ()nfl::details::r_set32 void operator()(value_type *y, value_type const *x) { 33 constexpr size_t r = r_loop<1, degree, 0u, I>::value; 34 y[r] = x[I]; 35 } 36 }; 37 38 template <uint64_t N> 39 struct uint_value_t 40 { 41 using type = typename std::conditional< 42 N <= std::numeric_limits<uint8_t>::max(), 43 uint8_t, 44 typename std::conditional< 45 N <= std::numeric_limits<uint16_t>::max(), 46 uint16_t, 47 typename std::conditional< 48 N <= std::numeric_limits<uint32_t>::max(), 49 uint32_t, 50 uint64_t>::type 51 >::type 52 >::type; 53 }; 54 55 template <size_t degree> 56 struct permut_compute 57 { 58 using idx_type = typename uint_value_t<degree>::type; 59 idx_type data_[degree]; 60 permut_computenfl::details::permut_compute61 permut_compute() 62 { 63 for (idx_type i = 0; i < degree; ++i) { 64 idx_type ii = i; 65 idx_type r = 0; 66 67 for (idx_type h = 1; h < degree; h=h<<1) 68 { 69 r = (r << 1) | (ii & 1); 70 ii >>= 1; 71 } 72 73 data_[i] = r; 74 } 75 } 76 operator ()nfl::details::permut_compute77 inline idx_type operator()(size_t i) const { 78 assert(i < degree); 79 return data_[i]; 80 } 81 }; 82 83 template <size_t degree, bool unroll> 84 struct permut; 85 86 template <size_t degree> 87 struct permut<degree, true> 88 { 89 template <class V> computenfl::details::permut90 static inline void compute(V* y, V const* x) 91 { 92 r_set<0, 1, degree>{}(y, x); 93 } 94 }; 95 96 template <size_t degree> 97 struct permut<degree, false> 98 { 99 static permut_compute<degree> P; 100 101 template <class V> computenfl::details::permut102 static inline void compute(V* y, V const* x) 103 { 104 for (size_t i = 0; i < degree; ++i) { 105 y[i] = x[P(i)]; 106 } 107 } 108 }; 109 110 template <size_t degree> 111 permut_compute<degree> permut<degree,false>::P; 112 113 } // details 114 115 template <size_t degree> 116 struct permut: public details::permut<degree, degree <= PERMUT_LIMIT_UNROLL> 117 { }; 118 119 120 } // nfl 121 122 #endif 123