Coding a CRC-Generating Algorithm in C - Wait, we have memory!
(Page 3 of 4 )
Instead of this slow operation we will use to our advantage the fact that computers have memory, and we can store the result of multiple operations done beforehand, prior to our program. This approach is the table drive solution, and tries to speed up shift operations by performing multiple operations at once.
During our previous approach, a one-bit-at-a-time shift was required. What if we could shift a byte at a time? Happily for us, modulo two arithmetic operations will help us again. Most of the time we use CRCs for 8, 16 and 32 bit registers. Also, if we XOR a piece of data with another one, shift it, and do this multiple times, it is the same as if we shifted at once with the same length and just XOR it with custom data. For example:
Shift( Shift( (Shift Data XOR alfa) ) )+XOR alfa = Shift by three and XOR beta
Of course, this beta is different for each input data, given a custom "alfa" value. In our case the "alfa" is the generator polynomial and the data is the content of our registry. If we make our registry a byte long, that will mean that we can put 256 different values into it. Now we only need to generate a table that contains that for the register with content x (a number from 0 t0 255); the old school method will generate that.
Afterward we can shift our data by a byte, and then XOR it with this custom value. You could say that this way we will discard the bits that we will shift in from our input data, because while we generate our table, we only shift in zeros. Nevertheless, this is not an issue, because if we subtract too little with the XOR of the new value, this will come back at the next XOR, and if we subtract too many that will also come back, because in the modulo two world there is no such thing as negative numbers.
While the content of the registry will be different from the basic approach during the run time of the algorithm, in the end it will generate the same result. The code snippet generating the table is:
void crcGenerateTable(void)
{
crc remainder;
int dividend;
unsigned char curBitPos;
#ifdef WRITE_TO
char filePosPlace[256];
FILE* write_to;
sprintf_s(filePosPlace,
((dividend =strlen(WRITE_TO)+strlen(CRC_NAME) + 12) > 220) ? 232 : dividend,
"%s\%s_table.txt", WRITE_TO, CRC_NAME);
if(fopen_s(&write_to, filePosPlace,"w"))
printf("Cannot open the file in what to writen");
else
printf("Success to open and start write to: %sn", filePosPlace);
#endif
/*
* Compute the remainder of each possible dividend. Therefore first generate all the possible curBitPos combinations.*/
for (dividend = 0; dividend < 256; ++dividend)
{
/* Start with the dividend followed by zeros. Push the dividend to the start of the crc byte.*/
remainder =(crc) dividend << (WIDTH - 8);
/*Perform modulo-2 division, a curBitPos at a time.*/
for (curBitPos = 8; curBitPos > 0; --curBitPos)
{
/* Try to divide the current byte (check if at the correct position there is a 1 bit). If so discard first bit and subtract, otherwise shift and try again.*/
if (remainder & TOPBIT)
{remainder = (remainder << 1) ^ POLYNOMIAL;}
else
{remainder = (remainder << 1);}
}
/* Store the result into the table.*/
#ifdef WRITE_TO
if(write_to)
fprintf(write_to, "%s%X%s", SEPARATE_START, remainder, SEPARATE_END);
#endif
crcTable[dividend] = remainder;
}
}
I have also implemented a printing mechanism to a custom file of the table. This is useful because there is a different table for each type of generator polynomial. Due to this, you need to rerun this function whenever you change the generator polynomial. If you are implementing this in a microprocessor to speed up your device, you would want to save this into ROM. Using this, you can copy the binary table from the file and compile it as a constant.
Next: The table-Drive implementation >>
More C# Articles
More By Gabor Bernat
