Tamir Khason – Just code

How to calculate CRC in C#?

First of all, I want to beg your pardon about the frequency of posts last time. I’m completely understaffed and have a ton of things to do for my job. This why, today I’ll just write a quick post about checksum calculation in C#. It might be very useful for any of you, working with devices or external systems.

CRC – Cyclic Redundancy Check is an algorithm, which is widely used in different communication protocols, packing and packaging algorithms for assure robustness of data. The idea behind it is simple – calculate unique checksum (frame check sequence) for each data frame, based on it’s content and stick it at the end of each meaningful message. Once data received it’s possible to perform the same calculating and compare results – if results are similar, message is ok.

There are two kinds of CRC – 16 and 32 bit. There are also less used checksums for 8 and 64 bits. All this is about appending a string of zeros to the frame equal in number of frames and modulo two device by using generator polynomial containing one or more bits then checksum to be generated. This is very similar to performing a bit-wise XOR operation in the frame, while the reminder is actually our CRC.

In many industries first polynomial is in use to create CRC tables and then apply it for performance purposes. The default polynomial, defined by IEEE 802.3 which is 0xA001 for 16 bit and 0×04C11DB7 for 32 bit. We’re in C#, thus we should use it inversed version which is 0×8408 for 16 bit and 0xEDB88320 for 32 bit. Those polynomials we’re going to use also in our sample.

So let’s start. Because CRC is HashAlgorithm after all, we can derive our classes from System.Security.Cryptography.HashAlgorithm class.

public class CRC16 : HashAlgorithm {
public class CRC32 : HashAlgorithm {

Then, upon first creation we’ll generate hashtables with CRC values to enhance future performance. It’s all about values table for bytes from 0 to 255 , so we should calculate it only once and then we can use it statically.

[CLSCompliant(false)]
public CRC16(ushort polynomial) {
HashSizeValue = 16;
_crc16Table = (ushort[])_crc16TablesCache[polynomial];
if (_crc16Table == null) {
_crc16Table = CRC16._buildCRC16Table(polynomial);
_crc16TablesCache.Add(polynomial, _crc16Table);
}
Initialize();
}

[CLSCompliant(false)]
public CRC32(uint polynomial) {
HashSizeValue = 32;
_crc32Table = (uint[])_crc32TablesCache[polynomial];
if (_crc32Table == null) {
_crc32Table = CRC32._buildCRC32Table(polynomial);
_crc32TablesCache.Add(polynomial, _crc32Table);
}
Initialize();
}

Then let’s calculate it

private static ushort[] _buildCRC16Table(ushort polynomial) {
// 256 values representing ASCII character codes.
ushort[] table = new ushort[256];
for (ushort i = 0; i < table.Length; i++) {
ushort value = 0;
ushort temp = i;
for (byte j = 0; j < 8; j++) {
if (((value ^ temp) & 0×0001) != 0) {
value = (ushort)((value >> 1) ^ polynomial);
} else {
value >>= 1;
}
temp >>= 1;
}
table[i] = value;
}
return table;
}

private static uint[] _buildCRC32Table(uint polynomial) {
uint crc;
uint[] table = new uint[256];

// 256 values representing ASCII character codes.
for (int i = 0; i < 256; i++) {
crc = (uint)i;
for (int j = 8; j > 0; j–) {
if ((crc & 1) == 1)
crc = (crc >> 1) ^ polynomial;
else
crc >>= 1;
}
table[i] = crc;
}

return table;
}

The result will looks like this for 32 bits

