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

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

<GUFFAW> Sorry, that was uncalled for.

I can't speak for highly-optimised algorithms or for SIMD stuff, and would also suggest that the appropriate implementation depends on whether you're checksumming an entire buffer or are doing it byte-by-byte.

There's lots of different algorithms, which may be defined by starting value, polynomial, and whether the value is negated at various points. Even assuming the same length, the CRC varies depending on the application: CRCs were originally designed to detect the type of impulsive errors you'd get on a comms line so to some extent depended on the bit rate relative to the predominant electrical noise which was typically non-random. For applications other than that, e.g. to verify a block of text which might be corrupted randomly, a cryptographic hash is better.

I've used them quite a lot over the years. A couple of years ago I was interfacing to a piece of test equipment and used the CRC units from http://www.wolfgang-ehrhardt.de/crchash_en.html to explore arbitrary message blocks and identify which CRC each appeared to use and (hence) where each one ended. I believe they can be classes as freeware, and I think they could usefully be added to FPC.

Another useful resource for those with plenty of time on their hands is http://www.quadibloc.com

Ok, thanks. This is yet another topic I should learn about.

Tony, I don't believe pycrc can generate much faster functions than ours unless it uses SIMD.
Our function works well but it is called so ofter that its speed is relevant.

Mark, I promise to study the algorithms but changing our algorith is not an option now. We want the same but faster.
Maybe loop unrolling can make it little faster but nothing compared to a SIMD version of course.

Juha

Juha,

You may find these references useful

"Computation of Cyclic Redundancy Checks vis Table Lookup" Dilip V Sarwate, Communications of the ACM, August 1988.

"An Arithmetic Checksum for Serial Transmission" John G. Fletcher, IEEE Transactions on Communications, January 1982

Juha Manninen wrote

Ok, thanks. This is yet another topic I should learn about.

My point was to take a look at the ones in the library, and see if one matches and if so whether it's faster (and then work out why). However I'm a bit dubious about your and $00FFFFFF operation which I suspect makes your implementation non-standard.

Loop unrolling may be an option, as might making sure that FPC is compiling the CRC generator with the best possible set of options. Using a thread probably isn't unless the buffers are large and you've got other useful work to do in parallel.

Quote :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.> hashing function at application level

Problem : does it exist on other processor architectures ?

An alternative if you dont need a standard CRC, for FPC internals. Needs to be retested by someone else.

What I dont know is if this algorythm would always give the EXACT same hash value on any processor. It is written in pure pascal so should be testable on various achitectures.

These are my timings calculating CRC and FNV Hash on a Win32 Dual-Core CPU.

Calculating CRC, FNVHash and SHA1 on file
lazarus\1.3\lcl\include\wincontrol.inc rev. 45788

Compiled with -O3

CRC : 2 ms, 48 mus CRC : 7df71ee1 unit fpccrc.pas

FNV : 619 mus FNV : 54b39e30 unit uFnvHash32buf.pp

SHA1 : 3 ms, 318 mus unit fpc-2.6.4\packages\hash\src\sha1.pp

CRC handles 1 complete buffer at the byte level

FNV handles 1 complete buffer at the DWORD level (Probably a problem with Endianness)

SHA1 handles streams and can be continued after intermediate results and of course returns a very long digest.

Tony Whyman wrote

There are indeed many different CRC algorithms. The division polynomial typically determines the function

And why I always favoured SHA1 instead of CRC. I don't have vast knowledge on the subject, but SHA1 seems more standardised than CRC. At least with the tests I have done, using various SHA1 implementations, they gave me consistent results.

I know this doesn't help your cause Juha. I too read that article you quoted, and was very impressed by the speed increase of the SSE enabled CRC, but returning different results makes it unusable with existing code and stored CRC values - at least you spotted that part too. ;-)

Regards,
- Graeme -

Graeme Geldenhuys wrote

And why I always favoured SHA1 instead of CRC. I don't have vast knowledge on the subject, but SHA1 seems more standardised than CRC. At least with the tests I have done, using various SHA1 implementations, they gave me consistent results.

It's "horses for courses". SHA-1 checksums add 160 bits to each message while a 16 bit CRC adds 16 bits. CRCs main use is with low speed modems. They can be readily implemented in hardware and when the division polynomial is carefully chosen can give an undetected bit error rate of better than 1 in 10^8, which is more than sufficient for the data volume possible. SHA-1 can give a ridiculously low undetected bit error rate but the computational and bit overhead is not really justified in such applications.

