为什么这个哈希计算位 hack 有效？

Question

为了练习，我用 Rust 实现了 qoi specification。里面有一个小的哈希函数用来存储最近使用过的像素：

index_position = (r * 3 + g * 5 + b * 7 + a * 11) % 64

其中 r、g、b 和 a 分别是红色、绿色、蓝色和 alpha 通道。

我假设它作为散列工作，因为它为带有 mod 的数字创建了一个唯一的质因数分解来限制字节数。不管怎样，我在我的代码中天真地实现了它。

在查看其他实现时，我发现了这个优化哈希计算的技巧：

fn hash(rgba:[u8:4]) -> u8 {
        let v = u32::from_ne_bytes(rgba);
        let s = (((v as u64) << 32) | (v as u64)) & 0xFF00FF0000FF00FF;

        s.wrapping_mul(0x030007000005000Bu64.to_le()).swap_bytes() as u8 & 63
    }

我想我了解大部分情况，但我对幻数（被乘数）感到困惑。根据我的理解，它应该被翻转。作为一步一步的例子：

let rgba = [0x12, 0x34, 0x56, 0x78].
在我的机器上（小端）这给 v 值 0x78563412。
移位扩展值，给出 s = 0x7800340000560012。
这就是我感到困惑的地方。幻数具有应该相乘并在 64 位字段（3、5、7、11）中对齐的值，其间隔方式与原始值相同。然而，它们似乎与值的顺序相反：

0x7800340000560012
0x030007000005000B

当相乘时，最高值 Alpha 通道 (0x78) 似乎乘以 3，而最低值红色通道 (0x12) 乘以 11。我也是在将值乘以 2 的各种幂之后，不完全确定为什么这个乘法仍然有效。

我知道字节随后会被交换为大端字节序并进行修剪，但那是在乘法步骤之后我才失去的。

我知道代码生成了正确的散列，但我不明白为什么会这样。任何人都可以向我解释我错过了什么吗？

Answer 1

如果您考虑数学运算的方式，您想要这个翻转顺序，因为它意味着[=]中每个“逻辑”乘法簇的所有结果43=]相同字节。第一个值中的最高字节乘以第二个值中的最低字节产生最高字节的结果。第一个值的最低字节与第二个值的最高字节的乘积在相同的最高字节中产生结果，中间字节也是如此。

是的，0x78... 和 0x03... 也相互相乘，但它们溢出 way 超过值的顶部并丢失。具有“向后”的顺序意味着我们关心的所有乘法结果最终都在最高字节中求和（我们想要的结果的总移位总是 56 位，因为第 56 位偏移值乘以第 0 位，即40 到 16，16 到 40，0 到 56），其余的乘法我们不不希望它们的结果溢出（并丢失）或出现在较低的字节中（我们忽略）。如果翻转第二个值中的字节，0x78 * 0x0B（alpha 值和乘数）组件将丢失以溢出，而 0x12 * 0x03（红色值和乘数）组件不会到达目标字节（我们关心的每个组件最终都会不是最高字节）。

举一个可能更直观的例子，想象一下做同样的工作，但是一个输入的所有字节除了一个组件之外都是零。如果乘以：

0x7800000000000000 * 0x030007000005000B

逻辑结果是：

0x1680348000258052800000000000000

但删除溢出将其减少为：

0x2800000000000000 //^^ result we care about (actual product of 0x78 and 0x0B is 0x528, but only keeping low byte)

同样，

0x0000340000000000 * 0x030007000005000B

产生：

0x9c016c000104023c0000000000

溢出到：

0x04023c0000000000 //^^ result we care about (actual product of 0x34 and 0x5 was 0x104, but only 04 kept)

在那种情况下，其他乘法确实会在结果中留下数据（并非全部溢出），但由于我们只查看高字节，其余部分将被忽略。

如果你一步一步地做这个数学运算并将结果相加，你会发现高字节最终是你预期的四个单独乘法的正确答案 (mod 256)；翻转顺序，这样就不行了。

把所有结果放在那个高字节的好处是它允许你使用 swap_bytes 将它便宜地移动到低字节，并直接读取值（甚至不需要屏蔽它许多体系结构）。

为什么这个哈希计算位 hack 有效？

Why does this hash calculating bit hack work?

bit-manipulation

rust