Adler-32

Adler-32是一种校验算法，由在1995年发明，是对的一种改进。与相同长度的循环冗余校验相比，它以可靠性换取速度（更倾向于后者）。Adler-32比更加可靠，比可靠性稍差。
 历史 
Adler-32校验和是广泛使用的zlib压缩库的一部分，因为两者都是由开发的。在rsync工具中使用了Adler-32的“旋转哈希”版本。

 算法 

Adler-32校验和是通过计算两个16位的校验和A和B，并将它们的位连为一个32位整数来获得的。A是流中所有字节的总和加1，而B是每个步骤中A的各个值的总和。
在Adler-32运行开始时，A被初始化为1，B为0。以模65521（小于216的最大质数）进行求和。字节以网络顺序存储（字节序），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

其中D是要计算校验和的字节串，n是D的长度。

 示例 

ASCII字符串“ Wikipedia ”的Adler-32校验和计算如下：
字符ASCII码 A B (显示为10进制)   W87       1 +  87 =  88      0 +  88 =   88   i105     88 + 105 = 193     88 + 193 =  281   k107    193 + 107 = 300    281 + 300 =  581   i105    300 + 105 = 405    581 + 405 =  986   p112    405 + 112 = 517    986 + 517 = 1503   e101    517 + 101 = 618   1503 + 618 = 2121   d100    618 + 100 = 718   2121 + 718 = 2839   i105    718 + 105 = 823   2839 + 823 = 3662   a97     823 +  97 = 920   3662 + 920 = 4582

 A =  920 =  0x398  (16-{zh-hans:进制; zh-hant:進位}-)
 B = 4582 = 0x11E6
 输出 = 0x11E6 << 16 + 0x398 = 0x11E60398

在这个例子中，取模运算没有效果，因为没有一个值达到65521。
 与Fletcher校验和的比较 

两种算法之间的第一个区别，是Adler-32和是以一个质数为模数计算的，而Fletcher和是以24-1、28-1或216-1为模（取决于所使用的位数）为模数计算的，它们都是复合数。使用质数使得Adler-32可以捕获到Fletcher无法检测到的某些字节组合中的差异。

第二个区别，也是对算法的速度影响最大的区别，是Adler和是在8位的字节上计算的，而不是16位的字上，导致循环迭代次数增加了一倍。 这使得对于16位字对齐数据，Adler-32校验和花的时间是Fletcher校验和的1.5到2倍。对于字节对齐的数据，Adler-32比正确实现的Fletcher的校验和（例如，HDF中的实现）要快。

 实现示例 

在C语言中，一个低效但直接的实现方式是：

const uint32_t MOD_ADLER = 65521;

uint32_t adler32(unsigned char *data, size_t len) 
/* 
    where data is the location of the data in physical memory and 
    len is the length of the data in bytes 
*/
{
    uint32_t a = 1, b = 0;
    size_t index;

    // Process each byte of the data in order
    for (index = 0; index < len; ++index)
    {
        a = (a + data[index]) % MOD_ADLER;
        b = (b + a) % MOD_ADLER;
    }

    return (b << 16) | a;
}
请参阅zlib源代码，了解更有效的实现，它需要对每个字节进行一次取数和两次加法，模数运算延后，并每隔几千个字节计算两次余数，这种技术最早是在1988年被发现用于Fletcher校验。也提供了类似的优化，增加了一个技巧，即推迟计算65536-65521中的“15”，这样模数运算就会变得更快：可以证明相当于简单的积累。

 优点和缺点 

 与标准CRC-32一样，Adler-32校验和很容易伪造，因此在防止故意修改方面是不安全的。
 在许多平台上，它都比CRC-32更快。
 Adler-32对于只有几百个字节的短消息方面有一个弱点，因为这类消息的校验和对32个可用位的覆盖率很低。

 弱点 
对于短消息来说，Adler-32是很弱的，因为总和A不会回绕（英语：Wrap，即整数溢出后的处理）。128字节消息的最大和是32640，低于取模操作所使用的值65521，这意味着大约有一半的输出空间未使用，并且使用部分内的分布也是不均匀的。延伸的解释可以在中找到，它规定流控制传输协议SCTP使用CRC32C而不是Adler-32。对于较小的增量更改，Adler-32也被证明变化很弱，并且对于从一个共同的前缀和连续的数字生成的字符串也很弱（例如由典型代码生成器自动生成的标签名）。

 参见 


 脚注 

 外部链接 

  – 规范，包含示例C代码
 ZLib – 在adler32.c中实现了Adler-32算法
 Chrome – 在adler32_simd.c中使用SIMD实现的Adler-32算法
  – 有关短消息弱点和SCTP相关更改的信息

Category:校验和算法