A implementação de referência do CRC32 calcula uma tabela de pesquisa em tempo de execução:

/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];

/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;

/* Make the table for a fast CRC. */
void make_crc_table(void)
{
    unsigned long c;

    int n, k;
    for (n = 0; n < 256; n++) {
        c = (unsigned long) n;
        for (k = 0; k < 8; k++) {
            if (c & 1) {
                c = 0xedb88320L ^ (c >> 1);
            } else {
                c = c >> 1;
            }
        }
        crc_table[n] = c;
    }
    crc_table_computed = 1;
}

Você pode calcular a tabela em tempo de compilação, eliminando a função e o sinalizador de status?

Aqui está uma solução C simples:

crc32table.c

#if __COUNTER__ == 0

    /* Initial setup */
    #define STEP(c) ((c)>>1 ^ ((c)&1 ? 0xedb88320L : 0))
    #define CRC(n) STEP(STEP(STEP(STEP(STEP(STEP(STEP(STEP((unsigned long)(n)))))))))
    #define CRC4(n) CRC(n), CRC(n+1), CRC(n+2), CRC(n+3)

    /* Open up crc_table; subsequent iterations will fill its members. */
    const unsigned long crc_table[256] = {

    /* Include recursively for next iteration. */
    #include "crc32table.c"

#elif __COUNTER__ < 256 * 3 / 4

    /* Fill the next four CRC entries. */
    CRC4((__COUNTER__ - 3) / 3 * 4),

    /* Include recursively for next iteration. */
    #include "crc32table.c"

#else

    /* Close crc_table. */
    };

#endif

Ele se baseia na __COUNTER__macro fora do padrão , bem como em uma semântica de avaliação onde __COUNTER__é avaliada antes de ser passada como argumento para uma macro.

Observe que, como STEPavalia seu argumento duas vezes e CRCusa oito invocações aninhadas, há uma pequena explosão combinatória no tamanho do código:

$ cpp crc32table.c | wc -c
4563276

Testei isso no GCC 4.6.0 e no Clang 2.8 no Linux de 32 bits e ambos produzem a tabela correta.

O loop principal

for (k = 0; k < 8; k++) {
    if (c & 1) {
        c = 0xedb88320L ^ (c >> 1);
    } else {
        c = c >> 1;
    }
}

pode ser convertido em uma meta-função:

template <unsigned c, int k = 8>
struct f : f<((c & 1) ? 0xedb88320 : 0) ^ (c >> 1), k - 1> {};

template <unsigned c>
struct f<c, 0>
{
    enum { value = c };
};

Em seguida, 256 chamadas para essa meta-função (para o inicializador de matriz) são geradas pelo pré-processador:

#define A(x) B(x) B(x + 128)
#define B(x) C(x) C(x +  64)
#define C(x) D(x) D(x +  32)
#define D(x) E(x) E(x +  16)
#define E(x) F(x) F(x +   8)
#define F(x) G(x) G(x +   4)
#define G(x) H(x) H(x +   2)
#define H(x) I(x) I(x +   1)
#define I(x) f<x>::value ,

unsigned crc_table[] = { A(0) };

Se você possui o Boost instalado, gerar um inicializador de matriz é um pouco mais simples:

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

#define F(Z, N, _) f<N>::value

unsigned crc_table[] = { BOOST_PP_ENUM(256, F, _) };

Por fim, o seguinte driver de teste simplesmente imprime todos os elementos da matriz no console:

#include <cstdio>

int main()
{
    for (int i = 0; i < 256; ++i)
    {
        printf("%08x  ", crc_table[i]);
    }
}

Uma solução C ++ 0x

template<unsigned long C, int K = 0>
struct computek {
  static unsigned long const value = 
    computek<(C & 1) ? (0xedb88320L ^ (C >> 1)) : (C >> 1), K+1>::value;
};

template<unsigned long C>
struct computek<C, 8> {
  static unsigned long const value = C;
};

template<int N = 0, unsigned long ...D>
struct compute : compute<N+1, D..., computek<N>::value> 
{ };

template<unsigned long ...D>
struct compute<256, D...> {
  static unsigned long const crc_table[sizeof...(D)];
};

template<unsigned long...D>
unsigned long const compute<256, D...>::crc_table[sizeof...(D)] = { 
  D...
};

/* print it */
#include <iostream>

int main() {
  for(int i = 0; i < 256; i++)
    std::cout << compute<>::crc_table[i] << std::endl;
}

Trabalhos em GCC (4.6.1) e Clang (tronco 134121).

C ++ 0x com constexpr. Trabalhos em GCC4.6.1

constexpr unsigned long computek(unsigned long c, int k = 0) {
  return k < 8 ? computek((c & 1) ? (0xedb88320L ^ (c >> 1)) : (c >> 1), k+1) : c;
}

struct table {
  unsigned long data[256];
};

template<bool> struct sfinae { typedef table type; };
template<> struct sfinae<false> { };

template<typename ...T>
constexpr typename sfinae<sizeof...(T) == 256>::type compute(int n, T... t) { 
  return table {{ t... }}; 
}

template<typename ...T>
constexpr typename sfinae<sizeof...(T) <= 255>::type compute(int n, T... t) {
  return compute(n+1, t..., computek(n));
}

constexpr table crc_table = compute(0);

#include <iostream>

int main() {
  for(int i = 0; i < 256; i++)
    std::cout << crc_table.data[i] << std::endl;
}

Você pode usar crc_table.data[X]em tempo de compilação porque crc_tableé constexpr.

