/*! Sunrise Data Dictionary Library
 *
 *  @brief a library for hashtable storage of arbitrary data objects
 *  with built-in reference counting and guaranteed order iteration.
 *
 *  @file dd_hash_functions.h
 *  default hash functions
 *
 *  @author Benjamin Kowarsch <nospam://com.sunrise-tel/~firstname~>
 *
 *  @note The author's true email address is herewith specifically excluded
 *  from the license of this software.  You are _not permitted_ to make the
 *  author's true email address available to any third party.  You may only
 *  pass on the modified version of the email address as presented above.
 *
 * (C) 2006 Sunrise Telephone Systems Ltd. All rights reserved.
 *
 * @cond LICENSE_TERMS
 *
 * Permission is  hereby granted,  free of charge,  to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction,  including without limitation
 * the rights  to  use, copy, modify, merge, publish, distribute, sublicense,
 * and/or  sell copies of  the Software,  and  to permit persons  to whom the
 * Software is furnished to do so,  subject to the following conditions:
 *
 * The above copyright notice  and  this permission notice  shall be included
 * in all copies or substantial portions of the Software.
 *
 * Under no circumstances is it permitted for any licensee to take credit for
 * the creation of  the Software,  to claim  authorship  or  ownership in the
 * Software  or in any other way  give the impression  that they have created
 * the Software.  Credit to the  true authors  and  copyright holders  of the
 * Software is absolutely mandatory and must be given as follows:
 *
 * Software packages incorporating the Software or substantial portions of it
 * shall display  a copyright notice  for the Software  in the same manner as
 * they  display  any  other copyright notice;  shall  display  an authorship
 * notice  for  the Software  in the  same manner  as they display  any other
 * authorship notice;  and shall display  the license terms or a reference to
 * the license terms of the Software  in the same manner  as they display any
 * other license or license reference.
 *
 * GUI-based or GUI-alike  interactive installers  installing the Software or
 * substantial portions of it, shall display the Software's copyright notice,
 * authorship notice  and  license terms  in  full  during  the  installation
 * process.  Other installers such as shell command driven package installers
 * on Unix systems shall display copyright,  authorship  and  license  in the
 * same  manner  as for  any other software.  Installers shall allow users to
 * install the license file for the Software along with the Software itself.
 *
 * Software  which makes use of  but  does not incorporate,  nor bundle,  nor
 * install the Software  or substantial portions of it,  is  NOT  required to
 * display any copyright, authorship, license terms  or license reference for
 * the Software.  Static linking to the Software constitutes 'incorporating',
 * dynamic linking to the Software constitutes 'making use of' the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED,  INCLUDING  BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE  AND  NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY,  WHETHER IN AN ACTION OF CONTRACT,  TORT OR OTHERWISE,  ARISING
 * FROM,  OUT OF  OR  IN CONNECTION WITH THE SOFTWARE  OR  THE USE  OR  OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 * In countries and territories  where  the  above  no-warranty disclaimer is
 * not permissible by applicable law, the following terms apply:
 *
 * NO PERMISSION TO USE THE SOFTWARE IS GRANTED  AND THE SOFTWARE MUST NOT BE
 * USED AT ALL  IN SUCH COUNTRIES AND TERRITORIES WHERE THE ABOVE NO-WARRANTY
 * DISCLAIMER IS NOT PERMISSIBLE AND INVALIDATED BY APPLICABLE LAW.  HOWEVER,
 * THE COPYRIGHT HOLDERS HEREBY WAIVE THEIR RIGHT TO PURSUE OFFENDERS AS LONG
 * AS THEY OTHERWISE ABIDE BY THE TERMS OF THE LICENSE  AS APPLICABLE FOR USE
 * OF THE SOFTWARE  IN COUNTRIES AND TERRITORIES WHERE THE ABOVE  NO-WARRANTY
 * DISCLAIMER IS PERMITTED BY APPLICABLE LAW. THIS WAIVER DOES NOT CONSTITUTE
 * A LICENSE TO USE THE SOFTWARE IN COUNTRIES AND TERRITORIES WHERE THE ABOVE
 * NO-WARRANTY DISCLAIMER IS  NOT PERMISSIBLE  AND  INVALIDATED BY APPLICABLE
 * LAW.  ANY LIABILITY OF ANY KIND IS CATEGORICALLY RULED OUT AT ALL TIMES.
 *
 * @endcond
 */

