CRC Coding in C language

Let's start with a brief introduction

 

One 、CRC Code Introduction

CRC Our English full name is Cyclic Redundancy Check（Code）, Chinese name is Cyclic redundancy check （ code ）. It is an important class of linear block codes , The encoding and decoding methods are simple , Strong ability of error detection and correction , It is widely used in the field of communication to realize error control .

Two 、CRC Coding process

The following steps will describe 6 Byte infrared control code generation process ：

1． Extract from the QR code in sequence front 2 English letters 、 Last 2 English letters （X、x With the exception of , Take English letters ASCII The value is the original data ）, And extract polynomials g(x)（ The highest bit of the polynomial is x16, The lowest is 1）;

2． preset 1 individual 16 Bit register is hexadecimal FFFF（ It's all about 1）, Call this register CRC register ;

3． Take the first one. 8 Bit binary data （ That is, the first byte of the original data ） And 16 Bit CRC Register low 8 Different positions or , Put the results in CRC register , The upper eight bits of data remain unchanged ;

4．CRC Shift the register one bit to the right ,MSB（ highest ） Zero compensation , And move it back to the right LSB（ Its lowest ）.

5． If LSB by 0, Repeat the first 4 Step ; if LSB by 1,CRC Register and Polynomial code Different or .

6． Repeat the first 4 With the first 5 Step until 8 The first shift is complete . One at this time 8-bit Data processing finished .

7． Repeat the first 3 To 5 Step until it will be left 3 All raw data are processed .

8． Final CRC The contents of the register are CRC value .

9． take CRC As the first byte of the infrared control code , Take the raw data in sequence as the second of the infrared control code 、 3、 ... and 、 Four 、 Five bytes , take CRC The lower eight bits of the value are the sixth byte of the infrared control code .

3、 ... and 、 Algorithm example

The string data extracted from the QR code is ：<Aa12x16,Fg.5tx15/x2+\1/hgBb>, Then the extracted 4 English characters are AaBb, polynomial g(x)=x16+x15+x2+1;

Extract the original data as 0x41、 0x61、 0x42 、0x62, The polynomial code is 0xA001（ The polynomial ignores the highest order "1", The generated item is 0x8005, among 0xA001 by 0x8005 The result of bitwise inversion ）; Calculated CRC The code value is 0x8FF4; income 6 Byte infrared control code is ：0x8f 0x41 0x61 0x42 0x62 0xf4.

Write the code according to the algorithm example as ：

It needs to be explained , Polynomial extraction may be problematic , Because this document does not explain the specific process and requirements of polynomial extraction , So I wrote a polynomial extraction method according to my own understanding .

Such as ： character string ：<Aa12x16,Fg.5tx15/x2+\1/hgBb>

I would think there are many in this string x start , And there are numbers behind it , That is to say, this string may be like this ：<Ax23a12x16,Fx15g.125tx15/x2+\1/hgBb>

So my understanding is , Can be extracted as ：x23+12+x16+x15+125+x15+x2+1, After integration, it is like this ：

x16+x15+x2+1. explain ： Because no x23, So leave 23, But in the end, they were normalized , So the coefficient in front of each term is set to 1

 

The code is as follows ：

#include <stdio.h>
#include <string.h>

unsigned short CRC = 0XFFFF;				//	CRC  register   Preset to all F
unsigned short Polynomial_Code = 0X0000;	//	 Polynomial code 
unsigned short Polynomial = 0X0000;			//	 Positive sequence code before polynomial code 

unsigned char source[4] = {0x41,0x61,0x42,0x62};	//	 Raw data 
unsigned char Infrared_Control_Code[6]={0};			//	 Infrared control code 

unsigned char cnt = 0;

unsigned char str[100]= "<Aa12x16,Fg.5tx15/x2+\1/hgBbxxxxXXXXxxx>";    //Aa12x15,Fg.5tx15/x2*x1*x13/x2+\1/hgBbXxx  <Aa12x15,Fg.5tx15/x2*x1*x13/x2+\1/hgBbXx>;"<Aa12x16,Fg.5tx15/x2+\1/hgBb>";

void string_CRC(unsigned char str[]);		//	 Declaration of functions 
void main()
{	
	puts(str);
	string_CRC(str);
}

void string_CRC(unsigned char str[])
{
	int len;
	int i,n=0;
	int cnt_x=0;
	unsigned char str_temp[50];
	char str_temp2[50] = {0};
	unsigned char LSB = 0;
	len = strlen(str);
	
	for(i=0;i<len;i++)
	{
		if('x' == str[i] || 'X' == str[i])
		{
			continue;
		}
		if((str[i]<='z'&&str[i]>='a') || (str[i]<='Z'&&str[i]>='A'))
		{
			str_temp[n] = str[i];
			n++;
		}
	}
		4 Byte extraction source code     start     /
	source[0] = str_temp[0];
	source[1] = str_temp[1];
	source[2] = str_temp[n-2];
	source[3] = str_temp[n-1];
		4 Byte extraction source code     end      /
	n = 0;
	
	for(i=0;i<len;i++)
	{
		if('x' == str[i])
		{
			if(str[i+2]>='1' && str[i+2]<='6')
			{
				if('1' == str[i+1])
				{
					str_temp2[n] = (str[i+1]-'0')*10 + (str[i+2]-'0');
					i = i+2;
					n++;
				}
			}
			else
			{
				if(str[i+1]>='1' && str[i+1]<='9')
				{
					str_temp2[n] = str[i+1]-'0';
					i = i+1;
					n++;
				}
			}
			
		}
		else if((str[i] >'0' && str[i] <='9') || (str[i] >0 && str[i] <=9))		//	 here (str[i] >0 && str[i] <=9) To solve the problem C The problem of escape in language 
		{
			str_temp2[n] = -1;
			n++;
		}
	}
	
	for(i=0;i<=n-1;i++)
	{
		printf("%d ",str_temp2[i]);	
	}
	printf("\n");
	
	for(i=0;i<=n;i++)
	{
		switch(str_temp2[i])
		{
			case 16:
				break;
			case 15:
				Polynomial = Polynomial|0X8000;
				Polynomial_Code = Polynomial_Code|0X0001;
				break;
			case 14:
				Polynomial = Polynomial|0X4000;
				Polynomial_Code = Polynomial_Code|0X0002;
				break;
			case 13:
				Polynomial = Polynomial|0X2000;
				Polynomial_Code = Polynomial_Code|0X0004;
				break;
			case 12:
				Polynomial = Polynomial|0X1000;
				Polynomial_Code = Polynomial_Code|0X0008;
				break;
			case 11:
				Polynomial = Polynomial|0X0800;
				Polynomial_Code = Polynomial_Code|0X0010;
				break;
			case 10:
				Polynomial = Polynomial|0X0400;
				Polynomial_Code = Polynomial_Code|0X0020;
				break;
			case 9:
				Polynomial = Polynomial|0X0200;
				Polynomial_Code = Polynomial_Code|0X0040;
				break;
			case 8:
				Polynomial = Polynomial|0X0100;
				Polynomial_Code = Polynomial_Code|0X0080;
				break;
			case 7:
				Polynomial = Polynomial|0X0080;
				Polynomial_Code = Polynomial_Code|0X0100;
				break;
			case 6:
				Polynomial = Polynomial|0X0040;
				Polynomial_Code = Polynomial_Code|0X0200;
				break;
			case 5:
				Polynomial = Polynomial|0X0020;
				Polynomial_Code = Polynomial_Code|0X0400;
				break;
			case 4:
				Polynomial = Polynomial|0X0010;
				Polynomial_Code = Polynomial_Code|0X0800;
				break;
			case 3:
				Polynomial = Polynomial|0X0008;
				Polynomial_Code = Polynomial_Code|0X1000;
				break;
			case 2:
				Polynomial = Polynomial|0X0004;
				Polynomial_Code = Polynomial_Code|0X2000;
				break;
			case 1:
				Polynomial = Polynomial|0X0002;
				Polynomial_Code = Polynomial_Code|0X4000;
				break;
			case -1:
				Polynomial = Polynomial|0X0001;
				Polynomial_Code = Polynomial_Code|0X8000;
				break;
			default:
				break;
		}
	}
	printf("source = ");
	for(i=0;i<4;i++)
	{
		printf("%X ",source[i]);
	}
	printf("\n");
	printf("Polynomial = %X",Polynomial);
	printf("\n");
	printf("Polynomial_Code = %X",Polynomial_Code);
	printf("\n");

	///  CRC  Calculation 
	for(n=0;n<4;n++)
	{
		CRC = CRC^source[n];
		for(i=0;i<8;i++)	
		{	
			LSB = CRC&0X0001;
			CRC = CRC>>1;
			cnt++;
			if(0 == LSB)
			{
				continue;
			}
			else		//	 When LSB by 1 when 
			{
				CRC = CRC^Polynomial_Code;
			}
			if(8 == cnt )
			{
				cnt=0;
				break;
			}
			
		}
	}
	printf("CRC = %X \n",CRC);
	/// Infrared control code calculation 
	Infrared_Control_Code[0] =  (unsigned char)(CRC>>8) ;
	Infrared_Control_Code[1] = source[0]; 
	Infrared_Control_Code[2] = source[1];
	Infrared_Control_Code[3] = source[2];
	Infrared_Control_Code[4] = source[3];
	Infrared_Control_Code[5] = (unsigned char)CRC;
	printf("Infrared_Control_Code = ");
	for(i=0;i<6;i++)
	{
		printf("%X ",Infrared_Control_Code[i]);
	}
	printf("\n");
}

 

The effect is ：