CRC 校验解析

一个 CRC 校验模型需要包含以下信息：

WIDTH，指 CRC 校验码的最终位数（二进制）
POLY，指用来做二进制除法的多项式。
INIT，指 CRC 的初始值。存在初始值是为了避免全 0 数据的校验码恒为 0。若初始值不为 0，则对于不同长度的全 0 数据，校验码一般也会不一样。
XOROUT，指最后对 CRC 校验码进行异或的数值。
REFIN，指是否对初始数据进行翻转。
REFOUT，指是否对输出数据进行翻转。

对于一些特定的、公开的模型，会有一个特定的名字。一般有模型的名字就可以知道其参数。比如 CRC4-ITU 代表的就是 WIDTH = 4, POLY = 0x03, INIT = 0x00, XOROUT = 0x00, REFIN = true, REFOUT = true 的一个 CRC 模型。

无论是有名字的模型还是没有名字的（自定义）模型，其框架都是一样的。所以我们可以先把代码框架搭建好。

class CRCCommon {
    public:
    	virtual const long long unsigned operator()(char(*nextData)(), size_t length) const=0; // 因为 CRC 对于数据是逐字节处理，所以每次获取的数据是 char 类型。使用函数指针，既可以兼容读取数组，也可以兼容直接从输入流获取数据。
    	long long unsigned file(FILE*) const; // 获取一个文件的校验码
};

template <unsigned WIDTH, long long unsigned POLY, long long unsigned INIT, long long unsigned XOROUT, bool REFIN, bool REFOUT>
class CRC : public CRCCommon {
    private:
    	CRC() {}
    public:
    	~CRC() {}
    	virtual const long long unsigned operator()(char(*nextData)(), size_t length); // 对于每个模型其计算方式不一样，所以每个子类需要用虚函数来实现该功能。
    	static CRC* getInstance() {
            // 每个实例会占用一个虚函数指针的空间。由于我们只需要使用 CRC 类的成员函数，不需要每次都定义一个实例。同时定义多个实例也会使得空间浪费。所以使用单例模式。
        	static CRC* crc = new CRC();
        	return crc;
    	}
};

为了更好理解 CRC 校验模型的原理并写出其代码，下面进行 CRC 手算。

比如说现在有这样一个模型：WIDTH = 5, POLY = 0xd, INIT = 0xf, XOROUT = 0x1, REFIN = false, REFOUT = true。而输入的数据是 0x1234。

CRC 对于数据是逐字节处理的。输入数据共分为两个字节，分别是 0x12 和 0x34。

定义 crc 表示校验码的值。初始时为 INIT = 0xf，然后异或第一字节，crc = 0xf ^ 0x12 = 0x1d = 0b00011101。

这个数可以看做多项式 \(x^4+x^3+x^2+x^0\) 在 \(x=2\) 时的取值。上述多项式若看做 \(4\) 次多项式，则其系数按照降幂排列则为 1, 1, 1, 0, 1，恰好是 0b11101 的二进制表示。若看做更高次多项式，如 \(9\) 次多项式，则其系数按照降幂应为 0, 0, 0, 0, 0, 1, 1, 1, 0, 1，变成二进制数则是 \(10\) 位二进制数 0b0000011101。

令二进制下 \(k\) 位数（包括前导 \(0\)）对应一个 \(k-1\) 次多项式，则 0b11101 对应多项式 \(x^4+x^3+x^2+x^0\)。而我们给定的多项式 POLY = 0xd，其实应该是 WIDTH = 5 次多项式，任何次数高于 \(5\) 的项系数都是 \(0\)，且 \(5\) 次项的系数必须是 \(1\)（这是人为规定的）。所以在表示 POLY 的时候，就偷懒不表示 \(5\) 次项系数了（根据 WIDTH = 5 即可补全 POLY）。所以 POLY 应该是 (1 << 5) | 0xd = 0x2d = 0b101101，它对应一个 \(5\) 次多项式。

而 CRC 校验的实质，就是求出原数据左移 WIDTH 位之后，对 POLY 进行二进制取模的结果。

