c++ - 在编译时使用 CRC32 算法对字符串进行哈希处理

Question

基本上我希望我的代码能够做到这一点:

 Engine.getById(WSID('some-id'));

哪个应该被改造

 Engine.getById('1a61bc96');

就在被编译成 asm 之前。所以在编译时。

这是我的尝试

constexpr int WSID(const char* str) {
    boost::crc_32_type result;
    result.process_bytes(str,sizeof(str));
    return result.checksum();
}

但我在尝试使用 MSVC 18(CTP 2013 年 11 月)编译时得到了这个

error C3249: illegal statement or sub-expression for 'constexpr' function

我怎样才能得到 WSID 函数，使用这种方式或任何方式，只要它是在编译期间完成的？

试过这个:Compile time string hashing

 warning C4592: 'crc32': 'constexpr' call evaluation failed; function will be called at run-time

编辑:

我在 Jason Gregory 的 Game Engine Architecture 中第一次听说这种技术。我联系了作者，他很乐意回答我这个问题:

What we do is to pass our source code through a custom little pre-processor that searches for text of the form SID('xxxxxx') and converts whatever is between the single quotes into its hashed equivalent as a hex literal (0xNNNNNNNN). [...]

You could conceivably do it via a macro and/or some template metaprogramming, too, although as you say it's tricky to get the compiler to do this kind of work for you. It's not impossible, but writing a custom tool is easier and much more flexible. [...]

Note also that we chose single quotes for SID('xxxx') literals. This was done so that we'd get some reasonable syntax highlighting in our code editors, yet if something went wrong and some un-preprocessed code ever made it thru to the compiler, it would throw a syntax error because single quotes are normally reserved for single-character literals.

Note also that it's crucial to have your little pre-processing tool cache the strings in a database of some sort, so that the original strings can be looked up given the hash code. When you are debugging your code and you inspect a StringId variable, the debugger will normally show you the rather unintelligible hash code. But with a SID database, you can write a plug-in that converts these hash codes back to their string equivalents. That way, you'll see SID('foo') in your watch window, not 0x75AE3080 [...]. Also, the game should be able to load this same database, so that it can print strings instead of hex hash codes on the screen for debugging purposes [...].

但是虽然预处理有一些主要优点，但这意味着我必须准备某种修改文件的输出系统(那些将存储在其他地方，然后我们需要告诉 MSVC)。所以它可能会使编译任务复杂化。有没有办法用 python 预处理文件而不用头疼？但这不是问题，我仍然对使用编译时函数感兴趣(关于缓存我可以使用 ID 索引)

Answer 1

这是一个完全在编译时工作的解决方案，但也可以在运行时使用。它是 constexpr、模板和宏的混合体。您可能需要更改一些名称或将它们放在单独的文件中，因为它们很短。

请注意，我重用了 this answer for the CRC table generation 中的代码我基于 this page 的代码用于实现。

我没有在 MSVC 上测试它，因为我目前没有在我的 Windows VM 中安装它，但我相信它应该可以工作，或者至少可以进行一些细微的更改。

这里是代码，你可以直接使用crc32函数，也可以使用更符合你的问题的WSID函数:

#include <cstring>
#include <cstdint>
#include <iostream>

// Generate CRC lookup table
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};};

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

constexpr unsigned crc_table[] = { A(0) };

// Constexpr implementation and helpers
constexpr uint32_t crc32_impl(const uint8_t* p, size_t len, uint32_t crc) {
    return len ?
            crc32_impl(p+1,len-1,(crc>>8)^crc_table[(crc&0xFF)^*p])
            : crc;
}

constexpr uint32_t crc32(const uint8_t* data, size_t length) {
    return ~crc32_impl(data, length, ~0);
}

constexpr size_t strlen_c(const char* str) {
    return *str ? 1+strlen_c(str+1) : 0;
}

constexpr int WSID(const char* str) {
    return crc32((uint8_t*)str, strlen_c(str));
}

// Example usage
using namespace std;

int main() {
    cout << "The CRC32 is: " << hex << WSID("some-id") << endl;
}

第一部分负责生成常量表，而 crc32_impl 是标准的 CRC32 实现，转换为与 C++11 constexpr 一起使用的递归样式。 那么 crc32 和 WSID 只是为了方便起见的简单包装器。