摘要

本文首先阐述了错误检测的目的以及纠错复杂度，然后以此引出了CRC背后的基础思想。为了能够充分理解CRC运算所基于的运算系统，本文还介绍了抽象代数中的相关概念（多项式环、素域、扩域）。然后描述了如何选取CRC的多项式。有了这些基本概念之后，本文介绍了三种CRC的实现，对于同一个CRC算法，其中SIMPLE于TABLE ALGORITHM所使用的寄存器初值是一样的，只是后者更高效一点，而DIRECT TABLE ALGORITHM则更高效，而且寄存器初值也与前两种不一样（通常CRC算法所说的初值就是指的这个算法的寄存器初值），因此需要进行初值转换。在此之后还介绍了一些决定CRC算法的其他参数，并且以此定义一个名为Rocksoft™的参数化模型，用以精确描述CRC算法。最后本文还包含了CRC算法的C实现。

本文很大程度上参考了A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS，在其中加入了一些自己的理解。因此非常感谢Ross N. Williams.大佬

错误检测的目的

发射机产生的数据，在经过带有噪声的信道之后，会被噪声所污染，从而导致接收机接收到错误的数据。为了解决这一情况，通常可以使用一个校验算法函数$f(Msg)$，该函通常是一个关于数据原文的函数，产生一个校验和$CheckSum$。然后接收方即可以通过实现约定好的算法，验证$Msg$与$CheckSum$之间的关系。

例如，如若定义$CheckSum = f(Msg) = sum(int(byte))\mod 256$，则整个校验流程如下图，接收方可以计算出$(6+27+4) \mod 256 \neq 33$，因此可以判断出数据收到了损坏。

但是如果$Msg$与$CheckSum$都被改变了，而且改变之后的值能够与校验函数$f$对应上，就会使接收方误以为数据正确，从而引发故障。不幸的是，这种可能性是完全不能够避免的，最好的办法就是增加校验中的信息量来减小其发生的概率。

纠错复杂度

上述的算法的问题在于其太过于简单，如果数据受到了随机污染，则会接收方有$\frac{1}{256}$的概率无法检测处错误。例如：

为了增加该校验算法，我们可以将存储校验和的寄存器从8bit增加到16bit，然后使用模$2^{16}$的加法作为校验算法。这样无法检测出错误的概率就降低到了$\frac{1}{2^{16}}$。虽然这是一个好的改进，但是依然无法解决本例的错误。因为该校验算法是求和，不够随机——每次求和的时候，不管校验寄存器有多宽，都只会影响校验寄存器中大约一个字节的数据。从而我们可以从以下两个方面来增强校验算法：

WIDTH: 校验寄存器的宽度——减小碰撞的概率
CHAOS: 改进校验算法，使得每个字节都有潜力去改变校验急窜去中的任意数量bits

CRC算法背后的基础思想

虽然加法不够具有随机性，但是只要除数的宽度与校验寄存器的宽度一样，除法就能满足要求。而CRC算法的基本思想是简单地将消息视为一个巨大的二进制数，将其除以另一个固定二进制数，并将该除法的余数作为校验和。收到消息后，接收器可以执行相同的除法，并将余数与“校验和”（传输的余数）进行比较。

例如，有两个字节的消息原文（6，23），校验寄存器一个字节宽，除数为1001，其结果如下所示：

\[ \require{enclose} \begin{array}{r} 000\underline{0}000\underline{0}101\underline{0}110\underline{1}\, \\[-3pt] 9= 1001 \enclose{longdiv}{000\underline{0}011\underline{0}000\underline{1}011\underline{1}} \\[-3pt] \underline{\underline{1001}0000000}\, \\[-3pt] 110010111\, \\ \underline{\underline{1001}00000}\, \\ 1110111\, \\ \underline{\underline{1001}000}\, \\ 101111\, \\ \underline{\underline{1001}00}\, \\ 1011\, \\ \underline{\underline{1001}}\, \\ 10\, \end{array}\\ \]

虽然输入消息的每个位对商的影响并不那么显著，但在计算过程中，4位余数会被影响得很厉害，如果向消息中添加更多字节（被除数），它的值可能会很快再次发生根本性变化。这就是为什么除法在加法不起作用的地方起作用。

多项式运算

虽然前一节中描述的除法方案与称为CRC方案的校验和方案非常相似，但CRC方案实际上有点奇怪，我们需要深入研究一些奇怪的数字系统来理解它们。

多项式环

我们知道，函数是一种映射，特指 “值域是数字集合” 的映射。这里的 “数字集合”，通常指任何一个环，换句话说，只要是个环，其元素都可以被视为 “数字”。我们熟悉的整数环、有理数域2、实数域、复数域等都是很好的例子。

多项式就是一种极为重要的函数。在微积分中，性质良好的函数（解析函数）都可以被表示为一列多项式函数的极限，或者说总可以用一个多项式函数来逼近它。而多项式的性质较为简单，求导也很容易。我们现在讨论的是代数，所以就不关心可以怎么用求导啊积分啊等手段去处理多项式函数，而是关心这个概念可以怎么在代数上拓展。

先来观察一下我们熟知的多项式吧。作为实变量函数，一个多项式$f(x)$可以表示为：

\[ \begin{equation} f(x) = \sum_{i=0}^N a_i x^i~, \end{equation} \]

其中各$a_i$都是实数，而 xi是用来抽象表示 “任意自变量” 的。我们可以给$x$赋值，比如取一个实数$c$，然后令$x=c$，这样就能得到一个实数$f(c)=\sum_{i=0}^N a_i c^i$。但要是不赋值，那$f(x)$就不是一个具体的数，而是一个映射；$x$只是一个抽象符号。

两个多项式之间根本的不同，体现在哪里呢？是抽象符号吗？显然不是。$x^2+1$和$y^2+1$完全可以视为同一个多项式，用的符号不同而已。决定两个多项式差异的，是多项式的系数，对吧？$x^2+1$和$x^2+3$就不是同一个多项式。很明显，我们应该拓展的是系数的概念。

定义

设$R$是一个环,$x$是一个抽象符号。则形如:

\[ \begin{equation} f(x) = \sum_{i=0}^N a_i x^i~ \end{equation} \]

的表达式称为环$R$上的（一元）多项式（polynomial），其中各$a_i\in R$，称为该多项式的系数（coefficient）。$a_i x^i$称为$f(x)$的$i$次项（item），或者一个单项式，$i$称为其次数（degree）。全体以$x$为抽象符号的一元多项式构成的集合，记为$R[x]$。$R$称为$R[x]$的系数环；如果$R$是个域，也称之为系数域。

类似地，设各$x_k$都是抽象符号，那么形如

\[ \begin{equation} f(x_1, x_2, \cdots, x_m) = \sum_{k_1+k_2+\cdots k_m=0}^N a_{k_1, k_2, \cdots, k_m} x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}~ \end{equation} \]

的表达式称为环$R$上的$m$ 元多项式（polynomial），其中各$a_{k_1, k_2, \cdots, k_m}\in R$，称为其系数。每个$a_{k_1, k_2, \cdots, k_m} x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$是该多项式的一个$k_1+k_2+\cdots k_m$次项。

多项式中最高次的单项式的次数，称为该多项式的次数（degree）。特别的例外是，$\operatorname {deg}0 = -\infty$。多项式$f⁡(x)$的次数记为$\operatorname {deg} f(x)$。在不至于混淆的情况下，也可以简单地用$f$来表示多项式$f⁡(x)$或$f(x_1, x_2, \cdots, x_m)$。

定义

设$g(x_1, x_2, \cdots, x_m)\in R[x_1, x_2, \cdots, x_m]$。
如果$r\in R$满足$f(r)=0$，则称$r$是$f$的一个根（root）。如果数组$\{r_1, r_2, \cdots, r_m\}$满足$g(r_1, r_2, \cdots, r_m)$，则称该数组是$g$的一个根。

举几个例子。$x^2y+xy+y^3+2y$是一个整数环上的二元三次多项式，其中$x^2y$和$y^3$是其$3$次项。我们常会用到 “多项式环” 这一术语，这是因为环上的全体多项式构成的集合$R[x]$，还真就是一个环。

Attention

$R[x]$上加法和乘法的定义：同类单项式（即仅系数不同的单项式）之间的加法定义为以其系数相加的结果为系数的同类单项式，乘法类似地定义为系数的乘法；多项式乘法由单项式加法、乘法以及乘法对加法的分配律定义。

上面说了那么多，我一直在强调$x$是“抽象符号”。作为实变量函数的多项式，可以把抽象符号替换为实数来赋值，一般的环上当然也可以这么做。设$f$是环$R$上的一元多项式，那任取一个$r \in R$，依然有$f(r) \in R$。

域上的多项式除法

设$f(x)$是一个多项式，那么使得$f(r)=0$的$r$就被称为这个多项式的根（root）。根的性质决定了多项式的性质。为了理解这一点，我们要先讨论一下多项式之间的除法。不过要注意的是，我们这里要讨论的是域上的多项式除法，也就是系数选自域中，而不只是一个环中。尽管如此，多项式构成的集合依然只是一个环。

由于环没有要求乘法逆元存在性，故除法并不总是可行的。比如$5 \div 2$的结果就不在整数环中，尽管$5$和$2$都是整数。但是也正因为这样，环上诞生了独特的 “带余除法”，对，就是小学学过的$5/2=2\cdots 1$。但是$a/b=c\cdots r$的表述方法挺累赘的，不如写成$a=bc+r$好了，$a$是被除数，$b$是除数，$c$是商，$r$是余数。

尽管上述讨论中的$a, b, c, r$都是整数，我们也可以把这个概念移植到一般的环上。在稍后我们会讨论的 “欧几里得环” 中，这种带余除法非常重要，但现在我们就着眼于多项式环即可。

虑环$R$上的多项式$f(x)$和$g(x)$，则总存在$h(x)$和$r(x)$，其中$\operatorname {deg}r\leq \operatorname {deg}g$，使得$f(x)=h(x)g(x)+r(x)$。这就是多项式之间的除法。如果遇到$r(x)=0$的情况，那么就说$g$整除$f$，记为$g|f$ 。

定理1

给定域$\mathbb{F}$上的一个多项式$f(x)$。如果$r \in R$是$f$的一个根，那么$(x-r)|f$。

证明

存在$h(x), s(x)\in\mathbb{F}[x]$，使得$f(x)=h(x)\cdot(x-r)+s(x)$，且$s(x)$的次数小于$1$。这样一来，$s$实际上就是$\mathbb{F}$的一个元素。将$r$代入$x$，得到$0=f(r)=h(r)\cdot(r-r)+s$，因此$s=0$。故得证。

如果环$R$上的多项式$f⁡(x)$可以表示为两个多项式的乘积$h(x)g(x)$，或者说它可以被另一个次数为正的多项式整除，那么我们就说这个多项式是可约（reducible）的，而$h$ 和$g$就被称为其因子；否则，称$f$是不可约（irreducible）的。这样，我们只需要研究好其因子的性质，就能方便地推知$f$本身的性质。又由于定理1，多项式的性质归根到底由根来决定——如果根存在的话。

现在，我们引入一个实际计算多项式除法的方法，称为长除法，用表格表示。为方便理解，我们直接用一个具体实例来讲解：在整数环上，用$2x^2+1$去除$6x^5+x^4+2x^3-x^2-2$。

第一步，是比较两个多项式的最高次项，即$2⁢x^2$和$6⁢x^5$，然后凑一个$3⁢x^3$，比较$(2x^2+1)\cdot(3x^3)$和$6x^5+x^4+2x^3-x^2-2$的差，得到$x^4-x^3-x^2-2$。整个过程表示如下：

表1
	$3⁢x^3$
$2x^2+1$	$6x^5+x^4+2x^3-x^2-2$
	$x^4-x^3-x^2-2$

然后，再考虑剩下的$x^4-x^3-x^2-2$被$2x^2+1$除：

表2
	$3x^3+0.5x^2$
$2x^2+1$	$6x^5+x^4+2x^3-x^2-2$
	$x^4-x^3-x^2-2$
	$-x^3-1.5x^2-2$

以此类推，最终使被除多项式的次数小于$2x^2+1$的次数：

表3
	$3x^3+0.5x^2-0.5x-0.75$
$2x^2+1$	$6x^5+x^4+2x^3-x^2-2$
	$x^4-x^3-x^2-2$
	$-x^3-1.5x^2-2$
	$-1.5x^2+0.5x-2$
	$0.5x-1.25$

于是我们就得到了:

\[ \begin{equation} \begin{aligned} &6x^5+x^4+2x^3-x^2-2 \\ = &(3x^3+0.5x^2-0.5x-0.75)(2x^2+1)+(0.5x-1.25)~. \end{aligned} \end{equation} \]

我们所求的有效信息在表 3的最上方和最下方，即 “商数” 和 “余数”，而第二行则是已知的信息。剩下的部分全都是中间计算过程，算完以后就不用再关心了。

从运算过程你也可以看出来，为什么我们之前要求讨论范围是 “域” 上的多项式。除法的概念是可以局限在 “环” 上的多项式来讨论的，也依然可以使用长除法来计算，但就没法用到$0.5$这样的元素，也就无法保证余的次数比除数要小了。

素域（Prime field）

有限域也叫伽罗瓦域（galois field），指的是由有限个元素组成的集合，在这个集合内可以执行加、减、乘和逆运算。

域中包含元素的个数称为域的阶。
只有当$m$是一个素数幂时，即$m=p^n$(其中$n$为正整数是$p$的次数，$p$为素数)，阶为$m$的域才存在，$p$称为这个域的特征。

也就是说，有限域中元素的个数可以是11($p$=11是一个素数,$n$=1)、可以是81($p$=3是一个素数，$n$=4)、也可以是256($p$=2是一个素数，$n$=8).....但有限域的中不可能拥有12个元素，因为$12=2·2·3$，因此12也不是一个素数幂。

有限域中最直观的例子就是阶为素数的域，即$m=pn,(n=1)$的域，域中的元素可以用整数$\{0、1、...、p−1\}$来表示。

域的两种操作就是整数加法（模$p$）和整数乘法（模$p$），$p$是一个素数，整数环Z表示为$GF(p)$，也成为拥有素数个元素的素数域或者伽罗瓦域。

总结

素域就是有素数个元素的有限域，即阶为素数的有限域。

$GF(p)$中所有的非零元素都存在逆元
$GF(p)$内所有的运算都是模$p$实现的。

素域内的算数运算规则如下：

加法和乘法都是通过模$p$实现的；
任何一个元素$a$的加法逆元都是由$a+$($a$的逆元)=$0$(mod $p$)得到的；
任何一个非零元素$a$的乘法逆元定义为$a·$($a$的逆元)=$1$(mod $p$)。

例：在素域$GF(5)=\{0,1,2,3,4\}$中，$2$的加法逆元为$3$，这是因为，$2+(3)=5$，$5 \mod 5=0$,所以$2+3=5 \mod 5=0$；$2$的乘法逆元为$3$，这是因为，$2·3=6$，$6 \mod 5=1$，所以$2·3=6 \mod 5=1$。

Note

在很多地方$a$的加法逆元用$-a$表示，$a$的乘法逆元用$a^{-1}$表示

注：$GF(2)$是一个非常重要的素域，也是存在的最小的有限域，由于$GF(2)$的加法，即模$2$加法与异或(XOR)门等价，$GF(2)$的乘法与逻辑与(AND)门等价。
加法：$0+1=1;1+1=0;0+0=0$
乘法：$1\times 0 = 0;1 \times 1 =1; 0 \times 0 = 0$

另外素域$GF(p)$一般还用符号$F_p$表示，记$F_p^*$是由$F_p$中所有非零元构成的乘法群，即$(1,2,\dots,p-1)$，又因为$F_p^*$是循环群，所以在$F_p$中至少存在一个元素$g$，使得$F_p$中任意非零元都可以由$g$的一个幂表示，称$g$为$F_p^*$的生成元（本原元），即$F_p^*=\{g^i|0\leq i \leq p-2\}$。设$a=g^i \in F_p^*$，其中$0 \leq i \leq p-2$。则$a$的乘法逆元$a^{-1}=g^{p-1-i}$。

举例：
$13$是$F_{19}^∗$的一个生成元，则$F_{19}^∗$中的元素可以由13的方幂表示出来：
$13^0=1,13^1=13,13^2=17,13^3=12,13^4=4,13^5=14,13^6=11,13^7=10,13^8=16,13^9=18,$
$13^{10}=6,13^{11}=2,13^{12}=7,13^{13}=15,13^{14}=5,13^{15}=8,13^{16}=9,13^{17}=3,13^{18}=1$

扩域（extension field）

如果有限域的阶不是素数，则这样的有限域内的加法和乘法运算就不能用整数加法模$p$和整数乘法模$p$表示。

Note

阶数不是素数，且大于1的有限域被称为扩展域

为了处理扩展域，我们就要使用不同的符号表示扩展域内的元素，使用不同的规则执行扩展域内元素的算术运算。

设$q$是一个素数或素数方幂，$f(x)$是多项式环$F_q[x]$上的一个$m(m>1)$次不可约多项式，商环$F_q[x]/f(x)$是含$q^m$个元素的有限域，记$F_{q^m}$，即$F_{q^m}$是有限域$F_q$的扩域，域$F_q$是域$F_{q^m}$的子域，$m$是扩展次数（因子）。

$F_{q^m}$可以看作$F_q$上的$m$维向量空间，即在$F_{q^m}$中存在$m$个元素$\left \{ \alpha_{0},\alpha_{1},...., a_{m-1} \right \}$，使得$\forall a \in F_{q^{m}}$，$a$可以唯一表示为：$a=a_{m-1}\alpha_{m-1}+...+a_{1}\alpha_{1}$，其中$a_i\in F_q$，把$\left\{\alpha_{m-1}, \cdots, \alpha_{1}, \alpha_{0}\right\}$叫做$F_{q^m}$上在$F_q$上的一组基。

给定这样的一组基，就可以由向量$\left(a_{m-1},a_{m-2}...., a_{1}, a_{0}\right)$来表示域元素$a$。

$F_{q^m}$在$F_q$上的基有多种选择：多项式基和正规基等，下面简单介绍：

多项式基

不可约多项式$f(x)$可以取首一多项式$f(x)=x^{m}+f x^{m-1}+...+f_{2} x^{2}+f_{1} x+f_{0}$（其中$f_i\in F_q,i=0,...,m-1$）

$F_{q^m}$中的元素由多项式环$F_q[x]$中所有次数低于$m$的多项式构成，即$F_{q^m}=\left\{a_{m-1} x^{m-1}+a_{m-2} x^{m-2}+\cdots+a_{1} x+a_{0} \mid a_{i} \in F_{q}, i=0,1, \cdots, m-1\right\}$

