Pomalutku, powolutku przymierzam się do obsługi kart SD. Stwierdziłem, że dobrze będzie mieć działające CRC. Niestety wszystko co znalazłem w internecie to jakaś czarna magia i miliony wzorów, a nic prosto wyjaśnionego co i jak po kolei zrobić, żeby "było dobrze".

I gdybym nie znalazł tego: http://www.maximintegrated.com/app-notes/index.mvp/id/3969 to chyba pogryzłbym stykówkę

A teraz spróbuję wyjaśnić jak obsłużyć CRC najprościej jak się da

Co to jest CRC?
Są to nadmiarowe bity danych dodawane do właściwych, dzięki którym można z wysokim prawdopodobieństwem stwierdzić integralność tychże bitów.
"Standard" CRC określa sposób obliczania tych nadmiarowych bitów, a jego podtypy (CRC7 / CRC16 / CRC8) określają jego dalsze parametry.

Czym się różni CRC7 od CRC16?
Różni się ilością nadmiarowych bitów (7/16). Wymusza to różną długość rejestru przesuwnego oraz klucza (mądrzy ludzie nazywają to wielomianem, cholera wie dlaczego ).

Co to jest rejestr przesuwny?
Jest to miejsce gdzie będziemy obliczać nasze CRC. Można to porównać do rejestru SPDR w SPI. Nowy bit jaki chcemy dodać do sumy wchodzi do LSB, cały rejestr jest przesuwany, a MSB traci miejsce w rejestrze, ale w zależności od jego wartości będziemy robić XORowanie rejestru kluczem.

Co to jest klucz?
Klucz jest to stała wartość dla danego podtypu CRC, którą w pewnej sytuacji XORuję się rejestr. Niektóre podtypy mają tą samą ilość bitów, ale różne klucze, powoduje to uzyskanie różnych sum kontrolnych dla tych samych danych.

A teraz zaimplementujmy co trzeba

Inicjacja - "Zacznijmy od początku..."
Inicjacja polega jedynie na wyzerowaniu rejestru. Jeżeli podtyp się zmienił należy dodatkowo podać jego parametry.

Dodajemy bit - "Weź się posuń, a jak się nie mieścisz to wypad"
Jako, że bit jest najmniejszą jednostką niosącą informację, to jego dodanie opiszę. Nie ma sensu budować piramidy od czubka
Bit danych których sumę kontrolną chcemy obliczyć wpisujemy do LSB rejestru. Poprzednią wartość rejestru przesuwamy "w lewo" / "w stronę MSB" / "<<1". Jeżeli bit który zrobił "wypad" (poprzednie MSB) to 1 to cały rejestr XORujemy kluczem. Jeżeli było to 0 to nie robimy nic.

Finalizowanie obliczeń - "Wszystko dobre co się dobrze kończy"
Kiedy dodaliśmy już wszystkie dane, których sumę chcemy obliczyć, musimy jeszcze dodać tyle bitów '0' ile wynosi wielkość rejestru. Traktujemy je oczywiście jako zwykłe dane (jak przy dodawaniu bitów). I to wszystko! W rejestrze czeka na nas nasze wyczekiwane CRC

crc.h


crc.c

_________________
Nie pisz komentarzy - dobry kod komentuje się sam.

A tam, a tam , cudze chwalicie swego nie znacie , a to czytałeś - http://forum.atnel.pl/post42077.html#p42077

_________________
pozdrawiam
phill2k

No dokładnie ja też się zdziwiłem bo już jeden tłusty poradnik leży na forum ale jak to mówią od przybytku głowa nie boli

_________________
zapraszam na blog: http://www.mirekk36.blogspot.com (mój nick Skype: mirekk36 ) [ obejrzyj Kurs EAGLE ] [ mój kanał YT TV www.youtube.com/mirekk36 ]

phill2k: Tak, czytałem. I muszę przyznać, że wiedzy jest ogrom. Niestety nie tego potrzebowałem, kiedy chciałem zaimplementować standard . Kiedy muszę zaimplementować z góry narzuconą technologię to niestety nie interesuje mnie jej etymologia, sens (no, tutaj obchodziła, ale jest oczywista), wydajność/sprawność... tylko chce wiedzieć co muszę zrobić, żeby "było dobrze".

Wiedza tam zawarta jest naprawdę bardzo ciekawa, ale jest jej za dużo... Mnie czytanie tego poradnika wprawiło jedynie w frustrację. Potrzebowałem jedynie zaimplementować CRC, a czytałem o jakiś metodach przy słowie dziesiętnym, co to jest XOR... a na końcu metody były, tylko że było ich z ~5 i nie wiedziałem którą wybrać.

Z kolei dokument Maxima w rozdziale "Cyclic Redundancy Check" zawierał to (i jedynie to) czego potrzebowałem, aby zrozumieć co mam zrobić, aby dobrze zaimplementować CRC. I to on do mnie trafił, kiedy poradnik mg101 niestety tego nie potrafił

-- 12 sie 2013, o 11:51 --

