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

K U R S

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

To juø ostatni odcinek kursu. Jak siÍ przekonamy ca³y

trud zwi¹zany z†przedzieraniem siÍ przez meandry

wiedzy, o†ktÛrej nie moøna powiedzieÊ øeby by³a

ìlekkostrawnaî, bardzo siÍ teraz przyda. Procedury

obliczeniowe wydaj¹ siÍ prostsze niø moøna by pocz¹tkowo

przypuszczaÊ. Potwierdzaj¹ to zamieszczone przyk³ady.

W†poprzednim odcinku mieliúmy

okazjÍ przeúledziÊ program napisany

w†jÍzyku C, realizuj¹cy parametrycz-

n¹ metodÍ obliczania CRC. Wszystko

wygl¹da³o doúÊ powaønie. Sama pro-

cedura obliczaj¹ca CRC moøe byÊ -

przy wprowadzeniu pewnych za³oøeÒ

wstÍpnych - znacznie uproszczona.

Oczywiúcie usprawiedliwieniem dla

poprzednich rozwaøaÒ by³ zamiar

stworzenia programu uniwersalnego.

Tym razem zdecydujmy siÍ na jedn¹

(konkretn¹) wersjÍ metody: normaln¹

albo odwrÛcon¹. Jeúli przyjmiemy me-

todÍ normaln¹, bÍdzie to odpowiada-

³o nadaniu zmiennym refin i† refot

wartoúci FALSE. Dla metody odwrÛ-

conej obydwie zmienne maj¹ wartoúÊ

TRUE. Za³oøenia takie pozwalaj¹ zre-

zygnowaÊ z†powyøszych zmiennych

kosztem napisania dwÛch niezaleø-

nych procedur. Nasz generator bÍdzie

zaszyty w†tablicy. Pozosta³e paramet-

ry: INIT i†XOROT mog¹ byÊ zdefinio-

wane jako makra. Procedura 32-bito-

wa, normalna bÍdzie wiÍc wygl¹da³a

jak na list. 3 , odwrÛcona zaú jest

przedstawiona na list. 4 .

Generowanie tablic

wykorzystywanych

w†opisywanych

algorytmach ( Lookup

Table )

My tu sobie gadu-gadu, rozpatruje-

my rÛøne warianty, raz coú skompli-

kujemy, raz coú uproúcimy, a†tym cza-

sem nie mamy najwaøniejszego ele-

mentu naszego programu, czyli tablic

s³uø¹cych do obliczeÒ. Tablice takie

mog¹ byÊ obliczane w†biegu przez

funkcjÍ cm_tab , mog¹ byÊ teø oblicza-

ne wstÍpnie i†wstawiane do kodu pro-

gramu pisanego w†jÍzyku C. ZwrÛÊmy

uwagÍ na to, øe w†kaødym przypadku

bÍd¹ one zaleøa³y jedynie od paramet-

rÛw POLY oraz REFIN (i REFOUT).

Uúciúlaj¹c: jeúli zdecydujemy siÍ na

konkretn¹ metodÍ, to bÍdziemy mogli

wygenerowaÊ jedynie odpowiedni¹

wersjÍ tablicy (normaln¹ lub odwrÛ-

con¹). Na list. 5 przedstawiono pro-

gram generowania 16- lub 32-bitowej

tablicy CRC ( CRC Lookup Table ).

KrÛtkie podsumowanie

poznanych metod

Jako uzupe³nienie dotychczaso-

wych przyk³adÛw na list. 6 i† 7 pre-

zentujemy (w wersji oryginalnej) jesz-

cze dwie wersje gotowych procedur

s³uø¹cych do obliczeÒ CRC. W†tym

momencie w³aúciwie moøemy uznaÊ,

øe dobrnÍliúmy do koÒca kursu. Za-

czynaliúmy od metod najprostszych,

wykorzystuj¹cych niemal naturalne

prze³oøenie teorii na jÍzyk programo-

wania, by w†kolejnych krokach coraz

bardziej je komplikowaÊ. Nie by³a to

jednak sztuka dla sztuki. Zamierze-

niem by³o uzyskanie jak najwiÍkszej

wydajnoúci algorytmÛw, a†wiÍc

i†szybkoúci dzia³ania koÒcowych pro-

gramÛw. Doszliúmy do wniosku, øe

najlepsze rezultaty osi¹gniemy meto-

dami tablicowymi. Ich wad¹ jest nie-

stety zajmowanie sporej czÍúci pamiÍ-

ci programu. Wyboru naleøy dokony-

waÊ w†zaleønoúci od potrzeb i†moøli-

