探究CRC32算法实现原理-why table-driven implemention

2023-12-02 07:58
文章标签 算法 实现 原理 table 探究 crc32 driven implemention

本文主要是介绍探究CRC32算法实现原理-why table-driven implemention，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

探究CRC32算法实现原理-why table-driven implemention

Preface

基于不重造轮子的原则，本文尽量不涉及网络上遍地都是的资料。

What's CRC ?

简而言之，CRC是一个数值。该数值被用于校验数据的正确性。CRC数值简单地说就是通过让你需要做
处理的数据除以一个常数而得到的余数。当你得到这个数值后你可以将这个数值附加到你的数据后，
当数据被传送到其他地方后，取出原始数据(可能在传送过程中被破坏)与附加的CRC数值，然后将这里
的原始数据除以之前那个常数(约定好的)然后得到新的CRC值。比较两个CRC值是否相等即可确认你的
数据是否在传送过程中出现错误。

那么，如何让你的数据除以一个常数？方法是对你的数据进行必要的编码处理，逐字节处理成数字。
那么这个常数是什么？你不必关注它是什么，也不需要关注它是如何获得的。当你真的要动手写一个
CRC的实现算法时，我可以告诉你，CRC的理论学家会告诉你。不同长度的常数对应着不同的CRC实现算法。
当这个常数为32位时，也就是这里所说的CRC32。

以上内容你不必全部理解，因为你需要查阅其他资料来获取CRC完整的理论介绍。

The mathematics behind CRC ?

很多教科书会把CRC与多项式关联起来。这里的多项式指的是系数为0或1的式子，例如：
a0 + a1*x + a2*x^2 + ... + an*x^n。其中a0, a1, ..., an要么为0要么为1。我们并不关注x取什么值。
(如果你要关注，你可以简单地认为x为2) 这里把a0, a1, ..., an的值取出来排列起来，就可以表示比特
流。例如 1 + x + x^3所表示的比特流就为：1101。部分资料会将这个顺序颠倒，这个很正常。

什么是生成多项式？

所谓的生成多项式，就是上面我所说的常数。注意，在这里，一个多项式就表示了一个比特流，也就是一堆
1、0，组合起来最终就是一个数值。例如CRC32算法中，这个生成多项式为：
c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32。
其对应的数字就为：11101101101110001000001100100000(x^32在实际计算时隐含给出，因此这里没有包含它
的系数)，也就是0xEDB88320(多项式对应的数字可能颠倒，颠倒后得到的是0x04C11DB7，其实也是正确的)。

由此可以看出，CRC值也可以看成我们的数据除以一个生成多项式而得到的余数。

如何做这个除法？

套用大部分教科书给出的计算方法，因为任何数据都可以被处理成纯数字，因此，在某种程度上说，我们可以
直接开始这个除法。尽管事实上这并不是标准的除法。例如，我们的数据为1101011011(方便起见我直接给二进制
表示了，从这里也可以看出，CRC是按bit进行计算的)，给定的生成多项式(对应的值)为10011。通常的教科书
会告诉我们在进行这个除法前，会把我们的数据左移几位(生成多项式位数-1位)，从而可以容纳将来计算得到
的CRC值(我上面所说的将CRC值附加到原始数据后)。但是为什么要这样做？我也不知道。(不知道的东西不能含糊
而过)那么，除法就为：
            1100001010
       _______________
10011 ) 11010110110000 附加了几个零的新数据
        10011......... 这里的减法(希望你不至于忘掉小学算术)是一个异或操作
        -----.........
         10011........
         10011........
         -----........
          00001....... 逐bit计算
          00000.......
          -----.......
           00010......
           00000......
           -----......
            00101.....
            00000.....
            -----.....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = 这个余数也就是所谓的CRC值，通常又被称为校验值。

希望进行到这里，你可以获取更多关于CRC的感性认识。而我们所要做的，也就是实现一个CRC的计算算法。
说白了，就是提供一个程序，给定一段数据，以及一个生成多项式(对于CRC32算法而言该值固定)，然后
计算得出上面的1110余数。

The simplest algorithm.

最简单的实现算法，是一种模拟算法。我们模拟上面的除法过程，遵从网上一份比较全面的资料，我们设定
一个变量register。我们逐bit地将我们的数据放到register中。然后判断register最高位是否为1，如果是
则与生成多项式异或操作，否则继续处理。这个过程简单地模拟了上述除法过程：

 

///
/// The simplest CRC implement algorithm.
///
/*
   Load the register with zero bits.
   Augment the message by appending W zero bits to the end of it.
   While (more message bits)
      Begin
      Shift the register left by one bit, reading the next bit of the
         augmented message into register bit position 0.
      If (a 1 bit popped out of the register during step 3)
         Register = Register XOR Poly.
      End
   The register now contains the remainder.
*/

#include  < stdio.h >

#define  POLY 0x13

int  main()
 {
 /// the data 
 unsigned short data = 0x035b;
 /// load the register with zero bits
 unsigned short regi = 0x0000;
 /// augment the data by appending W(4) zero bits to the end of it.
 data <<= 4;

 /// we do it bit after bit
 for( int cur_bit = 15; cur_bit >= 0; -- cur_bit )
 {
  /// test the highest bit which will be poped later.
  /// in fact, the 5th bit from right is the hightest bit here
  if( ( ( regi >> 4 ) & 0x0001 ) == 0x1 )
  {
   regi = regi ^ POLY;
  }
  /// shift the register
  regi <<= 1;
  /// reading the next bit of the augmented data
  unsigned short tmp = ( data >> cur_bit ) & 0x0001;
  regi |= tmp;

 }

 /// and now, register contains the remainder which is also called CRC value.

 return 0;
}


better algorithm ?

很多时候这种让人容易理解的算法都不会被实际用到。这种逐bit操作的算法实在很慢。你可能知道
一般的CRC32算法都是一种基于表(table-driven)的算法。但是你可能不知道这个表是如何来的。

一种改善这种bit after bit的方法就是将这个bit扩大，例如典型的做法就是换成byte。这里我要详细地叙述下
上面那种算法的过程：

我们每次会先检查register的最高位是否为1，如果为1，则将生成多项式(所谓的Poly)与register进行异或操作。
然后，将register左移一位，也就舍弃了最高位。然后将我们的数据拿一bit出来放到register的最低位。

也就是说，register中的某一位的值会决定后面几位的值。如果将register最高字节每一bit编码为：
t7 t6 t5 t4 t3 t2 t1 t0。那么，t7会决定t6-t0的值(如果为1)，t6会决定t5-t0的值，依次类推。但是，无论谁
决定谁的值，当上面那个算法迭代一个字节后(8bits)，t7-t0都会被丢弃(whatever you do)。唯一留下来的东西，
就是对这个字节以后字节的影响。

那么，如果我们可以直接获取这个影响，我们就可以byte after byte地处理，而不是bit after bit。如何获取这个
影响呢？这个影响又是什么呢？这个影响就对应着我们的table-driven CRC算法中的表元素！

但是，为什么我们逐bit进行计算的过程为什么可以简化为一步操作？事实上，我们没有简化这个操作。一种用于教学
的算法，是实时地计算这个影响值：

 

///
/// The table-driven CRC implement algorithm part 1.
///
/*
  While (augmented message is not exhausted)
      Begin
      Examine the top byte of the register
      Calculate the control byte from the top byte of the register
      Sum all the Polys at various offsets that are to be XORed into
         the register in accordance with the control byte
      Shift the register left by one byte, reading a new message byte
         into the rightmost byte of the register
      XOR the summed polys to the register
      End
*/

#include  < stdio.h >
#include  < stdlib.h >
#include  < memory.h >

#define  POLY 0x04C11DB7L

int  main()
 {
 /// the data 
 unsigned long data = 0x1011035b;
 /// load the register with the data
 unsigned long regi = 0;
 /// allocate memory to contain the AUGMENTED data (added some zeros)
 unsigned char p[8];
 /// copy data
 memset( p, 0, 8 );
 memcpy( p, &data, 4 );
 
 /// because data contains 4 bytes
 for( int i = 0; i < 8; ++ i )
 {
  /// get the top byte of the register
  unsigned char top_byte = (unsigned char)( ( regi >> 24 ) & 0xff );
  /// sum all the polys at various offsets 
  unsigned long sum_poly = top_byte << 24;
  for( int j = 0; j < 8; ++ j )
  {
   /// check the top bit
   if( ( sum_poly >> 31 ) != 0 )
   {
    /// TODO : understand why '<<' first
    sum_poly = ( sum_poly << 1 ) ^ POLY;
   }
   else
   {
    sum_poly <<= 1;
   }
  }
  /// shift the register left by on byte, reading a new 
  regi = ( ( regi << 8 ) | p[i] );
  /// xor the summed polys to the register
  regi ^= sum_poly;
 }

 /// and now, register contains the remainder which is also called CRC value.
 
 return 0;
}
其中：

 

/// sum all the polys at various offsets 
  unsigned  long  sum_poly  =  top_byte  <<   24 ;
   for (  int  j  =   0 ; j  <   8 ;  ++  j )
   {
   /// check the top bit
   if( ( sum_poly >> 31 ) != 0 )
   {
    /// TODO : understand why '<<' first
    sum_poly = ( sum_poly << 1 ) ^ POLY;
   }
   else
   {
    sum_poly <<= 1;
   }
  }
  
就是用于计算这个影响值的。事实上，table-driven CRC算法中的那个表就是通过这段代码生成的(排除其他一些细节)。
你可能并不是很理解，这里我建议你忽略各种细节(更多的细节见参考资料)。你所需要知道的是，我们将8次逐bit的操
作合并到了一次byte操作中。而这个byte操作，就是8次bit操作的合操作(上面提到的影响值)。这个byte操作其实就是
一个数值，也就是table-driven CRC算法中那个表的一个元素。不同序列的bit操作其实对应着不同的unsigned char
值，因此那个table有256个元素。

 

show me where the table is :

如上所说，上面的算法很容易地就可以引进一个表：


进一步简化：

上述算法一个典型特征是会在我们的数据后面添加若干0。这样做其他做了很多没用的计算。一种简化做法就是将这些
没用的计算合并到其他计算中。其实这都是一些位操作的技巧：

///
/// The table-driven CRC implement algorithm part 2.
///
/*
  While (augmented message is not exhausted)
      Begin
      Examine the top byte of the register
      Calculate the control byte from the top byte of the register
      Sum all the Polys at various offsets that are to be XORed into
         the register in accordance with the control byte
      Shift the register left by one byte, reading a new message byte
         into the rightmost byte of the register
      XOR the summed polys to the register
      End
*/

#include  < stdio.h >
#include  < stdlib.h >
#include  < memory.h >

#define  POLY 0x04C11DB7L

unsigned  long  get_sum_poly( unsigned  char  top_byte )
 {
 /// sum all the polys at various offsets 
 unsigned long sum_poly = top_byte << 24;
 for( int j = 0; j < 8; ++ j )
 {
  /// check the top bit
  if( ( sum_poly >> 31 ) != 0 )
  {
   /// TODO : understand why '<<' first
   sum_poly = ( sum_poly << 1 ) ^ POLY;
  }
  else
  {
   sum_poly <<= 1;
  }
 }

 return sum_poly;
}

void create_table( unsigned long *table )
{
 for( int i = 0; i < 256; ++ i )
 {
  table[i] = get_sum_poly( (unsigned char) i );
 }
}

int main()
{
 /// the data 
 unsigned long data = 0x1011035b;
 /// load the register with the data
 unsigned long regi = 0;
 /// allocate memory to contain the AUGMENTED data (added some zeros)
 unsigned char p[8];
 /// copy data
 memset( p, 0, 8 );
 memcpy( p, &data, 4 );

 /// the table
 unsigned long table[256];
 /// create the table
 create_table( table );

 /// because data contains 4 bytes
 for( int i = 0; i < 8; ++ i )
 {
  /// get the top byte of the register
  unsigned char top_byte = (unsigned char)( ( regi >> 24 ) & 0xff );
  /// shift the register left by on byte, reading a new 
  regi = ( ( regi << 8 ) | p[i] );
  /// xor the summed polys to the register
  regi ^= table[top_byte];
 }

 /// and now, register contains the remainder which is also called CRC value.
 
 return 0;
}
 

 

讨厌的附加0

以上算法有个很大的特征就是要为我们的数据附加很多0。附加0后其实也附加了很多无用的操作。我们要将这些
讨厌的0去掉：

 

int  main()
 {
 /// the data 
 unsigned long data = 0x1011035b;
 /// load the register with the data
 unsigned long regi = 0;
 /// allocate memory to contain the data
 unsigned char p[4];
 /// copy data
 memcpy( p, &data, 4 );

 /// the table
 unsigned long table[256];
 /// create the table
 create_table( table );

 /// because data contains 4 bytes
 for( int i = 0; i < 4; ++ i )
 {
  regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ];
 }

 /// and now, register contains the remainder which is also called CRC value.
 
 return 0;
}


关键的一句regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ]; 简化了很多没用的操作。


In practice :

似乎一切被我说的很简单。我想只是因为我没说清楚。我尽量让你注意到事情的重点。我们进行到这里，似乎
我们立马就可以写出自己的CRC32算法并用于实践。但是你很快就会发现，事情并不如你想像的那么简单。

在实际处理时，很多数据的bit会进行一种颠倒操作，例如1010会被颠倒为0101。出现这样的情况是因为某些硬件
在实现CRC算法时，采用了这种(丑陋的)习惯。有些软件实现CRC算法时，也延用了这个习惯。

另外，关于register的初始值问题，有些CRC算法会初始化为0xffffffff。以下给出一个会进行bit颠倒的算法，
该算法可以直接输出table-driven中的表：

 

///
/// The table-driven CRC implement algorithm part 4.
///
/// Donot need augment W/8 zero bytes.
///
#include  < stdio.h >
#include  < stdlib.h >
#include  < memory.h >

#define  POLY 0x04C11DB7L

#define  BITMASK(X) (1L << (X))

unsigned  long  refelect( unsigned  long  v,  int  b )
 {
 int   i;
 unsigned long  t = v;
 for( i = 0; i < b; ++ i )
 {
  if( t & 1L )
   v |=  BITMASK( (b-1)-i );
  else
   v &= ~BITMASK( (b-1)-i );
  t >>= 1;
 }

 return v;
}

/// i'll try to write a correct algorithm
unsigned  long  get_sum_poly( unsigned  char   byte  )
 {
 byte = (unsigned long) refelect( byte, 8 );
 unsigned long sum_poly = byte << 24;

 for( int i = 0; i < 8; ++ i )
 {
  /// check the top bit
  if( ( sum_poly >> 31 ) != 0 )
  {
   /// TODO : understand why '<<' first
   sum_poly = ( sum_poly << 1 ) ^ POLY;
  }
  else
  {
   sum_poly <<= 1;
  }
 }

 sum_poly = refelect( sum_poly, 32 );
 return sum_poly;
}

void create_table( unsigned long *table )
{
 for( int i = 0; i <= 255; ++ i )
 {
  table[i] = get_sum_poly( (unsigned char) i );
 }
}

void output_table( const unsigned long *table )
{
 FILE *fp = fopen( "table.txt", "w" );
 
 for( int y = 0; y < 64; ++ y )
 {
  fprintf( fp, "0x%08lXL,/t0x%08lXL,/t0x%08lXL,/t0x%08lXL, /n", 
   table[ y * 4 + 0], 
   table[ y * 4 + 1], 
   table[ y * 4 + 2], 
   table[ y * 4 + 3] );
 }

 fclose( fp );
}

int main()
{
 /// the table
 unsigned long table[256];
 /// the data 
 unsigned long data = 0x1011035b;
 /// load the register with the data
 unsigned long regi = 0;
 /// allocate memory to contain the data
 unsigned char p[4];
 /// copy data
 memcpy( p, &data, 4 );
 /// create the table
 create_table( table );
 /// output the table
 output_table( table );

 /// because data contains 4 bytes
 for( int i = 0; i < 4; ++ i )
 {
  regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ];
 }

 /// and now, register contains the remainder which is also called CRC value.

 return 0;
}
Please FORGIVE me

 

我想我并没有将整个过程彻底地讲清楚。但是我希望你能明白大致的原理。关于table-driven中那个神奇的表的来历，
关于CRC32算法的推导过程等等之类。


本文代码下载： http://www.cppblog.com/Files/kevinlynx/CRC%20Implement.rar

参考资料：
http://www34.brinkster.com/dizzyk/math-crc.asp
http://www.greenend.org.uk/rjk/2004/crc.html
http://www.ross.net/crc/crcpaper.html

 

 

摘自：http://www.cppblog.com/kevinlynx/archive/2008/04/01/45952.html

这篇关于探究CRC32算法实现原理-why table-driven implemention的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/444538。

相关文章

Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...
SpringBoot+EasyExcel实现自定义复杂样式导入导出

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定，动态列2、动态下拉3、自定义锁定行/列，添加密码4、合并
阅读更多...
mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Qt使用QSqlDatabase连接MySQL实现增删改查功能

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...
Python中将嵌套列表扁平化的多种实现方法

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表（即列表中包含列表）转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert
阅读更多...
Python使用pip工具实现包自动更新的多种方法

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2