Adler-32是一種校驗算法，由馬克·阿德勒在1995年發明[1]，是對Fletcher校驗的一種改進。與相同長度的循環冗餘校驗相比，它以可靠性換取速度（更傾向於後者）。Adler-32比Fletcher-16更加可靠，比Fletcher-32可靠性稍差。[2]
 | 此條目需要補充更多來源。 (2020年6月12日) |
歷史
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進制) | |||||||||||
| W | 87 | 88 | 88 | ||||||||
| i | 105 | 193 | 281 | ||||||||
| k | 107 | 300 | 581 | ||||||||
| i | 105 | 405 | 986 | ||||||||
| p | 112 | 517 | 1503 | ||||||||
| e | 101 | 618 | 2121 | ||||||||
| d | 100 | 718 | 2839 | ||||||||
| i | 105 | 823 | 3662 | ||||||||
| a | 97 | 920 | 4582 | ||||||||
A = 920 = 0x398 (16進位) 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校驗。js-adler32也提供了類似的優化，增加了一個技巧，即推遲計算65536-65521中的「15」，這樣模數運算就會變得更快：可以證明((a >> 16) * 15 + (a & 65535)) % 65521相當於簡單的積累。[3]
優點和缺點
弱點
對於短消息來說，Adler-32是很弱的，因為總和A不會迴繞（英語：Wrap，即整數溢出後的處理）。128字節消息的最大和是32640，低於取模操作所使用的值65521，這意味着大約有一半的輸出空間未使用，並且使用部分內的分布也是不均勻的。延伸的解釋可以在RFC 3309中找到，它規定流控制傳輸協議SCTP使用CRC32C而不是Adler-32。[5]對於較小的增量更改，Adler-32也被證明變化很弱[6]，並且對於從一個共同的前綴和連續的數字生成的字符串也很弱（例如由典型代碼生成器自動生成的標籤名）。[7]
參見
- 哈希函數列表
腳註
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
