http://www.relisoft.com/science/CrcOptim.html
#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;
};
////////////////////////////////////////////////////////////////////////////////////
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;
}
}
////////////////////////////////////////////////////////////////////////////////////
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;
}
}
////////////////////////////////////////////////////////////////////////////////////
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;
}
//////////////////////////////////////////////////////////////////////////////////////
