 |
圖3：帶CRC外圍電路和DMA的系統(tǒng)模塊示意圖。 |
讓我們看一下如何利用傳統(tǒng)的軟件技巧來優(yōu)化CRC算法。因?yàn)镃RC操作中的一個(gè)操作數(shù)，即多項(xiàng)式(除數(shù))是常數(shù)，字節(jié)寬CRC操作的所有可能結(jié)果都可以預(yù)先計(jì)算并存儲(chǔ)在一個(gè)查找表中。這樣，通過一個(gè)讀查找表動(dòng)作就可讓操作按逐個(gè)字節(jié)執(zhí)行下去。
采用這一算法時(shí)，需要將這些預(yù)先計(jì)算好的值存儲(chǔ)在存儲(chǔ)器中。選擇ROM或RAM都可以，只要在啟動(dòng)CRC計(jì)算之前將存儲(chǔ)器初始化就行。查找表有256個(gè)字節(jié)，表中每個(gè)字節(jié)位置包含一個(gè)CRC結(jié)果，共有256種可能的8位消息(與多項(xiàng)式大小無關(guān))。
列表2示出了采用查找表方法的C代碼，包括生成查找表crcInit()中數(shù)值的代碼。
列表2：采用查找表方法的CRC算法C代碼。
crc crcTable[256];
void crcInit(void)
{
crc remainder;
/*
* Compute the remainder of each possible dividend.
*/
for (int dividend = 0; dividend < 256; ++dividend)
{
/*
* Start with the dividend followed by zeros.
*/
remainder = dividend << (WIDTH - 8);
/*
* Perform modulo-2 division, a bit at a time.
*/
for (unsigned char bit = 8; bit > 0; "bit)
{
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT)
{
remainder = (remainder << 1) ^ POLYNOMIAL;
}
else
{
remainder = (remainder << 1);
}
}
/*
* Store the result into the table.
*/
crcTable[dividend] = remainder;
}
} /* crcInit() */
crc crcFast(unsigned char const message[], int nBytes)
{
unsigned char data;
crc remainder = 0;
/*
* Divide the message by the polynomial, a byte at a time.
*/
for (int byte = 0; byte < nBytes; ++byte)
{
data = message[byte] ^ (remainder >> (WIDTH - 8));
remainder = crcTable[data] ^ (remainder << 8);
}
/*
* The final remainder is the CRC.
*/
return (remainder);
} /* crcFast() */
整個(gè)計(jì)算減少為一個(gè)循環(huán)，每字節(jié)(不是每位)有兩個(gè)異或、兩個(gè)移位操作和兩個(gè)裝載指令。基本上，這里是用查找表的存儲(chǔ)空間來換取速度。該方法比逐位計(jì)算的方法要快9.9倍，這一提高對(duì)某些應(yīng)用已經(jīng)足夠。如果需要更高的性能，可以嘗試編寫匯編代碼或增加查找表容量以擠出更多性能來。但是，如果需要20、50甚至500倍的性能提高，就要考慮采用硬件加速來實(shí)現(xiàn)該算法了。
