QOI 指数哈希函数的按位加权和

Question

我最近为 QOI 图像格式的 Rust 库做出了贡献。作为编码过程的一部分，编码器会跟踪已看到的 RGBA 像素值的数组。它使用简单的加权和哈希函数来计算索引：

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

该库使用按位运算来计算哈希值，这被证明比简单的解决方案更快。我需要帮助理解该算法。

pub fn hash_index(px: [u8; 4]) -> u8 {
    let v = u32::from_le_bytes([px[0], px[1], px[2], px[3]]) as u64;
    let s = ((v & 0xff00_ff00) << 32) | (v & 0x00ff_00ff);
 
    (s.wrapping_mul(0x0300_0700_0005_000b_u64) >> 56) as u8 & 63
}

根据我对算法的理解：

• 创建像素字节的 u32 表示
• 将其扩展为 u64 以适应 shl 32 的乘法。它之所以有效，是因为最大 mul 值 11x255 不会溢出一个字。
• 屏蔽高字节和低字节。高字节包含 A 和 B，低字节包含 G 和 R。

我不明白的是：

• 如何在同一次调用中完成乘法和求和？加法运算在哪里进行？
• 为什么权重常数是倒置的？不是应该

  0x0300_0700_0005_000b

  吗？
• 结果在哪里？为什么要调用 shr 56 来提取 MSB？

有人可以详细说明这些要点，或者引导我完成代码吗？我的按位技能相当缺乏，但我很高兴我到目前为止已经了解了。

谢谢

Answer 1

乘法用于将不同部分相加。总和在乘积的高字节中相加，其他一些不完整的结果最终在乘积的低字节中并被丢弃。

考虑

s * 0x0300_0700_0005_000b

=

s * 0xb + s * 0x5_0000 + s * 0x0700_0000_0000 + s * 0x0300_0000_0000_0000

，进而

s * 0x5_0000 = (s * 5) << 16

。

乘法的目标是将结果累加到乘积的最高有效字节中。最重要的字节是乘积中唯一可以从

s

的每个字节“访问”的字节：乘法只能将数据移至 left，而不是 right（好吧，双宽度乘法可以，如果您看它的上半部分，但这里没有使用）。

为了让

s

的一个字节到达最高有效字节，它需要移动一段距离，该距离在某种意义上与它开始的位置“相反”。因此

s

（

r

组件）的最低有效字节最需要移位，这就是为什么

r

组件的权重位于乘法器顶部的原因。乘数的其他非零数字也会在乘积的较低 7 个字节中生成

r

的额外副本，但它们将被忽略。

说到“副本”，请考虑

s

的形式为

r + (b << 16) + (g << 40) + (a << 56)

，乘数的形式为

11 + (5 << 16) + (7 << 40) + (3 << 56)

。如果你计算出所有的部分乘积，你会得到：

11r + (11b << 16) + (11g << 40) + (11a << 56) +
(5r << 16) + (5b << 32) + (5g << 56) + (5a << 72) +
(7r << 40) + (7b << 56) + (7g << 80) + (7a << 96) +
(3r << 56) + (3b << 72) + (3g << 96) + (3a << 112)

其中，任何移位 64 或更多的内容都会完全消失，因为我们正在进行包装 64 位乘法。

任何移位小于 56 的内容都将被右移 56 丢弃。顺便说一句，只有当您选择输入时，乘法执行的加法不会带入我们关心的乘积部分，这才是正确的关于。在这里效果很好，因为有大量的“缓冲区空间”：

(11g << 40) + (7r << 40)

（唯一两个接近最高有效字节的部分乘积）最多可以是

((11*255 << 40) + (7*255 << 40)) = 4590 << 40

，这还不足以影响最高有效字节。

剩下的是

11a + 5g + 7b + 3r

。由于这一切都发生在最高有效字节中，因此仅产生该总和的 8 个最低有效位，但无论如何我们只需要 6 最低有效位。