增量校驗和

我正在尋找校驗和算法，其中對於大塊數據，校驗和等於來自所有較小組件塊的校驗和的總和。我發現的大部分內容都來自提供此功能的RFC 1624/1141。有沒有人有這些校驗和技術或類似的經驗？增量校驗和

2009-07-23 Steve Severance

是否需要專門等於較小塊的校驗，算術和或者你只是更普遍希望能夠從計算大塊的校驗小塊的校驗和？ – 2009-07-23 18:08:41

在我看來，校驗和問題今天被認爲是「基本解決」，常常被解釋爲「IO約束」，因此從算法性能角度來看並不令人感興趣。但是，好吧，「IO界」是，我們可以做什麼IO？那麼，如果我們可以在緩存中IO仍然很熱的時候計算散列值，那就很好。 – 2010-09-15 15:21:56

我只使用Adler/Fletcher校驗和，其工作方式與您所描述的一樣。

加密哈希/校驗和實現here有很好的比較。

來源

2009-07-23 18:23:02

要回答Amigable Clark Kent的賞金問題，對於文件識別目的，您可能需要一個加密散列函數，該函數試圖保證任何兩個給定文件產生相同值的概率極低，而不是校驗和通常僅用於錯誤檢測，並可能爲兩個非常不同的文件提供相同的值。

許多加密散列函數，如MD5和SHA-1，使用Merkle–Damgård construction，在其中有一個計算以數據塊壓縮成固定大小，然後結合起來，與一個固定的大小的值從以前的塊（或第一個塊的初始化向量）。因此，他們能夠以流模式工作，隨着時間的推移逐漸計算。

來源

2010-09-22 14:55:08

如果只是快速組合小塊的校驗和以獲得較大消息的校驗和（不一定是通過簡單求和），則可以使用CRC類型（或類似）算法來實現。

的CRC-32算法是如此簡單：

uint32_t update(uint32_t state, unsigned bit) 
{ 
    if (((state >> 31)^bit) & 1) state = (state << 1)^0x04C11DB7; 
    else       state = (state << 1); 
    return state; 
}

在數學上，狀態表示在字段GF2是始終降低模生成多項式的多項式。給定一個新的位b老態轉化爲新的狀態這樣

state --> (state * x^1 + b * x^32) mod G

其中G是生成多項式和另外在GF2（XOR）來完成。該校驗和是在這個意義上線性可以編寫消息M如消息A，B，C，的總和（XOR）...這樣

10110010 00000000 00000000 = A = a  00000000 00000000 
    00000000 10010001 00000000 = B = 00000000 b  00000000 
    00000000 00000000 11000101 = C = 00000000 00000000 c 
------------------------------------------------------------- 
= 10110010 10010001 11000101 = M = a  b  c

具有以下屬性

  M =   A +   B +   C 
checksum(M) = checksum(A) + checksum(B) + checksum(C)

同樣，我的意思是GF2中的+，您可以使用二進制異或實現。

最後，有可能基於checksum(b)和相對B子塊b的位置來計算checksum(B)。簡單的部分是前導零。前導零不會影響校驗和。因此checksum(0000xxxx)與checksum(xxxx)相同。如果你想計算一個零填充（向右 - >尾隨零）消息的校驗和，給定非填充消息的校驗和，這有點複雜。但並不是很複雜：

zero_pad(old_check_sum, number_of_zeros) 
    := (old_check_sum * x^{number_of_zeros}  ) mod G 
    = (old_check_sum * (x^{number_of_zeros} mod G)) mod G

所以，得到一個零填充消息的校驗和僅僅是一個與其他一些多項式（x^{number_of_zeros} mod G）乘以「校驗多項式」非填充消息的事情，只有依賴關於你想添加的零的數量。您可以在表中預先計算此值，或使用平方和乘法算法快速計算此功率。

來源

2010-09-22 15:03:48 sellibitze

回答

相關問題