Add static loop which is unrolled in compile-time

2 files changed, 176 insertions, 0 deletions

diff --git a/test/utils_test.cc b/test/utils_test.cc
index 782027e..8596104 100644
--- a/test/utils_test.cc
+++ b/test/utils_test.cc
@@ -34,5 +34,49 @@ TEST_CASE("Expi (positive)",) {
   CHECK_EPS(expi(10), 22026.4657948067165170, eps);
 }
 
+struct StaticLoopTest {
+  template <typename Iterator>
+  static void body(Index& result) {
+    result >>= 1;
+  }
+};
+
+TEST_CASE("Static loop (N = 1)",) {
+  Index result = 128;
+  StaticLoop<StaticLoopTest, MakeStaticLoopIterator<1>>(result);
+  CHECK(result == 64);
+}
+
+TEST_CASE("Static loop (N = 7)",) {
+  Index result = 128;
+  StaticLoop<StaticLoopTest, MakeStaticLoopIterator<7>>(result);
+  CHECK(result == 1);
+}
+
+struct StaticLoopMultiDimTest {
+  template <typename Iterator>
+  static void body(Index& result) {
+    result = result * 10 + Iterator::template I<0>();
+  }
+};
+
+TEST_CASE("Static loop with mult-dim iterator (Iterator<1, 1>)",) {
+  Index result = 0;
+  StaticLoop<StaticLoopMultiDimTest, MakeStaticLoopIterator<1, 1>>(result);
+  CHECK(result == 0);
+}
+
+TEST_CASE("Static loop with mult-dim iterator (Iterator<1, 5>)",) {
+  Index result = 0;
+  StaticLoop<StaticLoopMultiDimTest, MakeStaticLoopIterator<1, 5>>(result);
+  CHECK(result == 0);
+}
+
+TEST_CASE("Static loop with mult-dim iterator (Iterator<5, 2>)",) {
+  Index result = 0;
+  StaticLoop<StaticLoopMultiDimTest, MakeStaticLoopIterator<5, 2>>(result);
+  CHECK(result == 11223344);
+}
+
 }
 }
diff --git a/utils.h b/utils.h
index 2927693..abc87a4 100644
--- a/utils.h
+++ b/utils.h
@@ -69,4 +69,136 @@ constexpr double expi(int n) {
   return (n >= 0 ? expi_nonnegative(n) : 1.0 / expi_nonnegative(-n));
 }
 
