Kompilieren Sie Time String Hashing

100

Ich habe an einigen Stellen gelesen, dass es mit den neuen String-Literalen von C ++ 11 möglich sein könnte, den Hash eines Strings zur Kompilierungszeit zu berechnen. Es scheint jedoch niemand bereit zu sein, herauszukommen und zu sagen, dass es möglich sein wird oder wie es gemacht werden würde.

  • Ist das möglich?
  • Wie würde der Bediener aussehen?

Ich interessiere mich besonders für solche Anwendungsfälle.

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

Hinweis: Die Hash-Funktion zur Kompilierungszeit muss nicht genau so aussehen, wie ich sie geschrieben habe. Ich habe mein Bestes getan, um zu erraten, wie die endgültige Lösung aussehen würde, meta_hash<"string"_meta>::valuekönnte aber auch eine praktikable Lösung sein.

deft_code
quelle
Ich kann anscheinend auch nichts finden, aber ich konnte sehen, dass ich Ihre Hashing-Funktion in einen Zusammenhang zwingen musste.
Luke
4
Gibt es einen Compiler, der bereits benutzerdefinierte Literale unterstützt? Gcc nicht ( gcc.gnu.org/projects/cxx0x.html ) und ich habe auch nicht festgestellt, dass sie für VC10 erwähnt werden. Ohne Compiler-Unterstützung kann dies nur eine Vermutung sein, aber die benutzerdefinierten Literale mit Vorlagen sehen so aus, als ob dies möglich sein sollte.
Georg Fritzsche
1
Es ist süß, aber nicht nützlich? Wenn der Schalterwert eine Laufzeitzeichenfolge ist, müssen Sie auch nach Kollisionen suchen. Vielleicht ist das Packen besser (meine Antwort hat eine Packfunktion zum Füllen von 9 Zeichen in 64 Bit).
u0b34a0f6ae
@ u0b34a0f6ae Warum auf Kollisionen prüfen?
cubuspl42
Der Compiler sollte einen Fehler ausgeben, wenn zwei Fallwerte gleich sind.
Mark Storer

Antworten:

88

Dies ist etwas spät, aber es ist mir gelungen, eine CRC32-Funktion zur Kompilierungszeit mithilfe von zu implementieren constexpr. Das Problem dabei ist, dass es zum Zeitpunkt des Schreibens nur mit GCC und nicht mit MSVC oder Intel Compiler funktioniert.

Hier ist das Code-Snippet:

// 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 ist gleich 0x335CC04A

Hoffe das wird dir helfen!

Clement JACOB
quelle
4
Ja absolut. Ich habe es mit dem Python CRC32-Laufzeitalgorithmus (von zlib) getestet und die Ergebnisse sind dieselben. Tatsächlich versuchen Sie genau zu erreichen, warum ich diese Technik verwende!
Clement JACOB
2
Vielen Dank für die Veröffentlichung, es ist sehr nützlich!
Tamás Szelei
2
Ihnen fehlte ein Kompilierungsflag. Außerdem musste ich den Wert -1 in der Stop-Rekursions-Template-Funktion auf size_t umwandeln. Die aktualisierte Version ist hier verfügbar (ab Clang 3.3): goo.gl/vPMkfB
Clement JACOB
1
constexprist nicht verfügbar in VS2013, außer im November 2013 CTP blogs.msdn.com/b/vcblog/archive/2013/11/18/…
2
Sie rekursieren zweimal. Diese Lösung weist eine exponentielle Komplexität in Bezug auf die Zeichenfolgenlänge auf, und der Compiler ist nicht klug genug, um den zweiten Aufruf zu vermeiden. Überprüfen Sie andere Antworten auf mögliche Lösungen für dieses Problem.
CygnusX1
30

Zumindest durch meine Lektüre von §7.1.5 / 3 und §5.19 könnte Folgendes legitim sein:

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

Dies scheint den Grundregeln in §7.1.5 / 3 zu folgen:

  1. Die Form lautet: "Ausdruck zurückgeben;"
  2. Sein einziger Parameter ist ein Zeiger, der ein Skalartyp und daher ein Literaltyp ist.
  3. Seine Rückgabe ist int ohne Vorzeichen, was ebenfalls skalar (und daher wörtlich) ist.
  4. Es gibt keine implizite Konvertierung in den Rückgabetyp.

