如何使用来自 sse4.2 x86 扩展的 CRC32C 指令在 C 中为字符串实现哈希函数？

Question

问题

我正在尝试使用 sse4.2 x86 扩展中的 crc32c 指令为简单散列 table 实现散列函数。然而，我对这些问题还不是很满意table，所以我有一些问题。

我查到有一个函数 unsigned int _mm_crc32_u8 (unsigned int crc, unsigned char v)（来源：https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=SSE4_2&expand=1283），它接受 unsigned char 和 returns 哈希。根据我的理解，crc 变量用于前导位的错误检查目的，这与我无关（我可以将其设置为 0 或 0xffffffff 并且不关心它）。

但是我有一个字符串 char *s 并且想计算它的哈希值。

问题

（按重要性排序）

如何使用_mm_crc32_u8对整个字符串进行散列？我应该单独散列 s 中的所有字符并对结果进行按位异或吗？我真的不知道。
函数_mm_crc32_u8接受无符号字符。在这种情况下，可以只将 unsigned char 转换为 char 以像 (unsigned char)s[0] 那样转换它吗？据我所知，这是因为 ASCII 字符只有 0 到 127 的值，所以它在转换过程中不会溢出。
还有多个字节的函数 (_mm_crc32_u{16,32,64})，我是否应该使用这些函数以获得更好的性能，因为它们一次最多可以散列 4 个字节？

详情

#include <nmmintrin.h>提供以上功能。我正在用 clang 标志 -msse4.2

编译它

Answer 1

我认为，您误解了这些功能的工作方式。对于您需要为其计算 CRC 的字符串中的每个字符（或者单词，如果您使用它的更大参数版本，您应该这样做），它们应该按顺序调用。

但思路保持不变：首先将 CRC 初始化为 0，然后在循环中调用 CRC 函数，在第一个参数中给出 CRC 的先前值，在第二个参数中给出散列值。您将结果存储在 CRC 中并保持冷静并继续。

这是代码示例：

uint64_t byte_crc32(unsigned int crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u8(crc, *(const unsigned char*)(*buf));
        ++*buf;
        --len;
    }

    return crc;
}

uint64_t hw_crc32(unsigned int crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u16(crc, *(const uint16_t*)(*buf));
        *buf += 2;
        --len;
    }

    return crc;
}

uint64_t word_crc32(unsigned int crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u32(crc, *(const uint32_t*)(*buf));
        *buf += 4;
        --len;
    }

    return crc;
}

uint64_t dword_crc32(uint64_t crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u64(crc, *(const uint64_t*)(*buf));
        *buf += 8;
        --len;
    }

    return crc;
}


uint64_t crc(const char* buff, size_t len) {

    const size_t dword_chunks = len / 8;
    const size_t dword_diff = len % 8;

    const size_t word_chunks = dword_diff / 4;
    const size_t word_diff = dword_diff % 4;

    const size_t hw_chunks = word_diff / 2;
    const size_t hw_diff = word_diff % 2;

    uint64_t crc = byte_crc32(0, &buff, hw_diff);
    crc = hw_crc32(crc, &buff, hw_chunks);
    crc = word_crc32(crc, &buff, word_chunks);
    crc = dword_crc32(crc, &buff, dword_chunks);

    return crc;
}

如何使用来自 sse4.2 x86 扩展的 CRC32C 指令在 C 中为字符串实现哈希函数？

How to implement a hash function for strings in C using CRC32C instruction from sse4.2 x86 extension?

c

hash

sse

crc

crc32

问题

问题

详情