Compile time string hashing

小开

Note that the form shown here wasn't accepted into the standard, as noted below.

通过 N2765中提出的 用户定义的文字可以实现编译时间串处理。
As i already mentioned, i don't know of any compiler that currently implements it and without compiler support there can be only guess work.

在草稿的2.13.7.3和4中，我们有以下内容:

否则(S 包含一个文本操作符模板) ，L 被视为表单的调用
操作符“”X < ‘ c1’，‘ c2’，... ，‘ ck’> () 其中 n 是源字符序列 c1c2... ck。[注意: 序列 c1c2... ck 可以只包含基本源字符集中的字符

结合 constexpr，我们应该有编译时字符串处理。

Update: i 忽略了我读错了段落，这个表单允许使用用户定义的整数字面值和浮点字面值，但显然不允许使用字符串字面值(2.13.7.5)。
这部分建议似乎没有被接受

That being said, with my limited glimpse at C++0x, it 也许吧 look something like this (i most likely got something wrong):

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;

如果 Jerrys approach工作，那么以下应该工作，但是:

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

小开

At least by my reading of §7.1.5/3 and §5.19, the following might be legitimate:

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

这似乎符合7.1.5/3的基本规则:

形式是: “返回表达式;

Its only parameter is a pointer, which is a scalar type, and therefore a literal type.

它的返回值是无符号整型，也是标量(因此是文字)。

没有对返回类型的隐式转换。

有一些问题是 *input是否涉及一个非法的左值到右值的转换，我不确定我对5.19/2/6/2¹和4.1中的规则有足够的了解来确定这一点。

从实用的角度来看，这段代码被 g + + 所接受(举个例子) ，至少可以追溯到 g + + 4.7.1。

用法是这样的:

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

为了符合5.19/2/6/2的要求，你可能不得不这样做:

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

我使用额外的“斜杠”数字来表示无数的项目符号点，所以这是第二个项目符号点，如果第六个项目符号点在5.19/2以下。我想我可能要和皮特 · 贝克谈谈是否有可能把一些数字/字母/罗马数字按层次顺序加起来，以识别这样的碎片..。

小开

以下内容适用于 GCC 4.6.1，您可以在开关块中使用 hash或 pack。

/* 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 seemingly(?) does not allow recursive calls where we pass on s+1 with s a pointer, which is why I use the off variable.

小开

最佳答案

这有点晚了，但是我使用 constexpr成功地实现了一个编译时 CRC32函数。它的问题在于，在编写本文时，它只能与 GCC 一起工作，而不能与 MSVC 或 Intel 编译器一起工作。

下面是代码片段:

// 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等于0x335CC04A

希望这个对你有帮助！

小开

这个代码片段基于 Clement JACOB 的。但是对于叮当声也有效。而且它在编译时应该更快(它只有一个递归调用，而不是像原始 post 那样有两个递归调用)。

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

见概念证明给你

小开

这是一种尽可能准确地解决 OP 问题的尝试。

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

活生生的例子。

注意主要的区别—— std::hash不能使用，因为我们不能控制 std::hash的算法，而且我们 必须的将它重新实现为 constexpr，以便在编译时对它进行评估。此外，在 std中没有“透明”散列，因此您不能(不创建 std::string)将原始字符缓冲区散列为 std::string。

I stuck the std::string custom hasher (with transparent const char* support) into a my_hash namespace, so you can store it in a std::unordered_map if you need consistency.

基于@JerryCoffin 的出色回答和下面的评论，但是尝试用当前的 C + + 11最佳实践(而不是期望它们!)来编写它.

注意，对 switch语句 case使用“原始散列”是危险的。你会想做一个 ==比较后，以确认它的工作。

小开

另一个基于 Clement JACOB 的解决方案，使用 C + + 11 Constexpr (不是扩展的 C + + 14) ，但只有一个递归。

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

一些解释

我们使用一个递归，这样即使对于较长的字符串，函数也能很好地工作。

额外的函数 combine_crc32允许我们将递归结果存储在一个变量 part下并使用两次。这个函数是 C + + 11限制不允许局部变量声明的一个演练。

ctcrc32函数需要一个字符串文字，该字符串文字作为 const char (&)[len]传递。通过这种方式，我们可以获得字符串长度作为模板参数，而不必依赖于宏。

小开

问得好。

Based on Jerry Coffin's answer, I've created another one that's compatible with Visual Studio 2017's std::hash.

#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

小开

下面是另一个 C + + 11实现(基于天鹅座 X1的答案) ，它可以同时使用 constexpr char数组和运行时 string:

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 N> constexpr uint32_t ctcrc32(const char (&str)[N]) { return detail::crc32(N - 2, str) ^ 0xFFFFFFFF; }

在第一个重载中需要 str.size() + 1，因为第二个重载中的 N是数组的大小，包括空终止字符(std::string::size没有考虑到这一点)。

我没有为 const char *添加重载，因为它扰乱了第二个重载ーー您可以很容易地为 const char *, size_t或 std::string_view添加重载。

小开

我仍然缺少 crc32-Literal 变体(模板是不可能的) ，所以这里是我基于天鹅座 X1的建议。做了一些测试，随时给予反馈。

在 MSVC 上测试。

PS: I hate searching for additional stuff somewhere else, so i copied the CRC table on the bottom of my answer.

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

与丹伯恩斯坦(djb2)的算法替代(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表:

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

小开

如果你有一个 c + + 17编译器和 string _ view，这就变得无关紧要了，只需要写一个普通的版本:

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

小开

基于 Jerry Coffin 的方法和 Georg Fritzsche 的方法

我使用了以下代码而没有使用 constexpr auto const_tmp = NGX_EM_HASH("authorization");:

template <size_t N> constexpr size_t string_literal_length(const char(&str)[N]) { return N - 1; } // https://stackoverflow.com/questions/2111667/compile-time-string-hashing/66690839#66690839 // "cookie"_hash = ngx_hash(ngx_hash(ngx_hash(ngx_hash(ngx_hash('c', 'o'), 'o'), 'k'), 'i'), 'e'); // See also `ngx_uint_t ngx_hash_key(u_char *data, size_t len)` in nginx\src\core\ngx_hash.c #if 0 template<ngx_uint_t sum, char ch, char... str> struct ngx_em_hasher { static const ngx_uint_t result = ngx_em_hasher<ngx_hash(sum, u_char(ch)), str...>::result; }; template<ngx_uint_t sum, char ch> struct ngx_em_hasher { static const ngx_uint_t result = ngx_hash(sum, u_char(ch)); }; template<char... str> constexpr ngx_uint_t operator "" _hash() { return ngx_em_hasher<0, str>::result; } // update: probably wrong, because the above form is not allowed for string-literals: // const unsigned h = "abcd"_hash; #elif defined(_MSC_VER2) // reducer function: the previous calculation result must be passed to the next iteration static constexpr ngx_uint_t ngx_em_hash(const char* const psz, ngx_uint_t sum = 0) { return *psz ? ngx_em_hash(psz + 1, ngx_hash(sum, u_char(*psz))) : sum; } constexpr ngx_uint_t operator "" _hash(const char* s, size_t) { return ngx_em_hash(s); } // #define NGX_EM_HASH(str) ngx_em_hash(str) #define NGX_EM_X(x) x // constexpr auto const_hash = NGX_EM_HASH("authorization"); // hdr->hash = const_hash; #define NGX_EM_HASH(string_literals) ngx_em_const<NGX_EM_X(string_literals)_hash>::value #else template<size_t idx> constexpr ngx_uint_t ngx_em_hash(const char* const psz, ngx_uint_t sum = 0) { return ngx_em_hash<idx - 1>(psz + 1, ngx_hash(sum, u_char(*psz))); } // This is the stop-recursion function template<> constexpr ngx_uint_t ngx_em_hash<0>(const char* const psz, ngx_uint_t sum) { return sum; } // This doesn't take into account the nul char. #define COMPILE_TIME_NGX_HASH(x) ngx_em_hash<sizeof(x) - 1>(x) // Regardless of what Optimize Options of the compiler? // https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html // https://learn.microsoft.com/en-us/cpp/build/reference/o-options-optimize-code?view=msvc-160 #define NGX_EM_HASH(x) ngx_em_const<ngx_em_hash<sizeof(x) - 1>(x)>::value #endif void snippet(ngx_table_elt_t *hdr) { ngx_str_set(&hdr->key, "Authorization"); hdr->lowcase_key = (u_char *) "authorization"; //constexpr auto const_tmp = NGX_EM_HASH("authorization"); //hdr->hash = const_tmp; hdr->hash = NGX_EM_HASH("authorization"); sr->headers_in.authorization = hdr; }

然后它的反汇编结果如下(使用 VS2017 v15.9.27) :

;hdr->hash = NGX_EM_HASH("authorization"); 00007FFD36B8B7DE mov rax,qword ptr [rbp+4D8h] 00007FFD36B8B7E5 mov rcx,4EEC63AFAD69E079h ; Decimal=5687030035641917561 __int64 00007FFD36B8B7EF mov qword ptr [rax],rcx

但是，如果使用 #define NGX_EM_HASH(string_literals) NGX_EM_X(string_literals)_hash，它的拆卸结果是这样的:

;hdr->hash = NGX_EM_HASH("authorization"); 00007FFD337FFE93 lea rcx,[string "authorization" (07FFD33885ED0h)] 00007FFD337FFE9A call operator "" _hash (07FFD336B78ECh) 00007FFD337FFE9F mov rcx,qword ptr [rbp+4D8h] 00007FFD337FFEA6 mov qword ptr [rcx],rax

Online

Compiler Explorer 使用 VC + + 和 GCC 的反汇编输出(从 Web 浏览器交互式地运行编译器并与程序集交互)

Ngx _ hash@OnlineGDB beta (c/c + + 的在线编译器和调试器)