简而言的CRC是个数值该数值被用于校验数据正确性CRC数值简单地说就是通过让你需要做处理数据除以个常数而得到余数当你得到这个数值后你可以将这个数值附加到你数据后当数据被传送到其他地方后取出原始数据(可能在传送过程中被破坏)和附加CRC数值然后将这里原始数据除以的前那个常数(约定好)然后得到新CRC值比较两个CRC值是否相等即可确认你数据是否在传送过程中出现

那么如何让你数据除以个常数？思路方法是对你数据进行必要编码处理逐字节处理成数字
那么这个常数是什么？你不必关注它是什么也不需要关注它是如何获得当你真要动手写个CRC实现算法时我可以告诉你CRC理论学家会告诉你区别长度常数对应着区别CRC实现算法当这个常数为32位时也就是这里所说CRC32

以上内容你不必全部理解你需要查阅其他资料来获取CRC完整理论介绍

The mathematics behind CRC ?

很多教科书会把CRC和多项式关联起来这里多项式指是系数为0或1式子例如:a0 + a1*x + a2*x^2 + ... + an*x^n其中a0, a1, ..., an要么为0要么为1我们并不关注x取什么值
(如果你要关注你可以简单地认为x为2) 这里把a0, a1, ..., an值取出来排列起来就可以表示比特流例如 1 + x + x^3所表示比特流就为:1101部分资料会将这个顺序颠倒这个很正常

什么是生成多项式？

所谓生成多项式就是上面我所说常数注意在这里个多项式就表示了个比特流也就是堆1、0组合起来最终就是个数值例如CRC32算法中这个生成多项式为:c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32其对应数字就为:11101101101110001000001100100000(x^32在实际计算时隐含给出因此这里没有包含它系数)也就是0xEDB88320(多项式对应数字可能颠倒颠倒后得到是0x04C11DB7其实也是正确)

由此可以看出CRC值也可以看成我们数据除以个生成多项式而得到余数

如何做这个除法？

套用大部分教科书给出计算思路方法任何数据都可以被处理成纯数字因此在某种程度上说我们可以直接开始这个除法尽管事实上这并不是标准除法例如我们数据为1101011011(方便起见我直接给 2进制表示了从这里也可以看出CRC是按bit进行计算)给定生成多项式(对应值)为10011通常教科书会告诉我们在进行这个除法前会把我们数据左移几位(生成多项式位数-1位)从而可以容纳将来计算得到CRC值(我上面所说将CRC值附加到原始数据后)但是为什么要这样做？我也不知道(不知道东西不能含糊过)那么除法就为:
1100001010
_______________
10011 ) 11010110110000 附加了几个零新数据
10011......... 这里减法(希望你不至于忘掉小学算术)是个异或操作
-----.........
10011........
10011........
-----........
00001....... 逐bit计算
00000.......
-----.......
00010......
00000......
-----......
00101.....
00000.....
-----.....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = 这个余数也就是所谓CRC值通常又被称为校验值

希望进行到这里你可以获取更多有关CRC感性认识而我们所要做也就是实现个CRC计算算法说白了就是提供个给定段数据以及个生成多项式(对于CRC32算法而言该值固定)然后计算得出上面1110余数

The simplest algorithm.



最简单实现算法是种模拟算法我们模拟上面除法过程遵从网上份比较全面资料我们设定个变量register我们逐bit地将我们数据放到register中然后判断register最高位是否为1如果是则和生成多项式异或操作否则继续处理这个过程简单地模拟了上述除法过程:



/**////
/// The simplest CRC implement algorithm.
///
/**//*
Load the register with zero bits.
Augment the message by appending W zero bits to the end of it.
While (more message bits)
Begin
Sht the register left by _disibledevent=>End
The register now contains the reder.
*/

# <stdio.h>

# POLY 0x13