多项式集合$\left\{x^{m-1}, x^{m-2}, \cdots, x, 1\right\}$是 $F_{q^m}$作为向量空间在$F_q$上的一组基，称为多项式基

当$m$含有因子$d(1<d<m)$时, $F_{q^m}$可以由$F_{q^d}$扩张生成, 从$F_{q^d}[x]$中选取一个合适的$m/d$次不可约多项式作为$F_{q^m}$在$F_{q^d}$上的不可约多项式，$F_{q^m}$可以由塔式扩张方法 (towering method) 得到, 这种扩张的基本形式仍是由$F_q$中元素组成的向量

例如当$m=6$时, 可以先由$F_q$经过$3$次扩张得扩域$F_{q^3}$ ，再由$F_{q^3}$经过$2$次扩张得到扩域$F_{q^6}$ ; 也可以先由$F_q$经过$2$次扩张得扩域$F_{q^2}$, 再由$F_{q^2}$经过$3$次扩张得到扩域$F_{q^6}$

正规基

$F_{q^m}$在$F_q$上形如$\left\{\beta, \beta^{q}, \beta^{q^{2}}, \cdots, \beta^{q^{m-1}}\right\}$的一组基称为正规基, 其中$\beta \in F_{q^{m}}$ 。 $\forall a \in F_{q^{m}}, a$可以唯一表示为:$a=a_{0} \beta+a_{1} \beta^{q}+\cdots+a_{m-1} \beta^{q^{m-1}}$, 其中$a_{i} \in F_{q}, i=0,1, \cdots, m-1$。

对于任意有限域$F_q$及其扩域$F_{q^m}$, 这样的基总是存在的。

例如在扩展域$GF(2^m)$中，元素并不是用整数表示的，而是用系数为域GF(2)中元素的多项式表示，这个多项式最大阶数（degree）为$m-1$，所以每个元素共有$m$个系数。比如在AES算法使用的域$GF(2^8)$中，每个元素$A\in GF(2^8)$都可以表示为：$A(x)=a_7x^7+a_6x^6+...+a_1x+a_0,a_i\in GF(2)$

注意：在域$GF(2^8)$中这样的多项式共有$256$个，这$256$个多项式组成的集合就是扩展域$GF(28)$，每个多项式都可以按一个$8$位向量的数值形式存储：$A=(a_7,a_6,...,a_1,a_0)$，像$x^7,x^6,…x$等因子都无需存储，因为从位的位置就可以清楚地判断出每个系数对应的幂。

扩域$GF(2^m)$内的算数运算规则如下：

加减法

在AES算法中的密钥加法层中就使用了这部分的知识，但是不是很明显，因为我们通常把扩展域中的加法当作异或运算进行处理了，因为在扩展域$GF(2^m)$中的加减法处理都是在底层域$GF(2)$内完成的，与按位异或运算等价。假设$A(x)、B(x)∈GF(2^m)$。

计算两个元素之和的方法就是：$C(x)=A(x)+B(x)=\sum_{i=0}^{m-1}c_ix^i$,其中$c_i=(a_i+b_i)mod 2$

两个元素之差的计算公式就是：$C(x)=A(x)-B(x)=\sum_{i=0}^{m-1}C_ix^i$,其中$c_i=(a_i-b_i)mod 2=(a_i+b_i)mod 2$

注：在减法运算中减号之所以变成加号，这就和二进制减法的性质有关了，从上述两个公式中我们发现在扩展域中加法和减法等价，并且与XOR等价(异或运算也被称作二进制加法)。

乘法

扩展域的乘法主要运用在AES算法的列混淆层(Mix Column)中，也是列混淆层中最重要的操作。

我们想将扩展域中的两个元素用多项式形式展开，然后使用标准的多项式乘法规则将两个多项式相乘：$C(x)=A(x).B(x)=(a_{m-1}x^{m-1}+...+a_0).(b_{m-1}x^{m-1}+...+b_0)=c_{2m-2}x^{2m-2}+...+c_0$，其中$c_0=(a_0.b_0)mod 2,c_1=(a_1.b_0+a_0.b_1)mod 2,...,c_{2m-2}=(a_{m-1}.b_{m-1})mod 2$

注：通常在多项式乘法中$C(x)$的级数会大于$m−1$，因此需要对此进行化简，而化简的基本思想与素域内乘法情况相似：在素域$GF(p)$中，将两个整数相乘得到的结果除以一个素数，化简后的结果就是最后的余数。而在扩展域中进行的操作就是：将两个多项式相乘的结果除以一个不可约多项式，最后的结果就是最后的余数。(这里的不可约多项式大致可以看作一个素数)

GF(2^m)乘法

举例：

CRC多项式运算

在处理CRC算法时，你经常听到的单词是“多项式”。给定的CRC算法将被称为使用特定的多项式，而CRC算法通常被称为是使用多项式算法进行操作的，即数字10111对应于多项式$x^4+x^2+x+1$,而多项式之间的加法和减法都是异或运算（因为CRC多项式的系数属于GF(2),GF(2)加减法就是异或运算）——指数相同的项的系数进行异或。
而乘法运算则是在原有基础之上，还满足分配律。例如：

\[ \begin{align*} (x^3+x^2+x^0)(x^3+x^1+x^0)=&x^6+x^4+x^3 \\+&x^5+x^3+x^2 \\ +&x^3+x^1+x^0 \\= &x^6+x^5+x^4+x^3+x^2+x^1+x^0 \end{align*} \]

没有进位信号的二进制运算

在省略了多项式之后，我们可以专注于真正的算术问题，即CRC计算期间执行的所有算术都是在二进制中执行的，没有进位。这通常被称为多项式算术，但正如我在本文档的其余部分所声明的那样，我们必须称之为CRC算术。由于这个算法是CRC计算的关键部分，我们最好习惯它。

CRC算术中的两个数字相加与普通二进制算术中的数字相加相同，除了没有进位。这意味着每对对应的比特确定对应的输出比特，而不参考任何其他比特位置。例如：

\[ \begin{align*} &10011011 \\+ &11001010 \\= &01010001 \\ \\ \\ &10011011 \\- &11001010 \\= &01010001 \end{align*} \]

定义了加减法之后，就可以很容易地定义乘除法。例如乘法就与普通的二进制乘法类似，除了最后求和的时候，使用的是忽略进位的加法。而除法也与普通的二进制除法类似（不考虑借位，而且大小的判断也与二进制不一样，如果$X$最高位的1的位置大于或者等于$Y$最高位1的位置，则$X$大于等于$Y$）。

乘法示例：

\[ \begin{align*} 1101 \\ \times 1011 \\ --- \\ 1101 \\ 11010 \\ 000000 \\ 1101000 \\ ---- \\ 1111111 \end{align*} \]

除法示例：

\[ \require{enclose} \begin{array}{r} 1100001010\, \\[-3pt] 10011 \enclose{longdiv}{11010110110000} \\[-3pt] 10011\phantom{110110000\,} \\ -------- \\ 1001110110000\, \\ 10011\phantom{10110000\,} \\ ------- \\ 10110000\, \\ 10011\phantom{000\,} \\ ----- \\ 101000\, \\ 10011\phantom{0\,}\\ ----\\ 1110 \end{array}\\ \]

定义了乘除之后，就可以定义倍数和整除的概念了（其实就是除法的余数等于0）。但是根据其乘法的性质，还可以得到如下的推论。

倍数的推论

如果$A$是$B$的倍数，则意味着，$A$可以由$B$的不同移位的结果相加得到。

Example

$A=0111010110$，$B=11$，则$A$可以通过如下方式从$B$构造而来:

\[ \begin{align*} 0111010110 \\ =\phantom{00000000}11\phantom{0} \\ +\phantom{000000}11\phantom{0000} \\ +\phantom{00000}11\phantom{00000} \\ +\phantom{000}11\phantom{0000000} \\ \end{align*} \]

而如果$A$是$0111010111$，则无法通过$B$构造而来，因此就不能被B整除。

一个可行的示例

定义了上述的运算法则之后，特别是除法运算规则之后，我们就可以得到CRC算法了。

要执行CRC计算，我们需要选择一个除数。在数学营销中，除数被称为“生成多项式”或简称为“多项式”，是任何CRC算法的关键参数。你可以选择任何多项式，并提出CRC算法。然而，有些多项式比其他多项式更好，所以明智的做法是坚持使用经过测试的多项式。稍后的部分将讨论这个问题。

多项式的宽度（最高位的1所处的位置，例如10011的宽度就是4，而不是5）是很重要的，因为它主导着整个计算，通常来说，16或者32的宽度比较常用，因为可以简化现代计算机实现。为了示例的目的，我选择多项式10011（$W$等于4）作为演示。

选择好多项式之后，就可以进行CRC计算了（就是CRC除法），需要注意的是，在进行除法之前，需要在原始消息的末尾添加$W$位的0(这么做的原因是，除法会得到$W$位的余数¹，而将得到的余数替换增加的$W$位0之后，就可以被整除了)

例如：

原始信息：1101011011
多项式：10011
补0后的信息：11010110110000

至此，就可以使用CRC除法，来将补0后的信息来除以多项式。

\[ \begin{align*} 1100001010\, & = 商（没人关心这个结果）\\[-3pt] 多项式=10011\enclose{longdiv}{11010110110000}& = 补0后的消息数据\\[-3pt] 10011\phantom{110110000\,} \\ -------- \\ 1001110110000\, \\ 10011\phantom{10110000\,} \\ ------- \\ 10110000\, \\ 10011\phantom{000\,} \\ ----- \\ 101000\, \\ 10011\phantom{0\,}\\ ----\\ 1110 & = 余数 = 校验数据 \end{align*} \]

