[C] Obliczanie sumy CRC 32


(Marcins2009) #1

Witam !

Potezebuje w moim programie napisać funkcje obliczającą sume CRC 32 z całego pliku. Myślałem nad zrobieniem tego w łopatologiczny sposób(tak jak to się robi na kartce), jednak w miedzy czasie znalazłem coś takiego:

#include 

#include 

#include 


uint32_t

rc_crc32(uint32_t crc, const char *buf, size_t len)

{

	static uint32_t table[256];

	static int have_table = 0;

	uint32_t rem, octet;

	int i, j;

	const char *p, *q;


	/* This check is not thread safe; there is no mutex. */

	if (have_table == 0) {

		/* Calculate CRC table. */

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

			rem = i; /* remainder from polynomial division */

			for (j = 0; j < 8; j++) {

				if (rem & 1) {

					rem >>= 1;

					rem ^= 0xedb88320;

				} else

					rem >>= 1;

			}

			table[i] = rem;

		}

		have_table = 1;

	}


	crc = ~crc;

	q = buf + len;

	for (p = buf; p < q; p++) {

		octet = *p; /* Cast to unsigned octet. */

		crc = (crc >> 8) ^ table[(crc & 0xff) ^ octet];

	}

	return ~crc;

}


int

main()

{

	const char *s = "The quick brown fox jumps over the lazy dog";

	printf("%" PRIX32 "\n", rc_crc32(0, s, strlen(s)));


	return 0;

}

i wydaje mi się to być sensowniejszym(szybszym) rozwiązaniem. Mam jednak jeden problem nie dokońca rozumiem co się dzieję (jaka magia) w tej linijce:

crc = (crc >> 8) ^ table[(crc & 0xff) ^ octet];

Tzn. rozumiem co robi każdy z operatorów, tylko nie wiem na jakiej zasadzie obliczane tu jest crc tj. w miejscu i dlaczego jest negowane przed i po.

Z góry dziękuje komuś kto pomożę mi to zrozumieć lub poleci lepszy sposób na wykonanie tej funkcji.


(Pablo_Wawa) #2

Tutaj masz analogiczny algorytm: http://gnuradio.org/redmine/projects/gnuradio/repository/revisions/1cb52da49230c64c3719b4ab944ba1cf5a9abb92/entry/gr-digital/lib/digital_crc32.cc

i jeszcze jeden: http://4programmers.net/Algorytmy/Obliczanie_sum_kontrolnych_CRC-32

Zamiast trzymać tablicę stałych (przyspiesza to liczne CRC) można ją liczyć (raz) dynamicznie.

Zamiast zaczynać od wartości 0xffffffff (jak jest w dokumentacji) można zanegować wartość 0 i się uzyska to samo.

Na końcu musimy to zrobić bo tak jest w dokumentacji algorytmu.


(Marcins2009) #3

Mógł byś się podzielić linkiem do dokumentacji ?


(Pablo_Wawa) #4

http://www.hackersdelight.org/crc.pdf - jeden z linków podanych na (angielskiej) Wikipedii.


(Marcins2009) #5

Ten pdf rozwiał wszystkie moje wątpliwości. Dziękuje za pomoc :smiley: