我的目标是理解和改进RISCV中使用clmul
指令的CRC计算。RISCV bitmanip文档中描述的方式如下:
4.8循环冗余校验(CRC)
存在用于使用两个最广泛的32位CRC多项式CRC-32和CRC-32 C来执行CRC的特殊指令。使用CLMUL可以有效地计算具有其他多项式的CRC。以下示例RISC-V Bitmanip Extension V0.93 83使用CRC 32 Q。使用clmul实现CRC 32 Q的最简单方法是使用Barrett归约。在RV 32上:
uint32_t crc32q_simple(const uint32_t *data, int length) {
uint32_t P = 0x814141AB; // CRC polynomial (implicit x^32)
uint32_t mu = 0xFEFF7F62; // x^64 divided by CRC polynomial
uint32_t mu1 = 0xFF7FBFB1; // "mu" with leading 1, shifted right by 1 bit
uint32_t crc = 0;
for (int i = 0; i < length; i++) {
crc ^= rev8(data[i]);
crc = clmulr(crc, mu1);
crc = clmul(crc, P);
}
return crc;
}
我已经知道常数mu
和mu1
是如何计算的,但我仍然有问题:
- 为什么原来的内部循环可以用
clmul
内部函数代替?文件中未对此进行说明。作为参考,以下是CRC-32/AIXM
的通用CRC代码示例:
uint32_t crc32_bitwise_aixm(const uint8_t* data, size_t length) {
uint32_t crc = 0;
for (int i = 0; i < length; i++) {
uint8_t byte = data[i];
for (int j = 0; j < 8; j++) {
if ((crc ^ (byte << 24)) & 0x80000000)
crc = (crc << 1) ^ 0x814141ab; // Here is the polynomial from which constants mu and mu1 are computed
else
crc = crc << 1;
byte = byte << 1;
}
}
return crc;
}
- 我知道这个常量是如何计算的,但问题是,为什么要计算它们,为什么把它们传递给
clmul
会使CRC工作? - 原始CRC循环中的
0x80000000
常量是什么?我认为这与屏蔽数字byte << 24
的部分有关。
1条答案
按热度按时间6l7fqoea1#
这里的答案有太多的东西要解释。由于您甚至不了解
0x80000000
,因此您需要首先了解循环冗余校验的基本数学,以及重要的实际实现。我推荐Ross William's guide。对于您的具体问题,简单的答案是,它实现了一个向上移位的线性反馈移位寄存器,并使用异或掩码阅读最高位以反馈到其他位。然而,您还需要了解这样的移位寄存器如何在GF(2)上实现多项式除法,其中CRC是这种除法的余数。一旦你理解了所有这些,那么你就准备好如何使用乘法而不是除法来做CRC了。您已经将该方法命名为Barrett's Reduction,它最初用于整数除法,但在这里应用于多项式除法。读那篇文章。总的来说,你用多项式的倒数来代替多项式的除法。你的
mu
是倒数。无进位乘法是多项式乘法,其中寄存器中的每个位是GF(2)上的多项式的系数。