Adler32算法.doc

文档介绍：1 Adler-32算法
Adler-32是Mark Adler提出的一种校验和算法,与同等长度的CRC校验算法相比,它
具有更好的执行效率。更低的不能检测出错误的概率。
Adler-32通过求解两个16位的数值A、B实现,并将结果连结成一个32位整数。其中
A为所有字节的和,B为每次A数组的和。在算法开始时,A=1,B=0,和对65521取模
(2的16次方范围内最大的素数)。字节存储为大字节序。B占用最高位。
其算法描述如下:
A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
= n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

Adler-32(D) = B × 65536 + A

对于无符号long型整数可以推迟到5552字节后,因此模运算时间可以忽略。如果字节
为a,b,c,那么sum为3a + 2b + c + 3。素数65521避免了任意两个字节发生改变的
错误。
A初始化为1而不是0,让字符总数成为B的一部分,所以字符长度校验不会分离。

2 例子
Character ASCII code A B
(shown as base 10)
W 87 1 + 87 = 88 0 + 88 = 88
i 105 88 + 105 = 193 88 + 193 = 281
k 107 193 + 107 = 300 281 + 300 = 581
i 105 300 + 105 = 405 581 + 405 = 986
p 112 405 + 112 = 517 986 + 517 = 1503
e 101 517 + 101 = 618 1503 + 618 = 2121
d 100 618 + 100 = 718 2121 + 718 = 2839
i 105 718 + 105 = 823 2839 + 823 = 3662
a 97 823 + 97 = 920 3662 + 920 = 4582

A = 920 = 398 hex (base 16)
B = 4582 = 11E6 hex

Output = 300286872 = 11E60398 hex

4 效率低下直观的算法
The following C putes the Adler-32 checksum of a data buffer.
It is written for clarity, not for speed. The sample code is in the
ANSI C programming language. Non C users may find it easier to read
with these hints:
#define BASE 65521 /* largest prime smaller than 65536 */
/*
Up