replace hash with fnv1

3 files changed, 34 insertions, 44 deletions

diff --git a/compat/int-hash.cpp b/compat/int-hash.cpp
index 00f2e474..72c38179 100644
--- a/compat/int-hash.cpp
+++ b/compat/int-hash.cpp
@@ -3,35 +3,31 @@
 
 namespace floormat {
 
-size_t int_hash(uint32_t x) noexcept
+template<typename T, T offset_basis, T prime>
+static CORRADE_ALWAYS_INLINE
+T FNVHash(const char* str, size_t size)
 {
-    if constexpr(sizeof(size_t) == 4)
+    const auto* end = str + size;
+    T hash = offset_basis;
+    for (; str != end; ++str)
     {
-        // by Chris Wellons <https://nullprogram.com/blog/2018/07/31/>
-
-        x ^= x >> 15;
-        x *= 0x2c1b3c6dU;
-        x ^= x >> 12;
-        x *= 0x297a2d39U;
-        x ^= x >> 15;
-
-        return x;
+        hash *= prime;
+        hash ^= (uint8_t)*str;
     }
+    return hash;
+}
+
+size_t int_hash(uint32_t x) noexcept
+{
+    if constexpr(sizeof(size_t) == 4)
+        return FNVHash<uint32_t, 0x811c9dc5u, 0x01000193u>((const char*)&x, 4);
     else
         return int_hash(uint64_t(x));
 }
 
 size_t int_hash(uint64_t x) noexcept
 {
-    // NASAM by Pelle Evensen <https://mostlymangling.blogspot.com/2020/01/nasam-not-another-strange-acronym-mixer.html>
-
-    x ^= std::rotr(x, 25) ^ std::rotr(x, 47);
-    x *= 0x9E6C63D0676A9A99UL;
-    x ^= x >> 23 ^ x >> 51;
-    x *= 0x9E6D62D06F6A9A9BUL;
-    x ^= x >> 23 ^ x >> 51;
-
-    return x;
+    return FNVHash<uint64_t, 0xcbf29ce484222325u, 0x100000001b3u>((const char*)&x, 8);
 }
 
 } // namespace floormat
diff --git a/src/world.cpp b/src/world.cpp
index 46a65f64..fd6e4cbb 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -6,21 +6,15 @@
 
 using namespace floormat;
 
-size_t std::hash<chunk_coords_>::operator()(const chunk_coords_& coord) const noexcept
-{
-    std::size_t x = 0;
-
-    x |= size_t(uint16_t(coord.y)) << 16;
-    x |= size_t(uint16_t(coord.x));
-    if constexpr(sizeof(size_t) > 4)
-        x |= size_t(uint8_t(coord.z- chunk_z_min) & 0xf) << 32;
-    else
-        x ^= size_t(uint8_t(coord.z- chunk_z_min) & 0xf) * size_t(1664525);
+size_t world::object_id_hasher::operator()(object_id id) const noexcept { return (size_t)int_hash(id); }
 
-    if constexpr(sizeof(size_t) > 4)
-        return int_hash(uint64_t(x));
-    else
-        return int_hash(uint32_t(x));
+size_t world::chunk_coords_hasher::operator()(const chunk_coords_& coord) const noexcept
+{
+    uint64_t x = 0;
+    x |= uint64_t((uint16_t)coord.x) << 0;
+    x |= uint64_t((uint16_t)coord.y) << 16;
+    x |= uint64_t( (uint8_t)coord.z) << 32;
+    return (size_t)int_hash(x);
 }
 
 namespace floormat {
diff --git a/src/world.hpp b/src/world.hpp
index 288d69ca..bda8d3a4 100644
--- a/src/world.hpp
+++ b/src/world.hpp
@@ -3,24 +3,15 @@
 #include "chunk.hpp"
 #include "global-coords.hpp"
 #include "object-type.hpp"
-#include "compat/int-hash.hpp"
 #include <memory>
 #include <unordered_map>
 #include <tsl/robin_map.h>
 #include <Corrade/Utility/Move.h>
 
-template<>
-struct std::hash<floormat::chunk_coords_> final {
-    floormat::size_t operator()(const floormat::chunk_coords_& coord) const noexcept;
-};
-
 namespace floormat {
 
 struct object;
 template<typename T> struct object_type_;
-struct object_id_hasher {
-    size_t operator()(object_id id) const noexcept { return int_hash(id); }
-};
 
 struct world final
 {
@@ -36,7 +27,16 @@ private:
         chunk_coords_ pos = invalid_coords;
     } _last_chunk;
 
-    std::unordered_map<chunk_coords_, chunk> _chunks;
+    struct object_id_hasher
+    {
+        size_t operator()(object_id id) const noexcept;
+    };
+
+    struct chunk_coords_hasher {
+        size_t operator()(const chunk_coords_& coord) const noexcept;
+    };
+
+    std::unordered_map<chunk_coords_, chunk, chunk_coords_hasher> _chunks;
     tsl::robin_map<object_id, std::weak_ptr<object>, object_id_hasher> _objects;
     size_t _last_collection = 0;
     size_t _collect_every = initial_collect_every;