The CRC algorithm requires the division of the message polynomial by the key polynomial. The straightforward implementation follows the idea of long division, except that it's much simpler. The coefficients of our polynomials are ones and zeros. We start with the leftmost coefficient (leftmost bit of the message). If it's zero, we move to the next coefficient. If it's one, we subtract the divisor. Except that subtraction modulo 2 is equivalent to exclusive or, so it's very simple.

Let's do a simple example, dividing a message 100110 by the key 101. Remember that the corresponding polynomials are `x ^{5} + x^{2} + x` and

10011000/ 101 101 111 101 100 101 100 10101

We don't even bother calculating the quotient, all we need is the remainder (the CRC), which is 01 in this case. The original message with the CRC attached reads 10011001. You can easily convince itself that it is divisible by the key, 101, with no remainder.

In practice we don't write the top bit of the key--it is implicit. In this particular example, we would only store bits 01 as our key.

The calculation above could be implemented using a 2-bit register for storing intermediate results (again, the top bit is always one, so we don't store it). Let's rewrite the above example and highlight the bits that are stored in the register at each step. The significant bits of the key are marked in red.

0010011000 / 101 001010100101 001011111101 010100101 001010100101 001

Notice that we subtract (or XOR, since this is arithmetic modulo 2) the key from the register every time a 1 is shifted out of it.

Let's start with the basic class, `Crc`. It defines the type `Crc::Type` as a 32-bit `unsigned long` (corresponding to a 33-bit key). The constructor takes the key and stores it, and it zeroes the register. The method `Done` returns the result of the CRC calculation. It also zeroes the register, so that it can be used to calculate another CRC.

#include <cassert> #include <iostream> #include <string> class Crc { public: typedef unsigned long Type; Crc (Type key) : _key (key), _register (0) {} Type Done () { Type tmp = _register; _register = 0; return tmp; } protected: Type _key; // really 33-bit key, counting implicit 1 top-bit Type _register; };

The straightforward implementation of the CRC algorithm is not very efficient, but it will serve as our starting point. The class `SlowCrc` implements a public method `PutByte` as well as a private helper, `PutBit`. `PutByte` simply splits the byte into bits and sends them one-by-one to `PutBit`. The value of the bit is encoded as a `bool` (`true` or `false`).

class SlowCrc: public Crc { public: SlowCrc (Crc::Type key) : Crc (key) {} void PutByte (unsigned char byte); private: void PutBit (bool bit); }; void SlowCrc::PutByte (unsigned char byte) { unsigned char mask = 0x80; // leftmost bit for (int j = 0; j < 8; ++j) { PutBit ((byte & mask) != 0); mask >>= 1; } }

Here is the heart of the algorithm, `PutBit`. We pick the top bit from the register, shift the register left by one, inserting a new message bit from the right. If the top bit was one, we XOR the key into the register.

void SlowCrc::PutBit (bool bit) { std::cout << bit? "1": "0"; bool topBit = (_register & 0x80000000) != 0; // shift bit into register from the right _register <<= 1; _register ^= (bit? 0x1: 0x0); // OR or XOR, same result if (topBit) { // XOR the 32-bits of the key. // The implicit high bit of the 33-bit key conceptually // clears the topBit shifted out of the register _register ^= _key; } }

Here is the `main` routine for testing the algorithm. First we extend the original message by 32 bits. This corresponds to multiplying the original polynomial by `x ^{32}`. Next we calculate the CRC for such an augmented message and add it to it. That corresponds to calculating

As a consistency test, we divide this new polynomial (the message with the CRC appended to it) by the key polynomial and make sure we get zero.

int main () { Crc::Type const ethernetKey = 0x04c11db7; SlowCrc slowCrc (ethernetKey); // calculate R in: M (x) * x^32 = Q (x) * K (x) + R (x) std::string msg ("Harry had a little lamp"); size_t origLen = msg.length (); // "Multiply" message by x^32 msg.resize (origLen + sizeof (Crc::Type)); for (size_t i = 0; i < msg.length (); ++i) { std::cout << " "; slowCrc.PutByte (msg [i]); } std::cout << "\n<- "; Crc::Type crc = slowCrc.Done (); std::cout << "\n0x" << std::hex << crc << std::endl; // Now test consistency // M (x) * x^32 + R (x) int shift = 32; for (int j = 0; j < sizeof (SlowCrc::Type); ++j) { shift -= 8; msg [origLen + j] = static_cast<unsigned char> (crc >> shift); } // Divide it by K (x) --> should be divisible for (i = 0; i < msg.length (); ++i) { std::cout << " "; slowCrc.PutByte (msg [i]); } std::cout << "\n<- "; crc = slowCrc.Done (); std::cout << "\n0x" << std::hex << crc << std::endl; assert (crc == 0); return 0; }

Next, we'll implement the optimized version.