Hash implementation.

[Raigne]

This is a hash produced by Bob Jenkins, and I just want to know from a more intelligent person than me if my overload method will work in all cases. It seems to be safe, but I would hate to start using it if it may fail under certain circumstances.

#include <string>

/*
	Hash Author: Bob Jenkins
*/

unsigned Hash(char* pKey, unsigned pLength, unsigned pInit);
unsigned Hash(unsigned char* pKey, unsigned pLength, unsigned pInit);
unsigned Hash(const char* pKey, unsigned pInit);
unsigned Hash(std::string pKey, unsigned pInit);



unsigned Hash( char* pKey, unsigned pLength, unsigned pInit )
{
	return Hash(std::string((const char*)pKey,pLength), pInit);
}

unsigned Hash( unsigned char* pKey, unsigned pLength, unsigned pInit)
{
	return Hash(std::string((const char*)pKey, pLength), pInit);
}

unsigned Hash( const char *pKey, unsigned pInit )
{
	return Hash(std::string(pKey),pInit);
}

void mix(unsigned& a, unsigned& b, unsigned& 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 );
}

unsigned Hash(std::string pKey, unsigned pInit)
{
	unsigned a, b;
	unsigned c = pInit;
	unsigned len = pKey.length();
	unsigned loc = 0;

	a = b = 0x9e3779b9;
	while ( len >= 12 ) {
		a += ( pKey[loc] + ( (unsigned)pKey[loc] << 8 ) 
			+ ( (unsigned)pKey[loc] << 16 )
			+ ( (unsigned)pKey[loc] << 24 ) );
		b += ( pKey[4] + ( (unsigned)pKey[5] << 8 ) 
			+ ( (unsigned)pKey[loc] << 16 )
			+ ( (unsigned)pKey[loc] << 24 ) );
		c += ( pKey[8] + ( (unsigned)pKey[9] << 8 ) 
			+ ( (unsigned)pKey[loc] << 16 )
			+ ( (unsigned)pKey[loc] << 24 ) );

		mix ( a, b, c );

		loc += 12;
		len -= 12;
		if ( loc > len )
			loc = len;
	}

	c += pKey.length();

	switch ( len ) {
	case 11: c += ( (unsigned)pKey[10] << 24 );
	case 10: c += ( (unsigned)pKey[9] << 16 );
	case 9 : c += ( (unsigned)pKey[8] << 8 );
		/* First byte of c reserved for length */
	case 8 : b += ( (unsigned)pKey[7] << 24 );
	case 7 : b += ( (unsigned)pKey[6] << 16 );
	case 6 : b += ( (unsigned)pKey[5] << 8 );
	case 5 : b += pKey[4];
	case 4 : a += ( (unsigned)pKey[3] << 24 );
	case 3 : a += ( (unsigned)pKey[2] << 16 );
	case 2 : a += ( (unsigned)pKey[1] << 8 );
	case 1 : a += pKey[0];
	}

	mix ( a, b, c );

	return c;
}

Thank you very much for any constructive criticism.
[/SIZE][/FONT][/SIZE][/FONT]

[stahta01]

No it will not work in all cases.
If "char" is unsigned it will likely not even compile.

Tim S.

[Raigne]

Okay, reason for unsigned char not compiling? It compiles fine and works fine, I just want to know if there is something im missing, and a brief explanation of why that is.

[phantomotap]

He is simply wrong about that part.

Presumably, he was thinking that if `char' was the same as `unsigned char' you would get an overload problem. (You would if you weren't using `char' as the base type. Feel free to try with `int' instead.)

This isn't a problem though because `signed char', `unsigned char', and `char' are three different types.

Anyway, because you are using a simple cast, the overloads and use of `std::string' should work.

The problem is, your implementation is wrong. Or at least, it will not return the same results as the canonical implementation.

Soma

[Raigne]

The implementation of the Hash is wrong?

unsigned char str[10] = "VariaTest";
	std::cout << "Hash 0 ( VariaTest ) = " << Hash(str, 9, 0) << '\n';
	std::cout << "Hash 1 ( VariaTest ) = " << Hash("VariaTest", 0) << '\n';
	std::cout << "Hash 2 ( VariaTest ) = " << Hash(std::string("VariaTest"), 0 ) << '\n';

Given this input it produces the same value.

[phantomotap]

O_o

All of that uses the same implementation. That only serves to say that the overloads do the job of forwarding to the same implementation.

Soma

[Raigne]

What is wrong with the implementation, and how to fix it?

edit: I think I know what the problem was, let me fix it and I will repost.

Fixed I think:

unsigned Hash(std::string pKey, unsigned pInit)
{
	unsigned a, b;
	unsigned c = pInit;
	unsigned len = pKey.length();
	unsigned loc = 0;

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

		mix ( a, b, c );

		loc += 12;
		len -= 12;
		if ( len <= 12 )
		{
			if ( len < 0 )
				len = 1;
			if ( loc > pKey.length()-10 )
				loc = pKey.length()-10;
		}
	}

	c += pKey.length();

	switch ( len ) {
	case 11: c += ( (unsigned)pKey[loc+10] << 24 );
	case 10: c += ( (unsigned)pKey[loc+9] << 16 );
	case 9 : c += ( (unsigned)pKey[loc+8] << 8 );
		/* First byte of c reserved for length */
	case 8 : b += ( (unsigned)pKey[loc+7] << 24 );
	case 7 : b += ( (unsigned)pKey[loc+6] << 16 ); 
	case 6 : b += ( (unsigned)pKey[loc+5] << 8 );
	case 5 : b += pKey[loc+4];
	case 4 : a += ( (unsigned)pKey[loc+3] << 24 );
	case 3 : a += ( (unsigned)pKey[loc+2] << 16 );
	case 2 : a += ( (unsigned)pKey[loc+1] << 8 );
	case 1 : a += pKey[loc];
	}

	mix ( a, b, c );

	return c;
}

[phantomotap]

O_o

Okay. You must be talking about a different hash than I think you are.

Do you have a link to the actual hash?

That said, kudos for hearing a reference to a potential problem and trying to fix it on your own. It is always nice to see that.

Soma

[Raigne]

Eternally Confuzzled - The Art of Hashing The hash is the last one torwards the bottom of the page. I am just trying to make it work with std::strings for simplicity. I hate managing c strings.

[phantomotap]

O_o

Okay. It is the algorithm I was thinking of.

As a matter of course, what does this code, from your implementation, do?

Soma

if ( len <= 12 )
{
	if ( len < 0 )
		len = 1;
	if ( loc > pKey.length()-10 )
		loc = pKey.length()-10;
}

[Raigne]

Make sure that the 'loc' does not go out of bounds.

[phantomotap]

Make sure that the 'loc' does not go out of bounds.

No. That is only the intent. That is not what it does.

Here, try going stepping through your implementation with strings that have a length of between 11 and 25. (Trying once for each string length.)

Soma