Haszowanie ciągów czasu kompilacji

100

W kilku różnych miejscach przeczytałem, że przy użyciu nowych literałów ciągów C ++ 11 może być możliwe obliczenie skrótu ciągu w czasie kompilacji. Jednak nikt nie wydaje się być gotowy, aby wyjść i powiedzieć, że będzie to możliwe i jak to się stanie.

  • czy to możliwe?
  • Jak wyglądałby operator?

Jestem szczególnie zainteresowany takimi przypadkami użycia.

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

Uwaga: funkcja skrótu czasu kompilacji nie musi wyglądać dokładnie tak, jak ją napisałem. Zrobiłem wszystko, co w mojej mocy, aby odgadnąć, jak będzie wyglądało ostateczne rozwiązanie, ale meta_hash<"string"_meta>::valuemogło też być rozwiązaniem wykonalnym.

deft_code
źródło
Wydaje się, że nie mogę też niczego znaleźć, ale widziałem, że muszę wymusić funkcję haszującą w constexpr.
Łukasz
4
Czy istnieje kompilator, który już obsługuje literały zdefiniowane przez użytkownika? Gcc tego nie robi ( gcc.gnu.org/projects/cxx0x.html ) i nie znalazłem też wzmianki o nich dla VC10. Bez obsługi kompilatora może to być tylko zgadywanie, ale szablony zdefiniowane przez użytkownika literały wyglądają tak, jakby to było możliwe.
Georg Fritzsche
1
To słodkie, ale nieprzydatne? Jeśli wartość przełącznika jest ciągiem czasu wykonywania, należy również sprawdzić, czy nie występują kolizje. Może pakowanie jest lepsze (moja odpowiedź ma funkcję paczki do upychania 9 znaków w 64 bity).
u0b34a0f6ae
@ u0b34a0f6ae Po co sprawdzać kolizje?
cubuspl42
Kompilator powinien zgłosić błąd, jeśli dwie wartości wielkości liter są równe.
Mark Storer

Odpowiedzi:

88

To trochę za późno, ale udało mi się zaimplementować funkcję CRC32 w czasie kompilacji przy użyciu constexpr. Problem polega na tym, że w chwili pisania tego tekstu działa tylko z GCC, a nie z kompilatorem MSVC ani Intel.

Oto fragment kodu:

// 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 jest równe 0x335CC04A

Mam nadzieję, że to ci pomoże!

Clement JACOB
źródło
4
Tak, absolutnie. Przetestowałem to z algorytmem wykonawczym Pythona CRC32 (pochodzącym z zlib) i wyniki są takie same. W rzeczywistości to, co próbujesz osiągnąć, jest dokładnie powodem, dla którego używam tej techniki!
Clement JACOB
2
Dzięki za opublikowanie tego, jest to bardzo przydatne!
Tamás Szelei
2
Brakowało flagi kompilacji. Ponadto musiałem rzutować na size_t wartość -1 w funkcji szablonu zatrzymania rekursji. Zaktualizowana wersja jest dostępna tutaj (działa z Clang 3.3): goo.gl/vPMkfB
Clement JACOB
1
constexprnie jest dostępny w VS2013, z wyjątkiem listopada 2013 CTP blogs.msdn.com/b/vcblog/archive/2013/11/18/ ...
2
Powtarzasz się dwukrotnie. To rozwiązanie ma wykładniczą złożoność w odniesieniu do długości łańcucha, a kompilator nie jest wystarczająco sprytny, aby wyeliminować drugie wywołanie. Sprawdź inne odpowiedzi, aby znaleźć możliwe rozwiązanie tego problemu.
CygnusX1
30

Przynajmniej po przeczytaniu przeze mnie § 7.1.5 / 3 i §5.19, poniższe mogą być uzasadnione:

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

Wydaje się, że jest to zgodne z podstawowymi zasadami w §7.1.5 / 3:

  1. Formularz to: "wyrażenie zwrotu;"
  2. Jego jedynym parametrem jest wskaźnik, który jest typem skalarnym, a zatem typem dosłownym.
  3. Jej zwrot to unsigned int, który jest również skalarny (a zatem dosłowny).
  4. Nie ma niejawnej konwersji na typ zwracany.

Pojawia się pytanie, czy *inputs wiążą się z niedozwoloną konwersją lwartości na rwartość, i nie jestem pewien, czy rozumiem reguły w §5.19 / 2/6/2 1 i § 4.1 na tyle dobrze, aby być tego pewnym.

Z praktycznego punktu widzenia ten kod jest akceptowany przez (na przykład) g ++, przynajmniej od g ++ 4.7.1.

Użycie byłoby takie jak:

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

Aby spełnić wymagania §5.19 / 2/6/2, może być konieczne wykonanie czegoś takiego:

// 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. Używam dodatkowych „ukośników”, aby odnieść się do nienumerowanych punktorów, więc jest to drugi punkt w środku, jeśli szósty punktor zgodnie z §5.19 / 2. Myślę, że być może będę musiał porozmawiać z Pete'em Beckerem o tym, czy można dodać jakieś cyfry / litery / cyfry rzymskie w dół hierarchii, aby zidentyfikować takie elementy ...
Jerry Coffin
źródło
3
Dwie rzeczy są nie tak. 1: Wywołania rekurencyjne są niedozwolone constexpr, 2: Nie masz warunku zatrzymania (gdzie *input == nullptr) i jak rozumiem constexpr, nie możesz go mieć.
Motti
9
Gdzie jest napisane, że rekursja nie jest dozwolona w constexpr? O ile widzę, mówi tylko, że wszystkie wywoływane funkcje muszą być oznaczone jako constexprt (§5.19 / 2/2). Popełniłem błąd w warunku zakończenia, który teraz naprawiłem (przypadkowo użyłem || tam, gdzie powinno być &&).
Jerry Coffin
3
rekurencyjne constexpr. Przeczytałem kilka protokołów ze spotkań z 2008 roku. Dyskutowano o dopuszczaniu lub niedozwoleniu rekurencyjnych funkcji constexpr. Istotą było to, że obecne sformułowanie tego nie zabraniało i lekko to sugerowało. Komisja uznała, że ​​taka potężna funkcja powinna zostać wyraźnie określona. To było w 2008 roku, nie wiem, co się stało od tamtego czasu.
deft_code
3
Racja - prawdopodobnie powinienem był wskazać, że jadę z N3000, który (jak sądzę) jest obecnie najnowszym projektem. Jestem prawie pewien, że kiedyś było to zabronione, ale przynajmniej na razie wydaje się, że jest to dozwolone.
Jerry Coffin
2
Hm, operator && zwraca wartość bool, więc ta funkcja prawdopodobnie nie robi tego, co chcesz. W szczególności zwraca 0 dla dowolnego pustego ciągu i prawdopodobnie niektórych innych ciągów zaczynających się od znaku, który jest konwertowany na, (unsigned)-1jeśli taki istnieje; i zwraca 1 dla wszystkich innych ciągów. Przepisać za pomocą trójargumentowego operatora warunkowego?
ndkrempel
13

Jest to próba jak najdokładniejszego rozwiązania problemu PO.

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

przykład na żywo .

Uwaga główną różnicę - std::hashnie może być stosowany, jako że nie mamy kontroli nad std::hashalgorytmem „s, a my musi reimplement go jako constexprw celu ocenienia go w czasie kompilacji. Ponadto, nie ma "przezroczystych" hashów std, więc nie możesz (bez tworzenia std::string) hashować surowego bufora znaków jako pliku std::string.

Wsadziłem do std::stringniestandardowego hasher (z przezroczystego const char*wsparcia) do my_hashnazw, dzięki czemu można przechowywać go w std::unordered_mapjeśli trzeba konsystencję.

Oparty na doskonałej odpowiedzi @ JerryCoffin i wątku komentarzy pod nią, ale z próbą napisania go z aktualnymi najlepszymi praktykami C ++ 11 (w przeciwieństwie do przewidywania ich!).

Zwróć uwagę, że użycie „surowego skrótu” w switchinstrukcji casejest niebezpieczne. Będziesz chciał ==później przeprowadzić porównanie, aby potwierdzić, że zadziałało.

Yakk - Adam Nevraumont
źródło
2
Wydaje się, że link do przykładu na żywo jest nieprawidłowy / nieaktualny?
fuenfundachtzig
@fuenfundachtzig Czy uwierzysz, że właśnie to naprawiłem?
Yakk - Adam Nevraumont
13

Ten fragment oparty na fragmencie Clement JACOB. Ale działa też z brzękiem. I powinien być szybszy na kompilacji (ma tylko jedno wywołanie rekurencyjne, a nie dwa jak w oryginalnym poście).

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

Zobacz dowód słuszności koncepcji tutaj

wieża120
źródło
1
Dziękuję, odpowiedź Jacoba działa dobrze na to, co chciałem w GCC, ale msvc wyrzucał błędy z większymi ciągami. Twoja odpowiedź działa na msvc z większymi ciągami, które muszę haszować.
Daniel Moodie,
8

Zwróć uwagę, że przedstawiony tutaj formularz nie został przyjęty do standardu, jak wspomniano poniżej.

Zakłada się, że przetwarzanie ciągu znaków czasu kompilacji stanie się możliwe dzięki literałom zdefiniowanym przez użytkownika, zaproponowanym w N2765 .
Jak już wspomniałem, nie znam żadnego kompilatora, który obecnie go implementuje, a bez wsparcia kompilatora można tylko zgadywać.

W §2.13.7.3 i 4 projektu mamy:

W przeciwnym razie (S zawiera szablon operatora literału), L jest traktowane jako wywołanie
operatora formularza "" X <'c1', 'c2', ..., 'ck'> (), gdzie n jest sekwencją znaków źródłowych c1c2 ... ck. [Uwaga: sekwencja c1c2 ... ck może zawierać tylko znaki z podstawowego zestawu znaków źródłowych. —End note]

Połącz to z constexpri powinniśmy mieć przetwarzanie ciągu czasu kompilacji.

