使用C预处理器计算8位CRC？

Question

使用C预处理器计算8位CRC？

5

我正在为一款只有几个字节RAM的微型8位微控制器编写代码。它的简单任务是传输7个16位字，然后是这些字的CRC。这些字的值在编译时被选择。具体而言，CRC是“将0到6号字作为无符号数除以多项式x^8+x²+x+1（初始值为0xFF）的余数”。是否可以使用C预处理器在编译时计算这些字节的CRC呢？

#define CALC_CRC(a,b,c,d,e,f,g)    /* what goes here? */

#define W0    0x6301
#define W1    0x12AF
#define W2    0x7753
#define W3    0x0007
#define W4    0x0007
#define W5    0x5621
#define W6    0x5422
#define CRC   CALC_CRC(W0, W1, W2, W3, W4, W5, W6)

- Rocketmagnet

2

http://codegolf.stackexchange.com/questions/3268/compute-the-crc32-table-at-compile-time - Xophmeister

如果速度对您比非易失性存储器（闪存）更重要，那么您可以预先计算所有结果并将其存储在常量查找表中。您所描述的CRC多项式称为“CRC-8-CCITT”。我不知道该算法的最佳方法，建议您在网上搜索。 - Lundin

3个回答

1

最简单的校验和算法是所谓的纵向奇偶校验，它将数据分成具有固定位数n的“字”，然后计算所有这些字的异或。结果作为额外的字附加到消息中。

为了检查消息的完整性，接收器计算所有字（包括校验和）的异或；如果结果不是一个具有n个零的字，接收器就知道发生了传输错误。

（来源：维基百科）

在你的例子中：

#define CALC_LRC(a,b,c,d,e,f) ((a)^(b)^(c)^(d)^(e)^(f))

- vulkanino

这不是循环冗余校验，这只是一个没有多项式的派对检查。它有50%的概率无法检测到单个比特错误。 - Lundin

我同意，但正如我所说的那样，这是最简单的校验和。使用此校验和，任何传输错误只要翻转了消息中的一个比特位或奇数个比特位，都将被检测为不正确的校验和。然而，如果一个错误影响了两个比特位，并且这些比特位位于两个不同单词的相同位置，则不会检测到该错误。如果受影响的比特位是独立随机选择的，则两个比特位错误未被检测到的概率为1/n。 - vulkanino

我应该提到这不仅仅是任何校验和，我需要一个特定的校验和。 - Rocketmagnet

0

免责声明：这并不是一个直接的答案，而是一系列问题和建议。内容过长只能以评论的形式呈现。

第一个问题：您是否控制协议两端，即您或同事可以通过控制另一端的代码来选择校验算法？

如果第一个问题的答案是肯定的：

您需要评估为什么需要使用校验和，什么校验和是适当的，以及收到一个带有有效校验和的损坏消息的后果（这涉及到“什么”与“为什么”）。

您的传输介质、协议、比特率等是什么？您是否预期/观察到位错？例如，在同一板上从一个芯片到另一个芯片使用SPI或I2C时，如果出现了位错误，则可能是硬件工程师的错，或者您需要降低时钟速率，或者两者都需要。校验和无害，但实际上并不是必要的。另一方面，在嘈杂的环境中使用红外信号，您将有更高的错误概率。

一个坏消息的后果总是最重要的问题。因此，如果您正在编写数字室温计的控制器并发送消息以每秒更新显示10次，则1000条消息中有一个坏值几乎没有任何实际伤害。没有校验和或弱校验和应该没问题。

如果这些6个字节发射导弹、设置机器人手术刀的位置或导致资金转移，那么你最好确定你有正确的校验和，甚至可能需要研究加密哈希（这可能需要比你拥有的RAM更多）。

对于中间的东西，虽然会对性能/产品满意度产生明显的不利影响，但没有真正的伤害，这取决于你自己。例如，电视偶尔改变音量而不是频道可能会让客户非常恼火——比起仅在好的CRC检测到错误时放弃命令，但如果你从事制造廉价/仿冒电视的业务，如果它可以更快地将产品推向市场，那么这可能是可以接受的。

那么你需要什么样的校验和呢？

如果两端都有硬件支持外围设备内置的校验和（例如SPI中相当普遍），那么这可能是一个明智的选择。然后计算就变得更加自由。

根据vulkanino的回答，LRC是最简单的算法。

如果你真的需要CRC，维基百科上有一些不错的关于如何选择多项式的信息： http://en.wikipedia.org/wiki/Cyclic_redundancy_check

如果问题1的答案是否定的：

另一端需要什么CRC算法/多项式？这就是你必须遵循的，但告诉我们可能会得到更好、更完整的答案。

实现思路：