因此最终用发送的消息是11010110111110

而在另一端的接收方需要做如下两件事情中的一件：

分开消息与校验信息，计算消息的校验信息（需要补$W$位0），然后比较校验信息是否一致。
对收到的数据整体计算校验信息（就是除以多项式，而且不用补0），然后看得到的校验信息是否为0（余数是否等于0）

总结

CRC算法的整个运作流程如下：
1. 确定宽度$W$和多项式$G$(宽度为$W$)
2. 添加$W$比特的0到消息的末尾，称之为$M^{\prime}$
3. 使用CRC除法，用$G$来除$M^{\prime}$，余数就是校验和

多项式的选择

选择多项式有点像一门黑魔法，读者可以参考[Tanenbaum81]²（第130-132页），其中对这个问题进行了非常清晰的讨论。本节主要针对于想要了解构建自己的多项式的人。如果你不关心为什么一个poly可能比另一个好，只是想了解高速实现，请选择本节末尾列出的算术上合理的poly之一，然后跳到下一节。

首先，我们可以发现，经过CRC之后，发送的数据$T$是多项式的倍数，而如果传输途中受到了干扰，则接收方收到的数据是$T+E$，其中$E$是干扰向量，$+$是CRC加法（即XOR）。当接收机收到消息$T+E$后，则会将其除以多项式$G$，由于$T \mod G = 0$，因此$(T+E) \mod G = E \mod G$，因此我们所选多项式的检错能力取决于多项式$G$的倍数集，因为只要干扰向量$E$是多项式$G$的倍数，错误就不会被检测出来。所以我们的任务就是去找到一类$G$，使得它的倍数集尽可能与线路的噪声不一致。

我们可以假设有如下类型的线路噪声：

单比特错误

单比特错误意味着$E=1000\cdots 0000$，面对这类错误，只要确保$G$至少有两比特1，就一定能够检测出来。因为通过对$G$移位求和的方式，无法从多个1构建出只有一个1。

两比特错误

为了检测出形如$E=100\cdots 000100 \cdots 000$的错误（$E$包含两比特的1），$G$的倍数当中不能包含$11,101,1001,10001,100001,\dots$等数字，我不知道如何构建这类$G$，但是Tanenbaum说这类$G$确实存在，并且他提供了一个例子——$G=x^{15}+x^{14}+1$无法整除任何等于$x^k+1$的数，只要$k$小于$32768$。

奇数位错误

为了检测出奇数位错误，我们可以选择具有偶数个1的生成多项式。之所以可以这么做的原因如下：

解释

CRC乘法就是将一个常数的各种移位结果进行XOR。
如果一个数$G$有偶数个1，然后使用$G$异或数$M$，其得到的结果与$M$中1的个数的奇偶性相同，即使用$G$来异或一个数，不会改变数中1个数的奇偶性。

大部分流行的CRC多项式都包含偶数个1（Tanenbaum说，所有奇数比特的错误都可以通过将G设为11的倍数来捕获）。

突发错误

长度为$k$的突发错误可以表示为$E=x^i(x^{k-1}+\cdots +1)$，其中$i$表示突发错误在接受帧中的起始位置，且假设消息中的校验位有$r$比特（生成多项式$G$的度为$r$，其二进制表示的宽度为$r+1$），依据突发错误的长度，可分为以下几种类型：

如果 $k < r+1$

当$G$包含项$x^0$时，$x^i$就不是$G$的因子（$i=0$时，没有该项，因此就可以不考虑$x^i$），如果此时$x^{k-1}+\cdots +1$的度要小于$G$的度，则$E \mod G \neq 0$，因此错误可以被检测到。

所以总的来说，当$G$包含项$x^0$时，只要满足$k \leq r$的突发错误，都可以被检测出来。

如果 $k = r+1$

当且仅当$x^{k-1}+\cdots +1=G$时，$E \mod G = 0$，由于其首尾两位恒为$1$，因此是否与$G$相等主要取决于中间的$r-1$比特，如果假设中间的每一比特发生错误的概率都是$1/2$，那么无法检测出错误的概率就是$(\frac{1}{2})^{r-1}$。

如果 $k > r+1$ 或者多个短的突发错误发生

无法检测出错误的概率为$(\frac{1}{2})^{r}$。

一些流行的多项式
校验位位数	多项式	应用场景
16	（16,12,5,0）	X25 standard
16	（16,15,2,0）	CRC-16
32	(32,26,23,22,16,12,11,10,8,7,5,4,2,1,0)	Ethernet

常用CRC连接

一种简单的CRC实现（SIMPLE）

要实现CRC算法，我们所要做的就是实现CRC除法，而CRC除法的运算过程中，消息的比特流被馈送到除法寄存器当中，因此在下面的讨论中，消息被当作字节流（每个字节8 bits,bit 7时MSB），而字节流中数据的馈送顺序为——第一个字节的MSB(bit 7)到第一个字节的LSB(bit 0)，然后第二个字节，并且依此类推。

为了描述方便，这里选择多项式为$10111$（$W=4$）,其结构如下图所示：

Augmented message : the raw message followed by $W$ zero bits

除法流程如下:

将寄存器初始化为全0
在原始消息的后面补充W位0
While(还有消息比特)
    Begin
        将寄存器中的内容左移一位，寄存器最低位补上剩余消息的首位
        IF(上一步左移时，Pop的数据等于1)
            Register = Register XOR Poly
    End
当前寄存器的值就是余数，即校验码

Note

在实际实现中，IF当中的条件可以使用其他判据。例如，在移位之前，判断寄存器最高位是否等于1

基于表的CRC实现（TABLE ALGORITHM）

上面的SIMPLE算法是一个很好的起点，因为它直接对应于到目前为止提出的理论。然而，由于它是在位级别操作的，因此编写代码（即使是在C中）也相当笨拙，执行效率也很低（它必须为每个位循环一次）。为了加快速度，我们需要找到一种方法，使算法能够以大于一位的单位处理消息。候选数量是半字节（4位）、字节（8位）、字（16位）和长字（32位），甚至更长。其中，最好避免4位，因为它不对应于字节边界。至少，任何加速都应该允许我们在字节边界上操作。事实上，大多数表驱动算法一次操作一个字节。

为了便于讨论，让我们从4位poly切换到32位poly。我们的寄存器看起来几乎一样，除了方框代表字节而不是位，Poly是33位（最高位是隐式的1）（$W=32$）。

在这个框图中，SIMPLE算法仍然适用，我们可以在这个模型当中使用上面的SIMPLE算法，然后推导出基于表实现的算法。想象一下，SIMPLE算法正在全面展开，并考虑32位寄存器（字节3）的前8位的值是$t_7,t_6,t_5,t_4,t_3,t_2,t_1,t_0$

在SIMPLE算法的下一次迭代中，$t_7$决定了寄存器中的值是否需要与Poly进行异或（$t_7=1$，则需要异或），假设Poly的最高八位是$g_7,g_6,\cdots,g_0$(剩下的32位中的最高八位)，因此迭代之后，最高字节的值为：

\[ \begin{align*} t_6& \quad& t_5& \quad& t_4& \quad& t_3& \quad& t_2& \quad& t_1& \quad& t_0& \quad& ??& \\ + \ t_7 \ *(g_7& \quad& g_6& \quad& g_5& \quad& g_4& \quad& g_3& \quad& g_2& \quad& g_1& \quad& g_0&) \qquad ps:\ +=XOR \end{align*} \]

因此下一次迭代中的最高位为$t_6+t_7*g_7$，因此依据递归的方法，我们可以算出前8次（亦或是16，32，可以自定，这里以8举例）迭代时，寄存器中的最高位。而依据这八个值，就可以算出这八次迭代对寄存器的影响（Poly各种移位结果进行异或）。至此我们可以发现如下特性：

寄存器的最高字节已经无关紧要了，就算被移出寄存器也无妨
由Poly各种移位结果（8种）进行异或产生的数据$T$长度为$32+8$，根据长除法的运算过程可知，$T$的高$8$位对当前的余数不产生影响，因此只需要取其低$32$位即可

因此在经历过这8次迭代之后，剩下的余数为$\{Register[23:0],剩余消息的最高字节\} \oplus T[32:0]$。然后重复流程（计算T,向左移位，XOR）直到剩余消息为空，就得到了校验结果。

其运行的伪代码如下：

While(Augmented message非空)
    Begin
        查看寄存器的最高字节，根据其生成控制字节
        根据控制字节产生不同偏移量的Poly,并将其全部进行异或，得到的结果记为T
        将Register左移一个字节，并且将消息的最高字节读入Register的最低字节
        将T低32为与Register进行异或，并将结果写入Register
    End
当前寄存器的值就是余数，即校验码

就目前而言，这并不比SIMPLE算法好多少。然而，事实证明，大多数计算都可以预先计算并存储到表中。因此，上述算法可以简化为：

While(Augmented message非空)
    Begin
        Top = top_byte(Register);
        Register = (Register <<8 | next_Augmented_message_byte);
        Register = Register XOR precomputed_table[Top];
    End
当前寄存器的值就是余数，即校验码

如果你理解了这个伪代码的含义，你就掌握了表驱动CRC算法的主要思想。以上是一种非常有效的算法，只需要移位、OR、XOR和以字节为地址的表查找。从图形上看，它看起来像这样：

其参考C代码如下:

r=0; 
while (len--) 
{ 
    byte t = (r >> 24) & 0xFF; 
    r = (r << 8) | *p++; 
    r^=table[t]; 
}

// 优雅版
r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];

其中len是补0后消息的长度（以字节为单位），p指向增强消息，r是寄存器，t是临时的，table是计算表。

基于表的CRC实现（DIRECT TABLE ALGORITHM）

尽管上述的代码只有一行，有一种简洁的美，但是就效率而言，其仍然有优化空间。因为上面基于表的CRC实现的循环判断条件是基于拓展后的消息是否为空，这就导致了需要额外的$\frac{W}{8}$次循环，现在需要做的就是想办法去避免处理后面补充的零字节。

现在我们回顾一下原本的基于表的CRC实现，其框图如下：

从中我们可以发现如下几点：

TAIL

额外添加的$\frac{W}{8}=4$个字节的0也会和Raw Message一样，从右边一个字节一个字节得送入寄存器当中，然而由于其值是0，因此对于Register值没有影响；而且由于最后的$W=32$比特也不会从Register的左侧移出去，因此不会被用作地址来查表。其根本作用就是为了额外进行$\frac{W}{8}=4$次迭代，直到所有的Raw Messaage都穿过Register。

HEAD

如果寄存器的初始值为0，那么前4次迭代的唯一作用就是将消息的前4个字节完全移入寄存器（因为前32比特都是0，查表得到的值都是0，从而在XOR操作中不改变寄存器的值）。即使寄存器的初始值不是0，前4次迭代的也是将消息的前4个自己完全移入寄存器，然后与一个常数（与寄存器的初值相关）进行异或。

结合异或的运算性质$(A \oplus B) \oplus C = A \oplus (B \oplus C)$，我们可以假装我们现在处于已经迭代了4次时的状态，即寄存器当中的值为$Raw Message \oplus C$，其中$C$就是上面说的与寄存器初值相关的常数，用于记录除法对于$Raw Message$的影响。因此我们可以将$Raw Message$单独拎出来，使得寄存器中存储$C$，并且将后续除法产生的对$Raw Message$的影响都归并到$C$中，这就使得$(Raw Message << i) \oplus C$（i从0开始，每迭代以此增加1）等于原本基于表实现的算法当中的寄存器的值。从而可以得到如下的算法流程图。

Note

从上述的定义不难看出，寄存器的初值$C$是原先基于表的CRC算法经过4次迭代所产生的四次查表结果的不同offset进行异或得到的。其数值可以通过下面的方法计算出来。

设原来基于表实现的CRC算法当中Register的初始值为$I_r$，而当前算法中Register的初始值为$C$，那么$C$在数值上等于以0为初值，$I_r$为Message的CRC校验值。
而且如果$I_r$全为0，则$C$也是全为零

本算法的C代码如下所示：

// r: Register
// len: length of Raw message(unit is byte)
// p: point to Raw message
// t: look up table
r=0; while (len--) r = (r <<8 ) ^ t[(r >> 24) ^ *p++];

// 原来的基于表实现，放在这里是为了进行对比
// r: Register
// len: length of Augmented message(unit is byte)
// p: point to Augmented message
// t: look up table
r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];

与原来的算法相比，这个算法的循环次数要少4次。

REFLECTED algorithm

Question

如果这一章没有看明白，可以结合后面的代码实现，会容易理解很多

尽管上述代码可能已经尽可能地优化了，但这并没有阻止一些有进取心的人把事情变得更加复杂。要了解这是如何发生的，我们必须进入硬件世界。

定义

一个值或者寄存器的反射（Reflected）就是按位进行颠倒，例如：

原始值	反射之后的值
0101	1010
0011	1100
0111-0101-1010-1111-0010-0101-1011-1100	0011-1101-1010-0100-1111-0101-1010-1110

事实证明，UART（那些执行串行IO的方便的小芯片）习惯于首先传输最低有效位（位0），最后传输最高有效位（位数7）的每个字节（即反射）。这种约定的一个效果是，构建在比特级运行的硬件CRC计算器的硬件工程师需要计算字节流的CRC，每个字节都反映在其内部。字节以相同的顺序处理，但每个字节中的位被交换；位0现在是位7，位1现在是位6，以此类推。详细描述如下：

需要发送的原始消息如下图所示：

根据上述的发送数据的原则，最先发送的是Byte3的LSB，因此经过CRC之后，线路上的数据如下图所示，其中$CheckSum=CRC(\{reflect(Byte3),reflect(Byte2),reflect(Byte1),reflect(Byte0)\})$，至于为什么CheckSum没有被反射，这是由于硬件CRC的性质决定的。

而硬件传递给软件的数据则是：

如果这个约定仅限于硬件领域，这就没什么关系了。然而，在某些时候，这些CRC值可能需要软件来处理，因此必须有人编写一些与硬件CRC兼容的代码。

在这个处境当中，一个正常的软件工程师只需要先将每一个字节反射，然后进行处理就行了。但是，总有些不正常的人，这些人将不反射输入字节，然而反射其他所有的东西。

Note

The table is identical to the one in the previous algorithm except that each entry has been reflected（table_reflected[i] = reflect(table[reflect(i)])）.
The initial value of the register is the same as in the previous algorithm except that it has been reflected.
The bytes of the message are processed in the same order as before (i.e. the message itself is not reflected).
The message bytes themselves don't need to be explicitly reflected, because everything else has been!

例如下面就是REFLECTED algorithm和正常算法的表的区别，其关系满足上面所说的公式关系：

/*****************************************************************/
/*                                                               */
/* CRC LOOKUP TABLE                                              */
/* ================                                              */
/* The following CRC lookup table was generated automagically    */
/* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
/* Program V1.0 using the following model parameters:            */
/*                                                               */
/*    Width   : 4 bytes.                                         */
/*    Poly    : 0x04C11DB7L                                      */
/*    Reverse : FALSE.                                           */
/*                                                               */
/* 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 the FTP archive "ftp.adelaide.edu.au/pub/rocksoft".        */
/*                                                               */
/*****************************************************************/

