c++ - 如何提高CRC-5计算的时间效率?
问题描述
我刚刚开始研究 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;
}
很明显,这个程序在执行时间上是无效的。所以我一直在思考如何从这个角度改进它的可能性。我知道有一种变体可以使用包含预先计算的提醒的查找表,但我想避免这种方法。有人知道如何从执行时间的角度改进上述算法吗?在此先感谢您的任何建议。
解决方案
快速浏览一下就会显示几个不必要的语句。你不需要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;
}
更简单和更快仍然相当于你的限制为八位,展开:
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;
}
但是,两者都无法计算出您的芯片需要什么。
推荐阅读
- spring-mvc - 从 java webapp 发送服务器端 POST
- wpf - WPF 中的图表控件
- excel - 设置两个不同的范围并执行代码
- javascript - 检查调查是否在过去 5 分钟内完成
- javascript - 具有一个指定参数的函数,其余参数可选
- sql - 具有多个聚合的动态 Pivot SQL
- c# - 使用 Unity 2018 时出现 TextMesh Pro 问题?
- openssl - 无法使用 OpenSSL 1.0.1e-fips 加载公钥 2013 年 2 月 11 日
- c++ - C++ 中的结构和类真的等价吗?
- oracle - Microsoft Access (mdb):列出连接的 Oracle 表