Murmurhash2 Unsigned Int 溢出

Question

我目前正在尝试实现 hashtable/trie，但是当我将参数传递给 murmurhash2 时，它会返回一个数字，但我得到运行 unsigned int 溢出的时间错误：

test.c:53:12: 运行时间错误：无符号整数溢出：24930 * 1540483477 不能用 'unsigned int'

类型表示

test.c:60:4: 运行时间错误：无符号整数溢出：2950274797 * 1540483477 不能用 'unsigned int' 类型表示 6265

我在第 53 行和第 60 行放了一堆星号(*)

我不确定我是否传递了一些错误的参数。任何帮助将不胜感激！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed );

int main(void)
{
   const char* s= "aa";
   unsigned int number= MurmurHash2 (s, (int)strlen(s), 1) % 10000;
   printf("%u\n", number);
}

unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
{
// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.

const unsigned int m = 0x5bd1e995;
const int r = 24;

// Initialize the hash to a 'random' value

unsigned int h = seed ^ len;

// Mix 4 bytes at a time into the hash

const unsigned char * data = (const unsigned char *)key;

while(len >= 4)
{
    unsigned int k = *(unsigned int *)data;

    k *= m;
    k ^= k >> r;
    k *= m;

    h *= m;
    h ^= k;

    data += 4;
    len -= 4;
}

// Handle the last few bytes of the input array

switch(len)
{
case 3: h ^= data[2] << 16;
case 2: h ^= data[1] << 8;
case 1: h ^= data[0];
        h *= m; ************************************************
};

// Do a few final mixes of the hash to ensure the last few
// bytes are well-incorporated.

h ^= h >> 13;
h *= m;   **************************************
h ^= h >> 15;

return h;
}

Answer 1

unsigned int 具有系统相关的位数。

在大多数系统上，此数字为 32 位（4 字节），但某些系统可能使用不同的大小（即在某些机器上为 64 位（8 字节））。

然而，murmur hash "words" 是一个特定的大小。 64 位变体需要 64 位无符号类型，32 位变体需要 32 位无符号类型。

这种不一致可以通过使用 <stdint.h> 中定义的 uint64_t 或 uint32_t 类型来解决。

我想补充一点，后缀 UL（unsigned long）可能应该添加到您使用的任何数值常量中。即 2950274797UL * 1540483477UL.

正如@nwellnhof 所指出的，您的代码似乎使用了该算法的 32 位变体。

乘法指令的溢出在这些情况下是正常的（结果大于可用位数并被截断）。作为散列过程的一部分，这种数据丢失是可以接受的。

考虑使用以下方法通知编译器预期结果：

 h = (uint32_t)(((uint64_t)h * m) & 0xFFFFFFFF)

祝你好运！

Answer 2

您似乎正在使用 UBSan 选项 -fsanitize=unsigned-integer-overflow 或启用此检查的其他选项（例如 -fsanitize=integer）进行构建。 The documentation 说：

Note that unlike signed integer overflow, unsigned integer is not undefined behavior. However, while it has well-defined semantics, it is often unintentional, so UBSan offers to catch it.

对于 MurmurHash，乘法中的无符号整数溢出是完全有意的，因此您应该禁用该选项。

如果您明确使用 -fsanitize=unsigned-integer-overflow，请将其删除。
如果通过其他选项启用，则传递-fno-sanitize=unsigned-integer-overflow。
或者，将函数 MurmurHash2 注释为 __attribute__((no_sanitize("unsigned-integer-overflow")))。

另一个注意事项：您的代码似乎是从假定 32 位 int 的 32-bit reference implementation of MurmurHash2 复制而来的。您应该考虑改用 uint32_t。

Murmurhash2 Unsigned Int 溢出

Murmurhash2 Unsigned Int overflow

c

murmurhash