woúci w†konkretnych przypadkach.

Metod sprawdzania poprawnoúci

transmisji obliczaj¹cych CRC nie bÍ-

dziemy zapewne stosowaÊ w†prostych

aplikacjach, w†ktÛrych ewentualna

utrata danych nie bÍdzie stanowi³a

wielkiego problemu. Decyzja o†rezyg-

nacji bÍdzie tym bardziej zasadna,

jeúli bÍdziemy mieli do czynienia

List. 3. Procedura normalna obliczania CRC

unsigned long crc_normal ();

unsigned long crc_normal (blk_adr,blk_len)

unsigned char *blk_adr;

unsigned long blk_len;

{

unsigned long crc = INIT;

while (blk_len--)

crc = crctable[((crc>>24) ^ *blk_adr++) & 0xFFL] ^ (crc << 8);

return crc ^ XOROT;

}

List. 4. Procedura odwrócona obliczania CRC

unsigned long crc_reflected ();

unsigned long crc_reflected (blk_adr,blk_len)

unsigned char *blk_adr;

unsigned long blk_len;

{

unsigned long crc = INIT_REFLECTED;

while (blk_len--)

crc = crctable[(crc ^ *blk_adr++) & 0xFFL] ^ (crc >> 8));

return crc ^ XOROT;

}

Elektronika Praktyczna 5/2003

K U R S

S³owniczek

List. 5. Program generowania 16− lub 32−bitowej tablicy CRC

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

/* Program crctable.c */

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

/* */

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

/* Data: 3 czerwca 1993. */

/* Wersja: 1.0. */

/* Status : Public domain. */

/* */

/* Opis: Program generuje tablicę CRC (lookup table), która może być dołączana */

/* do programów w języku C, obliczających CRC metodą tablicową. */

/* Wygenerowana tablica jest zapisywana w pliku wyjściowym. */

/* Tablice mogą być wykorzystywane w obliczeniach wykorzystujących */

/* "Rocksoft^tm Model CRC Algorithm" opisany w poprzednich */

/* odcinkach kursu. Materiał źródłowy nosi tytuł "A Painless Guide to CRC*/

/* Error Detection Algorithms" */

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

/* Dokument ten jest do pobrania z adresu: */

/* Błąd! Nie określono zakładki. */

/* */

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

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

Suma kontrolna - liczba wyliczona na

podstawie treœci pewnego komunikatu

(rozumianego tutaj jako ci¹g bajtów, nie-

koniecznie reprezentuj¹cego informacje

tekstowe) i do³¹czana do niego w celu

póŸniejszej kontroli prawid³owoœci od-

czytu. Przyk³adowe zastosowania: trans-

misja danych, rejestracja danych na noœ-

nikach magnetycznych itp. S³owo

„suma” niekoniecznie musi byæ rozu-

miane w dos³ownym znaczeniu. Naj-

czêœciej bêd¹ to bardziej wyrafinowane

metody obliczeniowe.

CRC - „Cyclic Redundancy Code” - akro-

nim okreœlaj¹cy metody kontrolowania

poprawnoœci odczytu danych bazuj¹ce

na dzieleniu wielomianów.

Komunikat, wiadomoœæ ( message ) -

dane wejœciowe, których poprawnoœæ

transmisji, zapisu itp. bêdzie sprawdza-

na w podczas odczytywania. Nie ko-

niecznie rozumiane w dos³ownym zna-

czeniu - jako informacja tekstowa. Naj-

czêœciej bêd¹ to struktury zorganizowa-

ne w sekwencje bajtów.

#include <stdio.h>

#include <stdlib.h>

#include "crcmodel.h"

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

/* PARAMETRY TABLICY */

/* ================= */

/* Poniższe parametry określają sposób generowania tablicy. W zależności od */

/* potrzeb należy je zmienić. */

/* */

/* TB_FILE - nazwa pliku wyjściowego */

/* TB_WIDTH - szerokość tablic w bajtach (2 or 4) */

/* TB_POLY - wielomian generujący, musi mieć szerokość taką jak TB_WIDTH */

/* TB_REVER - zmienna określająca, czy ma być użyty algorytm prosty, czy */

/* odwrócony */

/* */

/* Przykład: */

/* #define TB_FILE "crctable.out" */

/* #define TB_WIDTH 2 */

/* #define TB_POLY 0x8005L */

/* #define TB_REVER TRUE */

Generator ( poly ) - robocza nazwa

„wielomianu generuj¹cego”, bêd¹cego

podstawowym parametrem algorytmów

obliczania CRC.

Wielomian generuj¹cy ( polynomial ) -

wielomianem generuj¹cym nazywamy

dzielnik u¿ywany podczas obliczeñ

CRC. Jak ju¿ wiadomo metody stosowa-

ne do tego celu bazuj¹ na operacji dzie-

lenia wielomianów.

Liczba odwrócona (odbita) - liczba bi-

narna, której wszystkie bity zosta³y za-

mienione miejscami dooko³a punku cen-

tralnego, np. liczba 1101 jest odbiciem

liczby 1011.

ROCKSOFT TM MODEL CRC ALGO-

RITHM - sparametryzowany algorytm

obliczania CRC. Poprzez podanie odpo-

wiednich parametrów wejœciowych po-

zwala prowadziæ obliczenia ró¿nymi me-

todami.

Szerokoœæ algorytmu ( width ) - szero-

koœæ algorytmu odpowiada szerokoœci

wielomianu generuj¹cego minus jeden

(czyli jego stopniowi). Np. jeœli generato-

rem jest 11010, szerokoœæ bêdzie równa

4. Szerokoœæ algorytmu jest najczêœciej

wielokrotnoœci¹ liczby 8.

#define TB_FILE "crctable.out"

#define TB_WIDTH 4

#define TB_POLY 0x04C11DB7L

#define TB_REVER TRUE

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

/* Definicje */

#define LOCAL static

FILE *outfile;

#define WR(X) fprintf(outfile,(X))

#define WP(X,Y) fprintf(outfile,(X),(Y))

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

LOCAL void chk_err P_((char *));

LOCAL void chk_err (mess)

char *mess;

{

if (mess[0] != 0 ) {printf("%s\n",mess); exit(EXIT_FAILURE);}

if (ferror(outfile)) {perror("chk_err"); exit(EXIT_FAILURE);}

}

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

LOCAL void chkparam P_((void));

LOCAL void chkparam ()

{

if ((TB_WIDTH != 2) && (TB_WIDTH != 4))

chk_err("chkparam: Width parameter is illegal.");

if ((TB_WIDTH == 2) && (TB_POLY & 0xFFFF0000L))

chk_err("chkparam: Poly parameter is too wide.");

if ((TB_REVER != FALSE) && (TB_REVER != TRUE))

chk_err("chkparam: Reverse parameter is not boolean.");

}

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

LOCAL void gentable P_((void));

LOCAL void gentable ()

{

WR("/*****************************************************************/\n");

WR("/* */\n");

WR("/* CRC LOOKUP TABLE */\n");

WR("/* ================ */\n");

WR("/* The following CRC lookup table was generated automagically */\n");

WR("/* by the Rocksoft^tm Model CRC Algorithm Table Generation */\n");

WR("/* Program V1.0 using the following model parameters: */\n");

WR("/* */\n");

WP("/* Width : %1lu bytes. */\n",

(ulong) TB_WIDTH);

if (TB_WIDTH == 2)

WP("/* Poly : 0x%04lX */\n",

(ulong) TB_POLY);

else

Elektronika Praktyczna 5/2003

K U R S

List. 5. cd.

List. 6. Zestaw procedur do

obliczania CRC

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

crc.c - straightforward 16 bit CRC

by Alberto Ricci Bitti

released to public domain

compatibility notes:

works on little-endian machines only,

assumes 32 bit long integers,

16 bit integers and 8 byte characters

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

/*crc-16 standard root*/

#define POLYNOMIAL 0x8005

WP("/* Poly : 0x%08lXL */\n",

(ulong) TB_POLY);

if (TB_REVER)

WR("/* Reverse: TRUE. */\n");

else

WR("/* Reverse: FALSE. */\n");

WR("/* */\n");

WR("/* For more information on the Rocksoft^tm Model CRC Algorithm, */\n");

WR("/* see the document titled \"A Painless Guide to CRC Error */\n");

WR("/* Detection Algorithms\" by Ross Williams */\n");

WR("/* (ross@guest.adelaide.edu.au.). This document is likely to be */\n");

WR("/* in the FTP archive \"ftp.adelaide.edu.au/pub/rocksoft\". */\n");

WR("/* */\n");

WR("/*****************************************************************/\n");

WR("\n");

switch (TB_WIDTH)

{

case 2: WR("unsigned short crctable[256] =\n{\n"); break;

case 4: WR("unsigned long crctable[256] =\n{\n"); break;

default: chk_err("gentable: TB_WIDTH is invalid.");

}

chk_err("");

{

int i;

cm_t cm;

char *form = (TB_WIDTH==2) ? "0x%04lX": "0x%08lXL";

int perline = (TB_WIDTH==2) ? 8: 4;

cm.cm_width = TB_WIDTH*8;

cm.cm_poly = TB_POLY;

cm.cm_refin = TB_REVER;

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

{

WR(" ");

WP(form,(ulong) cm_tab(&cm,i));

if (i != 255) WR(",");

if (((i+1) % perline) == 0) WR("\n");

chk_err("");

}

WR("};\n");

WR("\n");

WR("/*****************************************************************/\n");

WR("/* End of CRC Lookup Table */\n");

WR("/*****************************************************************/\n");

WR("");

chk_err("");

}

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

main ()

{

printf("\n");

printf("Rocksoft^tm Model CRC Algorithm Table Generation Program V1.0\n");

printf("-------------------------------------------------------------\n");

printf("Output file is \"%s\".\n",TB_FILE);

chkparam();

outfile = fopen(TB_FILE,"w"); chk_err("");

gentable();

if (fclose(outfile) != 0)

chk_err("main: Couldn't close output file.");

printf("\nSUCCESS: The table has been successfully written.\n");

}

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

/* Koniec crctable.c */

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

/*place your own here*/

#define INITIAL_VALUE 0x0000

union

{

unsigned long Whole;

struct

{

unsigned char Data;

unsigned int Remainder;

unsigned char Head;

} Part;

} CRC_buffer;

/*internal use only - puts a byte*/

static void PutCRC(unsigned char b)

{

unsigned char i;

CRC_buffer.Part.Data = b;

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

{

CRC_buffer.Whole = CRC_buffer.Whole << 1;

if (CRC_buffer.Part.Head & 0x01)

CRC_buffer.Part.Remainder ^= POLYNOMIAL;

};

}

/*call this routine with your

own data buffer

yes! it's really that simple!*/

unsigned int CRC (unsigned char *

Data, unsigned int Length)

{

CRC.Part.Remainder = INITIAL_VALUE;

while (Length-- > 0)

PutCRC(*Data++);

PutCRC(0);

return CRC_buffer.Part.Remainder;

}

go rozwi¹zania moøe byÊ uk³ad

74F401 ( Fairchild ), bÍd¹cy generato-

rem/kontrolerem CRC. W†zaleønoúci

od ustawienia bitÛw steruj¹cych,

umoøliwia on pracÍ w†trybach CRC-

16 (X 16 +X 15 +X 2 +1), CRC-16 REVERSE

(X 16 +X 14 +X+1),

X 16 +X 15 +X 13 +X 7 +X 4 +X 2 +X 1 +1, CRC-12

(X 12 +X 11 +X 3 +X 2 +X+1),

X 8 +X 7 +X 5 +X 4 +X+1, LRC-8 (X 8 +1),

CRC-CCITT (X 16 +X 12 +X 5 +1) oraz CRC-

CCITT REVERSE (X 16 +X 11 +X 4 +1). Pe³-

na nota katalogowa uk³adu jest za-

mieszczona na p³ytce CD-ROM do³¹-

czonej do tego numeru EPooL.

z†dobrym, niezaszumionym i†niezak³Û-

conym kana³em transmisyjnym. Przy-

k³adem moøe byÊ choÊby telemetrycz-

na akwizycja danych o†temperaturze

z†czujnika oddalonego od stacji zbie-

raj¹cej dane z†wielu punktÛw. Utrata

jednego pomiaru nie bÍdzie wielk¹

strat¹, gdyø juø w†chwilÍ pÛüniej na-

dejdzie kolejna dana. Dla bezpieczeÒ-

stwa, zobrazowanie (lub dalsza obrÛb-

ka) wynikÛw moøe byÊ poprzedzone

uúrednieniem danych z†kilku trans-

misji. W†ostatecznoúci moøna zastoso-

waÊ duøo prostsz¹ metodÍ, do tego

bardzo ³atw¹ w†praktycznej realizacji,

jak¹ jest kontrola parzystoúci na po-

ziomie transmitowanych bajtÛw. Jeúli

jednak staniemy przed problemem

np. przes³ania duøej liczby danych

z†jednego urz¹dzenia do drugiego lub

zaleøy nam na jak najmniejszym

prawdopodobieÒstwie b³Ídu choÊby

ze wzglÍdu na znaczenie danych, me-

tody CRC mog¹ byÊ nieodzowne.

Czynnikiem wp³ywaj¹cym na podjÍ-

cie decyzji o†stosowaniu kontroli

transmisji moøe byÊ rÛwnieø prowa-

dzenie transmisji danych z†urz¹dzeÒ

w†czasie normalnego ich funkcjono-

wania (on-line). W†krytycznej sytua-

cji moøe siÍ nawet okazaÊ, øe zabrak-

nie nam mocy obliczeniowej mikro-

kontrolera. Trzeba wÛwczas siÍgaÊ po

metody sprzÍtowe. Przyk³adem takie-

Literatura:

1. Boudreau, Steen, ìCyclic Re-

dundancy Checking by Pro-

gramî AFIPS Proceedings, Vol.

39, 1971.

2. Davies, Barber, ìComputer Net-

works and Their Protocolsî J. Wi-

ley &Sons, 1979.

Elektronika Praktyczna 5/2003

K U R S

List. 7. Zestaw procedur do obliczania CRC stosowanych w protokole Modbus

/*>>>>>>>>>>>>>>>>>>>>>>>>> FUNCTION: crc_calc() <<<<<<<<<<<<<<<<<<<<<<<< */

/* */

/* Purpose: Generate the CRC checksum's used by the Modbus Protocol. */

/* */

/* Notes: This routine will simulate a "reverse" CRC Hardware circuit. */

/* (Used in the Modbus Protocol). */

/* */

/* This function uses the CRC-16 16 bit CCITT polynomial. */

/* CRC Polynomial Used: x16+x15+x2+x1 */

/* */

/* Entry: The calling routine must pass an unsigned char (byte) value */

/* to perform the CRC calculations on, and a pointer to an */

/* unsigned integer location for the storage of the generated */

/* CRC word (2 bytes). It is the calling functions */

/* responsibility to initialize the "crc_accum" location to 0xffff */

/* prior to calling this routine for the first time. Only init */

/* the location after the sequence of characters used in the */

/* CRC generation are complete. */

/* */

/* Example: If the character string is: 06 03 0b b9 00 01 */

/* The calculated CRC will be: 7c 56 */

/* (Note: Swap bytes for serial transmission - the */

/* complete transmission sequence will be: */

/* */

/* 06 03 0b b9 00 01 56 7c */

/* <-------- +---+ */

/* Data Flow CRC */

/* */

/* Exit: Location crc_accum will have a 16 bit (two bytes) value of */

/* the new calculated CRC. */

/* */

/* Programmer: Rick Vaughn Eagle Systems, Santa Fe, Texas */

/* */

/* Revisions: 8/26/94 (Orig) ---Rick Vaughn--- */

/* */

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */

void crc_calc(uchar work_data)

{

code uint genpoly = 0xa001; /* Reversed polynomial */

uchar i;

/* Convert the received byte to an integer */

crc_accum = crc_accum ^ (uint)work_data;

for(i=8; i>0; i--)

{

/* Loop 8 times to test each bit of the new character */

if ((crc_accum) & 0x0001)

crc_accum = ((crc_accum) >> 1) ^ genpoly;

else

(crc_accum) >>= 1;

}

3. Higginson, Kirstein, ìOn the Compu-

tation of Cyclic Redundancy Checks

by Programî, The Computer Journal

(British), Vol. 16, No. 1, Feb 1973.

4. McNamara, J. E., ìTechnical As-

pects of Data Communicationî

2 nd Edition, Digital Press, Bed-

ford, Massachusetts, 1982.

5. Marton and Frambs, ìA Cyclic

Redundancy Checking (CRC) Al-

gorithmî, Honeywell Computer

Journal, Vol. 5, No. 3, 1971.

6. Nelson M., ìFile verification us-

ing CRCî, Dr Dobbs Journal, May

1992, str. 64-67.

7. Ramabadran T.V., Gaitonde S.S.,

ìA tutorial on CRC computa-

tionsî, IEEE Micro, Aug 1988.

8. Schwaderer W.D., ìCRC Calculationî,

April 85 PC Tech Journal, str. 118-133.

9. Ward R.K, Tabandeh M., ìError Cor-

rection and Detection, A†Geometric

Approachî, The Computer Journal,

Vol. 27, No. 3, 1984, str. 246-253.

10. Wecker, S., ìA Table-Lookup Al-

gorithm for Software Computation

of Cyclic Redundancy Check

(CRC)î, Digital Equipment Corpo-

ration memorandum, 1974.

Jaros³aw Doliñski, AVT

jaroslaw.dolinski@ep.com.pl

Artyku³ powsta³ na podstawie

publikacji ìA†painless guide to CRC

error detection algorithmsî. Autor

Ross N. Williams. Moøna go znaleüÊ

pod adresem http://www.riccibit-

ti.com/crcguide.htm.

Elektronika Praktyczna 5/2003

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: