RISC-V中clmul内建函数优化CRC计算的原理及相关疑问

1. 为何CRC位循环可被clmul内建函数替代？ #

CRC的本质是GF(2)域下的多项式除法：输入数据对应一个多项式，CRC值是该多项式除以CRC生成多项式后的余数。

位循环实现是逐位手动模拟多项式除法：每处理1个数据位，就将CRC寄存器左移（对应多项式乘x），若最高位为1则异或生成多项式（对应GF(2)域下的减法操作，即异或）。

而clmul是RISC-V位操作扩展提供的GF(2)域多项式乘法指令，结合Barrett约简算法，能把逐位的除法操作转化为两次多项式乘法运算，一次性完成多个位的处理。两者核心都是执行GF(2)域的多项式运算，只是clmul利用硬件指令批量计算，效率远高于逐位循环。

位循环实现代码：

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;
      else
        crc = crc << 1;
      byte = byte << 1;
    }
  }
  return crc;
}

clmul实现代码：

uint32_t crc32q_simple(const uint32_t *data, int length) {
    uint32_t P = 0x814141AB;    // CRC多项式（隐含x^32项）
    uint32_t mu = 0xFEFF7F62;   // x^64除以CRC多项式的商
    uint32_t mu1 = 0xFF7FBFB1;  // 带前导1的mu右移1位
    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;
}

2. 为何mu、mu1传入clmul能实现正确CRC计算？ #

mu和mu1是Barrett约简算法的关键常量：

• mu是x^64除以CRC生成多项式P的商（GF(2)域下的除法结果）；
• mu1是带前导1的mu右移1位后的结果，用于简化约简步骤。

clmul实现的核心流程：

1. crc ^= rev8(data[i])：将输入数据与当前CRC值异或，对应GF(2)域下的多项式相加；
2. clmulr(crc, mu1)：执行GF(2)域的反向多项式乘法，得到约简所需的中间结果；
3. clmul(crc, P)：再次执行多项式乘法，完成Barrett约简，最终得到的结果就是输入数据多项式除以P后的余数——也就是CRC值。

整个流程用Barrett约简算法通过两次多项式乘法快速计算除法余数，和逐位循环的结果完全等价，只是计算效率更高。

3. 原CRC位循环中0x80000000的作用是什么？ #

0x80000000是一个掩码常量，用于提取32位CRC寄存器的最高位（第31位）。

在逐位CRC计算中，每次左移CRC寄存器前，需要判断最高位是否为1：

• 如果最高位是1，说明当前余数多项式的最高次项与生成多项式的最高次项相同，左移后需要异或生成多项式（对应除法中的减法操作）；
• 如果最高位是0，直接左移即可。

(crc ^ (byte << 24)) & 0x80000000这一步，先将当前输入字节的最高位与CRC寄存器的最高位异或，再用掩码提取异或后的最高位，以此判断是否需要执行异或生成多项式的操作。

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