CRC32 算法

CRC是什么东西呢？

其实我们大家都不应该会对它陌生，回忆一下？你用过RAR和ZIP等压缩软件吗？它们是不是常常会给你一个恼人的“CRC校验错误”信息呢？我想你应该明白了吧，CRC就是块数据的计算值，它的全称是“Cyclic Redundancy Check”，中文名是“循环冗余码”，“CRC校验”就是“循环冗余校验”。

CRC有什么用呢？

在 数据存储 和 数据通讯 领域， 为了保证数据的正确，就不得不采用检错的手段 。 在诸多检错手段中，CRC 是最著名的一种。

它的应用范围很广泛，最常见的就是在网络传输中进行信息的校对。其实我们大可以把它应用到软件保护中去，因为它的计算是非常非常非常严格的。严格到什么程度呢？你的程序只要被改动了一个字节（甚至只是大小写的改动），它的值就会跟原来的不同。所以只要给你的“原”程序计算好CRC值，储存在某个地方，然后在程序中随机地再对文件进行CRC校验，接着跟第一次生成并保存好的CRC值进行比较，如果相等的话就说明你的程序没有被修改/破解过，如果不等的话，那么很可能你的程序遭到了病毒的感染，或者被Cracker用16进制工具暴力破解过了。

CRC的原理。由于CRC实现起来有一定的难度，所以具体怎样用它来保护文件，留待下一节再讲。

首先看两个式子：

式一：9 / 3 = 3          （余数 = 0）

式二：(9 + 2 ) / 3 = 3   （余数 = 2）

除法运算就是将被减数重复地减去除数X次，然后留下余数，所以上面的两个式子可以用二进制计算为：

式一：

1001        --> 9

0011    -   --> 3

---------

0110        --> 6

0011    -   --> 3

---------

0011        --> 3

0011    -   --> 3

---------

0000        --> 0，余数

一共减了3次，所以商是3，而最后一次减出来的结果是0，所以余数为0

式二：

1011        --> 11

0011    -   --> 3

---------

1000        --> 8

0011    -   --> 3

---------

0101        --> 5

0011    -   --> 3

---------

0010        --> 2,余数

一共减了3次，所以商是3，而最后一次减出来的结果是2，所以余数为2。二进制减法运算的规则是，如果遇到0-1的情况，那么要从高位借1，就变成了(10+0)-1=1。CRC运算有什么不同呢？让我们看下面的例子：

这次用式子30 / 9，不过请读者注意最后的余数：

11110        --> 30

1001    -    --> 9

---------

 1100        --> 12    （很奇怪吧？为什么不是21呢？）

 1001   -    --> 9

 --------

  101        --> 5，余数 --> the CRC!

这个式子的计算过程是不是很奇怪呢？它不是直接减的，而是用XOR的方式来运算最后得到一个余数。对啦，这个就是CRC的运算方法，明白了吗？CRC的本质是进行XOR运算，运算的过程我们不用管它，因为运算过程对最后的结果没有意义；我们真正感兴趣的只是最终得到的余数，这个余数就是CRC值。

进行一个CRC运算我们需要选择一个除数，这个除数我们叫它为“poly”，宽度W就是最高位的位置，所以我刚才举的例子中的除数9，这个poly 1001的W是3，而不是4，注意最高位总是1。如果我们想计算一个位串的CRC码，我们想确定每一个位都被处理过，因此，我们要在目标位串后面加上W个0位。现在让我们根据CRC的规范来改写一下上面的例子：

Poly                    =    1001，宽度W = 3

位串Bitstring           =    11110

Bitstring + W zeroes    =    11110 + 000 = 11110000

11110000

1001||||    -

-------------

 1100|||

 1001|||    -

 ------------

  1010||

  1001||    -

  -----------

   0110|

   0000|    -

   ----------

    1100

    1001    -

    ---------

     101        --> 5，余数 --> the CRC!

还有两点重要声明如下：

1、只有当Bitstring的最高位为1，我们才将它与poly进行XOR运算，否则我们只是将Bitstring左移一位。

2、XOR运算的结果就是被操作位串Bitstring与poly的低W位进行XOR运算，因为最高位总为0。

由于速度的关系，CRC的实现主要是通过查表法，对于CRC-16和CRC-32，各自有一个现成的表，大家可以直接引入到程序中使用。两个表太长，在这里不列出来了，请读者自行在网络上查找。如果我们没有这个表怎么办呢？或者你跟我一样，懒得自己输入？不用急，我们可以“自己动手，丰衣足食”。你可能会说，自己编程来生成这个表，会不会太慢了？其实大可不必担心，而这个表只有区区256个双字，根本影响不了速度。

void CCrc32::MakeTable()

{

    int i,j;

    unsigned long crc;

    for (i = 0; i < 256; i++)

    {

        crc = i;

        for (j = 0; j < 8; j++)

        {

            if (crc & 1)

                crc = (crc >> 1) ^ 0xEDB88320;

            else

                crc >>= 1;

        }

        Crc32Table[i] = crc;

    }

}

生成表之后，就可以进行运算了。

我们的算法如下：

1、将寄存器向右边移动一个字节。

2、将刚移出的那个字节与我们的字符串中的新字节进行XOR运算，得出一个指向值表table[0..255]的索引。

3、将索引所指的表值与寄存器做XOR运算。

4、如果数据没有全部处理完，则跳到步骤1。

int CCrc32::GetCrc(CString &csData, DWORD dwSize)

{

    unsigned long crc  = 0xffffffff;

    int len;

    unsigned char* buffer;

    len = dwSize;

    buffer = (unsigned char*)(LPCTSTR)csData;

    while(len--)

    {

       crc = (crc >> 8) ^ Crc32Table[(crc & 0xFF) ^ *buffer++];

    }

    return crc ^ 0xffffffff;

}