Fletchers kontrollsumma

Fletcher -kontrollsumman är en algoritm för att beräkna en positionsberoende kontrollsumma som utvecklades av John G. Fletcher (1934–2012) vid Lawrence Livermore Labs i slutet av 1970-talet. Syftet med Fletcher-kontrollsumman var att tillhandahålla feldetekteringsegenskaper som närmar sig de för en cyklisk redundanskontroll men med den lägre beräkningsansträngningen som är förknippad med summeringstekniker.

Algoritmen

Granskning av enkla kontrollsummor

Som med enklare kontrollsummaalgoritmer involverar Fletcher-kontrollsumman att dela upp det binära dataordet som ska skyddas från fel i korta "block" av bitar och beräkna den modulära summan av dessa block. (Observera att terminologin som används i den här domänen kan vara förvirrande. Datan som ska skyddas, i sin helhet, hänvisas till som ett "ord", och delarna som de är uppdelade i kallas "block".)

Som ett exempel kan data vara ett meddelande som ska sändas bestående av 136 tecken, vart och ett lagrat som en 8-bitars byte , vilket ger ett dataord på totalt 1088 bitar. En lämplig blockstorlek skulle vara 8 bitar, även om detta inte krävs. På liknande sätt skulle en lämplig modul vara 255, även om andra skulle kunna väljas. Så den enkla kontrollsumman beräknas genom att lägga ihop alla 8-bitars bytes i meddelandet, dividera med 255 och bara behålla resten. (I praktiken modulo-operationen under summeringen för att styra storleken på resultatet.) Checksummevärdet sänds 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 värdet för att bestämma om meddelandet har ändrats av överföringsprocessen.

Svagheter med enkla kontrollsummor

Den första svagheten med den enkla kontrollsumman är att den är okänslig för ordningen på blocken (bytes) i dataordet (meddelandet). Om ordern ändras kommer kontrollsumman att vara detsamma och ändringen kommer inte att upptäckas. Den andra svagheten är att universum av kontrollsummevärden är litet och är 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 ungefär 0,4 % sannolikhet att ha samma kontrollsumma som vårt meddelande.

Fletchers kontrollsumma

Fletcher åtgärdar båda dessa svagheter genom att beräkna ett andra värde tillsammans med den enkla kontrollsumman. Detta är den modulära summan av värdena som tas av den enkla kontrollsumman när varje block av dataordet läggs till det. Modulen som används är densamma. Så, för varje block av dataordet, taget i sekvens, adderas blockets värde 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 med värdet noll (eller något annat känt värde). Vid slutet av dataordet appliceras moduloperatorn och de två värdena kombineras för att bilda Fletcher-kontrollsumman.

Känslighet för blockordningen introduceras eftersom när ett block väl läggs till den första summan, läggs det sedan upprepade gånger till den andra summan tillsammans med varje block efter det. Om till exempel två intilliggande block byts ut, kommer det som ursprungligen var först att läggas till den andra summan en färre gånger och det som ursprungligen var tvåa kommer att läggas till den andra summan en gång till. Det slutliga värdet på den första summan kommer att vara detsamma, men den andra summan kommer att vara annorlunda och detekterar ändringen i meddelandet.

Universum av möjliga kontrollsummavärden är nu kvadraten på värdet för den enkla kontrollsumman. I vårt exempel resulterar de två summorna, var och en med 255 möjliga värden, i 65025 möjliga värden för den kombinerade kontrollsumman.

Översikt över de olika algoritmparametrarna

Även om det finns en oändlighet av parametrar, studerar originaluppsatsen bara fallet K=8 (ordlängd) med modul 255 och 256.

16- och 32-bitarsversionerna (Fletcher-32 och -64) har härletts från originalfallet och studerats i efterföljande specifikationer eller artiklar.

Fletcher-16

     När dataordet är uppdelat i 8-bitars block, som i exemplet ovan, resulterar två 8-bitars summor och kombineras till en 16-bitars Fletcher-kontrollsumma. Vanligtvis kommer den andra summan att multipliceras med 256 och läggas till den enkla kontrollsumman, vilket effektivt staplar summorna sida vid sida i ett 16-bitars ord med den enkla kontrollsumman i den minst signifikanta änden. Denna algoritm kallas sedan för Fletcher-16-kontrollsumman. Användningen av modulen 2 8 − 1 = 255 är också generellt underförstådd.

Fletcher-32

     När dataordet är uppdelat i 16-bitars block, resulterar två 16-bitars summor och kombineras till en 32-bitars Fletcher-kontrollsumma. Vanligtvis kommer den andra summan att multipliceras med 2 16 och läggas till den enkla kontrollsumman, vilket effektivt staplar summorna sida vid sida i ett 32-bitars ord med den enkla kontrollsumman i den minst signifikanta änden. Denna algoritm kallas sedan för Fletcher-32-kontrollsumman. Användningen av modulen 2 16 − 1 = 65 535 antyds också generellt. Skälet för detta val är detsamma som för Fletcher-16.

Fletcher-64

     När dataordet är uppdelat i 32-bitars block, resulterar två 32-bitars summor och kombineras till en 64-bitars Fletcher-kontrollsumma. Vanligtvis kommer den andra summan att multipliceras med 2 32 och läggas till den enkla kontrollsumman, vilket effektivt staplar summorna sida vid sida i ett 64-bitars ord med den enkla kontrollsumman i den minst signifikanta änden. Denna algoritm kallas sedan för Fletcher-64-kontrollsumman. Användningen av modulen 2 32 − 1 = 4 294 967 295 antyds också generellt. Skälet för detta val är detsamma som för Fletcher-16 och Fletcher-32.

Jämförelse med Adlers kontrollsumma

Adler -32- kontrollsumman är en specialisering av Fletcher-32-kontrollsumman utarbetad av Mark Adler . Den valda modulen (för båda summorna) är primtalet 65 521 (65 535 är delbart med 3, 5, 17 och 257). Den första summan börjar också med värdet 1. Valet av en primmodul resulterar i förbättrad "blandning" (felmönster detekteras med mer enhetlig sannolikhet, vilket förbättrar sannolikheten att de minst detekterbara mönstren kommer att detekteras, vilket tenderar att dominera den totala prestandan ). Men minskningen av universums storlek av möjliga kontrollsummavärden motverkar detta och minskar prestandan något. En studie visade att Fletcher-32 överträffar Adler-32 i både prestanda och förmåga att upptäcka fel. Eftersom modulo-65,535-tillägg är betydligt enklare och snabbare att implementera än modulo-65,521-tillägg är Fletcher-32-kontrollsumman generellt sett en snabbare algoritm.

Varning för Modulus

En modul på 255 används ovan och i exemplen nedan för Fletcher-16, men vissa verkliga implementeringar använder 256. TCP-protokollets alternativa kontrollsumma har Fletcher-16 med en modul på 256, liksom kontrollsummorna för UBX-*-meddelanden från en U-blox GPS. Vilken modul du behöver beror på den andra partens implementering. Kontrollera noggrant dokumentationen för dina protokoll!

Exempelberäkning av Fletcher-16 kontrollsumma

Som ett exempel ska en Fletcher-16-kontrollsumma beräknas och verifieras för en byteström på 0x01 0x02.

  • C0_initial = 0
  • C1_initial = 0
Byte (B) C0 = (C0 föregående + B) mod 255 C1 = (C1 föregående + C0) mod 255 Beskrivning
0x01 0x01 0x01 Första byten matas in
0x02 0x03 0x04 Andra byte matas in

Kontrollsumman är därför 0x0403. Den skulle kunna sändas med byteströmmen och verifieras som sådan på den mottagande sidan. Ett annat alternativ är att i ett andra steg beräkna ett par kontrollbyte, som kan läggas till byteströmmen så att den resulterande strömmen har ett globalt Fletcher-16 kontrollsummavärde på 0.

Värdena för checkbytes beräknas enligt följande:

  • CB0 = 255 − ((C0 + C1) mod 255),
  • CB1 = 255 − ((C0 + CB0) mod 255),

där C0 och C1 är resultatet av det sista steget i Fletcher-16-beräkningen.

I vårt fall är kontrollsummans byte CB0 = 0xF8 och CB1 = 0x04. Den överförda byteströmmen är 0x01 0x02 0xF8 0x04. Mottagaren kör kontrollsumman på alla fyra byte och beräknar en passerande kontrollsumma på 0x00 0x00, som illustreras nedan:

Byte (B) C0 = (C0 föregående + B) mod 255 C1 = (C1 föregående + C0) mod 255 Beskrivning
0x01 0x01 0x01 Första byten matas in
0x02 0x03 0x04 Andra byte matas in
CB0 = 0xF8 (0x03 + 0xF8) % 0xFF = 0xFB (0x04 + 0xFB) % 0xFF = 0x00 Checksummaberäkning – byte 1
CB1 = 0x04 (0xFB + 0x04) % 0xFF = 0x00 (0x00 + 0x00) % 0xFF = 0x00 Checksummaberäkning – byte 2

Svagheter

Fletchers kontrollsumma kan inte skilja mellan block med alla 0 bitar och block med alla 1 bitar. Till exempel, om ett 16-bitars block i dataordet ändras från 0x0000 till 0xFFFF, förblir kontrollsumman för Fletcher-32 densamma. Detta betyder också att en sekvens med alla 00 byte har samma kontrollsumma som en sekvens (av samma storlek) av alla FF-byte.

Genomförande

Dessa exempel antar tvås komplementaritmetik , eftersom Fletchers algoritm kommer att vara felaktig på ens komplementmaskiner .

Enkel

Nedan är en behandling om hur man beräknar kontrollsumman inklusive kontrollbyte; dvs det slutliga resultatet bör vara lika med 0, givet korrekt beräknade kontrollbytes. Koden i sig kommer dock inte att beräkna kontrollbyten.

En ineffektiv men enkel implementering av en C-språkfunktion för att beräkna Fletcher-16-kontrollsumman för en array av 8-bitars dataelement följer: 

      

      0
      0
    

       0     
   
            
            
   

        
 uint16_t  Fletcher16  (  uint8_t  *  data  ,  int  count  )  {  uint16_t  sum1  =  ;  uint16_t  summa2  =  ;  int  index  ;  for  (  index  =  ;  index  <  count  ;  ++  index  )  {  sum1  =  (  summa1  +  data  [  index  ])  %  255  ;  summa2  =  (  summa2  +  summa1  )  %  255  ;  }  return  (  sum2  <<  8  )  |  summa1  ;  }

På raderna 3 och 4 är summorna 16-bitars variabler så att tilläggen på raderna 9 och 10 inte kommer att svämma över . Modulo -operationen appliceras på den första summan på rad 9 och på den andra summan på rad 10. Här görs detta efter varje addition, så att summorna i slutet av for-slingan alltid reduceras till 8 bitar. I slutet av indata kombineras de två summorna till 16-bitars Fletcher-kontrollsumman och returneras av funktionen på rad 13.

Varje summa beräknas modulo 255 och förblir således mindre än 0xFF hela tiden. Denna implementering kommer alltså aldrig att ge kontrollsummaresultaten 0x??FF, 0xFF?? eller 0xFFFF (dvs 511 av de totala 65536 möjliga 16-bitarsvärdena används aldrig). Det kan ge kontrollsumman 0x0000, vilket kanske inte är önskvärt under vissa omständigheter (t.ex. när detta värde har reserverats för att betyda "ingen kontrollsumma har beräknats").

Kontrollera bytes

Exempel på källkod för beräkning av kontrollbyte, med användning av ovanstående funktion, är följande. Kontrollbitgrupperna kan läggas till i slutet av dataströmmen, där c0 kommer före c1.

 
 

   
    
      
        
         uint16_t  csum  ;  uint16_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  );

Optimeringar

I en artikel från 1988 diskuterade och jämförde Anastase Nakassis olika sätt att optimera algoritmen. Den viktigaste optimeringen består i att använda större ackumulatorer och att fördröja den relativt kostsamma modulodriften så länge det kan bevisas att inget spill kommer att inträffa. Ytterligare fördelar kan erhållas genom att ersätta modulo-operatorn med en likvärdig funktion anpassad för detta specifika fall – till exempel en enkel jämförelse och subtrahera, eftersom kvoten aldrig överstiger 1.

Här är en C- implementering som tillämpar den första men inte den andra optimeringen: 

 
 

      
	  

	
	
	     0   0  
		   
		    
			  
		
		  
		 
			    
			    
		  
		    
		    
   
        


      
	  
	            

	
	
	     0   0  
		   
		    
			  
		
		  
		 
			    
			    
		    
		    
		    
	
	     


 #include  <stdlib.h>  /* för size_t */  #include  <stdint.h>  /* för uint8_t, uint16_t & uint32_t */  uint16_t  fletcher16  (  const  uint8_t  *  data  ,  size_t  len  ​​)  {  uint32_t  c0  ,  c1  ;  /* Hittat genom att lösa för c1-spill: */  /* n > 0 och n * (n+1) / 2 * (2^8-1) < (2^32-1). */   för  (  c0  =  c1  =  ;  len  >  ;  )  {  size_t  blocklen  =  len  ;  if  (  blocklen  >  5802  )  {  blocklen  =  5802  ;  }  len  -=  blocklen  ;  gör  {  c0  =  c0  +  *  data  ++  ;  cl  =  cl  +  cO  ;  }  while  (  --  blocklen  );  c0  =  c0  %  255  ;  cl  =  cl  %  255  ;  }  return  (  c1  <<  8  |  c0  );  }  uint32_t  fletcher32  (  const  uint16_t  *  data  ,  size_t  len  ​​)  {  uint32_t  c0  ,  c1  ;  len  =  (  len  +  1  )  &  ~  1  ;  /* Runda upp len till ord */  /* Vi löser på liknande sätt för n > 0 och n * (n+1) / 2 * (2^16-1) < (2^32-1) här. */   /* På moderna datorer kan en 64-bitars c0/c1 tillåta en gruppstorlek på 23726746. */  for  (  c0  =  c1  =  ;  len  >  ;  )  {  size_t  blocklen  =  len  ;  if  (  blocklen  >  360  *  2  )  {  blocklen  =  360  *  2  ;  }  len  -=  blocklen  ;  gör  {  c0  =  c0  +  *  data  ++  ;  cl  =  cl  +  cO  ;  }  while  ((  blocklen  -=  2  ));  c0  =  c0  %  65535  ;  cl  =  cl  %  65535  ;  }  return  (  c1  <<  16  |  c0  );  }  // En liknande rutin skulle kunna skrivas för fletcher64. Gruppstorleken skulle vara 92681.

Den andra optimeringen används inte eftersom "aldrig överstiger 1"-antagandet endast gäller när modulo beräknas naivt; att tillämpa den första optimeringen skulle bryta den. Å andra sidan är modulo Mersenne-nummer som 255 och 65535 en snabb operation på datorer ändå, eftersom det finns knep för att göra dem utan den kostsamma divisionsoperationen.

Testa vektorer

8-bitars implementering (16-bitars kontrollsumma)

"abcde" -> 51440 (0xC8F0) "abcdef" -> 8279 (0x2057) "abcdefgh" -> 1575 (0x0627)

16-bitars implementering (32-bitars kontrollsumma), med 8-bitars ASCII -värden för ingångsordet sammansatta till 16-bitars block i little-endian ordning, ordet utfyllt med nollor efter behov till nästa hela block, med modul 65535 och med resultatet presenterat som summan av summorna förskjuten vänster med 16 bitar (multiplicerat med 65536) plus den enkla summan 

"abcde" -> 4031760169 (0xF04FC729) "abcdef" -> 1448095018 (0x56502D2A) "abcdefgh" -> 3957429649 (0xEBE19591)

32-bitars implementering (64-bitars kontrollsumma)

"abcde" -> 14467467625952928454 (0xC8C6C527646362C6) "abcdef" -> 14467579776138987718 (0xC8C72B276463> 827646362C6) "8207579776138987718" 6982 (0x312E2B28CCCAC8C6)

Bit- och byteordning ( endianness /nätverksordning)

Som med alla beräkningar som delar upp ett binärt dataord i korta block och behandlar blocken som siffror, bör alla två system som förväntar sig att få samma resultat bevara ordningen av bitar i dataordet. I detta avseende skiljer sig inte Fletchers kontrollsumma från andra kontrollsumma och CRC-algoritmer och behöver ingen speciell förklaring.

Ett ordningsproblem som är lätt att föreställa sig uppstår när dataordet överförs byte-för-byte mellan ett big-endian- system och ett little-endian- system och Fletcher-32-kontrollsumman beräknas. Om block extraheras från dataordet i minnet genom en enkel läsning av ett 16-bitars heltal utan tecken, kommer blockens värden att vara olika i de två systemen, på grund av omkastningen av byteordningen för 16-bitars dataelement i minnet, och kontrollsummans resultat blir annorlunda som en konsekvens. Implementeringsexemplen ovan tar inte upp beställningsproblem för att inte skymma kontrollsummaalgoritmen. Eftersom Fletcher-16-kontrollsumman använder 8-bitars block, påverkas den inte av byte endianness .

  1. ^ Fletcher, JG (januari 1982). "En aritmetisk kontrollsumma för seriella överföringar". IEEE-transaktioner på kommunikation . COM-30 (1): 247–252. doi : 10.1109/tcom.1982.1095369 .
  2. ^ Theresa C. Maxino, Philip J. Koopman (januari 2009). "Effektiviteten av kontrollsummor för inbyggda kontrollnätverk" ( PDF) . IEEE-transaktioner på pålitlig och säker datoranvändning.
  3. ^ J.Zweig, UIUC, C.Partridge, BBN (februari 1990). "TCP alternativa kontrollsummaalternativ" . Nätverksarbetsgrupp. {{ citera webben }} : CS1 underhåll: flera namn: lista över författare ( länk )
  4. ^ Sartek, Olika (juni 2018). "Beräknar UBX-kontrollsumma korrekt i python" . uBlox supportportal.
  5. ^   Anastase Nakassis (oktober 1988). "Fletchers feldetekteringsalgoritm: hur man implementerar den effektivt och hur man undviker de vanligaste fallgroparna". Nyhetsbrev ACM SIGCOMM Computer Communication Review Hemsida Arkiv . 18 (5): 63–88. doi : 10.1145/53644.53648 . S2CID 17356816 .
  6. ^ Jones Douglas W. "Modul utan uppdelning, en handledning" . UNIVERSITY OF IOWA Institutionen för datavetenskap . Hämtad 9 september 2019 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Fletcher%27s_checksum&oldid=1139370264 "