Este é o meu primeiro metaprograma :

#include <cassert>
#include <cstddef>

template <std::size_t N, template <unsigned long> class T, unsigned long In>
struct times : public T<times<N-1,T,In>::value> {};

template <unsigned long In, template <unsigned long> class T>
struct times<1,T,In> : public T<In> {};

template <unsigned long C>
struct iter {
    enum { value = C & 1 ? 0xedb88320L ^ (C >> 1) : (C >> 1) };
};

template <std::size_t N>
struct compute : public times<8,iter,N> {};

unsigned long crc_table[] = {
    compute<0>::value,
    compute<1>::value,
    compute<2>::value,
    // .
    // .
    // .
    compute<254>::value,
    compute<255>::value,
};

/* Reference Table of CRCs of all 8-bit messages. */
unsigned long reference_table[256];

/* Flag: has the table been computed? Initially false. */
int reference_table_computed = 0;

/* Make the table for a fast CRC. */
void make_reference_table(void)
{
    unsigned long c;

    int n, k;
    for (n = 0; n < 256; n++) {
        c = (unsigned long) n;
        for (k = 0; k < 8; k++) {
            if (c & 1) {
                c = 0xedb88320L ^ (c >> 1);
            } else {
                c = c >> 1;
            }
        }
        reference_table[n] = c;
    }
    reference_table_computed = 1;
}

int main() {
    make_reference_table();
    for(int i = 0; i < 256; ++i) {
        assert(crc_table[i] == reference_table[i]);
    }
}

Eu "codifiquei" as chamadas para o modelo que faz o cálculo :)

D

import std.stdio, std.conv;

string makeCRC32Table(string name){

  string result = "immutable uint[256]"~name~" = [ ";

  for(uint n; n < 256; n++){
    uint c = n;
    for(int k; k < 8; k++)
      c = (c & 1) ? 0xedb88320L ^ (c >> 1) : c >>1;
    result ~= to!string(c) ~ ", ";
  }
  return result ~ "];";
}

void main(){

  /* fill table during compilation */
  mixin(makeCRC32Table("crc_table"));

  /* print the table */
  foreach(c; crc_table)
    writeln(c);
}

Realmente envergonha C ++, não é?

C / C ++, 306295 bytes

#define C(c)((c)>>1^((c)&1?0xEDB88320L:0))
#define K(c)(C(C(C(C(C(C(C(C(c))))))))),
#define F(h,l)K((h)|(l+0))K((h)|(l+1))K((h)|(l+2))K((h)|(l+3))
#define R(h)F(h<<4,0)F(h<<4,4)F(h<<4,8)F(h<<4,12)
unsigned long crc_table[]={R(0)R(1)R(2)R(3)R(4)R(5)R(6)R(7)R(8)R(9)R(10)R(11)R(12)R(13)R(14)R(15)};

Trabalhando ao contrário, terminamos com uma matriz longa não assinada chamada crc_table. Podemos omitir o tamanho da matriz, pois as macros garantirão que haja exatamente 256 elementos na matriz. Inicializamos a matriz com 16 'linhas' de dados usando 16 invocações da macro R.

Cada chamada de R se expande em quatro fragmentos (macro F) de quatro constantes (macro K) para um total de 16 'colunas' de dados.

A macro K é o loop desenrolado indexado por k no código da pergunta original. Ele atualiza o valor c oito vezes chamando a macro C.

Essa solução baseada em pré-processador usa bastante memória durante a expansão da macro. Tentei torná-lo um pouco mais curto com um nível extra de expansão de macro e meu compilador vomitou. O código acima é compilado (lentamente) com o Visual C ++ 2012 e o g ++ 4.5.3 no Cygwin (Windows 7 de 64 bits e 8 GB de RAM).

Editar:

O fragmento acima tem 295 bytes, incluindo espaço em branco. Depois de expandir todas as macros, exceto C, ele cresce para 9.918 bytes. À medida que cada nível de macro C é expandido, o tamanho aumenta rapidamente:

1. 25.182
2. 54.174
3. 109.086
4. 212.766
5. 407.838
6. 773.406
7. 1.455.390
8. 2.721.054

Assim, quando todas as macros foram expandidas, esse pequeno arquivo de 295 bytes se expande para mais de 2,7 megabytes de código que devem ser compilados para gerar a matriz original de 1024 bytes (assumindo valores longos não assinados de 32 bits)!

Outra edição:

Modifiquei a macro C com base em uma macro de outra resposta para extrair 11 bytes extras e reduzi bastante o tamanho total da macro expandida. Embora 2,7 MB não sejam tão ruins quanto 54 MB (o tamanho final anterior de toda a expansão de macros), ainda é significativo.

Eu modificaria a resposta anterior substituindo as três últimas linhas por:

#define crc4( x)    crcByte(x), crcByte(x+1), crcByte(x+2), crcByte(x+3)
#define crc16( x)   crc4(x), crc4(x+4), crc4(x+8), crc4(x+12)
#define crc64( x)   crc16(x), crc16(x+16), crc16(x+32), crc16(x+48)
#define crc256( x)  crc64(x), crc64(x+64), crc64(x+128), crc64(x+192)

Onde crcByte é sua macro K sem a vírgula à direita. Em seguida, crie a própria tabela com:

static const unsigned long crc32Table[256] = { crc256( 0)};

E nunca deixe de fora o tamanho da matriz, pois o compilador verificará se você tem a quantidade correta de elementos.