[fpc-pascal] Fast CRC functions?

[Tony Whyman]

Juha,

There are indeed many different CRC algorithms. The division polynomial
typically determines the function - but there are other tweaks including
whether you are dealing with big endian or little endian numbers. The
division polynomial is chosen such that it never divides exactly into
the predicted error pattern (i.e. leaves a zero remainder) and as such
is tuned to a specific communications medium.

The super fast function you have found is almost certainly table driven
as these algorithms  are much faster than direct computation. In the 'C'
world, you can generate your own CRC generator and checker for any given
polynomial using the generator at

http://www.tty1.net/pycrc/

I have used this successfully on 'C' projects. I suggest that you use
this to generate your CRC checker and either link it directly into your
Pascal program or translate the result to Pascal.


Regards

Tony Whyman
MWA


On 25/08/14 09:46, Juha Manninen wrote:
> We have an old function for calculating CRC like:
>
> function CalcCRC(const Str: String): Cardinal;
> var
>   Len, i, CRCVal: Cardinal;
> Begin
>   Len := Length(Str);
>   CRCVal := $FFFFFFFF;
>   if Len > 0 then
>     for i := 1 to Len do
>       CRCVal := CRCTbl[Byte(CRCVal xor Cardinal(Str[i]))] xor ((CRCVal
> shr 8) and $00FFFFFF);
>   Result := not(CRCVal);
> end;
>
> "CRCTbl" is a table with hex numbers.
>
> Then I tested a new super-fast function crc32c() from Synopse mORMot
> lib that uses Intel SSE instructions:
>
>   http://blog.synopse.info/post/2014/05/25/New-crc32c%28%29-function-using-optimized-asm-and-SSE-4.2-instruction
>
> Wow, with long input data strings it is 10 * faster!
> But, bummer, it returns a different value. :(
> Our CRCs are stored around in DBs and we need the same value.
>
> I thought CRC algorith is a standard but apparently not.
> It says at the Synopse blog-page:
> ---
> In fact, most popular file formats and protocols (Ethernet, MPEG-2,
> ZIP, RAR, 7-Zip, GZip, and PNG) use the polynomial $04C11DB7, while
> Intel's hardware implementation is based on another polynomial,
> $1EDC6F41 (used in iSCSI and Btrfs).
> So you would not use this new crc32c() function to replace the zlib's
> crc32() function, but as a convenient very fast hashing function at
> application level.
> For instance, our TDynArray wrapper will use it for fast items hashing.
> ---
>
> I don't know what the "polynomial" does here. Does it mean Intel CPUs
> have built-in support for specific CRC calculations?
>
> Does anybody know of other optimized CRC functions?
> We would love the speedup.
>
> Regards,
> Juha
> _______________________________________________
> fpc-pascal maillist  -  fpc-pascal at lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal