最近搞一個(gè)協(xié)議，以實(shí)現(xiàn)隱蔽通道，其中需要使用CRC校驗(yàn)算法，由于數(shù)據(jù)位數(shù)比較少，最后決定使用位的CRC校驗(yàn)算法。
該算法主要就是實(shí)現(xiàn)一個(gè)模二運(yùn)算，基本原理就是異或，移位。
模二運(yùn)算的算法如下（C語言描述）：
模二運(yùn)算
// CrcMOD2函數(shù)///////////////////////////////////////////////////////
// 作用：模2運(yùn)算
// 參數(shù)說明；
// m —— 被除數(shù)
// p —— 除數(shù)
// 返回：余數(shù)
unsigned long CrcMOD2(unsigned long m, unsigned long p)
{
int m_bits = 0, p_bits = 0, a = 1, bit = 0, flag = 0;
unsigned long m_temp = m, p_temp = p;
unsigned long remainder = 0, andData = 0x00000001;
unsigned long dividend, divisor;
// 得到被除數(shù)位數(shù)
while (m_temp)
{
m_temp /= 2;
++m_bits;
}
// 得到除數(shù)位數(shù)
while (p_temp)
{
p_temp /= 2;
++p_bits;
}
// 如果被除數(shù)位數(shù)小于除數(shù)，則直接返回被除數(shù)作為余數(shù)
if (m_bits < p_bits)
return m;
// 在此開始第一次模2運(yùn)算
m_temp = m >> (m_bits - p_bits); // 被除數(shù)右移相應(yīng)的位數(shù)
dividend = m_temp; // 得到第一次進(jìn)行運(yùn)算的被除數(shù)
divisor = p; // 得到除數(shù)
remainder = dividend ^ divisor; // 得到模2運(yùn)算的結(jié)果作為余數(shù)
m_bits -= p_bits; // 第一次計(jì)算完成，減去已經(jīng)計(jì)算過的位數(shù)
while (m_bits)
{
if (!flag)
{
dividend = (remainder << 1); // 上一次得到的余數(shù)作為這次被除數(shù)的高位
m_temp = m >> (m_bits - 1);
bit = andData & m_temp;
dividend |= bit; // 原被除數(shù)的某一位作為現(xiàn)在的被除數(shù)的最低位
}
else
{
dividend <<= 1;
m_temp = m >> (m_bits - 1);
bit = andData & m_temp;
dividend |= bit;
}
// 比較除數(shù)和被除數(shù)的最高位大小
if ((dividend & (andData << (p_bits - 1))) >= (divisor & (andData << (p_bits - 1))))
{
flag = 0;
remainder = dividend ^ divisor; // 得到模2運(yùn)算的結(jié)果作為余數(shù)
}
else
{
// 需要借位
flag = 1;
}
--m_bits;
}
if (flag)
remainder = dividend;
return remainder;
} CrcGetCode函數(shù)獲原始數(shù)據(jù)和CRC生成多項(xiàng)式，利用模二運(yùn)算得到新的數(shù)據(jù)。算法如下：
給數(shù)據(jù)加上校驗(yàn)碼
// CrcGetCode函數(shù)///////////////////////////////////////////////////
// 作用：通過原始數(shù)據(jù)與CRC多項(xiàng)式，得到整個(gè)數(shù)據(jù)的編碼
// 參數(shù)說明：
// originalData —— 原始數(shù)據(jù)
// crcPolynomial —— CRC生成多項(xiàng)式
// 返回：原始數(shù)據(jù) + 校驗(yàn)碼
int CrcGetCode(unsigned long originalData, unsigned long crcPolynomial)
{
unsigned long checkBits = 0, temp = crcPolynomial, m = originalData, fcs;
while (temp)
{
temp /= 2;
++checkBits; // 校驗(yàn)位個(gè)數(shù)加一
}
-- checkBits; // 得到校驗(yàn)位個(gè)數(shù)（比生成多項(xiàng)式少1位）
m <<= checkBits; // 得到模二運(yùn)算的被除數(shù)
if (checkBits == 0)
return m;
fcs = CrcMOD2(m, crcPolynomial);
m |= fcs; // 加上FCS校驗(yàn)子
return m; // 返回整個(gè)編碼
}