Reliable Software Logo
Home  > Science  >Cyclic Redundancy Check  >  Implementation

Naive CRC Calculation

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 x5 + x2 + x and x2 + 1. Since the degree of the key is 2, we start by appending two zeros to our message.

10011000 / 101
101
underline
  111
  101
  underline
   100
   101
   underline
     100
     101
     underline
      01
                        

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
001
 010
  100
  101
  underline
  001
   011
    111
    101
    underline
    010
     100
     101
     underline
     001
      010
       100
       101
       underline
       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.

Implementation

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 x32. Next we calculate the CRC for such an augmented message and add it to it. That corresponds to calculating M (x) * x32 + R (x), where M (x) is the message polynomial and R (x) is the remainder from our division--in other words the CRC.

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;
}

NextNext, we'll implement the optimized version.