Metaprogramming in C ++

Metaprogramming is “programming of programs”, that is, writing some intermediate program, the result of which will be some part of another program. The simplest example of metaprogramming is C ++ templates. Instead of writing ten identical functions for different types, we write a template, and the compiler itself will collect these ten functions for us.

Another implicit example of metaprogramming is precomputing, calculations that are performed at the compilation stage. If in the code you write
int i = 2+2*2;
the compiler (or rather, the precompiler) will calculate this value and pass the ready to the compiler
int i = 6;
The precompiler tries to compute everything possible at the compilation stage in order to unload the runtime, including uncover patterns. It is this property that allows you to write very interesting precomputing things that will be calculated at the compilation stage.

A specific example is the implementation of CRC32. Without going into details, I will give her algorithm:

unsigned long Crc32( unsigned char *buf, unsigned long len)
{
unsigned long crc_table[256];
unsigned long crc;

for ( int i = 0; i < 256; i++)
{
crc = i;
for ( int j = 0; j < 8; j++)
crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;

crc_table[i] = crc;
}

crc = 0xFFFFFFFFUL;

while (len--)
crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);

return crc ^ 0xFFFFFFFFUL;
};
* This source code was highlighted with Source Code Highlighter .

This algorithm requires a table of 256 numbers. It would be logical not to calculate it with each function call, and indeed, since the table is defined in advance, write it in the form
long crc_table[256] = {"0x12345678", ... }
But this is somehow quite cool. Therefore, it was decided to make its calculation in compile-time by means of metaprogramming.
')
Consider the function of calculating the table closer. It consists of four components:

1. calculating the value of a polynomial: crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1; crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
2. a cycle repeating the calculations “recursively” 8 times, that is, applying the first expression sequentially for the same algorithm: for ( int j = 0; j < 8; j++)
3. save the calculated value in the table: crc_table[i] = crc
4. and cycle for the entire table: for ( int i = 0; i < 256; i++)

We will create our calculation in steps.
The first step is to create a template that, using this t, will calculate the value of the polynomial. This is not too difficult:
template < unsigned long t> struct Polynome { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1 }; };


This template takes an unsigned long parameter as an input and turns it into a structure with a value defined inside by a constant.

The next step is to execute this code in a loop. To do this, we define the following pattern:

template < unsigned long t, int i> struct For { static const unsigned long value = For<Polynome<t>::value, i-1 >::value; };

This is where the magic begins.

We defined a pattern that takes two parameters - t, the actual calculated value, and i - a counter. This template creates a structure with a single constant value inside, which is calculated ... through the value of the same template! We get recursion - the pattern is defined by itself. To complete the recursion, we will use a partial template specialization:

template < unsigned long t> struct For<t,0> { static const unsigned long value = Polynome<t>::value; };


And finally, the calculation itself is a call to the For template with a certain number of iterations:

template < unsigned long t> struct Hash { static const unsigned long value = For<t,7>::value; };


What happens in these lines.
The precompiler tries to calculate all constant values. If the expression is specified via other constants, this expression is also constant and will be calculated at the compilation stage. On the other hand, the compiler from the precompiler requires fully specialized templates, so the precompiler will consistently disclose all templates, simultaneously computing the constants defined in them.

All this is very similar to the calculation of recursive functions in functional programming:

polynom x = x & 1 ? (x >> 1) ^ 0xEDB88320UL : x >> 1

for xt = polynom(fx t-1)
for x 0 = polynom(x)

hash x = for x 7

(Not sure of the accuracy of the writing, but the essence, I think, is understood)

The third and fourth steps are to create a table of calculated values. Again, use the template with the counter:

template < int r, int t> struct Table : Table<r+1, t-1>
{
Table() { values[t]=Hash<t>::value; }
};

template < int r> struct Table<r,0>
{
unsigned long values[r+1];
Table() { values[0]=Hash<0>:: value ; }
unsigned long operator []( int i) { return values[i];}
}; * This source code was highlighted with Source Code Highlighter .

Here is the transition from the preprocessor itself to the code. The first template creates a recursive hierarchy for the heirs of the Table structures, each of which adds a value to the values ​​table, corresponding to its number. The second pattern defines the end of the recursion, the actual values ​​table itself and the indexer for easier use of this table.

The last step is, in fact, the declaration of the table itself.

typedef Table<0,255> CRC_TABLE;

Now we have a structure that behaves exactly as the table we need. Since all calculations are known at compile time, the precompiler will open all the templates and eventually collect the table we need.

That's how it all looks assembled.

template < unsigned long t> struct Polynome { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1; };
template < unsigned long t, int i> struct For { static const unsigned long value = For<Polynome<t>::value,i-1 >::value; };
template < unsigned long t> struct For<t,0> { static const unsigned long value = Polynome<t>::value; };
template < unsigned long t> struct Hash { static const unsigned long value = For<t,7>::value; };

template < int r, int t> struct Table : Table<r+1, t-1>
{
Table() { values[t]=Hash<t>::value; }
};
template < int r> struct Table<r,0>
{
int values[r+1];
Table() { values[0]=Hash<0>::value; }
int operator []( int i) { return values[i];}
};

typedef Table<0,255> CRC_TABLE;

class Crc32Hasher
{
CRC_TABLE crc_table;
public :
unsigned long GetHashCode( const void * pObj, size_t length){
const char * buf = ( const char *)pObj;
unsigned long crc32=0xffffffff;
for (size_t i=0; i<length; i++)
crc32=crc_table[(crc32^(*buf++))&0xff]^(crc32>>8);
crc32=crc32^0xffffffff;
return crc32;
}
}; * This source code was highlighted with Source Code Highlighter .

For those interested - I advise you to read Andrew Alexandrescu "Modern design in C ++" ISBN: 5-8459-0351-3