Cosine lookup table with c++

Question

Here's a snippet that should generate a cosine lookup table of 2048 elements, taken from the book Building Embedded Systems by Changyi Gu:

#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;

Note: Written for C++11.

I come from a primarily Java world and I've got an okay grasp of the basics of C++. Since it's never really explained in the book, I am really confused as to how does this snippet achieve the task, and how does it achieve the following (also taken out of the book):

Template specialization and class inheritance will help us get rid of the restriction that constexpr function can only have return state as its function body, which is why the lookup table has to be manually populated when the table size increases.

Any help would be greatly appreciated. I understand the part with constexpr template which would generate the actual value, but I am really unsure what the struct is doing and how the final array is constructed.

Answer 1

For first let's take a look into the following line:

const std::array<uint16_t, 2048> lookup_table =
        lookup_table_expand<uint16_t, 2048>::values;

There the lookup_table will be copy-constructed from values array held inside the lookup_table_expand<uint16_t, 2048> structure. This is simple, now let's see what happens when template instantiation being done.

We have a primary template with empty body (where forward declaration would be enough, we won't use it in this form):

template<typename T, int... N>
struct lookup_table_expand {
};

The lookup_table_expand<uint16_t, 2048> will match the following partial specialization of primary template:

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...> {
};

Because the inheritance the template above will be recursively instantiated with growing template parameter list until the current template won't match to the following partial specialization of primary template:

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...
    }};
};

The match to the template above will be happen when L becomes 1 in the recursion. At this point the template parameter list (N...) will contain the invocation results of the following function with values from 1 to 2047:

constexpr uint16_t look_up_table_elem(int i) {
    return round(cos(static_cast<long double>(i) / 2048 * 3.14159 / 4) * 32767);
}

This is where the only member of lookup_table_expand template (values) will be initialized with the values of template parameter list.

Note that values is a static constexpr data member which may be initialized in the class/struct declaration, therefore the following line not even necessary:

template<typename T, int... N>
constexpr std::array<T, sizeof...(N) + 1> lookup_table_expand<T, 1, N...>::values;

The values array will be inherited by lookup_table_expand<uint16_t, 2048>, so in the end you can access it from that structure.