Suma kontrolna BSD

Algorytm sumy kontrolnej BSD był powszechnie używanym, starszym algorytmem sumy kontrolnej . Został zaimplementowany w starym BSD i jest również dostępny za pośrednictwem narzędzia wiersza poleceń sum .

Ten algorytm jest bezużyteczny z punktu widzenia bezpieczeństwa i jest słabszy niż CRC-32 cksum do wykrywania błędów.

Obliczanie sumy kontrolnej BSD

Poniżej znajduje się odpowiednia część sumy kodu źródłowego GNU ( na licencji GPL ). Oblicza 16-bitową sumę kontrolną, dodając wszystkie bajty (8-bitowe słowa) wejściowego strumienia danych. Aby uniknąć wielu słabości zwykłego dodawania danych, akumulator sumy kontrolnej jest obracany w prawo o jeden bit na każdym kroku przed dodaniem nowego znaku.

   

       0             

               
                  
          
                 
    
     
 int  bsdChecksumFromFile  (  PLIK  *  fp  )  /* Uchwyt pliku dla danych wejściowych */  {  int  suma kontrolna  =  ;  /* Modyfikacja sumy kontrolnej 2^16. */   for  (  int  ch  =  getc  (  fp  );  ch  !=  EOF  ;  ch  =  getc  (  fp  ))  {  suma kontrolna  =  (  suma kontrolna  >>  1  )  +  ((  suma kontrolna  &  1  )  <<  15  );  suma kontrolna  +=  kan  ;  suma kontrolna  &=  0xffff  ;  /* Trzymaj to w granicach. */   }  zwróć  sumę kontrolną  ;  }

Opis algorytmu

Jak wspomniano powyżej, ten algorytm oblicza sumę kontrolną, dzieląc dane na segmenty i dodając je do akumulatora, który jest kołowo przesunięty w prawo między każdym sumowaniem. Aby utrzymać akumulator w granicach wartości zwracanej, wykonywane jest maskowanie bitów za pomocą jedynek.

Przykład: Obliczanie 4-bitowej sumy kontrolnej przy użyciu segmentów o rozmiarze 4-bitowym ( big-endian )

Wejście: 101110001110 -> trzy segmenty: 1011, 1000, 1110.

Iteracja 1:

segment: 1011 suma kontrolna: 0000 maska bitowa: 1111

a) Zastosuj przesunięcie kołowe do sumy kontrolnej:

0000 -> 0000

b) Dodaj sumę kontrolną i segment, nałóż maskę bitową na otrzymany wynik:

0000 + 1011 = 1011 -> 1011 i 1111 = 1011

Iteracja 2:

segment: 1000 suma kontrolna: 1011 maska bitowa: 1111

a) Zastosuj przesunięcie kołowe do sumy kontrolnej:

1011 -> 1101

b) Dodaj sumę kontrolną i segment, nałóż maskę bitową na otrzymany wynik:

1101 + 1000 = 10101 -> 10101 i 1111 = 0101

Iteracja 3:

segment: 1110 suma kontrolna: 0101 maska bitowa: 1111

a) Zastosuj przesunięcie kołowe do sumy kontrolnej:

0101 -> 1010

b) Dodaj sumę kontrolną i segment, nałóż maskę bitową na otrzymany wynik:

1010 + 1110 = 11000 -> 11000 i 1111 = 1000

Końcowa suma kontrolna: 1000

Źródła