Pull to refresh

Метапрограммирование в C++

Reading time 5 min
Views 38K
Метапрограммирование — это «программирование программ», то есть написание некой промежуточной программы, результатом которой будет некая часть другой программы. Самый простой пример метапрограммирования — это шаблоны C++. Вместо написания десяти одинаковых функций для разных типов, мы пишем шаблон, и компилятор сам соберет нам эти десять функций.

Другой неявный пример метапрограммирования — это precomputing, вычисления, которые проводятся на этапе компиляции. Если в коде вы напишете
int i = 2+2*2;
компилятор (вернее, прекомпилятор), вычислит это значение и передаст компилятору уже готовое
int i = 6;
Прекомпилятор пытается вычислить все возможное на этапе компиляции, чтобы разгрузить ран-тайм, в том числе и раскрыть шаблоны. Именно это его свойство позволяет писать очень интересные precomputing штучки, которые будут вычислены на этапе компиляции.

Конкретный пример — это реализация CRC32. Не вдаваясь в детали, приведу ее алгоритм:

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


Для этого алгоритма нужна таблица из 256 чисел. Логично было бы не вычислять ее при каждом вызове функции, да и вообще, так как таблица определена заранее, записать ее в виде
long crc_table[256] = {"0x12345678", ... }
Но это как-то неслишком круто. Посему было решено вынести ее вычисление в compile-time средствами метапрограммирования.

Рассмотрим функцию вычисления таблицы поближе. Она состоит из четырех составляющих:
  1. вычисления значения полинома: crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
  2. цикла, повторяющего вычисления «рекурсивно» 8 раз, то есть применяющего первое выражение последовательно для одного и того же алгортима: for (int j = 0; j < 8; j++)
  3. сохранения вычисленного значения в таблице: crc_table[i] = crc
  4. и цикла для всей таблицы: for (int i = 0; i < 256; i++)


Будем создавать наше вычисление по шагам.
Первый шаг — создание шаблона, который по данному t вычислит значение полинома. Это неслишком сложно:
template <unsigned long t> struct Polynome  { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1   }; };


Данный шаблон принимает на вход unsigned long параметр и превращает его в структуру с определенной внутри константой value.

Следющий шаг — выполнение этого кода в цикле. Для этого определим такой шаблон:

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

Здесь начинается магия.

Мы определили шаблон, который получает два параметра — t, собственно вычисляемое значение, и i — счетчик. Этот шаблон создает структуру с единственной константой value внутри, которая вычисляется… через значение этого же шаблона! Мы получаем рекурсию — шаблон определеятся через самого себя. Для завершения рекурсии, мы воспользуемся частичной специализацией шаблона:

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


И, наконец, само вычисление — вызов шаблона For с определенным количество итераций:

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


Что же происходит в этих строчках.
Прекомпилятор пытается вычислить все значения констант. Если выражение задано через другие константы — это выражение также является константным и будет вычислено на этапе компиляции. С другой стороны, компилятору от прекомпилятора необходимы полностью специализированные шаблоны, поэтому прекомпилятор будет последовательно раскрывать все шаблоны, попутно вычисляя константы, определенные в них.

Все это очень напоминает вычисление рекурсивных функций в функциональном программировании:

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

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

hash x = for x 7

(Не уверен в точности написания, но суть, думаю, понята)

Третий и четвертый шаги — создать таблицу вычисленных значений. Опять-таки воспользуемся шаблоном со счетчиком:

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
.


Здесь происходит переход от препроцессора собственно к коду. Первый шаблон создает рекурсивную иеррахию наследников структур Table, каждый из которых добавляет занчение в таблицу values, соотвествующую своему номеру. Второй шаблон определяет конец рекурсии, собственно саму таблицу values и идексатор для более простого использования этой таблицы.

Последний шаг — это, собственно, объявление самой таблицы

typedef Table<0,255> CRC_TABLE;

Теперь у нас есть структура, которая ведет себя в точности как необходимая нам таблица. Так как все вычисления известны во время компиляции, прекомпилятор раскроет все шаблоны и в конце концов соберет нужную нам таблицу.

Вот так это все выглядит в собранном виде

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
.


Для заинтересовавшихся — советую почитать Андрей Александреску «Современное проектирование на С++» ISBN: 5-8459-0351-3
Tags:
Hubs:
+59
Comments 55
Comments Comments 55

Articles