【算法】CRC32的C语言实现和NASM汇编语言实现
CRC32是用来校验数据是否正确的简易方法。它的算法很简单,把上次计算的CRC码的低8位和数据字节做异或运算,得到的值用作CRC表的索引,从CRC表提取一个数字并把旧的CRC码右移8位然后把这个移动了的旧CRC码和从CRC表提取出的数字作异或运算得出新的CRC码。进行多次这样的运算可以计算多个字节的数据的CRC码。这个算法用汉语不好描述,但是用C语言很好描述,就像这样:typedef unsigned long crc_t;
crc_t crc32(crc_t crc,void*pBuf,unsigned int cbSize)
{
crc^=0xffffffffUL;
do
crc=crc_table[((int)crc^(*(unsigned char*)pBuf++))&0xFF]^(crc>>8);
while(--cbSize);
return crc^0xffffffffUL;
}而NASM汇编的也很简单,这样写:_crc32:
push esi
mov edx, ;edx存储crc32的值
mov esi, ;esi指向数据
mov ecx, ;ecx计字节数
xor eax,eax ;eax清零
not edx ;crc求反
.LoopBytes:
lodsb ;读取字节al=*esi++
xor al,dl ;字节异或
shr edx,8 ;crc右移8位
xor edx, ;crc表取值然后和edx异或
loop .LoopBytes ;处理所有字节
mov eax,edx ;设置返回值
not eax ;求反
pop esi ;恢复esi的值
ret那么这两个算法都需要一个crc表。这个表是一个什么样的表呢?C语言是这样表示的:crc_t crc_table=
{
0x00000000UL, 0x77073096UL, 0xee0e612cUL, 0x990951baUL,
0x076dc419UL, 0x706af48fUL, 0xe963a535UL, 0x9e6495a3UL,
0x0edb8832UL, 0x79dcb8a4UL, 0xe0d5e91eUL, 0x97d2d988UL,
0x09b64c2bUL, 0x7eb17cbdUL, 0xe7b82d07UL, 0x90bf1d91UL,
0x1db71064UL, 0x6ab020f2UL, 0xf3b97148UL, 0x84be41deUL,
0x1adad47dUL, 0x6ddde4ebUL, 0xf4d4b551UL, 0x83d385c7UL,
0x136c9856UL, 0x646ba8c0UL, 0xfd62f97aUL, 0x8a65c9ecUL,
0x14015c4fUL, 0x63066cd9UL, 0xfa0f3d63UL, 0x8d080df5UL,
0x3b6e20c8UL, 0x4c69105eUL, 0xd56041e4UL, 0xa2677172UL,
0x3c03e4d1UL, 0x4b04d447UL, 0xd20d85fdUL, 0xa50ab56bUL,
0x35b5a8faUL, 0x42b2986cUL, 0xdbbbc9d6UL, 0xacbcf940UL,
0x32d86ce3UL, 0x45df5c75UL, 0xdcd60dcfUL, 0xabd13d59UL,
0x26d930acUL, 0x51de003aUL, 0xc8d75180UL, 0xbfd06116UL,
0x21b4f4b5UL, 0x56b3c423UL, 0xcfba9599UL, 0xb8bda50fUL,
0x2802b89eUL, 0x5f058808UL, 0xc60cd9b2UL, 0xb10be924UL,
0x2f6f7c87UL, 0x58684c11UL, 0xc1611dabUL, 0xb6662d3dUL,
0x76dc4190UL, 0x01db7106UL, 0x98d220bcUL, 0xefd5102aUL,
0x71b18589UL, 0x06b6b51fUL, 0x9fbfe4a5UL, 0xe8b8d433UL,
0x7807c9a2UL, 0x0f00f934UL, 0x9609a88eUL, 0xe10e9818UL,
0x7f6a0dbbUL, 0x086d3d2dUL, 0x91646c97UL, 0xe6635c01UL,
0x6b6b51f4UL, 0x1c6c6162UL, 0x856530d8UL, 0xf262004eUL,
0x6c0695edUL, 0x1b01a57bUL, 0x8208f4c1UL, 0xf50fc457UL,
0x65b0d9c6UL, 0x12b7e950UL, 0x8bbeb8eaUL, 0xfcb9887cUL,
0x62dd1ddfUL, 0x15da2d49UL, 0x8cd37cf3UL, 0xfbd44c65UL,
0x4db26158UL, 0x3ab551ceUL, 0xa3bc0074UL, 0xd4bb30e2UL,
0x4adfa541UL, 0x3dd895d7UL, 0xa4d1c46dUL, 0xd3d6f4fbUL,
0x4369e96aUL, 0x346ed9fcUL, 0xad678846UL, 0xda60b8d0UL,
0x44042d73UL, 0x33031de5UL, 0xaa0a4c5fUL, 0xdd0d7cc9UL,
0x5005713cUL, 0x270241aaUL, 0xbe0b1010UL, 0xc90c2086UL,
0x5768b525UL, 0x206f85b3UL, 0xb966d409UL, 0xce61e49fUL,
0x5edef90eUL, 0x29d9c998UL, 0xb0d09822UL, 0xc7d7a8b4UL,
0x59b33d17UL, 0x2eb40d81UL, 0xb7bd5c3bUL, 0xc0ba6cadUL,
0xedb88320UL, 0x9abfb3b6UL, 0x03b6e20cUL, 0x74b1d29aUL,
0xead54739UL, 0x9dd277afUL, 0x04db2615UL, 0x73dc1683UL,
0xe3630b12UL, 0x94643b84UL, 0x0d6d6a3eUL, 0x7a6a5aa8UL,
0xe40ecf0bUL, 0x9309ff9dUL, 0x0a00ae27UL, 0x7d079eb1UL,
0xf00f9344UL, 0x8708a3d2UL, 0x1e01f268UL, 0x6906c2feUL,
0xf762575dUL, 0x806567cbUL, 0x196c3671UL, 0x6e6b06e7UL,
0xfed41b76UL, 0x89d32be0UL, 0x10da7a5aUL, 0x67dd4accUL,
0xf9b9df6fUL, 0x8ebeeff9UL, 0x17b7be43UL, 0x60b08ed5UL,
0xd6d6a3e8UL, 0xa1d1937eUL, 0x38d8c2c4UL, 0x4fdff252UL,
0xd1bb67f1UL, 0xa6bc5767UL, 0x3fb506ddUL, 0x48b2364bUL,
0xd80d2bdaUL, 0xaf0a1b4cUL, 0x36034af6UL, 0x41047a60UL,
0xdf60efc3UL, 0xa867df55UL, 0x316e8eefUL, 0x4669be79UL,
0xcb61b38cUL, 0xbc66831aUL, 0x256fd2a0UL, 0x5268e236UL,
0xcc0c7795UL, 0xbb0b4703UL, 0x220216b9UL, 0x5505262fUL,
0xc5ba3bbeUL, 0xb2bd0b28UL, 0x2bb45a92UL, 0x5cb36a04UL,
0xc2d7ffa7UL, 0xb5d0cf31UL, 0x2cd99e8bUL, 0x5bdeae1dUL,
0x9b64c2b0UL, 0xec63f226UL, 0x756aa39cUL, 0x026d930aUL,
0x9c0906a9UL, 0xeb0e363fUL, 0x72076785UL, 0x05005713UL,
0x95bf4a82UL, 0xe2b87a14UL, 0x7bb12baeUL, 0x0cb61b38UL,
0x92d28e9bUL, 0xe5d5be0dUL, 0x7cdcefb7UL, 0x0bdbdf21UL,
0x86d3d2d4UL, 0xf1d4e242UL, 0x68ddb3f8UL, 0x1fda836eUL,
0x81be16cdUL, 0xf6b9265bUL, 0x6fb077e1UL, 0x18b74777UL,
0x88085ae6UL, 0xff0f6a70UL, 0x66063bcaUL, 0x11010b5cUL,
0x8f659effUL, 0xf862ae69UL, 0x616bffd3UL, 0x166ccf45UL,
0xa00ae278UL, 0xd70dd2eeUL, 0x4e048354UL, 0x3903b3c2UL,
0xa7672661UL, 0xd06016f7UL, 0x4969474dUL, 0x3e6e77dbUL,
0xaed16a4aUL, 0xd9d65adcUL, 0x40df0b66UL, 0x37d83bf0UL,
0xa9bcae53UL, 0xdebb9ec5UL, 0x47b2cf7fUL, 0x30b5ffe9UL,
0xbdbdf21cUL, 0xcabac28aUL, 0x53b39330UL, 0x24b4a3a6UL,
0xbad03605UL, 0xcdd70693UL, 0x54de5729UL, 0x23d967bfUL,
0xb3667a2eUL, 0xc4614ab8UL, 0x5d681b02UL, 0x2a6f2b94UL,
0xb40bbe37UL, 0xc30c8ea1UL, 0x5a05df1bUL, 0x2d02ef8dUL
};共256个表项。那个crc_t其实就是32位无符号整数,x86和x64下是unsigned long。用汇编语言表示就是_crc_table:
dd 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba
dd 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3
dd 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988
dd 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91
dd 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de
dd 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7
dd 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec
dd 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5
dd 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172
dd 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b
dd 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940
dd 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59
dd 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116
dd 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f
dd 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924
dd 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d
dd 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a
dd 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433
dd 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818
dd 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01
dd 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e
dd 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457
dd 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c
dd 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65
dd 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2
dd 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb
dd 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0
dd 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9
dd 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086
dd 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f
dd 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4
dd 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad
dd 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a
dd 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683
dd 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8
dd 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1
dd 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe
dd 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7
dd 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc
dd 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5
dd 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252
dd 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b
dd 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60
dd 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79
dd 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236
dd 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f
dd 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04
dd 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d
dd 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a
dd 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713
dd 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38
dd 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21
dd 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e
dd 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777
dd 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c
dd 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45
dd 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2
dd 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db
dd 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0
dd 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9
dd 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6
dd 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf
dd 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94
dd 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d完整的文件我这里提供下载。
以下这两个文件可以独立下载。二选一。
C语言版本:crc32.c:
NASM汇编版本(x86):crc32.asm:
以下这是实例。
一个完整的VC6工程:
一个完整的VS2012工程: 然后我最近发现SSE4.2里有专门的CRC32指令,循环里用CRC32指令可以直接省略定义CRC表,还有那些指令。 tangptr@126.com 发表于 2019-3-9 02:15
然后我最近发现SSE4.2里有专门的CRC32指令,循环里用CRC32指令可以直接省略定义CRC表,还有那些指令。 ...
嗯,虽说使用了这个指令也就意味着你的程序要依赖带有SSE4.2指令集的处理器了。 头次来这里,全是干货呀,谢谢分享!
页:
[1]