Using a lookup table at compile time

[mark]

What is a good way to use a lookup table at compile time? Using C++11 is
not an option (must work with GCC 4.3). This is for embedded usage with
tiny amounts of memory and every byte counts. Having increased code or
data size compared to hardcoding things is not an option.

E.g:

---------------------------------------------------
class A {
public:
void m();
private:
static const int table[5];
};

void A::m() {
int arr[table[3]]; // table[3] is not compile time const
}

const int A::table[] = {0, 1, 2, 3, 4};
---------------------------------------------------

[Rick C. Hodgin]

I was surprised nobody's replied by now. I'm not sure what the best
way to do it in C++ is, but if you know explicitly these constants at
compile-time, such that you're referencing table[3], then you could
use an enum like this:

class A {
public:
void m();

private:

enum { first = 0, one, two, three, four };
};

void A::m() {
int arr[A::three]; // A::three is a compile time const
}

-----
You could also define compile-time constants for the values 0, 1, 2,
3, and 4, and define constants which reference those constants using
a similar name, like...:

#define _const0 0
#define _const1 1
#define _const2 2
#define _const3 3
#define _const4 4

const int A::table[] = {_const0, _const1, _const2, _const3, _const4};

#define table0 _const0
#define table1 _const1
#define table2 _const2
#define table3 _const3
#define table4 _const4

...so that instead of using "table[3]" you'd use "table3" which would map
to the same constant value:

int arr[table3]; // Make sure table3's declared ahead of use

These are the solutions I would use if I had constraints. I am, however,
curious what the proper C++ solution is.

Best regards,
Rick C. Hodgin

[mark]

On 2016-08-23 18:51, Stefan Ram wrote:

> mark <ma...@invalid.invalid> writes:
>> const int A::table[] = {0, 1, 2, 3, 4};
>

> #include <iostream>
> #include <ostream>
>
> #define TABLE0 0
> #define TABLE1 1
> #define TABLE2 2
> #define TABLE3 3
> #define TABLE4 4
> #define TABLE(x) TABLE##x
>
> int main()
> { ::std::cout << TABLE( 0 )<< '\n';
> ::std::cout << TABLE( 1 )<< '\n';
> ::std::cout << TABLE( 2 )<< '\n';
> ::std::cout << TABLE( 3 )<< '\n';
> ::std::cout << TABLE( 4 )<< '\n'; }

Maybe that isnt't clear from the post, but it's supposed to be a lookup
table and also needs to work for dynamic lookups.

I.e.:

void A::m2(int i) {
return table[i] * 42;
}

needs to work.

[Rick C. Hodgin]

The second solution I provided would allow your option here to work.
It simply migrates the constant values from being specified in the
{ ... } definition into #define tokens, but it still creates table.

#define _const0 0
#define _const1 1
#define _const2 2
#define _const3 3
#define _const4 4

const int A::table[] = {_const0, _const1, _const2, _const3, _const4};

#define table0 _const0
#define table1 _const1
#define table2 _const2
#define table3 _const3
#define table4 _const4

void A::m() {
int arr[table3];

}

void A::m2(int i) {
return table[i] * 42;
}

Both would be valid.

[mark]

Thank's. I was hoping for something more elegant.

[Rick C. Hodgin]

Well, I'm sure someone else will be able to provide you with a more
elegant solution. I apologize if my offering offended you.

[Richard]

[Please do not mail me a copy of your followup]

First, let me say that you've posed a very specific question with a
generic example in the form of "how do I perform this task?" but you
haven't told us the actual goal the task is supposed to accomplish.

Eric Raymond calls this "describe the goal, not the step". Here
you've described the step and not the goal. If we knew the goal, we
could probably advise you more fully on the best way to achieve it.
<http://www.catb.org/esr/faqs/smart-questions.html#goal>

Let's proceed...

mark <ma...@invalid.invalid> spake the secret code
<nphric$gl3$1...@dont-email.me> thusly:

>What is a good way to use a lookup table at compile time?

An easier solution might be to simply generate source files at build
time that reflect whatever it is you're trying to do at compile time.

Compile-time evaluation occurs through one of two C++ mechanisms:
templates and constexpr. Since you are using an ancient gcc, you
can't use constexpr. That leaves templates. (I'm ignoring
preprocessor hacks, I'm sure someone else will post a disgusting
solution using macros.)

Templates can implement a table-lookup type mechanism through
a generic template and one specialization of the generic template for
each input to the lookup. The outputs are obtained through the
differences in the specializations.

>class A {
>public:
> void m();
>private:
> static const int table[5];
>};
>
>void A::m() {
> int arr[table[3]]; // table[3] is not compile time const
>}
>
>const int A::table[] = {0, 1, 2, 3, 4};

template <int Index>
struct table
{
static const int value;
};

template <>
struct table<0>
{
static const int value = 0;
};

template <>
struct table<1>
{
static const int value = 1;
};

template <>
struct table<2>
{
static const int value = 2;
};

template <>
struct table<3>
{
static const int value = 3;
};

template <>
struct table<4>
{
static const int value = 4;
};

class A
{
public:
void m();

};

void A::m()
{
int arr[table<3>::value];
for (int i = 0; i < sizeof(arr)/sizeof(int); ++i)
{
arr[i] = 2*i;
}
}

int main()
{
A a;
a.m();
}

So yeah, that works, but it's pretty noisy.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[mark]

On 2016-08-23 21:49, Rick C. Hodgin wrote:
>> > Thank's. I was hoping for something more elegant.
> Well, I'm sure someone else will be able to provide you with a more
> elegant solution. I apologize if my offering offended you.

This wasn't intended to be ironic or anything. Your second suggestion
may very well be what I will use.

Which doesn't mean I'm happy with it, what I really want is something like:

class A {
public:
void m();

int m2(int v);
int m3(int v);
private:
static constexpr int table[5] = { 4, 1, 7, 2, 1 };
static constexpr int i = table[2];
};

void A::m() {
int arr[table[3]];
}

int A::m2(int v) {
return table[v] * 42;
}

int A::m3(int v) {
switch(v) {
case table[2]:
return 42;
default:
return -1;
}
}

[mark]

On 2016-08-23 22:20, Stefan Ram wrote:
> Here is a new, more general version:
>
> #include <iostream>
> #include <ostream>
>
> #define F(i,j) (j),
> #define TAB F(0,0)F(1,1)F(2,2)F(3,3)F(4,4)
> int array[] ={ TAB };
> #undef F
>
> #define F(i,j) TAB##i=(j),
> enum table { TAB };
> #undef F
>
> #define TABLE(i) TAB##i
>
> int main( void )
> { int i; switch( 0 ){ case TABLE( 0 ): case TABLE( 1 ): case TABLE( 2 ): ; }
> ::std::cout << TABLE( 0 )<< '\n'; i = 0; ::std::cout << array[ i ]<< '\n';
> ::std::cout << TABLE( 1 )<< '\n'; i = 1; ::std::cout << array[ i ]<< '\n';
> ::std::cout << TABLE( 2 )<< '\n'; i = 2; ::std::cout << array[ i ]<< '\n'; }
>
> The programmer must choose himself to use »TABLE« for compile-time lookup
> and »array« for run-time lookup for each lookup case.

Wow, some neat macro (ab)use. I'm not sure other people will be
thrilled, if I use something like that.

[Öö Tiib]

That you can't use with gcc 4.3, it did not have 'constexpr'.
It had variadic templates so you can perhaps make slightly
more convenient template than Richard suggests.

[mark]

On 2016-08-24 00:15, Öö Tiib wrote:
>> what I really want is something like:
>> >
>> > class A {
>> > public:
>> > void m();
>> > int m2(int v);
>> > int m3(int v);
>> > private:
>> > static constexpr int table[5] = { 4, 1, 7, 2, 1 };
>> > static constexpr int i = table[2];
>> > };
>> >
>> > void A::m() {
>> > int arr[table[3]];
>> > }
>> >
>> > int A::m2(int v) {
>> > return table[v] * 42;
>> > }
>> >
>> > int A::m3(int v) {
>> > switch(v) {
>> > case table[2]:
>> > return 42;
>> > default:
>> > return -1;
>> > }
>> > }
> That you can't use with gcc 4.3, it did not have 'constexpr'.

I know, that's exactly my problem. This is just an illustration of the
kind of simplicity and non-verbosity I would like to get.

> It had variadic templates so you can perhaps make slightly
> more convenient template than Richard suggests.

I played around a bit with variadic templates. Getting to a dynamic
array is easy, but getting compile time constants is not. Unfortunately,
there isn't even a C++ standard library, so no std::tuple to get
somewhat sane access to parameter pack elements. I don't see an
implementation with reasonable complexity and without too much template
black magic.

[David Brown]

