首页
论坛
课程
招聘
CRC-32的算法小议
2006-8-8 23:15 7132

CRC-32的算法小议

2006-8-8 23:15
7132
现在网络上广为流传的CRC32的实现代码,是基于little endian的,
幸运地是,X86CPU和Ethernet都是基于little endian的。
little endian从小头开始吃鸡蛋,将the most significant放在相对低位。

一块以little endian存放和传输方式的数据块(我当然说的是x86环境),
如何适应CRC32模型?
解决方法:
数据块的每一个字节内,相对低位是多项式码中的相对高位;
数据块的字节间,相对低位的字节是多项式码中的相对高位。

举个例子:
/*  C  */
char    String[]={a,b,c,d,e,f};

=
;  MASM
String   db   'a','b','c','d','e','f'

=
; 在x86环境中的内存分布
0x61    |   0x62   |  0x63    |  0x64   | 0x65    | 0x66
0110 0001 0110 0010  0110 0011 0110 0100 0110 0101 0110 0110
=
; 表示成多项式,!!!
1000 0110 0100 0110 1100 0110 0010 0110 1010 0110 0110 0110......
; 为什么我加省略号,后面还可能接有更多的字节。

为什么选择这种方法,(1)后面可以有更多的字节,而只需要简单地往这个队列添加;(2)方便实现,还有,跟贴吧!!!

CRC的本质是多项式的模2运算,如果你关心它运算的过程,你就知道它的各种可能的变体。

模2运算
模2运算的加法和减法的结果都是相同,可以用逻辑异或来表示;

模2加减运算的特点:每一位的结果和上位或下位无关。

模2除法的余数总比除数少1位。

模2运算没有进位和退位的概念。

模2除法的上商原则是:余数最高位为1,上1,余数最高位为0,上0.

这一结论可以推至比特位:
任何数与0x0000000异或,结果不变;
任何数与0xfffffff异或,结果为反,相当于not指令。

CRC_Table表
CRC16_Table
CRC_Table是一个元素数目为256,类型为unsigned short的一维数列
CRC32_Table
CRC_Table是一个元素数目为256,类型为unsigned int的一维数列

256=2^8,多项式的最高字节一共有8位

for(i=0;i<256;i++)   
{
    register = i;        /* the top byte of the polynominal */
   
    for(j=0;j<8;j++)      
/* the ordinal of bits in a byte: 7, 6, 5, ... */

    {
        if ( register & 1 )    /* dividable */
            register = ( register >> 1 ) ^ 0xEDB88320;
        else
            register >>= 1;
    }
   
    crc_table[i]=register;
}

char CRC_TABLE={y0,y1,y2,y3,y4,...,y255};
可以看作一个一对一的映射f(index)=y;
index是被除数,y是余数,映射关系是经过8次模2除法运算。

index = ( crc ^ char [n] ) & 0x000000ff;
crc = crc_table[index] ^ crc>>8;   

一次运算,指8次有8比特位参加的模2除法运算。

crc ^ char [n]   
本次运算的被除数,是上次运算的余数和char[n]的逻辑加

crc_table[index] ^ crc >> 8
最后的结果等于本次运算的结果异或上次运算的余数,
(余数需经过移位)


[2023春季班]《安卓高级研修班(网课)》月薪两万班招生中~

收藏
点赞0
打赏
分享
最新回复 (12)
雪    币: 10187
活跃值: 活跃值 (12955)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 活跃值 8 2006-8-9 14:39
2
0
谢谢tnttools的好文
我将帖移到这个版块,人气旺些。
雪    币: 2139
活跃值: 活跃值 (796)
能力值: ( LV9,RANK:850 )
在线值:
发帖
回帖
粉丝
wofan[OCN] 活跃值 21 2006-8-26 00:39
3
0
这样的好贴,为什么没有跟贴?我顶一下,别让它沉下去。
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
asmbOys 活跃值 2006-8-26 09:24
4
0
看了两遍,也有点收获,谢过!
雪    币: 3540
活跃值: 活跃值 (41)
能力值: (RANK:760 )
在线值:
发帖
回帖
粉丝
cnbragon 活跃值 18 2006-8-26 09:42
5
0
最初由 tnttools 发布
现在网络上广为流传的CRC32的实现代码,是基于little endian的,
幸运地是,X86CPU和Ethernet都是基于little endian的。
little endian从小头开始吃鸡蛋,将最不重要地放在最前面。

一块以little endian存放和传输方式的数据块(我当然说的是x86环境),
........


这不叫“最不重要”
the least significant bit这叫最低位
the most significant bit这叫最高位

也没什么最前面之说,这叫“最左边”(little endian)或者“最右边”(big endian)
the left-most bit position
the right-most bit position

这篇文章是你原创的么?
雪    币: 213
活跃值: 活跃值 (27)
能力值: ( LV13,RANK:380 )
在线值:
发帖
回帖
粉丝
tnttools 活跃值 9 2006-8-26 21:37
6
0
回应cnbragon - 请大家先弄清楚这些:
字节内的顺序,字节之间的顺序,字word之间的顺序

标题中的字word,
指在CPU环境下表示CPU处理和存储的单元。

(1)不是!!!比特位!!!

