Re: JFFS3 & performance

["Jörn Engel" <joern@wohnheim.fh-wedel.de>]

On Wed, 22 December 2004 13:36:47 +0000, Artem B. Bityuckiy wrote:
> 
> I decided to write a test to experimentally check the CRCs speed.

Looks good.  Thanks.

> For now I have added only CRCs which are in linux/lib. They do forward CRC 
> check of course.

How about adding adler32 and possibly this algorithm?  Engel32
(missing a better name) is basically adler32, but instead of a
modula-operation, it mirrors one of the two checksums (last bit
becomes first, etc.) and XORs both.

Doesn't have any measurable effect on i386.  Leaving out any of the
five mirror rounds makes the algorithm lightly worse than adler32 in
my hash-table test.  Maybe on some cpu either the modulo or the
mirroring is much slower.

uint32_t engel32(uint32_t engel, const void *_s, size_t len)
{
	const char *s = _s;
	uint32_t sum=engel, prod=engel;
	for (; len>=4; len-=4, s+=4) {
		sum += s[0];
		prod += sum;
		sum += s[1];
		prod += sum;
		sum += s[2];
		prod += sum;
		sum += s[3];
		prod += sum;
	}
	for (; len; len--, s++) {
		sum += *s;
		prod += sum;
	}
	sum = (sum&0x0000ffff)<<16^ (sum&0xffff0000)>>16;
	sum = (sum&0x00ff00ff)<<8 ^ (sum&0xff00ff00)>>8;
	sum = (sum&0x0f0f0f0f)<<4 ^ (sum&0xf0f0f0f0)>>4;
	sum = (sum&0x33333333)<<2 ^ (sum&0xcccccccc)>>2;
	sum = (sum&0x55555555)<<1 ^ (sum&0xaaaaaaaa)>>1;
	prod ^= sum;
	return prod;
}

Jörn

-- 
Victory in war is not repetitious.
-- Sun Tzu