CRC doda Ci pewności, cz. 4.pdf

K U R S

CRC doda Ci pewnoci, czêæ 4

Ufff... Zbli¿amy siê do koñca. W zasadzie ca³¹ teoriê dotycz¹c¹

algorytmów generowania CRC mamy ju¿ za sob¹.

Czas na æwiczenia praktyczne.

Wartoci pocz¹tkowe

i koñcowe

Poszczególne algorytmy generowania

CRC ró¿ni¹ siê miêdzy sob¹ nie tylko za-

stosowanymi chwytami programowymi,

ale równie¿ przyjmowanymi wartociami

pocz¹tkowymi rejestru oraz wartoci¹,

która bêdzie XOR-owana z koñcow¹ jego

zawartoci¹. Przyk³adowo: w kodzie

CRC32 rejestr jest inicjowany wartoci¹

FFFFFFFFh, koñcowa zawartoæ rejestru

jest XOR-owana wartoci¹ FFFFFFFFh.

Wiele algorytmów CRC inicjuje rejestr

wartoci¹ zero, ale nie musi to byæ regu-

³¹. Niektóre, jak widaæ choæby z powy-

¿szego przyk³adu, wpisuj¹ do rejestru nie-

zerow¹ wartoæ pocz¹tkow¹. Teoretycznie

nie ma ona wp³ywu na wydajnoæ ani

efekt pracy algorytmu. W praktyce niektó-

re wiadomoci (ci¹gi danych, z których

bêdzie wyliczane CRC) s¹ bardziej praw-

dopodobne od innych. Rozs¹dne wydaje

siê inicjowanie rejestru tak¹ wartoci¹,

która nie bêdzie zawiera³a martwych

punktów mog¹cych wyst¹piæ w rzeczy-

wistoci. Okrelenie martwy punkt

oznacza w tym przypadku tak¹ sekwencjê

danych (odbieranych bajtów), która wziê-

ta do obliczeñ nie spowoduje zmiany sta-

nu rejestru. Algorytmy, które inicjuj¹ re-

jestr wartoci¹ zerow¹, mog¹ zawieraæ

martwy punkt. Zdarza siê bowiem czês-

to, ¿e sekwencja rozbiegowa transmisji

zawiera taki w³anie ci¹g. Z tego powodu

bezpieczniej jest przyjmowaæ niezerow¹

wartoæ pocz¹tkow¹ rejestru.

Gdybymy zdecydowali siê na stwo-

rzenie jednego, uniwersalnego algorytmu,

nale¿a³oby precyzyjniej okreliæ za³o¿e-

nia. Spróbujemy to zrobiæ. Otrzymamy

pewien sparametryzowany model, który

póniej bêdzie móg³ byæ wykorzystywa-

ny w sposób uniwersalny.

Model parametryczny dla

algorytmów obliczania CRC

Dojrzelimy ju¿ do tego, ¿eby

stworzyæ praktyczny model oblicza-

nia CRC. No dobrze, powiedzmy

szczerze, to nie my bêdziemy go two-

rzyæ, gdy¿ zrobiono to ju¿ za nas trochê

wczeniej. My przeledzimy tylko tok ro-

zumowania. Bêdzie to tzw. Rocksoft Mo-

del CRC Algorithm . W modelu tym, sku-

pimy siê wy³¹cznie na funkcjonalnoci

algorytmu, nie zwa¿aj¹c na detale im-

plementacyjne. Nie bêdziemy wiêc, przy-

najmniej na razie, przejmowaæ siê ewen-

tualnymi problemami, jakie mog¹ wyst¹-

piæ na etapie kodowania algorytmu

w konkretnym jêzyku programowania,

chocia¿ finalnym produktem rozwa¿añ

bêdzie program w jêzyku C. Tworzony

sparametryzowany model musi byæ mak-

symalnie prosty i precyzyjny, a co za

tym idzie uporz¹dkowany. Bêdzie on ba-

zowa³ zasadniczo na bezporednim algo-

rytmie tablicowym (patrz czêæ 3). Pa-

