Adler-32

✍ dations ◷ 2025-02-23 10:10:38 #校验和算法

Adler-32是一种校验算法,由马克·阿德勒(英语:Mark Adler)在1995年发明,是对Fletcher校验(英语:Fletcher's checksum)的一种改进。与相同长度的循环冗余校验相比,它以可靠性换取速度(更倾向于后者)。Adler-32比Fletcher-16(英语:Fletcher-16)更加可靠,比Fletcher-32(英语:Fletcher-32)可靠性稍差。

Adler-32校验和是广泛使用的zlib压缩库的一部分,因为两者都是由马克·阿德勒(英语:Mark Adler)开发的。在rsync工具中使用了Adler-32的“旋转哈希”版本。

Adler-32校验和是通过计算两个16位的校验和和,并将它们的位连为一个32位整数来获得的。是流中所有字节的总和加1,而是每个步骤中的各个值的总和。在Adler-32运行开始时,被初始化为1,为0。以模65521(小于216的最大质数)进行求和。字节以网络顺序存储(字节序),占据最高的两个字节。

该函数可以表示为

 = 1 + 1 + 2 + ... +  (mod 65521) = (1 + 1) + (1 + 1 + 2) + ... + (1 + 1 + 2 + ... + ) (mod 65521)  = ×1 + (−1)×2 + (−2)×3 + ... +  +  (mod 65521)() =  × 65536 + 

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

ASCII字符串“ Wikipedia ”的Adler-32校验和计算如下:

A =  920 =  0x398  (16进制)B = 4582 = 0x11E6输出 = 0x11E6 << 16 + 0x398 = 0x11E60398

在这个例子中,取模运算没有效果,因为没有一个值达到65521。

两种算法之间的第一个区别,是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) % MOD_ADLER;        b = (b + a) % MOD_ADLER;    }        return (b << 16) | a;}

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

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

相关

  • Gmelin盖墨林数据库是一个收录无机化学和金属有机化学化合物和反应的化学数据库。它的前身是德国化学家利奥波德·盖墨林(Leopold Gmelin)于1817年编撰的《盖墨林无机化学手册》(Gmel
  • 查理四世查理四世(美男子)(Charles IV le Bel,1294年6月19日-1328年2月1日)卡佩王朝的法兰西国王(1322年—1328年在位)和纳瓦拉国王(称卡洛斯一世,1322年起)。查理四世是法兰西国王腓力四世(美男
  • 阿片样肽阿片类药物(Opioid)是具有吗啡作用的化学物质,主要用途是镇痛。阿片类药物通过存在于中枢神经系统和消化系统的阿片类受体(Opioid receptor)起作用。这些阿片类受体能引发有益的
  • 春香传《春香传》(춘향전)是朝鲜半岛著名的爱情故事,数百年来一直都在当地乃至东亚地区流传。春香歌是朝鲜半岛传统说唱艺术盘索里的代表节目之一,也曾多次改编成电影。中国亦曾把此剧
  • 华富里府华富里府(泰语:จังหวัดลพบุรี,皇家转写:Changwat Lop Buri,泰语发音:)是泰国中部之一个府。华富里府的行政区的行政区共分为11个县(Amphoe);再分成124个区(Tambon);最后细分
  • 詹姆斯·兰克福德詹姆斯·保罗·兰克福德(英语:James Paul Lankford;1968年3月4日-),是一位美国共和党政治人物,自2015年成为奥克拉荷马州联邦参议院议员。此前他曾是美国众议院2011年至2015年期间
  • 维尔京群岛维尔京群岛国家公园(英语:Virgin Islands National Park)是美国的一处国家公园,公园的大部分地区位于圣约翰岛,此外还包括了一些邻近岛屿。维尔京群岛国家公园是一个浮潜圣地,此外
  • 善导寺 (台北市)坐标:25°02′44″N 121°31′29″E / 25.04556°N 121.52472°E / 25.04556; 121.52472 善导寺(英语:Shandao Temple),全名为财团法人台北市净土宗善导寺,位于台湾台北市忠孝东路
  • 彼得·克鲁格彼得·克鲁格(Peter Crüger)是一位德国数学家、天文学家暨博学家,也是约翰·赫维留的老师。在发表的拉丁文献中,他的常用名Krüger被拉丁化并拼写成Crüger)(作为家族姓氏,Krüger
  • 穆拉维约夫-阿穆尔斯基半岛穆拉维约夫-阿穆尔斯基半岛(俄语:Полуостров Муравьёва-Амурского,罗马化:Poluostrov Muravyova-Amurskogo)是俄罗斯彼得大帝湾内的一个半岛,将此湾