aktualizacja: przeoczyłem, że czytałem niewłaściwy akapit, ta forma jest dozwolona dla literałów całkowitych zdefiniowanych przez użytkownika i literałów zmiennoprzecinkowych, ale najwyraźniej nie dla literałów -string (§ 2.13.7.5).
Wydaje się, że ta część wniosku nie została przyjęta.

Biorąc to pod uwagę, z moim ograniczonym spojrzeniem na C ++ 0x, może to wyglądać mniej więcej tak (najprawdopodobniej coś mi się nie udało):

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;

Jeśli podejście Jerrysa działa, to jednak powinny działać:

constexpr unsigned operator "" _hash(const char* s, size_t) {
    return const_hash(s);
}
Georg Fritzsche
źródło
Ładne (i konieczne) połączenie szablonów o zmiennej długości i constexprliterału zdefiniowanego przez użytkownika. Nie jestem pewien, czy można użyć literału ciągu jako parametru szablonu, czy nie mają one statycznego powiązania? (robią co najmniej w C ++ 98 i dlatego są verboten jako parametry szablonu).
Motti
Pomieszałem akapity i pomyślałem, że ten przypadek był wyjątkiem - niestety tak nie jest.
Georg Fritzsche,
1
@Motti: gdzie gf używa literału ciągu jako parametru szablonu? Czy mylisz się przekazywanie wariadycznego szablonu znaków jako literału ciągu?
deft_code
Wygląda na to, że z pierwotnej propozycji wersja szablonu dla literałów ciągów nie została zaakceptowana (z powodu problemów z konkatenacją? Stackoverflow.com/questions/1108008/any-ideas-for-c1y/ ... - komentarze) - szkoda.
Georg Fritzsche
1
Ostatnia wersja operator ""_hashdziała dla mnie w Xcode 5.0.2.
cubuspl42
8

Inne rozwiązanie oparte na rozwiązaniu Clementa JACOBa, wykorzystujące C ++ 11 constexpr (nie rozszerzony C ++ 14), ale mające tylko jedną rekursję.

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

Jakieś wyjaśnienie

  • Używamy pojedynczej rekurencji, więc funkcja działa dobrze nawet dla dłuższych ciągów.
  • Ta dodatkowa funkcja combine_crc32pozwala nam przechowywać wynik rekursji pod zmienną parti używać jej dwukrotnie. Ta funkcja jest obejściem ograniczenia C ++ 11, które nie zezwala na deklaracje zmiennych lokalnych.
  • ctcrc32Funkcja oczekuje ciągiem znaków, który jest przekazywany jako const char (&)[len]. W ten sposób możemy pobrać długość łańcucha jako parametr szablonu i nie musimy polegać na makrach.
CygnusX1
źródło
2
Dziękuję, to moja ulubiona implementacja.
Daniel Moodie,
6

Następujące prace w GCC 4.6.1 i można użyć jednej hashlub packw blokach rozdzielczych.

/* 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 pozornie (?) Nie pozwala wywołań cyklicznych gdzie przechodzimy s+1ze swskaźnikiem, dlatego używam offzmienną.

u0b34a0f6ae
źródło
5

Jeśli masz kompilator C ++ 17 i string_view, staje się to trywialne, po prostu napisz normalną wersję:

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
źródło
Zauważ, że kompilator może zdecydować, że nie będzie przetwarzać tego w czasie kompilacji, jeśli po prostu napiszesz crc32("mystring")(zwykle VS to robi). Sztuczka pozwalająca obejść ten problem polega na utworzeniu zmiennej constexpr, która zależy od oceny czasu kompilacji twojego crc32. Zazwyczajconstexpr uint32_t val = crc32("mystring");
Guillaume Gris
3

Oto kolejna implementacja C ++ 11 (oparta na odpowiedzi @ CygnusX1), która działa zarówno z tablicami constexpr char, jak i ciągami uruchomieniowymi:

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

Potrzebujesz, str.size() + 1ponieważ lenw drugim przeciążenie jest strlen(str) + 1spowodowane znakiem null na końcu.

Nie dodałem przeciążenia for, const char *ponieważ miesza się z drugim przeciążeniem - możesz łatwo dodać przeciążenia dla const char *, size_tlub std::string_view.

Holt
źródło
2

To miłe pytanie.

Na podstawie odpowiedzi Jerry'ego Coffina stworzyłem kolejny, który jest zgodny ze std :: hash programu Visual Studio 2017.

#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
źródło
0

Wciąż brakowało mi wariantu dosłownego crc32 (co nie jest możliwe w przypadku szablonów), więc oto moja sugestia oparta na CygnusX1 . Zrobiłem jakieś testy, nie wahaj się przekazać opinii.

Testet na MSVC.

PS: Nienawidzę szukać dodatkowych rzeczy gdzie indziej, więc skopiowałem tabelę CRC na dole mojej odpowiedzi.

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

Alternatywa z algorytmem Dana Bernsteina (djb2) (połączone odpowiedzi od Jerry'ego Coffina + Georga Fritzsche'a )

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

Stół CRC32:

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
źródło