Die Referenzimplementierung von CRC32 berechnet zur Laufzeit eine Nachschlagetabelle:

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

Können Sie die Tabelle zur Kompilierungszeit berechnen und so die Funktion und das Statusflag entfernen?

Hier ist eine einfache C-Lösung:

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

Es stützt sich auf das nicht standardmäßige __COUNTER__Makro sowie auf eine Auswertungssemantik, die __COUNTER__ausgewertet wird, bevor sie als Argument an ein Makro übergeben wird.

Beachten Sie, dass, da STEPdas Argument zweimal ausgewertet wird und CRCacht verschachtelte Aufrufe verwendet werden, die Codegröße eine kleine kombinatorische Explosion aufweist:

$ cpp crc32table.c | wc -c
4563276

Ich habe dies in GCC 4.6.0 und Clang 2.8 unter 32-Bit-Linux getestet und beide haben die richtige Tabelle erstellt.

Die Kernschleife

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

kann in eine Meta-Funktion umgewandelt werden:

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

Dann werden 256 Aufrufe dieser Meta-Funktion (für den Array-Initialisierer) vom Präprozessor generiert:

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

Wenn Sie Boost installiert haben, ist das Generieren des Array-Initialisierers etwas einfacher:

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

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

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

Schließlich druckt der folgende Testtreiber einfach alle Array-Elemente auf die Konsole:

#include <cstdio>

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

Eine C ++ 0x Lösung

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

Funktioniert mit GCC (4.6.1) und Clang (Trunk 134121).

C ++ 0x mit constexpr. Funktioniert mit 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;
}

Sie können dann crc_table.data[X]zur Kompilierungszeit verwenden , weil crc_tableist constexpr.

Dies ist mein erstes Metaprogramm :

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

Ich habe die Aufrufe der Vorlage, die die Berechnung durchführt, "hardcodiert" :)

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

C ++ wird wirklich beschämt, nicht wahr?

C / C ++, 306 295 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)};

Bei umgekehrter Arbeit erhalten wir ein vorzeichenloses langes Array mit dem Namen crc_table. Wir können die Größe des Arrays weglassen, da die Makros sicherstellen, dass das Array genau 256 Elemente enthält. Wir initialisieren das Array mit 16 'Datenzeilen', indem wir 16 Aufrufe des Makros R verwenden.

Jeder Aufruf von R expandiert in vier Fragmente (Makro F) von vier Konstanten (Makro K) für insgesamt 16 "Datenspalten".

Das Makro K ist die entrollte Schleife, die im Code der ursprünglichen Frage mit k indiziert ist. Der Wert c wird achtmal aktualisiert, indem das Makro C aufgerufen wird.

Diese auf Präprozessoren basierende Lösung beansprucht während der Makro-Erweiterung ziemlich viel Speicher. Ich habe versucht, es ein wenig kürzer zu machen, indem ich eine zusätzliche Stufe der Makro-Erweiterung hatte und mein Compiler puked. Der obige Code wird (langsam) mit Visual C ++ 2012 und g ++ 4.5.3 unter Cygwin (Windows 7 64-Bit 8 GB RAM) kompiliert.

Bearbeiten:

Das obige Fragment enthält 295 Bytes einschließlich Leerzeichen. Nachdem alle Makros mit Ausnahme von C erweitert wurden, wächst sie auf 9.918 Byte. Mit jeder Ebene des C-Makros wächst die Größe schnell:

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

Wenn also alle Makros erweitert wurden, wird diese kleine 295-Byte-Datei zu über 2,7 Megabyte Code erweitert, der kompiliert werden muss, um das ursprüngliche 1024-Byte-Array zu generieren (unter der Annahme von vorzeichenlosen 32-Bit-Long-Werten)!

Eine andere Bearbeitung:

Ich habe das C-Makro basierend auf einem Makro aus einer anderen Antwort modifiziert, um zusätzliche 11 Bytes herauszupressen, und die vollständig erweiterte Makrogröße stark reduziert. 2,7 MB sind zwar nicht so schlimm wie 54 MB (die vorherige endgültige Größe aller Makroerweiterungen), sie sind jedoch immer noch von Bedeutung.

Ich würde die vorherige Antwort ändern, indem ich die letzten drei Zeilen durch Folgendes ersetze:

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

Wobei crcByte sein K-Makro ohne das nachstehende Komma ist. Dann bauen Sie die Tabelle selbst mit:

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

Lassen Sie niemals die Größe des Arrays aus, da der Compiler dann überprüft, ob Sie über die richtige Anzahl von Elementen verfügen.