大多数算法在RAM/寄存器方面都非常轻量级，只需要几个额外的字节。通常情况下，函数会产生更好、更清晰、更易读、更易调试的代码。

你应该把宏解决方案看作是一种优化技巧，像所有的优化技巧一样，过早地采用它们可能会浪费开发时间，并引起比它们值得的更多问题。

使用宏也有一些奇怪的影响，您可能尚未考虑到：
您知道预处理器只能在编译时计算消息中所有字节是否固定吗？如果其中有一个变量，则编译器必须生成代码。没有函数，每次使用时该代码将被内联（是的，这可能意味着大量的ROM使用）。如果所有字节都是变量，则该代码可能比仅在C中编写函数更糟糕。或者使用好的编译器，它可能会更好。很难确定。另一方面，如果发送的消息根据可变字节数不同，则可能会得到几个版本的代码，每个版本都针对特定的用途进行了优化。

- Brian McFarland

我已经在我的问题中添加了多项式。 - Rocketmagnet

我知道所有字节都必须在编译时知道。这就是为什么我的示例代码中它们都被定义了。 - Rocketmagnet

@Rocketmagnet: 首先，我建议您尝试使用查找表作为位运算的快捷方式来编写一个可行的算法。使用PC程序计算查找表并将其存储在预处理器变量（即宏）中。然后展开“外部”循环，对每个字进行查找，大致如下：#define CALC_CRC(a,b, c) LUT[ c ^ LUT[ b ^ LUT[ a ^ FF ] ] ]。 - Brian McFarland

SPI或I2C... /--/ ...如果您有位错误，那很可能是硬件工程师的错。他们在铜线上犯错的方式太多了。相反，如果SPI或I2C出现位错误，则很可能是软件工程师的错！根据我的经验，配置不当的问题或定义/标准化通信设置不良占所有SPI/I2C错误的约99％。 - Lundin

顺便提一下，许多嵌入式系统的 C 编译器不使用堆栈来存储自动变量或参数传递。相反，它们静态分配变量，以使同时存在变量的例程将其自动变量和参数存储在不同的地址中，而那些变量不同时存在的例程可能会被赋予重叠地址。 - supercat

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- supercat · Accepted Answer

可以设计一个宏，在编译时执行CRC计算。类似于

 //选择短且独特的名称。
 #define cZX((n),b,v) (((n) & (1 << b)) ? v : 0)
 #define cZY((n),b, w,x,y,z) (cZX((n),b,w)^CzX((n),b+1,x)^CzX((n),b+2,y)^cZX((n),b+3,z))
 #define CRC(n) (cZY((n),0,cZ0,cZ1,cZ2,cZ3)^cZY((n),4,cZ4,cZ5,cZ6,cZ7))

应该可以工作，并且如果(n)可以被评估为编译时常量，则非常高效;它将简单地评估为一个常量本身。另一方面，如果n是一个表达式，则该表达式最终会被重新计算8次。即使n是一个简单的变量，生成的代码也可能比写成最快的非基于表格的方式要大得多，并且可能比写成最紧凑的方式要慢。

顺便说一下，我真的希望在C和C ++标准中能够指定重载的方法，仅在特定参数可以评估为编译时常量时才使用这些方法。语义将是这样的：不保证任何这样的重载将在每种情况下都被使用，但是保证（1）在必须在运行时评估“编译时常量”参数的任何情况下都不会使用此类重载，以及（2）在其中一个这样的重载中被视为常量的任何参数将在从其中调用的任何函数中被视为常量。有很多情况下，如果其参数是常量，则可以编写函数以计算为编译时常量，但其中运行时评估将是绝对可怕的。例如：

#define bit_reverse_byte(n) ( (((n) & 128)>>7)|(((n) & 64)>>5)|(((n) & 32)>>3)|(((n) & 16)>>1)|
  (((n) & 8)<<1)|(((n) & 4)<<3)|(((n) & 2)<<5)|(((n) & 1)<<7) )
#define bit_reverse_word(n) (bit_reverse_byte((n) >> 8) | (bit_reverse_byte(n) << 8))

在PIC上，一个简单的非循环单字节位反转函数的渲染大约需要17-19个单周期指令；一个字（16位）位反转需要34个指令，或者大约10个加上一个字节反转函数（执行两次）。最优汇编代码为反转字节需要15个单周期指令，反转字则需要17个。计算一些字节变量b的bit_reverse_byte(b)将需要数十条指令，总共需要数十个周期。计算一些16位字w的bit_reverse_word(w)可能需要数百条指令，需要数百或数千个周期才能执行。如果可以像上面的公式那样标记一个函数以扩展内联，当它扩展为四条指令时（基本上只是加载结果），这将非常好，但在内联扩展会很麻烦的情况下使用函数调用。