Najprostsza funkcja obliczająca CRC32

[Bremse]

----------------------------------------------------------------------------
----
/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];
/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;
/* Make the table for a fast CRC. */
void make_crc_table(void)
{
unsigned long c;
int n, k;
for (n = 0; n < 256; n++) {
c = (unsigned long) n;

dlaczego uzależnia się c od zmiennej iteracji?

for (k = 0; k < 8; k++) {
if (c & 1)

dlaczego sprawdza się "c&1" - na co jest to warunek?

c = 0xedb88320L ^ (c >> 1);

co to robi?

else
c = c >> 1;
}
crc_table[n] = c;
}
crc_table_computed = 1;
}
/* Update a running CRC with the bytes buf[0..len-1]--the CRC
should be initialized to all 1's, and the transmitted value
is the 1's complement of the final running CRC (see the
crc() routine below)). */
unsigned long update_crc(unsigned long crc, unsigned char *buf,
int len)
{
unsigned long c = crc;
int n;
if (!crc_table_computed)
make_crc_table();
for (n = 0; n < len; n++) {
c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);

no tu już wysiadam :-( Do czego to służy?

}
return c;
}
/* Return the CRC of the bytes buf[0..len-1]. */
unsigned long crc(unsigned char *buf, int len)
{
return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
}
----------------------------------------------------------------------------
----
unsigned long mojeCRC32=crc(napis,dlugosc);
Dziala - bawilem sie tym....

Może ktoś mi wytłumaczy jak to działa? Co ten kod robi? Może komuś
będzie się chciało skrobnąć kilka zdań?

[Krzysztof Rudnik]

----------------------------------------------------------------------------

Post by Bremse

----
/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];
/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;
/* Make the table for a fast CRC. */
void make_crc_table(void)
{
unsigned long c;
int n, k;
for (n = 0; n < 256; n++) {
c = (unsigned long) n;

dlaczego uzależnia się c od zmiennej iteracji?

for (k = 0; k < 8; k++) {
if (c & 1)

dlaczego sprawdza się "c&1" - na co jest to warunek?

Najmnlodzy bit c - inaczej czy liczba jest nieparzysta.

Post by Bremse

c = 0xedb88320L ^ (c >> 1);

co to robi?

else
c = c >> 1;
}
crc_table[n] = c;
}
crc_table_computed = 1;
}
/* Update a running CRC with the bytes buf[0..len-1]--the CRC
should be initialized to all 1's, and the transmitted value
is the 1's complement of the final running CRC (see the
crc() routine below)). */
unsigned long update_crc(unsigned long crc, unsigned char *buf,
int len)
{
unsigned long c = crc;
int n;
if (!crc_table_computed)
make_crc_table();
for (n = 0; n < len; n++) {
c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);

no tu już wysiadam :-( Do czego to służy?

Obliczanie CRC :)) 'Doliczenie' kolejnego bajty do sumy.

Post by Bremse

}
return c;
}
/* Return the CRC of the bytes buf[0..len-1]. */
unsigned long crc(unsigned char *buf, int len)
{
return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
}

----------------------------------------------------------------------------

Post by Bremse

----
unsigned long mojeCRC32=crc(napis,dlugosc);
Dziala - bawilem sie tym....

Może ktoś mi wytłumaczy jak to działa? Co ten kod robi? Może komuś
będzie się chciało skrobnąć kilka zdań?

Tak malo formalnie:
Musisz poczytac o wielomianach i operacjach na nich.
Troche trudno wytlumaczyc w paru zdaniach.
Kod wyglada na troche skomplikowany, bo to sa same zabawy bitami.
Latwiej to wyglada w postaci schematu ukladu cyfrowego. CRC sa
wymyslone tak, by latwo je sie realizowalo sprzetowo przy podawaniu
danych szeregowo (a wiec jako ciag bitow), wiec program ktory
robi to samo jest nieco porabany. Uklad ma postac rejestru przesuwajacego
(stad pelno >>) z wieloma miejscami w ktorych wykonuje sie XOR.
CRC to, o ile dobrze pamietam, reszta z dzielenia podanego ciagu,
traktowanego jako wielomian z pewnym wielomianem. Ta
tajemnicza liczba to wlasnie ten wielomian.
Jest kilka standardowo przyjetych do
liczenia roznych wariantow CRC.

A jesli chodzi o program to jest jedna funkcja ktora liczy stosowna
tabelke, tak potem bylo szybciej. Jak chcesz mozesz ta tabelke wprowadzic
samemu. Jak chcesz znalezc ta tabelke gotowa polecam poszukac zrodel
zmodem (rz.c/sz.c/crctab.c). Oto umieszczony tam komentarz - troche
wyjasnia, ale jednak nalezy wczesniej poczytac by wiedziec o co chodzi:
/*
* Copyright (C) 1986 Gary S. Brown. You may use this program, or
* code or tables extracted from it, as desired without restriction.
*/

/* First, the polynomial itself and its table of feedback terms. The */
/* polynomial is */
/* X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 */
/* Note that we take it "backwards" and put the highest-order term in */
/* the lowest-order bit. The X^32 term is "implied"; the LSB is the */
/* X^31 term, etc. The X^0 term (usually shown as "+1") results in */
/* the MSB being 1. */

/* Note that the usual hardware shift register implementation, which */
/* is what we're using (we're merely optimizing it by doing eight-bit */
/* chunks at a time) shifts bits into the lowest-order term. In our */
/* implementation, that means shifting towards the right. Why do we */
/* do it this way? Because the calculated CRC must be transmitted in */
/* order from highest-order term to lowest-order term. UARTs transmit */
/* characters in order from LSB to MSB. By storing the CRC this way, */
/* we hand it to the UART in the order low-byte to high-byte; the UART */
/* sends each low-bit to hight-bit; and the result is transmission bit */
/* by bit from highest- to lowest-order term without requiring any bit */
/* shuffling on our part. Reception works similarly. */

/* The feedback terms table consists of 256, 32-bit entries. Notes: */
/* */
/* The table can be generated at runtime if desired; code to do so */
/* is shown later. It might not be obvious, but the feedback */
/* terms simply represent the results of eight shift/xor opera- */
/* tions for all combinations of data and CRC register values. */
/* */
/* The values must be right-shifted by eight bits by the "updcrc" */
/* logic; the shift must be unsigned (bring in zeroes). On some */
/* hardware you could probably optimize the shift in assembler by */
/* using byte-swap instructions. */


Krzysiek Rudnik

[Bremse]

Post by Krzysztof Rudnik
/*
* Copyright (C) 1986 Gary S. Brown. You may use this program, or
* code or tables extracted from it, as desired without restriction.
*/

Wielkie dzięki, już większość zrozumiałem. Został jeszcze kawałek kodu
którego nie rozumiem. Chodzi mi o to "doliczenie" kolejnego bajtu do
sumy.

c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);

Jak to się ma do algorytmu tworzenia crc-32? Rozumiem, że z tablicą
jest to trochę inaczej, ale chyba są jakieś podobieństwa?

1. Określ ile bajtów obejmuje blok danych.
2. Wypełnij wszystkie bity rejestru CRC wartością 1
3. Pobierz bajt danych
4. Wykonaj operacje XOR na Rejestrze CRC pobranym bajtem
5.Sprawdź czy zerowy bit jest ustawiony
[Jeśli tak]
6. Przesuń w prawo o jeden bit rejestr CRC
7. Wykonaj operacje : rejestr CRC XOR wielomian
[Jeśli nie]
8. Tylko przesuń w prawo o jeden bit
9. Kroki od 5 powtarzaj aż zostanie sprawdzony cały bajt
10. Jeśli są jeszcze dane to pobierz kolejną daną z bloku danych i
wykonaj wszystko od kroku 4
11. Koniec generowania kodu CRC

Jeśli ktoś inny chciałby mi pomóc to też się nie obrażę ;-)