Optymalizacja przez tablicowanie
Metoda bit-po-bicie jest metodą najprostszą w implementacji, zajmującą najmniej FLASHa oraz najwolniejszą (no bo nic w życiu nie może być proste ). Obliczanie CRC można przyśpieszyć poprzez przygotowanie tablicy w której będziemy mieć wartość z którą będziemy XORować rejestr w zależności od wartości bitów, które robią "wypad".

Wzorem:
Bcrc = Bo + Bp
gdzie:
Bcrc - ilość bitów rejestru CRC
Bo - ilość bitów, których "wypad" będziemy optymalizować (od MSB do LSB)
Bp - bity, które pozostaną w rejestrze (od LSB do MSD)

Należy pamiętać, że nie interesuje nas wartość bitów Bp, a jedynie wartość z jaką będą one XORowane.

Pseudokodem C można zapisać to tak:
Bcrc=0bBoBp;

Mechanizm optymalizacji opiera się na tym, że jeżeli mamy 16bitowe CRC i wprowadzamy do niego bajt (8bitów) to sekwencja XORowania rejestru kluczem jest zależna jedynie od najstarszych 8bitów rejestru (czyli tych, które zrobią "wypad"). Sekwencję tą można zoptymalizować do postaci:
XORoptymalizacji=(XOR0<<0)^(XOR1<<1)^(XOR2<<2)........

W praktyce polega to na stablicowaniu wszystkich możliwości bitów Bo za pomocą następującego algorytmu:
1. Ustawiamy rejestr CRC na wartość:
Bo - obecnie sprawdzana wartość
Bp - wszystkie na zero
2. Dodajemy do rejestru tyle "0" ile jest Bo (tak jak zwykłe dane)
3. W rejestrze czeka na nas nasz XORoptymalizacji

Podany algorytm realizuje poniższa funkcja:

Przed jej wywołaniem inicjalizujemy bibliotekę funkcją crc_init(...), a następnie wywołujemy naszą nową funkcję podając jako parametr ilość bitów które chcemy optymalizować.
Mądrze będzie wyrzucić wyliczone wartości na jakiś terminal, aby wygodnie skopiować je do kodu programu.

Skoro mamy już mamy naszą tablicę z wyliczonymi sekwencjami XORowania rejestru (zastępującą klucz w metodzie bit-po-bicie) musimy jeszcze przerobić funkcję dodającą bajt do CRC, tak aby była w stanie wykorzystać nową optymalizację

Zakładając, że będziemy korzystać tylko z CRC16 i przygotowaliśmy tablicę dla Bo=8, funkcja może wyglądać tak:

Czyli do rejestru jest dodawany nowy bajt, a potem rejestr jest XORowany wartością zapisaną pod indeksem tablicy będącym bajtem, który zaliczył "wypad" z rejestru.

Kilka właściwości:
1. Możliwe jest wykorzystanie tablicy przygotowanej dla n bitów podczas dodawania m<=n bitów.
Dowód
Bo_m=3
Bo_n=5

Stan wejściowy CRC (przy generowaniu tablic dla takich ilości bitów i wartości bitów Bo = 3 (0b011)), rejestr CRC 8 bitowy:
CRC_m=0b01100000; // 3x"0"
CRC_n=0b00011000; // 5x"0"

Po dodawaniu zer tak długo, aż następnym bitem, który zrobi "wypad" będzie "1" uzyskamy
CRC_m=0b11100000; // 2x"0" - wsunęliśmy 1 bit
CRC_n=0b11100000; // 2x"0" - wsunęliśmy 3 bity, wartości rejestrów zrównały się

2. Możliwe jest stosowanie tablicy optymalizacji obliczonej dla Klucza1, dla Klucza2, jeżeli K2 ma mniej bitów niż K1 i ich wartości są identyczne z tymi klucza K1 (aż do końca bitów K2, potem bez znaczenia).

3. Szybkość konwersji skaluje się prawie liniowo do ilości bitów optymalizacji:
Szybkość=Szybkość_bit_po_bicie*Bo
Zajętość pamięci niestety rośnie wykładniczo:
FLASH=(rozmiar_rejestru)*(2^Bo)

Nowe kody:
bCRCnoInit.h (kompilator narzekał na niewykorzystane definicje i deklaracje)


bCRC.h




Tablica wartości dla CRC16 do wykorzystania przy kartach SD w bonusie

No i kilka fotek z pogaduszek z kartą
F_CPU=8MHz
SPI=F_CPU/2 (czyli do oporu )

Dla transmisji bajtu T1-T2 to czas transmisji SPI, width to czas obliczeń (w większości).
Dla transmisji bloku T1-T2 to czas faktycznego przesyłania bloku, a width zawiera do tego "prolog" i "epilog" transmisji.

Bit-po-bicie


Optymalizacja 4bitowa


Optymalizacja 8bitowa


W kodach jest jeszcze metoda uniwersalna, ale jak to metody uniwersalne mają w zwyczaju, jej szybkość jest taka, że żal pokazywać (dla 8 bitów optymalizacji ~połowa czasu bit-po-bicie)...

Na zakończenie chciałbym podziękować Fredkowi za analizator stanów, bez niego nic nie byłoby takie proste

_________________
Nie pisz komentarzy - dobry kod komentuje się sam.