Es ist fraglich, ob es sich bei den *inputs um eine illegale Umwandlung von Wert zu Wert handelt, und ich bin mir nicht sicher, ob ich die Regeln in §5.19 / 2/6/2 1 verstehe und §4.1 gut genug verstehe, um sicher zu sein.

Aus praktischer Sicht wird dieser Code von (zum Beispiel) g ++ akzeptiert, zumindest bis zu g ++ 4.7.1.

Verwendung wäre so etwas wie:

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

Um die Anforderungen von §5.19 / 2/6/2 zu erfüllen, müssen Sie möglicherweise Folgendes tun:

// 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. Ich verwende die zusätzlichen Schrägstriche, um auf nicht nummerierte Aufzählungspunkte zu verweisen. Dies ist also der zweite Aufzählungspunkt im Inneren, wenn der sechste Aufzählungspunkt gemäß §5.19 / 2. Ich denke, ich muss vielleicht mit Pete Becker darüber sprechen, ob es möglich ist, Zahlen / Buchstaben / römische Ziffern in der Hierarchie hinzuzufügen, um solche Teile zu identifizieren ...
Jerry Sarg
quelle
3
Zwei Dinge sind daran falsch. 1: Rekursive Anrufe sind nicht zulässig constexpr. 2: Sie haben keine Haltebedingung (wo *input == nullptr) und wie ich verstehe constexpr, können Sie keine haben.
Motti
9
Wo steht, dass Rekursion in einem Constexpr nicht erlaubt ist? Soweit ich sehen kann, heißt es nur, dass alle Funktionen, die Sie aufrufen, selbst als constexprt gekennzeichnet sein müssen (§5.19 / 2/2). Ich habe einen Fehler in der Kündigungsbedingung gemacht, die ich jetzt behoben habe (ich habe versehentlich || verwendet, wo es hätte sein sollen &&).
Jerry Coffin
3
rekursive constexpr. Ich habe einige Sitzungsprotokolle aus dem Jahr 2008 gelesen. Es gab Diskussionen darüber, rekursive Constexpr-Funktionen zuzulassen oder nicht zuzulassen. Das Wesentliche war, dass der aktuelle Wortlaut es nicht verbot und es leicht implizierte. Der Ausschuss war der Ansicht, dass ein derart mächtiges Merkmal ausdrücklich dargelegt werden sollte. Das war im Jahr 2008, ich weiß nicht, was seitdem passiert ist.
Deft_code
3
Richtig - ich hätte wahrscheinlich darauf hinweisen sollen, dass ich von N3000 gegangen bin, was (glaube ich) derzeit der neueste Entwurf ist. Ich bin mir ziemlich sicher, dass es einmal verboten war, aber zumindest für den Moment scheint es erlaubt zu sein.
Jerry Coffin
2
Ähm, der Operator && gibt einen Bool zurück, sodass diese Funktion wahrscheinlich nicht das tut, was Sie wollen. Insbesondere wird 0 für jede leere Zeichenfolge und möglicherweise für bestimmte andere Zeichenfolgen zurückgegeben, die mit einem Zeichen beginnen, das in ein Zeichen konvertiert wird, (unsigned)-1falls vorhanden. und gibt 1 für alle anderen Zeichenfolgen zurück. Mit ternärem bedingtem Operator umschreiben?
Ndkrempel
13

Dies ist ein Versuch, das Problem des OP so genau wie möglich zu lösen.

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

Live-Beispiel .

Beachten Sie die Hauptunterschied - std::hashnicht verwendet werden können, wie wir die Kontrolle über nicht haben std::hashs - Algorithmus‘, und wir müssen es als neu implementieren , constexprum es bei der Kompilierung zu bewerten. Außerdem gibt es keine "transparenten" Hashes std, sodass Sie (ohne Erstellen eines std::string) keinen Rohzeichenpuffer als std::string.

Ich habe den std::stringbenutzerdefinierten Hasher (mit transparenter const char*Unterstützung) in einen my_hashNamespace gesteckt , damit Sie ihn in einem speichern können, std::unordered_mapwenn Sie Konsistenz benötigen.

Basierend auf der exzellenten Antwort von @ JerryCoffin und dem Kommentarthread darunter, aber mit dem Versuch, sie mit den aktuellen C ++ 11-Best Practices zu schreiben (anstatt sie vorwegzunehmen!).

Beachten Sie, dass die Verwendung eines "Raw-Hash" für eine switchAnweisung casegefährlich ist. Anschließend sollten Sie einen ==Vergleich durchführen, um zu bestätigen, dass er funktioniert hat.

Yakk - Adam Nevraumont
quelle
2
Der Live-Beispiel-Link scheint falsch / veraltet zu sein?
Fuenfundachtzig
@fuenfundachtzig Würden Sie glauben, ich habe es gerade repariert?
Yakk - Adam Nevraumont
13

Dieser Ausschnitt basiert auf dem von Clement JACOB. Funktioniert aber auch mit Clang. Und es sollte beim Kompilieren schneller sein (es gibt nur einen rekursiven Aufruf, nicht zwei wie im ursprünglichen Beitrag).

#include <iostream>
#include <string>
#include <vector>

static constexpr unsigned int crc_table[256] = {
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    0xe963a535, 0x9e6495a3,    0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};


template<int size, int idx = 0, class dummy = void>
struct MM{
  static constexpr unsigned int crc32(const char * str, unsigned int prev_crc = 0xFFFFFFFF)
  {
      return MM<size, idx+1>::crc32(str, (prev_crc >> 8) ^ crc_table[(prev_crc ^ str[idx]) & 0xFF] );
  }
};

// This is the stop-recursion function
template<int size, class dummy>
struct MM<size, size, dummy>{
  static constexpr unsigned int crc32(const char * str, unsigned int prev_crc = 0xFFFFFFFF)
  {
      return prev_crc^ 0xFFFFFFFF;
  }
};

// This don't take into account the nul char
#define COMPILE_TIME_CRC32_STR(x) (MM<sizeof(x)-1>::crc32(x))


template<unsigned int crc>
void PrintCrc()
{
    std::cout << crc << std::endl;
}


int main()
{

    PrintCrc<COMPILE_TIME_CRC32_STR("HAH")>();
}

Siehe Proof of Concept hier

Turm120
quelle
1
Vielen Dank, Jacobs Antwort funktioniert gut für das, was ich auf GCC wollte, aber msvc warf Fehler mit größeren Zeichenfolgen. Ihre Antwort funktioniert auf msvc mit den größeren Zeichenfolgen, die ich hashen muss.
Daniel Moodie
8

Beachten Sie, dass das hier gezeigte Formular nicht in den Standard aufgenommen wurde, wie unten angegeben.

Es wird vermutet, dass die Verarbeitung von Zeichenfolgen für die Kompilierungszeit durch benutzerdefinierte Literale möglich wird, die in N2765 vorgeschlagen werden .
Wie ich bereits erwähnt habe, kenne ich keinen Compiler, der es derzeit implementiert, und ohne Compiler-Unterstützung kann es nur Vermutungen geben.

In §2.13.7.3 und 4 des Entwurfs haben wir Folgendes:

Andernfalls (S enthält eine Literaloperatorvorlage) wird L als Aufruf des Formularoperators
"" X <'c1', 'c2', ..., 'ck'> () behandelt, wobei n die Quellzeichenfolge c1c2 ist ... ck. [Hinweis: Die Sequenz c1c2 ... ck darf nur Zeichen aus dem Basisquellzeichensatz enthalten. - Endnote]

Kombinieren Sie das mit constexprund wir sollten die Verarbeitung von Kompilierungszeitzeichenfolgen haben.

Update: Ich habe übersehen, dass ich den falschen Absatz gelesen habe. Dieses Formular ist für benutzerdefinierte Ganzzahl-Literale und Floating-Literale zulässig, aber anscheinend nicht für String-Literale (§2.13.7.5).
Dieser Teil des Vorschlags scheint nicht angenommen worden zu sein.

Abgesehen davon könnte es mit meinem begrenzten Blick auf C ++ 0x ungefähr so aussehen (ich habe höchstwahrscheinlich etwas falsch gemacht):

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;

Wenn Jerrys Ansatz funktioniert, sollte jedoch Folgendes funktionieren:

constexpr unsigned operator "" _hash(const char* s, size_t) {
    return const_hash(s);
}
Georg Fritzsche
quelle
Schöne (und notwendige) Kombination aus Vorlagen mit unterschiedlicher Länge und constexprbenutzerdefiniertem Literal. Ich bin nicht sicher, ob Sie ein Zeichenfolgenliteral als Vorlagenparameter verwenden können. Haben sie keine statische Verknüpfung? (Sie funktionieren zumindest in C ++ 98 und sind daher als Vorlagenparameter verboten).
Motti
Ich habe die Absätze verwechselt und dachte, dass dieser Fall eine Ausnahme war - leider scheint es nicht so zu sein.
Georg Fritzsche
1
@Motti: Wo verwendet gf das String-Literal als Vorlagenparameter? Sind Sie verwirrend, wenn Sie die variadische Vorlage von Zeichen als Zeichenfolgenliteral übergeben?
Deft_code
Aus dem ursprünglichen Vorschlag geht hervor, dass die Vorlagenversion für Zeichenfolgenliterale nicht akzeptiert wurde (aufgrund von Verkettungsproblemen? Stackoverflow.com/questions/1108008/any-ideas-for-c1y/… - Kommentare) - schade.
Georg Fritzsche
1
Die letzte Version von operator ""_hashfunktioniert für mich in Xcode 5.0.2.
cubuspl42
8

Eine andere Lösung, die auf der von Clement JACOB basiert und C ++ 11 constexpr (nicht das erweiterte C ++ 14) verwendet, aber nur eine Rekursion aufweist.

namespace detail {
// CRC32 Table (zlib polynomial)
static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, ... }

template<size_t idx>
constexpr uint32_t combine_crc32(const char * str, uint32_t part) {
  return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
}

template<size_t idx>
constexpr uint32_t crc32(const char * str) {
  return combine_crc32<idx>(str, crc32<idx - 1>(str));
}

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

} //namespace detail

template <size_t len>
constexpr uint32_t ctcrc32(const char (&str)[len]) {
  return detail::crc32<len - 2>(str) ^ 0xFFFFFFFF;
}

Eine Erklärung

  • Wir verwenden eine einzelne Rekursion, damit die Funktion auch für längere Zeichenfolgen gut funktioniert.
  • Mit der Zusatzfunktion combine_crc32können wir das Ergebnis einer Rekursion unter einer Variablen speichern partund zweimal verwenden. Diese Funktion ist eine Problemumgehung für C ++ 11-Grenzwerte, bei denen lokale Variablendeklarationen nicht zulässig sind.
  • Die ctcrc32Funktion erwartet ein String-Literal, das als übergeben wird const char (&)[len]. Auf diese Weise können wir die Zeichenfolgenlänge als Vorlagenparameter abrufen und müssen uns nicht auf Makros verlassen.
CygnusX1
quelle
2
Dies war meine Lieblingsimplementierung, danke.
Daniel Moodie
6

Das Folgende funktioniert in GCC 4.6.1, und Sie können entweder hashoder packin Schalterblöcken verwenden.

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

GCC erlaubt anscheinend (?) Keine rekursiven Aufrufe, bei denen wir s+1mit seinem Zeiger weiterleiten, weshalb ich die offVariable verwende.

u0b34a0f6ae
quelle
5

Wenn Sie einen c ++ 17-Compiler und string_view haben, wird dies trivial. Schreiben Sie einfach die normale Version:

constexpr uint32_t crc32(std::string_view str)
{
    uint32_t crc = 0xffffffff;
    for (auto c : str)
        crc = (crc >> 8) ^ crc_table[(crc ^ c) & 0xff];
    return crc ^ 0xffffffff;
}
Guillaume Gris
quelle
Beachten Sie, dass der Compiler möglicherweise beschließt, dies zur Kompilierungszeit nicht zu verarbeiten, wenn Sie einfach schreiben crc32("mystring")(normalerweise tendiert VS dazu). Der Trick, um dieses Problem zu umgehen, besteht darin, eine constexpr-Variable zu erstellen, die von der Bewertung der Kompilierungszeit Ihres crc32 abhängt. Normalerweiseconstexpr uint32_t val = crc32("mystring");
Guillaume Gris
3

Hier ist eine weitere C ++ 11-Implementierung (basierend auf der Antwort von @ CygnusX1), die sowohl mit constexpr char-Arrays als auch mit Laufzeitzeichenfolgen funktioniert:

namespace detail {

