如何在 zlib CRC32 中正确使用无进位乘法程序集 (PCLMULQDQ)?

How to properly use carry-less multiplication assembly (PCLMULQDQ) in zlib CRC32?

我最近一直在研究 CloudFlare's optimized zlib,结果确实令人印象深刻。

不幸的是,他们似乎假设 zlib 的开发被放弃了,他们的分叉也中断了。我最终能够 manually rebase their changes on to the current zlib development 分支,尽管这真的很痛苦。

无论如何,CloudFlare 代码中还有一项 主要 优化我无法使用,即 fast CRC32 code implemented with the PCLMULQDQ 附带的无进位乘法指令较新的(Haswell 和更高版本,我相信)Intel 处理器,因为:

  1. 我在Mac,clang集成汇编器和Apple的古老GAS都不懂使用的较新的GAS助记符, 和

  2. 代码是从 Linux 内核中提取出来的,并且是 GPL2,这使得整个库都是 GPL2,因此基本上对我来说毫无用处。

所以我四处寻找,几个小时后我偶然发现了 Apple 在其 bzip2 中使用的一些代码:arm64 and x86_64.

的手写矢量化 CRC32 实现

奇怪的是,x86_64 程序集的注释(仅)在 arm64 源代码中,但它似乎确实表明此代码可以与 zlib 一起使用:

This function SHOULD NOT be called directly. It should be called in a wrapper
function (such as crc32_little in crc32.c) that 1st align an input buffer to 16-byte (update crc along the way),
and make sure that len is at least 16 and SHOULD be a multiple of 16.

但不幸的是,经过几次尝试,在这一点上我似乎有点不知所措。而且我不确定如何真正做到这一点。所以我希望有人能告诉我 how/where 一个人会调用提供的函数。

(如果有一种方法可以在运行时检测到必要的功能,并且在硬件功能不可用时可以回退到软件实现,那也太棒了,所以我不必分发多个二进制文件。但是,至少,如果有人能帮我弄清楚如何让库正确使用基于 Apple PCLMULQDQ 的 CRC32,那将大有帮助。)

如其所说,您需要计算长度为 16 字节倍数的 16 字节对齐缓冲区的 CRC 和。因此,您将当前缓冲区指针转换为 uintptr_t,只要它的 4 个 LSB 位不为零,您就增加指针,将字节送入普通的 CRC-32 例程。一旦你在 16 字节对齐的地址,你将剩余的长度向下舍入到 16 的倍数,然后将这些字节提供给快速 CRC-32,然后将剩余的字节再次提供给慢速计算。


类似于:

// a function for adding a single byte to crc
uint32_t crc32_by_byte(uint32_t crc, uint8_t byte);

// the assembly routine
uint32_t _crc32_vec(uint32_t crc, uint8_t *input, int length);

uint32_t crc = initial_value;
uint8_t *input = whatever;
int length = whatever; // yes, the assembly uses *int* length.

assert(length >= 32); // if length is less than 32 just calculate byte by byte
while ((uintptr_t)input & 0xf) { // for as long as input is not 16-byte aligned
    crc = crc32_by_byte(crc, *input++);
    length--;
}

// input is now 16-byte-aligned
// floor length to multiple of 16
int fast_length = (length >> 4) << 4;
crc = _crc32_vec(crc, input, fast_length);

// do the remaining bytes
length -= fast_length;
while (length--) {
    crc = crc32_by_byte(crc, *input++)
}
return crc;