Commits

bitsquid  committed a025030

Added murmur hash and did some additional clean up.

  • Participants
  • Parent commits 4d065f7

Comments (0)

Files changed (7)

File README.markdown

 
 * **Abstract classes.** Used for high-level systems that are only accessed through pointers and/or references. These are predeclared in the \_types.h file. The virtual interface is found in the .h file.
 
+## Compiler flags
+
+* **PLATFORM_BIG_ENDIAN** Should be defined if you are compiling for a big endian platform.
+
 ## Systems
 
 ### Memory

File collection_types.h

 };
 
 /// Hash from an uint64_t to POD objects. If you want to use a generic key
-/// object, use a hash function to map that to an uint64_t.
+/// object, use a hash function to map that object to an uint64_t.
 ///
 /// * Does not call constructors & destructors on elements.
 /// * Assumes they can be moved with memmove().
 public:
 	Hash(Allocator &a);
 	
-	// Marks end of linked next list.
-	static const uint32_t END_OF_LIST = 0xffffffffu;
-
 	struct Entry {
 		uint64_t key;
 		uint32_t next;

File murmur_hash.cpp

+#include "murmur_hash.h"
+
+uint64_t murmur_hash_64(const void * key, uint32_t len, uint64_t seed)
+{
+	const uint64_t m = 0xc6a4a7935bd1e995ULL;
+	const uint32_t r = 47;
+
+	uint64_t h = seed ^ (len * m);
+
+	const uint64_t * data = (const uint64_t *)key;
+	const uint64_t * end = data + (len/8);
+
+	while(data != end)
+	{
+		#ifdef PLATFORM_BIG_ENDIAN
+			uint64 k = *data++;
+			char *p = (char *)&k;
+			char c;
+			c = p[0]; p[0] = p[7]; p[7] = c;
+			c = p[1]; p[1] = p[6]; p[6] = c;
+			c = p[2]; p[2] = p[5]; p[5] = c;
+			c = p[3]; p[3] = p[4]; p[4] = c;
+		#else
+			uint64_t k = *data++;
+		#endif
+
+		k *= m;
+		k ^= k >> r;
+		k *= m;
+		
+		h ^= k;
+		h *= m;
+	}
+
+	const unsigned char * data2 = (const unsigned char*)data;
+
+	switch(len & 7)
+	{
+	case 7: h ^= uint64_t(data2[6]) << 48;
+	case 6: h ^= uint64_t(data2[5]) << 40;
+	case 5: h ^= uint64_t(data2[4]) << 32;
+	case 4: h ^= uint64_t(data2[3]) << 24;
+	case 3: h ^= uint64_t(data2[2]) << 16;
+	case 2: h ^= uint64_t(data2[1]) << 8;
+	case 1: h ^= uint64_t(data2[0]);
+			h *= m;
+	};
+	
+	h ^= h >> r;
+	h *= m;
+	h ^= h >> r;
+
+	return h;
+}

File murmur_hash.h

+#pragma once
+
+#include "types.h"
+
+/// Implementation of the 64 bit MurmurHash2 function
+/// http://murmurhash.googlepages.com/
+uint64_t murmur_hash_64(const void *key, uint32_t len, uint64_t seed);
 
 COMPILER = "g++"
 EXEC = "unit_test"
+# Use -DPLATFORM_BIG_ENDIAN for big endian platforms
 FLAGS = "-Wall -Wextra -g"
 
-OBJECTS = %w(unit_test.o memory.o)
+OBJECTS = %w(unit_test.o memory.o murmur_hash.o)
 HEADERS = %w(array.h collection_types.h memory.h memory_types.h types.h temp_allocator.h hash.h)
 
 # tasks
 # dependencies
 
 file 'unit_test.o' => %w(unit_test.cpp) + HEADERS
-file 'memory.o' => %w(memory.cpp) + %w(types.h memory_types.h memory.h)
+file 'memory.o' => %w(memory.cpp) + %w(types.h memory_types.h memory.h)
+file 'murmur_hash.o' => %w(murmur_hash.cpp) + %w(murmur_hash.h)

File temp_allocator.h

 void *TempAllocator<BUFFER_SIZE>::allocate(uint32_t size, uint32_t align)
 {
 	_p = (char *)memory::align_forward(_p, align);
-	if (size > _end - _p) {
+	if ((int)size > _end - _p) {
 		uint32_t to_allocate = sizeof(void *) + size + align;
 		if (to_allocate < _chunk_size)
 			to_allocate = _chunk_size;

File unit_test.cpp

+#include "murmur_hash.h"
 #include "hash.h"
 #include "temp_allocator.h"
 #include "array.h"
 		}
 		memory_globals::shutdown();
 	}
+
+	void test_murmur_hash()
+	{
+		const char *s = "test_string";
+		uint64_t h = murmur_hash_64(s, strlen(s), 0);
+		ASSERT(h == 0xe604acc23b568f83ull);
+	}
 }
 
 int main(int, char **)
 	test_scratch();
 	test_temp_allocator();
 	test_hash();
+	test_murmur_hash();
 	return 0;
 }