Adler-32

Adler-32是一種校驗演算法，由馬克·阿德勒在1995年發明，是對Fletcher校驗的一種改進。與相同長度的迴圈冗餘校驗相比，它以可靠性換取速度（更傾向於後者）。Adler-32比Fletcher-16更加可靠，比Fletcher-32可靠性稍差。

歷史

Adler-32校驗和是廣泛使用的zlib壓縮庫的一部分，因為兩者都是由馬克·阿德勒開發的。在rsync工具中使用了Adler-32的「旋轉雜湊」版本。

演算法

Adler-32校驗和是通過計算兩個16位元的校驗和A和B，並將它們的位連為一個32位元整數來獲得的。A是流中所有位元組的總和加1，而B是每個步驟中A的各個值的總和。 在Adler-32執行開始時，A被初始化為1，B為0。以模65521（小於2¹⁶的最大質數）進行求和。位元組以網路順序儲存（位元組序），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		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 =  0x398  (16進位)
B = 4582 = 0x11E6
輸出 = 0x11E6 << 16 + 0x398 = 0x11E60398

在這個例子中，取模運算沒有效果，因為沒有一個值達到65521。

與Fletcher校驗和的比較

兩種演算法之間的第一個區別，是Adler-32和是以一個質數為模數計算的，而Fletcher和是以2⁴-1、2⁸-1或2¹⁶-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相當於簡單的積累。

優點和缺點

• 與標準CRC-32一樣，Adler-32校驗和很容易偽造，因此在防止故意修改方面是不安全的。
• 在許多平台上，它都比CRC-32更快。
• Adler-32對於只有幾百個位元組的簡訊方面有一個弱點，因為這類訊息的校驗和對32個可用位的覆蓋率很低。

弱點

對於簡訊來說，Adler-32是很弱的，因為總和A不會迴繞（英語：Wrap，即整數溢位後的處理）。128位元組訊息的最大和是32640，低於取模操作所使用的值65521，這意味著大約有一半的輸出空間未使用，並且使用部分內的分布也是不均勻的。延伸的解釋可以在RFC 3309中找到，它規定流控制傳輸協定SCTP使用CRC32C而不是Adler-32。對於較小的增量更改，Adler-32也被證明變化很弱，並且對於從一個共同的字首和連續的數字生成的字串也很弱（例如由典型碼產生器自動生成的標籤名）。

參見

• 雜湊函式列表

外部連結

• RFC 1950 – 規範，包含範例C代碼
• ZLib（頁面存檔備份，存於網際網路檔案館） – 在adler32.c中實現了Adler-32演算法
• Chrome（頁面存檔備份，存於網際網路檔案館） – 在adler32_simd.c（頁面存檔備份，存於網際網路檔案館）中使用SIMD實現的Adler-32演算法
• RFC 3309 – 有關簡訊弱點和SCTP相關更改的資訊