miêtaj¹c jednak, ¿e powinien spe³niaæ

wszystkie powy¿sze kryteria, do³o¿ymy

do niego mo¿liwoæ ustalania, czy ma

(tak jak w algorytmie odwróconym) do-

konywaæ odwracania bajtu wejciowego

oraz czy odwrócona ma byæ równie¿

koñcowa wartoæ wyliczonej sumy kont-

rolnej. Jeden z parametrów pozwoli ini-

cjowaæ rejestr obliczeniowy algorytmu

odpowiedni¹ wartoci¹, inny za bêdzie

argumentem operacji XOR na koñcowej

wartoci sumy kontrolnej, zanim zosta-

nie zwrócona jako ostateczny wynik ob-

liczeñ do procedury nadrzêdnej. Maj¹c

powy¿sze za³o¿enia, spróbujmy sporz¹-

dziæ konkretn¹ listê parametrów (przyj-

miemy oryginalne oznaczenia):

NAME - jest to nazwa algorytmu -

zmienna ³añcuchowa;

WIDTH - jest to szerokoæ s³owa obli-

czeniowego algorytmu (rejestru) - licz-

ba bitów. Parametr SZEROKOÆ jest

liczb¹ o jeden mniejsz¹ ni¿ szerokoæ

generatora.

POLY - ten parametr to po prostu nasz

wielomian generuj¹cy (generator, poly ).

Jest to liczba binarna, któr¹ dla wygo-

dy bêdziemy zapisywaæ w postaci

szesnastkowej, ale uwaga! W zapisie

bêdziemy omijaæ najstarszy bit genera-

tora, pamiêtaj¹c, ¿e zawsze jest on

równy 1. Jeli wiêc zastosujemy ge-

nerator np. 10110, to jako parametr

bêdziemy podawaæ go w postaci 0x06.

Wa¿ne jest, ¿e parametr ten przedsta-

wia generator w postaci nieodwróco-

nej. Dolny bit tego parametru bêdzie

zawsze najmniej znacz¹cym bitem

dzielnika, niezale¿nie od tego, czy al-

gorytm bêdzie prosty, czy odwrócony.

INIT - parametr, okrelaj¹cy stan pocz¹t-

kowy rejestru. Jest to wartoæ wpisy-

wana do rejestru w bezporedniej me-

todzie tablicowej. W algorytmie tabli-

cowym rejestr jest zawsze zerowany na

pocz¹tku, a INIT bêdzie wartoci¹,

z któr¹ zostanie XOR-owany rejestr po

N-tej iteracji. Parametr ten powinien

byæ podawany w postaci liczby szes-

nastkowej.

REFIN - jest to parametr logiczny. Jeli

bêdzie on mia³ wartoæ FALSE, to bit

7 bajtów wejciowych bêdzie traktowa-

ny jako najbardziej znacz¹cy (MSB),

a bit 0 jako najmniej znacz¹cy (LSB).

W tym przypadku ka¿dy bajt powinien

byæ odwrócony przed wykonaniem ob-

liczeñ.

REFOUT - jest te¿ parametrem logicz-

nym. Jeli bêdzie mia³ wartoæ FAL-

SE, to koñcowa wartoæ rejestru bê-

dzie bezporednio przenoszona do po-

la XOROUT, w przeciwnym przypad-

ku przed przeniesieniem zawartoci re-

jestru do pola XOROUT rejestr musi

byæ najpierw odwrócony.

XOROUT - jest to W-bitowa liczba, któr¹

bêdziemy podawaæ w postaci szesnast-

kowej. Bêdzie ona XOR-owana z koñco-

w¹ zawartoci¹ rejestru (po REFOUT),

przed umieszczeniem wartoci zwraca-

nej przez procedurê jako koñcowa war-

toæ wyliczonej sumy kontrolnej.

Algorytm absolutny

Jak moglimy siê przekonaæ z wcze-

niejszych rozwa¿añ, w teorii tablicowych

algorytmów obliczania CRC pojawi³o siê

kilka wa¿nych aspektów. W ich wyniku

powsta³o wiele metod obliczania CRC,