若对多个字节进行校验，则将上一字节校验的结果作为 INIT，异或该字节数据后，对 POLY 进行取模，得到的结果作为该字节的校验结果。也可以认为 INIT 是第 \(0\) 字节校验的结果，然后对于每一字节的校验就是当前字节的数据异或上一字节的结果，再进行取模。

所以，若对多个字节进行校验，上一字节校验的结果必定是二进制下 WIDTH 位数，一个字节固定是二进制下 \(8\) 位数。若 WIDTH > 8，则异或后的结果至多是 WIDTH 位数，对应一个 WIDTH-1 次多项式。但 POLY 是 WIDTH 次多项式，取模的结果一定还是原数据。所以要先把原数据左移 WIDTH 位再进行取模。

接下来说说“二进制取模”是如何运算的。

首先看看正整数的取模。有这样一种方法：比如十进制下 \(1234\) 对 \(9\) 取模，先在 \(9\) 后面添若干个 \(0\)，使其变成不大于 \(1234\) 的最大的数，也就是 \(900\)，然后原数 \(1234\) 一直减去 \(900\) 直到不能再减，得到 \(334\)。

下一步，去掉一个 \(0\)，变成 \(90\)。然后 \(334\) 不断减去 \(90\)，可以得到 \(64\)。

最后，不停减去 \(9\)，得到 \(1\)，所以 \(1234\) 对 \(9\) 取模的结果就是 \(1\)。

二进制取模原理相似，但是运算是在二进制下进行的，而且“减法”变成了“按位异或”。

例如，上面原数据，先异或 INIT，再左移 WIDTH 位后为 0b1110100000，而多项式是 0b101101。先在 POLY 后面添加若干个 \(0\)，使得其首位和被除数首位对齐。虽然这个时候 POLY 的值已经大于原数据，但是我们采用的运算不是减法，而是按位异或，所以不会出现负数的情况。我们可以直接异或，因为首位（最高位）都是 \(1\)，所以异或的结果必然会小于当前 POLY（最高位异或结果为 \(0\)，异或的结果至少会比运算数少一位）。这样经过有限次运算之后，就可以得到一个小于 POLY 的数。这个数就是取模的结果。

比如说，用 x 代表原数据，p 表示多项式。则一开始

x = 0b1110100000
p = 0b101101 // 结尾的 0 省略不写
x = 0b 101110 // 异或运算的结果，和原始数据位对齐。整数除法的竖式也是位对齐的，不是吗？
p = 0b 101101
x = 0b     11000 // 已经小于原始多项式（即没有在后面补 0 的），所以运算结束

因此，x 对 p 取模的结果就是十进制下的 \(24\)。

然后再把 \(24\) 异或下一个字节的数据 0x34，继续对 POLY 取模可以得到 0x16。

然后，由于 REFOUT = true，所以对 0x16 在 \(5\) 位二进制下进行位翻转（需要考虑前导 \(0\)，比如 0b01111 翻转的结果是 0b11110 而非 0b1111。因为是在 \(5\) 位二进制下翻转而不是在有效位内翻转，所以补足 \(5\) 位用到的前导 \(0\) 也要翻转），得到的结果是 0x0d。最后异或 XOROUT = 0x1 就可以得到数据 0x1234 的自定义 \(5\) 位 CRC 模型校验码为 0x0c = 12。

那么上述并没有提及到的 REFIN 是什么意思呢？当 REFIN = false 的时候，我们并不需要进行多余操作。而当 REFIN 为 true 的时候，我们需要把输入数据的 每一字节 按位翻转，也就是在 \(8\) 位二进制下翻转每一字节的数据。注意是 每一字节 翻转。REFIN 的翻转与 REFOUT 翻转的不同之处就在于，REFIN 是对输入数据的 每一字节 进行 \(8\) 位二进制翻转；而 REFOUT 是对输出的 校验码 进行 WIDTH 位二进制翻转（也应注意这个操作在异或 XOROUT 之前）。

