【算法】CRC32的C语言实现和NASM汇编语言实现

0xAA55

CRC32是用来校验数据是否正确的简易方法。它的算法很简单，把上次计算的CRC码的低8位和数据字节做异或运算，得到的值用作CRC表的索引，从CRC表提取一个数字并把旧的CRC码右移8位然后把这个移动了的旧CRC码和从CRC表提取出的数字作异或运算得出新的CRC码。进行多次这样的运算可以计算多个字节的数据的CRC码。
这个算法用汉语不好描述，但是用C语言很好描述，就像这样：

1. typedef unsigned long crc_t;
   
2. 
   
3. crc_t crc32(crc_t crc,void*pBuf,unsigned int cbSize)
   
4. {
   
5.         crc^=0xffffffffUL;
   
6.         do
   
7.                 crc=crc_table［((int)crc^(*(unsigned char*)pBuf++))&0xFF］^(crc>>8);
   
8.         while(--cbSize);
   
9.         return crc^0xffffffffUL;
   
10. }

复制代码

而NASM汇编的也很简单，这样写：

1. _crc32:
   
2. push esi
   
3. mov edx,[esp+8]                                ;edx存储crc32的值
   
4. mov esi,[esp+12]                        ;esi指向数据
   
5. mov ecx,[esp+16]                        ;ecx计字节数
   
6. 
   
7. xor eax,eax                                        ;eax清零
   
8. not edx                                                ;crc求反
   
9. 
   
10. .LoopBytes:
    
11. lodsb                                                ;读取字节al=*esi++
    
12. xor al,dl                                        ;字节异或
    
13. shr edx,8                                        ;crc右移8位
    
14. xor edx,[eax*4+_crc_table]        ;crc表取值然后和edx异或
    
15. loop .LoopBytes                                ;处理所有字节
    
16. 
    
17. mov eax,edx                                        ;设置返回值
    
18. not eax                                                ;求反
    
19. 
    
20. pop esi                                                ;恢复esi的值
    
21. ret

复制代码

那么这两个算法都需要一个crc表。这个表是一个什么样的表呢？C语言是这样表示的：

1. crc_t crc_table[256]=
   
2. {
   
3.         0x00000000UL, 0x77073096UL, 0xee0e612cUL, 0x990951baUL,
   
4.         0x076dc419UL, 0x706af48fUL, 0xe963a535UL, 0x9e6495a3UL,
   
5.         0x0edb8832UL, 0x79dcb8a4UL, 0xe0d5e91eUL, 0x97d2d988UL,
   
6.         0x09b64c2bUL, 0x7eb17cbdUL, 0xe7b82d07UL, 0x90bf1d91UL,
   
7.         0x1db71064UL, 0x6ab020f2UL, 0xf3b97148UL, 0x84be41deUL,
   
8.         0x1adad47dUL, 0x6ddde4ebUL, 0xf4d4b551UL, 0x83d385c7UL,
   
9.         0x136c9856UL, 0x646ba8c0UL, 0xfd62f97aUL, 0x8a65c9ecUL,
   
10.         0x14015c4fUL, 0x63066cd9UL, 0xfa0f3d63UL, 0x8d080df5UL,
    
11.         0x3b6e20c8UL, 0x4c69105eUL, 0xd56041e4UL, 0xa2677172UL,
    
12.         0x3c03e4d1UL, 0x4b04d447UL, 0xd20d85fdUL, 0xa50ab56bUL,
    
13.         0x35b5a8faUL, 0x42b2986cUL, 0xdbbbc9d6UL, 0xacbcf940UL,
    
14.         0x32d86ce3UL, 0x45df5c75UL, 0xdcd60dcfUL, 0xabd13d59UL,
    
15.         0x26d930acUL, 0x51de003aUL, 0xc8d75180UL, 0xbfd06116UL,
    
16.         0x21b4f4b5UL, 0x56b3c423UL, 0xcfba9599UL, 0xb8bda50fUL,
    
17.         0x2802b89eUL, 0x5f058808UL, 0xc60cd9b2UL, 0xb10be924UL,
    
18.         0x2f6f7c87UL, 0x58684c11UL, 0xc1611dabUL, 0xb6662d3dUL,
    
19.         0x76dc4190UL, 0x01db7106UL, 0x98d220bcUL, 0xefd5102aUL,
    
20.         0x71b18589UL, 0x06b6b51fUL, 0x9fbfe4a5UL, 0xe8b8d433UL,
    
21.         0x7807c9a2UL, 0x0f00f934UL, 0x9609a88eUL, 0xe10e9818UL,
    
22.         0x7f6a0dbbUL, 0x086d3d2dUL, 0x91646c97UL, 0xe6635c01UL,
    
23.         0x6b6b51f4UL, 0x1c6c6162UL, 0x856530d8UL, 0xf262004eUL,
    
24.         0x6c0695edUL, 0x1b01a57bUL, 0x8208f4c1UL, 0xf50fc457UL,
    
25.         0x65b0d9c6UL, 0x12b7e950UL, 0x8bbeb8eaUL, 0xfcb9887cUL,
    
26.         0x62dd1ddfUL, 0x15da2d49UL, 0x8cd37cf3UL, 0xfbd44c65UL,
    
27.         0x4db26158UL, 0x3ab551ceUL, 0xa3bc0074UL, 0xd4bb30e2UL,
    
28.         0x4adfa541UL, 0x3dd895d7UL, 0xa4d1c46dUL, 0xd3d6f4fbUL,
    
29.         0x4369e96aUL, 0x346ed9fcUL, 0xad678846UL, 0xda60b8d0UL,
    
30.         0x44042d73UL, 0x33031de5UL, 0xaa0a4c5fUL, 0xdd0d7cc9UL,
    
31.         0x5005713cUL, 0x270241aaUL, 0xbe0b1010UL, 0xc90c2086UL,
    
32.         0x5768b525UL, 0x206f85b3UL, 0xb966d409UL, 0xce61e49fUL,
    
33.         0x5edef90eUL, 0x29d9c998UL, 0xb0d09822UL, 0xc7d7a8b4UL,
    
34.         0x59b33d17UL, 0x2eb40d81UL, 0xb7bd5c3bUL, 0xc0ba6cadUL,
    
35.         0xedb88320UL, 0x9abfb3b6UL, 0x03b6e20cUL, 0x74b1d29aUL,
    
36.         0xead54739UL, 0x9dd277afUL, 0x04db2615UL, 0x73dc1683UL,
    
37.         0xe3630b12UL, 0x94643b84UL, 0x0d6d6a3eUL, 0x7a6a5aa8UL,
    
38.         0xe40ecf0bUL, 0x9309ff9dUL, 0x0a00ae27UL, 0x7d079eb1UL,
    
39.         0xf00f9344UL, 0x8708a3d2UL, 0x1e01f268UL, 0x6906c2feUL,
    
40.         0xf762575dUL, 0x806567cbUL, 0x196c3671UL, 0x6e6b06e7UL,
    
41.         0xfed41b76UL, 0x89d32be0UL, 0x10da7a5aUL, 0x67dd4accUL,
    
42.         0xf9b9df6fUL, 0x8ebeeff9UL, 0x17b7be43UL, 0x60b08ed5UL,
    
43.         0xd6d6a3e8UL, 0xa1d1937eUL, 0x38d8c2c4UL, 0x4fdff252UL,
    
44.         0xd1bb67f1UL, 0xa6bc5767UL, 0x3fb506ddUL, 0x48b2364bUL,
    
45.         0xd80d2bdaUL, 0xaf0a1b4cUL, 0x36034af6UL, 0x41047a60UL,
    
46.         0xdf60efc3UL, 0xa867df55UL, 0x316e8eefUL, 0x4669be79UL,
    
47.         0xcb61b38cUL, 0xbc66831aUL, 0x256fd2a0UL, 0x5268e236UL,
    
48.         0xcc0c7795UL, 0xbb0b4703UL, 0x220216b9UL, 0x5505262fUL,
    
49.         0xc5ba3bbeUL, 0xb2bd0b28UL, 0x2bb45a92UL, 0x5cb36a04UL,
    
50.         0xc2d7ffa7UL, 0xb5d0cf31UL, 0x2cd99e8bUL, 0x5bdeae1dUL,
    
51.         0x9b64c2b0UL, 0xec63f226UL, 0x756aa39cUL, 0x026d930aUL,
    
52.         0x9c0906a9UL, 0xeb0e363fUL, 0x72076785UL, 0x05005713UL,
    
53.         0x95bf4a82UL, 0xe2b87a14UL, 0x7bb12baeUL, 0x0cb61b38UL,
    
54.         0x92d28e9bUL, 0xe5d5be0dUL, 0x7cdcefb7UL, 0x0bdbdf21UL,
    
55.         0x86d3d2d4UL, 0xf1d4e242UL, 0x68ddb3f8UL, 0x1fda836eUL,
    
56.         0x81be16cdUL, 0xf6b9265bUL, 0x6fb077e1UL, 0x18b74777UL,
    
57.         0x88085ae6UL, 0xff0f6a70UL, 0x66063bcaUL, 0x11010b5cUL,
    
58.         0x8f659effUL, 0xf862ae69UL, 0x616bffd3UL, 0x166ccf45UL,
    
59.         0xa00ae278UL, 0xd70dd2eeUL, 0x4e048354UL, 0x3903b3c2UL,
    
60.         0xa7672661UL, 0xd06016f7UL, 0x4969474dUL, 0x3e6e77dbUL,
    
61.         0xaed16a4aUL, 0xd9d65adcUL, 0x40df0b66UL, 0x37d83bf0UL,
    
62.         0xa9bcae53UL, 0xdebb9ec5UL, 0x47b2cf7fUL, 0x30b5ffe9UL,
    
63.         0xbdbdf21cUL, 0xcabac28aUL, 0x53b39330UL, 0x24b4a3a6UL,
    
64.         0xbad03605UL, 0xcdd70693UL, 0x54de5729UL, 0x23d967bfUL,
    
65.         0xb3667a2eUL, 0xc4614ab8UL, 0x5d681b02UL, 0x2a6f2b94UL,
    
66.         0xb40bbe37UL, 0xc30c8ea1UL, 0x5a05df1bUL, 0x2d02ef8dUL
    
67. };

