Compiler le temps de hachage de la chaîne

Question

J'ai lu à différents endroits que l'utilisation de C++11 de la nouvelle chaîne de caractères littéraux, il pourrait être possible de calculer une chaîne de hash au moment de la compilation. Cependant, personne ne semble être prêt à sortir et de dire qu'il sera possible, ou comment il serait fait.

• Est-ce possible?
• Ce serait l'opérateur?

---

Je suis particulièrement intéressé cas d'utilisation de ce genre.

void foo( const std::string& value )
{
   switch( std::hash(value) )
   {
      case "one"_hash: one(); break;
      case "two"_hash: two(); break;
      /*many more cases*/
      default: other(); break;
   }
}

Remarque: le temps de compilation fonction de hachage n'avons pas à chercher exactement comme je l'ai écrit. J'ai fait de mon mieux pour deviner ce que la solution finale devrait ressembler, mais meta_hash<"string"_meta>::value pourrait également être une solution viable.

Answer 1

C’est un peu tard, mais j’ai réussi à implémenter une fonction CRC32 au moment de la compilation avec l’utilisation de constexpr . Le problème, c’est qu’au moment de l’écriture, cela ne fonctionne qu'avec GCC et pas avec MSVC ni le compilateur Intel.

Voici l'extrait de code:

 // CRC32 Table (zlib polynomial)
static constexpr uint32_t crc_table[256] = {
    0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
    0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
    0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
...
};
template<size_t idx>
constexpr uint32_t crc32(const char * str)
{
    return (crc32<idx-1>(str) >> 8) ^ crc_table[(crc32<idx-1>(str) ^ str[idx]) & 0x000000FF];
}

// This is the stop-recursion function
template<>
constexpr uint32_t crc32<size_t(-1)>(const char * str)
{
    return 0xFFFFFFFF;
}

// This doesn't take into account the nul char
#define COMPILE_TIME_CRC32_STR(x) (crc32<sizeof(x) - 2>(x) ^ 0xFFFFFFFF)

enum TestEnum
{
    CrcVal01 = COMPILE_TIME_CRC32_STR("stack-overflow"),
};
 

CrcVal01 est égal à 0x335CC04A

J'espère que ceci vous aidera!

Answer 2

Au moins par ma lecture du §7.1.5/3 et §5.19, les éléments suivants pourraient être légitimes:

unsigned constexpr const_hash(char const *input) {
    return *input ?
        static_cast<unsigned int>(*input) + 33 * const_hash(input + 1) :
        5381;
}

Cela ne semble pas suivre les règles de base dans le §7.1.5/3:

1. Le formulaire est: "le retour de l'expression;"
2. Son seul paramètre est un pointeur, qui est un type scalaire, et, par conséquent, un type de littéral.
3. Son retour est de type unsigned int, qui est également scalaire (et donc littérale).
4. Il n'y a pas de conversion implicite du type de retour.

Il ya une certaine question de savoir si l' *inputs impliquer illégale d'un lvalue à rvalue de conversion, et je ne suis pas sûr de comprendre les règles du §5.19/2/6/2¹ et §4.1 assez bien pour être sûr à ce sujet.

À partir d'un point de vue pratique, ce code est accepté par (pour un exemple) g++, au moins aussi loin que g++ 4.7.1.

L'utilisation serait quelque chose comme:

switch(std::hash(value)) {
    case const_hash("one"): one(); break;
    case const_hash("two"): two(); break;
    // ...
    default: other(); break;
}

Pour se conformer aux exigences du §5.19/2/6/2 vous pourriez avoir à faire quelque chose comme cela:

// one of the `constexpr`s is probably redundant, but I haven't figure out which.
char constexpr * constexpr v_one = "one"; 

// ....

case const_hash(v_one): one(); break;

1. Je suis à l'aide de l'extra "slash" numéros pour désigner des innombrables points de balle, c'est donc le deuxième point à l'intérieur si le sixième point, en vertu du §5.19/2. Je pense que je pourrais avoir à parler à Pete Becker, de savoir s'il est possible d'ajouter une sorte de chiffres/lettres/chiffres romains en bas de la hiérarchie pour identifier les pièces de ce genre...

Answer 3

C'est une tentative de résoudre le cas des OP problème aussi précisément que possible.

