/*
 * Copyright (c) International Business Machines Corp., 2014
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

/*
 *   File: hash.h
 * Author: Shaun Wetzstein <shaun@us.ibm.com>
 *  Descr: Various int32 hash functions
 *   Note:
 *   Date: 10/03/10
 */

#ifndef __HASH_H__
#define __HASH_H__

#include <stdint.h>

/* ======================================================================= */

static inline int32_t int32_hash1(int32_t);
static inline int32_t int32_hash2(int32_t);
static inline int32_t int32_hash3(int32_t);

typedef uint32_t(*hash_t) (char *, uint32_t);

static inline uint32_t rs_hash(char *, uint32_t);
static inline uint32_t js_hash(char *, uint32_t);
static inline uint32_t pjw_hash(char *, uint32_t);
static inline uint32_t elf_hash(char *, uint32_t);
static inline uint32_t bkdr_hash(char *, uint32_t);
static inline uint32_t sdbm_hash(char *, uint32_t);
static inline uint32_t djb_hash(char *, uint32_t);
static inline uint32_t dek_hash(char *, uint32_t);
static inline uint32_t bp_hash(char *, uint32_t);
static inline uint32_t fnv_hash(char *, uint32_t);
static inline uint32_t ap_hash(char *, uint32_t);

/* ======================================================================= */

static inline int32_t int32_hash1(int32_t key)
{
	key = ~key + (key << 15);
	key = key ^ (key >> 12);
	key = key + (key << 2);
	key = key ^ (key >> 4);
	key = key * 2057;
	key = key ^ (key >> 16);

	return key;
}

static inline int32_t int32_hash2(int32_t key)
{
	key = (key + 0x7ed55d16) + (key << 12);
	key = (key ^ 0xc761c23c) ^ (key >> 19);
	key = (key + 0x165667b1) + (key << 5);
	key = (key + 0xd3a2646c) ^ (key << 9);
	key = (key + 0xfd7046c5) + (key << 3);
	key = (key ^ 0xb55a4f09) ^ (key >> 16);

	return key;
}

static inline int32_t int32_hash3(int32_t key)
{
	int32_t c2 = 0x27d4eb2d;

	key = (key ^ 61) ^ (key >> 16);
	key = key + (key << 3);
	key = key ^ (key >> 4);
	key = key * c2;
	key = key ^ (key >> 15);

	return key;
}

/* ======================================================================= */

static inline uint32_t rs_hash(char *str, uint32_t len)
{
	uint32_t b = 378551;
	uint32_t a = 63689;
	uint32_t hash = 0;
	uint32_t i = 0;

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

	return hash;
}

static inline uint32_t js_hash(char *str, uint32_t len)
{
	uint32_t hash = 1315423911;
	uint32_t i = 0;

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

	return hash;
}

static inline uint32_t pjw_hash(char *str, uint32_t len)
{
	const uint32_t BitsInUnsignedInt = (uint32_t) (sizeof(uint32_t) * 8);
	const uint32_t ThreeQuarters = (uint32_t) ((BitsInUnsignedInt * 3) / 4);
	const uint32_t OneEighth = (uint32_t) (BitsInUnsignedInt / 8);
	const uint32_t HighBits =
	    (uint32_t) (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
	uint32_t hash = 0;
	uint32_t test = 0;
	uint32_t i = 0;

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

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

	return hash;
}

static inline uint32_t elf_hash(char *str, uint32_t len)
{
	uint32_t hash = 0;
	uint32_t x = 0;
	uint32_t i = 0;

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

	return hash;
}

static inline uint32_t bkdr_hash(char *str, uint32_t len)
{
	uint32_t seed = 131;	/* 31 131 1313 13131 131313 etc.. */
	uint32_t hash = 0;
	uint32_t i = 0;

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

	return hash;
}

static inline uint32_t sdbm_hash(char *str, uint32_t len)
{
	uint32_t hash = 0;
	uint32_t i = 0;

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

	return hash;
}

static inline uint32_t djb_hash(char *str, uint32_t len)
{
	uint32_t hash = 5381;
	uint32_t i = 0;

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

	return hash;
}

static inline uint32_t dek_hash(char *str, uint32_t len)
{
	uint32_t hash = len;
	uint32_t i = 0;

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

static inline uint32_t bp_hash(char *str, uint32_t len)
{
	uint32_t hash = 0;
	uint32_t i = 0;

	for (i = 0; i < len; str++, i++) {
		hash = hash << 7 ^ (*str);
	}

	return hash;
}

static inline uint32_t fnv_hash(char *str, uint32_t len)
{
	const uint32_t fnv_prime = 0x811C9DC5;
	uint32_t hash = 0;
	uint32_t i = 0;

	for (i = 0; i < len; str++, i++) {
		hash *= fnv_prime;
		hash ^= (*str);
	}

	return hash;
}

static inline uint32_t ap_hash(char *str, uint32_t len)
{
	uint32_t hash = 0xAAAAAAAA;
	uint32_t i = 0;

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

	return hash;
}

/* ======================================================================= */

#endif				/* __HASH_H__ */