Fletchers16校驗和適合小數據嗎？

使用wikipedia Fletcher's checksum上的直接轉發實現，我們可以得到與「BCA」和「CAB」以及「BAC」和「ACB」等數據相同的校驗和。Fletchers16校驗和適合小數據嗎？

這是預期嗎？
不應該使用Fletcher16校驗和來計算塊的順序嗎？

的不足可以很容易地通過如下圖所示的代碼與中用OR的數據指標是固定....

uint16_t fletcher16(uint8_t *data, int count) 
{ 
    uint16_t sum1 = 0; 
    uint16_t sum2 = 0; 
    int index; 

    for(index = 0; index < count; ++index) 
    { 
     //sum1 = (sum1 + data[index]) % 255; // Original 
     sum1 = (sum1 + index | data[index]) % 255; // The "fix" 
     sum2 = (sum2 + sum1) % 255; 
    } 

    return (sum2 << 8) | sum1; 
}

來源

2017-08-11 Waxhead

「的中用OR指數」丟棄信息。「異或索引」或「添加」會更有意義。 – chux

用XOR代替OR也會改變這個問題。 –

@MichaelFoukarakis改變XOR不會改變這3個問題的答案，因爲它們都指的是缺少'（X）OR索引'的始發者算法。它確實會影響建議改進的質量。 – chux

...我們得到了相同的校驗...是這是預期的？

是的，因爲它是可能的。校驗和是16位（並且從不出現511個組合）：0x..FF,0xFF..），所以3個字符串24位肯定會發生衝突。 Pigeonhole principle

不應該使用Fletcher16校驗和來計算塊的順序嗎？

它的確如此。只是該算法容易與選擇的相似輸入相沖突。也參見Hamming distance

順便說一句，原始算法給出不同的結果，如果該長度或大小（也查詢空字符）用於的字符串。另外，4個輸入字符串給出了一對不同的結果。

printf("%x\n", fletcher16("BCA",3)); // 8ec6 
    printf("%x\n", fletcher16("CAB",3)); // 8ec6 same 
    printf("%x\n", fletcher16("BAC",3)); // 8cc6 
    printf("%x\n", fletcher16("ACB",3)); // 8cc6 same 

    printf("%x\n", fletcher16("BCA",4)); // 55c6 
    printf("%x\n", fletcher16("CAB",4)); // 55c6 same 
    printf("%x\n", fletcher16("BAC",4)); // 53c6 
    printf("%x\n", fletcher16("ACB",4)); // 53c6 same

OP商建議的改進削弱了校驗和也可作爲由-ING或在索引中，其中在每個階段忽略選擇位。建議改變或添加。

小尼特：

// return (sum2 << 8) | sum1; 
return (1u*sum2 << 8) | sum1;

這種變化是不是determental所有int/unsigned尺寸又避免了實現定義的行爲時，int/unsigned是16位。最好保證代碼不會左移到符號位。

some_int % 255執行簽名的餘數。在設備上，例如簡單的嵌入式設備，無符號的餘數肯定會更快或更快。 % 255u沒有什麼可以丟失的，但是可能有所改進。

[編輯]

雖然OP已經爲短字符串的「固定」的代碼，它違背了fletcher16()的設計參數，其執行速度。

細節：如果我們拋開%255，sum1是data[0] + ... + data[count-1]）和sum2是data[0]*(count) + data[0]*(count-1) + ... + data[count-1]*(1)，就很容易產生1,2,3等長字符串與招致一些低價值，如果有的話，%255操作。

請注意，sum2是根據訂單有效創建不同校驗和的部分。如果數組元素的總和永遠不會達到255（這發生在OP的4個測試用例中），則sum1對於任何僅按順序不同的2個字符串都是相同的。

要有效地「混合/散列」具有較低值的短字符串，需要使用不同的算法。

也許只有當使用一個count < 8變種：

sum1 = (sum1 + index + data[index]) % 255;

來源

2017-08-11 13:04:28 chux

感謝您的詳細解答。對我來說，聽起來更簡單的解決方案是在輸入數據中添加一些「種子」。例如只需增加數據[0] = 254，數據[1] ='A'，數據[2] ='B'...等輸入數據......當然，接收端必須處理額外的字節就像它需要處理修改的fletcher校驗和一樣。 – Waxhead

@Waxhead也許'uint16_t sum1 = SEED1; uint16_t sum2 = SEED2;'instead .'fletcher16（）'是速度，代碼尺寸和結果質量的妥協。最好的答案取決於典型的數據流（ASCII，隨機二進制等），處理器能力（內置％或不是本地整數大小）等。祝你好運。 – chux

Fletchers16校驗和適合小數據嗎？

回答

相關問題