improve hash api and hash test

7 files changed, 114 insertions, 45 deletions

diff --git a/compat/int-hash.cpp b/compat/int-hash.cpp
index d4f49bd3..6415f0e6 100644
--- a/compat/int-hash.cpp
+++ b/compat/int-hash.cpp
@@ -10,7 +10,6 @@ namespace {
 
 using namespace floormat::Hash;
 
-// todo implement in terms of fnvhash_buf()
 [[maybe_unused]]
 CORRADE_ALWAYS_INLINE size_t fnvhash_uint_32(uint32_t x)
 {
@@ -80,8 +79,31 @@ fm_UNROLL_8
     return hash;
 }
 
-size_t hash_int(uint32_t x) noexcept { return fnvhash_uint_32(x); }
-size_t hash_int(uint64_t x) noexcept { return fnvhash_uint_64(x); }
+size_t hash_buf(const void* buf, size_t size) noexcept
+{
+#if 1
+    if constexpr(sizeof nullptr > 4)
+        return hash_64(buf, size);
+    else
+#endif
+        return hash_32(buf, size);
+}
+
+size_t hash_int(uint32_t x) noexcept
+{
+#if 1
+    if constexpr(sizeof nullptr > 4)
+        return fnvhash_uint_64(x);
+    else
+#endif
+        return fnvhash_uint_32(x);
+}
+
+size_t hash_int(uint64_t x) noexcept
+{
+    return fnvhash_uint_64(x);
+}
+
 size_t hash_string_view::operator()(StringView s) const noexcept { return Hash::fnvhash_buf(s.data(), s.size()); }
 
 } // namespace floormat
diff --git a/compat/int-hash.hpp b/compat/int-hash.hpp
index 27f2651f..c512d249 100644
--- a/compat/int-hash.hpp
+++ b/compat/int-hash.hpp
@@ -18,6 +18,7 @@ namespace floormat { // todo
 
 uint64_t hash_64(const void* buf, size_t size) noexcept;
 uint32_t hash_32(const void* buf, size_t size) noexcept;
+size_t hash_buf(const void* buf, size_t size) noexcept;
 
 size_t hash_int(uint32_t x) noexcept;
 size_t hash_int(uint64_t x) noexcept;
diff --git a/serialize/savegame.cpp b/serialize/savegame.cpp
index 5c7e9b04..024ff85a 100644
--- a/serialize/savegame.cpp
+++ b/serialize/savegame.cpp
@@ -47,7 +47,6 @@ using floormat::Serialize::binary_reader;
 using floormat::Serialize::binary_writer;
 using floormat::Serialize::atlas_type;
 using floormat::Serialize::maybe_byteswap;
-using floormat::Hash::fnvhash_buf;
 
 namespace {
 
@@ -61,7 +60,7 @@ private:
     FILE* s;
 };
 
-struct string_hasher { CORRADE_ALWAYS_INLINE size_t operator()(StringView s) const { return fnvhash_buf(s.data(), s.size()); } };
+struct string_hasher { CORRADE_ALWAYS_INLINE size_t operator()(StringView s) const { return hash_buf(s.data(), s.size()); } };
 
 template<typename T> concept Number = std::is_arithmetic_v<std::remove_cvref_t<T>>;
 template<typename T> concept Enum = std::is_enum_v<std::remove_cvref_t<T>>;
diff --git a/src/point.cpp b/src/point.cpp
index 1c62b2ad..6cd2903b 100644
--- a/src/point.cpp
+++ b/src/point.cpp
@@ -8,13 +8,7 @@ size_t point::hash() const
 {
     constexpr size_t size = 2 * 2 + 1 + 1 + 2;
     static_assert(sizeof *this == size);
-#ifdef FLOORMAT_64
-    static_assert(sizeof nullptr > 4);
-    return hash_64(this, sizeof *this);
-#else
-    static_assert(sizeof nullptr == 4);
-    return hash_32(this, sizeof *this);
-#endif
+    return hash_buf(this, sizeof *this);
 }
 
 Debug& operator<<(Debug& dbg, const point& pt)
diff --git a/src/world.hpp b/src/world.hpp
index 420e8894..ecd58e3c 100644
--- a/src/world.hpp
+++ b/src/world.hpp
@@ -26,6 +26,8 @@ public:
     static constexpr float max_load_factor = .25;
     static constexpr size_t initial_collect_every = 64;
 
+    struct chunk_coords_hasher { size_t operator()(const chunk_coords_& coord) const noexcept; };
+
 private:
     struct chunk_tuple
     {
@@ -35,9 +37,8 @@ private:
     } _last_chunk;
 
     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; };