unsigned long  crctable[256] =
{
 0x00000000L, 0x04C11DB7L, 0x09823B6EL, 0x0D4326D9L,
 0x130476DCL, 0x17C56B6BL, 0x1A864DB2L, 0x1E475005L,
 0x2608EDB8L, 0x22C9F00FL, 0x2F8AD6D6L, 0x2B4BCB61L,
 0x350C9B64L, 0x31CD86D3L, 0x3C8EA00AL, 0x384FBDBDL,
 0x4C11DB70L, 0x48D0C6C7L, 0x4593E01EL, 0x4152FDA9L,
 0x5F15ADACL, 0x5BD4B01BL, 0x569796C2L, 0x52568B75L,
 0x6A1936C8L, 0x6ED82B7FL, 0x639B0DA6L, 0x675A1011L,
 0x791D4014L, 0x7DDC5DA3L, 0x709F7B7AL, 0x745E66CDL,
 0x9823B6E0L, 0x9CE2AB57L, 0x91A18D8EL, 0x95609039L,
 0x8B27C03CL, 0x8FE6DD8BL, 0x82A5FB52L, 0x8664E6E5L,
 0xBE2B5B58L, 0xBAEA46EFL, 0xB7A96036L, 0xB3687D81L,
 0xAD2F2D84L, 0xA9EE3033L, 0xA4AD16EAL, 0xA06C0B5DL,
 0xD4326D90L, 0xD0F37027L, 0xDDB056FEL, 0xD9714B49L,
 0xC7361B4CL, 0xC3F706FBL, 0xCEB42022L, 0xCA753D95L,
 0xF23A8028L, 0xF6FB9D9FL, 0xFBB8BB46L, 0xFF79A6F1L,
 0xE13EF6F4L, 0xE5FFEB43L, 0xE8BCCD9AL, 0xEC7DD02DL,
 0x34867077L, 0x30476DC0L, 0x3D044B19L, 0x39C556AEL,
 0x278206ABL, 0x23431B1CL, 0x2E003DC5L, 0x2AC12072L,
 0x128E9DCFL, 0x164F8078L, 0x1B0CA6A1L, 0x1FCDBB16L,
 0x018AEB13L, 0x054BF6A4L, 0x0808D07DL, 0x0CC9CDCAL,
 0x7897AB07L, 0x7C56B6B0L, 0x71159069L, 0x75D48DDEL,
 0x6B93DDDBL, 0x6F52C06CL, 0x6211E6B5L, 0x66D0FB02L,
 0x5E9F46BFL, 0x5A5E5B08L, 0x571D7DD1L, 0x53DC6066L,
 0x4D9B3063L, 0x495A2DD4L, 0x44190B0DL, 0x40D816BAL,
 0xACA5C697L, 0xA864DB20L, 0xA527FDF9L, 0xA1E6E04EL,
 0xBFA1B04BL, 0xBB60ADFCL, 0xB6238B25L, 0xB2E29692L,
 0x8AAD2B2FL, 0x8E6C3698L, 0x832F1041L, 0x87EE0DF6L,
 0x99A95DF3L, 0x9D684044L, 0x902B669DL, 0x94EA7B2AL,
 0xE0B41DE7L, 0xE4750050L, 0xE9362689L, 0xEDF73B3EL,
 0xF3B06B3BL, 0xF771768CL, 0xFA325055L, 0xFEF34DE2L,
 0xC6BCF05FL, 0xC27DEDE8L, 0xCF3ECB31L, 0xCBFFD686L,
 0xD5B88683L, 0xD1799B34L, 0xDC3ABDEDL, 0xD8FBA05AL,
 0x690CE0EEL, 0x6DCDFD59L, 0x608EDB80L, 0x644FC637L,
 0x7A089632L, 0x7EC98B85L, 0x738AAD5CL, 0x774BB0EBL,
 0x4F040D56L, 0x4BC510E1L, 0x46863638L, 0x42472B8FL,
 0x5C007B8AL, 0x58C1663DL, 0x558240E4L, 0x51435D53L,
 0x251D3B9EL, 0x21DC2629L, 0x2C9F00F0L, 0x285E1D47L,
 0x36194D42L, 0x32D850F5L, 0x3F9B762CL, 0x3B5A6B9BL,
 0x0315D626L, 0x07D4CB91L, 0x0A97ED48L, 0x0E56F0FFL,
 0x1011A0FAL, 0x14D0BD4DL, 0x19939B94L, 0x1D528623L,
 0xF12F560EL, 0xF5EE4BB9L, 0xF8AD6D60L, 0xFC6C70D7L,
 0xE22B20D2L, 0xE6EA3D65L, 0xEBA91BBCL, 0xEF68060BL,
 0xD727BBB6L, 0xD3E6A601L, 0xDEA580D8L, 0xDA649D6FL,
 0xC423CD6AL, 0xC0E2D0DDL, 0xCDA1F604L, 0xC960EBB3L,
 0xBD3E8D7EL, 0xB9FF90C9L, 0xB4BCB610L, 0xB07DABA7L,
 0xAE3AFBA2L, 0xAAFBE615L, 0xA7B8C0CCL, 0xA379DD7BL,
 0x9B3660C6L, 0x9FF77D71L, 0x92B45BA8L, 0x9675461FL,
 0x8832161AL, 0x8CF30BADL, 0x81B02D74L, 0x857130C3L,
 0x5D8A9099L, 0x594B8D2EL, 0x5408ABF7L, 0x50C9B640L,
 0x4E8EE645L, 0x4A4FFBF2L, 0x470CDD2BL, 0x43CDC09CL,
 0x7B827D21L, 0x7F436096L, 0x7200464FL, 0x76C15BF8L,
 0x68860BFDL, 0x6C47164AL, 0x61043093L, 0x65C52D24L,
 0x119B4BE9L, 0x155A565EL, 0x18197087L, 0x1CD86D30L,
 0x029F3D35L, 0x065E2082L, 0x0B1D065BL, 0x0FDC1BECL,
 0x3793A651L, 0x3352BBE6L, 0x3E119D3FL, 0x3AD08088L,
 0x2497D08DL, 0x2056CD3AL, 0x2D15EBE3L, 0x29D4F654L,
 0xC5A92679L, 0xC1683BCEL, 0xCC2B1D17L, 0xC8EA00A0L,
 0xD6AD50A5L, 0xD26C4D12L, 0xDF2F6BCBL, 0xDBEE767CL,
 0xE3A1CBC1L, 0xE760D676L, 0xEA23F0AFL, 0xEEE2ED18L,
 0xF0A5BD1DL, 0xF464A0AAL, 0xF9278673L, 0xFDE69BC4L,
 0x89B8FD09L, 0x8D79E0BEL, 0x803AC667L, 0x84FBDBD0L,
 0x9ABC8BD5L, 0x9E7D9662L, 0x933EB0BBL, 0x97FFAD0CL,
 0xAFB010B1L, 0xAB710D06L, 0xA6322BDFL, 0xA2F33668L,
 0xBCB4666DL, 0xB8757BDAL, 0xB5365D03L, 0xB1F740B4L
};

/*****************************************************************/
/*                   End of CRC Lookup Table                     */
/*****************************************************************/



/*****************************************************************/
/*                                                               */
/* CRC LOOKUP TABLE                                              */
/* ================                                              */
/* The following CRC lookup table was generated automagically    */
/* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
/* Program V1.0 using the following model parameters:            */
/*                                                               */
/*    Width   : 4 bytes.                                         */
/*    Poly    : 0x04C11DB7L                                      */
/*    Reverse : TRUE.                                            */
/*                                                               */
/* 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 the FTP archive "ftp.adelaide.edu.au/pub/rocksoft".        */
/*                                                               */
/*****************************************************************/

unsigned long  crctable[256] =
{
 0x00000000L, 0x77073096L, 0xEE0E612CL, 0x990951BAL,
 0x076DC419L, 0x706AF48FL, 0xE963A535L, 0x9E6495A3L,
 0x0EDB8832L, 0x79DCB8A4L, 0xE0D5E91EL, 0x97D2D988L,
 0x09B64C2BL, 0x7EB17CBDL, 0xE7B82D07L, 0x90BF1D91L,
 0x1DB71064L, 0x6AB020F2L, 0xF3B97148L, 0x84BE41DEL,
 0x1ADAD47DL, 0x6DDDE4EBL, 0xF4D4B551L, 0x83D385C7L,
 0x136C9856L, 0x646BA8C0L, 0xFD62F97AL, 0x8A65C9ECL,
 0x14015C4FL, 0x63066CD9L, 0xFA0F3D63L, 0x8D080DF5L,
 0x3B6E20C8L, 0x4C69105EL, 0xD56041E4L, 0xA2677172L,
 0x3C03E4D1L, 0x4B04D447L, 0xD20D85FDL, 0xA50AB56BL,
 0x35B5A8FAL, 0x42B2986CL, 0xDBBBC9D6L, 0xACBCF940L,
 0x32D86CE3L, 0x45DF5C75L, 0xDCD60DCFL, 0xABD13D59L,
 0x26D930ACL, 0x51DE003AL, 0xC8D75180L, 0xBFD06116L,
 0x21B4F4B5L, 0x56B3C423L, 0xCFBA9599L, 0xB8BDA50FL,
 0x2802B89EL, 0x5F058808L, 0xC60CD9B2L, 0xB10BE924L,
 0x2F6F7C87L, 0x58684C11L, 0xC1611DABL, 0xB6662D3DL,
 0x76DC4190L, 0x01DB7106L, 0x98D220BCL, 0xEFD5102AL,
 0x71B18589L, 0x06B6B51FL, 0x9FBFE4A5L, 0xE8B8D433L,
 0x7807C9A2L, 0x0F00F934L, 0x9609A88EL, 0xE10E9818L,
 0x7F6A0DBBL, 0x086D3D2DL, 0x91646C97L, 0xE6635C01L,
 0x6B6B51F4L, 0x1C6C6162L, 0x856530D8L, 0xF262004EL,
 0x6C0695EDL, 0x1B01A57BL, 0x8208F4C1L, 0xF50FC457L,
 0x65B0D9C6L, 0x12B7E950L, 0x8BBEB8EAL, 0xFCB9887CL,
 0x62DD1DDFL, 0x15DA2D49L, 0x8CD37CF3L, 0xFBD44C65L,
 0x4DB26158L, 0x3AB551CEL, 0xA3BC0074L, 0xD4BB30E2L,
 0x4ADFA541L, 0x3DD895D7L, 0xA4D1C46DL, 0xD3D6F4FBL,
 0x4369E96AL, 0x346ED9FCL, 0xAD678846L, 0xDA60B8D0L,
 0x44042D73L, 0x33031DE5L, 0xAA0A4C5FL, 0xDD0D7CC9L,
 0x5005713CL, 0x270241AAL, 0xBE0B1010L, 0xC90C2086L,
 0x5768B525L, 0x206F85B3L, 0xB966D409L, 0xCE61E49FL,
 0x5EDEF90EL, 0x29D9C998L, 0xB0D09822L, 0xC7D7A8B4L,
 0x59B33D17L, 0x2EB40D81L, 0xB7BD5C3BL, 0xC0BA6CADL,
 0xEDB88320L, 0x9ABFB3B6L, 0x03B6E20CL, 0x74B1D29AL,
 0xEAD54739L, 0x9DD277AFL, 0x04DB2615L, 0x73DC1683L,
 0xE3630B12L, 0x94643B84L, 0x0D6D6A3EL, 0x7A6A5AA8L,
 0xE40ECF0BL, 0x9309FF9DL, 0x0A00AE27L, 0x7D079EB1L,
 0xF00F9344L, 0x8708A3D2L, 0x1E01F268L, 0x6906C2FEL,
 0xF762575DL, 0x806567CBL, 0x196C3671L, 0x6E6B06E7L,
 0xFED41B76L, 0x89D32BE0L, 0x10DA7A5AL, 0x67DD4ACCL,
 0xF9B9DF6FL, 0x8EBEEFF9L, 0x17B7BE43L, 0x60B08ED5L,
 0xD6D6A3E8L, 0xA1D1937EL, 0x38D8C2C4L, 0x4FDFF252L,
 0xD1BB67F1L, 0xA6BC5767L, 0x3FB506DDL, 0x48B2364BL,
 0xD80D2BDAL, 0xAF0A1B4CL, 0x36034AF6L, 0x41047A60L,
 0xDF60EFC3L, 0xA867DF55L, 0x316E8EEFL, 0x4669BE79L,
 0xCB61B38CL, 0xBC66831AL, 0x256FD2A0L, 0x5268E236L,
 0xCC0C7795L, 0xBB0B4703L, 0x220216B9L, 0x5505262FL,
 0xC5BA3BBEL, 0xB2BD0B28L, 0x2BB45A92L, 0x5CB36A04L,
 0xC2D7FFA7L, 0xB5D0CF31L, 0x2CD99E8BL, 0x5BDEAE1DL,
 0x9B64C2B0L, 0xEC63F226L, 0x756AA39CL, 0x026D930AL,
 0x9C0906A9L, 0xEB0E363FL, 0x72076785L, 0x05005713L,
 0x95BF4A82L, 0xE2B87A14L, 0x7BB12BAEL, 0x0CB61B38L,
 0x92D28E9BL, 0xE5D5BE0DL, 0x7CDCEFB7L, 0x0BDBDF21L,
 0x86D3D2D4L, 0xF1D4E242L, 0x68DDB3F8L, 0x1FDA836EL,
 0x81BE16CDL, 0xF6B9265BL, 0x6FB077E1L, 0x18B74777L,
 0x88085AE6L, 0xFF0F6A70L, 0x66063BCAL, 0x11010B5CL,
 0x8F659EFFL, 0xF862AE69L, 0x616BFFD3L, 0x166CCF45L,
 0xA00AE278L, 0xD70DD2EEL, 0x4E048354L, 0x3903B3C2L,
 0xA7672661L, 0xD06016F7L, 0x4969474DL, 0x3E6E77DBL,
 0xAED16A4AL, 0xD9D65ADCL, 0x40DF0B66L, 0x37D83BF0L,
 0xA9BCAE53L, 0xDEBB9EC5L, 0x47B2CF7FL, 0x30B5FFE9L,
 0xBDBDF21CL, 0xCABAC28AL, 0x53B39330L, 0x24B4A3A6L,
 0xBAD03605L, 0xCDD70693L, 0x54DE5729L, 0x23D967BFL,
 0xB3667A2EL, 0xC4614AB8L, 0x5D681B02L, 0x2A6F2B94L,
 0xB40BBE37L, 0xC30C8EA1L, 0x5A05DF1BL, 0x2D02EF8DL
};