字节内的顺序,如cnbragon所说:
the least significant bit
the most significant bit

the left-most bit position
the right-most bit position

请cnbragon注意,little endian所描述的数据存储方式的单位不是比特位,而至少是字节或是字节的倍数,不要和CPU的移位指令弄混。

(2)
我所说的最重要,最不重要指的是英文原文
the most significant  and the least significant

后面特意没有加byte, word等名词,是因为在不同的语境下,
这些都有可能。

    BYTE
UNICODE
按Little Endian存储如果是0xAA, 0xBB,
那么Big Endian存储就是0xBB, 0xAA

    WORD
这里的WORD,指16比特位
按little endian存储如果是0xAA, 0xBB, 0xCC, 0xDD
那么按Big Endian存储就是0xCC, 0xDD, 0xAA, 0xBB

(3)

关于最前面和最后面

一个队列,你说最前面和最后面,没有什么不妥,
说最左边和最右边也没有什么错。

雪    币: 213
活跃值: 活跃值 (27)
能力值: ( LV13,RANK:380 )
在线值:
发帖
回帖
粉丝
tnttools 活跃值 9 2006-8-26 21:48
7
0
  这篇文章被看雪老大列为精华,我也觉得意外。
因为这只是我学习算法过程中的一个小小的思考过程,文章太短了,
但我觉得如果你真正想看懂网上CRC32代码的实现,这篇文章绝对有帮助。

  当时在看CRC32代码实现时,不想作个copypaster,反复思考:
I.为什么要用表来实现
解决方法:
你既可以静态填表,也可以动态生成那个表。

II.为什么要这样写代码,以字节为单位,为什么要移8位

  所有思考的结果就汇成了这样一篇小文章,cnbragon前辈说它不是原创,也对:我生来就什么都不知道,都是后天学习的结果,全部都是COPY|paste到脑袋中的。

  这篇文章被看雪老大列为精华,我再次表示意外。
雪    币: 3540
活跃值: 活跃值 (41)
能力值: (RANK:760 )
在线值:
发帖
回帖
粉丝
cnbragon 活跃值 18 2006-8-26 22:24
8
0


我不是前辈。这篇文章加为精华实属正常,没有必要意外,我也替你感到高兴

(1)、(2)说话不要这么肯定,建议你看看标准文档后再来反驳:
little-endian

Describes a computer architecture in which, within a given 16- or 32-bit word, bytes at lower addresses have lower significance (the word is stored ‘little-end-first’). The PDP-11 and VAX families of computers and Intel microprocessors and a lot of communications and networking hardware are little-endian. See big-endian, middle-endian, NUXI problem. The term is sometimes used to describe the ordering of units other than bytes; most often, bits within a byte.

请你注意最后一句话。再说,没说你little-endian理解有错误,只是指出你专业英文翻译中的不当之处:the most significant  and the least significant翻译成最重要和最不重要有点贻笑大方了。
(3)关于最前面和最后面,这种说法是不准确的,只能说你考虑的不是很全面
假如在内存中有如下的数据存储形式:
0x00405000 ab cd ef 01 23 45

人家可以理解成从ab到45的方向是由后到前或者理解成从45到ab的方向是由后到前,必须指出是左还是右才不易引起混淆
在NIST的fips 180-2中,有这样一段话:
Throughout this specification, the “big-endian” convention is used when expressing
both 32- and 64-bit words, so that within each word, the most significant bit is stored
in the left-most bit position.

这些知识都是已经有标准的定论的基本概念,根本不需要做过多的讨论。当然如果你愿意按照自己的理解也无可厚非,只是希望你能多读读一些标准的东西,再对照自己的想法,以达到理解上没有偏差,做学问应当如此。
雪    币: 213
活跃值: 活跃值 (27)
能力值: ( LV13,RANK:380 )
在线值:
发帖
回帖
粉丝
tnttools 活跃值 9 2006-8-26 22:35
9
0
已看,你正确,我失误。多谢!!!

我发表文章的原因之一:就是希望有人指出我的错误。

孟子问“独乐乐,与人乐乐,孰乐"
答:与人乐乐,乐。
雪    币: 2139
活跃值: 活跃值 (796)
能力值: ( LV9,RANK:850 )
在线值:
发帖
回帖
粉丝
wofan[OCN] 活跃值 21 2006-8-27 01:17
10
0
我不顶,大家都不说话,哈……
雪    币: 203
活跃值: 活跃值 (15)
能力值: ( LV9,RANK:610 )
在线值:
发帖
回帖
粉丝
网游难民 活跃值 15 2006-8-27 21:08
11
0
好文章啊~~
楼主能不能把其它的加密算法也总结下贴出来弄个加密算法合集??
人气肯定旺~~也有利与偶等菜鸟学习~~多谢拉~
雪    币: 200
活跃值: 活跃值 (197)
能力值: ( LV12,RANK:2670 )
在线值:
发帖
回帖
粉丝
KuNgBiM 活跃值 66 2006-8-28 09:30
12
0
学习.....
雪    币: 215
活跃值: 活跃值 (15)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
一叶飘红 活跃值 2006-8-28 20:04
13
0
最初由 KuNgBiM 发布
学习.....
游客
登录 | 注册 方可回帖
返回