Calculer la table CRC32 au moment de la compilation [fermé]

16

L' implémentation de référence de CRC32 calcule une table de recherche au moment de l'exécution:

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

Pouvez-vous calculer la table au moment de la compilation, éliminant ainsi la fonction et l'indicateur d'état?

fredoverflow
la source
2
Quel est le principal critère de gain objectif ici?
John Dvorak
De plus, les questions spécifiques à la langue sont désapprouvées ici. vous devez supprimer la balise c ++.
fier haskeller du

Réponses:

12

Voici une solution simple en 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

Il s'appuie sur la __COUNTER__macro non standard , ainsi que sur une sémantique d'évaluation où __COUNTER__est évalué avant d'être passé comme argument à une macro.

Notez que, puisque STEPévalue son argument deux fois et en CRCutilise huit invocations imbriquées, il y a une petite explosion combinatoire dans la taille du code:

$ cpp crc32table.c | wc -c
4563276

J'ai testé cela dans GCC 4.6.0 et Clang 2.8 sur Linux 32 bits, et les deux produisent le bon tableau.

Joey Adams
la source
Génial, je ne m'attendais certainement pas à ça. Avoir un +1.
R. Martinho Fernandes
9

La boucle centrale

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

peut être converti en une méta-fonction:

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

Ensuite, 256 appels à cette méta-fonction (pour l'initialiseur de tableau) sont générés par le préprocesseur:

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

Si Boost est installé, la génération de l'initialiseur de tableau est un peu plus simple:

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

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

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

Enfin, le pilote de test suivant imprime simplement tous les éléments du tableau sur la console:

#include <cstdio>

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

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

Fonctionne sur GCC (4.6.1) et Clang (trunk 134121).

Johannes Schaub - litb
la source
Concernant C >> 1, N'est-ce pas déplacer des valeurs négatives vers le bon comportement non spécifié? ;)
fredoverflow
Pouvez-vous également expliquer la partie où vous définissez le tableau? Je suis un peu perdu là-bas ...
fredoverflow
@Fred vous avez raison. Je ferai également Cun unsigned long. Le tableau de constantes est défini pour être initialisé par l'extension du pack D.... Dest un pack de paramètres de modèle non type. Une fois que GCC le prend en charge, on peut également déclarer le tableau en classe avec static unsigned long constexpr crc_table[] = { D... };, mais GCC n'analyse pas encore les initialiseurs en classe contreventés. L'avantage sera qu'il compute<>::crc_table[I]pourrait être utilisé dans des expressions constantes plus tard dans le code.
Johannes Schaub - litb
5

C ++ 0x avec constexpr. Fonctionne sur 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;
}

Vous pouvez ensuite utiliser crc_table.data[X]au moment de la compilation car crc_tableest constexpr.

Johannes Schaub - litb
la source
4

Ceci est mon premier métaprogramme :

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

J'ai "codé en dur" les appels au modèle qui fait le calcul :)

R. Martinho Fernandes
la source
1
Si vous voulez le faire de cette façon, pourquoi ne pas coder en dur les valeurs réelles dans le programme? (Après les avoir obtenus avec une autre méthode, bien sûr.) Économise du temps de compilation.
Matthew Read
+1 pour le test et le timesmodèle
fredoverflow
@Matthew: avec seulement C ++ 03, il y a peu de choix. Vous pouvez utiliser le préprocesseur, comme l'a fait Fred, mais cela ne raccourcira pas le temps de compilation. Et apparemment, son préprocesseur s'étouffe avec sa solution :)
R. Martinho Fernandes
@Matthew Le but est de le calculer au moment de la compilation , et non de les avoir codés en dur. La réponse de Fred génère un tableau de cette forme: en 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 ,utilisant le préprocesseur. Il faut environ autant de temps pour compiler que le mien. Si vous le souhaitez, vous pouvez lire ce dernier paragraphe comme "J'ai déroulé la boucle extérieure". Il n'y a pas d'autre choix en C ++ 03
R. Martinho Fernandes
Ah, je ne faisais pas assez attention aux exigences de la question. +1, bien que je ne sois plus sûr d'aimer la question. J'aime mes défis de code pratiques: P
Matthew Lire le
3

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

Cela fait vraiment honte au C ++, n'est-ce pas?

Arlen
la source
2
En fait, je préfère les solutions non typées. Cela ressemble beaucoup à la compilation eval.
R. Martinho Fernandes
Pas besoin d'utiliser un mixage de chaînes pour cela, voici comment nous le faisons dans la bibliothèque standard de D , genTables et call-site pour stocker le résultat dans le segment de données const.
Martin Nowak
3

C / C ++, 306 295 octets

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

En travaillant en sens inverse, nous nous retrouvons avec un long tableau non signé nommé crc_table. Nous pouvons omettre la taille du tableau car les macros garantiront qu'il y a exactement 256 éléments dans le tableau. Nous initialisons le tableau avec 16 «lignes» de données en utilisant 16 invocations de la macro R.

Chaque invocation de R se développe en quatre fragments (macro F) de quatre constantes (macro K) pour un total de 16 «colonnes» de données.

La macro K est la boucle déroulée indexée par k dans le code de la question d'origine. Il met à jour la valeur c huit fois en appelant la macro C.

Cette solution basée sur un préprocesseur utilise beaucoup de mémoire lors de l'expansion des macros. J'ai essayé de le raccourcir un peu en ayant un niveau supplémentaire d'expansion de macro et mon compilateur a vomi. Le code ci-dessus se compile (lentement) avec Visual C ++ 2012 et g ++ 4.5.3 sous Cygwin (Windows 7 64 bits 8 Go de RAM).

Éditer:

Le fragment ci-dessus fait 295 octets, espace blanc compris. Après avoir développé toutes les macros sauf C, il passe à 9 918 octets. Au fur et à mesure que chaque niveau de macro C est développé, la taille augmente rapidement:

  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

Donc, au moment où toutes les macros ont été développées, ce petit fichier de 295 octets se développe en plus de 2,7 mégaoctets de code qui doivent être compilés pour générer le tableau d'origine de 1024 octets (en supposant des valeurs longues non signées 32 bits)!

Un autre montage:

J'ai modifié la macro C sur la base d'une macro d'une autre réponse pour extraire 11 octets supplémentaires et j'ai considérablement réduit la taille de la macro étendue. Bien que 2,7 Mo ne soit pas aussi mauvais que 54 Mo (la taille finale précédente de toutes les extensions de macro), il est toujours important.

CasaDeRobison
la source
Ce n'est pas du golf de code , vous n'avez donc pas besoin de minimiser le nombre de caractères.
Ilmari Karonen du
Ah. Donc c'est. Mon mauvais côté. Bien que je pense que cette implémentation est portable (j'entends par là qu'elle est conforme au langage C et au préprocesseur; sa véritable portabilité dépendra des limites exactes de l'environnement sur l'expansion des macros).
CasaDeRobison
3

Je modifierais la réponse précédente en remplaçant les trois dernières lignes par:

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

Où crcByte est sa macro K sans la virgule de fin. Créez ensuite la table elle-même avec:

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

Et ne laissez jamais de côté la taille du tableau car le compilateur vérifiera alors que vous avez la bonne quantité d'éléments.

Geai
la source