c - 异构元组的快速8位校验和算法

假设我的三元组包含3个异类整数类型(int16_t，int32_t和int64_t)，并且我想为这3个值计算一个8位无符号校验和。假设所有值在所有有效位上都具有均匀分布，因此我们不能通过在连接它们时截断任何值来作弊。

对我而言，计算具有相对较低的冲突率和非加密属性的校验和的快速方法是什么？我猜想我可以连接字节并使用Fletcher的校验和或Pearson哈希的变体，但是我所看到的所有实现似乎都过时了，我想看看是否可以进一步利用SIMD或现代(Skylake)建筑。

我也知道MurmurHash，但是它没有8位实现。

最佳答案

现代的x86具有非常快的CRC32C (hardware instruction added in SSE4.2)。将int32和int16串联为零扩展的int64_t，并使用两条CRC32C指令累加单个校验和，可能会得到良好的结果。要使编译器为您完成此操作，请使用imintrin.h:unsigned __int64 _mm_crc32_u64( unsinged __int64 crc, unsigned __int64 data )中的内在函数。

根据Agner Fog's instruction tables的说法，crc32在Skylake上具有每个时钟吞吐量1个和3个周期的延迟，因此，向其馈送2x 8字节并获得32位结果应该只需要2 uops / 6个周期的延迟。首先将其输入uint64_t，以便将uint16和uint32串联起来是关键路径，即在shift / or与第一个crc32之间创建指令级并行性。

然后将crc32c水平异或为8位:

uint32_t crc = my_object_crc32(&my_object);
crc ^= crc>>16;
crc ^= crc>>8;
crc = (uint8_t)crc;

将较宽的crc / hash /校验和的位混合为8位值的水平异或运算适用于您要使用的任何哈希函数。

或简单地获取CRC32C 的低字节。通过将所有4个字节异或为1，对IDK可以得到多少收益。同样，可以与任何多字节散列函数一起使用。

您甚至可以对输入的中的所有字节进行水平异或。例如加载16字节的SSE2加载，并屏蔽填充字节，然后将pshufd / pxor减小到8个字节，将pshuflw / pxor减小到4个字节。
然后将另一个pshuflw / pxor减小至2个字节，并将movd转换为整数以进行最后的移位/ xor。 (或者，您也可以将movd更早地转换为整数，尤其是在编译器具有要使用一条指令进行复制和移位的BMI2 rorx的情况下)。

关于c - 异构元组的快速8位校验和算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48878862/