namespace my_hash {
  template<class>struct hasher;
  template<>
  struct hasher<std::string> {
    std::size_t constexpr operator()(char const *input)const {
      return *input ?
        static_cast<unsigned int>(*input) + 33 * (*this)(input + 1) :
        5381;
    }
    std::size_t operator()( const std::string& str ) const {
      return (*this)(str.c_str());
    }
  };
  template<typename T>
  std::size_t constexpr hash(T&& t) {
    return hasher< typename std::decay<T>::type >()(std::forward<T>(t));
  }
  inline namespace literals {
    std::size_t constexpr operator "" _hash(const char* s,size_t) {
      return hasher<std::string>()(s);
    }
  }
}
using namespace my_hash::literals;
void one() {} void two() {} void other() {}

void foo( const std::string& value )
{
  switch( my_hash::hash(value) )
  {
    case "one"_hash: one(); break;
    case "two"_hash: two(); break;
    /*many more cases*/
    default: other(); break;
  }
}

exemple vivant.

Notez la différence principale -- std::hash ne peut pas être utilisé, car nous n'avons pas de contrôle std::hashs'algorithme, et nous devons ré-écrire comme un constexpr afin d'évaluer au moment de la compilation. En outre, il n'y a pas "transparent" hachages en std, de sorte que vous ne pouvez pas sans la création d'un std::string) hachage raw d'un tampon de caractères en tant que std::string.

J'ai collé l' std::string personnalisé hasher (avec transparence const char* de soutien) en my_hash d'espace de noms, de sorte que vous pouvez les stocker dans un std::unordered_map si vous avez besoin de cohérence.

Basé sur @JerryCoffin excellente réponse et le fil de commentaires ci-dessous, mais avec une tentative d'écriture avec C++11 meilleures pratiques (par opposition à prévoir!).

Answer 4

Notez que la forme présentée ici n'a pas été acceptée dans la norme, comme indiqué ci-dessous.

Moment de la compilation, traitement de chaîne est deviné à devenir possible à travers définis par l'utilisateur littéraux proposé dans N2765.
Comme je l'ai déjà mentionné, je ne sais pas du tout compilateur qui implémente actuellement et sans prise en charge du compilateur il ne peut être que du domaine de la conjecture.

Dans le §2.13.7.3 et 4 du projet de nous avons les éléments suivants:

Autre (S contient un littéral de l'opérateur modèle), L est traité comme un appel de la forme
l'opérateur "" X< "c1", "c2', ... , 'ck'>() où n est la source de la séquence de caractères c1c2...ck. [Note: La séquence c1c2...ck peut ne contient que des caractères à partir de la source de base de jeu de caractères. -la note de fin]

Combinez cela avec constexpr et nous devrions avoir le temps de compilation de la chaîne de traitement.

mise à jour: j'ai oublié que je lisais le mauvais point, ce formulaire est autorisé définies par l'utilisateur-entier-littéraux et flottant littéraux, mais apparemment pas pour cordes-littéraux (§2.13.7.5).
Cette partie de la proposition semble ne pas avoir été accepté.

Cela étant dit, avec mon peu de aperçu de C++0x, il pourrait ressembler à quelque chose comme ceci (j'ai probablement eu quelque chose de mal):

template<char c, char... str>
struct hash {
    static const unsigned result = c + hash<str...>::result;
};

template<char c>
struct hash {
    static const unsigned result = c;
};

template<char... str> 
constexpr unsigned
operator "" _hash() {
    return hash<str>::result;
}

// update: probably wrong, because the above 
// form is not allowed for string-literals:    
const unsigned h = "abcd"_hash;

---

Si Jerrys approche fonctionne, alors le suivant devrait fonctionner, cependant:

constexpr unsigned operator "" _hash(const char* s, size_t) {
    return const_hash(s);
}

Answer 5

Ce qui suit fonctionne dans GCC 4.6.1, et vous pouvez utiliser soit hash ou pack dans les blocs de commutateurs.

 /* Fast simple string hash (Bernstein?) */                                       
constexpr unsigned int hash(const char *s, int off = 0) {                        
    return !s[off] ? 5381 : (hash(s, off+1)*33) ^ s[off];                           
}                                                                                

/* Pack the string into an unsigned int                                          
 * Using 7 bits (ascii) it packs 9 chars into a uint64_t                         
 */                                                                              
template <class T = uint64_t, unsigned int Bits = 7>                             
constexpr T pack(const char *s, unsigned int off = 0) {                          
    return (Bits*off >= CHAR_BIT*sizeof(T) || !s[off]) ? 0 :                     
        (((T)s[off] << (Bits*off)) | pack(s,off+1));                             
}  
 

Apparemment, GCC (?) N'autorise pas les appels récursifs où nous transmettons un pointeur à s+1 avec s , c'est pourquoi j'utilise la variable off .