{
/**//// the data
unsigned data = 0x035b;
/**//// load the register with zero bits
unsigned regi = 0x0000;
/**//// augment the data by appending W(4) zero bits to the end of it.
data <<= 4;

/**//// we do it bit after bit
for( cur_bit = 15; cur_bit >= 0; -- cur_bit )
{
/**//// test the highest bit which will be poped later.
/// in fact, the 5th bit from right is the hightest bit here
( ( ( regi >> 4 ) & 0x0001 ) 0x1 )
{
regi = regi ^ POLY;
}
/**//// sht the register
regi <<= 1;
/**//// reading the next bit of the augmented data
unsigned tmp = ( data >> cur_bit ) & 0x0001;
regi |= tmp;

}

/**//// and now, register contains the reder which is also called CRC value.

0;
}



better algorithm ?

很多时候这种让人容易理解算法都不会被实际用到这种逐bit操作算法实在很慢你可能知道般CRC32算法都是种基于表(table-driven)算法但是你可能不知道这个表是如何来

种改善这种bit after bit思路方法就是将这个bit扩大例如典型做法就是换成这里我要详细地叙述下上面那种算法过程:

我们每次会先检查register最高位是否为1如果为1则将生成多项式(所谓Poly)和register进行异或操作然后将register左移位也就舍弃了最高位然后将我们数据拿bit出来放到register最低位

也就是说register中某位值会决定后面几位值如果将register最高字节每bit编码为:t7 t6 t5 t4 t3 t2 t1 t0那么t7会决定t6-t0值(如果为1)t6会决定t5-t0值依次类推但是无论谁决定谁值当上面那个算法迭代个字节后(8bits)t7-t0都会被丢弃(whatever you do)唯留下来东西就是对这个字节以后字节影响

那么如果我们可以直接获取这个影响我们就可以 after 地处理而不是bit after bit如何获取这个影响呢？这个影响又是什么呢？这个影响就对应着我们table-driven CRC算法中表元素！

但是为什么我们逐bit进行计算过程为什么可以简化为步操作？事实上我们没有简化这个操作种用于教学算法是实时地计算这个影响值:



/**////
/// The table-driven CRC implement algorithm part 1.
///
/**//*
While (augmented message is not exhausted)
Begin
Examine the top of the register
Calculate the control from the top of the register
Sum all the Polys at various offs that are to be XORed o
the register in accordance with the control
Sht the register left by _disibledevent=>/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the AUGMENTED data (added some zeros)
unsigned char p[8];
/**//// copy data
mem( p, 0, 8 );
memcpy( p, &data, 4 );

/**//// because data contains 4 s
for( i = 0; i < 8; i )
{
/**//// get the top of the register
unsigned char top_ = (unsigned char)( ( regi >> 24 ) & 0xff );
/**//// sum all the polys at various offs
unsigned long sum_poly = top_ << 24;
for( j = 0; j < 8; j )
{
/**//// check the top bit
( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}

{
sum_poly <<= 1;
}
}
/**//// sht the register left by _disibledevent=>/**//// xor the summed polys to the register
regi ^= sum_poly;
}

/**//// and now, register contains the reder which is also called CRC value.

0;
}



其中:


/**//// sum all the polys at various offs
unsigned long sum_poly = top_ << 24;
for( j = 0; j < 8; j )
{
/**//// check the top bit
( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}

{
sum_poly <<= 1;
}
}




就是用于计算这个影响值事实上table-driven CRC算法中那个表就是通过这段代码生成(排除其他些细节)你可能并不是很理解这里我建议你忽略各种细节(更多细节见参考资料)你所需要知道是我们将8次逐bit操作合并到了次操作中而这个操作就是8次bit操作合操作(上面提到影响值)这个操作其实就是个数值也就是table-driven CRC算法中那个表个元素区别序列bit操作其实对应着区别unsigned char值因此那个table有256个元素

show me where the table is :

如上所说上面算法很容易地就可以引进个表:


进步简化:

上述算法个典型特征是会在我们数据后面添加若干0这样做其他做了很多没用计算种简化做法就是将这些没用计算合并到其他计算中其实这都是些位操作窍门技巧:


/**////
/// The table-driven CRC implement algorithm part 2.
///
/**//*
While (augmented message is not exhausted)
Begin
Examine the top of the register
Calculate the control from the top of the register
Sum all the Polys at various offs that are to be XORed o
the register in accordance with the control
Sht the register left by _disibledevent=>for( j = 0; j < 8; j )
{
/**//// check the top bit
( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}

