Christopher Smith on 2 Sep 2003 23:26:29 -0000


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

[ALACPP] Solution


So, if you are curious, this seems to work. If anyone has thoughts on
possible improvements, let me know.

--Chris
#ifndef JENKINS_HASH_H__INCLUDE
#define JENKINS_HASH_H__INCLUDE

#include <sys/types.h>

namespace jenkins {
    namespace jenkinsmixer {
	inline void mix(u_int32_t& a, u_int32_t& b, u_int32_t& 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);
	}
    }

    template<typename RandIter>
    inline u_int32_t hash(RandIter begin, RandIter end, u_int32_t initVal = 0) {
	const u_int32_t length = static_cast<u_int32_t>(end - begin);
	u_int32_t len = length;
	u_int32_t a = 0x9e3779b9;
	u_int32_t b = 0x9e3779b9;
	u_int32_t c = initVal;

	RandIter i = begin;
	while (len >= 12) {
	    a += (i[0] + (static_cast<u_int32_t>(i[1]) << 8) + (static_cast<u_int32_t>(i[2]) << 16)
		  + (static_cast<u_int32_t>(i[3]) << 24));
	    b += (i[4] + (static_cast<u_int32_t>(i[5]) << 8) + (static_cast<u_int32_t>(i[6]) << 16)
		  + (static_cast<u_int32_t>(i[7]) << 24));
	    c += (i[8] + (static_cast<u_int32_t>(i[9]) << 8) + (static_cast<u_int32_t>(i[10]) << 16)
		  + (static_cast<u_int32_t>(i[11]) << 24));
	    jenkinsmixer::mix(a, b, c);
	    i += 12;
	    len -= 12;
	}

	c += length;
	switch(len) {
	case 11: c+=(static_cast<u_int32_t>(i[10])<<24);
	case 10: c+=(static_cast<u_int32_t>(i[9])<<16);
	case 9 : c+=(static_cast<u_int32_t>(i[8])<<8);
	    /* the first byte of c is reserved for the length */
	case 8 : b+=(static_cast<u_int32_t>(i[7])<<24);
	case 7 : b+=(static_cast<u_int32_t>(i[6])<<16);
	case 6 : b+=(static_cast<u_int32_t>(i[5])<<8);
	case 5 : b+=i[4];
	case 4 : a+=(static_cast<u_int32_t>(i[3])<<24);
	case 3 : a+=(static_cast<u_int32_t>(i[2])<<16);
	case 2 : a+=(static_cast<u_int32_t>(i[1])<<8);
	case 1 : a+=i[0];
	    /* case 0: nothing left to add */	    
	}

	jenkinsmixer::mix(a, b, c);

	return c;
    }
}
#endif
_______________________________________________
alacpp mailing list
alacpp@xxxxxxxxxxx
http://lists.ellipsis.cx/mailman/listinfo/alacpp