Fletcher-kontrollsumman är en kontrollsummaalgoritm som utvecklades av John Fletcher (1934–2012) från Lawrence Livermore Laboratory i slutet av 1970-talet. [1] Fletchers kontrollsummamål var att tillhandahålla feldetektering nära egenskaperna hos cyklisk redundanskod , men med lägre beräkningskomplexitet när den implementerades på processorer för allmänna ändamål.
Som med enklare kontrollsummaalgoritmer involverar Fletchers kontrollsumma att dela upp det binära ordet som ska felkontrolleras i korta "block" av bitar och beräkna modulosumman för dessa block. (Datan som behöver kontrolleras som helhet kallas ett "ord", och de delar som det är uppdelat i kallas "block").
Till exempel, om det överförda meddelandet består av 136 tecken, som vart och ett är 8 bitar, är dataordet 1088 bitar. En lämplig blockstorlek skulle vara 8 bitar, även om detta inte krävs. Och bekvämlighetsmodulen skulle vara 255, även om en annan skulle kunna väljas. Således beräknas en enkel kontrollsumma genom att summera alla 8-bitars block av meddelandet och beräkna resultatet modulo 255 (det vill säga dividera med 255 och endast ta resten). I praktiken utförs modulo under summering för att kontrollera storleken på resultatet. Kontrollsumman skickas tillsammans med meddelandet och ökar dess längd till 137 byte eller 1096 bitar. Mottagaren av meddelandet kan räkna om kontrollsumman och jämföra den med det mottagna kontrollsummans värde för att avgöra om meddelandet har modifierats under överföringen.
Den första svagheten med en enkel kontrollsumma är att den är okänslig för ordningen på blocken (bytes) i dataordet (meddelandet). Om deras beställning har ändrats kommer kontrollsummans värde att vara detsamma och ändringen kommer inte att upptäckas. Den andra svagheten är att uppsättningen av möjliga kontrollsummavärden är liten och lika med den valda modulen. I vårt exempel finns det bara 255 möjliga kontrollsummavärden, så det är lätt att se att även slumpmässiga data har cirka 0,4 % chans att få samma kontrollsumma som vårt meddelande (se hashfunktionskollision ).
Fletcher korrigerade båda dessa brister genom att beräkna det andra värdet tillsammans med en enkel kontrollsumma. Detta är modulo summan av värdena som produceras av den enkla kontrollsumman när varje block av dataordet läggs till det. Modulen som används är densamma. Sålunda, för varje block av dataordet som tas i följd, adderas värdet av blocket till den första summan, och det nya värdet av den första summan adderas sedan till den andra summan. Båda summorna börjar på noll (eller något annat förutbestämt värde). Modulo-addition tillämpas i slutet av dataordet och de två värdena kombineras för att bilda Fletcher-kontrollsumman.
Känslighet för blockordning införs eftersom när ett block läggs till den första summan, läggs det sedan till på nytt till den andra summan tillsammans med varje block före den. Om till exempel två angränsande block byts ut, kommer det som ursprungligen var det första att läggas till den andra summan en gång och det andra, som ursprungligen var det andra, kommer att läggas till den andra summan igen. Det slutliga värdet på den första summan kommer att vara detsamma, men den andra summan kommer att vara annorlunda, vilket upptäcker en förändring i meddelandet.
Uppsättningen av alla möjliga kontrollsummavärden är nu kvadraten på samma värde för en enkel kontrollsumma. I vårt exempel resulterar två summor, var och en med 255 möjliga värden, i 65025 möjliga värden för den kombinerade kontrollsumman.
Trots det oändliga antalet parametrar studerar originaldokumentet fallet med en blocklängd på 8 bitar och en modul på 255 och 256.
16-bitars och 32-bitars blockvarianter härleddes från det ursprungliga fallet och studerades i efterföljande specifikationer eller dokument.
När dataordet är uppdelat i 8-bitarsblock, som i exemplet ovan, kombineras de två 8-bitarssummorna till en 16-bitars Fletcher-kontrollsumma.
Självklart måste valet av modul vara sådant att resultaten matchar blockstorleken. 256 är därför den största möjliga modulen för Fletcher-16. Detta är dock ett dåligt val, eftersom bitar som svämmar över på bit 7 helt enkelt går till spillo. En modul som tar spillbiten och blandar dem med de låga bitarna ger bättre feldetektering. Modulen måste dock vara stor för att erhålla det största antalet möjliga kontrollsummavärden. Värdet 255 tas i samband med det andra övervägandet, men har visat sig ha utmärkta prestanda.
När dataordet är uppdelat i 16-bitarsblock kombineras de två 16-bitarssummorna till en 32-bitars kontrollsumma. Modulen 65535 används vanligtvis av samma skäl som 16-bitars summan.
När dataordet är uppdelat i 32-bitarsblock kombineras de två 32-bitarssummorna till en 64-bitars kontrollsumma. Modulen 4294967295 används vanligtvis, av samma skäl som 16 och 32 bitars summor.
Adler -32- kontrollsumman är en specialisering av Fletcher-32-kontrollsumman utvecklad av Mark Adler. Den valda modulen (för båda summorna) är lika med primtalet 65521 (65535 är delbart med 3, 5, 17 och 257). Den första summan börjar vid 1. Att välja en enkel modul resulterar i förbättrad "shuffle" (fel upptäcks med mer enhetlig sannolikhet, vilket förbättrar sannolikheten för att hitta de minst detekterbara felen). Men att minska storleken på uppsättningen av alla möjliga kontrollsummavärden motverkar detta och minskar prestandan något. En studie visade att Fletcher-32 var överlägsen Adler-32 i både prestanda och feldetektering. Eftersom modulo 65535 resten är mycket enklare och snabbare att implementera än modulo 65521, är Fletcher-32 kontrollsumma vanligtvis den snabbare algoritmen. [2]
Fletchers kontrollsumma kan inte skilja mellan block som alla är 0:or eller endast 1:or. Till exempel, om 16-bitarsblocket i dataordet ändras från 0x0000 till 0xFFFF, kommer Fletcher-32-kontrollsumman att förbli oförändrad.
En ineffektiv men enkel C -implementering av en funktion för att beräkna en Fletcher-16-kontrollsumma från en array av 8-bitars dataobjekt:
uint16_t Fletcher16 ( uint8_t * data , int count ) { uint16_t summa1 = 0 ; uint16_t summa2 = 0 ; int index ; för ( index = 0 ; index < count ; ++ index ) { summa1 = ( summa1 + data [ index ]) % 255 ; summa2 = ( summa2 + summa1 ) % 255 ; } return ( sum2 << 8 ) | summa1 ; }På raderna 3 och 4 är summorna 16-bitars variabler, så tilläggen på raderna 9 och 10 kommer inte att svämma över. Operationen moduloappliceras på den första summan på rad 9 och på den andra summan på rad 10. Här görs den efter varje addition, så att forsummorna i slutet av slingan alltid reduceras till 8 bitar. I slutet av inmatningen sammanfogas de två summorna till ett 16-bitars Fletcher-kontrollsummavärde och returneras av funktionen på rad 13.
Varje summa beräknas modulo 255 och förblir därför alltid mindre än 0xFF. Således kommer den här implementeringen aldrig att ge kontrollsummaresultat på 0x00FF, 0xFF00 eller 0xFFFF. Det kan returnera ett kontrollsummaresultat på 0x0000, vilket kan vara oönskat i vissa fall (till exempel när detta värde är reserverat för att betyda "ingen kontrollsumma har beräknats").
Ett exempel på källkod för att beräkna checkbytes med användning av ovanstående funktion är följande. Checkbytes kan läggas till i slutet av dataströmmen, med c0 före c1.
uint16_t csum ; uint8_t c0 , c1 , f0 , f1 ; csum = Fletcher16 ( data , längd ); f0 = csum & 0xff ; f1 = ( csum >> 8 ) & 0xff ; c0 = 0xff - (( fo + f1 ) % 0xff ); c1 = 0xff - (( fo + c0 ) % 0xff );I en artikel från 1988 diskuterade och jämförde Anastas Nakassis olika sätt att optimera en algoritm. Den viktigaste optimeringen är att skjuta upp moduloberäkningen tills det är känt att ett spill definitivt inte kommer att inträffa. [3]
Här är en C-implementering som tillämpar denna optimering:
uint16_t fletcher16 ( const uint8_t * data , size_t len ) { uint32_t c0 , c1 ; osignerad int i ; för ( c0 = c1 = 0 ; len >= 5802 ; len -= 5802 ) { för ( i = 0 ; i < 5802 ; ++ i ) { c0 = c0 + * data ++ ; cl = cl + cO ; } c0 = c0 % 255 ; cl = cl % 255 ; } för ( i = 0 ; i < len ; ++ i ) { c0 = c0 + * data ++ ; cl = cl + cO ; } c0 = c0 % 255 ; cl = cl % 255 ; return ( c1 << 8 | c0 ); } uint32_t fletcher32 ( const uint16_t * data , size_t len ) { uint32_t c0 , c1 ; osignerad int i ; för ( c0 = c1 = 0 ; len >= 360 ; len -= 360 ) { för ( i = 0 ; i < 360 ; ++ i ) { c0 = c0 + * data ++ ; cl = cl + cO ; } c0 = c0 % 65535 ; cl = cl % 65535 ; } för ( i = 0 ; i < len ; ++ i ) { c0 = c0 + * data ++ ; cl = cl + cO ; } c0 = c0 % 65535 ; cl = cl % 65535 ; return ( c1 << 16 | c0 ); }8-bitars implementering (16-bitars kontrollsumma).
"abcde" -> 51440 (0xC8F0) "abcdef" -> 8279 (0x2057) "abcdefgh" -> 1575 (0x0627)16-bitars implementering (32-bitars kontrollsumma).
"abcde" -> 4031760169 (0xF04FC729) "abcdef" -> 1448095018 (0x56502D2A) "abcdefgh" -> 3957429649 (0xEBE19591)32-bitars implementering (64-bitars kontrollsumma)
"abcde" -> 14467467625952928454 (0xC8C6C527646362C6) "abcdef" -> 14467579776138987718 (0xC8C72B276463C8C6)