    // CRC32 Table (zlib polynomial)
    static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, ... };

    constexpr uint32_t combine_crc32(size_t idx, const char * str, uint32_t part) {
        return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
    }

    constexpr uint32_t crc32(size_t idx, const char * str) {
        return idx == size_t(-1) ? 
            0xFFFFFFFF : combine_crc32(idx, str, crc32(idx - 1, str));
    }
}

uint32_t ctcrc32(std::string const& str) {
    size_t len = str.size() + 1;
    return detail::crc32(len - 2, str.c_str()) ^ 0xFFFFFFFF;
}

template <size_t len>
constexpr uint32_t ctcrc32(const char (&str)[len]) {
    return detail::crc32(len - 2, str) ^ 0xFFFFFFFF;
}

Sie müssen, str.size() + 1weil lenin der zweiten Überladung strlen(str) + 1auf das Nullzeichen am Ende zurückzuführen ist.

Ich habe keine Überladung hinzugefügt, const char *da dies die zweite Überladung durcheinander bringt. Sie können problemlos Überladungen für const char *, size_toder hinzufügen std::string_view.

Holt
quelle
2

Das ist eine schöne Frage.

Basierend auf der Antwort von Jerry Coffin habe ich eine weitere erstellt, die mit dem std :: hash von Visual Studio 2017 kompatibel ist.

#include <functional>
#include <cassert>
using namespace std;


constexpr size_t cx_hash(const char* input) {
    size_t hash = sizeof(size_t) == 8 ? 0xcbf29ce484222325 : 0x811c9dc5;
    const size_t prime = sizeof(size_t) == 8 ? 0x00000100000001b3 : 0x01000193;

    while (*input) {
        hash ^= static_cast<size_t>(*input);
        hash *= prime;
        ++input;
    }

    return hash;
}


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    auto a = cx_hash("test");
    hash<string> func;
    auto b = func("test");
    assert(a == b);

    return 0;
}

https://github.com/manuelgustavo/cx_hash

Manuel Saraiva
quelle
0

Mir fehlte noch eine crc32-Literal-Variante (was mit Vorlagen nicht möglich ist), daher hier mein Vorschlag, der auf CygnusX1 basiert . Haben einige Tests durchgeführt, zögern Sie nicht, Feedback zu geben.

Testet auf MSVC.

PS: Ich hasse es, woanders nach zusätzlichen Dingen zu suchen, deshalb habe ich die CRC-Tabelle am Ende meiner Antwort kopiert.

#include <inttypes.h>

namespace detail
{
    // CRC32 Table (zlib polynomial)
    static constexpr uint32_t crc_table[256] =
    {
        0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
        ...
    };

    constexpr uint32_t combine_crc32( const char c, uint32_t part )
    {
        return (part >> 8) ^ crc_table[(part ^ c) & 0x000000FF];
    }

    constexpr uint32_t crc32( const char * str, size_t idx )
    {
        return combine_crc32( str[idx], idx ? crc32( str, idx - 1 ) : 0xFFFFFFFF );
    }
} //namespace detail

constexpr uint32_t ctcrc32( const char* str, size_t len )
{
    return detail::crc32( str, len ) ^ 0xFFFFFFFF;
}

size_t constexpr operator "" _hash( const char* str, size_t len )
{
    return ctcrc32( str, len );
}

Alternative mit Algorithmus von Dan Bernstein (djb2) (kombinierte Antworten von Jerry Coffin + Georg Fritzsche )

unsigned constexpr const_hash( char const *input )
{
    return *input ?
        static_cast<unsigned int>(*input) + 33 * const_hash( input + 1 ) :
        5381;
}
size_t constexpr operator "" _hash( const char* str, size_t len )
{
    return const_hash( str );
}

Crc32-Tabelle:

static constexpr uint32_t crc_table[256] =
    {
        0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
        0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
        0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
        0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
        0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
        0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
        0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
        0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
        0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
        0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
        0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
        0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
        0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
        0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
        0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
        0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
        0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
        0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
        0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
        0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
        0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
        0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
        0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
        0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
        0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
        0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
        0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
        0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
        0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
        0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
        0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
        0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
        0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
        0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
        0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
        0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
        0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
        0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
        0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
        0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
        0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
        0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
        0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
        0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
        0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
        0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
        0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
        0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
        0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
        0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
        0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
        0x2d02ef8dL
    };
Zacharias
quelle