使用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只要在编译期间完成,我怎样才能以这种方式或任何方式获得该函数？

试过这个:编译时间字符串哈希

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

编辑:

我第一次在Jason Gregory的游戏引擎架构中听说过这种技术.我联系了那位有意回答我的作者:

我们所做的是通过一个自定义的小预处理器传递我们的源代码,该预处理器搜索表单的文本SID('xxxxxx')并将单引号之间的任何内容转换为其哈希等效项作为十六进制文字(0xNNNNNNNN).[...]

你可以想象通过宏和/或一些模板元编程也可以做到这一点,尽管如你所说让编译器为你做这种工作是很棘手的.这并非不可能,但编写自定义工具更容易,也更灵活.[...]

另请注意,我们为SID('xxxx')文字选择单引号.这样做是为了让我们在代码编辑器中得到一些合理的语法突出显示,但是如果出现问题并且一些未预处理的代码通过编译器,它会引发语法错误,因为单引号通常是保留的单字符文字.

另请注意,让您的小预处理工具将字符串缓存到某种类型的数据库中是至关重要的,这样可以在给定哈希码的情况下查找原始字符串.当您调试代码并检查StringId变量时,调试器通常会向您显示相当难以理解的哈希代码.但是使用SID数据库,您可以编写一个插件,将这些哈希代码转换回其字符串等效项.这样,你会在你的观察窗口看到SID('foo'),而不是0x75AE3080[...].此外,游戏应该能够加载这个相同的数据库,以便它可以在屏幕上打印字符串而不是十六进制哈希码用于调试目的[...].

但是虽然预处理有一些主要优点,但这意味着我必须准备一些修改文件的输出系统(那些将存储在别处,然后我们需要告诉MSVC).因此,它可能会使编译任务复杂化.有没有办法用python预处理文件,例如没有头痛？但这不是问题,我仍然对使用编译时功能感兴趣(关于缓存我可以使用ID索引)

Answer 1

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

请注意,我重复使用了这个答案中的代码来生成CRC表,并且我自己从这个页面的代码开始实现.

我没有在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只是简单的包装为方便起见.