Oblicz tabelę CRC32 w czasie kompilacji [zamknięte]

16

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?

code-challenge  c++  compile-time 
— fredoverflow
źródło
2
Jakie jest tutaj główne obiektywne kryterium wygranej?
— John Dvorak,
nie są też mile widziane pytania specyficzne dla języka. powinieneś usunąć tag c ++.
— dumny haskeller

Odpowiedzi:

12

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ę.

— Joey Adams
źródło
Wspaniale, na pewno się tego nie spodziewałem. Masz +1.
— R. Martinho Fernandes,
9

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]);
    }
}
— fredoverflow
źródło
6

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

— Johannes Schaub - litb
źródło
Odnośnie C >> 1: Czy przesunięcie wartości ujemnych na właściwe, nieokreślone zachowanie? ;)
— fredoverflow
Czy możesz również wyjaśnić część, w której definiujesz tablicę? Trochę się tam zagubiłem ...
— fredoverflow
@Fred masz rację. Będę również . Stała tablica jest definiowana jako inicjowana przez rozszerzenie pakietu . to nietypowy pakiet parametrów szablonu. Gdy GCC go obsługuje, można również zadeklarować tablicę w klasie , ale GCC nie analizuje jeszcze inicjalizujących w klasie wzmocnionych. Korzyścią będzie to, że można je wykorzystać w stałych wyrażeniach w dalszej części kodu. Cunsigned longD...Dstatic unsigned long constexpr crc_table[] = { D... };compute<>::crc_table[I]
— Johannes Schaub - litb
5

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.

— Johannes Schaub - litb
źródło
4

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

— R. Martinho Fernandes
źródło
1
Jeśli zamierzasz to zrobić w ten sposób, dlaczego po prostu nie zakodowałbyś rzeczywistych wartości w programie? (Oczywiście po uzyskaniu ich inną metodą.) Oszczędność czasu kompilacji.
— Mateusz
+1 za test i timesszablon
— fredoverflow
@Matthew: tylko C ++ 03 nie ma większego wyboru. Możesz użyć preprocesora, tak jak Fred, ale to nie skróci czasu kompilacji. I najwyraźniej jego preprocesor dusi się w swoim rozwiązaniu :)
— R. Martinho Fernandes
@Matthew Chodzi o to, aby obliczyć go w czasie kompilacji , a nie na stałe. Odpowiedź Freda generuje tablicę tego formularza: unsigned crc_table[] = { f<0>::value , f<0 + 1>::value , f<0 + 2>::value , f<0 + 2 + 1>::value , f<0 + 4>::value , f<0 + 4 + 1>::value , f<0 + 4 + 2>::value , f<0 + 4 + 2 + 1>::value , f<0 + 8>::value ,za pomocą preprocesora. Kompilacja zajmuje tyle samo czasu co moja. Jeśli chcesz, możesz przeczytać ten ostatni akapit jako „rozwinąłem zewnętrzną pętlę”. W C ++ 03 nie ma innego wyboru
— R. Martinho Fernandes
Ach, nie zwracałem wystarczającej uwagi na wymagania pytania. +1, choć nie jestem pewien, czy podoba mi się to pytanie. Lubię praktyczne wyzwania związane z kodem: P
— Mateusz Czyta
3

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?

— Arlen
źródło
2
Właściwie wolę rozwiązania nietypowe. Wygląda to jak czas kompilacji eval.
— R. Martinho Fernandes,
Nie trzeba do tego używać mieszania łańcuchów, oto jak to robimy w standardowej bibliotece D , genTables i witrynie wywołań, aby przechowywać wynik w stałym segmencie danych.
— Martin Nowak
3

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.

— CasaDeRobison
źródło
To nie jest golf golfowy , więc nie musisz minimalizować liczby postaci.
— Ilmari Karonen
Ach Tak jest. Mój zły z tej strony. Chociaż myślę, że ta implementacja jest przenośna (przez co rozumiem, że jest zgodna z językiem C i preprocesorem; jej prawdziwa przenośność będzie zależeć od dokładnych ograniczeń środowiska w zakresie rozszerzania makr).
— CasaDeRobison
3

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.

— Sójka
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.