比常规CRC32C算法快12倍的优化.解决方案

比常规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，就比从内存读省了不知道多少时间了，运算部分不会差太多吧

查看更多 下一篇