#include <string.h>
#include "dd_settings.pp"
#include "dd_hash_functions.h"


// --------------------------------------------------------------------------
// function:  dd_SDBM_hash_string(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// SDBM hash algorithm.  The number  of significant characters  for which the
// hash  value  will  be  calculated  is limited to  the  value  returned  by
// function dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_SDBM_hash_string(const char *string) {
	register cardinal len, index, hash = 0;
	register char ch;
	
	if (string == NULL)
		return 0;
	
	len = strlen(string);
	
	if (len > DD_SIGNIFICANT_CHARS) {
		len = DD_SIGNIFICANT_CHARS;
	} // end if
	
	// PUBLIC DOMAIN ALGORITHM FOLLOWS
	for (index = 0; index < len; index++) {
		ch = string[index];
		hash = ch + (hash << 6) + (hash << 16) - hash;
	} // end for
	
	return (hash & 0x7FFFFFFF);
} // end dd_SDBM_hash_string


// --------------------------------------------------------------------------
// function:  dd_SDBM_hash_string_toupper(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// SDBM hash algorithm after converting <string> to its uppercase equivalent,
// which  effectively makes the function  case insensitive.   Case conversion
// is limited  to characters  in the ASCII range 'a' to 'z'.  The  number  of
// significant characters  for which  the hash value  will  be  calculated is
// limited to the value returned by function dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_SDBM_hash_string_toupper(const char *string) {	
	register cardinal len, index, hash = 0;
	register char ch;
	
	if (string == NULL)
		return 0;

	len = strlen(string);
	
	if (len > DD_SIGNIFICANT_CHARS) {
		len = DD_SIGNIFICANT_CHARS;
	} // end if
	
	for (index = 0; index < len; index++) {
		ch = string[index];
		if /* LOWERCASE CHARACTER */ ((ch >= 'a') && (ch <= 'z')) {
			ch = ch - 32;
		} // end if
		hash = ch + (hash << 6) + (hash << 16) - hash;
	} // end for
	
	return (hash & 0x7FFFFFFF);
} // end dd_SDBM_hash_string_toupper


#if 0
// alternative implementation for case insensitive hash function ...
// --------------------------------------------------------------------------
// function:  dd_SDBM_hash_string_tolower(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string> using the
// SDBM hash algorithm after converting <string> to its lowercase equivalent,
// which effectively makes the function case insensitive.  Case conversion is
// limited to characters in the ASCII range 'A' to 'Z'.  The number of
// significant characters for which the hash value will be calculated is
// limited to the value returned by function dd_significant_chars().

cardinal dd_SDBM_hash_string_tolower(const char *string) {
	register cardinal len, index, hash = 0;
	register char ch;
	
	if (string == NULL)
		return 0;

	len = strlen(string);
	
	if (len > DD_SIGNIFICANT_CHARS) {
		len = DD_SIGNIFICANT_CHARS;
	} // end if
	
	for (index = 0; index < len; index++) {
		ch = string[index];
		// checking for ch <= 'Z' first is faster
		if /* UPPERCASE CHARACTER */ ((ch <= 'Z') && (ch >= 'A')) {
			ch = ch + 32;
		} // end if
		hash = ch + (hash << 6) + (hash << 16) - hash;
	} // end for
	
	return (hash & 0x7FFFFFFF);
} // end dd_SDBMhash_string_tolower
#endif


// seed value for DJB hashes
#define _DJB_INIT 5381

// --------------------------------------------------------------------------
// Function:  dd_DJB_hash_string(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// DJB hash algorithm  (published by D.J.Bernstein on Usenet in comp.lang.c).
// The number  of  significant characters  for which the  hash value  will be
// calculated    is    limited   to   the   value   returned   by    function
// dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_DJB_hash_string(const char *string) {
	register cardinal index = 0, hash = _DJB_INIT;
	
	if ((string == NULL) || (string[0] == 0))
		return 0;

	while ((string[index] != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		hash = string[index] + ((hash << 5) + hash);
		index++;
	} // end while
	
	return (hash & 0x7fffffff);
} // end dd_DJB_hash_string


// --------------------------------------------------------------------------
// Function:  dd_DJB_hash_string_toupper(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// DJB hash algorithm after converting <string> to its  uppercase equivalent,
// which effectively makes the function case insensitive.  Case conversion is
// limited  to  characters  in  the  ASCII range 'A' to 'Z'.   The  number of
// significant characters  for which the  hash value  will be  calculated  is
// limited to the value returned by function dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_DJB_hash_string_toupper(const char *string) {
	register cardinal index = 0, hash = _DJB_INIT;
	register char ch;
	
	if (string == NULL)
		return 0;

	ch = string[0];
	if (ch == 0)
		return 0;
	
	while ((ch != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		if /* LOWERCASE CHARACTER */ ((ch >= 'a') && (ch <= 'z'))
			ch = ch - 32;
		hash = ch + ((hash << 5) + hash);
		index++; ch = string[index];
	} // end while
	
	return (hash & 0x7fffffff);
} // end dd_DJB_hash_string_toupper


#if 0
// alternative implementation for case insensitive hash function ...
// --------------------------------------------------------------------------
// Function:  dd_DJB_hash_string_tolower(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// DJB hash algorithm after converting <string> to its  lowercase equivalent,
// which effectively makes the function case insensitive.  Case conversion is
// limited  to  characters  in  the  ASCII range 'A' to 'Z'.   The  number of
// significant characters  for which the  hash value  will be  calculated  is
// limited to the value returned by function dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_DJB_hash_string_tolower(const char *string) {
	register cardinal index = 0, hash = _DJB_INIT;
	register char ch;
	
	if (string == NULL)
		return 0;
	
	ch = string[0];
	if (ch == 0)
		return 0;
	
	while ((ch != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		// checking for ch <= 'Z' first is faster
		if /* UPPERCASE CHARACTER */ ((ch <= 'Z') && (ch >= 'A'))
			ch = ch + 32;
		hash = ch + ((hash << 5) + hash);
		index++; ch = string[index];
	} // end while
	
	return (hash & 0x7fffffff);
} // end dd_DJB_hash_string_tolower
#endif


// --------------------------------------------------------------------------
// Function:  dd_ELF_hash_string(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// ELF hash algorithm  (as used in most Unix systems for passwd hashes).  The
// number   of  significant characters  for  which  the  hash value  will  be
// calculated    is    limited   to   the   value   returned   by    function
// dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_ELF_hash_string(const char *string) {
	register cardinal index = 0, temp = 0, hash = 0;
	
	if ((string == NULL) || (string[0] == 0))
		return 0;
	
	while ((string[index] != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		hash = (hash << 4) + string[index];
		temp = hash & 0xF0000000L;
		if (temp != 0)
			hash = hash ^ (temp >> 24);
		hash = hash & (~temp);
		index++;
	} // end while
		
	return (hash & 0x7fffffff);
} // end dd_ELF_hash_string


// --------------------------------------------------------------------------
// Function:  dd_ELF_hash_string_toupper(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// ELF hash algorithm after converting <string> to its  uppercase equivalent,
// which effectively makes the function case insensitive.  Case conversion is
// limited  to  characters  in  the  ASCII range 'A' to 'Z'.   The  number of
// significant characters  for which the  hash value  will be  calculated  is
// limited to the value returned by function dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_ELF_hash_string_toupper(const char *string) {
	register cardinal index = 0, temp = 0, hash = 0;
	register unsigned char ch;
	
	if (string == NULL)
		return 0;
	
	ch = string[0];
	if (ch == 0)
		return 0;
	
	while ((ch != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		// checking for ch <= 'Z' first is faster
		if /* UPPERCASE CHARACTER */ ((ch <= 'Z') && (ch >= 'A'))
			ch = ch + 32;
		hash = (hash << 4) + ch;
		temp = hash & 0xF0000000L;
		if (temp != 0)
			hash = hash ^ (temp >> 24);
		hash = hash & (~temp);
		index++; ch = string[index];
	} // end while
	
	return (hash & 0x7fffffff);
} // end dd_ELF_hash_string_toupper


