比常规CRC32C算法快12倍的优化.
CRC-32C (Castagnoli) 算法是 iSCSI 和SCTP 数据校验的算法，和常用CRC-32-IEEE 802.3算法所不同的是多项式常数CRC32C是0x1EDC6F41 ,CRC32是0x04C11DB7 ,也就是说由此生成的CRC表不同外算法是一模一样.
CRC32 常规算法如下：
- Delphi(Pascal) code
function _CRC32CX86(Data: PByte; aLength: Integer): DWORD; const _CRC32CTable: array[0..255] of DWORD = ( $00000000, $F26B8303, $E13B70F7, $1350F3F4, //CRC32C Table $C79A971F, $35F1141C, $26A1E7E8, $D4CA64EB, $8AD958CF, $78B2DBCC, $6BE22838, $9989AB3B, $4D43CFD0, $BF284CD3, $AC78BF27, $5E133C24, $105EC76F, $E235446C, $F165B798, $030E349B, $D7C45070, $25AFD373, $36FF2087, $C494A384, $9A879FA0, $68EC1CA3, $7BBCEF57, $89D76C54, $5D1D08BF, $AF768BBC, $BC267848, $4E4DFB4B, $20BD8EDE, $D2D60DDD, $C186FE29, $33ED7D2A, $E72719C1, $154C9AC2, $061C6936, $F477EA35, $AA64D611, $580F5512, $4B5FA6E6, $B93425E5, $6DFE410E, $9F95C20D, $8CC531F9, $7EAEB2FA, $30E349B1, $C288CAB2, $D1D83946, $23B3BA45, $F779DEAE, $05125DAD, $1642AE59, $E4292D5A, $BA3A117E, $4851927D, $5B016189, $A96AE28A, $7DA08661, $8FCB0562, $9C9BF696, $6EF07595, $417B1DBC, $B3109EBF, $A0406D4B, $522BEE48, $86E18AA3, $748A09A0, $67DAFA54, $95B17957, $CBA24573, $39C9C670, $2A993584, $D8F2B687, $0C38D26C, $FE53516F, $ED03A29B, $1F682198, $5125DAD3, $A34E59D0, $B01EAA24, $42752927, $96BF4DCC, $64D4CECF, $77843D3B, $85EFBE38, $DBFC821C, $2997011F, $3AC7F2EB, $C8AC71E8, $1C661503, $EE0D9600, $FD5D65F4, $0F36E6F7, $61C69362, $93AD1061, $80FDE395, $72966096, $A65C047D, $5437877E, $4767748A, $B50CF789, $EB1FCBAD, $197448AE, $0A24BB5A, $F84F3859, $2C855CB2, $DEEEDFB1, $CDBE2C45, $3FD5AF46, $7198540D, $83F3D70E, $90A324FA, $62C8A7F9, $B602C312, $44694011, $5739B3E5, $A55230E6, $FB410CC2, $092A8FC1, $1A7A7C35, $E811FF36, $3CDB9BDD, $CEB018DE, $DDE0EB2A, $2F8B6829, $82F63B78, $709DB87B, $63CD4B8F, $91A6C88C, $456CAC67, $B7072F64, $A457DC90, $563C5F93, $082F63B7, $FA44E0B4, $E9141340, $1B7F9043, $CFB5F4A8, $3DDE77AB, $2E8E845F, $DCE5075C, $92A8FC17, $60C37F14, $73938CE0, $81F80FE3, $55326B08, $A759E80B, $B4091BFF, $466298FC, $1871A4D8, $EA1A27DB, $F94AD42F, $0B21572C, $DFEB33C7, $2D80B0C4, $3ED04330, $CCBBC033, $A24BB5A6, $502036A5, $4370C551, $B11B4652, $65D122B9, $97BAA1BA, $84EA524E, $7681D14D, $2892ED69, $DAF96E6A, $C9A99D9E, $3BC21E9D, $EF087A76, $1D63F975, $0E330A81, $FC588982, $B21572C9, $407EF1CA, $532E023E, $A145813D, $758FE5D6, $87E466D5, $94B49521, $66DF1622, $38CC2A06, $CAA7A905, $D9F75AF1, $2B9CD9F2, $FF56BD19, $0D3D3E1A, $1E6DCDEE, $EC064EED, $C38D26C4, $31E6A5C7, $22B65633, $D0DDD530, $0417B1DB, $F67C32D8, $E52CC12C, $1747422F, $49547E0B, $BB3FFD08, $A86F0EFC, $5A048DFF, $8ECEE914, $7CA56A17, $6FF599E3, $9D9E1AE0, $D3D3E1AB, $21B862A8, $32E8915C, $C083125F, $144976B4, $E622F5B7, $F5720643, $07198540, $590AB964, $AB613A67, $B831C993, $4A5A4A90, $9E902E7B, $6CFBAD78, $7FAB5E8C, $8DC0DD8F, $E330A81A, $115B2B19, $020BD8ED, $F0605BEE, $24AA3F05, $D6C1BC06, $C5914FF2, $37FACCF1, $69E9F0D5, $9B8273D6, $88D28022, $7AB90321, $AE7367CA, $5C18E4C9, $4F48173D, $BD23943E, $F36E6F75, $0105EC76, $12551F82, $E03E9C81, $34F4F86A, $C69F7B69, $D5CF889D, $27A40B9E, $79B737BA, $8BDCB4B9, $988C474D, $6AE7C44E, $BE2DA0A5, $4C4623A6, $5F16D052, $AD7D5351); var i: Integer; begin Result := $FFFFFFFF; for I := 0 to aLength - 1 do begin Result := (Result shr 8) xor _CRC32CTable[(Result and $FF) xor Data^]; Inc(Data); end; Result := not Result; end;
CRC32C使用SSE4.2硬件指令优化算法部分代码如下：
- Delphi(Pascal) code
function _CRC32CSSE(Data: PByte; aLength: Integer): DWORD; asm push esi push edx push ecx mov esi,eax mov eax,$FFFFFFFF test edx,edx jz @Exit test esi,esi jz @Exit mov ecx,edx shr ecx, 2 test ecx,ecx jz @Exit xor edx,edx@Alignment: crc32 eax,[edx*4+esi] inc edx cmp edx,ecx jb @Alignment@Exit: not eax pop ecx pop edx pop esiend;
以上2个不同实现方式在Intel Core i7 720QM 1.60GHz CPU上测试成绩如下：
(数据采用随机算法生成，1M*100表示使用1M数据进行100次重复计算，数据量相当于100M)
--------------------------------------------------
| 数据量 | 常规算法时间 | 优化算法时间 | 快出百分比 |
--------------------------------------------------
| 1M *100 | X86 Time:390ms | SSE Time:32ms | 1218% |
--------------------------------------------------
| 4M *100 | X86 Time:1575ms | SSE Time:156ms | 1009% |
--------------------------------------------------
| 8M *100 | X86 Time:3136ms | SSE Time:280ms | 1120% |
--------------------------------------------------
| 32M *100 | X86 Time:12542ms | SSE Time:1092ms | 1148% |
--------------------------------------------------
通过对比可以清楚的看到使用SSE4.2中的新指令crc32可以比常规CRC32C算法要快出最少10倍的效率，Intel新增的指令确实对常规某些算法提供了高效的解决方案，使用好它们将对我们在以后的开发中得到质的提升。
[解决办法]
MARK...
[解决办法]
建议你也编写个DEMO程序,也传上来吧谢谢
[解决办法]
先Mark，再看
[解决办法]
mark 一下，偏听则暗兼听则明，听听其他高手是啥意见~~
[解决办法]
支持研究性能优化，不过建议还是在楼主“使用1M数据进行100次重复计算”的基础上，使用非重复的100M，甚至1G数据(随机生成即可)进行运算，这样更接近于真实环境。毕竟重复计算难免多少从某些缓冲机制中受益的。
[解决办法]
@Alignment:
crc32 eax,[edx*4+esi]
inc edx
cmp edx,ecx
jb @Alignment
这里面的 crc32 eax,[edx*4+esi] 这一句应该是硬件指令吧，
for I := 0 to aLength - 1 do
begin
Result := (Result shr 8) xor _CRC32CTable[(Result and $FF) xor Data^];
Inc(Data);
end;
分析一下这句，For 循环一个计数器 一个跳转指令，
一个shr 一个xor 一个Xor 两个寻址，一个ADD
本身也没有多少时钟周期，
硬件指令中同样需要循环和寻址。
应该跟具体算法关系不大，虽然结果看起来是快了十倍。
[解决办法]
楼主试下这个函数呢,希望差距小点点,我这CPU不支持
function _CRC32CX86(Data: Pointer; Size: Integer): DWORD;
asm
PUSH EBX;
MOV ECX , EDX;
MOV EDX , EAX;
MOV EAX , $FFFFFFFF;
@@Loop:
XOR EBX , EBX
MOV BL , AL;
XOR BL , BYTE PTR [EDX];
SHR EAX , 8;
XOR EAX , DWORD PTR _CRC32Table + EBX*4;
INC EDX;
Loop @@Loop
NOT EAX;
POP EBX;
end;
[解决办法]
lz的机器不错。。。
sse4.2要新机器 Nehalem 架构以后的才支持。
[解决办法]
用CRC32指令是快，但是结果与标准CRC32算法不一致，所以只能程序中自己用，不能用于校验其他程序-比如RAR-生成的校验码。
另外，这个_CRC32CSSE有BUG，只能验算4的倍数长度的数据，否则结果是错误的。先改正了再说性能吧。
------解决方案--------------------
嗯 ，确实比CRC16,CRC32代码快多了！ 学习！
[解决办法]
地址搞死我了。
procedure TForm2.Button1Click(Sender: TObject);
var
Data: array [0 .. 1023] of Byte;
Data2: array of Byte;
Pd: PByte;
Fs: TFileStream;
begin
try
// demo1
Pd := @Data;
FillChar(Data, 1024, 1);
ShowMessage(IntToStr(_CRC32CX86(Pd, 1024)));
// demo2
Fs := TFileStream.Create('E:\iTAS\Source\Lib\Common\access.txt', FmOpenRead);
SetLength(Data2, 1024);
Pd := @Data2[0];
Fs.Position := 0;
Fs.Read(Pd^, Fs.Size); // 动态数组指针，可以得到数据
// Fs.Read(Data2, Fs.Size); // 动态数组，得不到数据
// Fs.Read(Data, Fs.Size); // 静态数组，可以得到数据
// 结论：
// 动态数组的首地址：@DynamicArray[0];
// 静态数组的首地址：@StaticArray[0]或@StaticArray.
ShowMessage(IntToHex(_CRC32CX86(Pd, Fs.Size), 8));
finally
Fs.Free;
end;
end;
[解决办法]
但是得到的crc32值跟其他工具计算出来的有不一致
[解决办法]
CPU内建的CRC table，就比从内存读省了不知道多少时间了，运算部分不会差太多吧