首页
论坛
课程
招聘
[原创]小议Fletcher's checksum
2006-9-20 19:58 9161

[原创]小议Fletcher's checksum

2006-9-20 19:58
9161
将一些标准或实现语焉不详的地方或难于理解的地方说清楚,不希望有任何死角。
欢迎大牛指正。

By:TnTTools

        :::参数集合:::
         Parameter Set

利用参数集合来描述具体的算法,是我从Ross处得到的灵感。
http://www.ross.net/crc/

Name
Chksum(LengthA+LengthB)                  
Block
InitA, InitB
Modulo(Base)

Name
算法的名字,一般是约定俗成的,可不是我随意起的。
                  
Block指处理单元(块)的长度。
8-bit可用于处理ANSI字符,16-bit可用于处理Unicode字符。
标准中8-bit Fletcher, 16-bit Fletcher
就是指此参数。

Chksum指校验和的长度。
A和B的长度一般相同:LengthA=LengthB=Chksum/2。
Adler-8, Adler-16, Adler-32
其中的数字8,16,32就是指此参数。

InitA,InitB
A和B的初始化值

Modulo(Base)
模,Base见于adler32.c in zlib
一般地Fletcher's checksum的模是65535;
而Adler's checksum的模变为65521.

  Name: Adler-32
  ChkSum: 32(LengthA,LengthB: 16)
  InitB,InitA: 0x0000, 0x0001
  Modulo: 65521
            

                :::数学原理:::

Fletcher's 的数学原理非常简单:和,数列的和。

; original

A = Sum.
B = Sum of sum.

; More practical

A = InitA + D[1] + D[2] + D[3] + ... + D[n]
B = InitB + nInitA + nD[1] + (n-1)D[2] + (n-2)D[3] + ... + D[n]

        :::实现:::

RFC1146中的实现太过简略,没有实用价值。

实用的代码,可参见
Fletcher's
ttp://en.wikipedia.org/wiki/Fletcher%27s_checksum
Adler's
(1)
adler32.c
(2)
ttp://en.wikipedia.org/wiki/Adler-32

外循环遍历字符数列,内循环实现不溢出条件下的具体加法操作。

下面说明一下360和5552这两个数字的来历。

            
              :::360:::

    360是...算法中A和B都不会溢出时内循环最大次数N的最大整数值。
Block=16,Chksum=32, Modulo=65535

   
    <h>推导过程</h>

B和A执行相同次数的加法操作,B明显比A大
只要B不溢出,A也不会溢出。

B = InitB + N*InitA + N*D[1]+(N-1)*D[2]+(N-2)*D[3]+...+D[N]
MaxD[x]=0x0000FFFF,
MaxInitA=Modulo-1=0x0000FFFF
MaxInitB=Modulo-1=0x0000FFFF

B(max) = 0x0000FFFF * N * (N+1)/2 + (N+1)* 0x0000FFFF
B(max) <= 0xFFFFFFFF

解不等方程式:
0xFFFFFFFF >= 0x0000FFFF * N * (N+1)/2 + (N+1)* 0x0000FFFF
<=>
N*N + 3N - (65537-1)*2 <= 0
N*N + 3N - 131072 <= 0
解得:
-363.54 <= N <= +360.54       

              :::5552:::

    5552是...算法中A和B都不会溢出时内循环最大次数N的最大整数值。
Block=8, Chksum=32, Modulo=65535

   
    <h>推导过程</h>

B = InitB + N*InitA + N*D[1]+(N-1)*D[2]+(N-2)*D[3]+...+D[N]
MaxD[x]=0x000000FF
MaxInitA=Modulo-1=0x0000FFFF
MaxInitB=Modulo-1=0x0000FFFF

B(max) = 0x000000FF * N * (N+1)/2 + (N+1)* 0x0000FFFF
B(max) <= 0xFFFFFFFF

解不等方程式:
0xFFFFFFFF >= 0x000000FF * N * (N+1)/2 + (N+1)* 0x0000FFFF
<=>
N*N + (1+0x202)N <= ( 0x1010101 - 0x101 )*2
N*N + 515*N <= 33685504
解得:       
-6067.13 <= N <= + 5552.13

              ::组合::

  如果有两个Fltecher's checksum,如何组合它们。相关的数学原理为

                                             
A1 = InitA + P[1] + P[2] + ... + P[m]
B1 = InitB + mInitA + mP[1] + (m-1)P[2] + ... + P[m]

A2 = InitA + Q[1] + Q[2] + ... + Q[n]
B2 = InitB + nInitA + nQ[1] + (n-1)Q[2] + ... + Q[n]

A = InitA + P[1] + ... + P[m] + Q[1] + ... + Q[n]      
  = A1 + A2 - InitA
  
B = InitB + (m+n)InitA + (m+n)P[1] + ... + (1+n)P[m] + nQ[1] + ... + Q[n]
  = B1 + B2 + n*(A1 - InitA) - InitB
                       
    adler32的实现代码可参见adler32_combine() in adler32.c in zlib 1.2.3.

看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞0
打赏
分享
最新回复 (4)
雪    币: 1613
活跃值: 活跃值 (33)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
北极星2003 活跃值 25 2006-9-21 16:24
2
0
总体来说,文章的目标写的并不清楚
作为一个读者来说,我如果不知道这是个什么东西,不太愿意看一些原理性的东西,实话实说,别介意

如果有时间的话,可以改进下,把目标写的明确写


一般地Fletcher's checksum的模是65535;
而Adler's checksum的模变为65521.

不知道这两个到底是什么东西,校验??


Fletcher's 的数学原理非常简单:和,数列的和。

退一步说,最多也属于级数求和
雪    币: 213
活跃值: 活跃值 (26)
能力值: ( LV13,RANK:380 )
在线值:
发帖
回帖
粉丝
tnttools 活跃值 9 2006-9-21 22:35
3
0
无它,纯粹的个人的算法解惑笔记,
发表在论坛上,因为很少有人涉及――大多数人不感兴趣――只是让有心的后来者理解的更快一些。
雪    币: 1018
活跃值: 活跃值 (9934)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 活跃值 8 2006-9-22 21:00
4
0
最初由 tnttools 发布
无它,纯粹的个人的算法解惑笔记,
发表在论坛上,因为很少有人涉及――大多数人不感兴趣――只是让有心的后来者理解的更快一些。


概念性的东西如果稍介绍一下就好了。
雪    币: 0
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
AlphaOF 活跃值 2020-4-13 17:52
5
0
14年之后的我看完瑟瑟发抖,我是想知道alder32是如何保证文件被篡改的,浏览完貌似没有得到答案。
游客
登录 | 注册 方可回帖
返回