QOI索引哈希函数的位运算加权求和实现解析求助

在QOI图像格式的编码器中，需要通过加权哈希计算已见RGBA像素的索引，原始公式为：
index = (3*r + 5*g + 7*b + 11*a) % 64

下面是用位运算优化后的Rust实现，我们逐行解析并解答你的疑惑：

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
}

已理解部分回顾 #

• 通过from_le_bytes将RGBA像素数组[r,g,b,a]转成小端序的u32，再扩展为u64，为后续位运算预留空间
• 用掩码0xff00_ff00和0x00ff_00ff拆分u32的字节，再通过左移合并为64位整数s，让每个原始像素字节处于64位中的独立16位段（互不重叠）

疑惑解析 #

1. 单次乘法如何完成加权求和？加法在哪里？ #

这是利用了64位乘法的字节级并行特性：

• 构造s后，每个像素字节（r/g/b/a）都被隔离在64位的独立位置，彼此的二进制位不会重叠
• 乘法常量0x0300_0700_0005_000b的每个16位段对应一个权重，且位置与s中的像素字节完全对齐
• 当s与常量相乘时，每个像素字节会和对应的权重单独相乘，这些乘积的高位部分会自动叠加到64位结果的最高8位——这就相当于完成了加权求和，不需要显式编写加法指令。

本质是把加法操作“隐藏”在了乘法的进位过程中，利用CPU的64位乘法指令一次性完成所有加权运算，比逐个计算再相加更快。

2. 为什么权重常量的顺序看起来颠倒？ #

这是由字节在64位整数中的排列顺序决定的：

• 原始像素数组[r,g,b,a]转成u32后，小端序的内存布局是0xAA_BB_GG_RR（AA是a，BB是b，GG是g，RR是r）
• 构造s后，64位中的字节段顺序从高到低是：a → g → b → r
• 原始公式的权重顺序是r(3) → g(5) → b(7) → a(11)，为了让每个权重和对应像素字节对齐，常量中的权重顺序必须反过来，变成a(3) → g(7) → b(5) → r(11)，对应常量0x0300_0700_0005_000b的字节拆分（从高到低的权重字节依次是0x03、0x07、0x05、0x0b），确保每个像素字节都能和公式中对应的权重相乘。

简单说：权重顺序颠倒，是为了匹配像素字节在64位整数中的排列顺序，确保乘法时权重和对应像素值正确关联。

3. 为什么右移56位提取最高有效字节？ #

核心原因是我们只需要求和结果的高位来计算模64的哈希值：

• 每个加权项的最大值是11*255=2805，总和最大是3*255+5*255+7*255+11*255=6630，二进制仅占13位
• 乘法后，所有加权项的高位都会叠加到64位结果的最高8位（第56-63位），这部分值完全能代表总和的特征
• 右移56位就是提取这个最高字节，最后&63等价于对64取模，得到0-63的索引值。

这种方式比直接计算求和再取模更快，因为它利用CPU的单条乘法+移位指令就能完成运算。

内容的提问来源于stack exchange，提问作者AregevDev