+/*
+ * Multi-dimmension static loop iterator over range [0, 0, ...] - [Ns...] (exclusive)
+ * starting from IterationNumber-th iteration. Keep in mind that iterations are counted
+ * from 0.
+ * 
+ * For example, StaticLoopIterator<3, 5, 2> creates iterator:
+ *   [1, 1] -> [2, 0] -> ... -> [4, 0] -> [4, 1]
+ * because first 3 steps i.e.:
+ *   [0, 0] -> [0, 1] -> [1, 0]
+ * are skipped.
+ * 
+ * To extract I-th component of the iterator, use get<I>() function.
+ */
+template <Index IterationNumber, Index... Ns>
+struct StaticLoopIterator {
+private:
+  template <Index N, Index FirstDimmension, Index... RestDimmensions>
+  struct get_dimmension_s {
+    static constexpr Index value = get_dimmension_s<N - 1, RestDimmensions...>::value;
+  };
+
+  template <Index FirstDimmension, Index... RestDimmensions>
+  struct get_dimmension_s<0, FirstDimmension, RestDimmensions...> {
+    static constexpr Index value = FirstDimmension;
+  };
+
+  template <Index N, Index FirstDimmension, Index... RestDimmensions>
+  struct multiply_first_n_dimmensions_s {
+    static constexpr Index value = FirstDimmension * multiply_first_n_dimmensions_s<N - 1, RestDimmensions...>::value;
+  };
+
+  template <Index FirstDimmension, Index... RestDimmensions>
+  struct multiply_first_n_dimmensions_s<1, FirstDimmension, RestDimmensions...> {
+    static constexpr Index value = FirstDimmension;
+  };
+
+  template <Index N>
+  struct multiply_first_n_dimmensions : multiply_first_n_dimmensions_s<N, Ns...> {};
+
+public:
+  /*
+   * Total number of iteration in the given dimmensions.
+   */
+  static constexpr Index total_iterations = multiply_first_n_dimmensions<sizeof...(Ns)>::value;
+
+  /*
+   * Current iteration number
+   */
+  static constexpr Index iteration_number = IterationNumber;
+
+  /*
+   * Get I-th dimmension of the iterator.
+   */
+  template <Index Ith = 0>
+  static constexpr inline Index N() {
+    return get_dimmension_s<Ith, Ns...>::value;
+  }
+
+  /*
+   * Return I-th component of the iterator.
+   */
+  template <Index Ith = 0>
+  static constexpr inline Index I() {
+    return (iteration_number * multiply_first_n_dimmensions<Ith + 1>::value / total_iterations) % N<Ith>();
+  }
+
+  /*
+   * Next iterator
+   */
+  using next = StaticLoopIterator<iteration_number + 1, Ns...>;
+
+  /*
+   * Last iterator
+   */
+  using last = StaticLoopIterator<total_iterations - 1, Ns...>;
+};
+
+/*
+ * Create multi-dimmension static loop iterator over range [0, 0, ...] - [Ns...] (exclusive)
+ * 
+ * For example, MakeStaticLoopIterator<5, 2> creates iterator:
+ *   [0, 0] -> [0, 1] -> [1, 0] -> [1, 1] -> [2, 0] -> ... -> [4, 0] -> [4, 1]
+ */
+template <Index... Ns>
+using MakeStaticLoopIterator = StaticLoopIterator<0, Ns...>;
+
+/*
+ * Static loop over range defined by the give static loop iterator.
+ *
+ * To use it, you need to create a body structure containing static inline procedure
+ * 'body' with template parameter Iterator. If you need you can also
+ * add extra template parameters.
+ *
+ * Example:
+ *   struct Test {
+ *     template <typename Iterator, typename Number>
+ *     static inline void body(const char* text, Number number) {
+ *       std::cout << "[" << Iterator::template get<0>() << ", " << Iterator::template get<1>() << "] " << text << " " << number << std::endl;
+ *     }
+ *   };
+ *
+ * To run static loop, you just need to call StaticLoop<Body, Iterator>. It takes
+ * the same parameters as body procedure inside Body structure.
+ * 
+ * Example:
+ *   StaticLoop<Test, MakeStaticLoopIterator<5, 2>>("Test", 1);
+ *
+ * Output of the example:
+ *
+ * [0, 0] Test 1
+ * [0, 1] Test 1
+ * [1, 0] Test 1
+ * [1, 1] Test 1
+ * [2, 0] Test 1
+ * [2, 1] Test 1
+ * [3, 0] Test 1
+ * [3, 1] Test 1
+ * [4, 0] Test 1
+ * [4, 1] Test 1
+ *
+ */
+template <typename Body, typename StaticLoopIterator, typename std::enable_if<std::is_same<StaticLoopIterator, typename StaticLoopIterator::last>::value>::type* = nullptr, typename... Args>
+__attribute__((always_inline)) static inline void StaticLoop(Args&&... args) {
+  Body::template body<StaticLoopIterator>(std::forward<Args>(args)...);
+}
+
+template <typename Body, typename StaticLoopIterator, typename std::enable_if<!std::is_same<StaticLoopIterator, typename StaticLoopIterator::last>::value>::type* = nullptr, typename... Args>
+__attribute__((always_inline)) static inline void StaticLoop(Args&&... args) {
+  Body::template body<StaticLoopIterator>(std::forward<Args>(args)...);
+  StaticLoop<Body, typename StaticLoopIterator::next>(std::forward<Args>(args)...);
+}
+
 }