{
sum_poly <<= 1;
}
}

sum_poly;
}

void create_table( unsigned long *table )
{
for( i = 0; i < 256; i )
{
table[i] = get_sum_poly( (unsigned char) i );
}
}


{
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the AUGMENTED data (added some zeros)
unsigned char p[8];
/**//// copy data
mem( p, 0, 8 );
memcpy( p, &data, 4 );

/**//// the table
unsigned long table[256];
/**//// create the table
create_table( table );

/**//// because data contains 4 s
for( i = 0; i < 8; i )
{
/**//// get the top of the register
unsigned char top_ = (unsigned char)( ( regi >> 24 ) & 0xff );
/**//// sht the register left by _disibledevent=>/**//// xor the summed polys to the register
regi ^= table[top_];
}

/**//// and now, register contains the reder which is also called CRC value.

0;
}



讨厌附加0

以上算法有个很大特征就是要为我们数据附加很多0附加0后其实也附加了很多无用操作我们要将这些讨厌0去掉:




{
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the data
unsigned char p[4];
/**//// copy data
memcpy( p, &data, 4 );

/**//// the table
unsigned long table[256];
/**//// create the table
create_table( table );

/**//// because data contains 4 s
for( i = 0; i < 4; i )
{
regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ];
}

/**//// and now, register contains the reder which is also called CRC value.

0;
}



关键句regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ]; 简化了很多没用操作


In practice :



似乎切被我说很简单我想只是我没说清楚我尽量让你注意到事情重点我们进行到这里似乎我们立马就可以写出自己CRC32算法并用于实战但是你很快就会发现事情并不如你想像那么简单

在实际处理时很多数据bit会进行种颠倒操作例如1010会被颠倒为0101出现这样情况是某些硬件在实现CRC算法时采用了这种(丑陋)习惯有些软件Software实现CRC算法时也延用了这个习惯

另外有关register值问题有些CRC算法会化为0xffffffff以下给出个会进行bit颠倒算法该算法可以直接输出table-driven中表:



/**////
/// The table-driven CRC implement algorithm part 4.
///
/// Donot need augment W/8 zero s.
///
# <stdio.h>
# <stdlib.h>
# <memory.h>

# POLY 0x04C11DB7L

# BITMASK(X) (1L << (X))

unsigned long refelect( unsigned long v, b )
{
i;
unsigned long t = v;
for( i = 0; i < b; i )
{
( t & 1L )
v |= BITMASK( (b-1)-i );

v &= ~BITMASK( (b-1)-i );
t >>= 1;
}

v;
}

/**//// i'll try to write a correct algorithm
unsigned long get_sum_poly( unsigned char )
{
= (unsigned long) refelect( , 8 );
unsigned long sum_poly = << 24;

for( i = 0; i < 8; i )
{
/**//// check the top bit
( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}

{
sum_poly <<= 1;
}
}

sum_poly = refelect( sum_poly, 32 );
sum_poly;
}

void create_table( unsigned long *table )
{
for( i = 0; i <= 255; i )
{
table[i] = get_sum_poly( (unsigned char) i );
}
}

void output_table( const unsigned long *table )
{
FILE *fp = fopen( "table.txt", "w" );

for( y = 0; y < 64; y )
{
fprf( fp, "0x%08lXL,\t0x%08lXL,\t0x%08lXL,\t0x%08lXL, \n",
table[ y * 4 + 0],
table[ y * 4 + 1],
table[ y * 4 + 2],
table[ y * 4 + 3] );
}

fclose( fp );
}


{
/**//// the table
unsigned long table[256];
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the data
unsigned char p[4];
/**//// copy data
memcpy( p, &data, 4 );
/**//// create the table
create_table( table );
/**//// output the table
output_table( table );

/**//// because data contains 4 s
for( i = 0; i < 4; i )
{
regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ];
}

/**//// and now, register contains the reder which is also called CRC value.

0;
}



Please FORGIVE me

我想我并没有将整个过程彻底地讲清楚但是我希望你能明白大致原理有关table-driven中那个神奇表来历
有关CRC32算法推导过程等等的类
代码下载: /uploads/soft/1_080624030837.rar