/*****************************************************************/
/*                   End of CRC Lookup Table                     */
/*****************************************************************/

在执行结束之后，寄存器留下的值就相当于反射后的消息经过非反射的算法后所得到的结果，再对结果进行反射的值（即对应着Rocksoft模型中的Refin=TRUE和Refot=TRUE），如果没看明白可以看看后面的C代码。

多项式反转（Reversed Polys）

事实证明，一个好的多项式，其反射也是一个好的多项式。也就是说，如果$G=11101$有不错的效果，那么$G=10111$的效果也很好。因此，似乎每次一个组织（如CCITT）对一个特别好的多项式进行标准化时，在实际使用过程中，人们也不会放过该多项式的反射。因此，一组“标准”多项式有一组相应的反射，这些反射也在使用中。

为了避免迷惑，我们在这里称之为多项式反转（reversed poly）.

Example

标准	多项式
X25 standard	1-0001-0000-0010-0001
X25 reversed	1-0000-1000-0001-0001
CRC16 standard	1-1000-0000-0000-0101
CRC16 reversed	1-0100-0000-0000-0011

请注意，这里反射（反转）的是整个多项式，而不仅仅是底部的$W$位。这是一个重要的区别。在前一节描述的反射算法中，反射算法中使用的多项式实际上与非反射算法中的多项式的反射是反射底部的$W$位，而不包含最高位隐藏$1$。相比之下，反转多项式是包含最高位的$1$的。

初始化和最终值

除了上述复杂性之外，CRC算法在另外两个方面也有所不同：

寄存器初始值
输出异或值（与最终的寄存器值进行异或）

例如CRC32使用$FFFFFFFF$初始化寄存器，并且使用$FFFFFFFF$对最终的寄存器值进行异或。

大部分的CRC算法都将寄存器初始化为0，但是还是存在初始化为非0的情况。就理论上来说（messgage完全随机），初始值的选择不影响CRC 算法的有效性，初始值仅仅提供了一个寄存器值开始运算的固定起点。然而，在实践中，有些信息出现的可能性要更高，因此把CRC 寄存器初始化为一个不太可能在实际中出现“盲点” 的值是更明智的。“盲点” 是指一系列不会导致CRC 寄存器值变化的信息字节。特别是当CRC 寄存器被初始化为0 时就具有“零盲点”，当它运行的时候就不知道前面有多少个零字节。而零字节在实际应用中充当信息的前导字节是非常普遍的，所以把CRC 寄存器初始化为非零值是一个明智的做法。

算法的定义

至此，我们已经介绍了表驱动CRC算法的所有不同方面。由于这些算法有很多变体，因此值得尝试为它们建立一个命名法。这就是本章节的目的。

从上面的讨论我们可以看出，CRC算法主要由下面几个参数决定：

多项式的宽度
多项式的值
寄存器的初始值
输入数据的每个字节是否需要反射
算法是直接表算法（DIRECT TABLE ALGORITHM）还是间接表算法(TABLE ALGORITHM)
最终寄存器的值是否需要被反射
输出异或值（与最终CRC值进行异或）

为了能够讨论特定的CRC算法，我们需要能够更精确地定义它们。因此，下一节将尝试为CRC算法提供一个定义良好的参数化模型。要引用特定的算法，我们只需根据模型的参数指定算法。

CRC参数化模型（Rocksoft™）

在本节中，我们定义了一个精确的参数化模型CRC算法，我们将称之为“Rocksoft™ Model CRC Algorithm”，这个模型最重要的一点就是它忽略了所有的具体实现，而只关注于功能。而构建这么一个模型则是为了能够精确引用特定的CRC算法，而不用管其具体实现是多么的复杂和混乱。因此模型应该简单精确，不会造成混淆。

Important

Rocksoft™模型本质上是基于DIRECT TABLE ALGORITHM的，但是该模型也被进一步参数化了，使得其能够表征更加复杂的和混乱的现实算法

为了能够表征反射算法，本模型提供了两个bool值选项，其中一个用来控制输入字节是否反射，另一个用来控制输出的校验值是否反射。还有一个参数用于指定寄存器的初始值，已经一个用于指定输出异或值的参数。

总的来说Rocksoft™模型的参数如下表：

Rocksoft™模型参数表
参数名称	参数类型	参数意义
NAME	字符串	算法的名称
WIDTH	十进制数	算法宽度（以bit为单位）。比多项式的位数少1，因为多项式首字节有隐藏的1
POLY	十六进制数	多项式所对应的二进制数的十六进制表示，并且忽略最高位的1，例如多项式$10110$则表示为$06$
INIT	十六进制数	DIRECT TABLE ALGORITHM中的寄存器初值。如果使用的是TALBE ALGORITHM则需要将其转换，才能使结果一致
REFIN	布尔值	如果等于True，则反射输入Message的每个字节
REFOUR	布尔值	如果等于False，则直接将寄存器中的值送入XOR阶段，否则，先将寄存器中的值进行反射，然后送入XOR阶段
XOROUT	十六进制数	$W$ bit宽的数，将异或之后的结果作为最终的校验值
CHECK	十六进制数	这个不是必须的，主要是用来作为检查的，其值等于上述参数描述的算法，对字符串"123456789"产生的校验值

定义了这些参数后，该模型现在可用于精确指定特定的CRC算法。以下是CRC-16算法的一种流行形式的示例规范。

参数名称	参数值
NAME	“CRC-16”
WIDTH	16
POLY	8005
INIT	0000
REFIN	True
REFOUR	True
XOROUT	0000
CHECK	BB3D

以及CRC-32算法（据说是用于PKZip, AUTODIN II, Ethernet, 和 FDDI）。

参数名称	参数值
Name	"CRC-32"
Width	32
Poly	04C11DB7
Init	FFFFFFFF
RefIn	True
RefOut	True
XorOut	FFFFFFFF
Check	CBF43926

Rocksoft™模型的参考实现

这是用C编程语言实现的模型算法。该实现由一个头文件（.h）和一个实现文件（.c）组成。如果想验证本代码的正确性，可以将其配置称上述的CRC-16和CRC-32，然后使用“123456789”作为message，然后将产生的结果与上述表中的Check进行比较。

crcmodel.h

/******************************************************************************/
/*                             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

typedef unsigned long ulong;
typedef unsigned bool;
typedef unsigned char* 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.                      */
typedef struct
{
    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;
typedef cm_t* p_cm_t;

/******************************************************************************/

/* Functions That Implement The Model */
/* ---------------------------------- */
/* The following functions animate the cm_t abstraction. */

void cm_ini(p_cm_t p_cm);
/* Initializes the argument CRC model instance.          */
/* All parameter fields must be set before calling this. */

void cm_nxt(p_cm_t p_cm, int ch);
/* Processes a single message byte [0,255]. */

void cm_blk(p_cm_t p_cm, p_ubyte_ blk_adr, ulong blk_len);
/* Processes a block of message bytes. */

ulong cm_crc(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_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                              */
/******************************************************************************/

crcmodel.c

/******************************************************************************/
/*                             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

/******************************************************************************/

/* Returns the value v with the bottom b [0,32] bits reflected. */
/* Example: reflect(0x3e23L,3) == 0x3e26                        */
LOCAL ulong reflect(ulong v, int b);
LOCAL ulong reflect(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;
}

/******************************************************************************/

/* Returns a longword whose value is (2^p_cm->cm_width)-1.     */
/* The trick is to do this portably (e.g. without doing <<32). */
LOCAL ulong widmask(p_cm_t);
LOCAL ulong widmask(p_cm_t p_cm)
{
    return (((1L << (p_cm->cm_width - 1)) - 1L) << 1) | 1L;
}

/******************************************************************************/

void cm_ini(p_cm_t p_cm)
{
    p_cm->cm_reg = p_cm->cm_init;
}

/******************************************************************************/

void cm_nxt(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);
    }
}

