循环冗余码(crc)及计算方法详解(计算循环冗余码)

一、crc简介及其应用

循环冗余码(crc)是一种数据检验码，被广泛应用于数据通信领域，如网络传输、存储介质等。crc码通过特别设计的算法，将数据流映射为比特串，再生成一定长度的冗余码与原始数据一起传输。在接收端，接收方通过相同的算法计算出接收到的数据的crc码与传输的冗余码进行比较，以判断数据是否正确。

使用crc可以极大地提高数据传输的可靠性和数据完整性，对于长距离的高速数据传输尤为重要。目前，crc码已被广泛用于许多网络通信协议的数据包检验、磁盘操作系统的文件检查等。

二、crc算法原理

一般而言，crc算法的实现基于三个基本元素：生成多项式、初始值和异或输出处理。其原理与实现方式相对较为复杂，本文将分别对这三个元素进行详细解释。

1、生成多项式

crc算法通过一个特定的生成多项式来生成冗余码。生成多项式通常被表示为二进制数，如crc-32标准的生成多项式为0x04c11db7。

unsigned long crc32(unsigned char * buf, int len)
{
    unsigned long crc_table[256];
    unsigned long crc = 0xffffffff;
    int i, j;
    
    for (i = 0; i < 256; i++) {
        crc = i;
        for (j = 0; j > 1) ^ 0xedb88320 : crc >> 1;
        }
        crc_table[i] = crc;
    }
    
    crc = 0xffffffff;
    
    for (i = 0; i > 8);
    }
    
    return crc ^ 0xffffffff;
}

2、初始值

初始值是指crc码的初始值，通常为全1或全0。实现时，该值同样可以作为算法的参数进行设置。

unsigned short crc16(unsigned char * data_p, unsigned short length)
{
    unsigned char i;
    unsigned short data;
    unsigned short crc = 0xffff;
    
    if (length == 0)
        return (~crc);
    
    do {
        for (i = 0, data = (unsigned short)0xff & *data_p++; i >= 1) {
            if ((crc & 0x0001) ^ (data & 0x0001)) {
                crc = (crc >> 1) ^ C16_CCITT;
            }
            else {
                crc >>= 1;
            }
        }
    } while (--length);
    
    crc = ~crc;
    
    data = crc;
    crc = (crc <> 8 & 0xff);
    
    return crc;
}

3、异或输出处理

一般而言，crc码的输出需要进行异或处理。例如，crc-32标准的输出是通过异或处理0xffffffff得到的。

unsigned char crc8(unsigned char *pcBlock, unsigned int len)
{
    unsigned char crc = 0xFF;
    unsigned int i;
    
    while (len--) {
        crc ^= *pcBlock++;
        
        for (i = 0; i < 8; i++) {
            if (crc & 0x80) {
                crc = (crc << 1) ^ 0x31;
            }
            else {
                crc <<= 1;
            }
        }
    }
    
    return crc;
}

三、crc的应用举例

下面将以使用crc算法实现数据包校验为例进行阐述。

对于数据包，其通常包含头部信息、数据信息和校验码等。在发送端，我们可以对头部信息和数据信息进行处理，再使用crc算法生成校验码并加入数据包中。在接收端，接收方可以从接收到的数据包中提取出头部信息、数据信息和校验码等，再对头部信息和数据信息进行解析，最后使用crc算法验证校验码是否正确。

unsigned char calc_crc(unsigned char * ptr, unsigned char len)
{
    unsigned char i;
    unsigned char ret = 0;
    
    while (len--) {
        for (i = 0x80; i != 0; i /= 2) {
            if ((ret & 0x80) != 0) {
                ret *= 2;
                ret ^= CRC8_POLYNOMIAL;
            }
            else {
                ret *= 2;
            }
            
            if ((*ptr & i) != 0) {
                ret ^= CRC8_POLYNOMIAL;
            }
        }
        ptr++;
    }
    
    return ret;
}

四、crc算法的优化

在实际应用中，crc算法可以通过多种方法得到优化，如使用查表法、加速算法等。下面我们将针对这些优化进行详细阐述。

1、查表法优化

使用查表法可以极大地提高crc算法的计算速度。具体而言，可以将256个可能的字节都预先计算出其crc码值，然后直接查询计算结果即可，而不必进行每一位的计算。

unsigned short calc_crc_table(unsigned char * ptr, unsigned char len)
{
    unsigned short crc_table[256];
    unsigned char i, j;
    
    for (i = 0; i < 256; i++) {
        crc_table[i] = i;
        for (j = 0; j > 1) ^ CRC16_CCITT : crc_table[i] >> 1;
        }
    }
    
    unsigned short crc = 0xFFFF;
    while (len--) crc = crc_table[(crc ^ *ptr++) & 0xFF] ^ (crc >> 8);
    return crc;
}

2、加速算法优化

对于较短的数据计算，使用加速算法可以得到更好的效果。例如，对于16位的crc计算，可以将其拆分为两个8位的crc计算。这样可以减少crc计算的总时间，提高算法效率。

unsigned short update_crc(unsigned short crc, unsigned char * data_p, unsigned char length)
{
    unsigned char i;
    unsigned short data;
    
    do {
        for (i = 0, data = (unsigned short)0xff & *data_p++; i >= 1) {
            if ((crc & 0x0001) ^ (data & 0x0001)) {
                crc = (crc >> 1) ^ 0x8408;
            }
            else {
                crc >>= 1;
            }
        }
    } while (--length);
    
    return crc;
}

unsigned short crc16(unsigned char * data_p, unsigned char length)
{
    unsigned short crc = 0xffff;
    
    crc = update_crc(crc, data_p, length);
    crc = update_crc(crc, (unsigned char *)&crc, 2);
    
    return crc;
}

总结

本文详细介绍了循环冗余码(crc)及其计算方法，包括生成多项式、初始值和异或输出处理等三个基本元素。同时，我们也结合具体的例子，说明了crc算法在数据包校验中的应用，并介绍了crc算法的优化方法。通过本文的学习，我们能够更好地理解和应用crc算法，提高数据传输的可靠性和完整性。