// seed values for FNV hashes
#define _FNVM_INIT32 0x811c9dc5
#define _FNVM_PRIME32 0x01000193

// --------------------------------------------------------------------------
// Function:  dd_FNVM_hash_string(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// FNVM hash algorithm  (Fowler, Noll and Vo hash,  modified by Bret Mulvey).
// The number of  significant characters  for  which the hash value  will  be
// calculated   is   limited   to   the   value    returned    by    function
// dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_FNVM_hash_string(const char *string) {
	register uint32_t index = 0, hash = _FNVM_INIT32;
	
	if ((string == NULL) || (string[0] == 0))
		return 0;
	
	while ((string[index] != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		hash = hash ^ string[index];
		hash = hash * _FNVM_PRIME32;
		index++;
	} // end while
	
	hash = hash + (hash << 13);
	hash = hash ^ (hash >> 7);
	hash = hash + (hash << 3);
	hash = hash ^ (hash >> 17);
	hash = hash + (hash << 5);
	
	return (hash & 0x7fffffff);
} // end dd_FNV_hash_string


// --------------------------------------------------------------------------
// Function:  dd_FNVM_hash_string_toupper(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// FNVM  hash  algorithm   after  converting  <string>   to   its   uppercase
// equivalent,  which  effectively makes the hash function  case insensitive.
// Case conversion is  limited to characters  in the ASCII range  'A' to 'Z'.
// The number of  significant characters  for which  the hash value  will  be
// calculated   is   limited    to   the   value    returned    by   function
// dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_FNVM_hash_string_toupper(const char *string) {
	register uint32_t index = 0, hash = _FNVM_INIT32;
	register char ch;
	
	if ((string == NULL) || (string[0] == 0))
		return 0;
	
	ch = string[0];
	if (ch == 0)
		return 0;

	while ((ch != 0) && (index < DD_SIGNIFICANT_CHARS)) {
		// checking for ch <= 'Z' first is faster
		if /* UPPERCASE CHARACTER */ ((ch <= 'Z') && (ch >= 'A'))
			ch = ch + 32;
		hash = hash ^ ch;
		hash = hash * _FNVM_PRIME32;
		index++; ch = string[index];
	} // end while
	
	hash = hash + (hash << 13);
	hash = hash ^ (hash >> 7);
	hash = hash + (hash << 3);
	hash = hash ^ (hash >> 17);
	hash = hash + (hash << 5);

	return (hash & 0x7fffffff);
} // end dd_FNVM_hash_string_toupper


// type cast macro
#define _UINT32(_val) ((uint32_t)_val)

// --------------------------------------------------------------------------
// Function:  dd_HSIEH_hash_string(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// HSIEH hash algorithm (developed by Paul Hsieh).  The number of significant
// characters for which the hash value will be calculated  is limited  to the
// value returned by function dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_HSIEH_hash_string(const char *string) {
	register uint32_t temp, hash;
	register cardinal rem, len, index = 0;
	
	if ((string == NULL) || (string[0] == 0))
		return 0;
	
	// find the end of the string unless it exceeds significant chars
	while ((string[index] != 0) && (index < DD_SIGNIFICANT_CHARS))
		index++;
	
	hash = _UINT32(index); // initial value for hash
	
	// our main loop handles 4 chars at every iteration
	// so we need to exclude any chars at the end which
	// don't fit into a multiple of 4 sized buffer
	// those chars will be processed separately
	rem = index & 3; // number of remaining chars
	len = index - rem; // number of chars in buffer
	
	index = 0;
	// processing chars in buffer
	while (index < len) {
		hash = hash + (_UINT32(string[index]) << 8); index++;
		hash = hash + (_UINT32(string[index])); index++;
		temp = (_UINT32(string[index]) << 8); index ++;
		temp = ((temp + (_UINT32(string[index]))) << 11) ^ hash;
		hash = ((hash << 16) ^ temp) >> 11;
		index++;
	} // end while

	// processing remaining chars
	switch (rem) {
		case 3: 
			hash = hash + (_UINT32(string[index]) << 8); index++;
			hash = hash + (_UINT32(string[index])); index++;
			hash = hash ^ (hash << 16);
			hash = hash ^ ((_UINT32(string[index])) << 18);
			hash = hash + (hash >> 11);
			break;
		case 2:
			hash = hash + (_UINT32(string[index]) << 8); index++;
			hash = hash + (_UINT32(string[index]));
			hash = hash ^ (hash << 11);
			hash = hash + (hash >> 17);
			break;
		case 1:
			hash = hash + (_UINT32(string[index]) << 8);
			hash = hash ^ (hash << 10);
			hash = hash + (hash >> 1);
	} // end switch
	
	// mishmash least significant 127 bits
	hash = hash ^ (hash << 3);
	hash = hash + (hash >> 5);
	hash = hash ^ (hash << 4);
	hash = hash + (hash >> 17);
	hash = hash ^ (hash << 25);
	hash = hash + (hash >> 6);
	
	return (hash & 0x7fffffff);
} // end dd_HSIEH_hash_string


