如何提高CRC-5计算的时间效率？

Question

我刚刚开始研究CRC，以及如何在软件中实现它。我的信息源主要是跟随文档。本文给出了计算任意生成多项式CRC的一些简单算法。我尝试用C++语言编写这个算法。我已经用这个晶片测试了生成多项式x^5 + x^4 + x^2 +1 (CRC-5) (由在线计算器使用的生成器多项式)，并进行了工作。

#include <iostream>
using namespace std;

int main() {
   
    uint8_t data_byte = 0x31;
    // polynom x^5 + x^4 + x^2 + 1 
    uint16_t polynom = 0x35;

    // register contains 0 at the beginning
    uint32_t crc = 0;
    uint32_t message = 0;
    // shift the message byte to left by so many bits which is needed for generator polynomial
    message = (data_byte << 5);
    // now the message byte is 13 bits long
    uint8_t processed_bit = 13;
    while(processed_bit > 0) {
                    
        // prepare free space for new bit from the message byte
        crc = crc << 1;
        // find out value of current msb in the message byte
        message = message << 1;
        if(message & 0x2000) {
            // msb in message byte is "1"
            // lsb in register is set to "1"
            crc |= 1U;
        } else {
            // msb in message byte is "0"
            // lsb in register is set to "0"
            crc &= ~1U;
        }
        // remove msb from message byte
        message = message & ~0x2000;
        
        if(crc & 0x20) {
            // subtract current multiple of the generator polynomial
            crc = crc ^ polynom;
        }
        // remove msb from the register
        crc = crc & ~0x20;
        
        processed_bit--;
    }
                
    cout << "CRC: " << (int)crc << endl;
    
    return 0;
}  

显然，就执行时间而言，该程序是无效的。因此，我一直在考虑如何从这个角度改进它的可能性。我知道有一个变体可以使用包含预先计算的提醒的查找表，但是我想避免这种方法。有人知道如何从执行时间的角度来改进上述算法吗？谢谢您的建议。

Answer 1

简单地看一眼，就会看到几个不必要的语句。你不需要crc &= ~1U;，因为crc = crc << 1;已经在那里放了一个零。您不需要message = message & ~0x2000;，因为您只看过其中的一点。就让其他的部分移开。您不需要crc = crc & ~0x20;，因为排他性--或者多项式已经做到了。

如果您阅读您所链接的文档，您将发现您不需要再处理5位(总共13位)。您只需要处理这八个消息位。在阅读该文档时，不需要一次只输入一个消息位。您可以将消息字节直接排它到CRC寄存器上，然后处理寄存器中的所有八位。

最后，您可以通过查找表来显著加快计算速度，一次处理八位，而不是一次处理一位。在您链接的文档中也很漂亮地描述了这一点。您可以找到代码在这里自动生成用于计算的表和C代码。

不过，如果你一开始就没有考虑到正确的事情，那么这一切都无关紧要。首先需要用芯片上的数据来验证计算结果。我找到了这份文件详细介绍了该芯片的CRC计算。。你需要花点时间来了解它的细节。

为了直接回答您的问题，这里有一些代码可以执行您的代码，但要简单得多。同时，它也被扩展到n位上，而不仅仅是8位。它使用n个循环而不是n+5循环：

// Return a CRC-5 of the low n bits of data. The remaining bits of data must be
// zero. n must be in [5..32].
uint8_t crc5(uint32_t data, int n) {
    int shift = n - 5;
    uint32_t poly = (uint32_t)0x15 << shift;
    uint32_t top = (uint32_t)1 << (n - 1);
    do {
        data = data & top ? (data << 1) ^ poly : data << 1;
    } while (--n);
    return (data >> shift) & 0x1f;
}

更简单、更快的，与你的相同，限制为8位，展开：

uint8_t crc5_8(uint8_t data) {
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    data = data & 0x80 ? (data << 1) ^ 0xa8 : data << 1;
    return data >> 3;
}

然而，这两种方法都不能计算出你需要什么芯片。