-    struct robin_map_wrapper;
 
+    struct robin_map_wrapper;
     std::unordered_map<chunk_coords_, chunk, chunk_coords_hasher> _chunks;
     safe_ptr<robin_map_wrapper> _objects;
     std::shared_ptr<char> _unique_id = std::make_shared<char>('A');
diff --git a/test/app.cpp b/test/app.cpp
index 35a65743..6ace3ca5 100644
--- a/test/app.cpp
+++ b/test/app.cpp
@@ -65,7 +65,6 @@ int App::exec()
         FM_TEST(test_bptr),
         FM_TEST(test_iptr),
         FM_TEST(test_entity),
-        FM_TEST(test_hash),
         // normal
         FM_TEST(test_bitmask),
         FM_TEST(test_json),
@@ -75,6 +74,7 @@ int App::exec()
         FM_TEST(test_raycast),
         FM_TEST(test_wall_atlas),
         FM_TEST(test_wall_atlas2),
+        FM_TEST(test_hash),
         FM_TEST(test_region),
         // the rest are slow
         FM_TEST(test_rtree),
diff --git a/test/hash.cpp b/test/hash.cpp
index 16ae3173..a06d16a6 100644
--- a/test/hash.cpp
+++ b/test/hash.cpp
@@ -1,9 +1,12 @@
 #include "app.hpp"
 #include "compat/int-hash.hpp"
 #include "compat/array-size.hpp"
+#include "src/global-coords.hpp"
+#include "src/world.hpp"
 #include <cr/StringView.h>
 #include <bitset>
 #include <memory>
+#include <mg/Functions.h>
 
 namespace floormat {
 
@@ -16,49 +19,67 @@ void test_simple()
 
     size_t hashes[size] = {};
     for (auto i = 0uz; i < size; i++)
-        hashes[i] = hash_64(list[i].data(), list[i].size());
+        hashes[i] = hash_buf(list[i].data(), list[i].size());
 
     for (auto i = 0uz; i < size; i++)
         for (auto j = i+1; j < size; j++)
         {
             if (hashes[i] == hashes[j])
-                fm_abort("hash collision between '%s' and '%s': 0x%p", list[i].data(), list[j].data(), (void*)hashes[i]);
+                fm_abort("hash collision between '%s' and '%s': 0x%p",
+                    list[i].data(), list[j].data(), (void*)hashes[i]);
         }
 }
 