CRCs are fully standardised by the laws of arithmetic. What tends to confuse is that CRCs are a class of functions each characterised by a different division polynomial - while SHA-1 is a single function. When we talk about CRC-16 or CRC-32, all you are defining is the number of coefficients (i.e. bits) in the remainder and not the division polynomial itself. In order to fully define the CRC you must also define the division polynomial and how you arrange the bits in the message (as polynomial coefficients). There are both bigendian and little endian variants plus bit reflections possible.

What has always surprised me is when CRCs are used outside of the communications domain. Arithmetic checksums can give similar performance with lower computational overhead and the same bit length. CRCs only really have the edge with communications because the error pattern is typically known for a given communications medium and the CRC can be tuned to the media in order to give better performance. Alternatively, when you have a more longer term or security need to protect integrity then message digests (like SHA-1) are what you should be using.

I know this doesn't help your cause Juha. I too read that article you quoted, and was very impressed by the speed increase of the SSE enabled CRC, but returning different results makes it unusable with existing code and stored CRC values - at least you spotted that part too. ;-)

CRCs are computed by polynomial division. For a given polynomial and bit layout they are deterministic. if an implementation claims to implement the same CRC and gives a different result to a standard implementation then it's a bug and not a feature.

CRC is invented to do it in hardware (using a shift register and some XOR gates), and hence happily supports very high speed transfer. But it can rather efficiently be done in Software using a Table (e.g. 256 entries).

With a decent Polynomial, the "single bit error undetected" rate is zero (as with all theses algorithms), while the "multi-bit error undetected" (of course) depends on CTC size (most common is 32 Bits, then 16 bits, but in theory any bit rate is doable, in certain applications I do use 4 Bits and 5 Bits). This depends on the difference between the count of CRC bits and the binary log of the count of message bits per block (Hamming distance -> http://en.wikipedia.org/wiki/Hamming_distance).

Moreover with a "complete" polynomial a single bit error can be not only detected but also corrected.

CRCs are a class of functions each characterised by a different division polynomial

More characteristics that can be differ in certain applications are
- bit count
- starting value
- shift count (only data block bits or data block bits plus CRC bits
- order of the bits (including bits in bytes and/or words), as well in the data block as in the CRC itself
- sometimes the data bits are inverted before the CRC calculation, sometimes the CRC bits are inverted before transmission.

CRCs are computed by polynomial division. For a given polynomial and bit layout they are deterministic. if an implementation claims to implement the same CRC and gives a different result to a standard implementation then it's a bug and not a feature.

Yep.

-Michael

That is the important point. If looking at a communications channel (e.g. a file on disc, after the OS etc. has done its bit to promote reliability) where the error distribution is perfectly random then a checksum is a better test of correctness than a CRC. But a checksum is easily fooled if the channel is malicious, which gave rise to the various cryptographic message digest algorithms including SHA-1.

None of which really helps Juha, whose problem boils down to identifying which CRC algorithm he's using as the prerequisite to finding out whether its performance can be improved.

Tony Whyman wrote

CRCs only really have the edge with communications because the error pattern is typically known for a given communications medium and the CRC can be tuned to the media in order to give better performance.

Even in software-only applications, CRCs are used rather ubiquitously. e.g. ZIP uses CRC 32.

-Michael

Certainly true, but doesn't necessarily invalidate my comment.

The zip format is an interesting case and it would be of (academic) interest to know if Phil Katz used a 32 bit CRC after researching alternatives - or simply because CRCs are widely used.

On the other hand, if you get a bit error in compressed data then the Deflate algorithm will tend to replicate and magnify the error as it decompresses the message resulting in a very different outcome to the original message. Hence any half decent checksum whether CRC or otherwise should pick up the error.

In our previous episode, Michael Schnell said:

More characteristics that can be differ in certain applications are - bit count - starting value - shift count (only data block bits or data block bits plus CRC bits

- Shift direction. msbit first, lsbit first, in case of wordwise crc also low/hi byte.
- in case of (d)wordwise CRCs padding value.

- order of the bits (including bits in bytes and/or words), as well in the data block as in the CRC itself - sometimes the data bits are inverted before the CRC calculation, sometimes the CRC bits are inverted before transmission.