// (c) Electronic Arts.  All Rights Reserved.
//
// EATypeOf/internal/hash.h
//
// Implements FNV1 hashing functions (http://www.isthe.com/chongo/tech/comp/fnv/)
// for internal use by EA::Type::TypeOf.  There are two hash functions:
//
//     RuntimeHash      // runtime FNV-1 string hash
//     StaticHash       // compile-time FNV-1 hash (using template metaprogramming)
//
// David Bollo (mailto:dbollo@ea.com)
 
#ifndef EATYPEOF_INTERNAL_HASH_H
#define EATYPEOF_INTERNAL_HASH_H


namespace EA		{
namespace Type		{
namespace internal	{


template <size_t HashBits> class HashConstants;

template <> class HashConstants<32>
{
public:
	static const uint32_t FNV_BASIS = UINT32_C(2166136261);
	static const uint32_t FNV_PRIME = UINT32_C(16777619);
};

template <> class HashConstants<64>
{
public:
	static const uint64_t FNV_BASIS = UINT64_C(14695981039346656037);
	static const uint64_t FNV_PRIME = UINT64_C(1099511628211);
};

template <typename HashType> inline static HashType RuntimeHash(const char* s)
{
	HashType h = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_BASIS);
	while (*s != 0)
	{
		HashType c = static_cast<HashType>(*s);
		h = static_cast<HashType>(h * HashConstants<sizeof(HashType)*8>::FNV_PRIME) ^ c;
		++s;
	}
	return (h) ? h : static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_BASIS);
}

template <typename HashType, int N> class StaticHash_Unrolled;

template <typename HashType> class StaticHash_Unrolled<HashType, 0>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index) { return init; }
};

template <typename HashType> class StaticHash_Unrolled<HashType, 128>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((init 
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]))
		* prime) ^ static_cast<HashType>(s[index + 2]))
		* prime) ^ static_cast<HashType>(s[index + 3]))
		* prime) ^ static_cast<HashType>(s[index + 4]))
		* prime) ^ static_cast<HashType>(s[index + 5]))
		* prime) ^ static_cast<HashType>(s[index + 6]))
		* prime) ^ static_cast<HashType>(s[index + 7]))
		* prime) ^ static_cast<HashType>(s[index + 8]))
		* prime) ^ static_cast<HashType>(s[index + 9]))
		* prime) ^ static_cast<HashType>(s[index + 10]))
		* prime) ^ static_cast<HashType>(s[index + 11]))
		* prime) ^ static_cast<HashType>(s[index + 12]))
		* prime) ^ static_cast<HashType>(s[index + 13]))
		* prime) ^ static_cast<HashType>(s[index + 14]))
		* prime) ^ static_cast<HashType>(s[index + 15]))
		* prime) ^ static_cast<HashType>(s[index + 16]))
		* prime) ^ static_cast<HashType>(s[index + 17]))
		* prime) ^ static_cast<HashType>(s[index + 18]))
		* prime) ^ static_cast<HashType>(s[index + 19]))
		* prime) ^ static_cast<HashType>(s[index + 20]))
		* prime) ^ static_cast<HashType>(s[index + 21]))
		* prime) ^ static_cast<HashType>(s[index + 22]))
		* prime) ^ static_cast<HashType>(s[index + 23]))
		* prime) ^ static_cast<HashType>(s[index + 24]))
		* prime) ^ static_cast<HashType>(s[index + 25]))
		* prime) ^ static_cast<HashType>(s[index + 26]))
		* prime) ^ static_cast<HashType>(s[index + 27]))
		* prime) ^ static_cast<HashType>(s[index + 28]))
		* prime) ^ static_cast<HashType>(s[index + 29]))
		* prime) ^ static_cast<HashType>(s[index + 30]))
		* prime) ^ static_cast<HashType>(s[index + 31]))
		* prime) ^ static_cast<HashType>(s[index + 32]))
		* prime) ^ static_cast<HashType>(s[index + 33]))
		* prime) ^ static_cast<HashType>(s[index + 34]))
		* prime) ^ static_cast<HashType>(s[index + 35]))
		* prime) ^ static_cast<HashType>(s[index + 36]))
		* prime) ^ static_cast<HashType>(s[index + 37]))
		* prime) ^ static_cast<HashType>(s[index + 38]))
		* prime) ^ static_cast<HashType>(s[index + 39]))
		* prime) ^ static_cast<HashType>(s[index + 40]))
		* prime) ^ static_cast<HashType>(s[index + 41]))
		* prime) ^ static_cast<HashType>(s[index + 42]))
		* prime) ^ static_cast<HashType>(s[index + 43]))
		* prime) ^ static_cast<HashType>(s[index + 44]))
		* prime) ^ static_cast<HashType>(s[index + 45]))
		* prime) ^ static_cast<HashType>(s[index + 46]))
		* prime) ^ static_cast<HashType>(s[index + 47]))
		* prime) ^ static_cast<HashType>(s[index + 48]))
		* prime) ^ static_cast<HashType>(s[index + 49]))
		* prime) ^ static_cast<HashType>(s[index + 50]))
		* prime) ^ static_cast<HashType>(s[index + 51]))
		* prime) ^ static_cast<HashType>(s[index + 52]))
		* prime) ^ static_cast<HashType>(s[index + 53]))
		* prime) ^ static_cast<HashType>(s[index + 54]))
		* prime) ^ static_cast<HashType>(s[index + 55]))
		* prime) ^ static_cast<HashType>(s[index + 56]))
		* prime) ^ static_cast<HashType>(s[index + 57]))
		* prime) ^ static_cast<HashType>(s[index + 58]))
		* prime) ^ static_cast<HashType>(s[index + 59]))
		* prime) ^ static_cast<HashType>(s[index + 60]))
		* prime) ^ static_cast<HashType>(s[index + 61]))
		* prime) ^ static_cast<HashType>(s[index + 62]))
		* prime) ^ static_cast<HashType>(s[index + 63]))
		* prime) ^ static_cast<HashType>(s[index + 64]))
		* prime) ^ static_cast<HashType>(s[index + 65]))
		* prime) ^ static_cast<HashType>(s[index + 66]))
		* prime) ^ static_cast<HashType>(s[index + 67]))
		* prime) ^ static_cast<HashType>(s[index + 68]))
		* prime) ^ static_cast<HashType>(s[index + 69]))
		* prime) ^ static_cast<HashType>(s[index + 70]))
		* prime) ^ static_cast<HashType>(s[index + 71]))
		* prime) ^ static_cast<HashType>(s[index + 72]))
		* prime) ^ static_cast<HashType>(s[index + 73]))
		* prime) ^ static_cast<HashType>(s[index + 74]))
		* prime) ^ static_cast<HashType>(s[index + 75]))
		* prime) ^ static_cast<HashType>(s[index + 76]))
		* prime) ^ static_cast<HashType>(s[index + 77]))
		* prime) ^ static_cast<HashType>(s[index + 78]))
		* prime) ^ static_cast<HashType>(s[index + 79]))
		* prime) ^ static_cast<HashType>(s[index + 80]))
		* prime) ^ static_cast<HashType>(s[index + 81]))
		* prime) ^ static_cast<HashType>(s[index + 82]))
		* prime) ^ static_cast<HashType>(s[index + 83]))
		* prime) ^ static_cast<HashType>(s[index + 84]))
		* prime) ^ static_cast<HashType>(s[index + 85]))
		* prime) ^ static_cast<HashType>(s[index + 86]))
		* prime) ^ static_cast<HashType>(s[index + 87]))
		* prime) ^ static_cast<HashType>(s[index + 88]))
		* prime) ^ static_cast<HashType>(s[index + 89]))
		* prime) ^ static_cast<HashType>(s[index + 90]))
		* prime) ^ static_cast<HashType>(s[index + 91]))
		* prime) ^ static_cast<HashType>(s[index + 92]))
		* prime) ^ static_cast<HashType>(s[index + 93]))
		* prime) ^ static_cast<HashType>(s[index + 94]))
		* prime) ^ static_cast<HashType>(s[index + 95]))
		* prime) ^ static_cast<HashType>(s[index + 96]))
		* prime) ^ static_cast<HashType>(s[index + 97]))
		* prime) ^ static_cast<HashType>(s[index + 98]))
		* prime) ^ static_cast<HashType>(s[index + 99]))
		* prime) ^ static_cast<HashType>(s[index + 100]))
		* prime) ^ static_cast<HashType>(s[index + 101]))
		* prime) ^ static_cast<HashType>(s[index + 102]))
		* prime) ^ static_cast<HashType>(s[index + 103]))
		* prime) ^ static_cast<HashType>(s[index + 104]))
		* prime) ^ static_cast<HashType>(s[index + 105]))
		* prime) ^ static_cast<HashType>(s[index + 106]))
		* prime) ^ static_cast<HashType>(s[index + 107]))
		* prime) ^ static_cast<HashType>(s[index + 108]))
		* prime) ^ static_cast<HashType>(s[index + 109]))
		* prime) ^ static_cast<HashType>(s[index + 110]))
		* prime) ^ static_cast<HashType>(s[index + 111]))
		* prime) ^ static_cast<HashType>(s[index + 112]))
		* prime) ^ static_cast<HashType>(s[index + 113]))
		* prime) ^ static_cast<HashType>(s[index + 114]))
		* prime) ^ static_cast<HashType>(s[index + 115]))
		* prime) ^ static_cast<HashType>(s[index + 116]))
		* prime) ^ static_cast<HashType>(s[index + 117]))
		* prime) ^ static_cast<HashType>(s[index + 118]))
		* prime) ^ static_cast<HashType>(s[index + 119]))
		* prime) ^ static_cast<HashType>(s[index + 120]))
		* prime) ^ static_cast<HashType>(s[index + 121]))
		* prime) ^ static_cast<HashType>(s[index + 122]))
		* prime) ^ static_cast<HashType>(s[index + 123]))
		* prime) ^ static_cast<HashType>(s[index + 124]))
		* prime) ^ static_cast<HashType>(s[index + 125]))
		* prime) ^ static_cast<HashType>(s[index + 126]))
		* prime) ^ static_cast<HashType>(s[index + 127]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 64>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((init
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]))
		* prime) ^ static_cast<HashType>(s[index + 2]))
		* prime) ^ static_cast<HashType>(s[index + 3]))
		* prime) ^ static_cast<HashType>(s[index + 4]))
		* prime) ^ static_cast<HashType>(s[index + 5]))
		* prime) ^ static_cast<HashType>(s[index + 6]))
		* prime) ^ static_cast<HashType>(s[index + 7]))
		* prime) ^ static_cast<HashType>(s[index + 8]))
		* prime) ^ static_cast<HashType>(s[index + 9]))
		* prime) ^ static_cast<HashType>(s[index + 10]))
		* prime) ^ static_cast<HashType>(s[index + 11]))
		* prime) ^ static_cast<HashType>(s[index + 12]))
		* prime) ^ static_cast<HashType>(s[index + 13]))
		* prime) ^ static_cast<HashType>(s[index + 14]))
		* prime) ^ static_cast<HashType>(s[index + 15]))
		* prime) ^ static_cast<HashType>(s[index + 16]))
		* prime) ^ static_cast<HashType>(s[index + 17]))
		* prime) ^ static_cast<HashType>(s[index + 18]))
		* prime) ^ static_cast<HashType>(s[index + 19]))
		* prime) ^ static_cast<HashType>(s[index + 20]))
		* prime) ^ static_cast<HashType>(s[index + 21]))
		* prime) ^ static_cast<HashType>(s[index + 22]))
		* prime) ^ static_cast<HashType>(s[index + 23]))
		* prime) ^ static_cast<HashType>(s[index + 24]))
		* prime) ^ static_cast<HashType>(s[index + 25]))
		* prime) ^ static_cast<HashType>(s[index + 26]))
		* prime) ^ static_cast<HashType>(s[index + 27]))
		* prime) ^ static_cast<HashType>(s[index + 28]))
		* prime) ^ static_cast<HashType>(s[index + 29]))
		* prime) ^ static_cast<HashType>(s[index + 30]))
		* prime) ^ static_cast<HashType>(s[index + 31]))
		* prime) ^ static_cast<HashType>(s[index + 32]))
		* prime) ^ static_cast<HashType>(s[index + 33]))
		* prime) ^ static_cast<HashType>(s[index + 34]))
		* prime) ^ static_cast<HashType>(s[index + 35]))
		* prime) ^ static_cast<HashType>(s[index + 36]))
		* prime) ^ static_cast<HashType>(s[index + 37]))
		* prime) ^ static_cast<HashType>(s[index + 38]))
		* prime) ^ static_cast<HashType>(s[index + 39]))
		* prime) ^ static_cast<HashType>(s[index + 40]))
		* prime) ^ static_cast<HashType>(s[index + 41]))
		* prime) ^ static_cast<HashType>(s[index + 42]))
		* prime) ^ static_cast<HashType>(s[index + 43]))
		* prime) ^ static_cast<HashType>(s[index + 44]))
		* prime) ^ static_cast<HashType>(s[index + 45]))
		* prime) ^ static_cast<HashType>(s[index + 46]))
		* prime) ^ static_cast<HashType>(s[index + 47]))
		* prime) ^ static_cast<HashType>(s[index + 48]))
		* prime) ^ static_cast<HashType>(s[index + 49]))
		* prime) ^ static_cast<HashType>(s[index + 50]))
		* prime) ^ static_cast<HashType>(s[index + 51]))
		* prime) ^ static_cast<HashType>(s[index + 52]))
		* prime) ^ static_cast<HashType>(s[index + 53]))
		* prime) ^ static_cast<HashType>(s[index + 54]))
		* prime) ^ static_cast<HashType>(s[index + 55]))
		* prime) ^ static_cast<HashType>(s[index + 56]))
		* prime) ^ static_cast<HashType>(s[index + 57]))
		* prime) ^ static_cast<HashType>(s[index + 58]))
		* prime) ^ static_cast<HashType>(s[index + 59]))
		* prime) ^ static_cast<HashType>(s[index + 60]))
		* prime) ^ static_cast<HashType>(s[index + 61]))
		* prime) ^ static_cast<HashType>(s[index + 62]))
		* prime) ^ static_cast<HashType>(s[index + 63]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 32>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((init 
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]))
		* prime) ^ static_cast<HashType>(s[index + 2]))
		* prime) ^ static_cast<HashType>(s[index + 3]))
		* prime) ^ static_cast<HashType>(s[index + 4]))
		* prime) ^ static_cast<HashType>(s[index + 5]))
		* prime) ^ static_cast<HashType>(s[index + 6]))
		* prime) ^ static_cast<HashType>(s[index + 7]))
		* prime) ^ static_cast<HashType>(s[index + 8]))
		* prime) ^ static_cast<HashType>(s[index + 9]))
		* prime) ^ static_cast<HashType>(s[index + 10]))
		* prime) ^ static_cast<HashType>(s[index + 11]))
		* prime) ^ static_cast<HashType>(s[index + 12]))
		* prime) ^ static_cast<HashType>(s[index + 13]))
		* prime) ^ static_cast<HashType>(s[index + 14]))
		* prime) ^ static_cast<HashType>(s[index + 15]))
		* prime) ^ static_cast<HashType>(s[index + 16]))
		* prime) ^ static_cast<HashType>(s[index + 17]))
		* prime) ^ static_cast<HashType>(s[index + 18]))
		* prime) ^ static_cast<HashType>(s[index + 19]))
		* prime) ^ static_cast<HashType>(s[index + 20]))
		* prime) ^ static_cast<HashType>(s[index + 21]))
		* prime) ^ static_cast<HashType>(s[index + 22]))
		* prime) ^ static_cast<HashType>(s[index + 23]))
		* prime) ^ static_cast<HashType>(s[index + 24]))
		* prime) ^ static_cast<HashType>(s[index + 25]))
		* prime) ^ static_cast<HashType>(s[index + 26]))
		* prime) ^ static_cast<HashType>(s[index + 27]))
		* prime) ^ static_cast<HashType>(s[index + 28]))
		* prime) ^ static_cast<HashType>(s[index + 29]))
		* prime) ^ static_cast<HashType>(s[index + 30]))
		* prime) ^ static_cast<HashType>(s[index + 31]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 16>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((((((((((((((((((((((((((((((init 
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]))
		* prime) ^ static_cast<HashType>(s[index + 2]))
		* prime) ^ static_cast<HashType>(s[index + 3]))
		* prime) ^ static_cast<HashType>(s[index + 4]))
		* prime) ^ static_cast<HashType>(s[index + 5]))
		* prime) ^ static_cast<HashType>(s[index + 6]))
		* prime) ^ static_cast<HashType>(s[index + 7]))
		* prime) ^ static_cast<HashType>(s[index + 8]))
		* prime) ^ static_cast<HashType>(s[index + 9]))
		* prime) ^ static_cast<HashType>(s[index + 10]))
		* prime) ^ static_cast<HashType>(s[index + 11]))
		* prime) ^ static_cast<HashType>(s[index + 12]))
		* prime) ^ static_cast<HashType>(s[index + 13]))
		* prime) ^ static_cast<HashType>(s[index + 14]))
		* prime) ^ static_cast<HashType>(s[index + 15]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 8>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((((((((((((((init 
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]))
		* prime) ^ static_cast<HashType>(s[index + 2]))
		* prime) ^ static_cast<HashType>(s[index + 3]))
		* prime) ^ static_cast<HashType>(s[index + 4]))
		* prime) ^ static_cast<HashType>(s[index + 5]))
		* prime) ^ static_cast<HashType>(s[index + 6]))
		* prime) ^ static_cast<HashType>(s[index + 7]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 4>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((((((init 
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]))
		* prime) ^ static_cast<HashType>(s[index + 2]))
		* prime) ^ static_cast<HashType>(s[index + 3]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 2>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		HashType prime = static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_PRIME);
		return 
		(((init 
		* prime) ^ static_cast<HashType>(s[index]))
		* prime) ^ static_cast<HashType>(s[index + 1]);
	}
};

template <typename HashType> class StaticHash_Unrolled<HashType, 1>
{
public:

	template <size_t L> EA_FORCE_INLINE static HashType hash(HashType init, const char (&s)[L], size_t index)
	{
		return 
		(init 
		* HashConstants<sizeof(HashType)*8>::FNV_PRIME) ^ static_cast<HashType>(s[index]);
	}
};

template <typename HashType, bool runtime, size_t N> class StaticHash_Impl;

template <typename HashType, size_t N> class StaticHash_Impl<HashType, true, N>
{
public:
	template <size_t L> EA_FORCE_INLINE static HashType hash(const char (&s)[L])
	{
		static HashType id;
		if (!id)
		{
			id = internal::RuntimeHash<HashType>(s);
		}
		return id;
	}
};

template <typename HashType, size_t N> class StaticHash_Impl<HashType, false, N>
{
public:
	template <size_t L> EA_FORCE_INLINE static HashType hash(const char (&s)[L])
	{
		HashType result = HashConstants<sizeof(HashType)*8>::FNV_BASIS;
		size_t index = 0;
		result = StaticHash_Unrolled<HashType, N & 128>::hash(result, s, index);
		index += N & 128;
		result = StaticHash_Unrolled<HashType, N & 64>::hash(result, s, index);
		index += N & 64;
		result = StaticHash_Unrolled<HashType, N & 32>::hash(result, s, index);
		index += N & 32;
		result = StaticHash_Unrolled<HashType, N & 16>::hash(result, s, index);
		index += N & 16;
		result = StaticHash_Unrolled<HashType, N & 8>::hash(result, s, index);
		index += N & 8;
		result = StaticHash_Unrolled<HashType, N & 4>::hash(result, s, index);
		index += N & 4;
		result = StaticHash_Unrolled<HashType, N & 2>::hash(result, s, index);
		index += N & 2;
		result = StaticHash_Unrolled<HashType, N & 1>::hash(result, s, index);
		
		return result;
	}
};

template <typename HashType, size_t L> EA_FORCE_INLINE static HashType StaticHash(const char (&s)[L])
{
	HashType h = StaticHash_Impl<HashType, (L > 256), L-1>::hash(s);
	return (h) ? h : static_cast<HashType>(HashConstants<sizeof(HashType)*8>::FNV_BASIS);
}

}
}
}

#endif
