0

我正在尝试将意外噪声库从 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 循环中，我们看到以下内容：

  1. 执行按位异或运算hval
  2. 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

我没有在我的实现中提供缓冲区长度，因为 Lua 的位运算符总是在 32 位有符号整数上工作。

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

字节# C＃ 卢阿
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)

卢阿：01111110_10111100_11101000_10111000（2126309560）

可以看出，在第一个散列循环之后的结果非常不同。从调试中我可以看到与素数相乘时数字会出现差异。我相信原因可能是 Lua 默认使用有符号数字，而 C# 实现适用于无符号整数。或者可能由于字节顺序的不同而导致结果不同？

我确实读过 Lua 在使用十六进制文字时使用无符号整数。由于FNV_32_PRIME是十六进制文字，我想它应该与 C# 实现相同，但最终结果不同。

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

4

2 回答 2

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
于 2021-10-12T08:42:32.740 回答
1

对 32 位无符号数进行算术运算不一定会产生 32 位数。

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

于 2021-10-11T07:19:52.713 回答