Implementacja referencyjna CRC32 oblicza tabeli odnośników w czasie wykonywania:

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

Czy możesz obliczyć tabelę w czasie kompilacji, pozbywając się w ten sposób funkcji i flagi statusu?

Oto proste rozwiązanie C:

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

Opiera się na niestandardowym __COUNTER__makrze, a także semantyce oceny, w której __COUNTER__jest oceniany przed przekazaniem go jako argument do makra.

Zauważ, że skoro STEPdwukrotnie ocenia swój argument i CRCużywa ośmiu jego zagnieżdżonych wywołań, rozmiar kodu jest niewielki w kombinacji:

$ cpp crc32table.c | wc -c
4563276

Przetestowałem to w GCC 4.6.0 i Clang 2.8 na 32-bitowym Linuksie i oba tworzą poprawną tabelę.

Pętla rdzenia

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

można przekształcić w meta-funkcję:

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

Następnie preprocesor generuje 256 wywołań tej meta-funkcji (dla inicjatora macierzy):

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

Jeśli masz zainstalowany Boost, generowanie inicjalizatora tablicy jest nieco prostsze:

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

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

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

Wreszcie następujący sterownik testowy po prostu drukuje wszystkie elementy tablicy w konsoli:

#include <cstdio>

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

Rozwiązanie 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;
}

Działa na GCC (4.6.1) i Clang (trunk 134121).

C ++ 0x z constexpr. Działa na 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;
}

Możesz wtedy użyć crc_table.data[X]w czasie kompilacji, ponieważ crc_tablejest constexpr.

To jest mój pierwszy metaprogram :

#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]);
    }
}

„Zakodowałem” wywołania szablonu, który wykonuje obliczenia :)

re

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

Naprawdę zawstydza C ++, prawda?

C / C ++, 306 295 bajtów

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

Pracując w odwrotnej kolejności, otrzymujemy niepodpisaną długą tablicę o nazwie crc_table. Możemy pominąć rozmiar tablicy, ponieważ makra zapewnią, że w tablicy jest dokładnie 256 elementów. Inicjujemy tablicę za pomocą 16 „wierszy” danych, używając 16 wywołań makra R.

Każde wywołanie R rozwija się do czterech fragmentów (makro F) czterech stałych (makro K), co daje 16 „kolumn” danych.

Makro K jest rozwiniętą pętlą indeksowaną przez k w kodzie z pierwotnego pytania. Aktualizuje wartość c osiem razy, wywołując makro C.

To rozwiązanie oparte na preprocesorze zużywa sporo pamięci podczas rozwijania makr. Próbowałem to zrobić nieco krócej, mając dodatkowy poziom ekspansji makr, a mój kompilator zwymiotował. Powyższy kod kompiluje się (powoli) zarówno z Visual C ++ 2012, jak i g ++ 4.5.3 pod Cygwin (Windows 7 64 bit 8 GB RAM).

Edytować:

Powyższy fragment ma 295 bajtów, w tym białe znaki. Po rozwinięciu wszystkich makr oprócz C rośnie do 9 918 bajtów. W miarę rozszerzania każdego poziomu makra C rozmiar szybko rośnie:

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

Do czasu rozwinięcia wszystkich makr ten mały plik 295 bajtów rozwija się do ponad 2,7 megabajtów kodu, który należy skompilować, aby wygenerować oryginalną tablicę 1024 bajtów (przy założeniu 32 bitowych długich wartości bez znaku)!

Kolejna edycja:

Zmodyfikowałem makro C na podstawie makra z innej odpowiedzi, aby wycisnąć dodatkowe 11 bajtów, i znacznie zmniejszyłem pełny rozmiar makra. Chociaż 2,7 MB nie jest tak złe jak 54 MB (poprzedni końcowy rozmiar wszystkich rozszerzeń makr), nadal jest znaczące.

Zmodyfikowałbym poprzednią odpowiedź, zastępując ostatnie trzy wiersze:

#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)

Gdzie crcByte jest jego makro K bez końcowego przecinka. Następnie zbuduj sam stół za pomocą:

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

I nigdy nie pomijaj rozmiaru tablicy, ponieważ kompilator sprawdzi, czy masz odpowiednią liczbę elementów.