====== General purpose hash function algorithms library ====== Variants RS--AP are taken from Arash Partow collection: [[http://www.partow.net/programming/hashfunctions]]. ===== RS Hash Function =====


unsigned int RSHash (char *str, unsigned int len)
{
	unsigned int b = 378551;
	unsigned int a = 63689;
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = hash * a + (unsigned char)(*str);
		a = a * b;
	}
	return hash;
}

===== JS Hash Function =====


unsigned int JSHash (char *str, unsigned int len)
{
	unsigned int hash = 1315423911;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash ^= ((hash << 5) + (unsigned char)(*str) + (hash >> 2));
	}
	return hash;
}

===== P. J. Weinberger Hash Function =====


unsigned int PJWHash (char *str, unsigned int len)
{
	unsigned int BitsInUnsignedInt = (unsigned int) (sizeof (unsigned int) * 8);
	unsigned int ThreeQuarters = (unsigned int) ((BitsInUnsignedInt * 3) / 4);
	unsigned int OneEighth = (unsigned int) (BitsInUnsignedInt / 8);
	unsigned int HighBits = (unsigned int) (0xFFFFFFFF) <<
		(BitsInUnsignedInt - OneEighth);
	unsigned int hash = 0;
	unsigned int test = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = (hash << OneEighth) + (unsigned char)(*str);

		if ((test = hash & HighBits) != 0) {
			hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
		}
	}
	return hash;
}

===== ELF Hash Function =====


unsigned int ELFHash (char *str, unsigned int len)
{
	unsigned int hash = 0;
	unsigned int x = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = (hash << 4) + (unsigned char)(*str);
		if ((x = hash & 0xF0000000L) != 0) {
			hash ^= (x >> 24);
			hash &= ~x;
		}
	}
	return hash;
}

===== BKDR Hash Function =====


unsigned int BKDRHash (char *str, unsigned int len)
{
	unsigned int seed = 131313; /* 31 131 1313 13131 131313 etc.. */
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = (hash * seed) + (unsigned char)(*str);
	}
	return hash;
}

===== SDBM Hash Function =====


unsigned int SDBMHash (char *str, unsigned int len)
{
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = (unsigned char)(*str) + (hash << 6) +
			(hash << 16) - hash;
	}
	return hash;
}

===== DJB Hash Function =====


unsigned int DJBHash (char *str, unsigned int len)
{
	unsigned int hash = 5381;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = ((hash << 5) + hash) + (unsigned char)(*str);
	}
	return hash;
}

===== DEK Hash Function =====


unsigned int DEKHash (char *str, unsigned int len)
{
	unsigned int hash = len;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = ((hash << 5) ^ (hash >> 27)) ^ (unsigned char)(*str);
	}
	return hash;
}

===== AP Hash Function =====


unsigned int APHash (char *str, unsigned int len)
{
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash ^= ((i & 1) == 0) ?
		    ((hash << 7) ^ (unsigned char)(*str) ^ (hash >> 3)) :
		    (~((hash << 11) ^ (unsigned char)(*str) ^ (hash >> 5)));
	}
	return hash;
}

===== LY Hash Function ===== Congruential generator proposed by [[http://leo.yuriev.ru/random | Leonid Yuriev]]. Multiplier constant suggested by M.Lavaux & F.Janssens.


unsigned int LYHash (char *str, unsigned int len)
{
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223;
	}
	return hash;
}

===== ROT13 Hash Function ===== No multiplication, by Serge Vakulenko. Two shifts are converted by GCC 4 to a single rotation instruction.


unsigned int ROT13Hash (char *str, unsigned int len)
{
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash += (unsigned char)(*str);
		hash -= (hash << 13) | (hash >> 19);
	}
	return hash;
}

===== FAQ6 Hash Function ===== From Bob Jenkins Hash Function FAQ: http://burtleburtle.net/bob/hash/hashfaq.html


unsigned int bob_faq6_hash (char *str, unsigned int len)
{
	unsigned int hash = 0;
	unsigned int i = 0;

	for (i = 0; i < len; str++, i++) {
		hash += (unsigned char)(*str);
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}
	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);
	return hash;
}

===== LOOKUP3 Hash Function ===== See http://burtleburtle.net/bob/c/lookup3.c Slightly modified for byte data.


#define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))

#define mix(a,b,c) { \
	a -= c;  a ^= rot (c,  4);  c += b; \
	b -= a;  b ^= rot (a,  6);  a += c; \
	c -= b;  c ^= rot (b,  8);  b += a; \
	a -= c;  a ^= rot (c, 16);  c += b; \
	b -= a;  b ^= rot (a, 19);  a += c; \
	c -= b;  c ^= rot (b,  4);  b += a; }

#define final(a,b,c) { \
	c ^= b; c -= rot (b, 14); \
	a ^= c; a -= rot (c, 11); \
	b ^= a; b -= rot (a, 25); \
	c ^= b; c -= rot (b, 16); \
	a ^= c; a -= rot (c, 4);  \
	b ^= a; b -= rot (a, 14); \
	c ^= b; c -= rot (b, 24); }

unsigned int bob_lookup3_hash (char *str, unsigned int len8)
{
	unsigned int a, b, c;

	/* the key, an array of unsigned int values */
	unsigned int *k = (unsigned int*) str;

	/* the length of the key, in unsigned ints */
	unsigned int length = (len8 + 3) / 4;

	/* tail pad with zeros */
	str [len8] = 0;
	str [len8 + 1] = 0;
	str [len8 + 2] = 0;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + len8;

	/* handle most of the key */
	while (length > 3) {
		a += k[0];
		b += k[1];
		c += k[2];
		mix (a, b, c);
		length -= 3;
		k += 3;
	}

	/* handle the last 3 unsigned ints */
	switch(length) {
	case 3:
		c += k[2];
	case 2:
		b += k[1];
	case 1:
		a += k[0];
		final (a, b, c);
	case 0:
		/* nothing left to add */
		break;
	}
	return c;
}

===== CRC32 Function =====


unsigned int crc32 (char *buf, unsigned int len)
{
	unsigned int crc;

	crc = 0xffffffff;
	while (len--) {
		crc = crc_table [(crc ^ (unsigned char)*buf++) & 0xff] ^ (crc >> 8);
	}
	return crc ^ 0xffffffff;
}