        0x00, 0x31, 0x62, 0x53, 0xC4, 0xF5, 0xA6, 0x97,
        0xB9, 0x88, 0xDB, 0xEA, 0x7D, 0x4C, 0x1F, 0x2E,
        0x43, 0x72, 0x21, 0x10, 0x87, 0xB6, 0xE5, 0xD4,
        0xFA, 0xCB, 0x98, 0xA9, 0x3E, 0x0F, 0x5C, 0x6D,
        0x86, 0xB7, 0xE4, 0xD5, 0x42, 0x73, 0x20, 0x11,
        0x3F, 0x0E, 0x5D, 0x6C, 0xFB, 0xCA, 0x99, 0xA8,
        0xC5, 0xF4, 0xA7, 0x96, 0x01, 0x30, 0x63, 0x52,
        0x7C, 0x4D, 0x1E, 0x2F, 0xB8, 0x89, 0xDA, 0xEB,
        0x3D, 0x0C, 0x5F, 0x6E, 0xF9, 0xC8, 0x9B, 0xAA,
        0x84, 0xB5, 0xE6, 0xD7, 0x40, 0x71, 0x22, 0x13,
        0x7E, 0x4F, 0x1C, 0x2D, 0xBA, 0x8B, 0xD8, 0xE9,
        0xC7, 0xF6, 0xA5, 0x94, 0x03, 0x32, 0x61, 0x50,
        0xBB, 0x8A, 0xD9, 0xE8, 0x7F, 0x4E, 0x1D, 0x2C,
        0x02, 0x33, 0x60, 0x51, 0xC6, 0xF7, 0xA4, 0x95,
        0xF8, 0xC9, 0x9A, 0xAB, 0x3C, 0x0D, 0x5E, 0x6F,
        0x41, 0x70, 0x23, 0x12, 0x85, 0xB4, 0xE7, 0xD6,
        0x7A, 0x4B, 0x18, 0x29, 0xBE, 0x8F, 0xDC, 0xED,
        0xC3, 0xF2, 0xA1, 0x90, 0x07, 0x36, 0x65, 0x54,
        0x39, 0x08, 0x5B, 0x6A, 0xFD, 0xCC, 0x9F, 0xAE,
        0x80, 0xB1, 0xE2, 0xD3, 0x44, 0x75, 0x26, 0x17,
        0xFC, 0xCD, 0x9E, 0xAF, 0x38, 0x09, 0x5A, 0x6B,
        0x45, 0x74, 0x27, 0x16, 0x81, 0xB0, 0xE3, 0xD2,
        0xBF, 0x8E, 0xDD, 0xEC, 0x7B, 0x4A, 0x19, 0x28,
        0x06, 0x37, 0x64, 0x55, 0xC2, 0xF3, 0xA0, 0x91,
        0x47, 0x76, 0x25, 0x14, 0x83, 0xB2, 0xE1, 0xD0,
        0xFE, 0xCF, 0x9C, 0xAD, 0x3A, 0x0B, 0x58, 0x69,
        0x04, 0x35, 0x66, 0x57, 0xC0, 0xF1, 0xA2, 0x93,
        0xBD, 0x8C, 0xDF, 0xEE, 0x79, 0x48, 0x1B, 0x2A,
        0xC1, 0xF0, 0xA3, 0x92, 0x05, 0x34, 0x67, 0x56,
        0x78, 0x49, 0x1A, 0x2B, 0xBC, 0x8D, 0xDE, 0xEF,
        0x82, 0xB3, 0xE0, 0xD1, 0x46, 0x77, 0x24, 0x15,
        0x3B, 0x0A, 0x59, 0x68, 0xFF, 0xCE, 0x9D, 0xAC

Now, all we have to do is to upon request to lookup into this hash table for related value and XOR it

protected override void HashCore(byte[] buffer, int offset, int count) {

for (int i = offset; i < count; i++) {

ulong ptr = (_crc & 0xFF) ^ buffer[i];

_crc >>= 8;

_crc ^= _crc32Table[ptr];

}

}

new public byte[] ComputeHash(Stream inputStream) {

byte[] buffer = new byte[4096];

int bytesRead;

while ((bytesRead = inputStream.Read(buffer, 0, 4096)) > 0) {

HashCore(buffer, 0, bytesRead);

}

return HashFinal();

}

protected override byte[] HashFinal() {

byte[] finalHash = new byte[4];

ulong finalCRC = _crc ^ _allOnes;

finalHash[0] = (byte)((finalCRC >> 0) & 0xFF);

finalHash[1] = (byte)((finalCRC >> & 0xFF);

finalHash[2] = (byte)((finalCRC >> 16) & 0xFF);

finalHash[3] = (byte)((finalCRC >> 24) & 0xFF);

return finalHash;

}

We done. Have a good time and be good people. Also, I want to thank Boris for helping me with this article. He promised to write here some day…

Source code for this article

You may also be interested with:

1. Quick how to: Reduce number of colors programmatically
2. Real singleton approach in WPF application

April 6th, 2009 · Comments (1)