在很多以太网、SATA 或其他高速接口项目中，我们经常会接触到 CRC（循环冗余校验）。通常，工程师会通过网站或软件工具生成一整套带异或操作的组合逻辑来实现 CRC 算法，而不去深入理解其原理——只知道可以这样用。事实上，在大多数情况下，确实不需要了解 CRC 的具体实现方法，这种黑盒化的使用方式在低频窄位宽场景下确实可行。 但是，当你的系统时钟非常高，例如 800MHz、1GHz，且数据位宽很大如 256bit、512bit时，工具生成的完整组合逻辑往往会因为时序问题而无法跑通。这时，就需要对 CRC 进行拆分设计，以优化时序和逻辑面积。如果不了解 CRC 的本质和计算方法，就很难进行这样的优化设计。因此，理解 CRC 的原理和硬件实现方式非常必要。 如果你曾经困惑过：为什么要做输入/输出反转？CRC 的异或参数到底有什么意义？又或者想知道 CRC 在硬件里是如何高效实现的——那么这篇文章正好适合你。这里我会讲解一种适合硬件实现的高效查表算法，并分享如何进一步优化。在此基础上，还会带你理解常见 CRC 参数的来源与作用。读完之后，相信你对 CRC 的认识会比大多数人更深。 前面介绍的 简单 算法很适合作为入门，因为它和 CRC 的理论对应得很直接，而且名字就叫“简单”嘛。但它有两个大问题： 为了加速，我们得想办法一次处理更多的位，比如： 4 位（半字节）最好别用，因为它不和字节对齐，不方便。至少我们得做到按字节来处理，大多数表驱动的算法也都是一次处理一个字节的。 为了说明方便，我们把 CRC 的多项式从 4 位换成 32 位 的。寄存器的样子不变，只是每个格子现在代表的是1 个字节而不是 1 位。 SIMPLE 算法还是能用的，但我们来看它在 32 位寄存器里的运作方式： poly是： 下一步， 如果 那么新的最高位就是： 重点是： 为了有一个更直观的感受，我们可以举一个W=2的例子，可以看到：t1_1和t1_2完全是由t1,t0,g1,g0所产生，也就是说第2次循环的最高位只取决于当前最高位的前2位(t1,t0) 既然这样，我们完全可以一次拿原来最高字节的全部 8 位，把接下来 8 轮的最高位变化一次算好。 这样有几个好处： 多次在不同偏移量上 XOR 某个常数，其实等效于一开始就 XOR 一个“合并好的常数”。 意思是：你不必一位位做多次 XOR，把它们的效果一次算出来也行。 所以，最终算法可以这样做： 但因为控制字节和 XOR 结果是可以提前算好的，我们可以直接用一个查表法实现： 为什么表大小是 256 这样每个循环只要： 速度快到飞起。 C 代码长这样： 其中， 或者压缩成一行： 这就是 TABLE 算法，简洁、高效，但不懂 CRC 的人可能一眼看不出来它在干嘛。 在之前的表算法中，为了确保真实数据的所有位都经过寄存器的最高位（控制是否异或多项式），必须在消息末尾添加W/8个零字节（如32位CRC添加4字节零），称为扩展消息（Augmented Message）。其作用是： 但扩展消息的问题在于： 回顾一下 CRC 的处理过程： 1. TAIL: 处理末尾填充的零字节（结束处理） 简单说： 末尾加零不是为了改变寄存器内容，是为了让计算多做几步，把最后一点真实数据“推”到寄存器最深处，确保它们被完全计算进去。 2. HEAD: 处理开头几个字节（初始化） 简单说： 开头几个字节主要是为了把初始数据装进寄存器。如果寄存器本来为零，就是简单的移入；如果寄存器非零，初始值会在装入过程中“混合”（异或）一下这些字节，但核心动作还是装入。 我们可以发现原算法本质上就是完全的异或操作： 因为异或运算有结合律： 我们可以直接把数据字节异或到寄存器的高字节，然后查表，这样就不必让它真的在寄存器里流动 W/4 次。当然这里面的表虽然逻辑上和原算法是等价的，但是里面存的内容已经完全不一样了 原算法的 当寄存器的最高字节是 也就是说，这个表是一步的转移函数，不能直接把“多步延迟”压缩到一步里。 而这里的 当寄存器最高字节和当前输入字节 XOR 得到 但这里有个坑：如果直接用原算法的 table，这个 为了让大家有一个直观的感受，可以看下面的示例： 假设 原算法（补零版） 可以看到： 改进算法（提前 XOR 版） 这里： 一开始你可能会觉得奇怪：原来是从寄存器里取出高字节查表，现在怎么是先拿数据字节去异或寄存器的高字节再查表？ 反射 (reflection) = 把比特顺序左右翻转。 例子： 因为 硬件 UART 串口或者网口 在传输数据时，是 低位在前 (LSB first)，高位在后 (MSB last) 。 这就导致硬件工程师在设计 CRC 电路时，干脆直接按 反射后的位流 来做 CRC。 本来，最“直观”的方法是：软件里先把每个字节做 bit 反射，再用正常的表驱动 CRC 算法计算。 这样做的效果是： 这就是所谓的 Reflected Table Algorithm。 那么问题来了，为什么不直接反射字节，而是要在算法里用查表法等“间接实现”？ 原因主要有这几点： 最后得到的 CRC 是 普通算法结果的 bit 反射版本。 因为现在世界上有一半的 CRC 实现用反射算法，另一半不用。 这就是为什么很多 CRC 库里会有四个参数： 其中 反射 CRC 其实就是为了配合硬件“低位先发”的习惯，把整个 CRC 算法对折了一次。 前面讲了“反射的算法”已经够绕的了，现在还有一种让人更晕的东西：反转的多项式（polynomial） 。 CRC 的核心是一个生成多项式（poly）。奇怪的是，一个好的多项式的反射版本通常也是个好多项式。 结果就是，每当一个组织（比如 CCITT）把某个多项式定为标准，多半在实际应用中，人们又忍不住去用它的反射版。 举几个例子： 答案是：不是一回事！ 所以千万别搞混： 除了前面那些反射、多项式的坑，CRC 算法还有两个常见的“变量”： 举个例子： 大多数 CRC 算法其实都是把初始值设成 从数学角度讲： 但从工程角度看： 而开头一长串 0 在真实世界的数据（例如压缩包、图像、协议头）里很常见，所以： 总结： 前面我们看到，CRC 算法会因为各种原因变得千奇百怪： 如果光靠“名字”，比如叫“CRC16”，根本没法确定到底是哪一种实现，因为“CRC16”就可能有 N 种版本。所以必须要有一种方式 用一组参数把算法说死，这样才能不混淆。因此必须有一个参数模型把这些东西说清楚 这就是Rocksoft™模型，这个模型给了几个参数，每个参数都清楚定义算法的某个方面： 按照这个模型，CRC-16 可以被这样定义： 总的来说：Rocksoft™ 模型就是一个 参数清单，用来精确描述 CRC 算法，不管实现方式有多混乱，只要你把这 7 个参数（加上 check 值）写清楚，就能唯一确定是哪一个 CRC。 通过这两篇文章，相信你已经对 CRC 有了比较深入的了解。不过，你可能依然会好奇：CRC 的查表究竟是如何生成的？CRC 的算法又是如何推导出来的？考虑到篇幅限制，这里我会在附录 C 中贴出 CRC 表以及其生成算法的 C 语言实现，供大家参考。后续如果大家感兴趣，我也会单独写一篇文章，专门来详细解析这一问题。 欢迎加入FPGA/IC专属AI知识库，在这里你可以查阅更多知识，无需下载App，微信小程序即可一键使用。 欢迎加入FPGA与数字IC学习交流群! #FPGA #数字IC #CRC硬件实现 #表驱动算法 #直接表优化 #输入输出反射 #多项式反转 #Rocksoft参数模型 #初始值盲区 #高低频场景优化 #时序优化 #预计算表 #异或特性 #CRC反射算法 #XorOut参数 前言
CRC硬件算法初探
表驱动 （Table-Driven）实现方法
nibbles（4 位）bytes（8 位）words（16 位）longwords（32 位）doublewords（64 位）甚至更大。
从位到字节的思路转换
多项式（Poly）是 33 位的：最高位有一个隐含的 1，剩下 32 位是有效位。 3 2 1 0 (字节编号)
+----+----+----+----+
| | | | | <- 接收消息（补充后的消息）
+----+----+----+----+
假设最高字节（第 3 个字节）的位是：t7 t6 t5 t4 t3 t2 t1 t0g7 g6 g5 g4 g3 g2 g1 g0t7 决定要不要把多项式（Poly）XOR 进整个寄存器。t7 = 1，就 XOR；如果是 0，就不动。那么可以表示为： t6 t5 t4 t3 t2 t1 t0 ??
+ t7 * (g7 g6 g5 g4 g3 g2 g1 g0) [Reminder: + is XOR]t6 + t7*g7
![图片[1]-FPGA基础：一文吃透CRC算法（下）——CRC硬件加速原理深度解析-Anlogic-安路社区-FPGA CPLD-ChipDebug](https://chipdebug.com/wp-content/uploads/2025/08/20250818121909567-wxsync-2025-08-a7e7ef53dcae49c201ce6f79c4394257.png?v=1755490749 "null")
这 8 个“提前算好”的控制位（control byte）可以放进一个字节里，每次取出一位来控制是否 XOR。
XOR 可以提前合并
举个例子：0100010 (寄存器)
...0110 (XOR 常数 #1)
..0110. (XOR 常数 #2)
0110... (XOR 常数 #3)
结果是：
0011000 (一次 XOR 的等效结果)
组合成表驱动算法
3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Augmented message
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+ Algorithm
v +----+----+----+----+ ---------
| +----+----+----+----+ 1. Shift the register left by
| +----+----+----+----+ one byte, reading in a new
| +----+----+----+----+ message byte.
| +----+----+----+----+ 2. Use the top byte just rotated
| +----+----+----+----+ out of the register to index
+----->+----+----+----+----+ the table of 25632-bit values.
+----+----+----+----+ 3. XOR the table value into the
+----+----+----+----+ register.
+----+----+----+----+ 4. Goto 1 iff more augmented
+----+----+----+----+ message bytes.
255+----+----+----+----+
While (还有数据没处理)
Top = 寄存器最高字节
寄存器 = (寄存器左移 8 位) | 下一个消息字节
寄存器 = 寄存器 XOR 表[Top]
End
len是扩展消息（augmented message，即填充了冗余位的消息）的字节长度，p指向扩展消息的起始地址，r是CRC寄存器（存储中间状态），t是临时变量，table是预计算表（存储256个32位CRC值的数组）。r = 0;
while (len--) {
byte t = (r >> 24) & 0xFF;
r = (r << 8) | *p++;
r ^= table[t];
}r = 0; while (len--) r = ((r << 8) | *p++) ^ table[(r >> 24) & 0xFF];CRC硬件算法优化
直接表（Direct Table）算法
原始表的痛点
r = 0;
while (len--)
r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];
如何让算法不需要补零
0x00 字节）。
XOR) 的特性是 任何值 X ^ 0 = X。因此，当寄存器内部发生异或操作时，这些零值不会改变目标字节的值。
r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];
可以转换为：
r = (r << 8) ^ (*p++) ^ t[(r >> 24) & 0xFF]; //本质上就是全异或操作原算法
3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Augmented message
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+ Algorithm
v +----+----+----+----+ ---------
| +----+----+----+----+ 1. Shift the register left by
| +----+----+----+----+ one byte, reading in a new
| +----+----+----+----+ message byte.
| +----+----+----+----+ 2. Use the top byte just rotated
| +----+----+----+----+ out of the register to index
+----->+----+----+----+----+ the table of 25632-bit values.
+----+----+----+----+ 3. XOR the table value into the
+----+----+----+----+ register.
+----+----+----+----+ 4. Goto 1 iff more augmented
+----+----+----+----+ message bytes.
255+----+----+----+----+优化后算法
+-----<Message (non augmented)
|
v 3 2 1 0 Bytes
| +----+----+----+----+
XOR----<| | | | |
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+ Algorithm
v +----+----+----+----+ ---------
| +----+----+----+----+ 1. Shift the register left by
| +----+----+----+----+ one byte, reading in a new
| +----+----+----+----+ message byte.
| +----+----+----+----+ 2. XOR the top byte just rotated
| +----+----+----+----+ out of the register with the
+----->+----+----+----+----+ next message byte to yield an
+----+----+----+----+ index into the table ([0,255]).
+----+----+----+----+ 3. XOR the table value into the
+----+----+----+----+ register.
+----+----+----+----+ 4. Goto 1 iff more augmented
255+----+----+----+----+ message bytes.
r=0; while (len--) r = (r<<8) ^ t[(r >> 24) ^ *p++];table[i] 表示：
i 时，经过一次左移并按 CRC 多项式除法更新后的 32 位补偿值。table[i] 表示的是：
i 时，把它直接当作“最终会到达高位查表的值”，经过一次 CRC 变换后的结果。(r >> 24) ^ *p++ 会对应原算法中不同步的状态，导致结果不对。
为了让提前 XOR 的效果等价，改进算法的表实际上是基于原算法的表预处理了 4 次，相当于把“字节进入寄存器低位后移 3 步才到高位的计算”预先算进表里。示例
原算法：
b 进入低位 → (移位+XOR多项式) × 3 次 → 到高位 → 查 T1 → XOR 回寄存器
提前 XOR 算法：
(高位 ^ b) 直接查 T4 → XOR 回寄存器
其中 T4 = T1 连续跑 4 次的结果
r = 0B1, B2, B3, B4, B5（5 个字节）0, 0, 0, 0循环: r = ((r << 8) | byte) ^ t[(r >> 24) & 0xFF]
时刻 高位字节 ───── 低位字节
+------+------+------+------+
Step 1: | 0 | 0 | 0 | B1 | → 查表索引 H=0
Step 2: | 0 | 0 | B1 | B2 | → 查表索引 H=0
Step 3: | 0 | B1 | B2 | B3 | → 查表索引 H=0
Step 4: | B1 | B2 | B3 | B4 | → 查表索引 H=B1
Step 5: | B2 | B3 | B4 | B5 | → 查表索引 H=B2
Step 6: | B3 | B4 | B5 | 0 | → 查表索引 H=B3
Step 7: | B4 | B5 | 0 | 0 | → 查表索引 H=B4
Step 8: | B5 | 0 | 0 | 0 | → 查表索引 H=B5
循环: r = (r << 8) ^ t[(r >> 24) ^ byte]
Step 1: 查表索引 = (高位=0) ^ B1 → 直接用 B1
Step 2: 查表索引 = (高位=0) ^ B2 → 直接用 B2
Step 3: 查表索引 = (高位=0) ^ B3 → 直接用 B3
Step 4: 查表索引 = (高位=0) ^ B4 → 直接用 B4
Step 5: 查表索引 = (高位=?) ^ B5 → 直接用 B5
这就是因为我们把数据“提前”混到寄存器高字节里了，它本质上和原来的方法是一模一样的，只是走的路径不同——这只是数学等价变换。CRC的硬件特性
输入输出反射是怎么来的？
什么是“反射”？
10010011 → 11001001。为什么会有“反射”的 CRC？
但 CRC 多项式除法的数学定义，默认是 高位先来 (MSB first) 。
于是：
Message (non augmented) >-----+
|
Bytes 0 1 2 3 v
+----+----+----+----+ |
| | | | |>----XOR
+----+----+----+----+ |
^ |
| |
XOR |
| |
+----+----+----+----+0 |
+----+----+----+----+ v
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+<-----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+255
软件怎么配合硬件？
但有人没这样干，而是 —— 反射了整个算法世界（寄存器、表、初始值、结果），唯独 不反射输入字节。
反射算法与普通CRC算法
为什么这让人困惑？
所以你在看别人代码时，如果没弄清楚 算法到底是 MSB-first 还是 LSB-first、是否反射寄存器和结果，你几乎没法对上。
ReflectIn（输入是否反射）ReflectOut（输出是否反射）Init（初始寄存器）XorOut（结果异或）ReflectIn/ReflectOut 就是解决这个历史遗留问题的。
多项式反转
比如：
G = 11101 是一个“好”的多项式，那么它的反射版本 10111 也一样好。
于是，世界上很多 CRC 标准多项式都出现了“两份”：标准版和反射版。我们把这种反射版叫做 “reversed polys” 。X25 标准多项式: 1-0001-0000-0010-0001
X25 反转多项式: 1-0000-1000-0001-0001
CRC16 标准多项式: 1-1000-0000-0000-0101
CRC16 反转多项式: 1-0100-0000-0000-0011
反转多项式和反射算法是不是一回事
为什么要设置初始值与终值？
FFFFFFFFFFFFFFFF 做一次 XOR，才得到最终结果。0。
但也有一些故意设成非零值。为什么要搞这些骚操作？
0 的数据块。0，那开头这些全 0 的字节就不会引起寄存器变化（就是所谓的 “盲区 blind spot” ）。
很多 CRC 实现会把初始值设成一个非零的数，避免这个盲点。
初始值和最终 XOR 值是 CRC 算法里的“调味料”。
CRC的参数定义
算法的名字，比如 "CRC-16"。
CRC 的位宽，比如 16 位，32 位。
注意：这里是 多项式的位数 – 1。
多项式，用十六进制写。
注意：最顶上的那个 1 不写（因为它是固定存在的）。
例如多项式 10110，写成 06。
初始值（寄存器一开始的值）。
输入反射（Boolean）。
输出反射（Boolean）。
最终值异或常数（十六进制）。
算完后和这个数异或，得到最终结果。
校验值：规定用 "123456789" 这个字符串跑算法，得到的结果是多少。
（常用来验证实现对不对。）
举例：CRC-16
Name : "CRC-16"
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : BB3D
写在最后
往期回顾
附录A
附录B
在这里，你可以提出问题、分享你的学习心得，或是参与到有趣的讨论中。附录C
//////////////////////////////////////////////////An Implementation of the Model Algorithm
--------------------------------------------
Here is an implementation of the model algorithm in the C programming
language. The implementation consists of a header file(.h) and an
implementation file(.c). If you're reading this document in a
sequential scroller, you can skip this code by searching for the
string "Roll Your Own".
To ensure that the following code is working, configure it for the
CRC-16 and CRC-32 algorithms given above and ensure that they produce
the specified "check" checksum when fed the test string "123456789"
(see earlier).
/******************************************************************************/
/* Start of crcmodel.h */
/******************************************************************************/
/* */
/* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Date : 3 June 1993. */
/* Status : Public domain. */
/* */
/* Description : This is the header (.h) file for the reference */
/* implementation of the Rocksoft^tm Model CRC Algorithm. For more */
/* information on the Rocksoft^tm Model CRC Algorithm, see the document */
/* titled "A Painless Guide to CRC Error Detection Algorithms" by Ross */
/* Williams (ross@guest.adelaide.edu.au.). This document is likely to be in */
/* "ftp.adelaide.edu.au/pub/rocksoft". */
/* */
/* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */
/* */
/******************************************************************************/
/* */
/* How to Use This Package */
/* ----------------------- */
/* Step 1: Declare a variable of type cm_t. Declare another variable */
/* (p_cm say) of type p_cm_t and initialize it to point to the first */
/* variable (e.g. p_cm_t p_cm = &cm_t). */
/* */
/* Step 2: Assign values to the parameter fields of the structure. */
/* If you don't know what to assign, see the document cited earlier. */
/* For example: */
/* p_cm->cm_width = 16; */
/* p_cm->cm_poly = 0x8005L; */
/* p_cm->cm_init = 0L; */
/* p_cm->cm_refin = TRUE; */
/* p_cm->cm_refot = TRUE; */
/* p_cm->cm_xorot = 0L; */
/* Note: Poly is specified without its top bit (18005 becomes 8005). */
/* Note: Width is one bit less than the raw poly width. */
/* */
/* Step 3: Initialize the instance with a call cm_ini(p_cm); */
/* */
/* Step 4: Process zero or more message bytes by placing zero or more */
/* successive calls to cm_nxt. Example: cm_nxt(p_cm,ch); */
/* */
/* Step 5: Extract the CRC value at any time by calling crc = cm_crc(p_cm); */
/* If the CRC is a 16-bit value, it will be in the bottom 16 bits. */
/* */
/******************************************************************************/
/* */
/* Design Notes */
/* ------------ */
/* PORTABILITY: This package has been coded very conservatively so that */
/* it will run on as many machines as possible. For example, all external */
/* identifiers have been restricted to 6 characters and all internal ones to */
/* 8 characters. The prefix cm (for Crc Model) is used as an attempt to avoid */
/* namespace collisions. This package is endian independent. */
/* */
/* EFFICIENCY: This package (and its interface) is not designed for */
/* speed. The purpose of this package is to act as a well-defined reference */
/* model for the specification of CRC algorithms. If you want speed, cook up */
/* a specific table-driven implementation as described in the document cited */
/* above. This package is designed for validation only; if you have found or */
/* implemented a CRC algorithm and wish to describe it as a set of parameters */
/* to the Rocksoft^tm Model CRC Algorithm, your CRC algorithm implementation */
/* should behave identically to this package under those parameters. */
/* */
/******************************************************************************/
/* The following #ifndef encloses this entire */
/* header file, rendering it indempotent. */
#ifndef CM_DONE
#define CM_DONE
/******************************************************************************/
/* The following definitions are extracted from my style header file which */
/* would be cumbersome to distribute with this package. The DONE_STYLE is the */
/* idempotence symbol used in my style header file. */
#ifndef DONE_STYLE
typedefunsignedlong ulong;
typedefunsigned bool;
typedefunsignedchar * p_ubyte_;
#ifndef TRUE
#define FALSE 0
#define TRUE 1
#endif
/* Change to the second definition if you don't have prototypes. */
#define P_(A) A
/* #define P_(A) () */
/* Uncomment this definition if you don't have void. */
/* typedef int void; */
#endif
/******************************************************************************/
/* CRC Model Abstract Type */
/* ----------------------- */
/* The following type stores the context of an executing instance of the */
/* model algorithm. Most of the fields are model parameters which must be */
/* set before the first initializing call to cm_ini. */
typedefstruct
{
int cm_width; /* Parameter: Width in bits [8,32]. */
ulong cm_poly; /* Parameter: The algorithm's polynomial. */
ulong cm_init; /* Parameter: Initial register value. */
bool cm_refin; /* Parameter: Reflect input bytes? */
bool cm_refot; /* Parameter: Reflect output CRC? */
ulong cm_xorot; /* Parameter: XOR this to output CRC. */
ulong cm_reg; /* Context: Context during execution. */
} cm_t;
typedefcm_t *p_cm_t;
/******************************************************************************/
/* Functions That Implement The Model */
/* ---------------------------------- */
/* The following functions animate the cm_t abstraction. */
void cm_ini P_((p_cm_t p_cm));
/* Initializes the argument CRC model instance. */
/* All parameter fields must be set before calling this. */
void cm_nxt P_((p_cm_t p_cm,int ch));
/* Processes a single message byte [0,255]. */
void cm_blk P_((p_cm_t p_cm,p_ubyte_ blk_adr,ulong blk_len));
/* Processes a block of message bytes. */
ulong cm_crc P_((p_cm_t p_cm));
/* Returns the CRC value for the message bytes processed so far. */
/******************************************************************************/
/* Functions For Table Calculation */
/* ------------------------------- */
/* The following function can be used to calculate a CRC lookup table. */
/* It can also be used at run-time to create or check static tables. */
ulong cm_tab P_((p_cm_t p_cm,int index));
/* Returns the i'th entry for the lookup table for the specified algorithm. */
/* The function examines the fields cm_width, cm_poly, cm_refin, and the */
/* argument table index in the range [0,255] and returns the table entry in */
/* the bottom cm_width bytes of the return value. */
/******************************************************************************/
/* End of the header file idempotence #ifndef */
#endif
/******************************************************************************/
/* End of crcmodel.h */
/******************************************************************************/
/******************************************************************************/
/* Start of crcmodel.c */
/******************************************************************************/
/* */
/* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Date : 3 June 1993. */
/* Status : Public domain. */
/* */
/* Description : This is the implementation (.c) file for the reference */
/* implementation of the Rocksoft^tm Model CRC Algorithm. For more */
/* information on the Rocksoft^tm Model CRC Algorithm, see the document */
/* titled "A Painless Guide to CRC Error Detection Algorithms" by Ross */
/* Williams (ross@guest.adelaide.edu.au.). This document is likely to be in */
/* "ftp.adelaide.edu.au/pub/rocksoft". */
/* */
/* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */
/* */
/******************************************************************************/
/* */
/* Implementation Notes */
/* -------------------- */
/* To avoid inconsistencies, the specification of each function is not echoed */
/* here. See the header file for a description of these functions. */
/* This package is light on checking because I want to keep it short and */
/* simple and portable (i.e. it would be too messy to distribute my entire */
/* C culture (e.g. assertions package) with this package. */
/* */
/******************************************************************************/
#include "crcmodel.h"
/******************************************************************************/
/* The following definitions make the code more readable. */
#define BITMASK(X) (1L << (X))
#define MASK32 0xFFFFFFFFL
#define LOCAL static
/******************************************************************************/
LOCAL ulong reflect P_((ulong v,int b));
LOCAL ulong reflect(v,b)
/* Returns the value v with the bottom b [0,32] bits reflected. */
/* Example: reflect(0x3e23L,3) == 0x3e26 */
ulong v;
int b;
{
int i;
ulong t = v;
for (i=0; i<b; i++)
{
if (t & 1L)
v|= BITMASK((b-1)-i);
else
v&= ~BITMASK((b-1)-i);
t>>=1;
}
return v;
}
/******************************************************************************/
LOCAL ulong widmask P_((p_cm_t));
LOCAL ulong widmask(p_cm)
/* Returns a longword whose value is (2^p_cm->cm_width)-1. */
/* The trick is to do this portably (e.g. without doing <<32). */
p_cm_t p_cm;
{
return (((1L<<(p_cm->cm_width-1))-1L)<<1)|1L;
}
/******************************************************************************/
voidcm_ini(p_cm)
p_cm_t p_cm;
{
p_cm->cm_reg = p_cm->cm_init;
}
/******************************************************************************/
voidcm_nxt(p_cm,ch)
p_cm_t p_cm;
int ch;
{
int i;
ulong uch = (ulong) ch;
ulong topbit = BITMASK(p_cm->cm_width-1);
if (p_cm->cm_refin) uch = reflect(uch,8);
p_cm->cm_reg ^= (uch << (p_cm->cm_width-8));
for (i=0; i<8; i++)
{
if (p_cm->cm_reg & topbit)
p_cm->cm_reg = (p_cm->cm_reg << 1) ^ p_cm->cm_poly;
else
p_cm->cm_reg <<= 1;
p_cm->cm_reg &= widmask(p_cm);
}
}
/******************************************************************************/
voidcm_blk(p_cm,blk_adr,blk_len)
p_cm_t p_cm;
p_ubyte_ blk_adr;
ulong blk_len;
{
while (blk_len--) cm_nxt(p_cm,*blk_adr++);
}
/******************************************************************************/
ulong cm_crc(p_cm)
p_cm_t p_cm;
{
if (p_cm->cm_refot)
return p_cm->cm_xorot ^ reflect(p_cm->cm_reg,p_cm->cm_width);
else
return p_cm->cm_xorot ^ p_cm->cm_reg;
}
/******************************************************************************/
ulong cm_tab(p_cm,index)
p_cm_t p_cm;
int index;
{
int i;
ulong r;
ulong topbit = BITMASK(p_cm->cm_width-1);
ulong inbyte = (ulong) index;
if (p_cm->cm_refin) inbyte = reflect(inbyte,8);
r = inbyte << (p_cm->cm_width-8);
for (i=0; i<8; i++)
if (r & topbit)
r = (r << 1) ^ p_cm->cm_poly;
else
r<<=1;
if (p_cm->cm_refin) r = reflect(r,p_cm->cm_width);
return r & widmask(p_cm);
}
/******************************************************************************/
/* End of crcmodel.c */
/******************************************************************************/
//////////////////////////////////////////////////Roll Your Own Table-Driven Implementation
---------------------------------------------
Despite all the fuss I've made about understanding and defining CRC
algorithms, the mechanics of their high-speed implementation remains
trivial. There are really only two forms: normal and reflected. Normal
shifts to the left and covers the case of algorithms with Refin=FALSE
and Refot=FALSE. Reflected shifts to the right and covers algorithms
with both those parameters true. (If you want one parameter true and
the other false, you'll have to figure it out for yourself!) The
polynomial is embedded in the lookup table(to be discussed). The
other parameters, Init and XorOt can be coded as macros. Here is the
32-bit normal form(the 16-bit form is similar).
unsignedlongcrc_normal();
unsignedlongcrc_normal(blk_adr,blk_len)
unsignedchar *blk_adr;
unsignedlong blk_len;
{
unsignedlong crc = INIT;
while (blk_len--)
crc = crctable[((crc>>24) ^ *blk_adr++) & 0xFFL] ^ (crc << 8);
return crc ^ XOROT;
}
Here is the reflected form:
unsignedlongcrc_reflected();
unsignedlongcrc_reflected(blk_adr,blk_len)
unsignedchar *blk_adr;
unsignedlong blk_len;
{
unsignedlong crc = INIT_REFLECTED;
while (blk_len--)
crc = crctable[(crc ^ *blk_adr++) & 0xFFL] ^ (crc >> 8));
return crc ^ XOROT;
}
Note: I have carefully checked the above two code fragments, but I
haven't actually compiled or tested them. This shouldn't matter to
you, as, no matter WHAT you code, you will always be able to tell if
you have got it right by running whatever you have created against the
reference model given earlier. The code fragments above are really
just a rough guide. The reference model is the definitive guide.
Note: If you don't care much about speed, just use the reference model
code!
//////////////////////////////////////////////////Generating A Lookup Table
-----------------------------
The only component missing from the normal and reversed code fragments
in the previous section is the lookup table. The lookup table can be
computed at run time using the cm_tab function of the model package
given earlier, or can be pre-computed and inserted into the C program.
In either case, it should be noted that the lookup table depends only
on the POLY and RefIn (and RefOt) parameters. Basically, the
polynomial determines the table, but you can generate a reflected
table too if you want to use the reflected form above.
The following program generates any desired 16-bit or 32-bit lookup
table. Skip to the word "Summary" if you want to skip over this code.
/******************************************************************************/
/* Start of crctable.c */
/******************************************************************************/
/* */
/* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Date : 3 June 1993. */
/* Version : 1.0. */
/* Status : Public domain. */
/* */
/* Description : This program writes a CRC lookup table (suitable for */
/* inclusion in a C program) to a designated output file. The program can be */
/* statically configured to produce any table covered by the Rocksoft^tm */
/* Model CRC Algorithm. For more information on the Rocksoft^tm Model CRC */
/* Algorithm, see the document titled "A Painless Guide to CRC Error */
/* Detection Algorithms" by Ross Williams (ross@guest.adelaide.edu.au.). This */
/* document is likely to be in "ftp.adelaide.edu.au/pub/rocksoft". */
/* */
/* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */
/* */
/******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "crcmodel.h"
/******************************************************************************/
/* TABLE PARAMETERS */
/* ================ */
/* The following parameters entirely determine the table to be generated. You */
/* should need to modify only the definitions in this section before running */
/* this program. */
/* */
/* TB_FILE is the name of the output file. */
/* TB_WIDTH is the table width in bytes (either 2 or 4). */
/* TB_POLY is the "polynomial", which must be TB_WIDTH bytes wide. */
/* TB_REVER indicates whether the table is to be reversed (reflected). */
/* */
/* Example: */
/* */
/* #define TB_FILE "crctable.out" */
/* #define TB_WIDTH 2 */
/* #define TB_POLY 0x8005L */
/* #define TB_REVER TRUE */
#define TB_FILE "crctable.out"
#define TB_WIDTH 4
#define TB_POLY 0x04C11DB7L
#define TB_REVER TRUE
/******************************************************************************/
/* Miscellaneous definitions. */
#define LOCAL static
FILE *outfile;
#define WR(X) fprintf(outfile,(X))
#define WP(X,Y) fprintf(outfile,(X),(Y))
/******************************************************************************/
LOCAL void chk_err P_((char *));
LOCAL void chk_err (mess)
/* If mess is non-empty, write it out and abort. Otherwise, check the error */
/* status of outfile and abort if an error has occurred. */
char *mess;
{
if (mess[0] != 0 ) {printf("%sn",mess); exit(EXIT_FAILURE);}
if (ferror(outfile)) {perror("chk_err"); exit(EXIT_FAILURE);}
}
/******************************************************************************/
LOCAL void chkparam P_((void));
LOCAL void chkparam ()
{
if ((TB_WIDTH != 2) && (TB_WIDTH != 4))
chk_err("chkparam: Width parameter is illegal.");
if ((TB_WIDTH == 2) && (TB_POLY & 0xFFFF0000L))
chk_err("chkparam: Poly parameter is too wide.");
if ((TB_REVER != FALSE) && (TB_REVER != TRUE))
chk_err("chkparam: Reverse parameter is not boolean.");
}
/******************************************************************************/
LOCAL void gentable P_((void));
LOCAL void gentable ()
{
WR("/*****************************************************************/n");
WR("/* */n");
WR("/* CRC LOOKUP TABLE */n");
WR("/* ================ */n");
WR("/* The following CRC lookup table was generated automagically */n");
WR("/* by the Rocksoft^tm Model CRC Algorithm Table Generation */n");
WR("/* Program V1.0 using the following model parameters: */n");
WR("/* */n");
WP("/* Width : %1lu bytes. */n",
(ulong) TB_WIDTH);
if (TB_WIDTH == 2)
WP("/* Poly : 0x%04lX */n",
(ulong) TB_POLY);
else
WP("/* Poly : 0x%08lXL */n",
(ulong) TB_POLY);
if (TB_REVER)
WR("/* Reverse : TRUE. */n");
else
WR("/* Reverse : FALSE. */n");
WR("/* */n");
WR("/* For more information on the Rocksoft^tm Model CRC Algorithm, */n");
WR("/* see the document titled "A Painless Guide to CRC Error */n");
WR("/* Detection Algorithms" by Ross Williams */n");
WR("/* (ross@guest.adelaide.edu.au.). This document is likely to be */n");
WR("/* in the FTP archive "ftp.adelaide.edu.au/pub/rocksoft". */n");
WR("/* */n");
WR("/*****************************************************************/n");
WR("n");
switch (TB_WIDTH)
{
case 2: WR("unsigned short crctable[256] =n{n"); break;
case 4: WR("unsigned long crctable[256] =n{n"); break;
default: chk_err("gentable: TB_WIDTH is invalid.");
}
chk_err("");
{
int i;
cm_t cm;
char *form = (TB_WIDTH==2) ? "0x%04lX" : "0x%08lXL";
int perline = (TB_WIDTH==2) ? 8 : 4;
cm.cm_width = TB_WIDTH*8;
cm.cm_poly = TB_POLY;
cm.cm_refin = TB_REVER;
for (i=0; i<256; i++)
{
WR(" ");
WP(form,(ulong) cm_tab(&cm,i));
if (i != 255) WR(",");
if (((i+1) % perline) == 0) WR("n");
chk_err("");
}
WR("};n");
WR("n");
WR("/*****************************************************************/n");
WR("/* End of CRC Lookup Table */n");
WR("/*****************************************************************/n");
WR("");
chk_err("");
}
}
/******************************************************************************/
main ()
{
printf("n");
printf("Rocksoft^tm Model CRC Algorithm Table Generation Program V1.0n");
printf("-------------------------------------------------------------n");
printf("Output file is "%s".n",TB_FILE);
chkparam();
outfile = fopen(TB_FILE,"w"); chk_err("");
gentable();
if (fclose(outfile) != 0)
chk_err("main: Couldn't close output file.");
printf("nSUCCESS: The table has been successfully written.n");
}
/******************************************************************************/
/* End of crctable.c */
/******************************************************************************/
