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