[fpc-pascal] Fast CRC functions?

[Michael Schnell]

On 09/01/2014 10:12 AM, Tony Whyman wrote:
> 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.
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