summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--attic/hash.cpp254
-rw-r--r--attic/int-hash.cpp37
-rw-r--r--attic/int-hash.hpp8
3 files changed, 299 insertions, 0 deletions
diff --git a/attic/hash.cpp b/attic/hash.cpp
new file mode 100644
index 00000000..b287b27a
--- /dev/null
+++ b/attic/hash.cpp
@@ -0,0 +1,254 @@
+#include "app.hpp"
+#include "compat/int-hash.hpp"
+#include "src/global-coords.hpp"
+#include <cmath>
+#include <cstdio>
+#include <memory>
+#include <algorithm>
+#include <utility>
+#include <tsl/robin_hash.h>
+
+namespace floormat
+{
+
+namespace
+{
+
+template <uint8_t a, uint32_t b, uint8_t c, uint32_t d, uint8_t e> [[maybe_unused]] CORRADE_ALWAYS_INLINE uint32_t hash32(uint32_t x)
+{
+ x++;
+ x ^= x >> a;
+ x *= b;
+ x ^= x >> c;
+ x *= d;
+ x ^= x >> e;
+
+ return x;
+}
+
+template <uint8_t a, uint32_t b, uint8_t c, uint32_t d, uint8_t e> [[maybe_unused]] uint32_t hash32_(uint64_t x)
+{
+ return hash32<a, b, c, d, e>((uint32_t)(x * 65521 >> 32)) ^ hash32<a, b, c, d, e>((uint32_t)x);
+}
+
+template <uint8_t a, uint64_t b, uint8_t c, uint64_t d, uint8_t e> [[maybe_unused]] uint64_t hash64(uint64_t x)
+{
+ x++;
+ x ^= x >> a;
+ x *= b;
+ x ^= x >> c;
+ x *= d;
+ x ^= x >> e;
+ return x;
+}
+
+template <uint8_t a, uint32_t b, uint8_t c, uint32_t d, uint8_t e, uint32_t f, uint8_t g> [[maybe_unused]] uint32_t triple32(uint32_t x)
+{
+ x++;
+ x ^= x >> a;
+ x *= b;
+ x ^= x >> c;
+ x *= d;
+ x ^= x >> e;
+ x *= f;
+ x ^= x >> g;
+ return x;
+}
+
+template <uint8_t a, uint32_t b, uint8_t c, uint32_t d, uint8_t e, uint32_t f, uint8_t g> [[maybe_unused]] uint32_t triple32_(uint64_t x)
+{
+ return triple32<a, b, c, d, e, f, g>((uint32_t)(x * 65521 >> 32)) ^ triple32<a, b, c, d, e, f, g>((uint32_t)x);
+}
+
+[[maybe_unused]] CORRADE_ALWAYS_INLINE uint32_t triple32_1(uint32_t x)
+{
+ return triple32<17,0xed5ad4bb,11,0xac4c1b51,15,0x31848bab,14>(x);
+}
+
+[[maybe_unused]] uint64_t nasam(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;
+}
+
+[[maybe_unused]] uint64_t splitmix64(uint64_t x)
+{
+ x = (x ^ (x >> 30)) * uint64_t(0xbf58476d1ce4e5b9ULL);
+ x = (x ^ (x >> 27)) * uint64_t(0x94d049bb133111ebULL);
+ x = x ^ (x >> 31);
+ return x;
+}
+
+
+[[maybe_unused]] CORRADE_ALWAYS_INLINE uint32_t fmix32(uint32_t h)
+{
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ return h;
+}
+
+[[maybe_unused]] uint32_t MurmurHash3_x86_32(const uint32_t* key, int len, uint32_t seed)
+{
+ const uint8_t* data = (const uint8_t*)key;
+ const int nblocks = len >> 2;
+ int i;
+
+ uint32_t h1 = seed;
+ constexpr uint32_t c1 = 0xcc9e2d51;
+ constexpr uint32_t c2 = 0x1b873593;
+
+ const uint32_t* blocks = key + nblocks;
+
+ for (i = -nblocks; i; i++)
+ {
+ uint32_t k1 = blocks[i];
+
+ k1 *= c1;
+ k1 = std::rotl(k1, 15);
+ k1 *= c2;
+
+ h1 ^= k1;
+ h1 = std::rotl(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ const uint8_t* tail = (const uint8_t*)(data + nblocks * 4);
+
+ uint32_t k1 = 0;
+
+ switch (len & 3)
+ {
+ case 3:
+ k1 ^= (uint32_t)(tail[2] << 16);
+ [[fallthrough]];
+ case 2:
+ k1 ^= (uint32_t)(tail[1] << 8);
+ [[fallthrough]];
+ case 1:
+ k1 ^= tail[0];
+ k1 *= c1;
+ k1 = std::rotl(k1, 15);
+ k1 *= c2;
+ h1 ^= k1;
+ }
+
+ h1 ^= (uint32_t)len;
+ //h1 = hash32<16, 0x7feb352d, 15, 0x846ca68b, 16>(h1);
+ h1 = fmix32(h1);
+
+ return h1;
+}
+
+[[maybe_unused]] uint32_t murmur3(uint32_t x)
+{
+ return MurmurHash3_x86_32(&x, 4, 0xB16B00B5);
+}
+
+[[maybe_unused]] uint32_t murmur3_(uint64_t x)
+{
+ return MurmurHash3_x86_32((const uint32_t*)&x, 8, 0xB16B00B5);
+}
+
+[[maybe_unused]] constexpr auto std_hash = std::hash<uint64_t>{};
+
+template<typename T>
+constexpr bool is_prime(T n)
+{
+ // Corner cases
+ if (n <= 1) return false;
+ if (n <= 3) return true;
+
+ if (n%2 == 0 || n%3 == 0)
+ return false;
+
+ for (T i = 5; i * i <= n; i = i + 6)
+ if (n % i == 0 || n % (i + 2) == 0)
+ return false;
+
+ return true;
+}
+
+constexpr size_t next_prime(size_t pos)
+{
+ for (;;)
+ if (is_prime(++pos))
+ return pos;
+ return pos;
+}
+
+template <typename F> [[maybe_unused]] void test_coords64(const char* name, F&& fun)
+{
+ constexpr int32_t max = 1 << 12;
+ [[maybe_unused]] constexpr size_t iters = 4 * max * max;
+ constexpr auto size = next_prime(iters * 2);
+ //constexpr size_t size2 = 134217757;
+
+ auto array = std::make_unique<uint32_t[]>(size);
+ std::fill(array.get(), array.get() + size, 0);
+
+ for (int32_t y = -max; y < max; y++)
+ for (int32_t x = -max; x < max; x++)
+ {
+ global_coords coord{ x, y, 0 };
+ const auto val = uint64_t{coord.y} << 32 | uint64_t{coord.x};
+ const auto h = std::forward<F>(fun)(val) % size;
+ ++array[h];
+ }
+
+ uint32_t count = 0, num = 0;
+
+ for (unsigned i = 0; i < size; i++)
+ {
+ auto val = array[i];
+ if (val > 1)
+ num += val-1;
+ count = std::max(val, count);
+ }
+ std::printf("%-16s max=%-10zu bad=%f%%\n", name, size_t{count}, (double)num * 100 / (double)size);
+}
+
+template<typename T, T offset_basis, T prime>
+[[maybe_unused]] auto FNVHash(const char* str, size_t size)
+{
+ const auto* end = str + size;
+ T hash = offset_basis;
+ for (; str != end; ++str)
+ {
+ hash *= prime;
+ hash ^= (uint8_t)*str;
+ }
+ return hash;
+}
+
+[[maybe_unused]] auto fnv1_(uint64_t x)
+{
+ return FNVHash<uint64_t, 0xcbf29ce484222325ULL, 0x100000001b3ULL>((char*)&x, 8);
+}
+
+} // namespace
+
+#define FM_TEST_HASH_FUNCS
+
+void test_app::test_hash()
+{
+#ifdef FM_TEST_HASH_FUNCS
+ test_coords64("std::hash", [](uint64_t x) { return std_hash(x); });
+ test_coords64("murmur3", [](uint64_t x) { return murmur3_(x); });
+ test_coords64("fnv1", [](uint64_t x) { return fnv1_(x); });
+ test_coords64("splitmix64", [](uint64_t x) { return (uint32_t)splitmix64(x); });
+ test_coords64("nasam", [](uint64_t x) { return (uint32_t)nasam(x); });
+#endif
+}
+
+} // namespace floormat
diff --git a/attic/int-hash.cpp b/attic/int-hash.cpp
new file mode 100644
index 00000000..00f2e474
--- /dev/null
+++ b/attic/int-hash.cpp
@@ -0,0 +1,37 @@
+#include "int-hash.hpp"
+#include <bit>
+
+namespace floormat {
+
+size_t int_hash(uint32_t x) noexcept
+{
+ if constexpr(sizeof(size_t) == 4)
+ {
+ // 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;
+ }
+ 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;
+}
+
+} // namespace floormat
diff --git a/attic/int-hash.hpp b/attic/int-hash.hpp
new file mode 100644
index 00000000..2266bb4d
--- /dev/null
+++ b/attic/int-hash.hpp
@@ -0,0 +1,8 @@
+#pragma once
+
+namespace floormat {
+
+size_t int_hash(uint32_t x) noexcept;
+size_t int_hash(uint64_t x) noexcept;
+
+} // namespace floormat
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-14 21:44:46 +0000