例如，输入数据 0x1234 每字节翻转为 0x482c，因为 0x12 的翻转是 0x48，0x34 的翻转是 0x2c，所以每字节翻转的结果就是 0x482c，字节内的位翻转，字节间的顺序不变。

所以，0x1234 在 REFIN = false 的情况下得出的 CRC 码，与 0x482c 在 REFIN = true ，其他参数相同的情况下得出的 CRC 码是相同的。REFIN 的翻转应该是一拿到这一字节的数据就立刻进行翻转，翻转之后再与上一字节的结果异或，再进行二进制取模运算。

接下来考虑一下如何用代码实现 CRC 校验。

首先，不同的 CRC 模型的宽度 WIDTH 是不一样的，甚至可以自定义。但是一般来说，因为一个字节的宽度是 \(8\)，目前最大的数据类型宽度是 \(64\)，所以一般选取的 CRC 模型宽度下限是 \(8\)，上限是 \(64\)。（但是也有一些宽度为 \(4,5,6,7\) 的公开模型）

回忆一下二进制取模的过程，要首先“使得其（除数多项式）首位和被除数首位对齐”。如何找到被除数的最高位？又如何使得除数与之对齐？需要考虑到的问题是，若 CRC 模型的宽度达到了最大值 \(64\) 位，那么在后面添 \(64\) 个 \(0\) 之后就变成了 \(128\) 位，已经超出了最大宽度范围；而且此时 POLY 的 \(64\) 次位（第 \(65\) 位）也要补一个 \(1\)，也就是 POLY 实际上是 \(65\) 位。这样的话如果直接做那么无论是被除数还是多项式除数都已经超过了最大宽度。

为了解决这个问题，对于 WIDTH 位 CRC 模型，我们强制所有操作只能在 WIDTH 位下进行，哪怕 WIDTH 可能只是 \(8\)，使用 int 类型完全可以存储所有数据。但是考虑到方法的兼容性，我们必须想出一种只在 WIDTH 位下操作的方法。

“在原数据后面补 WIDTH 个 \(0\)”的操作可以分成 WIDTH 次做，每次只补一个 \(0\)。每次补一个 \(0\)，数据就会左移一位，原数据的最高位就会被舍弃。

一开始，被除数是 WIDTH 位，所有高于 WIDTH 的位置都是 \(0\)。现在我们依次在被除数后面加 \(0\)。

若某次加一个 \(0\) 之前，第 WIDTH 位是 \(1\)，那么加了 \(0\) 之后，第 WIDTH+1 位就会变成 \(1\)。因为 POLY 的第 WIDTH+1 位要补个 \(1\)，所以这时被除数和除数最高位对齐了！！！这时我们在补 \(0\) 之后就要进行异或了，异或之后第 WIDTH+1 位变成 \(0\)，保持了“所有高于 WIDTH 的位置都是 \(0\)”这个性质。反之如果加 \(0\) 之前第 WIDTH 位是 \(0\)，那么左移之后就不用进行异或。

然而实际操作时，因为 POLY 的第 WIDTH +1 位已经超出了宽度限制，所以我们不会把这位的 \(1\) 补上。同样，如果被除数的第 WIDTH 位是 \(1\)，那么左移之后这一位就会被舍弃，我们并不能获取这一位的任何信息。所以我们要在左移之前就进行判断，如果第 WIDTH 位是 \(1\)，那么左移之后再异或 POLY。

举个例子，WIDTH = 7, POLY = 0x3d, INIT=XOROUT=0, REFIN=REFOUT=false 的一个模型，只针对一个字节的校验，代码实现是这样的：