-void test_collisions()
+template<int16_t CoordMax, int8_t ZMax, uint32_t MaxCollisions>
+[[nodiscard]] bool test_collisions(const char* name)
 {
-    constexpr int max = 8;
-    constexpr size_t size = (2*max+1)*(2*max+1)*4 * 10;
-    constexpr size_t max_collisions = size*2/100;
-    size_t iter = 0, num_collisions = 0;
-    auto bitset_ = std::make_unique<std::bitset<size>>(false);
+    constexpr size_t Iters = (CoordMax*2 + 1)*(CoordMax*2 + 1)*(1+ZMax);
+    constexpr size_t BucketCount = Math::max(world::initial_capacity, size_t(Math::ceil(Iters / world::max_load_factor)));
+    uint32_t num_collisions = 0, iters = 0;
+    auto bitset_ = std::make_unique<std::bitset<BucketCount>>(false);
     auto& bitset = *bitset_;
 
-    for (int j = -max; j <= max; j++)
-    {
-        for (int i = -max; i <= max; i++)
-        {
-            for (int k = -2; k <= 1; k++)
+    for (int16_t j = -CoordMax; j <= CoordMax; j++)
+        for (int16_t i = -CoordMax; i <= CoordMax; i++)
+            for (int8_t k = 0; k <= ZMax; k++)
             {
-                ++iter;
-                uint64_t value = 0;
-                value |= (uint64_t)(uint16_t)(int16_t)i << 0;
-                value |= (uint64_t)(uint16_t)(int16_t)j << 16;
-                value |= (uint64_t)(uint16_t)(int16_t)k << 32;
-                auto x = (size_t)hash_int(value);
-                //Debug {} << "bitset:" << i << j << k << "=" << x % size << "/" << x;
-                x %= size;
-#if 1
-                if (bitset.test(x) && ++num_collisions >= max_collisions)
-                    fm_abort("test/bitset: %zu collisions at iter %zu id %zu (%d;%d:%d)", num_collisions, iter, x, i, j, k);
+                auto p = global_coords{i, j, k};
+                auto h = hash_buf(&p, sizeof p);
+                h %= BucketCount;
+                auto ref = bitset[h];
+                if (ref) [[unlikely]]
+                    ++num_collisions;
+                else
+                    ref = true;
+                (void)ref;
+                iters++;
+            }
+
+    fm_assert_equal(Iters, iters);
+
+//#define FM_TEST_DEBUG_PRINT
+
+    if (num_collisions > MaxCollisions)
+    {
+        DBG_nospace << Debug::color(Debug::Color::Magenta)
+                    << "fail" << Debug::resetColor << ": test/hash(\"" << name << "\")"
+                    << " collisions " << num_collisions << " > " << MaxCollisions
+                    << " (iters:" << iters << " buckets:" << BucketCount << ")";
+#ifdef FM_TEST_DEBUG_PRINT
+        return false;
 #else
-                if ((void)max_collisions, bitset.test(x))
-                        fm_warn("test/bitset: %zu collisions at iter %zu id %zu (%d;%d:%d)", ++num_collisions, iter, x, i, j, k);
+        fm_abort("test/hash: too many collisions");
 #endif
-                bitset.set(x);
-            }
-        }
+    }
+    else
+    {
+#ifdef FM_TEST_DEBUG_PRINT
+        DBG_nospace << Debug::color(Debug::Color::Cyan) << "pass" << Debug::resetColor
+                    << ": test/hash(\"" << name << "\") collisions "
+                    << num_collisions << " <= " << MaxCollisions
+                    << " (iters:" << iters << " buckets:" << BucketCount << ")";
+#endif
+        return true;
     }
 }
 
@@ -67,7 +88,38 @@ void test_collisions()
 void Test::test_hash()
 {
     test_simple();
-    test_collisions();
+
+    bool success = true;
+
+#ifdef FM_TEST_DEBUG_PRINT
+    DBG_nospace << "";
+#endif
+
+    success &= test_collisions<  3, 0,   0 >("small1");
+    success &= test_collisions<  6, 0,   4 >("mid2");
+    success &= test_collisions<  7, 0,   5 >("mid2");
+    success &= test_collisions<  8, 0,  13 >("mid2");
+    success &= test_collisions<  9, 0,  19 >("mid2");
+    success &= test_collisions< 10, 0,  26 >("large1");
+    success &= test_collisions< 12, 0,  46 >("large2");
+    success &= test_collisions< 14, 0,  83 >("large3");
+    success &= test_collisions< 15, 0, 109 >("large4");
+    success &= test_collisions< 16, 0, 127 >("large5");
+    success &= test_collisions<  3, 1,    2 >("zsmall2");
+    success &= test_collisions<  4, 1,    6 >("zsmall3");
+    success &= test_collisions<  2, 3,    1 >("zmid1");
+    success &= test_collisions<  6, 1,   17 >("zmid3");
+    success &= test_collisions<  6, 2,   37 >("zmid4");
+    success &= test_collisions<  7, 1,   27 >("zmid5");
+    success &= test_collisions< 10, 1,  107 >("zlarge2");
+    success &= test_collisions< 10, 4,  271 >("zlarge3");
+    success &= test_collisions< 16, 8, 1114 >("zlarge4");
+
+    if (!success)
+    {
+        DBG_nospace << "";
+        fm_abort("test/hash: too many collisions");
+    }
 }
 
 } // namespace floormat