A Fletcher-ellenőrző összeg egy ellenőrzőösszeg - algoritmus , amelyet John Fletcher (1934–2012) fejlesztett ki a Lawrence Livermore Laboratóriumból az 1970-es évek végén. [1] Fletcher ellenőrzőösszegének célja az volt, hogy a ciklikus redundancia kód tulajdonságaihoz közeli hibaérzékelést biztosítson , de alacsonyabb számítási bonyolultsággal, ha általános célú processzorokon alkalmazzák.
Az egyszerűbb ellenőrzőösszeg-algoritmusokhoz hasonlóan a Fletcher-féle ellenőrző összeg magában foglalja a hibaellenőrzendő bináris szó felosztását rövid bitek "blokkjaira", és kiszámítja e blokkok modulo összegét . (Azokat az adatokat, amelyeket összességében ellenőrizni kell, "szónak", azokat a részeket, amelyekre fel van osztva, "blokknak" nevezzük).
Például, ha a továbbított üzenet 136 karakterből áll, amelyek mindegyike 8 bites, akkor az adatszó 1088 bites. A megfelelő blokkméret 8 bites lenne, bár ez nem kötelező. A kényelmi modulus pedig 255 lenne, bár itt is lehetne másikat választani. Így egy egyszerű ellenőrző összeget úgy számítunk ki, hogy az üzenet összes 8 bites blokkját összeadjuk, és kiszámítjuk az eredményt 255 modulo (vagyis elosztjuk 255-tel, és csak a maradékot veszik figyelembe). A gyakorlatban az összegzés során modulo-t hajtanak végre az eredmény méretének szabályozására. Az ellenőrzőösszeg értéket az üzenettel együtt küldi el, hosszát 137 bájtra vagy 1096 bitre növelve. Az üzenet címzettje újraszámíthatja az ellenőrző összeget, és összehasonlíthatja azt a kapott ellenőrzőösszeg értékével annak megállapítására, hogy az üzenet módosult-e az átvitel során.
Az egyszerű ellenőrző összeg első gyengesége, hogy érzéketlen az adatszóban (üzenetben) lévő blokkok (byte) sorrendjére. Ha a sorrendjük megváltozott, az ellenőrző összeg értéke ugyanaz lesz, és a változás nem észlelhető. A második gyengeség az, hogy a lehetséges ellenőrzőösszeg értékek halmaza kicsi és egyenlő a választott modulussal. Példánkban csak 255 lehetséges ellenőrzőösszeg érték szerepel, így könnyen belátható, hogy még véletlenszerű adatoknak is körülbelül 0,4% az esélye, hogy ugyanazt az ellenőrző összeget kapják, mint az üzenetünk (lásd a hash függvény ütközését ).
Fletcher mindkét hiányosságot kijavította a második érték és egy egyszerű ellenőrző összeg kiszámításával. Ez az egyszerű ellenőrző összeg által generált értékek modulo összege, amikor az adatszó minden egyes blokkja hozzáadódik hozzá. A használt modul ugyanaz. Így az egymás után vett adatszó minden egyes blokkjához hozzáadjuk a blokk értékét az első összeghez, majd az első összeg új értékét hozzáadjuk a második összeghez. Mindkét összeg nullától (vagy más előre meghatározott értéktől) kezdődik. A modulo-összeadás az adatszó végén kerül alkalmazásra, és a két érték kombinálva a Fletcher-ellenőrző összeget alkotja.
A blokksorrendre való érzékenység azért van bevezetve, mert ha egyszer egy blokkot hozzáadunk az első összeghez, akkor azt minden előtte lévő blokkal együtt a második összeghez adjuk. Ha például két szomszédos blokkot cserélünk, akkor az eredetileg az első volt egyszer hozzáadódik a második összeghez, és a második, amely eredetileg a második volt, ismét a második összeghez. Az első összeg végső értéke ugyanaz lesz, de a második összeg eltérő lesz, változást észlelve az üzenetben.
Az összes lehetséges ellenőrzőösszeg érték halmaza most egy egyszerű ellenőrző összeg azonos értékének négyzete. Példánkban két, egyenként 255 lehetséges értékkel rendelkező összeg 65025 lehetséges értéket eredményez a kombinált ellenőrző összegre.
A végtelen számú paraméter ellenére az eredeti cikk 8 bites blokkhosszal és 255 és 256 modulussal vizsgálja az esetet.
A 16 bites és 32 bites blokkváltozatokat az eredeti esetből származtatták, és a későbbi specifikációkban vagy dokumentumokban tanulmányozták.
Ha az adatszót 8 bites blokkra osztjuk, mint a fenti példában, a két 8 bites összeget egy 16 bites Fletcher ellenőrző összegben egyesítjük.
Nyilvánvalóan a modul kiválasztásának olyannak kell lennie, hogy az eredmények megegyezzenek a blokk méretével. A 256 ezért a lehető legnagyobb modul a Fletcher-16 számára. Ez azonban rossz választás, mivel a 7. biten túlcsorduló bitek egyszerűen kárba vesznek. Az a modul, amely veszi a túlcsordulási bitet, és keveri azokat az alacsony bitekkel, jobb hibaérzékelést biztosít. A modulusnak azonban nagynak kell lennie ahhoz, hogy a lehető legtöbb ellenőrzőösszeg értéket kapjuk. A 255-ös értéket a második megfontolás kapcsán vettük, de kiváló teljesítményt mutatott.
Amikor az adatszót 16 bites blokkokra osztják, a két 16 bites összeget egy 32 bites ellenőrző összegben egyesítik. Általában a 65535 modulust használják, ugyanazon okokból, mint a 16 bites összeget.
Amikor az adatszót 32 bites blokkokra osztják, a két 32 bites összeget egy 64 bites ellenőrző összegben egyesítik. A 4294967295 modult általában ugyanazon okokból használják, mint a 16 és 32 bites összegeket.
Az Adler-32 ellenőrző összeg a Mark Adler által kifejlesztett Fletcher-32 ellenőrző összeg specializációja. A kiválasztott modulus (mindkét összegre) egyenlő a 65521 prímszámmal (65535 osztható 3-mal, 5-tel, 17-tel és 257-tel). Az első összeg 1-től kezdődik. Egy egyszerű modulus megválasztása jobb "keverést" eredményez (a hibákat egységesebb valószínűséggel észleli, javítva a legkevésbé észlelhető hibák megtalálásának valószínűségét). Az összes lehetséges ellenőrzőösszeg érték halmazának méretének csökkentése azonban ez ellen hat, és kissé csökkenti a teljesítményt. Egy tanulmány kimutatta, hogy a Fletcher-32 mind teljesítményben, mind hibaészlelésben jobb volt az Adler-32-nél. Mivel a modulo 65535 maradék sokkal könnyebben és gyorsabban megvalósítható, mint a modulo 65521, a Fletcher-32 ellenőrző összeg általában a gyorsabb algoritmus. [2]
A Fletcher-ellenőrző összeg nem tud különbséget tenni a 0-s vagy csak 1-es blokkok között. Például, ha az adatszó 16 bites blokkja 0x0000-ről 0xFFFF-re változik, a Fletcher-32 ellenőrző összeg változatlan marad.
Egy nem hatékony, de egyszerű C -megvalósítás egy Fletcher-16 ellenőrzőösszeg kiszámításához 8 bites adatelemek tömbjéből:
uint16_t Fletcher16 ( uint8_t * adatok , int count ) { uint16_t összeg1 = 0 ; uint16_t sum2 = 0 ; int index ; for ( index = 0 ; index < szám ; ++ index ) { összeg1 = ( összeg1 + adatok [ index ]) % 255 ; összeg2 = ( összeg2 + összeg1 ) % 255 ; } visszatérés ( összeg2 << 8 ) | összeg1 ; }A 3. és 4. sorban az összegek 16 bites változók, így a 9. és 10. sorban lévő összeadások nem fognak túlcsordulni. A műveletet moduloa 9. sorban az első összegre, a 10. sorban a második összegre alkalmazzuk. Itt minden összeadás után megtörténik, így a ciklus végén az forösszegek mindig 8 bitre csökkennek. A bemenet végén a két összeget összefűzi egy 16 bites Fletcher-ellenőrző összeg értékké, és a 13. sorban lévő függvény visszaadja.
Minden összeg modulo 255 kerül kiszámításra, és így mindig kisebb, mint 0xFF. Így ez a megvalósítás soha nem ad 0x00FF, 0xFF00 vagy 0xFFFF ellenőrzőösszegű eredményeket. 0x0000 ellenőrzőösszegű eredményt adhat vissza, ami bizonyos esetekben nem kívánatos (például ha ez az érték úgy van fenntartva, hogy "nincs ellenőrző összeg kiszámítva").
Egy példa forráskód az ellenőrző bájtok kiszámításához a fenti függvény használatával a következő. Ellenőrző bájtok hozzáadhatók az adatfolyam végéhez, c0-val a c1 előtt.
uint16_t csum ; uint8_t c0 , c1 , f0 , f1 ; csum = Fletcher16 ( adat , hossz ); f0 = csum & 0xff ; f1 = ( csum >> 8 ) & 0xff ; c0 = 0xff - (( f0 + f1 ) % 0xff ); c1 = 0xff - (( f0 + c0 ) % 0xff );Egy 1988-as cikkében Anastas Nakassis egy algoritmus optimalizálásának különböző módjait tárgyalta és hasonlította össze. A legfontosabb optimalizálás az, hogy elhalasztjuk a modulo számítást, amíg nem tudjuk, hogy túlcsordulás biztosan nem következik be. [3]
Itt van egy C megvalósítás, amely ezt az optimalizálást alkalmazza:
uint16_t fletcher16 ( const uint8_t * data , size_t len ) { uint32_t c0 , c1 ; unsigned int i ; for ( c0 = c1 = 0 ; len >= 5802 ; len -= 5802 ) { for ( i = 0 ; i < 5802 ; ++ i ) { c0 = c0 + * adat ++ ; c1 = c1 + c0 ; } c0 = c0 % 255 ; c1 = c1 % 255 ; } for ( i = 0 ; i < len ; ++ i ) { c0 = c0 + * adat ++ ; c1 = c1 + c0 ; } c0 = c0 % 255 ; c1 = c1 % 255 ; return ( c1 << 8 | c0 ); } uint32_t fletcher32 ( const uint16_t * data , size_t len ) { uint32_t c0 , c1 ; unsigned int i ; for ( c0 = c1 = 0 ; len >= 360 ; len -= 360 ) { for ( i = 0 ; i < 360 ; ++ i ) { c0 = c0 + * adat ++ ; c1 = c1 + c0 ; } c0 = c0 % 65535 ; c1 = c1 % 65535 ; } for ( i = 0 ; i < len ; ++ i ) { c0 = c0 + * adat ++ ; c1 = c1 + c0 ; } c0 = c0 % 65535 ; c1 = c1 % 65535 ; return ( c1 << 16 | c0 ); }8 bites megvalósítás (16 bites ellenőrző összeg).
"abcde" -> 51440 (0xC8F0) "abcdef" -> 8279 (0x2057) "abcdefgh" -> 1575 (0x0627)16 bites megvalósítás (32 bites ellenőrző összeg).
"abcde" -> 4031760169 (0xF04FC729) "abcdef" -> 1448095018 (0x56502D2A) "abcdefgh" -> 3957429649 (0xEBE19591)32 bites megvalósítás (64 bites ellenőrző összeg)
"abcde" -> 14467467625952928454 (0xC8C6C527646362C6) "abcdef" -> 14467579776138987718 (0xC8C72B276463C8C6)