crc.txt

Many crc routine in C

will be assuming option b because it is marginally mathematically
cleaner.

A summary of the operation of the class of CRC algorithms:

   1. Choose a width W, and a poly G (of width W).
   2. Append W zero bits to the message. Call this M'.
   3. Divide M' by G using CRC arithmetic. The remainder is the checksum.

That's all there is to it.


7. Choosing A Poly
------------------
Choosing a poly is somewhat of a black art and the reader is referred
to [Tanenbaum81] (p.130-132) which has a very clear discussion of this
issue. This section merely aims to put the fear of death into anyone
who so much as toys with the idea of making up their own poly. If you
don't care about why one poly might be better than another and just
want to find out about high-speed implementations, choose one of the
arithmetically sound polys listed at the end of this section and skip
to the next section.

First note that the transmitted message T is a multiple of the poly.
To see this, note that 1) the last W bits of T is the remainder after
dividing the augmented (by zeros remember) message by the poly, and 2)
addition is the same as subtraction so adding the remainder pushes the
value up to the next multiple. Now note that if the transmitted
message is corrupted in transmission that we will receive T+E where E
is an error vector (and + is CRC addition (i.e. XOR)). Upon receipt of
this message, the receiver divides T+E by G. As T mod G is 0, (T+E)
mod G = E mod G. Thus, the capacity of the poly we choose to catch
particular kinds of errors will be determined by the set of multiples
of G, for any corruption E that is a multiple of G will be undetected.
Our task then is to find classes of G whose multiples look as little
like the kind of line noise (that will be creating the corruptions) as
possible. So let's examine the kinds of line noise we can expect.

SINGLE BIT ERRORS: A single bit error means E=1000...0000. We can
ensure that this class of error is always detected by making sure that
G has at least two bits set to 1. Any multiple of G will be
constructed using shifting and adding and it is impossible to
construct a value with a single bit by shifting an adding a single
value with more than one bit set, as the two end bits will always
persist.

TWO-BIT ERRORS: To detect all errors of the form 100...000100...000
(i.e. E contains two 1 bits) choose a G that does not have multiples
that are 11, 101, 1001, 10001, 100001, etc. It is not clear to me how
one goes about doing this (I don't have the pure maths background),
but Tanenbaum assures us that such G do exist, and cites G with 1 bits
(15,14,1) turned on as an example of one G that won't divide anything
less than 1...1 where ... is 32767 zeros.

ERRORS WITH AN ODD NUMBER OF BITS: We can catch all corruptions where
E has an odd number of bits by choosing a G that has an even number of
bits. To see this, note that 1) CRC multiplication is simply XORing a
constant value into a register at various offsets, 2) XORing is simply
a bit-flip operation, and 3) if you XOR a value with an even number of
bits into a register, the oddness of the number of 1 bits in the
register remains invariant. Example: Starting with E=111, attempt to
flip all three bits to zero by the repeated application of XORing in
11 at one of the two offsets (i.e. "E=E XOR 011" and "E=E XOR 110")
This is nearly isomorphic to the "glass tumblers" party puzzle where
you challenge someone to flip three tumblers by the repeated
application of the operation of flipping any two. Most of the popular
CRC polys contain an even number of 1 bits. (Note: Tanenbaum states
more specifically that all errors with an odd number of bits can be
caught by making G a multiple of 11).

BURST ERRORS: A burst error looks like E=000...000111...11110000...00.
That is, E consists of all zeros except for a run of 1s somewhere
inside. This can be recast as E=(10000...00)(1111111...111) where
there are z zeros in the LEFT part and n ones in the RIGHT part. To
catch errors of this kind, we simply set the lowest bit of G to 1.
Doing this ensures that LEFT cannot be a factor of G. Then, so long as
G is wider than RIGHT, the error will be detected. See Tanenbaum for a
clearer explanation of this; I'm a little fuzzy on this one. Note:
Tanenbaum asserts that the probability of a burst of length greater
than W getting through is (0.5)^W.

That concludes the section on the fine art of selecting polys.

Some popular polys are:
16 bits: (16,12,5,0)                                [X25 standard]
         (16,15,2,0)                                ["CRC-16"]
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0)    [Ethernet]


8. A Straightforward CRC Implementation
---------------------------------------
That's the end of the theory; now we turn to implementations. To start
with, we examine an absolutely straight-down-the-middle boring
straightforward low-speed implementation that doesn't use any speed
tricks at all. We'll then transform that program progressively until we
end up with the compact table-driven code we all know and love and
which some of us would like to understand.

To implement a CRC algorithm all we have to do is implement CRC
division. There are two reasons why we cannot simply use the divide
instruction of whatever machine we are on. The first is that we have
to do the divide in CRC arithmetic. The second is that the dividend
might be ten megabytes long, and today's processors do not have
registers that big.

So to implement CRC division, we have to feed the message through a
division register. At this point, we have to be absolutely precise
about the message data. In all the following examples the message will
be considered to be a stream of bytes (each of 8 bits) with bit 7 of
each byte being considered to be the most significant bit (MSB). The
bit stream formed from these bytes will be the bit stream with the MSB
(bit 7) of the first byte first, going down to bit 0 of the first
byte, and then the MSB of the second byte and so on.

With this in mind, we can sketch an implementation of the CRC
division. For the purposes of example, consider a poly with W=4 and
the poly=10111. Then, to perform the division, we need to use a 4-bit
register:

                  3   2   1   0   Bits
                +---+---+---+---+
       Pop! <-- |   |   |   |   | <----- Augmented message
                +---+---+---+---+

             1    0   1   1   1   = The Poly

(Reminder: The augmented message is the message followed by W zero bits.)

To perform the division perform the following:

   Load the register with zero bits.
   Augment the message by appending W zero bits to the end of it.
   While (more message bits)
      Begin
      Shift the register left by one bit, reading the next bit of the
         augmented message into register bit position 0.
      If (a 1 bit popped out of the register during step 3)
         Register = Register XOR Poly.
      End
   The register now contains the remainder.

(Note: In practice, the IF condition can be tested by testing the top
 bit of R before performing the shift.)

We will call this algorithm "SIMPLE".

This might look a bit messy, but all we are really doing is
"subtracting" various powers (i.e. shiftings) of the poly from the
message until there is nothing left but the remainder. Study the
manual examples of long division if you don't understand this.

It should be clear that the above algorithm will work for any width W.


9. A Table-Driven Implementation
--------------------------------
The SIMPLE algorithm above is a good starting point because it
corresponds directly to the theory presented so far, and because it is
so SIMPLE. However, because it operates at the bit level, it is rather
awkward to code (even in C), and inefficient to execute (it has to
loop once for each bit). To speed it up, we need to find a way to
enable the algorithm to process the message in units larger than one
bit. Candidate quantities are nibbles (4 bits), bytes (8 bits), words
(16 bits) and longwords (32 bits) and higher if we can achieve it. Of
these, 4 bits is best avoided because it does not correspond to a byte
boundary. At the very least, any speedup should allow us to operate at
byte boundaries, and in fact most of the table driven algorithms
operate a byte at a time.

For the purposes of discussion, let us switch from a 4-bit poly to a
32-bit one. Our register looks much the same, except the boxes
represent bytes instead of bits, and the Poly is 33 bits (one implicit
1 bit at the top and 32 "active" bits) (W=32).

                   3    2    1    0   Bytes
                +----+----+----+----+
       Pop! <-- |    |    |    |    | <----- Augmented message
                +----+----+----+----+

               1<------32 bits------>

The SIMPLE algorithm is still applicable. Let us examine what it does.
Imagine that the SIMPLE algorithm is in full swing and consider the
top 8 bits of the 32-bit register (byte 3) to have the values:

   t7 t6 t5 t4 t3 t2 t1 t0

In the next iteration of SIMPLE, t7 will determine whether the Poly
will be XORed into the entire register. If t7=1, this will happen,
otherwise it will not. Suppose that the top 8 bits of the poly are g7
g6.. g0, then after the next iteration, the top byte will be:

        t6 t5 t4 t3 t2 t1 t0 ??
+ t7 * (g7 g6 g5 g4 g3 g2 g1 g0)    [Reminder: + is XOR]

The NEW top bit (that will control what happens in the next iteration)
now has the value t6 + t7*g7. The important thing to notice here is
that from an informational point of view, all the information required
to calculate the NEW top bit was present in the top TWO bits of the
original top byte. Similarly, the NEXT top bit can be calculated in
advance SOLELY from the top THREE bits t7, t6, and t5. In fact, in
general, the value of the top bit in the register in k iterations can
be calculated from the top k bits of the register. Let us take this
for granted for a moment.

Consider for a moment that we use the top 8 bits of the register to
calculate the value of the top bit of the register during the next 8
iterations. Suppose that we drive the next 8 iterations using the
calculated values (which we could perhaps store in a single byte
register and shift out to pick off each bit). Then we note three
things:

   * The top byte of the register now doesn't matter. No matter how
     many times and at what offset the poly is XORed to the top 8
     bits, they will all be shifted out the right hand side during the
     next 8 iterations anyway.


   * The remaining bits will be shifted left one position and the
     rightmost byte of the register will be shifted in the next byte

   AND

   * While all this is going on, the register will be subjected to a
     series of XOR's in accordance with the bits of the pre-calculated
     control byte.

Now consider the effect of XORing in a constant value at various
offsets to a register. For example:

       0100010  Register
       ...0110  XOR this
       ..0110.  XOR this
       0110...  XOR this
       -------
       0011000
       -------

The point of this is that you can XOR constant values into a register
to your heart's delight, and in the end, there will exist a value
which when XORed in with the original register will have the same
effect as all the other XORs.

Perhaps you can see the solution now. Putting all the pieces together
we have an algorithm that goes like this:

   While (augmented message is not exhausted)
      Begin
      Examine the top byte of the register
      Calculate the control byte from the top byte of the register
      Sum all the Polys at various offsets that are to be XORed into
         the register in accordance with the control byte
      Shift the register left by one byte, reading a new message byte
         into the rightmost byte of the register
      XOR the summed polys to the register
      End

As it stands this is not much better than the SIMPLE algorithm.
However, it turns out that most of the calculation can be precomputed
and assembled into a table. As a result, the above algorithm can be
reduced to:

   While (augmented message is not exhausted)
      Begin
      Top = top_byte(Register);
      Register = (Register << 24) | next_augmessage_byte;
      Register = Register XOR precomputed_table[Top];
      End

There! If you understand this, you've grasped the main idea of
table-driven CRC algorithms. The above is a very efficient algorithm
requiring just a shift, and OR, an XOR, and a table lookup per byte.
Graphically, it looks like this:

                   3    2    1    0   Bytes
                +----+----+----+----+
         +-----<|    |    |    |    | <----- Augmented message
         |      +----+----+----+----+
         |                ^
         |                |
         |               XOR
         |                |
         |     0+----+----+----+----+       Algorithm
         v      +----+----+----+----+       ---------
         |      +----+----+----+----+       1. Shift the register left by
         |      +----+----+----+----+          one byte, reading in a new
         |      +----+----+----+----+          message byte.
         |      +----+----+----+----+       2. Use the top byte just rotated
         |      +----+----+----+----+          out of the register to index
         +----->+----+----+----+----+          the table of 256 32-bit values.
                +----+----+----+----+       3. XOR the table value into the
                +----+----+----+----+          register.
                +----+----+----+----+       4. Goto 1 iff more augmented