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

Optimized CRC Calculation

The main trick in optimizing the CRC calculation is to operate on bytes rather than bits. Look at the top 8 bits of the CRC register. Scan this byte from left to right. Every time you find a non-zero bit, you XOR the key into the register at a bit offset such that this bit is turned off by the top invisible bit of the key. (Notice that this operation can modify the remaining bits in the byte you are scanning.) XORing is like addition, it is associative and you can do it in any order. So you can XOR together a bunch of shifted keys corresponding to a given byte and store it for later. This is simply a section of the slow CRC algorithm applied to our pre-calculation:

// for all possible byte values
for (unsigned i = 0; i < 256; ++i)
{
    // put this byte at the top of the register
    Crc::Type reg = i << 24;
    // for all bits in a byte
    for (int j = 0; j < 8; ++j)
    {
        bool topBit = (reg & 0x80000000) != 0;
        reg <<= 1;
        if (topBit)
            reg ^= _key;
    }
    _table [i] = reg;
}
                        

Once the table is pre-calculated, we can use it to evaluate the CRC of any message byte-by-byte. At each step, we shift one byte out of the register and shift in the next message byte. We use the shifted byte as an index to our pre-computed table. The value from the table contains the accumulated XOR of appropriately shifted keys. We XOR this value into the register and continue the process until the whole message is consumed.

In fact we can do even better. We can keep XORing the accumulated keys into the register, but postpone the XORing of the message byte until its time comes to be shifted out of the register. Imagine data flowing into the register and out of it.

Optimized CRC

As a bonus, we won't be wasting the first four cycles on pushing the null bytes through the register and we won't need to append four null bytes to the end of the message.

Optimized Implementation

The class FastCrc contains a static table with pre-computed values. This table is actually stored inside a class Table that is private to the class FastCrc. Notice the overloaded operator [] which makes Table behave like an array.
class FastCrc: public Crc
{
public:
    FastCrc (Crc::Type key) 
        : Crc (key) 
    {
        _table.Init (key);
    }
    void PutByte (unsigned byte);
private:
    class Table
    {
    public:
        Table () : _key (0) {}
        void Init (Crc::Type key);
        Crc::Type operator [] (unsigned i)
        {
            return _table [i];
        }
    private:
        Crc::Type _table [256];
        Crc::Type _key;
    };
private:
    static Table _table;
};
                        

The implementation file must contain the definition of the static member _table

FastCrc::Table FastCrc::_table;

The table is initialized when the first FastCrc object is created and then reinitialized only if the key changes.

void FastCrc::Table::Init (Crc::Type key)
{
    assert (key != 0);
    if (key == _key)
        return;
    _key = key;

    // for all possible byte values
    for (unsigned i = 0; i < 256; ++i)
    {
        Crc::Type reg = i << 24;
        // for all bits in a byte
        for (int j = 0; j < 8; ++j)
        {
            bool topBit = (reg & 0x80000000) != 0;
            reg <<= 1;
            if (topBit)
                reg ^= _key;
        }
        _table [i] = reg;
    }
}

Look at the simplicity of the PutByte method:

void FastCrc::PutByte (unsigned byte)
{
    unsigned top = _register >> 24;
    top ^= byte;
    _register = (_register << 8) ^ _table [top];
}
                        

The message byte is XORed only after the top byte is shifted out of the register. A new stack of keys obtained from the table is then XORed into the register.

To test our implementation, we will calculate the CRC using both the slow and the fast algorithms.

int main ()
{
    std::string msg ("Harry had a little lamp");
    std::string exMsg (msg);
    exMsg.resize (msg.length () + 4);
    
    Crc::Type const ethernetKey = 0x04c11db7;
    SlowCrc slowCrc (ethernetKey);

    for (size_t i = 0; i < exMsg.length (); ++i)
    {
        slowCrc.PutByte (exMsg [i]);
    }
    Crc::Type crc = slowCrc.Done ();
    std::cout << "\n0x" << std::hex << crc << std::endl;

    FastCrc fastCrc (ethernetKey);

    for (size_t j = 0; j < msg.length (); ++j)
    {
        fastCrc.PutByte (msg [j]);
    }
    Crc::Type newCrc = fastCrc.Done ();
    std::cout << "\n0x" << std::hex << newCrc << std::endl;

    return 0;
}
                        

Download Source CodeDownload the source code for this example.