复制代码

共256个表项。那个crc_t其实就是32位无符号整数，x86和x64下是unsigned long。用汇编语言表示就是

1. _crc_table:
   
2. dd        0x00000000, 0x77073096, 0xee0e612c, 0x990951ba
   
3. dd        0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3
   
4. dd        0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988
   
5. dd        0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91
   
6. dd        0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de
   
7. dd        0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7
   
8. dd        0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec
   
9. dd        0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5
   
10. dd        0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172
    
11. dd        0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b
    
12. dd        0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940
    
13. dd        0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59
    
14. dd        0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116
    
15. dd        0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f
    
16. dd        0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924
    
17. dd        0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d
    
18. dd        0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a
    
19. dd        0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433
    
20. dd        0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818
    
21. dd        0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01
    
22. dd        0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e
    
23. dd        0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457
    
24. dd        0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c
    
25. dd        0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65
    
26. dd        0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2
    
27. dd        0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb
    
28. dd        0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0
    
29. dd        0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9
    
30. dd        0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086
    
31. dd        0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f
    
32. dd        0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4
    
33. dd        0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad
    
34. dd        0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a
    
35. dd        0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683
    
36. dd        0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8
    
37. dd        0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1
    
38. dd        0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe
    
39. dd        0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7
    
40. dd        0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc
    
41. dd        0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5
    
42. dd        0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252
    
43. dd        0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b
    
44. dd        0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60
    
45. dd        0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79
    
46. dd        0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236
    
47. dd        0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f
    
48. dd        0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04
    
49. dd        0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d
    
50. dd        0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a
    
51. dd        0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713
    
52. dd        0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38
    
53. dd        0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21
    
54. dd        0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e
    
55. dd        0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777
    
56. dd        0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c
    
57. dd        0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45
    
58. dd        0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2
    
59. dd        0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db
    
60. dd        0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0
    
61. dd        0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9
    
62. dd        0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6
    
63. dd        0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf
    
64. dd        0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94
    
65. dd        0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d

复制代码

完整的文件我这里提供下载。
以下这两个文件可以独立下载。二选一。
C语言版本：crc32.c: crc32.c (4.69 KB, 下载次数: 1, 售价: 2 个宅币)

2014-8-10 23:40 上传

点击文件名下载附件

NASM汇编版本(x86)：crc32.asm: crc32.asm (3.84 KB, 下载次数: 2, 售价: 2 个宅币)

2014-8-10 23:41 上传

点击文件名下载附件

以下这是实例。
一个完整的VC6工程： crc32VC6.7z (58.11 KB, 下载次数: 1, 售价: 3 个宅币)

2014-8-10 23:47 上传

点击文件名下载附件

一个完整的VS2012工程： crc32VS2012.7z (24.64 KB, 下载次数: 2, 售价: 5 个宅币)

2014-8-11 00:38 上传

点击文件名下载附件

唐凌

然后我最近发现SSE4.2里有专门的CRC32指令，循环里用CRC32指令可以直接省略定义CRC表，还有那些指令。

0xAA55

tangptr@126.com 发表于 2019-3-9 02:15
然后我最近发现SSE4.2里有专门的CRC32指令，循环里用CRC32指令可以直接省略定义CRC表，还有那些指令。 ...

嗯，虽说使用了这个指令也就意味着你的程序要依赖带有SSE4.2指令集的处理器了。

a46213599

头次来这里，全是干货呀，谢谢分享!