Compile-time cosine lookup table with C++
The following post will revolve around a C++ snippet taken from a book I bought recently — Building Embedded Systems by Changyi Gu. The snippet will generate a cosine lookup table of 2048 items — which could be used to avoid floating point math. Useful for cases where we are very time-constrained when running the program.
Author’s first version of building a lookup table contains manually constructing an array of pre-calculated items:
{ look_up_table_elem(0), look_up_table_elem(1), ..., look_up_table_elem(2047)}You could generate that with a script, but every time you would want to increase table size, you would have to re-generate it. With the following, we get rid of that.
An important thing to note here is that we are trying to build the table compile-time, which is why we don’t just use a loop and fill the table that way. Loops cannot be compile-time. The example uses template specialization and class inheritance to achieve the task.
Firstly, a few symbols/operators/keywords that might seem confusing:
Full C++11 snippet
#include <cmath>
#include <array>
template<typename T>
constexpr T look_up_table_elem (int i) {
return {};
}
template<>
constexpr uint16_t look_up_table_elem (int i) {
return round (cos (static_cast <long double>(i) / 2048 * 3.14159 / 4) * 32767);
}
template<typename T, int... N>
struct lookup_table_expand{};
template<typename T, int... N>
struct lookup_table_expand<T, 1, N...> {
static constexpr std::array<T, sizeof...(N) + 1> values = {{ look_up_table_elem<T>(0), N... }};
};
template<typename T, int L, int... N>
struct lookup_table_expand<T, L, N...>: lookup_table_expand<T, L-1, look_up_table_elem<T>(L-1), N...> {};
template<typename T, int... N>
constexpr std::array<T, sizeof...(N) + 1> lookup_table_expand<T, 1, N...>::values;
const std::array<uint16_t, 2048> lookup_table = lookup_table_expand<uint16_t, 2048>::values;Snippet deconstructed
Generating a single element value
template<typename T>
constexpr T look_up_table_elem (int i) {
return {};
}
template<>
constexpr uint16_t look_up_table_elem (int i) {
return round (cos (static_cast <long double>(i) / 2048 * 3.14159 / 4) * 32767);
}I would say the first part is pretty self-explanatory as it only defines a template which returns our final value for i.
Recursion limit class definition
template<typename T, int... N>
struct lookup_table_expand{};
template<typename T, int... N>
struct lookup_table_expand<T, 1, N...> {
static constexpr std::array<T, sizeof...(N) + 1> values = {{ look_up_table_elem<T>(0), N... }};
};Base lookup_table_expand<T, 1, N…> class, is inherited with its members by lookup_table_expand<T, L, N…> upon template expansion. Meaning, this is where the recursion will end, by using template specialization.
Declares static constexpr std:array member of struct lookup_table_expand named values.
Recursion with inherited class definition
template<typename T, int L, int... N>
struct lookup_table_expand<T, L, N...>: lookup_table_expand<T, L-1, look_up_table_elem<T>(L-1), N...> {};This is the very first template to be used when expanding the end-result lookup table definition: lookup_table_expand<uint16_t, 2048>, upon first occurrence N will be zero arguments.
Recursively called until arguments match:
<uint16_t,
lookup_table_expand<uint16_t,
1,
look_up_table_elem<uint16_t>(1),
look_up_table_elem<uint16_t>(2),
... ,
look_up_table_elem<uint16_t>(2047)>>When the arguments match the aforementioned, template lookup_table_expand<T, 1, N…> will be used instead.
Has no member called values, because it inherits lookup_table_expand<T, 1, N…>‘s member, when its parent is recursively expanded and template-specialized.
Defining struct member ‘values’
template<typename T, int... N>
constexpr std::array<T, sizeof...(N) + 1> lookup_table_expand<T, 1, N...>::values;Defines static constexpr std:array member of struct lookup_table_expand<T, 1, N…> called ‘values’ (see odr-used). The reason why it is of type lookup_table_expand with arguments T, 1, N…, is because that is the base class that contains the declaration for the member.
End-result lookup table declaration
const std::array<uint16_t, 2048> lookup_table = lookup_table_expand<uint16_t, 2048>::values;Final declaration of the lookup table with lookup_table_expand’s member named values. Member values is of type std::array, so is our lookup_table. Template expansion starts at lookup_table_expand<T, L, N…>.
Moral of the story
C++ is awesome, but can be really tricky sometimes.