/******************************************************************************/

void cm_blk(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_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_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                              */
/******************************************************************************/

check.c

#include "crcmodel.h"
#include "stdio.h"
#include <assert.h>
#include <string.h>
int main()
{
    char* Benchmark = "123456789";
    printf("Checking CRC using string \"123456789\"\n");

    // CRC-16
    cm_t crc16 = {
        .cm_init = 0x0000,
        .cm_poly = 0x8005,
        .cm_refin = TRUE,
        .cm_refot = TRUE,
        .cm_width = 16,
        .cm_xorot = 0x0000
    };

    // CRC-32
    cm_t crc32 = {
        .cm_init = 0xffffffff,
        .cm_poly = 0x04c11db7,
        .cm_refin = TRUE,
        .cm_refot = TRUE,
        .cm_width = 32,
        .cm_xorot = 0xffffffff
    };

    p_cm_t p_crc16 = &crc16;
    p_cm_t p_crc32 = &crc32;

    // 设置初始化的值
    cm_ini(p_crc16);
    cm_ini(p_crc32);

    // 计算
    cm_blk(p_crc16, (unsigned char*)Benchmark, strlen(Benchmark));
    cm_blk(p_crc32, (unsigned char*)Benchmark, strlen(Benchmark));

    ulong checksum16 = cm_crc(p_crc16);
    ulong checksum32 = cm_crc(p_crc32);

    printf("crc 16 : 0x%lx\n", checksum16);
    printf("crc 32 : 0x%lx\n", checksum32);

    assert(checksum16 == 0xbb3d);
    assert(checksum32 == 0xcbf43926);

    printf("\e[1;32mcheck pass !!!\e[0m\n");

    return 0;
}

# 运行参考模型
run_reference:check.c crcmodel.c
	@gcc -g $^ -Wall -Werror -o reference && ./reference

# 生成查找表
gen_table:crctable.c crcmodel.c
	@gcc -g $^ -Wall -Werror -o gen_table && ./gen_table

# 运行表驱动算法
table_driven:crc32_table_driven.c gen_table
	@gcc -g $< -Wall -Werror -o table_driven && ./table_driven

all: run_reference table_driven

clean:
	rm crctable reference gen_table table_driven

基于表的CRC实现

尽管上面我介绍了很多细节用以理解和定义CRC算法，但是CRC的高速实现并没有那么复杂。总的来说，其高速实现其实只有两种形式——normal和reflected。其中normal向左移动寄存器（对应着Rocksoft模型中Refin=FALSE和Refot=FALSE），而reflected向右移动寄存器（对应着Rocksoft模型中Refin=TRUE和Refot=TRUE）。如果我们想要对应着Rocksoft模型中Refin=FALSE和Refot=TRUE，则只需要在normal的基础上，对其结果反射即可。而如果我们想要对应着Rocksoft模型中Refin=TRUE和Refot=FALSE，则只需要在reflected的基础上，对其结果进行反射即可。

一个32比特的CRC算法以及其reflected的其示例代码如下：

crc32_table_driven.c

// crc-32 parameter
#define XOROT 0Xffffffff
#define INIT 0Xffffffff
#define INIT_REFLECTED 0Xffffffff
#define CHECK 0XCBF43926

// this table is generated by crctable.c using crc-32 parameter
#include "crctable"
#include <assert.h>
#include <stdio.h>
#include <string.h>

// 32-bit normal form (the 16-bit form is similar).
unsigned long crc_normal(unsigned char* blk_adr, unsigned long blk_len)
{
    unsigned long crc = INIT;
    while (blk_len--)
        crc = crctable[((crc >> 24) ^ *blk_adr++) & 0xFFL] ^ (crc << 8);
    return crc ^ XOROT;
}

// Here is the reflected form:
unsigned long crc_reflected(unsigned char* blk_adr, unsigned long blk_len)
{
    unsigned long crc = INIT_REFLECTED;
    while (blk_len--)
        crc = crctable[(crc ^ *blk_adr++) & 0xFFL] ^ (crc >> 8);
    return crc ^ XOROT;
}

// check for validating
int main()
{
    printf("Check Algorithm by \"123456789\"\n");
    char* message = "123456789";
    unsigned long res = crc_reflected((unsigned char *)message, strlen(message));
    printf("crc result: %lx \n", res);
    assert(res == CHECK);
    printf("\e[1;32mCheck Pass !!!\e[0m\n");
}

生成查找表

上一节中的代码片段中中唯一缺少的组件是查找表。查找表可以在运行时使用前面给出的模型包的cm_tab函数计算，也可以预先计算并插入到C程序中。在任何一种情况下，都应该注意，查找表仅取决于POLY和RefIn参数。

下面的程序可以生成任何所需的32位或者16位查找表：

crctable.c

/******************************************************************************/
/*                             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 "crcmodel.h"
#include <stdio.h>
#include <stdlib.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                                                  */

// crc-32
#define TB_FILE "crctable"
#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))

/******************************************************************************/

/* If mess is non-empty, write it out and abort. Otherwise, check the error   */
/* status of outfile and abort if an error has occurred.                      */
LOCAL void chk_err(char*);
LOCAL void chk_err(char* mess)
{
    if (mess[0] != 0) {
        printf("%s\n", mess);
        exit(EXIT_FAILURE);
    }
    if (ferror(outfile)) {
        perror("chk_err");
        exit(EXIT_FAILURE);
    }
}

/******************************************************************************/

LOCAL void chkparam(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(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("\n");
        chk_err("");
    }
}

/******************************************************************************/

int main()
{
    printf("\n");
    printf("Rocksoft^tm Model CRC Algorithm Table Generation Program V1.0\n");
    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                              */
/******************************************************************************/

可用参考

Boudreau, Steen, "Cyclic Redundancy Checking by Program," AFIPS Proceedings, Vol. 39, 1971.

Davies, Barber, "Computer Networks and Their Protocols," J. Wiley & Sons, 1979.

Higginson, Kirstein, "On the Computation of Cyclic Redundancy Checks by Program," The Computer Journal (British), Vol. 16, No. 1, Feb 1973.

McNamara, J. E., "Technical Aspects of Data Communication," 2nd Edition, Digital Press, Bedford, Massachusetts, 1982.

Marton and Frambs, "A Cyclic Redundancy Checking (CRC) Algorithm," Honeywell Computer Journal, Vol. 5, No. 3, 1971.

Nelson M., "File verification using CRC", Dr Dobbs Journal, May 1992, pp.64-67.

Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE Micro, Aug 1988.

Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, pp.118-133.

Ward R.K, Tabandeh M., "Error Correction and Detection, A Geometric Approach" The Computer Journal, Vol. 27, No. 3, 1984, pp.246-253.

Wecker, S., "A Table-Lookup Algorithm for Software Computation of Cyclic Redundancy Check (CRC)," Digital Equipment Corporation memorandum, 1974.

[Griffiths87]³

[Knuth81]⁴

[Nelson91]⁵

[Sarwate88]⁶

[Tanenbaum81]⁷

CRC除法的性质决定的，而二进制除法则会得到$W+1$位的余数，因为除数的宽度是$W+1$↩︎
Tanenbaum, A.S., "Computer Networks", Prentice Hall, 1981, ISBN: 0-13-164699-0. Comment: Section 3.5.3 on pages 128 to 132 provides a very clear description of CRC codes. However, it does not describe table-driven implementation techniques.↩︎
Griffiths, G., Carlyle Stones, G., "The Tea-Leaf Reader Algorithm: An Efficient Implementation of CRC-16 and CRC-32", Communications of the ACM, 30(7), pp.617-620. Comment: This paper describes a high-speed table-driven implementation of CRC algorithms. The technique seems to be a touch messy, and is superceded by the Sarwete algorithm.↩︎
Knuth, D.E., "The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Section 4.6.↩︎
Nelson, M., "The Data Compression Book", M&T Books, (501 Galveston Drive, Redwood City, CA 94063), 1991, ISBN: 1-55851-214-4. Comment: If you want to see a real implementation of a real 32-bit checksum algorithm, look on pages 440, and 446-448.↩︎
Sarwate, D.V., "Computation of Cyclic Redundancy Checks via Table Look-Up", Communications of the ACM, 31(8), pp.1008-1013. Comment: This paper describes a high-speed table-driven implementation for CRC algorithms that is superior to the tea-leaf algorithm. Although this paper describes the technique used by most modern CRC implementations, I found the appendix of this paper (where all the good stuff is) difficult to understand.↩︎
Tanenbaum, A.S., "Computer Networks", Prentice Hall, 1981, ISBN: 0-13-164699-0. Comment: Section 3.5.3 on pages 128 to 132 provides a very clear description of CRC codes. However, it does not describe table-driven implementation techniques.↩︎

	\(3⁢x^3\)
\(2x^2+1\)	\(6x^5+x^4+2x^3-x^2-2\)
	\(x^4-x^3-x^2-2\)

	\(3x^3+0.5x^2\)
\(2x^2+1\)	\(6x^5+x^4+2x^3-x^2-2\)
	\(x^4-x^3-x^2-2\)
	\(-x^3-1.5x^2-2\)

	\(3x^3+0.5x^2-0.5x-0.75\)
\(2x^2+1\)	\(6x^5+x^4+2x^3-x^2-2\)
	\(x^4-x^3-x^2-2\)
	\(-x^3-1.5x^2-2\)
	\(-1.5x^2+0.5x-2\)
	\(0.5x-1.25\)