找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 5387|回复: 3

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

[复制链接]

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2014-8-11 00:38:57 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

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

  2. crc_t crc32(crc_t crc,void*pBuf,unsigned int cbSize)
  3. {
  4.         crc^=0xffffffffUL;
  5.         do
  6.                 crc=crc_table[((int)crc^(*(unsigned char*)pBuf++))&0xFF]^(crc>>8);
  7.         while(--cbSize);
  8.         return crc^0xffffffffUL;
  9. }
复制代码
而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. xor eax,eax                                        ;eax清零
  7. not edx                                                ;crc求反

  8. .LoopBytes:
  9. lodsb                                                ;读取字节al=*esi++
  10. xor al,dl                                        ;字节异或
  11. shr edx,8                                        ;crc右移8位
  12. xor edx,[eax*4+_crc_table]        ;crc表取值然后和edx异或
  13. loop .LoopBytes                                ;处理所有字节

  14. mov eax,edx                                        ;设置返回值
  15. not eax                                                ;求反

  16. pop esi                                                ;恢复esi的值
  17. 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 个宅币)
NASM汇编版本(x86):crc32.asm: crc32.asm (3.84 KB, 下载次数: 2, 售价: 2 个宅币)

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

本帖被以下淘专辑推荐:

回复

使用道具 举报

65

主题

113

回帖

1万

积分

用户组: 超级版主

OS与VM研究学者

UID
1043
精华
35
威望
789 点
宅币
8246 个
贡献
1094 次
宅之契约
0 份
在线时间
2053 小时
注册时间
2015-8-15
发表于 2019-3-9 02:15:58 | 显示全部楼层
然后我最近发现SSE4.2里有专门的CRC32指令,循环里用CRC32指令可以直接省略定义CRC表,还有那些指令。
回复 赞! 靠!

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
 楼主| 发表于 2019-3-9 18:09:34 | 显示全部楼层
tangptr@126.com 发表于 2019-3-9 02:15
然后我最近发现SSE4.2里有专门的CRC32指令,循环里用CRC32指令可以直接省略定义CRC表,还有那些指令。 ...

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

使用道具 举报

0

主题

3

回帖

28

积分

用户组: 初·技术宅

UID
6130
精华
0
威望
6 点
宅币
13 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2020-8-13
发表于 2020-8-13 21:57:13 | 显示全部楼层
头次来这里,全是干货呀,谢谢分享!
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-28 20:30 , Processed in 0.044131 second(s), 37 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表