a ogarniêcie ca³oci zagadnienia sta³o siê

doæ trudne. Spróbujmy teraz zebraæ na-

byt¹ wiedzê. Widzimy, ¿e poszczególne

algorytmy zale¿¹ od:

- d³ugoci wielomianu generuj¹cego (ge-

neratora),

- wartoci generatora,

- pocz¹tkowego stanu rejestru,

- tego, czy bity w ka¿dym odebranym

bajcie s¹ odwrócone przed wykona-

niem obliczeñ,

- tego, czy algorytm pobiera bajty wej-

ciowe poprzez rejestr, czy XOR-uje je

z bajtem tablicy,

- tego, czy koñcowa wartoæ rejestru po-

winna byæ odwrócona,

- tego, czy XOR-owaæ dan¹ z koñcow¹

wartoci¹ rejestru.

Bezpieczna wymiana danych w systemach mikroprocesorowych

Elektronika Praktyczna 4/2003

K U R S

List. 1. Plik nag³ówkowy crcmodel.h

/******************************************************************************/

/* Pocz¹tek pliku crcmodel.h

/******************************************************************************/

/* */

/* Autor: Ross Williams (ross@guest.adelaide.edu.au.). */

/* Data: 3 czerwca 1993. */

/* Status: Public domain. */

/* */

/* Opis: To jest plik nag³ówkowy (.h), dla programu obliczj¹cego CRC zgodnie */

/* z Rocksoft^tm Model CRC Algorithm. */

/*Uwaga: Rocksoft jest znakiem handlowym Rocksoft Pty Ltd, Adelaide, Australia*/

/* */

/******************************************************************************/

CHECK - to pole jest niezwi¹zane

z definicj¹ w dos³ownym znaczeniu

i w przypadku konfliktu pomiêdzy

nim a innymi polami ustêpuje im

pierwszeñstwa. Bêdzie s³u¿y³o do

kontrolowania poprawnoci imple-

mentacji algorytmu. Pole CHECK bê-

dzie zawiera³o sumê kontroln¹ otrzy-

man¹ w wyniku przepuszczenia

przez algorytm ³añcucha znakowego

(ASCII) o wartoci 123456789

(0x31,0x32,0x33, itd.).

Z tak zdefiniowanymi parametrami

model mo¿e byæ wykorzystany do do-

k³adnego opisywania algorytmów. Przy-

k³adem niech bêdzie popularny algorytm

CRC-16. Odpowiednie dla niego paramet-

ry bêd¹ nastêpuj¹ce:

Name: CRC-16

Width: 16

Poly: 8005 (pamiêtamy, ¿e

jest to zapis

szesnastkowy)

#ifndef CM_DONE

#define CM_DONE

#ifndef DONE_STYLE

typedef unsigned long ulong;

typedef unsigned bool;

typedef unsigned char * p_ubyte_;

#ifndef TRUE

#define FALSE 0

#define TRUE 1

#endif

Init: 0000

RefIn: True

RefOut: True

XorOut: 0000

Check: BB3D

/* Zamieniæ na drug¹ definicjê, jeli nie ma prototypów */

#define P_(A) A

/* #define P_(A) () */

/* Zdj¹æ symbol komentarza w poni¿szej definicji, jeli nie ma void. */

/* typedef int void; */

#endif

Przyk³adowe zestawienie

parametrów dla wybranych

algorytmów

Poni¿sza lista zawiera wielomiany

generuj¹ce dla kilku standardowych al-

gorytmów. Niestety, ze wzglêdu na

spotykane rozbie¿noci, okrelenie

kompletu parametrów okaza³o siê doæ

k³opotliwe.

X25 standardowy: 1021 (CRC-CCITT,

ADCCP,

SDLC/HDLC)

/******************************************************************************/

/* Krótki opis typów w Modelu CRC */

/* Poni¿sze typy zwi¹zane s¹ z wykorzystywanym modelem omawianym w artykule */

/* Wiêkszoæ z nich powinna byæ ustawiona przed pierwszym wywo³aniem cm_ini */

typedef struct