On 23/08/16 23:06, mark wrote:
> On 2016-08-23 21:49, Rick C. Hodgin wrote:
>>> > Thank's. I was hoping for something more elegant.
>> Well, I'm sure someone else will be able to provide you with a more
>> elegant solution. I apologize if my offering offended you.
>
> This wasn't intended to be ironic or anything. Your second suggestion
> may very well be what I will use.
>
> Which doesn't mean I'm happy with it, what I really want is something like:
>
> class A {
> public:
> void m();
> int m2(int v);
> int m3(int v);
> private:
> static constexpr int table[5] = { 4, 1, 7, 2, 1 };
> static constexpr int i = table[2];
> };

Pre C++11, these have to be "const" and defined outside the class. If
the class is defined in a header and used in other source that does not
have compile-time access to the table values, you may lose optimisation
opportunities.

>
> void A::m() {
> int arr[table[3]];
> }

Since "table[3]" is no longer a constant expression, this is not valid
in standard C++ (until C++14, but that doesn't help much!). But it /is/
valid in gcc, which allows variable length arrays as an extension.
Technically, since table[3] is not a constant expression, this is a VLA
- even though the compiler knows exactly what size it will be, and can
generate code using that fact. (gcc 4.3 may not be smart enough to do
so, however.)

There will be (or should be) no difference in the generated code between
a VLA with a size known to the compiler, and a "normal" array whose size
is a constant expression. However, you have some restrictions - you
can't make it "static", or file scope, for example.

>
> int A::m2(int v) {
> return table[v] * 42;
> }

That should be fine with table being a plain "const". The compiler
should be able to optimise this fully if it knows the value of "v" for a
particular call.

>
> int A::m3(int v) {
> switch(v) {
> case table[2]:
> return 42;
> default:
> return -1;
> }
> }

That will not work without constexpr table - even with gcc extensions.

[Tim Rentsch]

Something that acts like a lookup table can be provided pretty
straightforwardly using a function-like macro. Here is a simple
sketch (I chose different numbers for the example values):

#define table(k) ( \
(k) == 0 ? 27 : \
(k) == 1 ? 28 : \
(k) == 2 ? 29 : \
(k) == 3 ? 35 : \
(k) == 4 ? 47 : \
-1 \
)

(Obviously we might want to choose a better name in actual code.)

Calls to the table() macro are usable as constant expressions
when the "index" is a constant expression:

enum { SOMETHING = 3 };
char foo[ table(SOMETHING) ];

char bas[ table((int)2.0) ];

char bar[ table(12-11) ];

const int fantastic = 4;
char foobas[ table(fantastic) ];

Calls to table() with a constant argument also can be used as
'case' labels, if that is wanted.

If dynamic lookup is needed in addition to compile-time lookup,
this can be done by providing an inline function that accesses an
array:

extern const int table_values_array[];

static inline int
(table)( int index ){
return table_values_array[ index ];
}

Any "indexing" where the index is a dynamic value (eg, an auto
variable) rather than a compile-time constant may use the 'table'
function rather than the macro (this is done in the usual way by
putting parentheses around the function name):

int
dumb_example( int foo, int bas ){
return (table)(foo-bas);
}

Even low levels of optimization (eg, -O1 in gcc) should turn this
function call into just an array access.

The initializers for elements of table_values_array[] may be
written using repeated calls to the table() macro, to ensure
synchronization:

const int table_values_array[] = {
table(0),
table(1),
table(2),
table(3),
table(4),
};

That's everything. Not very high-powered, and some people may
blanch at using the preprocessor, but it works and seems easy
enough to understand.

The method shown above is simple, but it does have a problem of
sorts - the number of calls to table() in the array initializer
need to be kept in sync with the macro definition "by hand", as
it were. There are various techniques for avoiding this problem.
Here is one method, showing first how to define the values and
the table() macro:

#define TABLE_ENTRIES_FOREACH(k,WHAT) \
WHAT(k,0,27) \
WHAT(k,1,28) \
WHAT(k,2,29) \
WHAT(k,3,35) \
WHAT(k,4,47) \
/* end of TABLE_ENTRIES_FOREACH */

#define table(k) ( TABLE_ENTRIES_FOREACH( k, TABLE_VALUE_CHOOSE ) -1 )
#define TABLE_VALUE_CHOOSE( k, key, value ) (k) == (key) ? (value) :

And now the definition of the values array, with initializers:

const int table_values_array[] = {
#define TABLE_ARRAY_INITIALIZER( _1, _2, value ) (value),
TABLE_ENTRIES_FOREACH( 0, TABLE_ARRAY_INITIALIZER )
#undef TABLE_ARRAY_INITIALIZER
};

Obviously this scheme is more complicated in terms of how much
preprocessor machinery is used. Its compensating advantage is
that now all the values and indices are in only one place.
Different circumstances may favor one or the other, depending
on a variety of forces.