int crc_7_3d(const char data) {
    // WIDTH = 7, POLY = 0x3d, INIT=XOROUT=0, REFIN=REFOUT=false
    // 注意该函数只针对一个字节进行校验。实际进行多字节校验还需要使用一个 while 循环。
    // 注：该代码正确性未经过检验，仅作为示例帮助理解。
    int WIDTH = 7;
    long long unsigned poly = 0b00111101; // 实际 poly 应该是 0b10111101，但是并不储存最高位的 1
    long long unsigned x = data;
    for(int i = 0; i < WIDTH; ++i) {
        if(x & 0b1000000) x = (x << 1) ^ poly; // 第 7 位左移后成为第 8 位，舍弃，所以 poly 的最高位没有储存并不是问题。
        else x <<= 1;
    }
    return x & 0b1111111; // 取最低 7 位返回
}

观察最后返回那一行，需要按位与 0b1111111。这是因为我们采取 long long unsigned 来存储数据，而左移的时候溢出位并没有真正“舍弃”，我们的操作只是“不予理睬”。实际上溢出的 \(1\) 是还在的，而 POLY 没有储存最高位的 \(1\)，导致没有异或掉。所以溢出位的存在会干扰最后的结果，所以要按位与 0b1111111。

以下介绍两种不同的实现方法，仅作了解即可：

有一种方法是把 WIDTH 个有效位全部送上储存类型的最高位进行操作。比如上述例子是在 long long unsigned 的第 1~7 位（称最低位为第 \(1\) 位）进行操作，那么我们也可以把所有数据都左移到 long long unsigned 的第 58~64 位操作，这样每次左移就会立即溢出。但是同样在返回之前，需要把第 58~64 位操作的结果重新右移到第 1~7 位再返回。

int crc_7_3d(const char data) {
    // WIDTH = 7, POLY = 0x3d, INIT=XOROUT=0, REFIN=REFOUT=false
    // 注意该函数只针对一个字节进行校验。实际进行多字节校验还需要使用一个 while 循环。
    // 注：该代码正确性未经过检验，仅作为示例帮助理解。
    int WIDTH = 7;
    long long unsigned poly = 0b00111101 << (64- WIDTH); // 实际 poly 应该是 0b10111101，但是并不储存最高位的 1
    long long unsigned x = data << (64- WIDTH);
    for(int i = 0; i < WIDTH; ++i) {
        if(x & 0x8000000000000000) x = (x << 1) ^ poly; // 判断原 WIDTH 位，今最高位，是否为 1。
        else x <<= 1;
    }
    return x >> (64 -WIDTH); // 右移复位
}

还有一种方法是在低位进行操作，但是把被除数、除数都进行 WIDTH 位二进制翻转，然后左移操作变成右移操作，最高位就变成最低位，判断时可以直接按位与 0b1 得到。而右移的时候也会直接舍弃。

这样的话我们首先需要一些进行二进制翻转的函数。

inline unsigned short reverseShort(unsigned short x) {
    // 执行 16 位二进制翻转
	x = ((x & 0x00ff) << 8) | ((x & 0xff00) >> 8); // 字节之间交换顺序，字节内顺序不变。
	x = ((x & 0x0f0f) << 4) | ((x & 0xf0f0) >> 4); // 半字节之间交换顺序，半字节内顺序不变。
	x = ((x & 0x3333) << 2) | ((x & 0xcccc) >> 2); // 每两位交换顺序，这两位的相对顺序不变。
	x = ((x & 0x5555) << 1) | ((x & 0xaaaa) >> 1); // 相邻两位交换顺序。
	return x; // 如果不能理解这一函数，可以手动模拟实现一下。建议把执行按位与的数写成二进制观察一下他们的规律。
}

inline unsigned reverseInt(unsigned x) {
    // 执行 32 位二进制翻转
	return (reverseShort(x & 0xffff) << 16u) | reverseShort(x >> 16);
}

inline long long unsigned reverseLong(long long unsigned x) {
    // 执行 64 位二进制翻转。
	return ((long long unsigned)reverseInt(x & 0xffffffff) << 32) | reverseInt(x >> 32);
}

实际情况下，为了程序的兼容性，进行 WIDTH 位翻转时，我们会使用 reverseLong(x) >> (64 - WIDTH) 就可以进行 WIDTH 位二进制翻转。

int crc_7_3d(const char data) {
    // WIDTH = 7, POLY = 0x3d, INIT=XOROUT=0, REFIN=REFOUT=false
    // 注意该函数只针对一个字节进行校验。实际进行多字节校验还需要使用一个 while 循环。
    // 注：该代码正确性未经过检验，仅作为示例帮助理解。
    int WIDTH = 7;
    long long unsigned poly = reverseLong(0b00111101) >> (64- WIDTH); // 实际 poly 应该是 0b10111101，但是并不储存最高位的 1
    long long unsigned x = reverseLong(data) >> (64- WIDTH);
    for(int i = 0; i < WIDTH; ++i) {
        if(x & 0b1) x = (x >> 1) ^ poly; // 判断原 WIDTH 位，今最高位，是否为 1。
        else x >>= 1;
    }
    return reverseLong(x) >> (64 -WIDTH); // 反转回来。
}

这个方法也有一个要注意的地方。就是实现多字节校验时，应该是该字节的数据异或到上一字节的结果的低 \(8\) 位。但是由于进行了翻转，所以应该是该字节的数据翻转后，异或到上一字节结果的高 \(8\) 位。所以此时就不是 reverseLong(data) >> (64 - 8)，而应该也是 reverseLong(data) >> (64 - WIDTH)。

上述提到了三种方法，不同的程序会采取不同的方法，因此列出以作了解。后两种方法理解起来比较复杂，所以我们采取第一种方法来构建我们的代码。

还记得前面我们搭建的代码框架吗？我们使用了继承的方法，每一个子类都继承自父类 CRCCommon，需要实现一个虚函数重载运算符。

在此之前回忆（总结）一下 CRC 校验的步骤：

获取该字节数据。若 REFIN = true 则进行翻转。
异或上一字节的结果。若上一字节为第 \(0\) 字节则异或 INIT。
执行 WIDTH 次补 \(0\)、判断、异或的二进制取模操作。
若存在下一字节数据，则回到第 \(1\) 步。
若 REFOUT = true 则将校验码进行 WIDTH 位二进制翻转。
将校验码异或 XOROUT 后返回，作为校验值。

inline unsigned short reverseByte(unsigned short x) {
    // 进行一字节的二进制翻转。
	x = ((x & 0x0f) << 4) | ((x & 0xf0) >> 4);
	x = ((x & 0x33) << 2) | ((x & 0xcc) >> 2);
	x = ((x & 0x55) << 1) | ((x & 0xaa) >> 1);
	return x;
}

template <unsigned WIDTH, long long unsigned POLY, long long unsigned INIT, long long unsigned XOROUT, bool REFIN, bool REFOUT>
virtual const long long unsigned CRC<WIDTH, POLY, INIT, XOROUT, REFIN, REFOUT>::operator()(char(*nextData)(), size_t length) const {
    // 注：该代码仅通过了一部分正确性验证。剩余部分验证将逐步完善。
    // 验证网站：http://www.ip33.com/crc.html
    long long unsigned x = INIT;
    long long unsigned poly = POLY;
    if(REFIN) {
        while(length--) {
            x ^= reverseByte(nextData());
            for(unsigned i = 0; i < WIDTH; ++i) {
                if(x & (1 << (WIDTH - 1))) x = (x << 1) ^ poly;
                else x <<= 1;
            }
        }
    } else {
        while(length--) {
            x ^= nextData();
            for(unsigned i = 0; i < WIDTH; ++i) {
                if(x & (1 << (WIDTH - 1))) x = (x << 1) ^ poly;
                else x <<= 1;
            }
        }
    }
    x &= (1ull << WIDTH) - 1; // 取低 WIDTH 位
    if(REFOUT) x = reverseLong(x) >> (64 - WIDTH); // reverseLong 的定义在上文代码处。
    return x ^ XOROUT;
}

标签：字节,WIDTH,校验,long,CRC,异或,解析,翻转
From： https://www.cnblogs.com/LASS/p/17386057.html

CRC 校验解析

CRC 校验解析

相关文章

赞助商

阅读排行