(No Ratings Yet)
Loading...

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:

parameter pack function/template parameter pack, that accepts zero or more function/template arguments
:: scope resolution operator helps to identify and specify the context to which an identifier refers (eg. namespace, class), for example it can be used to define a function outside a class
: class inheritance, preceding initialization list
return {}; return an object of the function’s return type initialized with an empty list-initializer
constexpr declares that it is possible to evaluate the value of the function or variable at compile time – such variables and functions can then be used where only compile time constant expressions are allowed

Full C++11 snippet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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
1
2
3
4
5
6
7
8
9
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
1
2
3
4
5
6
7
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
1
2
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 forementioned, 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’
1
2
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
1
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…>.

Your email is kept private. Required fields are marked *