[fpc-pascal] Fast CRC functions?

[Tony Whyman]

On 31/08/14 12:07, 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.