crc32 na crc16

[DRAKE]

Ahoj
Mám mikroprocesor od STMka, který umí hardwarově počítat 32 bitové CRC. Já potřebuji do své aplikace pouze 16 bitové. Je možné vzít z těch 32 bitů jenom prvních šestnáct a použít to a poté při ověřování zkontrolovat nulovost opět jenom těch prvních šestnácti bitů? Bude to fungovat jako spávné 16 bitové CRC?.

Děkuji za odpověď

[Panda38]

Rozhodně. Správné CRC má charakter náhodného čísla a tak každá jeho část je náhodným číslem a lze tedy použít k ověření. Jen bude větší šance na chybu a nebude to zřejmě normalizované.

[Andrea]

CRC má charakter náhodného čísla? Od kdy?
CRC je zbytek po dělení konkrétního polynomu konkrétním polynomem a tudíž na něm není nic náhodného.

[Panda38]

Sice je to trochu off topic, tak se omlouvám DRAKE za vsuvku, ale zrovna jsem teď dělal CRC-CCITT XModem. Je to málo známý výpočet a je to škoda, má krátký kód a rychlost srovnatelnou s tabulkou (správnost výpočtu jsem ověřil srovnáním s tabulkovým výpočtem). Asm je sice pro AVR, ale třeba se to může někomu hodit.

Kód: Vybrat vše

/*-----------------------------------------------------------------------------
                        Calculate CRC-CCITT, 1 byte
-----------------------------------------------------------------------------*/

u16 Crc1(u16 crc, u8 data)
{

#ifdef USE_ASM

	asm (

	/* crc = (crc >> 8) | (crc << 8); */
	"mov	__tmp_reg__,%B0"	"\n\t"
	"mov	%B0,%A0"		"\n\t"

	/* crc ^= data; */
	"eor	__tmp_reg__,%1"		"\n\t"

	/* crc ^= (crc & 0xff) >> 4; */
	"mov	%A0,__tmp_reg__"	"\n\t"
	"swap	%A0"			"\n\t"
	"andi	%A0,0x0f"		"\n\t"
	"eor	__tmp_reg__,%A0"	"\n\t"

	/* crc ^= crc << 12; */
	"mov	%A0,__tmp_reg__"	"\n\t"
	"swap	%A0"			"\n\t"
	"andi	%A0,0xf0"		"\n\t"
	"eor	%B0,%A0"		"\n\t"

	/* crc ^= (crc & 0xff) << 5; */
	"mov	%A0,__tmp_reg__"	"\n\t"
	"swap	%A0"			"\n\t"
	"lsl	%A0"			"\n\t"
	"andi	%A0,0xe0"		"\n\t"
	"eor	%A0,__tmp_reg__"	"\n\t"
	"lsr	__tmp_reg__"		"\n\t"
	"lsr	__tmp_reg__"		"\n\t"
	"lsr	__tmp_reg__"		"\n\t"
	"eor	%B0,__tmp_reg__"	"\n\t"

	: "+r" (crc)
	: "r" (data)
	);

	return crc;

#else /* USE_ASM */

	crc = (crc >> 8) | (crc << 8);
	crc ^= data;
	crc ^= (crc & 0xff) >> 4;
	crc ^= crc << 12;
	crc ^= (crc & 0xff) << 5;
	return crc;

#endif /* USE_ASM */
}

/*-----------------------------------------------------------------------------
                      Calculate CRC-CCITT (XModem)
-----------------------------------------------------------------------------*/
/* Sample: 0xFC 0x05 0x4A -> 0x8048 */
#define CRC_INIT 0

u16 Crc(const void* buf, int len)
{
	u16 crc = CRC_INIT;
	const u8* s = (const u8*)buf;

	for (; len > 0; len--)
	{
		crc = Crc1(crc, *s++);
	}
	return crc;
}

[Panda38]

CRC má charakter náhodného čísla? Od kdy?
CRC je zbytek po dělení konkrétního polynomu konkrétním polynomem a tudíž na něm není nic náhodného.

Samozřejmě to není náhodné číslo!

Má vzhled náhodného čísla. Správné CRC vypadá při změně kontrolovaného obsahu tak, že se změní docela podstatně a na pohled jakoby náhodně. Jistě není moc dokonalé CRC, když při změně bitu 0 v datech se změní jen bit 0 v CRC.

Oříznutí 32 na 16 bitů by asi nebylo dobré např. u metody XOR + rotace (nebo u prostého součtu), protože tam se změna v datech projeví jen na 1 bitu, ale CRC-32 je dostatečně náhodný (pro Andreu proměnlivý ) aby se to dalo oříznout.

[procesor]

http://www.lammertbies.nl/comm/info/crc ... ation.html
nebude stačiť.

[DRAKE]

Jaká je vlastně detekční schopnost 16 bitového CRC s obecným polynomem.