使用CRC32算法在编译时对字符串进行哈希

Question

使用CRC32算法在编译时对字符串进行哈希

c++c++11visual-studio-2012constexprcompile-time

14

基本上我想在我的代码中能够做到这一点：

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

应该由什么来转换

 Engine.getById('1a61bc96');

就在汇编之前被编译。所以在编译时。

这是我的尝试

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

但是我在尝试使用MSVC 18（CTP November 2013）编译时遇到了这个问题

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索引）。

- Vinz243

2

请在此处查看答案：https://dev59.com/UHA75IYBdhLWcg3wkJ71 - Nim

另外，我们讨论的是字符串吗？还是你想要多个字符常量？ - Columbo

3

几年前有一个 Code Golf 是为了完成这个任务。 http://codegolf.stackexchange.com/questions/3268/compute-the-crc32-table-at-compile-time - Moby Disk

@MobyDisk 但这只给我表格，那么如何对字符串进行哈希处理呢？ - Vinz243

1

第一个错误信息“'constexpr'不允许的类型”是错误或误导性的：std::string const＆是一个字面类型（因为它是一个引用），因此可以作为constexpr函数的函数参数类型。clang++和g++也接受它（在C++11模式下）。 - dyp

显示剩余5条评论

3个回答

4

如果有人感兴趣，我编写了一个使用C++14风格的constexpr函数生成CRC-32表和代码的函数。结果是，在我看来，比我在互联网上看到的许多尝试都更易于维护，并且它远离了预处理器。

现在，它使用了一个名为cexp::array的自定义std::array“克隆”，因为G++似乎没有将constexpr关键字添加到它们的非const引用索引访问/写入运算符中。

然而，它非常轻量级，并且希望这个关键字会在不久的将来被添加到std::array中。但是现在，非常简单的数组实现如下：

namespace cexp
{

    // Small implementation of std::array, needed until constexpr
    // is added to the function 'reference operator[](size_type)'
    template <typename T, std::size_t N>
    struct array {
        T m_data[N];

        using value_type = T;
        using reference = value_type &;
        using const_reference = const value_type &;
        using size_type = std::size_t;

        // This is NOT constexpr in std::array until C++17
        constexpr reference operator[](size_type i) noexcept {
            return m_data[i];
        }

        constexpr const_reference operator[](size_type i) const noexcept {
            return m_data[i];
        }

        constexpr size_type size() const noexcept {
            return N;
        }
    };

}

现在，我们需要生成CRC-32表格。我基于一些Hacker's Delight代码编写了算法，它可能可以扩展支持许多其他CRC算法。但遗憾的是，我只需要标准实现，所以这里是：

// Generates CRC-32 table, algorithm based from this link:
// http://www.hackersdelight.org/hdcodetxt/crc.c.txt
constexpr auto gen_crc32_table() {
    constexpr auto num_bytes = 256;
    constexpr auto num_iterations = 8;
    constexpr auto polynomial = 0xEDB88320;

    auto crc32_table = cexp::array<uint32_t, num_bytes>{};

    for (auto byte = 0u; byte < num_bytes; ++byte) {
        auto crc = byte;

        for (auto i = 0; i < num_iterations; ++i) {
            auto mask = -(crc & 1);
            crc = (crc >> 1) ^ (polynomial & mask);
        }

        crc32_table[byte] = crc;
    }

    return crc32_table;
}

接下来，我们将表格存储在全局变量中，并对其进行基本的静态检查。这些检查很可能可以改进，并且没有必要将其存储在全局变量中。

// Stores CRC-32 table and softly validates it.
static constexpr auto crc32_table = gen_crc32_table();
static_assert(
    crc32_table.size() == 256 &&
    crc32_table[1] == 0x77073096 &&
    crc32_table[255] == 0x2D02EF8D,
    "gen_crc32_table generated unexpected result."
);

现在表格已经生成，是时候生成CRC-32代码了。我再次基于Hacker's Delight链接编写了算法，目前它仅支持从C字符串输入。

// Generates CRC-32 code from null-terminated, c-string,
// algorithm based from this link:
// http://www.hackersdelight.org/hdcodetxt/crc.c.txt 
constexpr auto crc32(const char *in) {
    auto crc = 0xFFFFFFFFu;

    for (auto i = 0u; auto c = in[i]; ++i) {
        crc = crc32_table[(crc ^ c) & 0xFF] ^ (crc >> 8);
    }

    return ~crc;
}

为了完整起见，我生成了一个CRC-32代码，并静态检查它是否具有预期的输出，然后将其打印到输出流中。

int main() {
    constexpr auto crc_code = crc32("some-id");
    static_assert(crc_code == 0x1A61BC96, "crc32 generated unexpected result.");

    std::cout << std::hex << crc_code << std::endl;
}

希望这能帮助其他想要在编译时生成CRC-32的人，甚至是一般情况下。

- Deus Sum

1

@tux3的回答很不错！但是很难维护，因为你基本上是在预处理器命令中编写自己的CRC32实现。

另一种解决问题的方法是首先回到了解需求的需要。如果我理解正确，关注点似乎是性能。在这种情况下，可以在程序加载时调用函数的第二个时间点而不会影响性能。在这种情况下，您将访问全局变量而不是传递常量。就性能而言，在初始化后，两者应该是相同的（常量从代码中获取32位，全局变量从常规内存位置获取32位）。

你可以像这样做：

static int myWSID = 0;

// don't call this directly
static int WSID(const char* str) {
  boost::crc_32_type result;
  result.process_bytes(str,sizeof(str));
  return result.checksum();
}

// Put this early into your program into the
// initialization code.
...
myWSID = WSID('some-id');

根据您的整体程序，您可能需要一个内联访问器来检索值。如果可以接受轻微的性能影响，您也可以像这样编写函数，基本上使用单例模式。

// don't call this directly
int WSID(const char* str) {
  boost::crc_32_type result;
  result.process_bytes(str,sizeof(str));
  return result.checksum();
}

// call this instead. Note the hard-coded ID string.
// Create one such function for each ID you need to
// have available.
static int myWSID() {
   // Note: not thread safe!
   static int computedId = 0;
   if (computedId == 0)
      computedId = WSID('some-id');
   return computedId;
}

当然，如果要求编译时评估的原因不同（例如，不希望some-id出现在编译后的代码中），这些技术将无济于事。

另一个选择是使用Jason Gregory提出的自定义预处理器。如果您将所有IDS收集到单独的文件中，则可以相当干净地完成此操作。该文件不需要具有C语法。我会给它一个扩展名，例如.wsid。自定义预处理器从中生成一个.H文件。

以下是其示例：

idcollection.wsid（自定义预处理器之前）：

some_id1
some_id2
some_id3

您的预处理器将生成以下idcollection.h文件：

#define WSID_some_id1 0xabcdef12
#define WSID_some_id2 0xbcdef123
#define WSID_some_id3 0xcdef1234

在你的代码中，你会调用：

。

Engine.getById(WSID_some_id1);

以下是一些注意事项：

这假设所有原始ID都可以转换为有效的标识符。如果它们包含特殊字符，则您的预处理器可能需要进行其他操作。
我注意到您原始问题中存在不匹配。您的函数返回一个int，但Engine.getById似乎接受一个字符串。我的建议代码将始终使用int（如果您想始终使用字符串，则很容易更改）。

- Kevin Keane

1

这应该是一条评论。你正在粘贴我的代码，这并没有直接回答问题（它更像是一个解决方法）。但第二个建议加一分。 - Vinz243

我可能应该将其分成评论和单独的答案。是的，我确实使用了您的代码作为起点。我的版本与您的版本之间的关键区别在于仅在初始化期间运行它一次。我对您这样的请求的看法是，您有一个需要解决的潜在问题，我猜测了问题可能是什么，并提出了另一种解决方案。如果这不能帮助您-没问题。因此提出了第二个建议。感谢您的赞成！ - Kevin Keane

这可能对我有所帮助。但问题团队的问题是在编译时使用crc32。因此第一部分有注释。 - Vinz243

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tux3 · Accepted Answer

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

请注意，我重用了此答案中的代码来生成CRC表，并且我基于此页面上的代码进行实现。

由于我目前没有安装在Windows虚拟机中MSVC，因此我尚未在其上进行测试，但我认为它应该可以工作，或者通过简单的更改使其正常工作。

这是代码，您可以直接使用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只是简单的包装器，为了方便而存在。