CRCs are among the best checksums available
to detect and/or correct errors in communications
transmissions.
Unfortunately, the modulo2 arithmetic used to compute
CRCs doesn't map easily into software. This article shows how to
implement an efficient CRC in C.
I'm going to complete my discussion of checksums by showing you
how to implement CRCs in software. I'll start with a naïve implementation
and gradually improve the efficiency of the code as I go along.
However, I'm going to keep the discussion at the level of the
C language, so further steps could be taken to improve the efficiency
of the final code simply by moving into the assembly language
of your particular processor.
For most software engineers, the overwhelmingly confusing thing
about CRCs is their implementation. Knowing that all CRC algorithms
are simply long division algorithms in disguise doesn't help.
Modulo2 binary division doesn't map particularly well to the
instruction sets of offtheshelf processors. For one thing, generally
no registers are available to hold the very long bit sequence
that is the numerator. For another, modulo2 binary division is
not the same as ordinary division. So even if your processor has
a division instruction, you won't be able to use it.
Modulo2 binary division
Before writing even one line of code, let's first examine the
mechanics of modulo2 binary division. We'll use the example in
Figure 1 to guide us. The number to be divided is the message
augmented with zeros at the end. The number of zero bits added
to the message is the same as the width of the checksum (what
I call c); in this case four bits were added.
The divisor is a c+1bit number known as the generator
polynomial.
Figure 1. An example of modulo2 binary division
The modulo2 division process is defined as follows:
 Call the uppermost c+1 bits of the message the remainder
 Beginning with the most significant bit in the original message
and for each bit position that follows, look at the c+1 bit
remainder:
 If the most significant bit of the remainder is a one,
the divisor is said to divide into it. If that happens (just
as in any other long division) it is necessary to indicate
a successful division in the appropriate bit position in
the quotient and to compute the new remainder. In the case
of modulo2 binary division, we simply:
 Set the appropriate bit in the quotient to a one,
and
 XOR the remainder with the divisor and store the result
back into the remainder
 Otherwise (if the first bit is not a one):
 Set the appropriate bit in the quotient to a zero,
and
 XOR the remainder with zero (no effect)
 Leftshift the remainder, shifting in the next bit of
the message. The bit that's shifted out will always be a
zero, so no information is lost.
The final value of the remainder is the CRC of the given message.
What's most important to notice at this point is that we never
use any of the information in the quotient, either during or after
computing the CRC. So we won't actually need to track the quotient
in our software implementation. Also note here that the result
of each XOR with the generator polynomial is a remainder that
has zero in its most significant bit. So we never lose any information
when the next message bit is shifted into the remainder.
