CRC校验的C语言实现

CRC校验

• 循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。此方法是由W. Wesley Peterson于1961年发表。

多项式G(x)

• 多项式为双方共同约定使用，常见的多项式有：

  • CRC-4 => x⁴+x¹+x⁰ => 10011
  • CRC-8 => x⁸+x⁵+x⁴+x⁰ => 100110001 等。

• 因为多项式第一项必为 1，因此简记一般除去第一位后进行 16 进制计算。以上两种多项式的简记分别为0x03和0x31。

计算步骤

• 首先是接收数据和多项式。

• 然后对数据进行处理，假定计算后的 Remainder 为0，对数据补 0。

• 使用模 2 除法计算 Remainder。模 2 除法例子如下。
  

• 将计算好的 Remainder 与原 data 结合后再进行模 2 除法计算。

• 如果得出为 0，则数据无误，否则有错误。

C语言实现

// CRC算法的C语言实现
#include<stdio.h>

// 获取字符数组长度
int len(char x[]){
    int i=0;
    while(x[i]!='\0'){
        i++;
    }
    return i;
}

// 补全data
void dataSet(char data[], int len_poly, char remainder[]){
    int i, len_data;
    len_data=len(data);
    if(remainder[0]=='\0'){
        for(i=len_data; i<len_data+len_poly-1; i++){
            data[i]='0';
        }
    }else{
        for(i=len_data-len_poly+1; i<len_data+1; i++){
            data[i]=remainder[i-len_data+len_poly-1];
        }
    }
}

// remainder计算
void crc(char data[], char poly[], char remainder[], int len_data, int len_poly){
    char tmp[100]={'\0'};
    int i,j;
    // 因为传参数组会对原数据进行修改（相当于传址）
    for(i=0;i<len_data;i++){
        tmp[i]=data[i];
    }
    for(i=0;i<len_data-len_poly;i++){
        if(tmp[i]!='0'){
            for(j=i;j<i+len_poly;j++){
                tmp[j]=(tmp[j]-48) ^ (poly[j-i]-48)+48;
            }
        }
        else if(tmp[i+1]!='0'){
           for(j=i+1;j<i+1+len_poly;j++) {
                tmp[j]=(tmp[j]-48) ^ (poly[j-1-i]-48)+48;
           }
        }
    }
    for(i=0;i<len_poly;i++){
        remainder[i]=tmp[len_data-len_poly+1+i];
    }
}

// 测试CRC
void crcTest(char remainder[]){
    int i;
    for(i=0;i<len(remainder);i++){
        if(remainder[i]!='0'){
            printf("False\n");
            return;
        }
    }
    printf("True\n");
}



int main(){
    char data[100]={'0'};
    char polynomial[10]={'\0'};
    char remainder[10]={'\0'};
    scanf("%s",data);   //11010011101100
    scanf("%s",polynomial); // 10011
    printf("%d %d\n",len(data),len(polynomial));
    printf("Data is %s\n",data);

    dataSet(data,len(polynomial),remainder);
    crc(data, polynomial, remainder, len(data),len(polynomial));
    printf("Remainder is %s\n",remainder);  //1011

    dataSet(data,len(polynomial),remainder);
    printf("CRC is %s\n",data); //110100111011001011
    crc(data, polynomial, remainder, len(data),len(polynomial));
    crcTest(remainder); //True
    return 0;
}

参考文章

• 循环冗余校验 wiki