#define _GNU_SOURCE
#include <string.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <net/if.h>

typedef unsigned int u32;
typedef unsigned char u8;

#define __jhash_mix(a, b, c) \
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8); \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12);  \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5); \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}

/* The golden ration: an arbitrary value */
#define JHASH_GOLDEN_RATIO	0x9e3779b9

/* The most generic version, hashes an arbitrary sequence
 * of bytes.  No alignment or length assumptions are made about
 * the input key.
 */
static inline u32 jhash(const void *key, u32 length, u32 initval)
{
	u32 a, b, c, len;
	const u8 *k = key;

	len = length;
	a = b = JHASH_GOLDEN_RATIO;
	c = initval;

	while (len >= 12) {
		a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24));
		b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24));
		c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24));

		__jhash_mix(a,b,c);

		k += 12;
		len -= 12;
	}

	c += length;
	switch (len) {
	case 11: c += ((u32)k[10]<<24);
	case 10: c += ((u32)k[9]<<16);
	case 9 : c += ((u32)k[8]<<8);
	case 8 : b += ((u32)k[7]<<24);
	case 7 : b += ((u32)k[6]<<16);
	case 6 : b += ((u32)k[5]<<8);
	case 5 : b += k[4];
	case 4 : a += ((u32)k[3]<<24);
	case 3 : a += ((u32)k[2]<<16);
	case 2 : a += ((u32)k[1]<<8);
	case 1 : a += k[0];
	};

	__jhash_mix(a,b,c);

	return c;
}


/* Name hashing routines. Initial hash value */
/* Hash courtesy of the R5 hash in reiserfs modulo sign bits */
#define init_name_hash()		0

/* partial hash update function. Assume roughly 4 bits per character */
static inline unsigned long
partial_name_hash(unsigned long c, unsigned long prevhash)
{
	return (prevhash + (c << 4) + (c >> 4)) * 11;
}

/*
 * Finally: cut down the number of bits to a int value (and try to avoid
 * losing bits)
 */
static inline unsigned long end_name_hash(unsigned long hash)
{
	return (unsigned int) hash;
}

/* Compute the hash for a name string. */
static inline unsigned int
full_name_hash(const char *name, unsigned int len)
{
	unsigned long hash = init_name_hash();
	while (len--)
		hash = partial_name_hash(*name++, hash);
	return end_name_hash(hash);
}

unsigned int dev_name_hash_new17(const char *name)
{
	unsigned hash = 0;
	int len = strnlen(name, IFNAMSIZ);
	int i;

	for (i = 0; i < len; ++i)
		hash = 17 * hash + name[i];
	return hash;
}

unsigned int dev_name_hash_new31(const char *name)
{
	unsigned hash = 0;
	int len = strnlen(name, IFNAMSIZ);
	int i;

	for (i = 0; i < len; ++i)
		hash = 31 * hash + name[i];
	return hash;
}

unsigned int dev_name_hash_orig(const char *name)
{
	return full_name_hash(name, strnlen(name, IFNAMSIZ));
}

unsigned int dev_name_hash_jhash(const char *name)
{
	return jhash(name, strnlen(name, IFNAMSIZ), 0);
}

typedef unsigned int (*dev_hash_name)(const char *name);

dev_hash_name hfn[] = {
	dev_name_hash_orig,
	dev_name_hash_jhash,
	dev_name_hash_new17,
	dev_name_hash_new31,
};

struct hocs {
	unsigned value;
	int occurences;
};

#if 0
#define debug(x...) printf(x)
#else
#define debug(x...) 
#endif

int main(int argc, char **argv)
{
	char dev_name[64];
	int no, htype, i, j, score, hbits;
	unsigned *h;
	/* stores hash elements by value and number of occurences */
	struct hocs *hocs;

	if (argc != 5) {
		fprintf(stderr, "syntax: dev_name_hash prefix no_of_names hash_type hash_bits\n");
		return -1;
	}

	no = atoi(argv[2]);
	if (no <= 0) {
		fprintf(stderr, "invalid number: %d\n", no);
		return -1;
	}

	htype = atoi(argv[3]);
	if (htype < 0 || htype >= sizeof(hfn)) {
		fprintf(stderr, "invalid hash type: %d\n", htype);
		return -1;
	}

	hbits = atoi(argv[4]);
	if (hbits <= 0) {
		fprintf(stderr, "invalid hash bits: %d\n", hbits);
		return -1;
	}
	
	h = malloc(no * sizeof(unsigned));

	for(i = 0; i < no; i++) {
		snprintf(dev_name, sizeof(dev_name), "%s%d", argv[1], i);
		h[i] = hfn[htype](dev_name) & ((1 << hbits) - 1);
		debug("h[i] = %x\n", h[i]);
	}

	hocs = malloc(no * sizeof(struct hocs));
	memset(hocs, 0, no * sizeof(unsigned));

	/* find occurences */
	for(i = 0; i < no; i++) {
		unsigned hash, dup;

		hash= h[i];
		dup = 0;
		hocs[i].value = hash;
		
		/* did we count this value already? */
		for(j = 0; j < i; j++) {
			if (i == j)
				continue;
			if (hocs[j].value == hash) {
				dup = 1;
				break;
			}
		}
		if (dup)
			continue;

		hocs[i].occurences = 1;

		for(j = 0; j < no; j++) {
			if (i == j)
				continue;
			if (hash == h[j])
				hocs[i].occurences++;
		}
	}

	/* the score is the number of iterations required to find each element
	   once */
	score = 0;
	for(i = 0; i < no; i++) {
		debug("hocs[%d] value = %x occurences = %d\n", i, hocs[i].value, hocs[i].occurences);
		score += hocs[i].occurences * (hocs[i].occurences + 1) / 2;
	}

	printf("score %d\n", score);

	return 0;
}