// function macro to return uppercase char
// this looks very messy but without it,  the code would look even messier
#define _UPPER(_ch) (((_ch) <= 'Z') && ((_ch) >= 'A')) ? ((_ch) + 32) : (_ch)

// --------------------------------------------------------------------------
// Function:  dd_HSIEH_hash_string_toupper(string)
// --------------------------------------------------------------------------
//
// Returns the hash value of the null terminated C string <string>  using the
// HSIEH hash algorithm after converting <string> to its uppercase equivalent
// which  effectively  makes  the  hash  function   case  insensitive.   Case
// conversion is  limited to characters  in the ASCII range  'A' to 'Z'.  The
// The number of  significant characters  for which  the hash value  will  be
// calculated   is   limited    to   the   value    returned    by   function
// dd_significant_chars().
//
// Returns 0 if <string> is empty or NULL.

cardinal dd_HSIEH_hash_string_toupper(const char *string) {
	register uint32_t temp, hash;
	register cardinal rem, len, index = 0;
	
	if ((string == NULL) || (string[0] == 0))
		return 0;
	
	// find the end of the string unless it exceeds significant chars
	while ((string[index] != 0) && (index < DD_SIGNIFICANT_CHARS))
		index++;
	
	hash = _UINT32(index); // initial value for hash
	
	// our main loop handles 4 chars at every iteration
	// so we need to exclude any chars at the end which
	// don't fit into a multiple of 4 sized buffer
	// those chars will be processed separately
	rem = index & 3; // number of remaining chars
	len = index - rem; // number of chars in buffer
	
	index = 0;
	// processing chars in buffer
	while (index < len) {
		
		hash = hash + (_UINT32(_UPPER(string[index])) << 8); index++;
		hash = hash + (_UINT32(_UPPER(string[index]))); index++;
		temp = (_UINT32(_UPPER(string[index])) << 8); index ++;
		temp = ((temp + (_UPPER(string[index]))) << 11) ^ hash;
		hash = ((hash << 16) ^ temp) >> 11;
		index++;
	} // end while
	
	// processing remaining chars
	switch (rem) {
		case 3: 
			hash = hash + (_UINT32(_UPPER(string[index])) << 8); index++;
			hash = hash + (_UINT32(_UPPER(string[index]))); index++;
			hash = hash ^ (hash << 16);
			hash = hash ^ ((_UINT32(_UPPER(string[index]))) << 18);
			hash = hash + (hash >> 11);
			break;
		case 2:
			hash = hash + (_UINT32(_UPPER(string[index])) << 8); index++;
			hash = hash + (_UINT32(_UPPER(string[index])));
			hash = hash ^ (hash << 11);
			hash = hash + (hash >> 17);
			break;
		case 1:
			hash = hash + (_UINT32(_UPPER(string[index])) << 8);
			hash = hash ^ (hash << 10);
			hash = hash + (hash >> 1);
	} // end switch
	
	// mishmash least significant 127 bits
	hash = hash ^ (hash << 3);
	hash = hash + (hash >> 5);
	hash = hash ^ (hash << 4);
	hash = hash + (hash >> 17);
	hash = hash ^ (hash << 25);
	hash = hash + (hash >> 6);
	
	return (hash & 0x7fffffff);
} // end dd_HSIEH_hash_string_toupper


// END OF FILE