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

(104 KB) Pobierz

K U R S

CRC doda Ci pewności, część 3

Jesteúmy juø po pierwszych przymiarkach do napisania w³asnego

programu licz¹cego CRC. Cel wydaje siÍ byÊ coraz bliøej, ale drogi

jakby zaczynaj¹ siÍ rozchodziÊ. Na szczÍúcie kaøda jest dobra.

Dociekliwie bÍdziemy sprawdzaÊ wszystkie tak, by pÛüniej kaødy mÛg³

wybraÊ najodpowiedniejsz¹ dla siebie.

Metoda maglowanej tablicy

Poprzedni odcinek zakoÒczyliúmy na-

pisaniem jednolinijkowego wyraøenia ob-

liczaj¹cego CRC. Jak na pocz¹tek ca³kiem

nieüle. Niby dopiero zaczynamy, a†juø

potrafimy stworzyÊ tak zwiÍz³y kod.

Przypomnijmy wiÍc:

unsigned long r;

...

r=0;

while(len--)

r=((r<<8) | *pMsg++)

^ tab[(unsigned char)((r>>24)

& 0xff)];

Jest jednak pewien problem. Jak wi-

daÊ powyøsza pÍtla operuje na danych

bÍd¹cych kolejnymi bajtami pobieranej

wiadomoúci. Chc¹c wykorzystaÊ tak na-

pisany program naleøy dopisaÊ na koÒ-

cu wiadomoúci (dope³niÊ j¹) W/8 bajtÛw

o†wartoúci zero. W†praktyce moøe to sta-

nowiÊ niedogodnoúÊ lub nie, zaleøy od

konkretnych rozwi¹zaÒ. Jeúli blok da-

nych jest przechwytywany przez inny

fragment programu, moøemy siÍ spodzie-

waÊ nawet sporych k³opotÛw. Jednym

z†moøliwych rozwi¹zaÒ bÍdzie dopisanie

poniøszej linii (bÍdzie ona wykonywana

po wyjúciu z†pÍtli obliczeniowej z†przy-

k³adu pokazanego wczeúniej):

for (i=0; i<W/4; i++)

r = (r << 8) ^ tab[(r >> 24)

& 0xFF];

LiniÍ tÍ bÍdzie moøna pÛüniej zmody-

fikowaÊ tak, øeby unikn¹Ê koniecznoúci

wczytywania zerowych bajtÛw lub w†spo-

sÛb jawny dopisywaÊ zera jak wyøej. Dla

objaúnienia zamys³u jeszcze raz pos³uøy-

my siÍ rysunkiem znanym z†czÍúci 2, ktÛ-

ry dla wygody powtarzamy poniøej (rys.

5).

Zauwaømy jeszcze dwa fakty:

KoÒcÛwka

- zerowe bajty (bÍdzie ich

W/4) pojawiaj¹ce siÍ na koÒcu pobiera-

nej wiadomoúci bÍd¹ ìwpychaneî do re-

jestru z†prawej strony, ale ich zerowa

wartoúÊ nie bÍdzie mia³a øadnego wp³y-

wu na wynik obliczeÒ. Wynika to z†te-

go, øe jak pamiÍtamy XOR-owanie z†ze-

rami nie zmienia bajtu wejúciowego. Tak

wiÍc, funkcja podstawowa wyliczaj¹ca

bajty zerowe generuje wyniki wykorzys-

tywane w†kolejnym cyklu obliczeÒ, co

powoduje, øe po ich zakoÒczeniu

wszystkie przesy³ane dane ìprzejd¹î

przez rejestr.

Nag³Ûwek

- jeúli po zainicjowaniu re-

jestr bÍdzie mia³ zerow¹ wartoúÊ, to

cztery pocz¹tkowe iteracje pÍtli s¹ rÛw-

noznaczne z†przesuniÍciem czterech pier-

wszych bajtÛw wiadomoúci. Wynika to

z†faktu, øe pierwsze 32 bity steruj¹ce

(pobierane kolejno z†rejestru) maj¹c war-

toúÊ zerow¹, s¹ ca³kowicie bez wp³ywu

na wynik XOR-owania. Co wiÍcej, nawet

jeúli wartoúÊ pocz¹tkowa rejestru nie jest

zerowa, to pierwsze cztery bajty itera-

cji omawianego algorytmu dadz¹ rÛw-

nieø jednoznaczny efekt przesuniÍcia

pierwszych czterech bajtÛw wiado-

moúci i†XOR-owania ich z†pewn¹ sta-

³¹ wartoúci¹ (bÍd¹c¹ funkcj¹ pocz¹tkowe-

go stanu rejestru).

Powyøsze fakty po³¹czone z†prze-

miennoúci¹ operacji XOR ((A†⊕†B)†⊕†C†=

A†⊕†(B†⊕†C)) oznaczaj¹, øe bajty wiado-

moúci nie wymagaj¹ przeskoku o†W/4

bajtÛw rejestru, nie bÍd¹ wiÍc przez nie-

go przepuszczane. Zamiast tego bÍd¹

XOR-owane z†najstarszym bajtem rejest-

ru zanim zostan¹ uøyte do indeksowania

tablicy. Na tej podstawie moøemy juø

zmodyfikowaÊ nasz algorytm. Jego gra-

ficzna interpretacja jest przedstawiona na

rys. 6,

a†komentarz do rysunku poniøej:

1. PrzesuÒ rejestr o†jeden bajt w†le-

wo, czytaj¹c nowy bajt wiadomoúci.

2. XOR-uj najstarszy bajt, wysuniÍty

w³aúnie z†rejestru z†nastÍpnym bajtem

wiadomoúci, otrzymuj¹c indeks tablicy

(z†przedzia³u od 0†do 255).

3. XOR-uj rejestr z†pobran¹ z†tablicy

dan¹.

4. Idü do pkt. 1, jeúli nie wykorzys-

ta³eú wszystkich bajtÛw wiadomoúci.

Rejestr dla powyøszego algorytmu

musi byÊ zainicjowany tak¹ sam¹ war-

toúci¹ jak w†omawianym poprzednio

z†tym, øe wartoúÊ pocz¹tkowa musi byÊ

powtÛrzona w†tablicy czterokrotnie. Jeúli

w†poprzedniej metodzie by³y wykorzys-

tywane 0, tak samo naleøy je stosowaÊ

w†tablicach tworzonych dla nowego al-

gorytmu. Moøna wiÍc powiedzieÊ, øe

obie wersje algorytmÛw bÍd¹ takie sa-

me, dadz¹ identyczny wynik. Zapis w†jÍ-

zyku C†bÍdzie wiÍc dobrze nam znany:

unsigned long r;

...

r=0;

while(len--)

r=((r<<8)

^ tab[(unsigned char)(r>>24)

^ *pMsg++];

la wygl¹da jak wyøej. Zastosowan¹ tu

metodÍ bÍdziemy nazywaÊ

bezpoúrednim

algorytmem tablicowym.

OdwrÛcona metoda tablicowa

Wydaje siÍ, øe powyøsza metoda jest

juø ca³kowicie zoptymalizowana. Czy na

pewno? Zaleøy jak na to patrzeÊ. Jeúli

uwzglÍdnimy pewne cechy fizycznych

uk³adÛw stosowanych do realizacji trans-

misji danych, to szybko dojdziemy do

wniosku, øe nie powiedzieliúmy jeszcze

ostatniego s³owa. Mimo, øe znaleüliúmy

siÍ na granicy rozumienia tematu sprÛ-

bujemy wprowadziÊ kolejny stopieÒ

komplikacji. Potrzebna nam bÍdzie do

tego definicja: o†pewnej danej (rejestrze)

bÍdziemy mÛwiÊ, øe jest odwrÛcona, jeú-

li jej bity stanowi¹ odbicie lustrzane

wzglÍdem úrodka. Na przyk³ad ci¹g 0101

jest 4-bitowym odbiciem ci¹gu 1010.

Ci¹g 0011 jest odbiciem 1100. I†jeszcze

nieco bardziej skomplikowany przyk³ad:

0111-0101-1010-1111-0010-0101-1011-

1100 to odbicie 0011-1101-1010-0100-

1111-0101-1010-1110.

Po co to wszystko? OtÛø wprowadze-

nie odwrÛconej metody tablicowej moøe

znacznie u³atwiÊ sprzÍtowe obliczanie

CRC w†systemach transmisji danych. Jak

wiemy wiÍkszoúÊ uk³adÛw UART wysy³a

dane w†liniÍ pocz¹wszy od najm³odsze-

go bitu w†bajcie do najstarszego, tymcza-

sem we wczeúniejszych rozwaøaniach za-

wsze rozpoczynaliúmy analizÍ od bitu

najstarszego. Oczywiúcie procesor pora-

dzi sobie z†takim problemem, i†tak bÍ-

dzie odczytywa³ dane bajtami z†bufora

UART-u. S¹ jednak urz¹dzenia, w†ktÛ-

rych kontrola CRC jest realizowana

sprzÍtowo

on-line

przez specjalizowane

uk³ady. Odbywa siÍ to na poziomie stru-

mienia danych - bit po bicie. Na potrze-

by takich w³aúnie uk³adÛw opracowano

W†powyøszym kodzie ³atwo znajdu-

jemy tablicow¹ implementacjÍ obliczania

CRC. Maska 0xff moøe byÊ stosowana

i†w†tym przypadku dla zachowania kom-

patybilnoúci, jakkolwiek podstawowa pÍt-

Bezpieczna wymiana danych w systemach mikroprocesorowych

Elektronika Praktyczna 3/2003

K U R S

Rys. 5

odwrÛcon¹ metodÍ tablicow¹. Rozpatruje

siÍ w†niej ci¹g bajtÛw taki sam jak

w†metodach poprzednich, ale bity w†kaø-

dym bajcie s¹ odwrÛcone: bit 7†staje siÍ

bitem 0, bit 6†bitem 1, itd. Tym razem

dane s¹ przesuwane w†rejestrze nie w†le-

wo, lecz w†prawo. WartoúÊ pocz¹tkowa

rejestru jest taka sama jak w†poprzedniej

metodzie, przy czym poszczegÛlne bity

s¹ odwrÛcone zgodnie z†powyøszym opi-

sem. OdwrÛcone s¹ teø dane zapisane

w†tablicy. Jedynie dane pozostaj¹ bez

zmian. Do obliczeÒ pobierane s¹ bity

w†kolejnoúci nadchodzenia (czyli od bi-

tu najm³odszego do najstarszego). ZasadÍ

dzia³ania algorytmu ilustruje

rys. 7.

Zauwaømy, øe i†w†tym przypadku

strumieÒ danych nie musi byÊ przepusz-

czany przez rejestr. No i†jeszcze jeden

szczegÛ³. Po zakoÒczeniu obliczeÒ w†re-

jestrze znajduje siÍ obliczona wartoúÊ

CRC... oczywiúcie odwrÛcona. Powyøszy

algorytm bÍdziemy nazywali

tablicowym

algorytmem odwrÛconym.

Oczywiúcie nasuwa siÍ spostrzeøenie,

øe przecieø moøna odpowiednio odwrÛ-

ciÊ bity przed przes³aniem ich do UART-

u, bez koniecznoúci opracowywania do-

datkowych algorytmÛw. Nie zawsze jest

to jednak moøliwe, choÊby z†uwagi na

zachowanie kompatybilnoúci z†innymi

systemami. Poza tym, wbrew pozorom

Rys. 6

nie jest to teø zadanie ³atwe do wykona-

nia dla procesorÛw. Na ogÛ³ nie posia-

daj¹ one odpowiedniego rozkazu i†w†ta-

kiej sytuacji musia³yby wykonywaÊ ìka-

wa³ekî bardziej z³oøonego programu. Do-

datkowe angaøowanie procesora do ta-

kich dzia³aÒ w†przypadku stosowania

duøych prÍdkoúci transmisji mog³oby byÊ

nie do przyjÍcia.

Rys. 7

CRC16 standard: 1-1000-0000-0000-0101

CRC reversed:

1-0100-0000-0000-0011

ZwrÛÊmy uwagÍ na to, øe zosta³y od-

wrÛcone ca³e generatory w³¹cznie z†do-

myúlnym bitem o†wartoúci ì1î na najstar-

szej pozycji, a†nie tylko W†dolnych bitÛw.

Jest to znacz¹ca rÛønica. W†opisywanym

wczeúniej tablicowym algorytmie odwrÛco-

nym stosowany generator by³ identyczny

z†tym, jaki wykorzystywaliúmy w†metodzie

nieodwrÛconej. W†zwi¹zku z†tym musimy

pamiÍtaÊ, øe odwrÛcony algorytm tablico-

wy nie jest odpowiednikiem algorytmu

z†odwrÛconym generatorem.

Czy to juø wszystko? Jeúli chodzi

o†algorytmy, to moøna powiedzieÊ, øe tak.

Pozosta³o jeszcze kilka zagadnieÒ ogÛl-

nych i†d³ugo oczekiwane zapewne przy-

k³ady, przyk³ady, przyk³ady. Na razie g³o-

wa chyba nam jednak uros³a i†trzeba jej

daÊ odpocz¹Ê. Do nastÍpnego miesi¹ca!

Jaros³aw Doliñski, AVT

jaroslaw.dolinski@ep.com.pl

[1] Artyku³ powsta³ na podstawie publi-

kacji ìA painless guide to CRC error

detection algorithmsî, Ross N. Wil-

liams. Moøna j¹ znaleüÊ pod adresem

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

[2] Tanenbaum, A.S., ìComputer Net-

worksî, Prentice Hall, 1981, ISBN: 0-

13-164699-0.

Metoda odwrÛconego generatora

Nie, nie, to jeszcze nie koniec. W†na-

dziei, øe wprowadzanie nowych udziw-

nieÒ moøe skutkowaÊ nieoczekiwanymi

efektami koÒcowymi, tym razem zasto-

sujemy trochÍ niejasn¹ na ìpierwszy rzut

okaî zmianÍ. BÍdzie ona polega³a na od-

wrÛceniu wielomianu generuj¹cego. Jeúli

wartoúÊ G=11101 by³a dobra, to 10111

rÛwnieø powinna siÍ sprawdziÊ i†okazu-

je siÍ w†praktyce, øe jest to s³uszne za-

³oøenie. Powyøszy pomys³ znalaz³ uzna-

nie w†organizacji zajmuj¹cej siÍ standa-

ryzacj¹ zagadnieÒ zwi¹zanych z†transmis-

j¹ danych - CCITT, ktÛra do ìlegalnychî

generatorÛw zaliczy³a rÛwnieø generato-

ry odwrÛcone. Dla unikniÍcia zamiesza-

nia s¹ one oficjalnie nazywane

reversed.

Mamy wiÍc np.:

X25 standard:

1-0001-0000-0010-0001

X25 reversed:

1-0000-1000-0001-0001

oraz

Elektronika Praktyczna 3/2003

Plik z chomika:

pawello00711

Inne pliki z tego folderu:

CRC doda Ci pewności, cz. 1.pdf (89 KB)
CRC doda Ci pewności, cz. 2.pdf (189 KB)
CRC doda Ci pewności, cz. 3.pdf (104 KB)
CRC doda Ci pewności, cz. 4.pdf (99 KB)
CRC doda Ci pewności, cz. 5.pdf (115 KB)

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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: