diff options
Diffstat (limited to 'attic/hash.cpp')
| -rw-r--r-- | attic/hash.cpp | 254 |
1 files changed, 254 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 |