将 FNV-1a 算法从 C# 移植到 Lua，乘法结果不匹配

Question

我正在尝试将 Accidental Noise 库从 C# 移植到 Lua。我在尝试移植 FNV-1A 算法时遇到问题。当使用相同的输入值时，与质数相乘的结果不匹配。

首先我想展示算法的C#代码：

// The "new" FNV-1A hashing
private const UInt32 FNV_32_PRIME = 0x01000193;
private const UInt32 FNV_32_INIT = 2166136261;

public static UInt32 FNV32Buffer(Int32[] uintBuffer, UInt32 len)
{
    //NOTE: Completely untested.
    var buffer = new byte[len];
    Buffer.BlockCopy(uintBuffer, 0, buffer, 0, buffer.Length);

    var hval = FNV_32_INIT;    
    for (var i = 0; i < len; i++)
    {
        hval ^= buffer[i];
        hval *= FNV_32_PRIME;
    }

    return hval;
}

此函数在代码库的其他地方被这样调用（简化）：

public static UInt32 HashCoordinates(Int32 x, Int32 y, Int32 seed)
{
    Int32[] d = { x, y, seed };
    return FNV32Buffer(d, sizeof(Int32) * 3);
}

我注意到 sizeof(Int32) 结果总是乘以 Int32[] 数组中的元素数。在这种情况下（在我的机器上）结果是 12，这导致 FNV32Buffer 函数中的缓冲区大小是一个 12 字节的数组。

在 for 循环中，我们看到以下内容：

对hval
hval乘以质数

乘法运算的结果与我的 Lua 实现的结果不匹配。

我的 Lua 实现是这样的：

local FNV_32_PRIME = 0x01000193
local FNV_32_INIT = 0x811C9DC5

local function FNV32Buffer(buffer)
    local bytes = {}

    for _, v in ipairs(buffer) do
        local b = toBits(v, 32)
        for i = 1, 32, 8 do
            bytes[#bytes + 1] = string.sub(b, i, i + 7)
        end
    end

    local hash = FNV_32_INIT
    for i, v in ipairs(bytes) do
        hash = bit.bxor(hash, v)
        hash = hash * FNV_32_PRIME
    end

    return hash
end

我在我的实现中没有提供缓冲区长度 as Lua's Bitwise operators always work on 32-bit signed integers。

在我的实现中，我创建了一个字节数组，并为缓冲区中的每个数字提取字节 table。比较 C# 和 Lua 字节数组时，我得到的结果大多相似：

byte #	C#	Lua
1	`00000000`	`00000000`
2	`00000000`	`00000000`
3	`00000000`	`00000000`
4	`00000000`	`00000000`
5	`00000000`	`00000000`
6	`00000000`	`00000000`
7	`00000000`	`00000000`
8	`00000000`	`00000000`
9	`00101100`	`00000000`
10	`00000001`	`00000000`
11	`00000000`	`00000001`
12	`00000000`	`00101100`

似乎由于字节顺序不同，字节顺序不同，但我可以更改。我认为这与我现在的问题没有任何关系。

对于 C# 和 Lua 字节数组，我遍历每个字节并对每个字节执行 FNV-1A 算法。

当使用值 {0, 0, 300} (x, y, seed) 作为 C# 和 Lua 函数的输入时，我得到以下结果 FNV 哈希循环的第一次迭代 已完成：

C#: 00000101_00001100_01011101_00011111 (84696351)

Lua: 01111110_10111100_11101000_10111000 (2126309560)

可以看出，第一次哈希循环后的结果非常不同。通过调试，我可以看到数字与素数相乘时会出现偏差。我认为原因可能是 Lua 默认使用有符号数，而 C# 实现适用于无符号整数。或者可能由于字节顺序不同导致结果不同？

我读到 Lua 在处理十六进制文字时使用无符号整数。由于 FNV_32_PRIME 是一个十六进制文字，我想它应该与 C# 实现一样工作，但最终结果不同。

如何确保 Lua 实现与 C# 实现的结果匹配？

Answer 1

32 位无符号数的算术不一定产生 32 位数。

未测试，但我认为应使用 bit.toBit() 对与质数相乘的结果进行归一化，如您提供的参考文献中所述。

Answer 2

LuaJIT 支持 CPU 本机数据类型。
64位值（以LL为后缀）用于避免乘法结果的精度损失。

-- LuaJIT 2.1 required
local ffi = require'ffi'

-- The "new" FNV-1A hashing
local function FNV32Buffer(data, size_in_bytes)
   data = ffi.cast("uint8_t*", data)
   local hval = 0x811C9DC5LL
   for j = 0, size_in_bytes - 1 do
      hval = bit.bxor(hval, data[j]) * 0x01000193LL
   end
   return tonumber(bit.band(2^32-1, hval))
end

local function HashCoordinates(x, y, seed)
   local d = ffi.new("int32_t[?]", 3, x, y, seed)
   return FNV32Buffer(d, ffi.sizeof(d))
end

print(HashCoordinates(0, 0, 300))  --> 3732851086

将 FNV-1a 算法从 C# 移植到 Lua，乘法结果不匹配

Porting FNV-1a algorithm from C# to Lua, multiplication result don't match

c#

lua

fnv