{

int cm_width; /* Parametr: Width w bitach [8,32]. */

ulong cm_poly; /* Parametr: Generator (poly) algorytmu */

ulong cm_init; /* Parametr: Wartoæ pocz¹tkowa rejestru */

bool cm_refin; /* Parametr: czy odwracaæ bajty? */

bool cm_refot; /* Parametr: czy odwracaæ wyjciowe CRC?*/

ulong cm_xorot; /* Parametr: wartoæ do XOR-owania wyjciowego CRC. */

ulong cm_reg; /* Kontekst: Kontekst podczas obliczeñ */

} cm_t;

typedef cm_t *p_cm_t;

X25 odwrócony: 0811

CRC16 standardowy: 8005

CRC16 odwrócony: 4003 (LHA)

W poni¿szym zestawie uwzglêdniono

pe³niejsz¹ listê parametrów:

Name: CRC-16/CITT

Width: 16

Poly: 1021

Init: FFFF

RefIn: False

RefOut: False

XorOut: 0000

Check: ?

/******************************************************************************/

/* Funkcje implementuj¹ce Model */

void cm_ini P_((p_cm_t p_cm));

/* Inicjowanie modelu */

/* Wszystkie parametry powinny byæ ustawione przed wywp³aniem */

void cm_nxt P_((p_cm_t p_cm,int ch));

/* Pobranie kolejnego bajtu do obliczeñ [0,255] */

void cm_blk P_((p_cm_t p_cm,p_ubyte_ blk_adr,ulong blk_len));

/* Pobranie bloku bajtów komunikatu */

ulong cm_crc P_((p_cm_t p_cm));

/* Zwraca wartoæ CRC dla wiadomoci */

Name: XMODEM

Width: 16

Poly: 8408

Init: 0000

RefIn: True

RefOut: True

XorOut: 0000

Check: ?

/******************************************************************************/

/* Funkcje dla obliczeñ tablicowych */

/* --------------- */

/* Poni¿sze funkcje mog¹ byæ wykorzystywane do obliczania tablic (lookup table)*/

/* dla metod tablicowych */

/* Mog¹ byæ równie¿ stosowane w biegu do tworzenia lub sprawdzania */

/* tablic statycznych */

Name: ARC

Width: 16

Poly: 8005

Init: 0000

RefIn: True

RefOut: True

XorOut: 0000

Check: ?

ulong cm_tab P_((p_cm_t p_cm,int index));

/* Zwraca i-ty element tablicy (lookup table) dla okrelonego algorytmu */

/* Funkcja sprawdza pola cm_width, cm_poly, cm_refin i argument tablicy */

/* indeksowany w zakresie [0,255] i zwraca jako wartoæ funkcji element tablicy*/

/* okrelony przez cm_width m³odszych bajtów */

/******************************************************************************/

#endif

/******************************************************************************/

/* Koniec pliku crcmodel.h */

/******************************************************************************/

Na zakoñczenie zestawienie paramet-

rów algorytmu CRC-32 (PKZIP, AUTO-

DIN II, Ethernet, FDDI)

Elektronika Praktyczna 4/2003

K U R S

List. 2. Plik implementacyjny crcmodel.c

/******************************************************************************/

/* Pocz¹tek pliku crcmodel.c */

/******************************************************************************/

/* */

/* Autor: Ross Williams (ross@guest.adelaide.edu.au.). */

/* Data: 3 czerwca 1993. */

/* Status: Public domain. */

/* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */

/* */

/******************************************************************************/

/* */

#include crcmodel.h

/******************************************************************************/

Name: CRC-32

Width: 32

Poly: 04C11DB7

Init: FFFFFFFF

RefIn: True

RefOut: True

XorOut: FFFFFFFF

Check: CBF43926

Implementacja modelu

w jêzyku C

Ci, którym uda³o siê przebrn¹æ przez

dotychczasowe odcinki artyku³u, z pew-

noci¹ czekali na ten w³anie moment.

Ca³a zdobyta wiedza bêdzie za chwilê

wykorzystana do napisania konkretnego

programu. Nie zdziwi chyba nikogo, ¿e

zostanie do tego celu wykorzystany jê-

zyk C, chyba najbardziej popularny

w profesjonalnych zastosowaniach. Nasz

program bêdzie zawiera³ plik nag³ówko-

wy (.h) i plik implementacyjny (.c). Cho-

cia¿ suma kontrolna bêdzie obliczana

w sposób jak najbardziej prawid³owy, to

program ze wzglêdu na jego uniwersal-

noæ bêdzie mia³ raczej niewielk¹ przy-

datnoæ praktyczn¹ (jako ca³oæ). Jest za-

prezentowany ze wzglêdu na walory dy-

daktyczne. Wprawny programista bêdzie

potrafi³ wyfiltrowaæ ewentualnie tylko te

jego fragmenty, które oka¿¹ siê potrzeb-

ne w konkretnych przypadkach. Dla

sprawdzenia, czy poni¿szy kod dzia³a

prawid³owo, mo¿na go bêdzie skonfigu-

rowaæ dla algorytmu CRC-16 lub CRC-

32, zgodnie z informacjami zamieszczo-

nymi powy¿ej i sprawdziæ wynik na

przyk³adowym, wejciowym ³añcuchu

tekstowym 123456789 o znanej sumie

kontrolnej. Autorem programu jest Ross

Williams. Program zosta³ zamieszczony

w Internecie ze statusem public domain.

Aby zapewniæ jak najwiêksz¹ niezale¿-

noæ od komputerów, na których mo¿e

byæ uruchamiany, zastosowano mo¿liwie

proste sposoby kodowania. Na przyk³ad

nazwy wszystkich zewnêtrznych identy-

fikatorów ograniczono do 6 znaków,

a wewnêtrznych do 8. W celu unikniêcia

ewentualnych kolizji w nazwach zmien-

nych zastosowano prefiks cm (od CRC

Model). Za³o¿ona uniwersalnoæ progra-

mu niestety niekorzystnie wp³ywa na je-

go efektywnoæ. Warto pamiêtaæ o prze-

wadze pod wzglêdem szybkoci dzia³a-

nia metod tablicowych nad metodami al-

gorytmicznymi.

/* Poni¿sze definicje zamieszczono w celu zwiêkszenia czytelnoci kodu. */

#define BITMASK(X) (1L << (X))

#define MASK32 0xFFFFFFFFL

#define LOCAL static

/******************************************************************************/

LOCAL ulong reflect P_((ulong v,int b));

LOCAL ulong reflect (v,b)

/* Zwraca wartoæ v, w której b m³odszych bitów [0,32] jest odwróconych */

/* Przyk³ad: reflect(0x3e23L,3) == 0x3e26 */

ulong v;

int b;

{

int i;

ulong t = v;

for (i=0; i<b; i++)

{

if (t & 1L)

v|= BITMASK((b-1)-i);

else

v&= ~BITMASK((b-1)-i);

t>>=1;

}

return v;

}

/******************************************************************************/

LOCAL ulong widmask P_((p_cm_t));

LOCAL ulong widmask (p_cm)

/* Zwraca wartoæ longword, równ¹ (2^p_cm->cm_width)-1 */

/* Zastosowano trik pozwalaj¹cy unikn¹æ przesuniêcia <<32) */

p_cm_t p_cm;

{

return (((1L<<(p_cm->cm_width-1))-1L)<<1)|1L;

}

/******************************************************************************/

void cm_ini (p_cm)

p_cm_t p_cm;

{

p_cm->cm_reg = p_cm->cm_init;

}

/******************************************************************************/

void cm_nxt (p_cm,ch)

p_cm_t p_cm;

int ch;

{

int i;

ulong uch = (ulong) ch;

ulong topbit = BITMASK(p_cm->cm_width-1);

Jak korzystaæ z programu?

Krok 1: Zadeklarowaæ zmienn¹ typu

cm_t. Zadeklarowaæ inn¹ zmienn¹

(p_cm) typu p_cm_t i zainicjowaæ j¹ ja-

ko wskazanie na pierwsz¹ (np. p_cm_t

p_cm = &cm_t)

Krok 2: Przypisaæ wartoci poszcze-

gólnym polom struktury (patrz uwagi

w tekcie)

Przyk³ad:

p_cm->cm_width = 16;

p_cm->cm_poly = 0x8005L;

p_cm->cm_init = 0L;

p_cm->cm_refin = TRUE;

p_cm->cm_refot = TRUE;

p_cm->cm_xorot = 0L;

Uwaga: Wartoæ Poly jest okrelana

bez najstarszego bitu (18005 to 8005).

if (p_cm->cm_refin) uch = reflect(uch,8);

p_cm->cm_reg ^= (uch << (p_cm->cm_width-8));

for (i=0; i<8; i++)

{

if (p_cm->cm_reg & topbit)

p_cm->cm_reg = (p_cm->cm_reg << 1) ^ p_cm->cm_poly;

else

p_cm->cm_reg <<= 1;

p_cm->cm_reg &= widmask(p_cm);

}

/******************************************************************************/

void cm_blk (p_cm,blk_adr,blk_len)

p_cm_t p_cm;

p_ubyte_ blk_adr;

ulong blk_len;

{

while (blk_len-) cm_nxt(p_cm,*blk_adr++);

}

Elektronika Praktyczna 4/2003

K U R S

List. 2. cd.

Wartoæ Width jest o jeden mniejsza ni¿

faktyczna szerokoæ poly.

Krok 3: Zainicjowaæ przyk³ad z wy-

wo³aniem cm_ini(p_cm);

Krok 4: Wykonaæ obliczenia dla ze-

rowej lub niezerowej liczby bajtów ko-

munikatu przez umieszczenie odpowied-

niej liczby wywo³añ cm_nxt. Np.:

cm_nxt(p_cm,ch);

Krok 5: Obliczyæ CRC, stosuj¹c wy-

wo³anie crc = cm_crc(p_cm);

Jeli CRC jest wartoci¹ 16-bitow¹,

wynikiem bêdzie 16 najm³odszych bitów.

/******************************************************************************/

ulong cm_crc (p_cm)

p_cm_t p_cm;

{

if (p_cm->cm_refot)

return p_cm->cm_xorot ^ reflect(p_cm->cm_reg,p_cm->cm_width);

else

return p_cm->cm_xorot ^ p_cm->cm_reg;

}

/******************************************************************************/

ulong cm_tab (p_cm,index)

p_cm_t p_cm;

int index;

{

int i;

ulong r;

ulong topbit = BITMASK(p_cm->cm_width-1);

ulong inbyte = (ulong) index;

Mam nadziejê, ¿e tym razem Czytel-

nicy zostali usatysfakcjonowani mo¿li-

woci¹ zetkniêcia siê z konkretnym pro-

gramem obliczaj¹cym CRC. W³aciwie to

ju¿ wszystko. Czym jest jednak obiad

bez deseru? W ostatnim ju¿ odcinku (za

miesi¹c) poka¿emy, jak s¹ generowane

tablice do metod tablicowych. Poka¿emy

równie¿ kilka innych przyk³adów oraz

wspomnimy co o metodach sprzêto-

wych obliczania CRC.

Jaros³aw Doliñski, AVT

jaroslaw.dolinski@ep.com.pl

if (p_cm->cm_refin) inbyte = reflect(inbyte,8);

r = inbyte << (p_cm->cm_width-8);

for (i=0; i<8; i++)

if (r & topbit)

r = (r << 1) ^ p_cm->cm_poly;

else

r<<=1;

if (p_cm->cm_refin) r = reflect(r,p_cm->cm_width);

return r & widmask(p_cm);

}

Artyku³ powsta³ na podstawie publi-

kacji A painless guide to CRC error de-

tection algorithms. Autor Ross N. Wil-

liams. Mo¿na go znaleæ pod adresem

http://www.riccibitti.com/crcguide.htm.

/******************************************************************************/

/* Koniec pliku crcmodel.c

/******************************************************************************/

Elektronika Praktyczna 4/2003

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: