Jak obliczyć CRC z wielomianem (x^24 + 4x^3 + 3x + 1) w procesorach XMEGA?

Mon Feb 14, 2011 2:25 pm   

XMEGA liczy CRC z wielomianem: x^24+4x^3+3x+1
http://www.atmel.com/dyn/resources/prod_documents/doc8077.pdf
strona 366.

Trochę próbowałem poszukać, ale wszędzie znajduję opisy CRC dla wielomianów,
które przy wszystkich potęgach x mają albo 0 albo 1, lub jakieś czysto
matematyczne wywody, bez wystarczająco prostego przełożenia na algorytm.

Wie ktoś może gdzie znaleźć opis jak to się liczy (jakiś przykład algorytmu)
?
P.G.

Mon Feb 14, 2011 10:17 pm   

W dniu 2011-02-14 14:25, Piotr Gałka pisze:

Zobacz w źródłach freemodbus.


--
Pozdrawiam
MD

Mon Feb 14, 2011 10:45 pm   

W dniu 2011-02-14 22:17 Mario napisał(a):


Tyle że w dokumentacji Atmela jest błąd i w rzeczywistości CRC jest
liczone wg bardziej powszechnego wzoru:

x^19 + x^4 + x^3 + x^1 + 1

http://www.avrfreaks.net/index.php?name=PNphpBB2&file=printview&t=29418

/*
* The Xmega manual Rev G lists the CRC Polynomial
* as: x^24 + 4x3 + 3x +1.
*
* Based on some untested code supplied by avr(at)atmel.com,
* I believe the correct Polynomial is:
* x^19 + x^4 + x^3 + x^1 + 1
*
* At any rate after cleaning up their code issues, the following C
* code generates the same values as the XMega 128A1 hardware.

To by chyba zamykało problem. W okolicy tego wpisu na forum AVRFreaks
jest podany link do źródeł funkcji obliczającej poprawnie CRC (tzn. z
wynikiem identycznym jak ATxmega).

--
Adam Dybkowski
http://dybkowski.net/

Uwaga: przed wysłaniem do mnie maila usuń cyfry z adresu.

Mon Feb 14, 2011 10:47 pm   

On Mon, 14 Feb 2011 14:25:44 +0100, Piotr Gałka wrote:

cos mi sie widzi ze i tak trzeba bedzie prosic Atmela o wyjasnienie,
ba tam chyba wiecej szczegolow jest istotnych.

podejrewam ze w kluczowym momencie trzeba cos co przesunac o dwa bity
(4) albo o jeden i xorowac z oryginalem (razem 3).

J.

Tue Feb 15, 2011 9:31 am   

Użytkownik "Adam Dybkowski" <adybkows12@45wp.pl> napisał w wiadomości
news:ijc7pv$hc5$1@news.onet.pl...

Dzięki.
P.G.

Tue Feb 15, 2011 1:20 pm   

Użytkownik "Adam Dybkowski" <adybkows12@45wp.pl> napisał w wiadomości
news:ijc7pv$hc5$1@news.onet.pl...

Może komuś się przyda moja wersja tego CRC:

dword crcXmega(byte *buf,dword n,dword crc)
{
for(n>>=1;n--;buf+=2)crc=(crc<<1)^*(word*)buf^((crc&0x800000)?0x80001B:0);
return crc&0xFFFFFF;
}


Wynik zgodził mi się dla wszystkich sum liczonych przez XMEGA po skasowaniu
(3 wyniki) i po wpisaniu programu z bootloaderem (kolejne 3).
Na maszynie mającej odwrotną kolejność bajtów w word mój zapis nie zadziała.

Nie wnikałem jak to działa bez obracania 16 razy (bo 2 bajty za jednym
ruchem) po bicie, ale sądzę, że przyczyną jest duża odległość między bitem
x^19 a następnymi. I tak brakuje mi gdzieś przesunięcia o 8 w jedną albo o
16 w drugą.
Zastanawia mnie też to, że do XOR użyta jest liczba, która by odpowiadała
zapisowi x^23 + x^4 + x^3 + x^1 + 1.
Czy brak obracania może mieć związek z zastąpieniem x^19 przez x^23. Gdyby
różnica była 8, ale jest 4.
Mam podejrzenie, że to crc tak na prawdę nie jest opisane żadnym z tych
wielomianów.
P.G.

Dla porównania oryginał:
--------------------------
#define CRC32_POLY (0x0080001BUL) /* Polynomial for use with Xmega 'A'
devices */

/* This CRC Routine is the corresponding routine implemented in Xmega
hardware: */
uint32_t CRC_Reference( uint32_t startWord_u32, uint32_t endWord_u32 )
{
uint32_t addr_u32, data_reg_u32, help_a_u32, help_b_u32;
uint32_t crc_reg_u32 = 0;

for( addr_u32 = startWord_u32; addr_u32 <= endWord_u32; addr_u32 += 2 )
{
help_a_u32 = crc_reg_u32 << 1;
help_a_u32 &= 0x00FFFFFEUL; /* Always act as 24-bit variable */

help_b_u32 = crc_reg_u32 & (1UL << 23);

if( help_b_u32 > 0 )
{
help_b_u32 = 0x00FFFFFFUL;
}

data_reg_u32 = SP_ReadWord( addr_u32 );

crc_reg_u32 = (help_a_u32 ^ data_reg_u32) ^ (help_b_u32 & CRC32_POLY);
crc_reg_u32 = crc_reg_u32 & 0x00FFFFFFUL;
}

return( crc_reg_u32 );
}

Tue Feb 15, 2011 3:52 pm   

On Tue, 15 Feb 2011 13:20:04 +0100, Piotr Gałka wrote:



No wlasnie - cos mi to zbyt prosto wyglada.
CRC zwykle wymagalo przetwarzania po bicie, albo dosc skomplikowanych
programow z tablicami. Cos tu mocno uproscili.

J.

Tue Feb 15, 2011 4:48 pm   

Użytkownik "J.F." <jfox_xnospamx@poczta.onet.pl> napisał w wiadomości
news:eb4ll61bl5sg1lot4onaai1culjf0ja88e@4ax.com...

pośredni algorytm oparty na znanej matematycznej metodzie: "zauważmy że".
Wyszło parę obliczeń bez przesuwania po bicie i bez tablic.
Korzystając z bitu parzystości akumulatora dawało się bardzo szybko
policzyć. W moich programach na PC korzystam z tej metody, choć znalezienie
w C bitu parzystości jest chyba najbardziej pracochłonnym jej kawałkiem. Nie
wrzucam z definicji kodu, ale jak ktoś zechce....
Jednak to co jest tu wydaje się za proste, aby mogło być jakimś CRC. A może
ten wielomian co jest w instrukcji jest prawdziwy i po jakichś "zauważmy że"
sprowadza się do przedstawionego obliczenia. A ktoś nie świadomy całości
widząc co jest brane do XOR uznał, że to jest ten wielomian. Widać, że się
bardzo śpieszył, bo nie doliczył się nawet pozycji pierwszej jedynki.
P.G.