Re: ipv4: Simplify ARP hash function.

From: Michał Mirosław <redacted>
Date: Fri, 8 Jul 2011 21:39:18 +0200

With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.

Ok, I'm convinced, thanks :-)

--------------------
#include <stdlib.h>
#include <stdio.h>

int hashfn(unsigned int key, unsigned int rnd)
{
	unsigned int x = key ^ rnd;

	x ^= (x >> 8) ^ (x >> 16) ^ (x >> 24);

	return x & 0xff;
}

int count[256];

unsigned int collide(unsigned int key)
{
	unsigned int b0 = key >> 24;
	unsigned int b1 = (key >> 16) & 0xff;
	unsigned int b2 = (key >> 8) & 0xff;

	key &= ~0xff;
	key |= (b0 ^ b1 ^ b2);

	return key;
}

int main(int argc, char **argp)
{
	unsigned int rnd = atoi(argp[1]);
	unsigned int i;

	for (i = 0; i < (64 * 1024); i++) {
		unsigned int key = i << 8;
		unsigned int hash;

		key = collide(key);
		hash = hashfn(key, rnd);
		printf("%u: %u\n", key, hash);
		count[hash]++;
	}
	for (i = 0; i < 256; i++)
		printf("COUNT[%3u]=%3u\n", i, count[i]);
	return 0;
}