Generating BitCount LUT at compile time

Question

Let's say that I need to create a LUT containing precomputed bit count values (count of 1 bits in a number) for 0...255 values:

int CB_LUT[256] = {0, 1, 1, 2, ... 7, 8};

If I don't want to use hard-coded values, I can use nice template solution How to count the number of set bits in a 32-bit integer?

template <int BITS>
int CountBits(int val) 
{
    return (val & 0x1) + CountBits<BITS-1>(val >> 1);
}

template<>
int CountBits<1>(int val) 
{
    return val & 0x1;
}

int CB_LUT[256] = {CountBits<8>(0), CountBits<8>(1) ... CountBits<8>(255)};

This array is computed completely at compile time. Is there any way to avoid a long list, and generate such array using some kind of templates or even macros (sorry!), something like:

Generate(CB_LUT, 0, 255);  // array declaration
...
cout << CB_LUT[255];       // should print 8

Notes. This question is not about counting 1 bits in an number, it is used just as example. I want to generate such array completely in the code, without using external code generators. Array must be generated at compile time.

Edit. To overcome compiler limits, I found the following solution, based on Bartek Banachewicz` code:

#define MACRO(z,n,text) CountBits<8>(n)
int CB_LUT[] = {
    BOOST_PP_ENUM(128, MACRO, _)
};
#undef MACRO

#define MACRO(z,n,text) CountBits<8>(n+128)
int CB_LUT2[] = {
    BOOST_PP_ENUM(128, MACRO, _)
};
#undef MACRO

for(int i = 0; i < 256; ++i)   // use only CB_LUT
{
    cout << CB_LUT[i] << endl;
}

I know that this is possibly UB...

Why would you not want a simple lookup table with hardcoded values? What is the problem with that? — orlp, Jul 24 '13 at 10:35
if you don't like Preprocessor magic, you can try variadic template magic: http://stackoverflow.com/q/2978259/819272 — TemplateRex, Jul 24 '13 at 11:32

score 5 · Accepted Answer · edited Jun 20 '20 at 09:12

5

It would be fairly easy with macros using (recently re-discovered by me for my code) Boost.Preprocessor - I am not sure if it falls under "without using external code generators".

`PP_ENUM` version

Thanks to @TemplateRex for BOOST_PP_ENUM, as I said, I am not very experienced at PP yet :)

#include <boost/preprocessor/repetition/enum.hpp>

// with ENUM we don't need a comma at the end
#define MACRO(z,n,text) CountBits<8>(n)
int CB_LUT[256] = {
    BOOST_PP_ENUM(256, MACRO, _)
};
#undef MACRO

The main difference with PP_ENUM is that it automatically adds the comma after each element and strips the last one.

`PP_REPEAT` version

#include <boost/preprocessor/repetition/repeat.hpp>
 
#define MACRO(z,n,data) CountBits<8>(n),
int CB_LUT[256] = {    
    BOOST_PP_REPEAT(256, MACRO, _)
};
#undef MACRO

Remarks

It's actually very straightforward and easy to use, though it's up to you to decide if you will accept macros. I've personally struggled a lot with Boost.MPL and template techniques, to find PP solutions easy to read, short and powerful, especially for enumerations like those. Additional important advantage of PP over TMP is the compilation time.

As for the comma at the end, all reasonable compilers should support it, but in case yours doesn't, simply change the number of repetitions to 255 and add last case by hand.

You might also want to rename MACRO to something meaningful to avoid possible redefinitions.

edited Jun 20 '20 at 09:12

Community

1
1

answered Jul 24 '13 at 11:05

Bartek Banachewicz

38,596
7
91
135

about the comma at the end, [it is legal according to the Standard](http://stackoverflow.com/q/7043372/819272), so it would be quite *unreasonable* for any compiler not to accept it ;-) – TemplateRex Jul 24 '13 at 11:35
@TemplateRex I know it is legal, but then again, there are more non-conformant compilers than conformant ones out there, sadly. – Bartek Banachewicz Jul 24 '13 at 11:37
Meanwhile I get `fatal error C1009: compiler limit : macros nested too deeply`. It works up to 230 size approximately. According to Microsoft, `The compiler has a limit of 256 levels of nested macros`. – Alex F Jul 24 '13 at 11:50
@AlexFarber more like `BOOST_PP_REPEAT_FROM_TO` – Bartek Banachewicz Jul 24 '13 at 12:07
From some reason, using BOOST_PP_REPEAT_FROM_TO twice to generate sub-arrays gives the same macros nesting error. Anyway, I accept this answer because it provides the way within compiler limits. Thanks. – Alex F Jul 24 '13 at 12:38
The question is edited, I found the way based on your code (though this is possibly hack). Thanks. – Alex F Jul 24 '13 at 12:50

score 2 · Answer 2 · answered Jul 24 '13 at 11:29

I like to do it like this:

#define MYLIB_PP_COUNT_BITS(z, i, data) \
        CountBits< 8 >(i)

int CB_LUT[] = {
        BOOST_PP_ENUM(256, MYLIB_PP_COUNT_BITS, ~)
};

#undef MYLIB_PP_COUNT_BITS

The difference with BOOST_PP_REPEAT is that BOOST_PP_ENUM generates a comma-separated sequence of values, so no need to worry about comma's and last-case behavior.
Furthermore, it is recommended to make your macros really loud and obnoixous by using a NAMESPACE_PP_FUNCTION naming scheme.
a small configuration thing is to omit the [256] in favor of [] in the array size so that you can more easily modify it later.
Finally, I would recommend making your CountBit function template constexpr so that you also can initialize const arrays.

Thanks, it looks similar to Bartek Banachewicz` solution posted before. If you can elaborate more about variadic templates solution, mentioned in your comment, it would be nice... — Alex F, Jul 24 '13 at 11:52
@AlexFarber I haven't tried that solution, but the answer by Georg Fritzsche can be pasted into [an online compiler](http://coliru.stacked-crooked.com/view?id=e48d855e1f73a74865eb95a4771970af-ce6b7b81d29c30e32c78aebe6e642254) — TemplateRex, Jul 24 '13 at 12:05

Generating BitCount LUT at compile time

2 Answers2

PP_ENUM version

PP_REPEAT version

Remarks

`PP_ENUM` version

`PP_REPEAT` version