The acuan pelaksanaan CRC32 menghitung tabel lookup saat runtime:

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

Bisakah Anda menghitung tabel pada waktu kompilasi, sehingga menyingkirkan fungsi dan flag status?

Inilah solusi C sederhana:

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

Itu bergantung pada __COUNTER__makro tidak standar , serta semantik evaluasi di mana __COUNTER__dievaluasi sebelum diteruskan sebagai argumen ke makro.

Perhatikan bahwa, sejak STEPmengevaluasi argumennya dua kali, dan CRCmenggunakan delapan pemanggilan bersarang, ada ledakan kombinatorial kecil dalam ukuran kode:

$ cpp crc32table.c | wc -c
4563276

Saya menguji ini di GCC 4.6.0 dan Dentang 2.8 pada Linux 32-bit, dan keduanya menghasilkan tabel yang benar.

Lingkaran inti

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

dapat dikonversi menjadi fungsi-meta:

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

Kemudian, 256 panggilan ke fungsi-meta ini (untuk penginisialisasi array) dihasilkan oleh preprocessor:

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

Jika Anda telah memasang Boost, membuat penginisialisasi array sedikit lebih sederhana:

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

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

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

Akhirnya, driver tes berikut ini hanya mencetak semua elemen array ke konsol:

#include <cstdio>

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

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

Bekerja pada GCC (4.6.1) dan Dentang (trunk 134121).

C ++ 0x dengan constexpr. Bekerja pada 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;
}

Anda kemudian dapat menggunakan crc_table.data[X]pada waktu kompilasi karena crc_tableini constexpr.

Ini adalah metaprogram pertama saya :

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

Saya "hardcoded" panggilan ke template yang melakukan perhitungan :)

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

Itu benar-benar membuat C ++ malu, bukan?

C / C ++, 306 295 byte

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

Bekerja secara terbalik, kita berakhir dengan array panjang tanpa tanda bernama crc_table. Kita dapat menghilangkan ukuran array karena makro akan memastikan ada persis 256 elemen dalam array. Kami menginisialisasi array dengan 16 'baris' data dengan menggunakan 16 doa makro R.

Setiap doa R berkembang menjadi empat fragmen (makro F) dari empat konstanta (makro K) dengan total 16 'kolom' data.

Makro K adalah loop terbuka dengan diindeks oleh k dalam kode dari pertanyaan asli. Ini memperbarui nilai c delapan kali dengan memanggil makro C.

Solusi berbasis preprosesor ini menggunakan sedikit memori selama ekspansi makro. Saya mencoba membuatnya sedikit lebih pendek dengan memiliki level tambahan ekspansi makro dan compiler saya muntah. Kode di atas mengkompilasi (secara perlahan) dengan Visual C ++ 2012 dan g ++ 4.5.3 di bawah Cygwin (Windows 7 64 bit 8GB RAM).

Edit:

Fragmen di atas adalah 295 byte termasuk spasi. Setelah memperluas semua makro kecuali untuk C tumbuh menjadi 9,918 byte. Karena setiap tingkat makro C diperluas ukurannya tumbuh dengan cepat:

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

Jadi pada saat semua makro telah diperluas, file 295 byte kecil itu berkembang menjadi lebih dari 2,7 megabita kode yang harus dikompilasi untuk menghasilkan array 1024 byte asli (dengan asumsi 32 bit nilai panjang yang tidak ditandatangani)!

Suntingan lain:

Saya memodifikasi makro C berdasarkan makro dari jawaban lain untuk memeras tambahan 11 byte, dan sangat mengurangi ukuran makro yang diperluas penuh. Meskipun 2,7 MB tidak seburuk 54 MB (ukuran akhir sebelumnya dari semua ekspansi makro), ini masih signifikan.

Saya akan memodifikasi jawaban sebelumnya dengan mengganti tiga baris terakhir dengan:

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

Di mana crcByte adalah makro K tanpa koma tertinggal. Kemudian buat tabel itu sendiri dengan:

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

Dan jangan pernah meninggalkan ukuran array karena kompiler akan memverifikasi bahwa Anda memiliki jumlah elemen yang benar.