精华内容
下载资源
问答
  • 基于crc32实现的内存的代码校验
  • 基于crc32实现的内存的代码校验

    千次阅读 2013-07-10 13:29:05
    b,内存校验:顾名思义,运行在内存代码通过crc32得到一个值,当第二次运行可执行文件的时候,可以把第一次保存下来的值和第二次运行的结果相比较,从而根据比较结果判断时候内存数据吧被修改。   1,crc32算法的...



    原理:

    a,crc32函数的实现

    b,内存校验:顾名思义,运行在内存代码通过crc32得到一个值,当第二次运行可执行文件的时候,可以把第一次保存下来的值和第二次运行的结果相比较,从而根据比较结果判断时候内存数据吧被修改。

     

    1,crc32算法的实现部分:

    DWORD CRC32(BYTE* ptr,DWORD Size)
    {
      
           DWORDcrcTable[256],crcTmp1;
          
           //动态生成CRC-32表
           for(int i=0; i<256; i++)
            {
                  crcTmp1 = i;
                  for (int j=8; j>0; j--)
                   {
                         if(crcTmp1&1) crcTmp1 = (crcTmp1 >> 1) ^ 0xEDB88320L;
                          else crcTmp1 >>= 1;
                  }
     
                   crcTable[i] = crcTmp1;
            }
           //计算CRC32值
           DWORDcrcTmp2= 0xFFFFFFFF;
           while(Size--)
           {
                  crcTmp2 = ((crcTmp2>>8) &0x00FFFFFF) ^ crcTable[ (crcTmp2^(*ptr)) & 0xFF ];
                  ptr++;
           }
          
           return(crcTmp2^0xFFFFFFFF);
    }


    2,代码实现:

    A,要保护的代码:

    ProtectStart:   //要保护的代码的起始地址
           __asm
           {
                  inc eax  //花指令
                    dec eax
                    push eax
                    pop eax
           }
    start:
              HMODULE hMod = GetModuleHandle(NULL);//同样是花指令
              HMODULE hUser32 =LoadLibrary("user32.dll");
    ProtectEnd:               //要保护代码的终结地址
              DWORD dwThreadId = 0;
     
              STBINGLEPARAM stParam = {0};
          stParam.hEvent = CreateEvent(NULL,FALSE,FALSE,"bingle");
             
              DWORD dwAddr = 0;  //一个缓存空间
              __asm mov eax,offset ProtectStart  //计算代码的起始地址
              __asm mov dwAddr,eax
              stParam.dwStart = dwAddr; //保存在我们自己定义的结构体里
     
          __asm mov eax,offset ProtectEnd //计算保护代码的结束地址,同样保存在自己定义的                   结构体里。
              __asm mov dwAddr,eax
              stParam.dwEnd = dwAddr;
             
              printf("开始了\n");
               CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)bingleProc,(LPVOID)&stParam,0,&dwThreadId);


    B,创建了一个线程,用来计算校验值。并且将线程的创建放在循环中,这样保证在程序运行的过程中,会不断的监视内存的数据是否改变。

    CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)bingleProc,(LPVOID)&stParam,0,&dwThreadId);
     
              DWORD dwRet = 0;
              dwRet =WaitForSingleObject(stParam.hEvent,INFINITE);
              while(dwRet == WAIT_OBJECT_0)
              {
                  Sleep(5000);
              CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)bingleProc,(LPVOID)&stParam,0,&dwThreadId);
                    dwRet = WaitForSingleObject(stParam.hEvent,INFINITE);
              }


    上边的代码是创建线程的,根据创建线程的返回值来作为循环条件。其中stParam是我自定义结构体生成的一个对象。这个对象保存在堆栈中。该结构体的定义如下:

    #pragma pack(1)
    typedef struct __STBINGLEPARAM
    {
     HANDLE hEvent;  //用于同步的一个信号量
     DWORD dwStart;  //要校验的代码的起始地址
     DWORD dwEnd;   //要校验的代码的终结地址
    }STBINGLEPARAM,*PBINGLEPARAM;
    #pragma pack()


     

    接下来是是线程函数了。

    STBINGLEPARAM *stParam = (STBINGLEPARAM*)lpParameter;
      
           DWORDdwCodeSize = stParam->dwEnd - stParam->dwStart;
           BYTE*pbyteBuf = NULL;
           pbyteBuf= (BYTE *)stParam->dwStart;
          
           DWORDdwOldProtect = 0;
           VirtualProtect((LPVOID)stParam->dwStart,4*1024,PAGE_EXECUTE_READWRITE,&dwOldProtect);
           if(CRC32(pbyteBuf,dwCodeSize)!= 0xa0eb5866)
           {
              MessageBox(NULL,"bingle","代码被修改了",NULL);
              printf("代码被修改了\n");
     
              SetEvent(stParam->hEvent);
              ExitProcess(0);
           }
     
     
           SetEvent(stParam->hEvent);//执行完上边的代码开始传信,让主线程继续运行



    在这里要说的是中的0xa0eb5866,这个是我在od中让代码运行起来找到的。

    在创建的线程函数体中找到0x40100a,ctrl+g来到这个地址,F2下断点,然后就来到线程函数了。

    一直往下找,找到比较代码cmpeax,0xa0eb5866这一句,把这个地址保存下来,就是我们要校验的地址。可以直接用在代码中。。

     

    3,测试:

    让debug版本的程序运行起来,ce附加进程。

    点击Memory View,定位到我们要保护的代码段。



    找到我们要保护的代码,然后用ce修改一下内存的数值试试,我想修改0x40127a。只要这个内存地址在我们要保护的代码中就可以。

    哈哈哈,还不错吧。内存校验不难吧。

    转自:http://bbs.pediy.com/showthread.php?t=140471

    展开全文
  • 通常程序中至少包括了代码段,数据段,而数据段中所存储的数据是经常会发生变动的,例如我们的全局变量,静态变量等都会默认存储在数据段,而代码段则不会发生变化,我们在检验时只需要注重.text内存段中的数据完整...

    背景

    通常程序中至少包括了代码段,数据段,而数据段中所存储的数据是经常会发生变动的,例如我们的全局变量,静态变量等都会默认存储在数据段,而代码段则不会发生变化,我们在检验时只需要注重.text内存段中的数据完整性即可,针对内存的校验同样可以抵御调试器的CC断点,该断点原理就是在下端处写入int3指令,同样可以检测得到。
    在这里插入图片描述

    校验思路如下
    1.首先从内存得到PE的代码节的RVA和节大小
    2.根据得到的RVA和节大小计算出crc32或是RC4值
    3.读取自身保存的原始CRC32值,与校验结果进行比较

    代码:

    #include <stdio.h>
    #include <windows.h>
    
    DWORD CRC32(BYTE* ptr, DWORD Size)
    {
    	DWORD crcTable[256], crcTmp1;
    
    	// 动态生成CRC-32表
    	for (int i = 0; i<256; i++)
    	{
    		crcTmp1 = i;
    		for (int j = 8; j>0; j--)
    		{
    			if (crcTmp1 & 1) crcTmp1 = (crcTmp1 >> 1) ^ 0xEDB88320L;
    			else crcTmp1 >>= 1;
    		}
    		crcTable[i] = crcTmp1;
    	}
    	// 计算CRC32值
    	DWORD crcTmp2 = 0xFFFFFFFF;
    	while (Size--)
    	{
    		crcTmp2 = ((crcTmp2 >> 8) & 0x00FFFFFF) ^ crcTable[(crcTmp2 ^ (*ptr)) & 0xFF];
    		ptr++;
    	}
    	return (crcTmp2 ^ 0xFFFFFFFF);
    }
    
    // 检查内存中CRC32特征值
    DWORD CheckMemory()
    {
    	PIMAGE_DOS_HEADER pDosHeader = NULL;
    	PIMAGE_NT_HEADERS pNtHeader = NULL;
    	PIMAGE_SECTION_HEADER pSecHeader = NULL;
    	DWORD ImageBase;
    
    	// 获取基地址
    	ImageBase = (DWORD)GetModuleHandle(NULL);
    
    	// 定位到PE头结构
    	pDosHeader = (PIMAGE_DOS_HEADER)ImageBase;
    	pNtHeader = (PIMAGE_NT_HEADERS32)((DWORD)pDosHeader + pDosHeader->e_lfanew);
    
    	// 定位第一个区块地址,因为默认的话第一个就是.text节
    	pSecHeader = IMAGE_FIRST_SECTION(pNtHeader);
    	DWORD va_base = ImageBase + pSecHeader->VirtualAddress;   // 定位代码节va基地址
    	DWORD sec_len = pSecHeader->Misc.VirtualSize;             // 获取代码节长度
    	//printf("镜像基址(.text): %x --> 镜像大小: %x \n", va_base, sec_len);
    
    	DWORD CheckCRC32 = CRC32((BYTE*)(va_base), sec_len);
    	// printf(".text节CRC32 = %x \n", CheckCRC32);
    	return CheckCRC32;
    }
    
    int main(int argc,char *argv[])
    {
    	// 用于保存初始化时 .text 节中的CRC32值
    	DWORD OriginalCRC32 = 0;
    
    	// 初始化时,给全局变量赋值,记录下初始的CRC32值
    	OriginalCRC32 = CheckMemory();
    
    	while (1)
    	{
    		Sleep(3000);
    		DWORD NewCRC32 = CheckMemory();
    		if (OriginalCRC32 == NewCRC32)
    			printf("程序没有被打补丁. \n");
    		else
    			printf("程序被打补丁 \n");
    	}
    
    	system("pause");
    	return 0;
    }
    

    在这里插入图片描述

    上方代码是保护了整个程序,在实际应用中,为了提高效率,有时我们只需要保护其中一个片段代码就好,这样可以提高效率,所有我们对上面代码稍作修改即可实现针对特定片段的内存校验。

    #include <stdio.h>
    #include <windows.h>
    
    DWORD CRC32(BYTE* ptr, DWORD Size)
    {
    	DWORD crcTable[256], crcTmp1;
    
    	// 动态生成CRC-32表
    	for (int i = 0; i<256; i++)
    	{
    		crcTmp1 = i;
    		for (int j = 8; j>0; j--)
    		{
    			if (crcTmp1 & 1) crcTmp1 = (crcTmp1 >> 1) ^ 0xEDB88320L;
    			else crcTmp1 >>= 1;
    		}
    		crcTable[i] = crcTmp1;
    	}
    	// 计算CRC32值
    	DWORD crcTmp2 = 0xFFFFFFFF;
    	while (Size--)
    	{
    		crcTmp2 = ((crcTmp2 >> 8) & 0x00FFFFFF) ^ crcTable[(crcTmp2 ^ (*ptr)) & 0xFF];
    		ptr++;
    	}
    	return (crcTmp2 ^ 0xFFFFFFFF);
    }
    
    // 检查内存中CRC32特征值
    DWORD CheckMemory(DWORD va_base, DWORD sec_len)
    {
    	PIMAGE_DOS_HEADER pDosHeader = NULL;
    	PIMAGE_NT_HEADERS pNtHeader = NULL;
    	PIMAGE_SECTION_HEADER pSecHeader = NULL;
    	DWORD ImageBase;
    	ImageBase = (DWORD)GetModuleHandle(NULL);
    	pDosHeader = (PIMAGE_DOS_HEADER)ImageBase;
    	pNtHeader = (PIMAGE_NT_HEADERS32)((DWORD)pDosHeader + pDosHeader->e_lfanew);
    
    	// 以下三条语句可用于确定位置
    	// pSecHeader = IMAGE_FIRST_SECTION(pNtHeader);
    	// DWORD va_base1 = ImageBase + pSecHeader->VirtualAddress;   // 定位代码节va基地址
    	// DWORD sec_len1 = pSecHeader->Misc.VirtualSize;             // 获取代码节长度
    	// printf("镜像基址(.text): %x --> 镜像大小: %x \n", va_base1, sec_len1);
    
    	DWORD CheckCRC32 = CRC32((BYTE*)(va_base), sec_len);
    	return CheckCRC32;
    }
    
    int main(int argc, char *argv[])
    {
    	// 用于保存初始化时 .text 节中的CRC32值
    	DWORD OriginalCRC32 = 0;
    
    	DWORD begin_addr, end_addr, size;
    	// 获取到两个位置的偏移地址
    	__asm mov begin_addr, offset begin;
    	__asm mov end_addr, offset end;
    
    	// 计算出 两者内存差值
    	size = end_addr - begin_addr;
    
    	// 校验指定内存位置
    	OriginalCRC32 = CheckMemory(begin_addr, size);
    
    	while (1)
    	{
    	begin: // 标记为需要保护的区域
    		printf("hello lyshark \n");
    		printf("hello lyshark \n");
    		printf("hello lyshark \n");
    	end:   // 保护区域声明结束
    
    		if (OriginalCRC32 == CheckMemory(begin_addr, size))
    			printf("此区域没有被破解 \n");
    		else
    			printf("此区域已被修改\n");
    
    		Sleep(3000);
    	}
    	system("pause");
    	return 0;
    }
    

    在这里插入图片描述

    通过使用磁盘校验结合内存校验两种方式综合保护,可以极大的提高软件的安全性,绕过方式则是找到哪儿跟全局变量将其修正为正确的值即可,同样的也可以更暴力一些直接将判断条件改掉均可。

    展开全文
  • crc

    2015-11-30 22:30:37
    1、CRC简介 CRC检验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个检验码r位(就是CRC码),附在信息后面,构成一个新的二进制码序列数共(k+r)位,最后发送出去。接收...

    1、CRC简介

    CRC检验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个检验码r位(就是CRC码),附在信息后面,构成一个新的二进制码序列数共(k+r)位,最后发送出去。接收端根据同样的规则校验,以确定传送中是否出错。接收端有两种处理方式:1、计算k位序列的CRC码,与接收到的CRC比较,一致则接收正确。2、计算整个k+r位的CRC码,若为0,则接收正确。
    CRC码有多种检验位数,8位、16位、32位等,原理相同。16位的CRC码产生的规则是先将要发送的二进制序列数左移16位(即乘以2的16次方后),除以一个多项式,最后所得到的余数就是CRC码。
    求CRC码所采用的是模2运算法则,即多项式除法中采用不带借位的减法运算,运算等同于异或运算。这一点要仔细理解,是编程的基础。
    CRC-16: (美国二进制同步系统中采用) G(X) = X16 + X15 + X2 + 1
    CRC-CCITT: (由欧洲CCITT推荐) G(X) = X16 + X12 + X5 + 1
    CRC-32: G(X) = X32 + X26 + X23 + X22 + X16 +X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1

    2、按位计算CRC

    采用CRC-CCITT多项式,多项式为0x11021,C语言编程时,参与计算为0x1021,这个地方得深入思考才能体会其中的奥妙,分享一下我的思路:当按位计算CRC时,例如计算二进制序列为1001 1010 1010 1111时,将二进制序列数左移16位,即为1001 1010 1010 1111 (0000 0000 0000 0000),实际上该二进制序列可拆分为1000 0000 0000 0000 (0000 0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 0000 (0000 0000 0000 0000) + …… 
    现在开始分析运算:
    <1>对第一个二进制分序列求余数,竖式除法即为0x10000 ^ 0x11021运算,后面的0位保留;
    <2>接着对第二个二进制分序列求余数,将第一步运算的余数*2后再和第二个二进制分序列一起对0x11021求余,这一步理解应该没什么问题。如果该分序列为0,无需计算。
    <3>对其余的二进制序列求余与上面两步相同。
    <4>计算到最后一位时即为整个二进制序列的余数,即为CRC校验码。
    该计算方法相当于对每一位计算,运算过程很容易理解,所占内存少,缺点是一位一位计算比较耗时。
    下面给出C语言实现方法:

    复制代码代码如下:

    unsigned char test[16] = {0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
    unsigned char len = 16;
    void main( void )
    {
       unsigned long temp = 0;
       unsigned int crc;
       unsigned char i;
       unsigned char *ptr = test;

       while( len-- ) {
          for(i = 0x80; i != 0; i = i >> 1) {
             temp = temp * 2;
             if((temp & 0x10000) != 0)
                temp = temp ^ 0x11021;

             if((*ptr & i) != 0) 
                temp = temp ^ (0x10000 ^ 0x11021);

         }
        ptr++;
       }
       crc = temp;
       printf("0x%x ",crc);
    }


    上面的程序根据运算分析而来,很容易理解。为了节约内存空间,我们对程序作进一步的简化。分析可知,当二进制序列中上一位计算的余数第15bit位为1时,即( 上一位计算的余数 & 0x8000) != 0,计算本位时,上一位余数 * 2后可对0x11021作求余运算,然后再加上本位计算所得余数。这个很好理解,也就是说,打个比方,把它看作简单的除法,计算上一位时的余数乘以2后,如果比较大可以当被除数,就再去除除数求余。有一点和普通除法不同的是,因为多项式除法中采用不带借位的减法运算,所以0x10000也可以被0x11021除,余数并非为0x10000,而是0x1021。这个自己动手算一下就知道了。余数之和也是不带进位的加法运算,即异或。最后还强调一点,因为二进制序列是左移16位后参与运算的,所以,一直算到序列的最后一位也是可以被除的,这点大家要明白。下面给出简化后的C语言实现。
    复制代码代码如下:

    unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
    unsigned char len = 16;
    void main( void )
    {
       unsigned int crc = 0;
       unsigned char i;
       unsigned char *ptr = test;

       while( len-- ) {
          for(i = 0x80; i != 0; i = i >> 1) {
            if((crc & 0x8000) != 0) {
               crc = crc << 1;
               crc = crc ^ 0x1021;
            }
            else {
               crc = crc << 1;
            }
            if((*ptr & i) != 0) {
              crc = crc ^ 0x1021; 
            }
         }
         ptr++;
       }

       printf("0x%x ",crc);
    }


    上面这段程序网上较为常见,但冇得详细的解释。通过我上面的详细分析,如果对此段程序理解还有困难,可以对比一下没简化之前的程序,细细品味一哈,还是比较容易理解的。要是还理解不了,还是从头再看下,我码这么多字容易吗。。。。。
    按位计算CRC代码比较简单,所占内存少,但要一位一位去计算,下面再介绍一种按字节查表快速计算CRC的方法。

    3、按字节计算CRC

    有了上面按位计算的知识,理解这个就是小case了。还是举前面的例子:当字节计算CRC时,例如计算二进制序列为1001 1010 1010 1111时,即0x9a9f时,将二进制序列数左移16位,即为0x9a9f(0 0 0 0),实际上该二进制序列可拆分为0x9a00(0 0 0 0) + 0x009f(0 0 0 0),分析计算时和上面的步骤一样,唯一不同的是计算中上一步的余数CRC要乘以2的八次方参与下一步的运算,这个应该好理解撒。为了简化编程,将计算中的CRC拆成高八位和低八位的形式,高八位的值直接与本位值相加求余,低八位的值乘以2的八次方后作为余数和计算得的余数相加。为了提高计算速度,我们把8位二进制序列数的CRC全部计算出来,放在一个表中,采用查表法可大大提高计算速度。
    表是怎么得到的呢?当然是计算出来的,下面的程序给出了多项式是0x11021的计算程序。

    复制代码代码如下:

    void main( void )
    {
       unsigned int crc = 0;
       unsigned char i;
       unsigned int j;

       for(j = 0; j < 256; j++) {
          crc = 0;
          for(i = 0x80; i != 0; i = i >> 1) {
             if((crc & 0x8000) != 0) {
                crc = crc << 1;
                crc = crc ^ 0x1021;
            }
            else {
                crc = crc << 1;
            }
            if((j & i) != 0) {
                crc = crc ^ 0x1021;
            }
       }
       printf("0x");
       if(crc < 0x10) {
          printf("000");
       }
       else if(crc < 0x100) {
          printf("00");
       }
       else if(crc < 0x1000) {
          printf("0");
       }

       printf("%x, ",crc);
       }
    }


    如果你不是使用的0x11021多项式,只需把程序中0x1021换成其他的就可以了。后面的几个printf语句为了控制使生成的表比较整齐,如果无所谓,可直接用printf("0x%x, ",crc);代替。生成的表如下:
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0,
    好了,我们来写按字节计算的源程序:
    复制代码代码如下:

    unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
    unsigned char len = 16;
    unsigned int crc_table[256] ={
    x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0};
    void main(void)
    {
       unsigned int crc = 0;
       unsigned char crc_H8;
       unsigned char *ptr = test;

       while( len-- ) {
          crc_H8 = (unsigned char)(crc >> 8);
          crc = crc << 8;
          crc = crc ^ crc_table[ crc_H8 ^ *ptr];
          ptr++;
       }
       printf("0x%x ",crc);
    }


    4、按半字节计算CRC

    是不是感觉上面的表太大了,不是很爽,我们再来改进一下,按半字节计算,原理我就不赘述了,程序如下:

    复制代码代码如下:

    unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
    unsigned char len = 16;
    unsigned int crc_table[16] =
    {0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef
    };
    void main(void)
    {
    unsigned int crc = 0;
    unsigned char crc_H4;
    unsigned char *ptr = test;

    while( len-- )
    {
    crc_H4 = (unsigned char)(crc >> 12);
    crc = crc << 4;
    crc = crc ^ crc_table[ crc_H4 ^ (*ptr >> 4)];
    crc_H4 = (unsigned char)(crc >> 12);
    crc = crc << 4;
    crc = crc ^ crc_table[ crc_H4 ^ (*ptr & 0x0f)];
    ptr++;
    }
    printf("0x%x ",crc);
    }

    展开全文
  • CRC

    千次阅读 2014-03-11 10:02:51
    CRC算法及原理   CRC校验码的基本思想是利用线性编码理论, 在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)...

    CRC算法及原理

     

    CRC校验码的基本思想是利用线性编码理论, 在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。
        
    在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25FCS(帧检错序列)采用的是CRC. CCITTARJLHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIFTIFF等也都用CRC作为检错手段。
        CRC
    的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32.
        
    CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位(既乘以2^16)后,再除以一个多项式,最后所得到的余数既是CRC码,如下式所示,其中K(X)表示n位的二进制序列数,G(X)为多项式,Q(X)为整数,R(X)是余数(既CRC码)。
    K(X)>>16=G(x)Q(x)+R(x)
        
    CRC码所采用模2加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算,加法和减法等价,乘法和除法运算与普通代数式的乘除法运算是一样,符合同样的规律。生成CRC码的多项式如下,其中CRC-16CRC-CCITT产生16位的CRC码,而CRC-32则产生的是32位的CRC
        
    接收方将接收到的二进制序列数(包括信息码和CRC码)除以多项式,如果余数为0,则说明传输中无错误发生,否则说明传输有误,关于其原理这里不再多述。用软件计算CRC码时,接收方可以将接收到的信息码求CRC码,比较结果和接收到的CRC码是否相同。
        
    CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16CRC16,其生成多项式为G(x)=x16+x12+x5+1, CRC-32的生成多项式为G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1
    CRC算法原理及C语言实现

    CRC原理介绍:

     CRC的英文全称为Cyclic Redundancy Check(Code),中文名称为循环冗余校验(码)。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。 


         CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的,而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数,在CRC运算中我们称之为poly,而宽度W就是poly最高位的位置。比如poly 1001的W是3,而不是4。注意最高位总是1,当你选定一个宽度,那么你只需要选择低W各位的值。假如我们想计算一个位串的CRC码,并要保证每一位都要被处理,因此我们需要在目标位串后面加上W个0。下面举例说明CRC算法的过程。

         在此例中,我们假设位串为110101101。

    Poly
                         = 10011(宽度W = 4)
    Bitstring + W zeros = 110101101 0000

    10011/1101011010000/110000101 (我们不关心此运算的商)
          10011|||||||| 
           -----||||||||
            10011|||||||
            10011|||||||
             -----|||||||
              00001||||||
              00000||||||
               -----||||||
                00010|||||
                00000|||||
                 -----|||||
                  00101||||
                  00000||||
                   -----||||
                    01010|||
                    00000||| 
                     -----|||
                      10100||
                      10011||
                       -----||
                        01110|
                        00000|
                         -----|
                         11100
                         10011
                          -----
                           1111 -> 余数 -> CRC!

    计算过程总结如下:
    1. 只有当位串的最高位为1,我们才将它与poly做XOR运算,否则我们只是将位串左移一位。
    2. 异或运算的结果实质上是被操作位串与poly的低W位进行运算的结果,因为最高位总为0。 

     


    CRC原理及其逆向破解方法:

    介绍:

     这篇短文包含CRC原理介绍和其逆向分析方法,很多程序员和破解者不是很清楚了解
    CRC
    的工作原理,而且几乎没人知道如何逆向分析它的方法,事实上它是非常有用的.
    首先,这篇教程教你一般如何计算CRC,你可以将它用在数据代码保护中.第二,主要是
    介绍如何逆向分析CRC-32,你可以以此来分析程序中的CRC保护(象反病毒编码).当然
    有很多有效的工具用来对付CRC,但我怀疑它是否会说明原理.
      
    我要告诉你,这篇短文里中应用了很多数学知识,这不会影响一些人,而且会被一般的
    程序员与逆向分析者很好理解.为什么?那么如果你不知道数学是如何被应用在CRC,
    我建议你可以停止继续学习了.所以我假定你们(读者)都是具备二进制算术知识的.

    第一部分:CRC 介绍,CRC是什么和计算CRC的方法

    循环冗余码 CRC

     我们都知道CRC.甚至你没有印象,但当你想到那些来自诸如RAR,ZIP等压缩软件发给你
    由于错误连接和其他一些意外原因导致的文件错误的恼人的消息时,你就会知道.CRC是块
    数据的计算值,比如对每一个文件进行压缩.在一个解压缩过程中,程序会从新计算解压文件
    CRC,并且将之与从文件中读取的CRC值进行比对,如果值相同,那么正确.CRC-32,
    会有1/2^32的可能性发生对确认数据更改的校验错误.    
      
    很多人认为CRC就是循环冗余校验,假如CRC真的就是循环冗余校验,那么很多人都错用了
    这个术语.你不能说"这个程序的CRC12345678".人们也常说某一个程序有CRC校验,而不
    说是 "循环冗余校验校验.结论:CRC 代表循环冗余码,而不是循环冗余校验.  
      
    计算是如何完成的呢?好,主要的想法就是将一个文件看成一个被一些数字分割的很长的
    位字串,这里会有一个余数---CRC!你总会有一个余数(可以是0),它至多比除数小一.
    (9/3=3 
    余数=0 ; (9+2)/3=3 余数=2)
    (
    或者它本身就包含一个除数在其中). 
      
    在这里CRC计算方法与除法有一点点区别,除法就是将被减数重复的减去除数X,然后留下
    余数.如果你希望得到原值,那么你就要把除数乘上X,然后加上余数.
      CRC
    计算使用特殊的减法与加法完成的.也就是一种新的"算法".计算中每一位计算的进位值
    "遗忘".  
    看如下两个例子,1是普通减法,23是特殊的.
         -+
    (1) 1101  (2) 1010  1010  (3) 0+0=0  0-0=0
        1010-     1111+ 1111-     0+1=1 *0-1=1
        ----      ----  ----      1+0=1  1-0=1
        0011      0101  0101     *1+1=0  1-1=0
      
    (1),右数第二列可以看成是0-1=-1,因此要从高位借1,就变成(10+0)-1=1.(这就象普通
    'by-paper'十进制减法).特例(2,3),1+1会有正常的结果10,'1'是计算后的进位.这个值
    被忽略了.特殊情况0-1应该有正常结果'-1'就要退到下一位.这个值也被忽略了.假如你对编程
    有一定了解,这就象,XOR 操作或者更好.
      
    现在来看一个除法的例子:

    在普通算法中:
    1001/1111000\1101 13            9/120\13
         1001    -                    09  -|
         ----                         --   |
          1100                         30  |
          1001    -                    27  -
          ----                         --
           0110                         3 -> 
    余数
           0000    -
           ----
            1100
            1001    -
            ----
             011 -> 3, 
    余数

    CRC算法中:
    1001/1111000\1110               9/120\14 
    余数为 6
         1001    -
         ----
          1100
          1001    -
          ----
           1010
           1001    -
           ----
            0110
            0000    -
            ----
             110 -> 
    余数
    (
     3)

     这个除法的商并不重要,也没必要去记住,因为他们仅仅是一组无关紧要的位串.真正
    重要的是余数!它就是这个值,可以说比原文件还重要的值,他就是基本的CRC.


    过度到真正的CRC码计算.

     进行一个CRC计算我们需要选则一个除数,从现在起我们称之为"poly".宽度W就是最高位
    的位置,所以这个poly 10013,而不是4.注意最高位总是1,当你选定一个宽度,那么你只
    需要选择低W各位的值.  
      
    假如我们想计算一个位串的CRC,我们想确定每一个位都被处理过,因此,我们要在目标
    位串后面加上W0.在此例中,我们假设位串为1111.请仔细分析下面一个例子:

    Poly                = 10011, 宽度 W=4
    位串                Bitstring 
    Bitstring + W zeros = 110101101 + 0000

    10011/1101011010000\110000101 (我们不关心此运算的商)
          10011|||||||| -
          -----||||||||
           10011|||||||
           10011|||||||  -
           -----|||||||
            00001||||||
            00000||||||   -
            -----||||||
             00010|||||
             00000|||||    -
             -----|||||
              00101||||
              00000||||     -
              -----||||
               01010|||
               00000|||      -
               -----|||
                10100||
                10011||       -
                -----||
                 01110|
                 00000|        -
                 -----|
                  11100
                  10011         -
                  -----
                   1111 -> 
    余数 -> the CRC!
    (
     4)

    重要两点声明如下:
    1.
    只有当Bitstring的最高位为1,我们才将它与polyXOR运算,否则我们只是将
      Bitstring
    左移一位.
    2.XOR
    运算的结果就是被操作位串bitstring与低W位进行XOR运算,因为最高位总为0.

    算法设计:

     你们都应知道基于位运算的算法是非常慢的而且效率低下.但如果将计算放在每一字节上
    进行,那么效率将大大提高.不过我们只能接受poly的宽度是8的倍数(一个字节;).可以形
    象的看成这样一个宽度为32poly(W=32):

              3   2   1   0    byte
            +---+---+---+---+
    Pop! <--|   |   |   |   |<-- bitstring with W zero bits added, in this case 32
            +---+---+---+---+
           1<--- 32 bits ---> this is the poly, 4*8 bits

    (figure 1)
      
    这是一个你用来存放暂时CRC结果的记存器,现在我称它为CRC记存器或者记存器.你从右
    至左移动位串,当从左边移出的位是1,则整个记存器被与poly的低W位进行XOR运算.(此例
    中为32).事实上,我们精确的完成了上面除法所做的事情.


    移动前记存器值为:10110100
    当从右边移入4位时,左边的高4位将被移出,此例中1011将被移出,1101被移入.

    情况如下:
    当前8CRC记存器      : 01001101
    刚刚被移出的高4     : 1011
    我们用此poly          : 101011100, 宽度 W=8

    现在我们用如前介绍的方法来计算记存器的新值.
    顶部 记存器
    ---- --------
    1011 01001101  
    高四位和当前记存器值
    1010 11100   + (*1) Poly 
    放在顶部最高位进行XOR运算 (因为那里是1)
    -------------
    0001 10101101 
    运算结果

    现在我们仍有一位1在高4:
    0001 10101101  
    上一步结果
       1 01011100+ (*2) Poly 
    放在顶部的最低位进行XOR运算 (因为那里是1)
    -------------
    0000 11110001 
    第二步运算结果
    ^^^^
    现在顶部所有位均为0,所以我们不需要在与poly进行XOR运算

    你可以得到相同的结果如果你先将(*1)(*2)XOR然后将结果与记存器值做XOR.
    这就是标准XOR运算的特性:
    (a XOR b) XOR c = a XOR (b XOR c)  
    由此,推出如下的运算顺序也是正确的.

    1010 11100       poly  (*1)    放在顶部最高位
       1 01011100+   polys (*2)    
    放在顶部最低位
    -------------
    1011 10111100  (*3) XOR
    运算结果

    The result (*3)   (*3)与记存器的值做XOR运算
    1011 10111100
    1011 01001101+    
    如右:
    -------------
    0000 11110001

    你看到了吗?得到一样的结果!现在(*3)变的重要了,因为顶部为1010(3)的值总是等于
    10111100(
    当然是在一定的条件之下)这意味着你可以预先计算出任意顶部位结合的XOR.
    注意,顶部结果总是0,这就是组合XOR操作导致的结果.(翻译不准确,保留原文)

     现在我们回到figure 1,对每一个顶部字节的值都做移出操作,我们可以预先计算出一个值.
    此例中,它将是一个包含256double word(32 bit)双字的表.(附录中CRC-32的表).
    (
    翻译不准确,保留原文

    用伪语言表示我们的算法如下:

    While (byte string is not exhausted)
        Begin
        Top = top_byte of register ;
        Register = Register shifted 8 bits left ORred with a new byte from string ;
        Register = Register XORred by value from precomputedTable at position Top ;
        End

    direct table算法:
      
    上面提到的算法可以被优化.字节串中的字节在被用到之前没有必要经过整个记村器.
    这个新的算法,我们可以直接用一个字节去XOR一个字节串通过将此字节移出记存器.结果
    指向预先计算的表中的一个值,这个值是用来被记存器的值做XOR运算的.  
      
    我不十分确切的知道为什么这会得到同样的结果(这需要了解XOR运算的特性),但是这又
    极为便利,因为你无须在你的字节串后填充0字节/.(如果你知道原理,请告诉我:) 
      
    让我们来实现这个算法:

      +----< byte string  (or file)  字节串,(或是文件)
      |
      v       3   2   1   0    byte  
    字节
      |     +---+---+---+---+
    XOR---<|   |   |   |   |  Register  
    记存器
      |     +---+---+---+---+
      |             |
      |            XOR
      |             ^
      v     +---+---|---+---+
      |     |   |   |   |   |  Precomputed table 
    值表(用来进行操作)
      |     +---+---+---+---+
      +--->-:   :   :   :   :
            +---+---+---+---+
            |   |   |   |   |
            +---+---+---+---+
    (figure 2)

    'reflected' direct Table 算法:

     由于这里有这样一个与之相对应的'反射'算法,事情显得复杂了.一个反射的值/记存器
    就是将它的每一位以此串的中心位为标准对调形成的.例如:0111011001就是1001101110
    的反射串.  
      
    他们提出'反射'是因为UART(一种操作IO的芯片)发送每一个字节时是先发最没用的0,
    最后再发最有意义的第七位.这与正常的位置是相逆的.  
      
    除了信息串不做反射以外,在进行下一步操作前,要将其于的数据都做反射处理.所以在
    计算值表时,位向右移,poly也是作过反射处理的.当然,在计算CRC,记存器也要向右
    ,而且值表也必须是反射过的

      byte string (or file) -->---+
                                  |    1. 
    表中每一个入口都是反射的.
        byte  3   2   1   0       V    2. 
    初始化记存器也是反射的.
            +---+---+---+---+     |    3. 
    但是byte string中的数据不是反射的,
            |   |   |   |   |>---XOR      
    因为其他的都做过反射处理了
            +---+---+---+---+     |
                    |             |
                   XOR            V
                    ^             |
            +---+---|---+---+     |
            |   |   |   |   |     |     
    值表
            +---+---+---+---+     |
            :   :   :   :   : <---+
            +---+---+---+---+
            |   |   |   |   |
            +---+---+---+---+
    (figure 3)

    我们的算法如下:
    1. 
    将记存器向右移动一个字节.
    2. 
    将刚移出的哪个字节与byte string中的新字节做XOR运算,
       
    得出一个指向值表table[0..255]的索引
    3. 
    将索引所指的表值与记存器做XOR运算.
    4. 
    如数据没有全部处理完,则跳到步骤1.


    下面是这个算法的简单的可执行汇编源码:

    完整的CRC-32标准所包含的内容:
    Name            : "CRC-32"
    Width           : 32
    Poly            : 04C11DB7
    Initial value   : FFFFFFFF
    Reflected       : True
    XOR out with    : FFFFFFFF

    作为对你好奇心的奖励这里是CRC-16标准: :)
    Name            : "CRC-16"
    Width           : 16
    Poly            : 8005
    Initial value   : 0000
    Reflected       : True
    XOR out with    : 0000

    'XOR out with' 是为了最终得到CRC而用来与记存器最后结果做XOR运算的值.
    假如你想了解一些关于'reversed'逆向CRC poly的话,请看我的参考文章.
      
      
    我是在16DOS模式下用的32位编码,因此你会在这个程序中看到很多32位与16位混合
    的编码...当然这是很容易转换成纯32位编码的.注意这个程序是经过完整测试并且能够
    正常运行的.下面的Java  C 代码都是由这个汇编代码而来的.  
    底下的这段程序就是用来计算CRC-32 table:

            xor     ebx, ebx   ;ebx=0, 将被用做一个指针.
    InitTableLoop:
            xor     eax, eax   ;eax=0 
    为计算新的entry.
            mov     al, bl     ;al<-bl

            ;生成入口.
            xor     cx, cx
    entryLoop:
            test    eax, 1
            jz     no_topbit
            shr     eax, 1
            xor     eax, poly
            jmp    entrygoon
    no_topbit:
            shr     eax, 1
    entrygoon:
            inc     cx
            test    cx, 8
            jz     entryLoop

            mov     dword ptr[ebx*4 + crctable], eax
            inc     bx
            test    bx, 256
            jz     InitTableLoop

    注释:  - crctable 是一个包含256dword的数组.
           - 
    由于使用反射算法,EAX被向右移.
           - 
    因此最低的8位被处理了.

    JavaC写的代码如下(int is 32 bit):

    for (int bx=0; bx<256; bx++){
      int eax=0;
      eax=eax&0xFFFFFF00+bx&0xFF;      // 
    就是 'mov al,bl' 指令
      for (int cx=0; cx<8; cx++){
        if (eax&&0x1) {
          eax>>=1;
          eax^=poly;
        }
        else eax>>=1;
      }
      crctable[bx]=eax;
    }

    下面的汇编代码是用来计算CRC-32:

    computeLoop:
            xor     ebx, ebx
            xor     al, [si]
            mov     bl, al
            shr     eax, 8
            xor     eax, dword ptr[4*ebx+crctable]
            inc     si
            loop   computeLoop

            xor     eax, 0FFFFFFFFh

    注释:  - ds:si 指向将要被处理的byte string信息流.
           - cx 
    信息流的长度.
           - eax 
    是当前的CRC.
           - crctable
    是用来计算CRC的值表.
           - 
    此例中记存器的初始值为: FFFFFFFF.
           - 
    要将中间值与FFFFFFFFhXOR才能得到CRC

    下面是JavaC写的代码:

    for (int cx=0; cx>=8;
       eax^=crcTable[ebx];
    }
    eax^=0xFFFFFFFF;

     现在我们已经完成了本文的第一部分:CRC原理部分,所以如果你希望能够对CRC做更深
    的研究,那么我建议你去读在本文最后给出连接上的资料,我读了.好了,终于到了本文最
    有意思的部分,CRC的逆向分析!


    ------------------------------------------------------------------------------------
    第二部分 CRC的逆向分析:

     我遇到了很多障碍,当我思考如何破解CRC.我试图使用一些特殊顺序的字节使CRC无效.
    但我没有做到...后来我意识到这种方法是行不同的,因为CRC内建了一些处理过程,无论你
    改变任何位它都不会出问题,真正的CRC就是在不断变化的,总是在变化的.找一些CRC程序,
    你可以自己尝试一下.  
      
    现在我知道我只能'纠正'CRC后面的那些我想改变的字节.所以我要构造一个字节序列,
    它可以将CRC转化成任何我想要的样子

    具体实现这个想法

    一个字节串?     01234567890123456789012345678901234567890123456789012
    You want to change from  ^  this byte to  ^  this one.

    就是位置9->26.
    同时我们需要额外的4个字节用来在最后恢复原始字节串.

     当你计算CRC-32,0-8都没有问题,直到第9,修补过的字节串会使CRC发生根本的改变.
    即使当走过了第26,以后的字节都没有改变,你也不可能在得到原始的CRC,不可能了!你读
    过后面的段落时就会明白为什么.间而言之,当你修改一个字节串时,要保证CRC不变

    1. 计算并保存从1~9位的CRC.
    2. 
    继续计算直到第27位还有额外的4字节并保存结果.
    3. 
    1的值来计算新的字节串和额外4字节的CRC(对应patch后的新的CRC),并将之保存.
    4. 
    现在我们得到了一个新的CRC,但是我们希望将它还原成原先的CRC,所以我们用逆向算法
       
    来计算那额外的4字节.

    1~3就是实际的情况,下面你将学到最关键的部分4.


    '
    反转'CRC-16

     我想,先来介绍计算逆CRC-16对于你来说会简单些.好的,我们现在处在一个恰当的位置,
    在以修改代码后面,就是你想将CRC还原的地方.我们知道原始的CRC(是在patch代码之前计
    算出来的)还有这个当前的记存器值.现在我们的目的就是计算可以改变当前记存器值到原
    始记存器值的两个字节.首先,我们用正常的方法计算这两个未知字节的CRC.我们设他们为
    X,Y.
    设记存器为a1,a0,只有0不能用来作为变量(00).:)在来看一下我们的CRC算法,figure
    3,
    更好的理解下面我要做的.

    ,我们开始:

    用这两字节串'X Y' 字节是从左边开始被处理的.
    记存器现在是a1 a0.
    '+'来表示XOR运算(和第一部分中用的一样)

    处理第一个字节, X:
    a0+X            
    这是顶部字节的计算结果 (1)
    b1 b0           
    这是(1)在表中索引对象.
    00 a1           
    向右移动记存器.
    00+b1 a1+b0     
    上面两行对应位做XOR运算.

    现在记存器为: (b1) (a1+b0)

    处理第二个字, Y:
    (a1+b0)+Y       
    此轮顶部字节的计算结果(2)
    c1 c0           
    这是(2)在表中的索引对象.
    00 b1           
    向右移动记存器.
    00+c1 b1+c0     
    上面两行对应位做XOR运算.

    最后记存器就是: (c1) (b1+c0)

    我用一点不同的方法来表示:

    a0 + X      =(1)  在表中指向b1 b0.
    a1 + b0 + Y =(2)  
    在表中指向c1 c0.
         b1 + c0=d0   
    记存器中新的低位字节.
              c1=d1   
    记存器中新的高位字节.
        (1)  (2)

    Wow! 请大家暂时记住上面的信息:)
    别着急下面给出一个有具体值的例子.
      
      
    如果你想要的记存器的值是d1 d0(是原始的CRC),而且你知道在变换之前的记存器的值
    (a1 a0)...
    那么你将要送如什么样的2个字节进记存器来做CRC计算呢?  
      
    好了,现在我们的工作应该从幕后走到台前来了.d0一定是bi+c0,并且d1一定是c1...
    但是这到底是怎么回事,我听到你这样问了,你能知道b1c0的值吗???你还记得哪个值表
    ?你只需要在表中查找c0 c1这个字的值就可以了因为你知道c1.所以你需要编写一个查
    找程序.假如你找到了这个值,一定要记住这个值的索引,因为这就是找出未知的两个顶部
    字节,举例来说:(1)(2)! 
      
    所以,现在你找到了c1 c0,那么如何来得到b1 b0?如果b1+c0=d0那么b1=d0+c0!如前所
    ,现在你用哪个查找程序在表中查b1 b0的值.现在我们得到了所有计算XY所需要的值.
    Cool huh?  
    a1+b0+Y=(2) so Y=a1+b0+(2)
    a0+X=(1)    so X=a0+(1)


    实例.

    让我们来看看这个具体值的例子:
    -register before: (a1=)DE (a0=)AD
    -wanted register: (d1=)12 (d0=)34
    在附录的CRC-16的表中查找以12开头值的入口.这里入口38h的值为12C0.试这找一找是否还
    有以12开头的值的入口.你不可能在找到的,因为我们计算每一中顶部字节组合而得的值的
    入口,一共是256个值,记住!
    现在我们知道(2)=38,c1=12,c0=C0,所以b1=C0+34=F4,现在查找以F4开头的b1的入口.这里
    入口4Fh的值是F441.
    我们还知道  (1)=4F,b1=F4,b0=41,现在所有我们需要的都已经清楚了,接下来我们计算X,Y.

    Y=a1+b0+(2)=DE+41+38=A7
    X=a0+(1)   =AD+4F   =E2

    结论:CRC 记存器的值从 DEAD 变为 1234 我们需要这两个字节 E2 A7 (以此顺序).

     你看,破解CRC校验你需要反向计算,还有要记住的就是计算过程中的值.当你在用汇编编写
    查找表程序时,要注意intel在小模式中是反向存储值的.现在你可能已经明白如何去破解这个
    CRC-16
    ...下面介绍如何在CRC-32中实现.


    破解 CRC-32

    现在我们来看CRC-32,CRC-16是一样容易的(可能一样的不容易你认为).这里你操作的对象
    4个字节的而不是2字节的.继续向下看,将它与上面CRC-16版本做对比.

    4字节串 X  Y  Z  W  , 从左边开始处理.
    设记存器为  a3 a2 a1 a0
    注意a3MSB,a0LSB

    处理第一个字节, X:
    a0+X                    
    这是顶部字节的计算结果(1).
    b3    b2    b1    b0    
    这是(1)在表中索引对象序列.
    00    a3    a2    a1    
    右移记存器.
    00+b3 a3+b2 a2+b1 a1+b0 
    上面两行对应位做XOR运算.

    现在记存器是: (b3) (a3+b2) (a2+b1) (a1+b0)

    Processing second byte, Y:
    (a1+b0)+Y                       
    这是顶部字节的计算结果(2).
    c3    c2    c1       c0         
    这是(2)在表中索引对象序列.
    00    b3    a3+b2    a2+b1      
    右移记存器.
    00+c3 b3+c2 a3+b2+c1 a2+b1+c0   
    上面两行对应位做XOR运算.

    现在记存器是: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)

    Processing third byte, Z:
    (a2+b1+c0)+Z                     
    这是顶部字节的计算结果(3).
    d3    d2    d1       d0          
    这是(3)在表中索引对象序列.
    00    c3    b3+c2    a3+b2+c1    
    右移记存器.
    00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 
    上面两行对应位做XOR运算.

    现在记存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)

    Processing fourth byte, W:
    (a3+b2+c1+d0)+W                  
    这是顶部字节的计算结果(4).
    e3    e2    e1       e0          
    这是(4)在表中索引对象序列.
    00    d3    c3+d2    b3+c2+d1    
    右移记存器.
    00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 
    上面两行对应位做XOR运算.

    最后,记存器为: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)

    我用一个不同一点的方法来表示:
    a0 + X                  =(1)  
    在表中指向 b3 b2 b1 b0  
    a1 + b0 + Y             =(2)  
    在表中指向 c3 c2 c1 c0  
    a2 + b1 + c0 + Z        =(3)  
    在表中指向 d3 d2 d1 d0  
    a3 + b2 + c1 + d0 + W   =(4)  
    在表中指向 e4 e3 e2 e1  
         b3 + c2 + d1 + e0  =f0
              c3 + d2 + e1  =f1
                   d3 + e2  =f2
                        e3  =f3
        (1)  (2)  (3)  (4)
    (figure 4)

    这里是用的与CRC-16同样的方法来实现的,我会给出一个具体值的例子.查找用附录中
    CRC-32
    的值表.

    Take for CRC register before, a3 a2 a1 a0 -> AB CD EF 66
    Take for CRC register after,  f3 f2 f1 f0 -> 56 33 14 78 (wanted value)

    我们开始:

    First byte of entries            entry   value
    e3=f3                     =56 -> 35h=(4) 56B3C423 for e3 e2 e1 e0
    d3=f2+e2      =33+B3      =E6 -> 4Fh=(3) E6635C01 for d3 d2 d1 d0
    c3=f1+e1+d2   =14+C4+63   =B3 -> F8h=(2) B3667A2E for c3 c2 c1 c0
    b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 for b3 b2 b1 b0

    Now we have all needed values, then
    X=(1)+         a0=         DE+66=B8
    Y=(2)+      b0+a1=      F8+D3+EF=C4
    Z=(3)+   c0+b1+a2=   4F+2E+FF+CD=53
    W=(4)+d0+c1+b2+a3=35+01+7A+6B+AB=8E
    (final computation)

    结论:要将 CRC-32 的记存器的值从 ABCDEF66 改变到 56331478 我们需要这样一个字节
    序列: B8 C4 53 8E


    CRC-32
    的破解算法

     假如你考虑手动计算这个可以还原CRC记存器的字节序列,那么这将很难变成一个
    简洁的算法.  
      
    看看下面这个最后计算的附加版本:
                                Position
    X =(1) +                a0     0
    Y =(2) +           b0 + a1     1
    Z =(3) +      c0 + b1 + a2     2
    W =(4) + d0 + c1 + b2 + a3     3
    f0= e0 + d1 + c2 + b3          4
    f1= e1 + d2 + c3               5
    f2= e2 + d3                    6
    f3= e3                         7

    (figure 5)
      
      
    它就等同于figure 4,只不过是一些值/字节被交换了.这种方法可以帮助我们构造一个
    简洁的算法.这里我们用一个8字节的缓冲区,0-3位我们放置a0a3,4-7位我们放置f0
    f3.
    象以前一样,我们用这个已知值e3(figure 5中得知)在表中查出(e3 e2 e1 e0),并且
    象图5(figure 5)中所示,将它们放到第4(position 4),我们马上得到了d3的值.因为f2=
    e2+d3,
    所以f2+e2=d3.又因为(4)已知(入口值),我们照样把它也放到位置3.然后在用d3查表
    得到(d3 d2 d1 d0),同上也将他们放到图中所述位置.同样,由于有f1+e1+d2=c3在位置5.
      
    我们继续做直到将b3 b2 b1 b0放到位置1,对了,就是它!  Et voila!
    此时,缓冲区的第3-0字节中已经包含全部元素,用来计算X~W! 

    算法总结如下:
    1.
    对于这个8字节的缓冲区,0~3字节放入a0...a3(CRC记存器起始值),4~7字节放入f0...f3
      (
    目标记存器的值).
    2.
    取出位置7的已知值,查表得到相应值.
    3.
    将查出值放如图5相应位置,其实就是做XOR运算.(为了直观,可以拟定此图)
    4.
    将入口字节放入图中.也是做XOR运算.
    5.
    继续做2,3两步3,同时每次降低1个位置 position 5 to 4, 4 to 3 and so on.


    算法的实现:

     现在是时候给出代码了.下面就是用汇编写成的可执行的CRC-32算法(用其他语言也一样
    简单,对于其他的CRC-32标准也一样).注意在汇编中(计算机里)双字在读写操作中顺序都是
    反着的.就是逆向顺序.
    crcBefore       dd (?)
    wantedCrc       dd (?)
    buffer          db 8 dup (?)

            mov     eax, dword ptr[crcBefore] ;/*
            mov     dword ptr[buffer], eax
            mov     eax, dword ptr[wantedCrc] ; Step 1
            mov     dword ptr[buffer+4], eax  ;*/

            mov     di, 4
    computeReverseLoop:
            mov     al, byte ptr[buffer+di+3] ;/*
            call   GetTableEntry              ; Step 2 */
            xor     dword ptr[buffer+di], eax ; Step 3
            xor     byte ptr[buffer+di-1], bl ; Step 4
            dec     di                        ;/*
            jnz    computeReverseLoop         ; Step 5 */

    Notes:
    -Registers eax, di bx are used

    Implementation of GetTableEntry

    crctable        dd 256 dup (?)       ;should be defined globally somewhere & initialized of course

            mov     bx, offset crctable-1
    getTableEntryLoop:
            add     bx, 4                ;points to (crctable-1)+k*4 (k:1..256)
            cmp     [bx], al             ;must always find the value somewhere
            jne     getTableEntryLoop

            sub     bx, 3
            mov     eax, [bx]
            sub     bx, offset crctable
            shr     bx, 2

            ret

    On return eax contains a table entry, bx contains the entry number.


    Outtro

     好了...你终于读到了本文的结尾.假如你认为从此不管对什么样的CRC保护都可以说bye
    bye
    ,那么你错了,不是的!很容易就可以写出对付破解CRC的代码的.想要成功的破解CRC
    你需要知道在一个保护中,到底使用的是那一种CRC算法,并且要知道CRC的具体的计算位置.
    比如说这里一种简单的对策就是使用2种不同的CRC算法,或者可以结合其他的数据保护算法
    共同使用.
      
    无论如何...我希望所有这里所介绍的内容都是受人关注的,并且我希望你(读者)可以很
    高兴的读着篇文章,就象我很高兴写一样.   


               

    翻译过程中难免有错误,不当之处,请见谅.              译者:  arbiter
                                                        2001-2-8 22:41
                                                        
                                                        
                                                        
    Fnx go out to the beta-testers Douby/DREAD and Knotty Dread for the good
    comments on my work which made it even better!

    For a sample CRC-32 correcting patcher program visit my webpages:
        http://surf.to/anarchriz  -> Programming -> Projects
    (it's still a preview but will give you a proof of my idea)

    For more info on DREAD visit http://dread99.cjb.net

    If you still have questions you can mail me at anarchriz@hotmail.com,
    or try the channels #DreaD, #Win32asm, #C.I.A and #Cracking4Newbies (in that
    order) on EFnet (on IRC).

    CYA ALL! - Anarchriz

    "The system makes its morons, then despises them for their ineptitude, and
    rewards its 'gifted few' for their rarity." - Colin Ward


    附录:

    CRC-16 Table

      00h   0000 C0C1 C181 0140 C301 03C0 0280 C241
      08h   C601 06C0 0780 C741 0500 C5C1 C481 0440
      10h   CC01 0CC0 0D80 CD41 0F00 CFC1 CE81 0E40
      18h   0A00 CAC1 CB81 0B40 C901 09C0 0880 C841

      20h   D801 18C0 1980 D941 1B00 DBC1 DA81 1A40
      28h   1E00 DEC1 DF81 1F40 DD01 1DC0 1C80 DC41
      30h   1400 D4C1 D581 1540 D701 17C0 1680 D641
      38h   D201 12C0 1380 D341 1100 D1C1 D081 1040

      40h   F001 30C0 3180 F141 3300 F3C1 F281 3240
      48h   3600 F6C1 F781 3740 F501 35C0 3480 F441
      50h   3C00 FCC1 FD81 3D40 FF01 3FC0 3E80 FE41
      58h   FA01 3AC0 3B80 FB41 3900 F9C1 F881 3840

      60h   2800 E8C1 E981 2940 EB01 2BC0 2A80 EA41
      68h   EE01 2EC0 2F80 EF41 2D00 EDC1 EC81 2C40
      70h   E401 24C0 2580 E541 2700 E7C1 E681 2640
      78h   2200 E2C1 E381 2340 E101 21C0 2080 E041

      80h   A001 60C0 6180 A141 6300 A3C1 A281 6240
      88h   6600 A6C1 A781 6740 A501 65C0 6480 A441
      90h   6C00 ACC1 AD81 6D40 AF01 6FC0 6E80 AE41
      98h   AA01 6AC0 6B80 AB41 6900 A9C1 A881 6840

      A0h   7800 B8C1 B981 7940 BB01 7BC0 7A80 BA41
      A8h   BE01 7EC0 7F80 BF41 7D00 BDC1 BC81 7C40
      B0h   B401 74C0 7580 B541 7700 B7C1 B681 7640
      B8h   7200 B2C1 B381 7340 B101 71C0 7080 B041

      C0h   5000 90C1 9181 5140 9301 53C0 5280 9241
      C8h   9601 56C0 5780 9741 5500 95C1 9481 5440
      D0h   9C01 5CC0 5D80 9D41 5F00 9FC1 9E81 5E40
      D8h   5A00 9AC1 9B81 5B40 9901 59C0 5880 9841

      E0h   8801 48C0 4980 8941 4B00 8BC1 8A81 4A40
      E8h   4E00 8EC1 8F81 4F40 8D01 4DC0 4C80 8C41
      F0h   4400 84C1 8581 4540 8701 47C0 4680 8641
      F8h   8201 42C0 4380 8341 4100 81C1 8081 4040


    CRC-32 Table

      00h   00000000 77073096 EE0E612C 990951BA
      04h   076DC419 706AF48F E963A535 9E6495A3
      08h   0EDB8832 79DCB8A4 E0D5E91E 97D2D988
      0Ch   09B64C2B 7EB17CBD E7B82D07 90BF1D91

      10h   1DB71064 6AB020F2 F3B97148 84BE41DE
      14h   1ADAD47D 6DDDE4EB F4D4B551 83D385C7
      18h   136C9856 646BA8C0 FD62F97A 8A65C9EC
      1Ch   14015C4F 63066CD9 FA0F3D63 8D080DF5

      20h   3B6E20C8 4C69105E D56041E4 A2677172
      24h   3C03E4D1 4B04D447 D20D85FD A50AB56B
      28h   35B5A8FA 42B2986C DBBBC9D6 ACBCF940
      2Ch   32D86CE3 45DF5C75 DCD60DCF ABD13D59

      30h   26D930AC 51DE003A C8D75180 BFD06116
      34h   21B4F4B5 56B3C423 CFBA9599 B8BDA50F
      38h   2802B89E 5F058808 C60CD9B2 B10BE924
      3Ch   2F6F7C87 58684C11 C1611DAB B6662D3D

      40h   76DC4190 01DB7106 98D220BC EFD5102A
      44h   71B18589 06B6B51F 9FBFE4A5 E8B8D433
      48h   7807C9A2 0F00F934 9609A88E E10E9818
      4Ch   7F6A0DBB 086D3D2D 91646C97 E6635C01

      50h   6B6B51F4 1C6C6162 856530D8 F262004E
      54h   6C0695ED 1B01A57B 8208F4C1 F50FC457
      58h   65B0D9C6 12B7E950 8BBEB8EA FCB9887C
      5Ch   62DD1DDF 15DA2D49 8CD37CF3 FBD44C65

      60h   4DB26158 3AB551CE A3BC0074 D4BB30E2
      64h   4ADFA541 3DD895D7 A4D1C46D D3D6F4FB
      68h   4369E96A 346ED9FC AD678846 DA60B8D0
      6Ch   44042D73 33031DE5 AA0A4C5F DD0D7CC9

      70h   5005713C 270241AA BE0B1010 C90C2086
      74h   5768B525 206F85B3 B966D409 CE61E49F
      78h   5EDEF90E 29D9C998 B0D09822 C7D7A8B4
      7Ch   59B33D17 2EB40D81 B7BD5C3B C0BA6CAD

      80h   EDB88320 9ABFB3B6 03B6E20C 74B1D29A
      84h   EAD54739 9DD277AF 04DB2615 73DC1683
      88h   E3630B12 94643B84 0D6D6A3E 7A6A5AA8
      8Ch   E40ECF0B 9309FF9D 0A00AE27 7D079EB1

      90h   F00F9344 8708A3D2 1E01F268 6906C2FE
      94h   F762575D 806567CB 196C3671 6E6B06E7
      98h   FED41B76 89D32BE0 10DA7A5A 67DD4ACC
      9Ch   F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5

      A0h   D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252
      A4h   D1BB67F1 A6BC5767 3FB506DD 48B2364B
      A8h   D80D2BDA AF0A1B4C 36034AF6 41047A60
      ACh   DF60EFC3 A867DF55 316E8EEF 4669BE79

      B0h   CB61B38C BC66831A 256FD2A0 5268E236
      B4h   CC0C7795 BB0B4703 220216B9 5505262F
      B8h   C5BA3BBE B2BD0B28 2BB45A92 5CB36A04
      BCh   C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D

      C0h   9B64C2B0 EC63F226 756AA39C 026D930A
      C4h   9C0906A9 EB0E363F 72076785 05005713
      C8h   95BF4A82 E2B87A14 7BB12BAE 0CB61B38
      CCh   92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21

      D0h   86D3D2D4 F1D4E242 68DDB3F8 1FDA836E
      D4h   81BE16CD F6B9265B 6FB077E1 18B74777
      D8h   88085AE6 FF0F6A70 66063BCA 11010B5C
      DCh   8F659EFF F862AE69 616BFFD3 166CCF45

      E0h   A00AE278 D70DD2EE 4E048354 3903B3C2
      E4h   A7672661 D06016F7 4969474D 3E6E77DB
      E8h   AED16A4A D9D65ADC 40DF0B66 37D83BF0
      ECh   A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9

      F0h   BDBDF21C CABAC28A 53B39330 24B4A3A6
      F4h   BAD03605 CDD70693 54DE5729 23D967BF
      F8h   B3667A2E C4614AB8 5D681B02 2A6F2B94
      FCh   B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D

     

     CRC算法原理及C語言實現

    对于RF通讯的通讯可靠性,有很强的检错能力的CRC.
    这里列出了实际中8,16位单片机用到的CRC实用子程序.

    ·                        1. 半字节16CRC---halfBcal_crc

    ·                        2.查表CRC---Bytecal_crc

    ·                        3.位计算的CRC.----bitcal_crc

    ·                        4.CRC检错的程序----IsCrc16

    ·                        5.一个很不错的CRC计算程序,--CRC16



    同时本文列出了调用函数和例程 

    const code Ploy=0x1021; 

    #ifndef uchar 
    typedef unsigned char uchar; 
    #endif 
    #ifndef uint 
    typedef unsigned int uint; 
    #endif 
    static unsigned short crc; //16bit 
    unsigned int code crc_ta[16]={ /* CRC 
    半字节余式表 */ 0X0000,0X1021,0X2042, 0X3063, 0X4084, 0X50A5, 0X60C6, 0X70E7, 0X8108,0X9129,0XA14A,0XB16B,0XC18C,0XD1AD,0XE1CE,0XF1EF, };


    unsigned int code crc_tab[256]={ /* CRC 
    余式表 */ 0X0000, 0X1021, 0X2042, 0X3063, 0X4084, 0X50A5, 0X60C6, 0X70E7, 0X8108, 0X9129, 0XA14A, 0XB16B, 0XC18C, 0XD1AD, 0XE1CE, 0XF1EF, 0X1231, 0X0210, 0X3273, 0X2252, 0X52B5, 0X4294, 0X72F7, 0X62D6, 0X9339, 0X8318, 0XB37B, 0XA35A, 0XD3BD, 0XC39C, 0XF3FF, 0XE3DE, 0X2462, 0X3443, 0X0420, 0X1401, 0X64E6, 0X74C7, 0X44A4, 0X5485, 0XA56A,0XB54B, 0X8528, 0X9509, 0XE5EE, 0XF5CF, 0XC5AC, 0XD58D, 0X3653, 0X2672, 0X1611, 0X0630, 0X76D7, 0X66F6, 0X5695, 0X46B4, 0XB75B,0XA77A, 0X9719, 0X8738, 0XF7DF, 0XE7FE, 0XD79D, 0XC7BC, 0X48C4,0X58E5, 0X6886, 0X78A7, 0X0840, 0X1861, 0X2802, 0X3823, 0XC9CC, 0XD9ED, 0XE98E, 0XF9AF, 0X8948, 0X9969, 0XA90A, 0XB92B, 0X5AF5, 0X4AD4, 0X7AB7, 0X6A96, 0X1A71, 0X0A50, 0X3A33, 0X2A12, 0XDBFD, 0XCBDC, 0XFBBF, 0XEB9E, 0X9B79, 0X8B58, 0XBB3B, 0XAB1A, 0X6CA6, 0X7C87, 0X4CE4, 0X5CC5, 0X2C22, 0X3C03, 0X0C60, 0X1C41, 0XEDAE, 0XFD8F, 0XCDEC, 0XDDCD, 0XAD2A, 0XBD0B, 0X8D68, 0X9D49, 0X7E97, 0X6EB6, 0X5ED5, 0X4EF4, 0X3E13, 0X2E32, 0X1E51, 0X0E70, 0XFF9F, 0XEFBE, 0XDFDD, 0XCFFC, 0XBF1B, 0XAF3A, 0X9F59, 0X8F78, 0X9188, 0X81A9, 0XB1CA, 0XA1EB, 0XD10C, 0XC12D, 0XF14E, 0XE16F, 0X1080, 0X00A1, 0X30C2, 0X20E3, 0X5004, 0X4025, 0X7046, 0X6067, 0X83B9, 0X9398, 0XA3FB, 0XB3DA, 0XC33D, 0XD31C, 0XE37F, 0XF35E, 0X02B1, 0X1290, 0X22F3, 0X32D2, 0X4235, 0X5214, 0X6277, 0X7256, 0XB5EA, 0XA5CB, 0X95A8, 0X8589, 0XF56E, 0XE54F, 0XD52C, 0XC50D, 0X34E2, 0X24C3, 0X14A0, 0X0481, 0X7466, 0X6447, 0X5424, 0X4405, 0XA7DB, 0XB7FA, 0X8799, 0X97B8, 0XE75F, 0XF77E, 0XC71D, 0XD73C, 0X26D3, 0X36F2, 0X0691, 0X16B0, 0X6657, 0X7676, 0X4615, 0X5634, 0XD94C, 0XC96D, 0XF90E, 0XE92F, 0X99C8, 0X89E9, 0XB98A, 0XA9AB, 0X5844, 0X4865, 0X7806, 0X6827, 0X18C0, 0X08E1, 0X3882, 0X28A3, 0XCB7D, 0XDB5C, 0XEB3F, 0XFB1E, 0X8BF9, 0X9BD8, 0XABBB, 0XBB9A, 0X4A75, 0X5A54, 0X6A37, 0X7A16, 0X0AF1, 0X1AD0, 0X2AB3, 0X3A92, 0XFD2E, 0XED0F, 0XDD6C, 0XCD4D, 0XBDAA, 0XAD8B, 0X9DE8, 0X8DC9, 0X7C26, 0X6C07, 0X5C64, 0X4C45, 0X3CA2, 0X2C83, 0X1CE0, 0X0CC1, 0XEF1F, 0XFF3E, 0XCF5D, 0XDF7C, 0XAF9B, 0XBFBA, 0X8FD9, 0X9FF8, 0X6E17, 0X7E36, 0X4E55, 0X5E74, 0X2E93, 0X3EB2, 0X0ED1, 0X1EF0 }; 

    unsigned int halfBcal_crc(unsigned char *ptr, unsigned char len)
    {
    unsigned int crc;
    unsigned char da; 
    crc=0;
    while(len--!=0)

    // da=((uchar)(crc/256))/16; /* 
    暂存CRC 的高四位 */
    da=((unsigned char)(crc>>8))>>4; 
    crc<<=4; /* CRC 
    右移位,相当于取CRC 的低12 位)*/
    crc^=crc_ta[da^(*ptr/16)]; /* CRC 
    的高位和本字节的前半字节相加后查表计算CRC, 然后加上上一次CRC 的余数 */
    da=((unsigned char)(crc>>8))>>4; /* 
    暂存CRC 的高 */
    crc<<=4; /* CRC 
    右移位, 相当于CRC 的低12 位) */
    crc^=crc_ta[da^(*ptr&0x0f)]; /* CRC 
    的高位和本字节的后半字节相加后查表计算CRCH缓笤偌由仙弦淮蜟RC 的余数 */

    ptr++; }

    return(crc);

    }

    unsigned int bitcal_crc(unsigned char *ptr, unsigned char len)


    { unsigned char i; unsigned int crc=0; while(len--!=0)

    {

    for(i=0x80; i!=0; i/=2)

    {

    if((crc&0x8000)!=0)

    {

    crc<<=1;

    crc^=0x1021;

    } /* 余式CRC 乘以再求CRC */

    else crc<<=1;

    if((*ptr&i)!=0) crc^=Ploy; /* 再加上本位的CRC */ }

    ptr++;

    }

    return(crc);

    }

    unsigned int Bytecal_crc(unsigned char *ptr, unsigned char len)

    {

    unsigned int crc;

    unsigned char da;

    crc=0;

    while(len--!=0)

    {

    da=(uchar) (crc/256); /* 位二进制数的形式暂存CRC 的高 */

    crc<<=8; /* 左移位,相当于CRC 的低位乘以8 */

    crc^=crc_tab[da^*ptr]; /* 位和当前字节相加后再查表求CRC ,再加上以前的CRC */

    ptr++;

    }

    return(crc);

    }

    uchar IsCrc16(const uchar *pData,int len)

    { uint fcs;

    fcs=0xffff;

    while(len>0)

    {

    fcs = (fcs << 8)^ crc_tab[fcs^ (*pData)&0xff];

    len--;

    pData++;

    }

    return(!fcs);

    }

    unsigned char CRC16(unsigned char ser_data)

    { // Update the CRC for transmitted and received data using // the CCITT 16bit algorithm (X^16 + X^12 + X^5 + 1). crc = (unsigned char)(crc >> 8) | (crc << 8);

    crc ^= ser_data;

    crc ^= (unsigned char)(crc & 0xff) >> 4;

    crc ^= (crc << 8) << 4; crc ^= ((crc & 0xff) << 4) << 1;

    return 0;

    }

    unsigned short doCRC16( unsigned char *mstr,unsigned char len)

    {

    unsigned char ch;

    crc = 0;

    do{

    ch = *mstr++;

    CRC16(ch);

    }while(--len);

    return(crc);

    }

    CRC-16/CRC-32 程序代码:

    不久前写一程序时要用到 CRC-16 ,但找来找去只在 UDDF 里找到一个 Delphi 的 CRC-32 程序代码,而且是用查表法,虽然说查表法速度快,但 256 项 32 位数据我怀疑可能会有输入错误, 让人不是那么放心,而我又不知道这个表是怎么算出来的。后来我又在一本两年前的笔记本里找到一段关于 CRC 的内容, 也不知是从哪里抄来的,还好里面有一段程序代码,是 CRC-16 的,这段程序正是产生 CRC 表的, 可是这区区几行的程序(基本上与下面的 BuilderTable16 函数相同)看得我一头雾水,直到这两天才弄明白, 并据此推出 CRC-32 的算法,现将全部程序列在下面,并作一些说明以助于理解,不但要知其然,还要知其所以然嘛: 

    // 注意:因最高位一定为“1”,故略去 
    const unsigned short cnCRC_16 = 0x8005; 
    // CRC-16 = X16 + X15 + X2 + X0 
    const unsigned short cnCRC_CCITT = 0x1021; 
    // CRC-CCITT = X16 + X12 + X5 + X0,据说这个 16 位 CRC 多项式比上一个要好 
    const unsigned long cnCRC_32 = 0x04C10DB7; 
    // CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0 

    unsigned long Table_CRC[256]; // CRC 表 

    // 构造 16 位 CRC 表 
    void BuildTable16( unsigned short aPoly ) 

    unsigned short i, j; 
    unsigned short nData; 
    unsigned short nAccum; 

    for ( i = 0; i < 256; i++ ) 

    nData = ( unsigned short )( i << 8 ); 
    nAccum = 0; 
    for ( j = 0; j < 8; j++ ) 

    if ( ( nData ^ nAccum ) & 0x8000 ) 
    nAccum = ( nAccum << 1 ) ^ aPoly; 
    else 
    nAccum <<= 1; 
    nData <<= 1; 

    Table_CRC[i] = ( unsigned long )nAccum; 



    // 计算 16 位 CRC 值,CRC-16 或 CRC-CCITT 
    unsigned short CRC_16( unsigned char * aData, unsigned long aSize ) 

    unsigned long i; 
    unsigned short nAccum = 0; 

    BuildTable16( cnCRC_16 ); // or cnCRC_CCITT 
    for ( i = 0; i < aSize; i++ ) 
    nAccum = ( nAccum << 8 ) ^ ( unsigned short )Table_CRC[( nAccum >> 8 ) ^ *aData++]; 
    return nAccum; 


    // 构造 32 位 CRC 表 
    void BuildTable32( unsigned long aPoly ) 

    unsigned long i, j; 
    unsigned long nData; 
    unsigned long nAccum; 

    for ( i = 0; i < 256; i++ ) 

    nData = ( unsigned long )( i << 24 ); 
    nAccum = 0; 
    for ( j = 0; j < 8; j++ ) 

    if ( ( nData ^ nAccum ) & 0x80000000 ) 
    nAccum = ( nAccum << 1 ) ^ aPoly; 
    else 
    nAccum <<= 1; 
    nData <<= 1; 

    Table_CRC[i] = nAccum; 



    // 计算 32 位 CRC-32 值 
    unsigned long CRC_32( unsigned char * aData, unsigned long aSize ) 

    unsigned long i; 
    unsigned long nAccum = 0; 

    BuildTable32( cnCRC_32 ); 
    for ( i = 0; i < aSize; i++ ) 
    nAccum = ( nAccum << 8 ) ^ Table_CRC[( nAccum >> 24 ) ^ *aData++]; 
    return nAccum; 


    说明: CRC 的计算原理如下(一个字节的简单例子) 
    11011000 00000000 00000000 <- 一个字节数据, 左移 16b 
    ^10001000 00010000 1 <- CRC-CCITT 多项式, 17b 
    -------------------------- 
    1010000 00010000 10 <- 中间余数 
    ^1000100 00001000 01 
    ------------------------- 
    10100 00011000 1100 
    ^10001 00000010 0001 
    ----------------------- 
    101 00011010 110100 
    ^100 01000000 100001 
    --------------------- 
    1 01011010 01010100 
    ^1 00010000 00100001 
    ------------------- 
    01001010 01110101 <- 16b CRC 

    仿此,可推出两个字节数据计算如下:d 为数据,p 为项式,a 为余数 
    dddddddd dddddddd 00000000 00000000 <- 数据 D ( D1, D0, 0, 0 ) 
    ^pppppppp pppppppp p <- 多项式 P 
    ----------------------------------- 
    ... 
    aaaaaaaa aaaaaaaa 0 <- 第一次的余数 A'' ( A''1, A''0 ) 
    ^pppppppp pppppppp p 
    -------------------------- 
    ... 
    aaaaaaaa aaaaaaaa <- 结果 A ( A1, A0 ) 

    由此与一字节的情况比较,将两个字节分开计算如下: 
    先算高字节: 
    dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0 
    ^pppppppp pppppppp p <- P 
    ----------------------------------- 
    ... 
    aaaaaaaa aaaaaaaa <- 高字节部分余数 PHA1, PHA0 

    此处的部分余数与前面两字节算法中的第一次余数有如下关系,即 A''1 = PHA1 ^ D0, A''0 = PHA0: 
    aaaaaaaa aaaaaaaa <- PHA1, PHA0 
    ^dddddddd <- D0 
    ----------------- 
    aaaaaaaa aaaaaaaa <- A''1, A''0 

    低字节的计算: 
    aaaaaaaa 00000000 00000000 <- A''1, 0, 0 
    ^pppppppp pppppppp p <- P 
    -------------------------- 
    ... 
    aaaaaaaa aaaaaaaa <- 低字节部分余数 PLA1, PLA0 
    ^aaaaaaaa <- A''0 , 即 PHA0 
    ----------------- 
    aaaaaaaa aaaaaaaa <- 最后的 CRC ( A1, A0 ) 

    总结以上内容可得规律如下: 
    设部分余数函数 
    PA = f( d ) 
    其中 d 为一个字节的数据(注意,除非 n = 0 ,否则就不是原始数据,见下文) 
    第 n 次的部分余数 
    PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( d ) 
    其中的 
    d = ( PA( n - 1 ) >> 8 ) ^ D( n ) 
    其中的 D( n ) 才是一个字节的原始数据。 

    公式如下: 
    PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( ( PA( n - 1 ) >> 8 ) ^ D( n ) ) 

    可以注意到函数 f( d ) 的参数 d 为一个字节,对一个确定的多项式 P, f( d ) 的返回值 
    是与 d 一一对应的,总数为 256 项,将这些数据预先算出保存在表里,f( d )就转换为一 
    个查表的过程,速度也就可以大幅提高,这也就是查表法计算 CRC 的原理,在 CRC_16 和 
    CRC_32 两个函数的循环中的语句便是上面那个公式。 

    再来看 CRC 表是如何计算出来的,即函数 f( d ) 的实现方法。分析前面一个字节数据的 
    计算过程可发现,d 对结果的影响只表现为对 P 的移位异或,看计算过程中的三个 8 位 
    的列中只有低两个字节的最后结果是余数,而数据所在的高 8 位列最后都被消去了,因其 
    中的运算均为异或,不产生进位或借位,故每一位数据只影响本列的结果,即 d 并不直接 
    影响结果。再将前例变化一下重列如下: 
    11011000 
    -------------------------- 
    10001000 00010000 1 // P 
    ^ 1000100 00001000 01 // P 
    ^ 000000 00000000 000 // 0 
    ^ 10001 00000010 0001 // P 
    ^ 0000 00000000 00000 // 0 
    ^ 100 01000000 100001 // P 
    ^ 00 00000000 0000000 // 0 
    ^ 1 00010000 00100001 // P 
    ------------------- 
    01001010 01110101 

    现在的问题就是如何根据 d 来对 P 移位异或了,从上面的例子看,也可以理解为每步 
    移位,但根据 d 决定中间余数是否与 P 异或。从前面原来的例子可以看出,决定的条 
    件是中间余数的最高位为0,因为 P 的最高位一定为1,即当中间余数与 d 相应位异或 
    的最高位为1时,中间余数移位就要和 P 异或,否则只需移位即可。具体做法见程序中 
    的 BuildTable16 和 BuildTable32 两个函数,其方法如下例(上例的变形,注意其中 
    空格的移动表现了 d 的影响如何被排除在结果之外): 

    d --------a-------- 
    1 00000000 00000000 <- HSB = 1 
    0000000 000000000 <- a <<= 1 
    0001000 000100001 <- P, CRC-CCITT 不含最高位的 1 
    ----------------- 
    1 0001000 000100001 
    001000 0001000010 
    000100 0000100001 
    ----------------- 
    0 001100 0001100011 <- HSB = 0 
    01100 00011000110 
    ----------------- 
    1 01100 00011000110 <- HSB = 1 
    1100 000110001100 
    0001 000000100001 
    ----------------- 
    1 1101 000110101101 <- HSB = 0 
    101 0001101011010 
    ----------------- 
    0 101 0001101011010 <- HSB = 1 
    01 00011010110100 
    00 01000000100001 
    ----------------- 
    0 01 01011010010101 <- HSB = 0 
    1 010110100101010 
    ----------------- 
    0 1 010110100101010 <- HSB = 1 
    0101101001010100 
    0001000000100001 
    ----------------- 
    0100101001110101 <- CRC 

    结合这些,前面的程序就好理解了。至于 32 位 CRC 的计算与 16 相似,就不多加说明,请参考源程序。

     

    AVR单片机CRC校验码的查表与直接生成
     言:
      随着技术的不断进步,各种数据通信的应用越来越广泛。由于传输距离、现场状况、干扰等诸多因素的影响,设备之间的通信数据常会发生一些无法预测的错误。为了降低错误所带来的影响,一般在通信时采用数据校验的办法,而循环冗余码校验是常用的重要校验方法之一。

      AVR高速嵌入式单片机是8RISC MCU,执行大多数指令只需一个时钟周期,速度快(8MHz AVR的运行速度约等于200MHz 80C51的运行速度),32个通用寄存器直接与ALU相连,消除了运算瓶颈;内嵌可串行下载或自我编程的FlashEPPROM,功能繁多,具有多种运行模式。

      本文采用Atmel公司的Atmega128高速嵌入式单片机,依照IEEE 1999年公布的802.11无线局域网协议标准,采用32位循环冗余校验码(Cyclic Redundancy Check)实现无线传输数据时的差错校验。

    1 CRC循环冗余校验码原理

    1.1 数据传输的帧格式

      根据IEEE制定的802.11无线局域网络协议,在数据传输时都应按照帧传输。这里,我们采用了信息处理系统-数据通信-高级数据链路控制规程-帧结构,它的每个帧由下列字段组成(传输顺序自左至右):

    地址——数据站地址字段;
    控制——控制字段。
    信息——信息字段;
    CRC
    校验位——根据前面三个字段生成的CRC校验位。
    由地址、控制、信息三个字段组成的总的字段统称为数据段。

    1.2 CRC校验码的理论生成方法

      CRC校验采用多项式编码方法,被处理的数据块可以看作是一个n阶的二进制多项式。这里,假定待发送的二进制数据段为g(x),生成多项式为m(x),得到的CRC校验码为c(x)

      CRC校验码的编码方法是用待发送的二进制数据g(x)除以生成多项式m(x),将最后的余数作为CRC校验码,实现步骤如下。

        设待发送的数据块是m位的二进制多项式 g(x),生成多项式为r阶的m(x)。在数据块的末尾添加r0,数据块的长度增加到m r位,对应的二进制多项式为G(x) 

       用生成多项式m(x)去除G(x) ,求得余数为阶数是r-1的二进制多项式c(x)。此二进制多项式 c(x)就是g(x)经过生成多项式m(x)编码的CRC校验码。

       用模2的方式减去c(x),得到的二进制多项式就是包含了CRC校验码的待发送字符串。
    CRC
    校验可以100%地检测出所有奇数个随机错误和长度小于等于rrm(x)的阶数)的突发错误。所以,CRC的生成多项式的阶数越高,误判的概率就越小。CCITT建议:2048 Kb/sPCM基群设备采用CRC-4方案,使用的CRC校验码生成多项式m(x)=x4 x 1 。采用16CRC校验,可以保证在1014bit码元中只含有1位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16,其生成多项式m(x)=x16 x15 x2 1;而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16,其生成多项式m(x)= x16 x15 x5 1CRC-32的生成多项式m(x)=x32 x26 x23 x22 x16 x12 x11 x10 x8 x7 x5 x4 x2 x 1CRC-32出错的概率为CRC-1610-5。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582Intel8273Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。

      m(x) 生成多项式的系数为01,但是m(x) 的首项系数为1,末项系数也必须为1m(x) 的次数越高,其检错能力越强。

    使用Atmega128生成32CRC校验码

    2.1 直接计算法生成32CRC校验码

      直接计算法就是依据CRC校验码的产生原理来设计程序。其优点是模块代码少,修改灵活,可移植性好。这种算法简单,容易实现,对任意长度生成多项式m(x) 都适用。在发送的数据不长的情况下可以使用,但是如果发送的数据块很长,这种方法就不太适合了。因为它1次只能处理1位数据,效率太低,运算量大。

      计算法生成32CRC校验码的流程如图1所示。

    AVR单片机汇编语言实现CRC-32源程序见本刊网络补充版(http://www.dpj.com.cn)。

    2.2 查表法生成32CRC校验码

      和直接计算法相反,查表法生成32CRC校验码的优点是运算量小,速度快;缺点是可移植性较差。这种算法首先要求得到32CRC生成表,由于1个字节有8位,所以这个表总共有256项。但是,由于AVR高速嵌入式单片机中的寄存器是以1个字节为单位的,所以在编程实现中,这个CRC生成表总共有1024项,分别从0~1023;每4位对应132CRC生成表的项,每一项都从高到低降幂排列。关于32CRC生成表的程序详见本刊网络补充版(http://www.dpj.com.cn)。

      查表法生成32CRC校验码的流程如图2所示。

    2所示的流程图中,在通过异或运算得到CRC生成表的索引时,由于AVR高速嵌入式单片机中的寄存器是以1个字节为单元的,所以在编程实现中应根据所要求生成的CRC校验码的位数乘以相应的系数。例如:在数据传输时要求32CRC校验码,应该把所得到的索引数乘以系数4,然后再从高到低依次取得32CRC生成表单元中的内容。

      使用查表法得到32CRC校验码的源程序详见本刊网络补充版(http://www.dpj.com.cn)。

    实验结果

      为了比较所述两种32CRC校验码生成方法的特点,分别选取不同字节数的数据段,对两种方法在不同情况下的效果进行比较,如表1所列。

    以上所有实验结果均是在AVR Studio4仿真软件上选用Atmel公司的Atmega128高速嵌入式单片机为实验设备平台,在12MHz运行速度下模拟所得。

      在调用32CRC生成表程序以得到32CRC生成表时,耗时3968.33μs,执行了47620个时钟周期。从上述实验结果可得出以下几点结论。

       如果不考虑生成32CRC生成表的时间,例如直接把32CRC生成表烧入到Atmega128的可编程闪速存储器Flash中,由表1可清楚地看出,查表法的运行速度比直接计算法要快得多。因此,在类似情况下,在进行数据传输要求生成32CRC校验码时,应该选择查表法。

       在某些应用中,如果对硬件存储器空间要求很高,并且在一定程度上对时间没有特别高的要求时,可以采用直接计算法,以避免查表法中CRC生成表对存储器空间的占用。

       虽然实验结果对32CRC校验码的两种算法进行了对比,但是所得到的结论也适用于8位、16位、24CRC校验码。

     

      CRC循环冗余校验码是一种方便、有效、快速的校验方法,被广泛应用在许多实际工程中。文中所列的两种算法——查表法和直接计算法,都可以得到CRC校验码;但是它们各有特点,在工程应用中应该根据实际需要选择最适合的方法,以得到最优的效果。

     

    CRC校验实用程序库 - 计算机论文

      在数据存储和数据通讯领域,为了保证数据的正确,就不得不采用检错的手段。在诸多检错手段中,CRC是最著名的一种。CRC的全称是循环冗余校验,其特点是:检错能力极强,开销小,易于用编码器及检测电路实现。从其检错能力来看,它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑,均远远优于奇偶校验及算术和校验等方式。因而,在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25FCS(帧检错序列)采用的是CRC-CCITTARJLHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIFTIFF等也都用CRC作为检错手段。 
    CRC
    的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式如表1所示。 
    @@10A08800.GIF;
    1.最常用的CRC码及生成多项式@@ 
    由于CRC在通讯和数据处理软件中经常采用,笔者在实际工作中对其算法进行了研究和比较,总结并编写了一个具有最高效率的CRC通用程序库。该程序采用查表法计算CRC,在速度上优于一般的直接模仿硬件的算法,可以应用于通讯和数据压缩程序。 
    通常的CRC算法在计算一个数据段的CRC值时,其CRC值是由求解每个数值的CRC值的和对CRC寄存器的值反复更新而得到的。这样,求解CRC的速度较慢。通过对CRC算法的研究,我们发现:一个8位数据加到16位累加器中去,只有累加器的高8位或低8位与数据相作用,其结果仅有256种可能的组合值。因而,我们可以用查表法来代替反复的运算,这也同样适用于CRC32的计算。本文所提供的程序库中,函数crchware是一般的16CRC的算法;mk-crctbl用以在内存中建立一个CRC数值表;crcupdate用以查表并更新CRC累加器的值;crcrevhwarecrcrevupdate是反序算法的两个函数;BuildCRCTableCalculateBlockCRC32UpdateCharac 
    terCRC32
    用于CRC32的计算。 
    /* CRC.C——CRC
    程序库 */ 
    #define CRCCCITT 0x1021 
    #define CCITT-REV 0x8408 
    #define CRC16 0x8005 
    #define CRC16-REV 0xA001 
    #define CRC32-POLYNOMIAL 0xEDB88320L 
    /* 
    以上为CRC除数的定义 */ 
    #define NIL 0 
    #define crcupdate(d,a,t)*(a)=(*(a)<<8)^(t)[(*(a)>>8)^(d)]; 
    #define crcupdate16(d,a,t)*(a)=(*(a)>>8^(t)[(*(a)^(d))0x00ff]) 
    /* 
    以上两个宏可以代替函数crcupdatecrcrevupdate */ 
    #include 
    #include 
    #include 
    /* 
    函数crchware是传统的CRC算法,其返回值即CRC */ 
    unsigned short crchware(data,genpoly,accum) 
    unsigned short data;/* 
    输入的数据 */ 
    unsigned short genpoly;/* CRC
    除数 */ 
    unsigned short accum;/* CRC
    累加器值 */ 

    static int i; 
    data<<=8; 
    for(i=8;i>0;i--) 

    if((data^accum)0x8000) 
    accum=(accum<<1)^genpoly; 
    else 
    accum<<=1; 
    data<<=1; 

    return (accum); 

    /* 
    函数mk-crctbl利用函数crchware建立内存中的CRC数值表 */ 
    unsigned short *mk-crctbl(poly,crcfn); 
    unsigned short poly;/* CRC
    除数--CRC生成多项式 */ 
    unsigned short (*crcfn)();/* 
    指向CRC函数(例如crchware)的指针 */ 

    /* unsigned short */malloc(); */ 
    unsigned short *crctp; 
    int i; 
    if((crctp=(unsigned short*)malloc(256*sizeof(unsigned)))==0) 
    return 0; 
    for(i=0;i<256;i++) 
    crctp[i]=(*crcfn)(i,poly,0); 
    return crctp; 

    /* 
    函数mk-crctbl的使用范例 */ 
    if((crctblp=mk-crctbl(CRCCCITT,crchware))==NIL) 

    puts("insuff memory for CRC lookup table.\n"); 
    return 1; */ 
    /* 
    函数crcupdate用以用查表法计算CRC值并更新CRC累加器值 */ 
    void crcupdate(data,accum,crctab) 
    unsigned short data;/* 
    输入的数据 */ 
    unsigned short *accum;/* 
    指向CRC累加器的指针 */ 
    unsigned short *crctab;/* 
    指向内存中CRC表的指针 */ 

    static short comb-val; 
    comb-val=(*accum>>8)^data; 
    *accum=(*accum<<8)^crctab[comb-val]; 

    /* 
    函数crcrevhware是传统的CRC算法的反序算法,其返回值即CRC */ 
    unsigned short crcrevhware(data,genpoly,accum) 
    unsigned short data; 
    unsigned short genpoly; 
    unsigned short accum; 

    static int i; 
    data<<=1; 
    for(i=8;i>0;i--) 

    data>>=1; 
    if((data^accum)0x0001) 
    accum=(accum>>1)^genpoly; 
    else 
    accum>>=1; 

    return accum; 

    /* 
    函数crcrevupdate用以用反序查表法计算CRC值并更新CRC累加器值 */ 
    void crcrevupdate(data,accum,crcrevtab) 
    unsigned short data; 
    unsigned short *accum;


    循环冗余校验 CRC的算法分析和程序实现

    摘要:   通信的目的是要把信息及时可靠地传送给对方,因此要求一个通信系统传输消息必须可靠与快速,在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性,通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC(Cyclic Redundancy Check)的差错控制原理及其算法实现。

     

    关键字 通信 循环冗余校验  CRC-32  CRC-16  CRC-4

     

    概述

    在数字通信系统中可靠与快速往往是一对矛盾。若要求快速,则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误地可能性增加,传送信息地可靠性下降。若是要求可靠,则使得传送消息地速率变慢。因此,如何合理地解决可靠性也速度这一对矛盾,是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性,需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)。在传输过程误码率比较低时,用FEC方式比较理想。在传输过程误码率较高时,采用FEC容易出现“乱纠”现象。HEC方式则是ARQ和FEC的结合。在许多数字通信中,广泛采用ARQ方式,此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多,传统的有:奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等,这些方法都是增加数据的冗余量,将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验,再将得到的校验码和接受到的校验码比较,如果二者一致则认为传输正确。但这些方法都有各自的缺点,误判的概率比较高。

    循环冗余校验CRC(Cyclic Redundancy Check)是由分组线性码的分支而来,其主要应用是二元码组。编码简单且误判概率很低,在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。

     

    一、循环冗余校验码(CRC)

    CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式,由。如一个8位二进制数10110101可以表示为:。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。

    采用CRC校验时,发送方和接收方用同一个生成多项式g(x),并且g(x)的首位和最后一位的系数必须为1。CRC的处理方法是:发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。

    CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。CCITT建议:2048 kbit/s的PCM基群设备采用CRC-4方案,使用的CRC校验码生成多项式g(x)=。采用16位CRC校验,可以保证在bit码元中只含有一位未被检测出的错误。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16,其生成多项式g(x)=;而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16,其生成多项式g(x)=。CRC-32的生成多项式g(x)=。CRC-32出错的概率比CRC-16低。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。

    二、CRC校验码的算法分析

    CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下:

    (1)     设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为

    (2)     用生成多项式g(x)去除,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。

    (3)     以模2的方式减去y(x),得到二进制多项式就是包含了CRC校验码的待发送字符串。

    从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。

    为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。

    设待发送的数据t(x)为12位的二进制数据100100011100;CRC-4的生成多项式为g(x)=,阶数r为4,即10011。首先在t(x)的末尾添加4个0构成,数据块就成了1001000111000000。然后用g(x)去除,不用管商是多少,只需要求得余数y(x)。下表为给出了除法过程。

    除数次数

    被除数/ gx/结果   

    余数

    0

     1 001000111000000

    100111000000

     1 0011

     0 000100111000000

    1

     1 00111000000 

    1000000

     1 0011

     0 00001000000

    2

     1 000000

    1100

     1 0011

     0 001100

     

    从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述:

    //reg是一个5 bits的寄存器

    把reg中的值置0.

    把原始的数据后添加r个0.

    While (数据未处理完)

    Begin

    If (reg首位是1)

    reg = reg XOR 0011.

    把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。

    End

    reg的后四位就是我们所要求的余数。

    这种算法简单,容易实现,对任意长度生成多项式的G(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以一次处理8位比较合适。

    为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程:

     由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0(reg的0位),同时reg3的数据移出reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和g(x)进行XOR运算;移出的数据为0时,reg不与g(x)进行XOR运算,相当与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有种选择。上述算法可以描述如下,

    //reg是一个4 bits的寄存器

    初始化t[]={0011,0000}

    把reg中的值置0.

    把原始的数据后添加r个0.

    While (数据未处理完)

    Begin

    把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。

    reg = reg XOR t[移出的位]

    End

    上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初值为0x00000000,数据依次移入reg0(reg的0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit,所以有种选择。上述算法可以描述如下:

    //reg是一个4 Byte的寄存器

    初始化t[]={…}//共有=256项

    把reg中的值置0.

    把原始的数据后添加r/8个0字节.

    While (数据未处理完)

    Begin

    把reg中的值左移一个字节,读入一个新的字节并置于reg的第0个byte<span sty

     

    展开全文
  • 已经实现了硬件的CRC7,CRC8,CRC16,CRC32运算,并且均进行了测试对比,计算结果完全正确,通过配置可以实现不同的CRC校验,我已经实现了如下的配置: ///////////////////////////////////////////////////////////...
  • [code="java"] import java.nio.MappedByteBuffer; ...import java.util.zip.CRC32; public static void main(String[] args){ try { //对文件进行crc校验 long begin = System.c...
  • CRC校验

    2017-01-20 14:18:30
    CRC校验简介 CRC的全称为Cyclic Redundancy Check,中文名称为循环冗余校验。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。 CRC原理简介及应用 CRC算法...
  • CRC32

    2018-12-26 14:52:31
    CRC校验实用程序库 在数据存储和数据通讯领域,为了保证数据的正确,就不得不采用检错的手段。在诸多检错手段中,CRC是最著名的一种。CRC的全称是循环冗余校验。 [1]  程序库特点编辑 检错能力极强,开销小,易于...
  • 文章目录目的CRC校验关键点参数模型计算方式CRC校验库源文件使用测试项目地址总结 目的 CRC即循环冗余校验码(Cyclic Redundancy Check):是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的...
  • CRC算法

    2016-08-17 12:56:00
    可是,我认识的嵌入式程序员中能真正掌握CRC算法的人却很少,平常在项目中见到的CRC的代码多数都是那种效率非常低下的实现方式。 其实,在网上有一篇介绍CRC 算法的非常好的文章,作者是Ross William
  • CRC校验代码整理

    千次阅读 2015-08-07 12:23:41
    CRC
  • crc 算法

    2010-07-31 01:11:00
    标准 根据应用环境与习惯的不同,CRC又可分为以下几种标准: ①CRC-12码; ②CRC-16码; ③CRC-CCITT码; ④CRC-32码。 CRC-12码通常用来传送6-bit字符串。 CRC-16及CRC-CCITT码则是用来传送8-bit字符串,其中CRC-...
  • 这样的状况一天可能要出现几次,硬盘是希捷500G,硬盘上的标签是2009年12月9日的,个人估计是硬盘出现了故障或是老化了,用HD Tune专业版V5.00检测硬盘并无坏道,健康栏内除“(C7)Ultra DMA CRC 错误计数”有...
  • CRC校验算法 STM32CRC

    万次阅读 2015-09-14 15:39:53
    写给嵌入式程序员的循环冗余校验(CRC)算法入门引导 前言 CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中,经常要用到CRC 算法对各种数据进行校验。因此,掌握基本的CRC算法应是...
  • crc校验详解

    千次阅读 2017-06-15 16:01:48
    一、crc校验是什么? CRC即循环冗余校验码(Cyclic Redundancy Check[1] ):是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能...
  • 在阅读Redis源码的时候,看到了两个文件:crc16.c、crc64.c。下面我抛砖引玉,简析一下原理。 CRC即循环冗余校验码,是信息系统中一种常见的检错码。大学课程中的“计算机网络”、“计算机组成”等课程中都有提及。...
  • crc校验

    2014-03-04 13:32:28
    CRC校验实用程序库 在数据存储和数据通讯领域,为了保证数据的正确,就不得不采用检错的手段。在诸多检错手段中,CRC是最著名的一种。CRC的全称是循环冗余校验,其特点是:检错能力极强,开销小,易于用编码器及检测...
  • CRC算法,动态存储

    2018-08-02 15:14:32
    CRC算法,使用VS开发环境使用C++语言进行编写控制台程序,通过与用户交互操作确定待校验码以及监督码序列,然后动态地给数组分配内存,并且真正实现长除法的除法运算,不仅仅是CRC算法的异或简单操作
  • CRC16 - CRC64 的碰撞测试

    千次阅读 2014-12-04 21:45:36
    CRC16 - CRC64 test results on 18.2M dataset...最近寻找一个key生成算法,md5的128bit对于我的内存来说太大了,十亿量级。找到这个东东,抽空试试看。先记录下 http://www.backplane.com/matt/crc64.html CRC16 -
  • CRC32使用

    千次阅读 2018-03-09 17:54:16
    1、用于校验 其特点是:检错能力极强...因而,在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT,ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CR...
  • crc322.c.zip

    2019-10-10 10:37:04
    CRC32无需查表生成,提升效率,节省内存使用空间,测试可用
  • 循环冗余校验(CRC)算法入门引导

    万次阅读 多人点赞 2012-08-19 12:42:34
    写给嵌入式程序员的循环冗余校验(CRC)算法入门引导 前言 CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中,经常要用到CRC 算法对各种数据进行校验。因此,掌握基本的CRC算法应是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,773
精华内容 15,109
热门标签
关键字:

内存crc