改文章是我在2011年写于某sdn的， 搬运过来。
在网络通信中，循环冗余校验（CRC）是一种广泛使用的检错码，用于检测数据传输过程中的错误。其中，CRC32由于其良好的检错能力和相对较低的计算复杂度，成为许多协议（包括以太网）中首选的检错机制。本文将深入探讨CRC32校验码的三种实现方法，并提供详细的代码实现。
方法一：按位计算CRC32校验码
这是最基础也是最直观的实现方式，它逐位地进行异或和移位操作，适用于理解CRC算法原理，但计算效率较低。
代码实现：
Cpp
#include <cstdint> uint32_t crc32_bitwise(uint32_t polynomial, uint32_t initial, const void *data, size_t len) { uint32_t crc = initial; const unsigned char *ptr = (const unsigned char *)data; for (size_t i = 0; i < len; i++) { crc ^= ((uint32_t)(*ptr++)) << 24; for (int j = 0; j < 8; j++) { if (crc & 0x80000000) crc = (crc << 1) ^ polynomial; else crc <<= 1; } } return crc; }
方法二：使用非翻转的查找表进行快速计算
为了提高计算速度，可以预先生成一个查找表，每次处理一个字节的数据。然而，这种实现通常包含位翻转操作，影响了计算效率。
代码实现：
Cpp
#include <cstdint> #include <array> constexpr uint32_t POLYNOMIAL = 0xEDB88320; std::array<uint32_t, 256> crc_table; void generate_crc_table() { for (int i = 0; i < 256; i++) { uint32_t crc = i; for (int j = 0; j < 8; j++) { if (crc & 1) crc = (crc >> 1) ^ POLYNOMIAL; else crc >>= 1; } crc_table[i] = crc; } } uint32_t crc32_lookup(uint32_t initial, const void *data, size_t len) { uint32_t crc = ~initial; const unsigned char *ptr = (const unsigned char *)data; for (size_t i = 0; i < len; i++) crc = (crc >> 8) ^ crc_table[(crc ^ *ptr++) & 0xFF]; return ~crc; }
方法三：使用翻转的查找表进行快速计算
这种方法通过预先翻转输入数据和查找表中的值，避免了在计算过程中的位翻转操作，从而极大地提高了计算速度。
代码实现：
Cpp
#include <cstdint> #include <array> constexpr uint32_t POLYNOMIAL = 0xEDB88320; std::array<uint32_t, 256> crc_table; void generate_crc_table_flip() { for (int i = 0; i < 256; i++) { uint32_t crc = i; for (int j = 0; j < 8; j++) { crc = (crc >> 1) ^ (-(crc & 1) & POLYNOMIAL); } crc_table[i] = crc; } } uint32_t crc32_lookup_flip(uint32_t initial, const void *data, size_t len) { uint32_t crc = initial; const unsigned char *ptr = (const unsigned char *)data; for (size_t i = 0; i < len; i++) crc = crc_table[(crc ^ *ptr++) & 0xFF] ^ (crc >> 8); return crc; }
结论
在实际应用中，根据性能需求和资源限制选择合适的CRC32实现至关重要。尽管按位计算提供了最清晰的算法理解，但在性能要求较高的场景下，使用查找表的方法（特别是翻转的查找表）能提供显著的速度优势。希望本文的代码实现能帮助读者更好地理解和应用CRC32校验码。
完整代码：
//位翻转函数 alt_u64 Reflect(alt_u64 ref,alt_u8 ch) { int i; alt_u64 value = 0; for( i = 1; i < ( ch + 1 ); i++ ) { if( ref & 1 ) value |= 1 << ( ch - i ); ref >>= 1; } return value; } //标准的CRC32多项式 //翻转的CRC32多项式 alt_u32 crc32_bit(alt_u8 *ptr, alt_u32 len, alt_u32 gx) { alt_u8 i; alt_u32 crc = 0xffffffff; while( len-- ) { for( i = 1; i != 0; i <<= 1 ) { if( ( crc & 0x80000000 ) != 0 ) { crc <<= 1; crc ^= gx; } else crc <<= 1; if( ( *ptr & i ) != 0 ) crc ^= gx; } ptr++; } return ( Reflect(crc,32) ^ 0xffffffff ); } alt_u32 Table1[256]; alt_u32 Table2[256]; // 生成CRC32 普通表 , 第二项是04C11DB7 void gen_direct_table(alt_u32 *table) { alt_u32 gx = 0x04c11db7; unsigned long i32, j32; unsigned long nData32; unsigned long nAccum32; for ( i32 = 0; i32 < 256; i32++ ) { nData32 = ( unsigned long )( i32 << 24 ); nAccum32 = 0; for ( j32 = 0; j32 < 8; j32++ ) { if ( ( nData32 ^ nAccum32 ) & 0x80000000 ) nAccum32 = ( nAccum32 << 1 ) ^ gx; else nAccum32 <<= 1; nData32 <<= 1; } table[i32] = nAccum32; } } // 生成CRC32 翻转表 第二项是77073096 void gen_normal_table(alt_u32 *table) { alt_u32 gx = 0x04c11db7; alt_u32 temp,crc; for(int i = 0; i <= 0xFF; i++) { temp=Reflect(i, 8); table[i]= temp<< 24; for (int j = 0; j < 8; j++) { unsigned long int t1,t2; unsigned long int flag=table[i]&0x80000000; t1=(table[i] << 1); if(flag==0) t2=0; else t2=gx; table[i] =t1^t2 ; } crc=table[i]; table[i] = Reflect(table[i], 32); } } alt_u32 DIRECT_TABLE_CRC(alt_u8 *ptr,int len, alt_u32 * table) { alt_u32 crc = 0xffffffff; alt_u8 *p= ptr; int i; for ( i = 0; i < len; i++ ) crc = ( crc << 8 ) ^ table[( crc >> 24 ) ^ (alt_u8)Reflect((*(p+i)), 8)]; return ~(alt_u32)Reflect(crc, 32) ; } alt_u32 Reverse_Table_CRC(alt_u8 *data, alt_32 len, alt_u32 * table) { alt_u32 crc = 0xffffffff; alt_u8 *p = data; int i; for(i=0; i <len; i++) crc = table[( crc ^( *(p+i)) ) & 0xff] ^ (crc >> 8); return ~crc ; } //这是一个完整的以太网帧。最后四个字节 8b 6b f5 13是其FCS字段，用于与后面生成的CRC32对照 alt_u8 tx_data[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x1f, //8 0x29, 0x00, 0xb5, 0xfa, 0x08, 0x06, 0x00, 0x01, //15 0x08, 0x00, 0x06, 0x04, 0x00, 0x01, 0x00, 0x1f, //24 0x29, 0x00, 0xb5, 0xfa, 0xac, 0x15, 0x0e, 0xd9, //32 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xac, 0x15, //40 0x0e, 0x8e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, //48 0x00, 0x00 , 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, //56 0x00, 0x00, 0x00, 0x00, 0x8b, 0x6b, 0xf5, 0x13 //64 }; int main() { alt_u8 *data = tx_data; alt_u32 dataLen = sizeof(tx_data) -4; int sum = 256; int i = 0; //生成普通表，用于直接计算的表 gen_direct_table(Table1); printf("Table1 :\n"); for( i = 0; i < sum; i++) { if(i<16) printf("%08x ",Table1[i]); } printf("\n\n"); //生成翻转表，是官方推荐的，故称其为normal_table gen_normal_table(Table2); printf("Table2 :\n"); for( i = 0; i < sum; i++) { if(i<16) printf("%08x ",Table2[i]); } printf("\n\n"); printf("dataLen = %d\n",dataLen);//打印数据长度，应该是60字节。 //计算并打印出CRC32校验码，应该是0x13f56b8b //按照bit进行校验，最慢 printf("Slow CRC by bit : %08x\n",crc32_bit( data, dataLen, 0x04c11db7 )); //使用普通表，非官方，很慢 printf("Direct Table ref + xor : %08x\n",DIRECT_TABLE_CRC (data,dataLen,Table1)); //使用翻转表，官方推荐的，很快 printf("Reverse Table ref + xor : %08x\n",Reverse_Table_CRC(data,dataLen,Table2)); system("pause"); return 0; }
