在RISCV中如何使用clmul内部函数来改进CRC的计算?

azpvetkf  于 2023-06-05  发布在  其他
关注(0)|答案(1)|浏览(226)

我的目标是理解和改进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;
}

我已经知道常数mumu1是如何计算的,但我仍然有问题:

  • 为什么原来的内部循环可以用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的部分有关。
6l7fqoea

6l7fqoea1#

这里的答案有太多的东西要解释。由于您甚至不了解0x80000000,因此您需要首先了解循环冗余校验的基本数学,以及重要的实际实现。我推荐Ross William's guide。对于您的具体问题,简单的答案是,它实现了一个向上移位的线性反馈移位寄存器,并使用异或掩码阅读最高位以反馈到其他位。然而,您还需要了解这样的移位寄存器如何在GF(2)上实现多项式除法,其中CRC是这种除法的余数。
一旦你理解了所有这些,那么你就准备好如何使用乘法而不是除法来做CRC了。您已经将该方法命名为Barrett's Reduction,它最初用于整数除法,但在这里应用于多项式除法。读那篇文章。总的来说,你用多项式的倒数来代替多项式的除法。你的mu是倒数。无进位乘法是多项式乘法,其中寄存器中的每个位是GF(2)上的多项式的系数。

相关问题