From 141c3755814cea60888c7ee548c7ce709550b784 Mon Sep 17 00:00:00 2001 From: reduz Date: Sat, 18 Jun 2022 16:20:55 +0200 Subject: Clean up Hash Functions Clean up and do fixes to hash functions and newly introduced murmur3 hashes in #61934 * Clean up usage of murmur3 * Fixed usages of binary murmur3 on floats (this is invalid) * Changed DJB2 to use xor (which seems to be better) --- core/io/file_access_pack.h | 4 +- core/io/resource.cpp | 20 +-- core/math/delaunay_3d.h | 2 +- core/multiplayer/multiplayer_peer.cpp | 11 +- core/object/callable_method_pointer.cpp | 4 +- core/object/class_db.cpp | 52 +++---- core/object/method_bind.cpp | 25 ++-- core/templates/hashfuncs.h | 162 +++++++++++++++++---- core/variant/array.cpp | 6 +- core/variant/callable.cpp | 3 +- core/variant/dictionary.cpp | 8 +- core/variant/variant.cpp | 144 +++++++++++++----- core/variant/variant_call.cpp | 16 +- core/variant/variant_utility.cpp | 12 +- drivers/vulkan/rendering_device_vulkan.h | 14 +- .../debugger/debug_adapter/debug_adapter_types.h | 2 +- editor/debugger/editor_debugger_node.h | 2 +- editor/plugins/mesh_instance_3d_editor_plugin.cpp | 4 +- modules/csg/csg.h | 6 +- modules/csg/csg_shape.h | 6 +- modules/gdscript/gdscript_lambda_callable.cpp | 6 +- modules/gdscript/gdscript_rpc_callable.cpp | 2 +- modules/lightmapper_rd/lightmapper_rd.h | 30 ++-- modules/mono/managed_callable.cpp | 3 +- modules/mono/signal_awaiter_utils.cpp | 4 +- modules/raycast/raycast_occlusion_cull.h | 4 +- scene/3d/label_3d.cpp | 2 +- scene/3d/lightmap_gi.cpp | 4 +- scene/3d/lightmap_gi.h | 10 +- scene/animation/animation_player.h | 4 +- scene/resources/canvas_item_material.h | 2 +- scene/resources/concave_polygon_shape_3d.h | 4 +- scene/resources/font.cpp | 8 +- scene/resources/material.cpp | 2 +- scene/resources/particles_material.h | 2 +- scene/resources/primitive_meshes.cpp | 4 +- scene/resources/surface_tool.cpp | 3 +- servers/physics_2d/godot_area_2d.h | 6 +- servers/physics_3d/godot_area_3d.h | 6 +- .../rendering/renderer_rd/uniform_set_cache_rd.h | 18 ++- 40 files changed, 391 insertions(+), 236 deletions(-) diff --git a/core/io/file_access_pack.h b/core/io/file_access_pack.h index 19a0cce796..e656f6b885 100644 --- a/core/io/file_access_pack.h +++ b/core/io/file_access_pack.h @@ -84,8 +84,8 @@ private: return (a == p_val.a) && (b == p_val.b); } static uint32_t hash(const PathMD5 &p_val) { - uint32_t h = hash_djb2_one_32(p_val.a); - return hash_djb2_one_32(p_val.b, h); + uint32_t h = hash_murmur3_one_32(p_val.a); + return hash_fmix32(hash_murmur3_one_32(p_val.b, h)); } PathMD5() {} diff --git a/core/io/resource.cpp b/core/io/resource.cpp index ad01eb1083..ed7228d0b9 100644 --- a/core/io/resource.cpp +++ b/core/io/resource.cpp @@ -100,14 +100,14 @@ String Resource::generate_scene_unique_id() { // If it's not unique it does not matter because the saver will try again. OS::Date date = OS::get_singleton()->get_date(); OS::Time time = OS::get_singleton()->get_time(); - uint32_t hash = hash_djb2_one_32(OS::get_singleton()->get_ticks_usec()); - hash = hash_djb2_one_32(date.year, hash); - hash = hash_djb2_one_32(date.month, hash); - hash = hash_djb2_one_32(date.day, hash); - hash = hash_djb2_one_32(time.hour, hash); - hash = hash_djb2_one_32(time.minute, hash); - hash = hash_djb2_one_32(time.second, hash); - hash = hash_djb2_one_32(Math::rand(), hash); + uint32_t hash = hash_murmur3_one_32(OS::get_singleton()->get_ticks_usec()); + hash = hash_murmur3_one_32(date.year, hash); + hash = hash_murmur3_one_32(date.month, hash); + hash = hash_murmur3_one_32(date.day, hash); + hash = hash_murmur3_one_32(time.hour, hash); + hash = hash_murmur3_one_32(time.minute, hash); + hash = hash_murmur3_one_32(time.second, hash); + hash = hash_murmur3_one_32(Math::rand(), hash); static constexpr uint32_t characters = 5; static constexpr uint32_t char_count = ('z' - 'a'); @@ -328,7 +328,7 @@ void Resource::notify_change_to_owners() { #ifdef TOOLS_ENABLED uint32_t Resource::hash_edited_version() const { - uint32_t hash = hash_djb2_one_32(get_edited_version()); + uint32_t hash = hash_murmur3_one_32(get_edited_version()); List plist; get_property_list(&plist); @@ -337,7 +337,7 @@ uint32_t Resource::hash_edited_version() const { if (E.usage & PROPERTY_USAGE_STORAGE && E.type == Variant::OBJECT && E.hint == PROPERTY_HINT_RESOURCE_TYPE) { Ref res = get(E.name); if (res.is_valid()) { - hash = hash_djb2_one_32(res->hash_edited_version(), hash); + hash = hash_murmur3_one_32(res->hash_edited_version(), hash); } } } diff --git a/core/math/delaunay_3d.h b/core/math/delaunay_3d.h index f8a10ec87e..4ab00e1f34 100644 --- a/core/math/delaunay_3d.h +++ b/core/math/delaunay_3d.h @@ -101,7 +101,7 @@ class Delaunay3D { _FORCE_INLINE_ static uint32_t hash(const Triangle &p_triangle) { uint32_t h = hash_djb2_one_32(p_triangle.triangle[0]); h = hash_djb2_one_32(p_triangle.triangle[1], h); - return hash_djb2_one_32(p_triangle.triangle[2], h); + return hash_fmix32(hash_djb2_one_32(p_triangle.triangle[2], h)); } }; diff --git a/core/multiplayer/multiplayer_peer.cpp b/core/multiplayer/multiplayer_peer.cpp index ae3b139bcc..b262903ce8 100644 --- a/core/multiplayer/multiplayer_peer.cpp +++ b/core/multiplayer/multiplayer_peer.cpp @@ -36,17 +36,18 @@ uint32_t MultiplayerPeer::generate_unique_id() const { uint32_t hash = 0; while (hash == 0 || hash == 1) { - hash = hash_djb2_one_32( + hash = hash_murmur3_one_32( (uint32_t)OS::get_singleton()->get_ticks_usec()); - hash = hash_djb2_one_32( + hash = hash_murmur3_one_32( (uint32_t)OS::get_singleton()->get_unix_time(), hash); - hash = hash_djb2_one_32( + hash = hash_murmur3_one_32( (uint32_t)OS::get_singleton()->get_user_data_dir().hash64(), hash); - hash = hash_djb2_one_32( + hash = hash_murmur3_one_32( (uint32_t)((uint64_t)this), hash); // Rely on ASLR heap - hash = hash_djb2_one_32( + hash = hash_murmur3_one_32( (uint32_t)((uint64_t)&hash), hash); // Rely on ASLR stack + hash = hash_fmix32(hash); hash = hash & 0x7FFFFFFF; // Make it compatible with unsigned, since negative ID is used for exclusion } diff --git a/core/object/callable_method_pointer.cpp b/core/object/callable_method_pointer.cpp index 1bf926cafc..81f8ab6be2 100644 --- a/core/object/callable_method_pointer.cpp +++ b/core/object/callable_method_pointer.cpp @@ -85,9 +85,9 @@ void CallableCustomMethodPointerBase::_setup(uint32_t *p_base_ptr, uint32_t p_pt // Precompute hash. for (uint32_t i = 0; i < comp_size; i++) { if (i == 0) { - h = hash_djb2_one_32(comp_ptr[i]); + h = hash_murmur3_one_32(comp_ptr[i]); } else { - h = hash_djb2_one_32(comp_ptr[i], h); + h = hash_murmur3_one_32(comp_ptr[i], h); } } } diff --git a/core/object/class_db.cpp b/core/object/class_db.cpp index 533cb6e789..3c9f373d12 100644 --- a/core/object/class_db.cpp +++ b/core/object/class_db.cpp @@ -164,7 +164,7 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { OBJTYPE_RLOCK; #ifdef DEBUG_METHODS_ENABLED - uint64_t hash = hash_djb2_one_64(HashMapHasherDefault::hash(VERSION_FULL_CONFIG)); + uint64_t hash = hash_murmur3_one_64(HashMapHasherDefault::hash(VERSION_FULL_CONFIG)); List class_list; ClassDB::get_class_list(&class_list); @@ -177,8 +177,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { if (t->api != p_api || !t->exposed) { continue; } - hash = hash_djb2_one_64(t->name.hash(), hash); - hash = hash_djb2_one_64(t->inherits.hash(), hash); + hash = hash_murmur3_one_64(t->name.hash(), hash); + hash = hash_murmur3_one_64(t->inherits.hash(), hash); { //methods @@ -200,27 +200,27 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { for (const StringName &F : snames) { MethodBind *mb = t->method_map[F]; - hash = hash_djb2_one_64(mb->get_name().hash(), hash); - hash = hash_djb2_one_64(mb->get_argument_count(), hash); - hash = hash_djb2_one_64(mb->get_argument_type(-1), hash); //return + hash = hash_murmur3_one_64(mb->get_name().hash(), hash); + hash = hash_murmur3_one_64(mb->get_argument_count(), hash); + hash = hash_murmur3_one_64(mb->get_argument_type(-1), hash); //return for (int i = 0; i < mb->get_argument_count(); i++) { const PropertyInfo info = mb->get_argument_info(i); - hash = hash_djb2_one_64(info.type, hash); - hash = hash_djb2_one_64(info.name.hash(), hash); - hash = hash_djb2_one_64(info.hint, hash); - hash = hash_djb2_one_64(info.hint_string.hash(), hash); + hash = hash_murmur3_one_64(info.type, hash); + hash = hash_murmur3_one_64(info.name.hash(), hash); + hash = hash_murmur3_one_64(info.hint, hash); + hash = hash_murmur3_one_64(info.hint_string.hash(), hash); } - hash = hash_djb2_one_64(mb->get_default_argument_count(), hash); + hash = hash_murmur3_one_64(mb->get_default_argument_count(), hash); for (int i = 0; i < mb->get_default_argument_count(); i++) { //hash should not change, i hope for tis Variant da = mb->get_default_argument(i); - hash = hash_djb2_one_64(da.hash(), hash); + hash = hash_murmur3_one_64(da.hash(), hash); } - hash = hash_djb2_one_64(mb->get_hint_flags(), hash); + hash = hash_murmur3_one_64(mb->get_hint_flags(), hash); } } @@ -235,8 +235,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { snames.sort_custom(); for (const StringName &F : snames) { - hash = hash_djb2_one_64(F.hash(), hash); - hash = hash_djb2_one_64(t->constant_map[F], hash); + hash = hash_murmur3_one_64(F.hash(), hash); + hash = hash_murmur3_one_64(t->constant_map[F], hash); } } @@ -252,9 +252,9 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { for (const StringName &F : snames) { MethodInfo &mi = t->signal_map[F]; - hash = hash_djb2_one_64(F.hash(), hash); + hash = hash_murmur3_one_64(F.hash(), hash); for (int i = 0; i < mi.arguments.size(); i++) { - hash = hash_djb2_one_64(mi.arguments[i].type, hash); + hash = hash_murmur3_one_64(mi.arguments[i].type, hash); } } } @@ -273,23 +273,23 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { PropertySetGet *psg = t->property_setget.getptr(F); ERR_FAIL_COND_V(!psg, 0); - hash = hash_djb2_one_64(F.hash(), hash); - hash = hash_djb2_one_64(psg->setter.hash(), hash); - hash = hash_djb2_one_64(psg->getter.hash(), hash); + hash = hash_murmur3_one_64(F.hash(), hash); + hash = hash_murmur3_one_64(psg->setter.hash(), hash); + hash = hash_murmur3_one_64(psg->getter.hash(), hash); } } //property list for (const PropertyInfo &F : t->property_list) { - hash = hash_djb2_one_64(F.name.hash(), hash); - hash = hash_djb2_one_64(F.type, hash); - hash = hash_djb2_one_64(F.hint, hash); - hash = hash_djb2_one_64(F.hint_string.hash(), hash); - hash = hash_djb2_one_64(F.usage, hash); + hash = hash_murmur3_one_64(F.name.hash(), hash); + hash = hash_murmur3_one_64(F.type, hash); + hash = hash_murmur3_one_64(F.hint, hash); + hash = hash_murmur3_one_64(F.hint_string.hash(), hash); + hash = hash_murmur3_one_64(F.usage, hash); } } - return hash; + return hash_fmix32(hash); #else return 0; #endif diff --git a/core/object/method_bind.cpp b/core/object/method_bind.cpp index a208c1a2b2..a4474ea53b 100644 --- a/core/object/method_bind.cpp +++ b/core/object/method_bind.cpp @@ -35,32 +35,27 @@ #include "method_bind.h" uint32_t MethodBind::get_hash() const { - uint32_t hash = hash_djb2_one_32(has_return() ? 1 : 0); - hash = hash_djb2_one_32(get_argument_count(), hash); - -#ifndef _MSC_VER -#warning This needs proper class name and argument type for hashing -#endif -#if 0 + uint32_t hash = hash_murmur3_one_32(has_return() ? 1 : 0); + hash = hash_murmur3_one_32(get_argument_count(), hash); for (int i = (has_return() ? -1 : 0); i < get_argument_count(); i++) { PropertyInfo pi = i == -1 ? get_return_info() : get_argument_info(i); - hash = hash_djb2_one_32(get_argument_type(i), hash); + hash = hash_murmur3_one_32(get_argument_type(i), hash); if (pi.class_name != StringName()) { - hash = hash_djb2_one_32(pi.class_name.operator String().hash(), hash); + hash = hash_murmur3_one_32(pi.class_name.operator String().hash(), hash); } } -#endif - hash = hash_djb2_one_32(get_default_argument_count(), hash); + + hash = hash_murmur3_one_32(get_default_argument_count(), hash); for (int i = 0; i < get_default_argument_count(); i++) { Variant v = get_default_argument(i); - hash = hash_djb2_one_32(v.hash(), hash); + hash = hash_murmur3_one_32(v.hash(), hash); } - hash = hash_djb2_one_32(is_const(), hash); - hash = hash_djb2_one_32(is_vararg(), hash); + hash = hash_murmur3_one_32(is_const(), hash); + hash = hash_murmur3_one_32(is_vararg(), hash); - return hash; + return hash_fmix32(hash); } PropertyInfo MethodBind::get_argument_info(int p_argument) const { diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h index 98ff7fa4ce..b0371f2ab5 100644 --- a/core/templates/hashfuncs.h +++ b/core/templates/hashfuncs.h @@ -62,7 +62,7 @@ static _FORCE_INLINE_ uint32_t hash_djb2(const char *p_cstr) { uint32_t c; while ((c = *chr++)) { - hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + hash = ((hash << 5) + hash) ^ c; /* hash * 33 ^ c */ } return hash; @@ -72,14 +72,14 @@ static _FORCE_INLINE_ uint32_t hash_djb2_buffer(const uint8_t *p_buff, int p_len uint32_t hash = p_prev; for (int i = 0; i < p_len; i++) { - hash = ((hash << 5) + hash) + p_buff[i]; /* hash * 33 + c */ + hash = ((hash << 5) + hash) ^ p_buff[i]; /* hash * 33 + c */ } return hash; } static _FORCE_INLINE_ uint32_t hash_djb2_one_32(uint32_t p_in, uint32_t p_prev = 5381) { - return ((p_prev << 5) + p_prev) + p_in; + return ((p_prev << 5) + p_prev) ^ p_in; } /** @@ -100,14 +100,76 @@ static _FORCE_INLINE_ uint32_t hash_one_uint64(const uint64_t p_int) { return uint32_t(v); } +#define HASH_MURMUR3_SEED 0x7F07C65 // Murmurhash3 32-bit version. // All MurmurHash versions are public domain software, and the author disclaims all copyright to their code. -static _FORCE_INLINE_ uint32_t rotl32(uint32_t x, int8_t r) { +static _FORCE_INLINE_ uint32_t hash_murmur3_one_32(uint32_t p_in, uint32_t p_seed = HASH_MURMUR3_SEED) { + p_in *= 0xcc9e2d51; + p_in = (p_in << 15) | (p_in >> 17); + p_in *= 0x1b873593; + + p_seed ^= p_in; + p_seed = (p_seed << 13) | (p_seed >> 19); + p_seed = p_seed * 5 + 0xe6546b64; + + return p_seed; +} + +static _FORCE_INLINE_ uint32_t hash_murmur3_one_float(float p_in, uint32_t p_seed = HASH_MURMUR3_SEED) { + union { + float f; + uint32_t i; + } u; + + // Normalize +/- 0.0 and NaN values so they hash the same. + if (p_in == 0.0f) { + u.f = 0.0; + } else if (Math::is_nan(p_in)) { + u.f = NAN; + } else { + u.f = p_in; + } + + return hash_murmur3_one_32(u.i, p_seed); +} + +static _FORCE_INLINE_ uint32_t hash_murmur3_one_64(uint64_t p_in, uint32_t p_seed = HASH_MURMUR3_SEED) { + p_seed = hash_murmur3_one_32(p_in & 0xFFFFFFFF, p_seed); + return hash_murmur3_one_32(p_in >> 32, p_seed); +} + +static _FORCE_INLINE_ uint32_t hash_murmur3_one_double(double p_in, uint32_t p_seed = HASH_MURMUR3_SEED) { + union { + double d; + uint64_t i; + } u; + + // Normalize +/- 0.0 and NaN values so they hash the same. + if (p_in == 0.0f) { + u.d = 0.0; + } else if (Math::is_nan(p_in)) { + u.d = NAN; + } else { + u.d = p_in; + } + + return hash_murmur3_one_64(u.i, p_seed); +} + +static _FORCE_INLINE_ uint32_t hash_murmur3_one_real(real_t p_in, uint32_t p_seed = HASH_MURMUR3_SEED) { +#ifdef REAL_T_IS_DOUBLE + return hash_murmur3_one_double(p_in, p_seed); +#else + return hash_murmur3_one_float(p_in, p_seed); +#endif +} + +static _FORCE_INLINE_ uint32_t hash_rotl32(uint32_t x, int8_t r) { return (x << r) | (x >> (32 - r)); } -static _FORCE_INLINE_ uint32_t fmix32(uint32_t h) { +static _FORCE_INLINE_ uint32_t hash_fmix32(uint32_t h) { h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; @@ -117,7 +179,7 @@ static _FORCE_INLINE_ uint32_t fmix32(uint32_t h) { return h; } -static _FORCE_INLINE_ uint32_t hash_murmur3_32(const void *key, int length, const uint32_t seed = 0x7F07C65) { +static _FORCE_INLINE_ uint32_t hash_murmur3_buffer(const void *key, int length, const uint32_t seed = HASH_MURMUR3_SEED) { // Although not required, this is a random prime number. const uint8_t *data = (const uint8_t *)key; const int nblocks = length / 4; @@ -133,11 +195,11 @@ static _FORCE_INLINE_ uint32_t hash_murmur3_32(const void *key, int length, cons uint32_t k1 = blocks[i]; k1 *= c1; - k1 = rotl32(k1, 15); + k1 = hash_rotl32(k1, 15); k1 *= c2; h1 ^= k1; - h1 = rotl32(h1, 13); + h1 = hash_rotl32(h1, 13); h1 = h1 * 5 + 0xe6546b64; } @@ -155,14 +217,14 @@ static _FORCE_INLINE_ uint32_t hash_murmur3_32(const void *key, int length, cons case 1: k1 ^= tail[0]; k1 *= c1; - k1 = rotl32(k1, 15); + k1 = hash_rotl32(k1, 15); k1 *= c2; h1 ^= k1; }; // Finalize with additional bit mixing. h1 ^= length; - return fmix32(h1); + return hash_fmix32(h1); } static _FORCE_INLINE_ uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381) { @@ -184,7 +246,7 @@ static _FORCE_INLINE_ uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev } template -static _FORCE_INLINE_ uint32_t make_uint32_t(T p_in) { +static _FORCE_INLINE_ uint32_t hash_make_uint32_t(T p_in) { union { T t; uint32_t _u32; @@ -213,11 +275,11 @@ static _FORCE_INLINE_ uint64_t hash_djb2_one_float_64(double p_in, uint64_t p_pr } static _FORCE_INLINE_ uint64_t hash_djb2_one_64(uint64_t p_in, uint64_t p_prev = 5381) { - return ((p_prev << 5) + p_prev) + p_in; + return ((p_prev << 5) + p_prev) ^ p_in; } template -static _FORCE_INLINE_ uint64_t make_uint64_t(T p_in) { +static _FORCE_INLINE_ uint64_t hash_make_uint64_t(T p_in) { union { T t; uint64_t _u64; @@ -241,9 +303,9 @@ struct HashMapHasherDefault { static _FORCE_INLINE_ uint32_t hash(const String &p_string) { return p_string.hash(); } static _FORCE_INLINE_ uint32_t hash(const char *p_cstr) { return hash_djb2(p_cstr); } - static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar) { return fmix32(p_wchar); } - static _FORCE_INLINE_ uint32_t hash(const char16_t p_uchar) { return fmix32(p_uchar); } - static _FORCE_INLINE_ uint32_t hash(const char32_t p_uchar) { return fmix32(p_uchar); } + static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar) { return hash_fmix32(p_wchar); } + static _FORCE_INLINE_ uint32_t hash(const char16_t p_uchar) { return hash_fmix32(p_uchar); } + static _FORCE_INLINE_ uint32_t hash(const char32_t p_uchar) { return hash_fmix32(p_uchar); } static _FORCE_INLINE_ uint32_t hash(const RID &p_rid) { return hash_one_uint64(p_rid.get_id()); } static _FORCE_INLINE_ uint32_t hash(const StringName &p_string_name) { return p_string_name.hash(); } static _FORCE_INLINE_ uint32_t hash(const NodePath &p_path) { return p_path.hash(); } @@ -251,21 +313,59 @@ struct HashMapHasherDefault { static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int) { return hash_one_uint64(p_int); } static _FORCE_INLINE_ uint32_t hash(const int64_t p_int) { return hash_one_uint64(p_int); } - static _FORCE_INLINE_ uint32_t hash(const float p_float) { return hash_djb2_one_float(p_float); } - static _FORCE_INLINE_ uint32_t hash(const double p_double) { return hash_djb2_one_float(p_double); } - static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return fmix32(p_int); } - static _FORCE_INLINE_ uint32_t hash(const int32_t p_int) { return fmix32(p_int); } - static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return fmix32(p_int); } - static _FORCE_INLINE_ uint32_t hash(const int16_t p_int) { return fmix32(p_int); } - static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int) { return fmix32(p_int); } - static _FORCE_INLINE_ uint32_t hash(const int8_t p_int) { return fmix32(p_int); } - static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector2i)); } - static _FORCE_INLINE_ uint32_t hash(const Vector3i &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector3i)); } - static _FORCE_INLINE_ uint32_t hash(const Vector2 &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector2)); } - static _FORCE_INLINE_ uint32_t hash(const Vector3 &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector3)); } - static _FORCE_INLINE_ uint32_t hash(const Rect2i &p_rect) { return hash_murmur3_32(&p_rect, sizeof(Rect2i)); } - static _FORCE_INLINE_ uint32_t hash(const Rect2 &p_rect) { return hash_murmur3_32(&p_rect, sizeof(Rect2)); } - static _FORCE_INLINE_ uint32_t hash(const AABB &p_aabb) { return hash_murmur3_32(&p_aabb, sizeof(AABB)); } + static _FORCE_INLINE_ uint32_t hash(const float p_float) { return hash_murmur3_one_float(p_float); } + static _FORCE_INLINE_ uint32_t hash(const double p_double) { return hash_murmur3_one_double(p_double); } + static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return hash_fmix32(p_int); } + static _FORCE_INLINE_ uint32_t hash(const int32_t p_int) { return hash_fmix32(p_int); } + static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return hash_fmix32(p_int); } + static _FORCE_INLINE_ uint32_t hash(const int16_t p_int) { return hash_fmix32(p_int); } + static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int) { return hash_fmix32(p_int); } + static _FORCE_INLINE_ uint32_t hash(const int8_t p_int) { return hash_fmix32(p_int); } + static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) { + uint32_t h = hash_murmur3_one_32(p_vec.x); + h = hash_murmur3_one_32(p_vec.y, h); + return hash_fmix32(h); + } + static _FORCE_INLINE_ uint32_t hash(const Vector3i &p_vec) { + uint32_t h = hash_murmur3_one_32(p_vec.x); + h = hash_murmur3_one_32(p_vec.y, h); + h = hash_murmur3_one_32(p_vec.z, h); + return hash_fmix32(h); + } + static _FORCE_INLINE_ uint32_t hash(const Vector2 &p_vec) { + uint32_t h = hash_murmur3_one_real(p_vec.x); + h = hash_murmur3_one_real(p_vec.y, h); + return hash_fmix32(h); + } + static _FORCE_INLINE_ uint32_t hash(const Vector3 &p_vec) { + uint32_t h = hash_murmur3_one_real(p_vec.x); + h = hash_murmur3_one_real(p_vec.y, h); + h = hash_murmur3_one_real(p_vec.z, h); + return hash_fmix32(h); + } + static _FORCE_INLINE_ uint32_t hash(const Rect2i &p_rect) { + uint32_t h = hash_murmur3_one_32(p_rect.position.x); + h = hash_murmur3_one_32(p_rect.position.y, h); + h = hash_murmur3_one_32(p_rect.size.x, h); + h = hash_murmur3_one_32(p_rect.size.y, h); + return hash_fmix32(h); + } + static _FORCE_INLINE_ uint32_t hash(const Rect2 &p_rect) { + uint32_t h = hash_murmur3_one_real(p_rect.position.x); + h = hash_murmur3_one_real(p_rect.position.y, h); + h = hash_murmur3_one_real(p_rect.size.x, h); + h = hash_murmur3_one_real(p_rect.size.y, h); + return hash_fmix32(h); + } + static _FORCE_INLINE_ uint32_t hash(const AABB &p_aabb) { + uint32_t h = hash_murmur3_one_real(p_aabb.position.x); + h = hash_murmur3_one_real(p_aabb.position.y, h); + h = hash_murmur3_one_real(p_aabb.position.z, h); + h = hash_murmur3_one_real(p_aabb.size.x, h); + h = hash_murmur3_one_real(p_aabb.size.y, h); + h = hash_murmur3_one_real(p_aabb.size.z, h); + return hash_fmix32(h); + } }; template diff --git a/core/variant/array.cpp b/core/variant/array.cpp index 599c3e1dfe..af166e09a3 100644 --- a/core/variant/array.cpp +++ b/core/variant/array.cpp @@ -190,13 +190,13 @@ uint32_t Array::recursive_hash(int recursion_count) const { return 0; } - uint32_t h = hash_djb2_one_32(Variant::ARRAY); + uint32_t h = hash_murmur3_one_32(Variant::ARRAY); recursion_count++; for (int i = 0; i < _p->array.size(); i++) { - h = hash_djb2_one_32(_p->array[i].recursive_hash(recursion_count), h); + h = hash_murmur3_one_32(_p->array[i].recursive_hash(recursion_count), h); } - return h; + return hash_fmix32(h); } bool Array::_assign(const Array &p_array) { diff --git a/core/variant/callable.cpp b/core/variant/callable.cpp index 516b8f2d51..5453f0d5c6 100644 --- a/core/variant/callable.cpp +++ b/core/variant/callable.cpp @@ -143,7 +143,8 @@ uint32_t Callable::hash() const { return custom->hash(); } else { uint32_t hash = method.hash(); - return hash_djb2_one_64(object, hash); + hash = hash_murmur3_one_64(object, hash); + return hash_fmix32(hash); } } diff --git a/core/variant/dictionary.cpp b/core/variant/dictionary.cpp index 822021f440..d9f4359ee5 100644 --- a/core/variant/dictionary.cpp +++ b/core/variant/dictionary.cpp @@ -298,15 +298,15 @@ uint32_t Dictionary::recursive_hash(int recursion_count) const { return 0; } - uint32_t h = hash_djb2_one_32(Variant::DICTIONARY); + uint32_t h = hash_murmur3_one_32(Variant::DICTIONARY); recursion_count++; for (const KeyValue &E : _p->variant_map) { - h = hash_djb2_one_32(E.key.recursive_hash(recursion_count), h); - h = hash_djb2_one_32(E.value.recursive_hash(recursion_count), h); + h = hash_murmur3_one_32(E.key.recursive_hash(recursion_count), h); + h = hash_murmur3_one_32(E.value.recursive_hash(recursion_count), h); } - return h; + return hash_fmix32(h); } Array Dictionary::keys() const { diff --git a/core/variant/variant.cpp b/core/variant/variant.cpp index aa640924e4..6007268e21 100644 --- a/core/variant/variant.cpp +++ b/core/variant/variant.cpp @@ -2780,7 +2780,7 @@ uint32_t Variant::recursive_hash(int recursion_count) const { return hash_one_uint64((uint64_t)_data._int); } break; case FLOAT: { - return hash_djb2_one_float(_data._float); + return hash_murmur3_one_float(_data._float); } break; case STRING: { return reinterpret_cast(_data._mem)->hash(); @@ -2788,50 +2788,102 @@ uint32_t Variant::recursive_hash(int recursion_count) const { // math types case VECTOR2: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Vector2)); + return HashMapHasherDefault::hash(*reinterpret_cast(_data._mem)); } break; case VECTOR2I: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Vector2i)); + return HashMapHasherDefault::hash(*reinterpret_cast(_data._mem)); } break; case RECT2: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Rect2)); + return HashMapHasherDefault::hash(*reinterpret_cast(_data._mem)); } break; case RECT2I: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Rect2i)); + return HashMapHasherDefault::hash(*reinterpret_cast(_data._mem)); } break; case TRANSFORM2D: { - return hash_murmur3_32(reinterpret_cast(_data._transform2d), sizeof(Transform2D)); + uint32_t h = HASH_MURMUR3_SEED; + const Transform2D &t = *_data._transform2d; + h = hash_murmur3_one_real(t[0].x, h); + h = hash_murmur3_one_real(t[0].y, h); + h = hash_murmur3_one_real(t[1].x, h); + h = hash_murmur3_one_real(t[1].y, h); + h = hash_murmur3_one_real(t[2].x, h); + h = hash_murmur3_one_real(t[2].y, h); + + return hash_fmix32(h); } break; case VECTOR3: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Vector3)); + return HashMapHasherDefault::hash(*reinterpret_cast(_data._mem)); } break; case VECTOR3I: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Vector3i)); + return HashMapHasherDefault::hash(*reinterpret_cast(_data._mem)); } break; case PLANE: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Plane)); + uint32_t h = HASH_MURMUR3_SEED; + const Plane &p = *reinterpret_cast(_data._mem); + h = hash_murmur3_one_real(p.normal.x, h); + h = hash_murmur3_one_real(p.normal.y, h); + h = hash_murmur3_one_real(p.normal.z, h); + h = hash_murmur3_one_real(p.d, h); + return hash_fmix32(h); } break; case AABB: { - return hash_murmur3_32(_data._aabb, sizeof(AABB)); + return HashMapHasherDefault::hash(*_data._aabb); } break; case QUATERNION: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Quaternion)); + uint32_t h = HASH_MURMUR3_SEED; + const Quaternion &q = *reinterpret_cast(_data._mem); + h = hash_murmur3_one_real(q.x, h); + h = hash_murmur3_one_real(q.y, h); + h = hash_murmur3_one_real(q.z, h); + h = hash_murmur3_one_real(q.w, h); + return hash_fmix32(h); } break; case BASIS: { - return hash_murmur3_32(_data._basis, sizeof(Basis)); + uint32_t h = HASH_MURMUR3_SEED; + const Basis &b = *_data._basis; + h = hash_murmur3_one_real(b[0].x, h); + h = hash_murmur3_one_real(b[0].y, h); + h = hash_murmur3_one_real(b[0].z, h); + h = hash_murmur3_one_real(b[1].x, h); + h = hash_murmur3_one_real(b[1].y, h); + h = hash_murmur3_one_real(b[1].z, h); + h = hash_murmur3_one_real(b[2].x, h); + h = hash_murmur3_one_real(b[2].y, h); + h = hash_murmur3_one_real(b[2].z, h); + return hash_fmix32(h); } break; case TRANSFORM3D: { - return hash_murmur3_32(_data._transform3d, sizeof(Transform3D)); + uint32_t h = HASH_MURMUR3_SEED; + const Transform3D &t = *_data._transform3d; + h = hash_murmur3_one_real(t.basis[0].x, h); + h = hash_murmur3_one_real(t.basis[0].y, h); + h = hash_murmur3_one_real(t.basis[0].z, h); + h = hash_murmur3_one_real(t.basis[1].x, h); + h = hash_murmur3_one_real(t.basis[1].y, h); + h = hash_murmur3_one_real(t.basis[1].z, h); + h = hash_murmur3_one_real(t.basis[2].x, h); + h = hash_murmur3_one_real(t.basis[2].y, h); + h = hash_murmur3_one_real(t.basis[2].z, h); + h = hash_murmur3_one_real(t.origin.x, h); + h = hash_murmur3_one_real(t.origin.y, h); + h = hash_murmur3_one_real(t.origin.z, h); + return hash_fmix32(h); } break; // misc types case COLOR: { - return hash_murmur3_32(reinterpret_cast(_data._mem), sizeof(Color)); + uint32_t h = HASH_MURMUR3_SEED; + const Color &c = *reinterpret_cast(_data._mem); + h = hash_murmur3_one_float(c.r, h); + h = hash_murmur3_one_float(c.g, h); + h = hash_murmur3_one_float(c.b, h); + h = hash_murmur3_one_float(c.a, h); + return hash_fmix32(h); } break; case RID: { return hash_one_uint64(reinterpret_cast(_data._mem)->get_id()); } break; case OBJECT: { - return hash_one_uint64(make_uint64_t(_get_obj().obj)); + return hash_one_uint64(hash_make_uint64_t(_get_obj().obj)); } break; case STRING_NAME: { return reinterpret_cast(_data._mem)->hash(); @@ -2850,7 +2902,7 @@ uint32_t Variant::recursive_hash(int recursion_count) const { case SIGNAL: { const Signal &s = *reinterpret_cast(_data._mem); uint32_t hash = s.get_name().hash(); - return hash_djb2_one_64(s.get_object_id(), hash); + return hash_murmur3_one_64(s.get_object_id(), hash); } break; case ARRAY: { const Array &arr = *reinterpret_cast(_data._mem); @@ -2862,9 +2914,9 @@ uint32_t Variant::recursive_hash(int recursion_count) const { int len = arr.size(); if (likely(len)) { const uint8_t *r = arr.ptr(); - return hash_murmur3_32((uint8_t *)&r[0], len); + return hash_murmur3_buffer((uint8_t *)&r[0], len); } else { - return hash_djb2_one_64(0); + return hash_murmur3_one_64(0); } } break; @@ -2873,9 +2925,9 @@ uint32_t Variant::recursive_hash(int recursion_count) const { int len = arr.size(); if (likely(len)) { const int32_t *r = arr.ptr(); - return hash_murmur3_32((uint8_t *)&r[0], len * sizeof(int32_t)); + return hash_murmur3_buffer((uint8_t *)&r[0], len * sizeof(int32_t)); } else { - return hash_djb2_one_64(0); + return hash_murmur3_one_64(0); } } break; @@ -2884,9 +2936,9 @@ uint32_t Variant::recursive_hash(int recursion_count) const { int len = arr.size(); if (likely(len)) { const int64_t *r = arr.ptr(); - return hash_murmur3_32((uint8_t *)&r[0], len * sizeof(int64_t)); + return hash_murmur3_buffer((uint8_t *)&r[0], len * sizeof(int64_t)); } else { - return hash_djb2_one_64(0); + return hash_murmur3_one_64(0); } } break; @@ -2896,9 +2948,13 @@ uint32_t Variant::recursive_hash(int recursion_count) const { if (likely(len)) { const float *r = arr.ptr(); - return hash_murmur3_32((uint8_t *)&r[0], len * sizeof(float)); + uint32_t h = HASH_MURMUR3_SEED; + for (int32_t i = 0; i < len; i++) { + h = hash_murmur3_one_float(r[i], h); + } + return hash_fmix32(h); } else { - return hash_djb2_one_float(0.0); + return hash_murmur3_one_float(0.0); } } break; @@ -2908,14 +2964,18 @@ uint32_t Variant::recursive_hash(int recursion_count) const { if (likely(len)) { const double *r = arr.ptr(); - return hash_murmur3_32((uint8_t *)&r[0], len * sizeof(double)); + uint32_t h = HASH_MURMUR3_SEED; + for (int32_t i = 0; i < len; i++) { + h = hash_murmur3_one_double(r[i], h); + } + return hash_fmix32(h); } else { - return hash_djb2_one_float(0.0); + return hash_murmur3_one_float(0.0); } } break; case PACKED_STRING_ARRAY: { - uint32_t hash = 5831; + uint32_t hash = HASH_MURMUR3_SEED; const Vector &arr = PackedArrayRef::get_array(_data.packed_array); int len = arr.size(); @@ -2923,14 +2983,15 @@ uint32_t Variant::recursive_hash(int recursion_count) const { const String *r = arr.ptr(); for (int i = 0; i < len; i++) { - hash = hash_djb2_one_32(r[i].hash(), hash); + hash = hash_murmur3_one_32(r[i].hash(), hash); } + hash = hash_fmix32(hash); } return hash; } break; case PACKED_VECTOR2_ARRAY: { - uint32_t hash = 5831; + uint32_t hash = HASH_MURMUR3_SEED; const Vector &arr = PackedArrayRef::get_array(_data.packed_array); int len = arr.size(); @@ -2938,15 +2999,16 @@ uint32_t Variant::recursive_hash(int recursion_count) const { const Vector2 *r = arr.ptr(); for (int i = 0; i < len; i++) { - hash = hash_djb2_one_float(r[i].x, hash); - hash = hash_djb2_one_float(r[i].y, hash); + hash = hash_murmur3_one_real(r[i].x, hash); + hash = hash_murmur3_one_real(r[i].y, hash); } + hash = hash_fmix32(hash); } return hash; } break; case PACKED_VECTOR3_ARRAY: { - uint32_t hash = 5831; + uint32_t hash = HASH_MURMUR3_SEED; const Vector &arr = PackedArrayRef::get_array(_data.packed_array); int len = arr.size(); @@ -2954,16 +3016,17 @@ uint32_t Variant::recursive_hash(int recursion_count) const { const Vector3 *r = arr.ptr(); for (int i = 0; i < len; i++) { - hash = hash_djb2_one_float(r[i].x, hash); - hash = hash_djb2_one_float(r[i].y, hash); - hash = hash_djb2_one_float(r[i].z, hash); + hash = hash_murmur3_one_real(r[i].x, hash); + hash = hash_murmur3_one_real(r[i].y, hash); + hash = hash_murmur3_one_real(r[i].z, hash); } + hash = hash_fmix32(hash); } return hash; } break; case PACKED_COLOR_ARRAY: { - uint32_t hash = 5831; + uint32_t hash = HASH_MURMUR3_SEED; const Vector &arr = PackedArrayRef::get_array(_data.packed_array); int len = arr.size(); @@ -2971,11 +3034,12 @@ uint32_t Variant::recursive_hash(int recursion_count) const { const Color *r = arr.ptr(); for (int i = 0; i < len; i++) { - hash = hash_djb2_one_float(r[i].r, hash); - hash = hash_djb2_one_float(r[i].g, hash); - hash = hash_djb2_one_float(r[i].b, hash); - hash = hash_djb2_one_float(r[i].a, hash); + hash = hash_murmur3_one_float(r[i].r, hash); + hash = hash_murmur3_one_float(r[i].g, hash); + hash = hash_murmur3_one_float(r[i].b, hash); + hash = hash_murmur3_one_float(r[i].a, hash); } + hash = hash_fmix32(hash); } return hash; diff --git a/core/variant/variant_call.cpp b/core/variant/variant_call.cpp index 6e8dc64811..cb9dfe478b 100644 --- a/core/variant/variant_call.cpp +++ b/core/variant/variant_call.cpp @@ -1170,19 +1170,19 @@ uint32_t Variant::get_builtin_method_hash(Variant::Type p_type, const StringName ERR_FAIL_INDEX_V(p_type, Variant::VARIANT_MAX, 0); const VariantBuiltInMethodInfo *method = builtin_method_info[p_type].lookup_ptr(p_method); ERR_FAIL_COND_V(!method, 0); - uint32_t hash = hash_djb2_one_32(method->is_const); - hash = hash_djb2_one_32(method->is_static, hash); - hash = hash_djb2_one_32(method->is_vararg, hash); - hash = hash_djb2_one_32(method->has_return_type, hash); + uint32_t hash = hash_murmur3_one_32(method->is_const); + hash = hash_murmur3_one_32(method->is_static, hash); + hash = hash_murmur3_one_32(method->is_vararg, hash); + hash = hash_murmur3_one_32(method->has_return_type, hash); if (method->has_return_type) { - hash = hash_djb2_one_32(method->return_type, hash); + hash = hash_murmur3_one_32(method->return_type, hash); } - hash = hash_djb2_one_32(method->argument_count, hash); + hash = hash_murmur3_one_32(method->argument_count, hash); for (int i = 0; i < method->argument_count; i++) { - hash = method->get_argument_type(i); + hash = hash_murmur3_one_32(method->get_argument_type(i), hash); } - return hash; + return hash_fmix32(hash); } void Variant::get_method_list(List *p_list) const { diff --git a/core/variant/variant_utility.cpp b/core/variant/variant_utility.cpp index 66badce268..7fabdcbc82 100644 --- a/core/variant/variant_utility.cpp +++ b/core/variant/variant_utility.cpp @@ -1423,17 +1423,17 @@ uint32_t Variant::get_utility_function_hash(const StringName &p_name) { const VariantUtilityFunctionInfo *bfi = utility_function_table.lookup_ptr(p_name); ERR_FAIL_COND_V(!bfi, 0); - uint32_t hash = hash_djb2_one_32(bfi->is_vararg); - hash = hash_djb2_one_32(bfi->returns_value, hash); + uint32_t hash = hash_murmur3_one_32(bfi->is_vararg); + hash = hash_murmur3_one_32(bfi->returns_value, hash); if (bfi->returns_value) { - hash = hash_djb2_one_32(bfi->return_type, hash); + hash = hash_murmur3_one_32(bfi->return_type, hash); } - hash = hash_djb2_one_32(bfi->argcount, hash); + hash = hash_murmur3_one_32(bfi->argcount, hash); for (int i = 0; i < bfi->argcount; i++) { - hash = hash_djb2_one_32(bfi->get_arg_type(i), hash); + hash = hash_murmur3_one_32(bfi->get_arg_type(i), hash); } - return hash; + return hash_fmix32(hash); } void Variant::get_utility_function_list(List *r_functions) { diff --git a/drivers/vulkan/rendering_device_vulkan.h b/drivers/vulkan/rendering_device_vulkan.h index 903a39b3d0..3b21ee67a1 100644 --- a/drivers/vulkan/rendering_device_vulkan.h +++ b/drivers/vulkan/rendering_device_vulkan.h @@ -457,17 +457,17 @@ class RenderingDeviceVulkan : public RenderingDevice { uint32_t hash() const { int vdc = vertex_formats.size(); - uint32_t h = hash_djb2_one_32(vdc); + uint32_t h = hash_murmur3_one_32(vdc); const VertexAttribute *ptr = vertex_formats.ptr(); for (int i = 0; i < vdc; i++) { const VertexAttribute &vd = ptr[i]; - h = hash_djb2_one_32(vd.location, h); - h = hash_djb2_one_32(vd.offset, h); - h = hash_djb2_one_32(vd.format, h); - h = hash_djb2_one_32(vd.stride, h); - h = hash_djb2_one_32(vd.frequency, h); + h = hash_murmur3_one_32(vd.location, h); + h = hash_murmur3_one_32(vd.offset, h); + h = hash_murmur3_one_32(vd.format, h); + h = hash_murmur3_one_32(vd.stride, h); + h = hash_murmur3_one_32(vd.frequency, h); } - return h; + return hash_fmix32(h); } }; diff --git a/editor/debugger/debug_adapter/debug_adapter_types.h b/editor/debugger/debug_adapter/debug_adapter_types.h index 4d77b6d51c..fd66905f9b 100644 --- a/editor/debugger/debug_adapter/debug_adapter_types.h +++ b/editor/debugger/debug_adapter/debug_adapter_types.h @@ -220,7 +220,7 @@ struct StackFrame { int column; static uint32_t hash(const StackFrame &p_frame) { - return hash_djb2_one_32(p_frame.id); + return hash_murmur3_one_32(p_frame.id); } bool operator==(const StackFrame &p_other) const { return id == p_other.id; diff --git a/editor/debugger/editor_debugger_node.h b/editor/debugger/editor_debugger_node.h index 8dc53690eb..d50cbec291 100644 --- a/editor/debugger/editor_debugger_node.h +++ b/editor/debugger/editor_debugger_node.h @@ -72,7 +72,7 @@ private: static uint32_t hash(const Breakpoint &p_val) { uint32_t h = HashMapHasherDefault::hash(p_val.source); - return hash_djb2_one_32(p_val.line, h); + return hash_murmur3_one_32(p_val.line, h); } bool operator==(const Breakpoint &p_b) const { return (line == p_b.line && source == p_b.source); diff --git a/editor/plugins/mesh_instance_3d_editor_plugin.cpp b/editor/plugins/mesh_instance_3d_editor_plugin.cpp index d85087b5ea..d1f858315c 100644 --- a/editor/plugins/mesh_instance_3d_editor_plugin.cpp +++ b/editor/plugins/mesh_instance_3d_editor_plugin.cpp @@ -350,8 +350,8 @@ struct MeshInstance3DEditorEdgeSort { Vector2 b; static uint32_t hash(const MeshInstance3DEditorEdgeSort &p_edge) { - uint32_t h = hash_djb2_one_32(HashMapHasherDefault::hash(p_edge.a)); - return hash_djb2_one_32(HashMapHasherDefault::hash(p_edge.b), h); + uint32_t h = hash_murmur3_one_32(HashMapHasherDefault::hash(p_edge.a)); + return hash_fmix32(hash_murmur3_one_32(HashMapHasherDefault::hash(p_edge.b), h)); } bool operator==(const MeshInstance3DEditorEdgeSort &p_b) const { diff --git a/modules/csg/csg.h b/modules/csg/csg.h index 53a9e5d722..738e3d68ea 100644 --- a/modules/csg/csg.h +++ b/modules/csg/csg.h @@ -130,9 +130,9 @@ struct CSGBrushOperation { struct VertexKeyHash { static _FORCE_INLINE_ uint32_t hash(const VertexKey &p_vk) { - uint32_t h = hash_djb2_one_32(p_vk.x); - h = hash_djb2_one_32(p_vk.y, h); - h = hash_djb2_one_32(p_vk.z, h); + uint32_t h = hash_murmur3_one_32(p_vk.x); + h = hash_murmur3_one_32(p_vk.y, h); + h = hash_murmur3_one_32(p_vk.z, h); return h; } }; diff --git a/modules/csg/csg_shape.h b/modules/csg/csg_shape.h index 0eaf5c3727..0b49dc4609 100644 --- a/modules/csg/csg_shape.h +++ b/modules/csg/csg_shape.h @@ -74,9 +74,9 @@ private: struct Vector3Hasher { _ALWAYS_INLINE_ uint32_t hash(const Vector3 &p_vec3) const { - uint32_t h = hash_djb2_one_float(p_vec3.x); - h = hash_djb2_one_float(p_vec3.y, h); - h = hash_djb2_one_float(p_vec3.z, h); + uint32_t h = hash_murmur3_one_float(p_vec3.x); + h = hash_murmur3_one_float(p_vec3.y, h); + h = hash_murmur3_one_float(p_vec3.z, h); return h; } }; diff --git a/modules/gdscript/gdscript_lambda_callable.cpp b/modules/gdscript/gdscript_lambda_callable.cpp index c43fa12c8c..a25bf9a306 100644 --- a/modules/gdscript/gdscript_lambda_callable.cpp +++ b/modules/gdscript/gdscript_lambda_callable.cpp @@ -91,7 +91,7 @@ GDScriptLambdaCallable::GDScriptLambdaCallable(Ref p_script, GDScriptF function = p_function; captures = p_captures; - h = (uint32_t)hash_djb2_one_64((uint64_t)this); + h = (uint32_t)hash_murmur3_one_64((uint64_t)this); } bool GDScriptLambdaSelfCallable::compare_equal(const CallableCustom *p_a, const CallableCustom *p_b) { @@ -161,7 +161,7 @@ GDScriptLambdaSelfCallable::GDScriptLambdaSelfCallable(Ref p_self, G function = p_function; captures = p_captures; - h = (uint32_t)hash_djb2_one_64((uint64_t)this); + h = (uint32_t)hash_murmur3_one_64((uint64_t)this); } GDScriptLambdaSelfCallable::GDScriptLambdaSelfCallable(Object *p_self, GDScriptFunction *p_function, const Vector &p_captures) { @@ -169,5 +169,5 @@ GDScriptLambdaSelfCallable::GDScriptLambdaSelfCallable(Object *p_self, GDScriptF function = p_function; captures = p_captures; - h = (uint32_t)hash_djb2_one_64((uint64_t)this); + h = (uint32_t)hash_murmur3_one_64((uint64_t)this); } diff --git a/modules/gdscript/gdscript_rpc_callable.cpp b/modules/gdscript/gdscript_rpc_callable.cpp index 07ef5aefcb..63ebd8acf5 100644 --- a/modules/gdscript/gdscript_rpc_callable.cpp +++ b/modules/gdscript/gdscript_rpc_callable.cpp @@ -71,7 +71,7 @@ GDScriptRPCCallable::GDScriptRPCCallable(Object *p_object, const StringName &p_m object = p_object; method = p_method; h = method.hash(); - h = hash_djb2_one_64(object->get_instance_id(), h); + h = hash_murmur3_one_64(object->get_instance_id(), h); node = Object::cast_to(object); ERR_FAIL_COND_MSG(!node, "RPC can only be defined on class that extends Node."); } diff --git a/modules/lightmapper_rd/lightmapper_rd.h b/modules/lightmapper_rd/lightmapper_rd.h index 503f5f7009..bf9f9b5954 100644 --- a/modules/lightmapper_rd/lightmapper_rd.h +++ b/modules/lightmapper_rd/lightmapper_rd.h @@ -110,12 +110,12 @@ class LightmapperRD : public Lightmapper { struct EdgeHash { _FORCE_INLINE_ static uint32_t hash(const Edge &p_edge) { - uint32_t h = hash_djb2_one_float(p_edge.a.x); - h = hash_djb2_one_float(p_edge.a.y, h); - h = hash_djb2_one_float(p_edge.a.z, h); - h = hash_djb2_one_float(p_edge.b.x, h); - h = hash_djb2_one_float(p_edge.b.y, h); - h = hash_djb2_one_float(p_edge.b.z, h); + uint32_t h = hash_murmur3_one_float(p_edge.a.x); + h = hash_murmur3_one_float(p_edge.a.y, h); + h = hash_murmur3_one_float(p_edge.a.z, h); + h = hash_murmur3_one_float(p_edge.b.x, h); + h = hash_murmur3_one_float(p_edge.b.y, h); + h = hash_murmur3_one_float(p_edge.b.z, h); return h; } }; @@ -146,15 +146,15 @@ class LightmapperRD : public Lightmapper { struct VertexHash { _FORCE_INLINE_ static uint32_t hash(const Vertex &p_vtx) { - uint32_t h = hash_djb2_one_float(p_vtx.position[0]); - h = hash_djb2_one_float(p_vtx.position[1], h); - h = hash_djb2_one_float(p_vtx.position[2], h); - h = hash_djb2_one_float(p_vtx.uv[0], h); - h = hash_djb2_one_float(p_vtx.uv[1], h); - h = hash_djb2_one_float(p_vtx.normal_xy[0], h); - h = hash_djb2_one_float(p_vtx.normal_xy[1], h); - h = hash_djb2_one_float(p_vtx.normal_z, h); - return h; + uint32_t h = hash_murmur3_one_float(p_vtx.position[0]); + h = hash_murmur3_one_float(p_vtx.position[1], h); + h = hash_murmur3_one_float(p_vtx.position[2], h); + h = hash_murmur3_one_float(p_vtx.uv[0], h); + h = hash_murmur3_one_float(p_vtx.uv[1], h); + h = hash_murmur3_one_float(p_vtx.normal_xy[0], h); + h = hash_murmur3_one_float(p_vtx.normal_xy[1], h); + h = hash_murmur3_one_float(p_vtx.normal_z, h); + return hash_fmix32(h); } }; diff --git a/modules/mono/managed_callable.cpp b/modules/mono/managed_callable.cpp index 4f7783b765..c159bb9eea 100644 --- a/modules/mono/managed_callable.cpp +++ b/modules/mono/managed_callable.cpp @@ -66,9 +66,8 @@ bool ManagedCallable::compare_less(const CallableCustom *p_a, const CallableCust } uint32_t ManagedCallable::hash() const { - // hmm uint32_t hash = delegate_invoke->get_name().hash(); - return hash_djb2_one_64(delegate_handle.handle, hash); + return hash_murmur3_one_64(delegate_handle.handle, hash); } String ManagedCallable::get_as_text() const { diff --git a/modules/mono/signal_awaiter_utils.cpp b/modules/mono/signal_awaiter_utils.cpp index 315a9c29f6..618e1b58e0 100644 --- a/modules/mono/signal_awaiter_utils.cpp +++ b/modules/mono/signal_awaiter_utils.cpp @@ -63,7 +63,7 @@ bool SignalAwaiterCallable::compare_less(const CallableCustom *p_a, const Callab uint32_t SignalAwaiterCallable::hash() const { uint32_t hash = signal.hash(); - return hash_djb2_one_64(target_id, hash); + return hash_murmur3_one_64(target_id, hash); } String SignalAwaiterCallable::get_as_text() const { @@ -164,7 +164,7 @@ bool EventSignalCallable::compare_less(const CallableCustom *p_a, const Callable uint32_t EventSignalCallable::hash() const { uint32_t hash = event_signal->field->get_name().hash(); - return hash_djb2_one_64(owner->get_instance_id(), hash); + return hash_murmur3_one_64(owner->get_instance_id(), hash); } String EventSignalCallable::get_as_text() const { diff --git a/modules/raycast/raycast_occlusion_cull.h b/modules/raycast/raycast_occlusion_cull.h index 4474031991..6562c4e9c4 100644 --- a/modules/raycast/raycast_occlusion_cull.h +++ b/modules/raycast/raycast_occlusion_cull.h @@ -87,8 +87,8 @@ private: RID instance; static uint32_t hash(const InstanceID &p_ins) { - uint32_t h = hash_djb2_one_64(p_ins.scenario.get_id()); - return hash_djb2_one_64(p_ins.instance.get_id(), h); + uint32_t h = hash_murmur3_one_64(p_ins.scenario.get_id()); + return hash_fmix32(hash_murmur3_one_64(p_ins.instance.get_id(), h)); } bool operator==(const InstanceID &rhs) const { return instance == rhs.instance && rhs.scenario == scenario; diff --git a/scene/3d/label_3d.cpp b/scene/3d/label_3d.cpp index 6ed4ce8c5b..0849b2c631 100644 --- a/scene/3d/label_3d.cpp +++ b/scene/3d/label_3d.cpp @@ -376,7 +376,7 @@ void Label3D::_generate_glyph_surfaces(const Glyph &p_glyph, Vector2 &r_offset, } else { mat_hash = hash_one_uint64(0); } - mat_hash = hash_djb2_one_64(p_priority | (p_outline_size << 31), mat_hash); + mat_hash = hash_fmix32(hash_murmur3_one_64(p_priority | (p_outline_size << 31), mat_hash)); if (!surfaces.has(mat_hash)) { SurfaceData surf; diff --git a/scene/3d/lightmap_gi.cpp b/scene/3d/lightmap_gi.cpp index 9d1d8721e6..a8eec4b1f3 100644 --- a/scene/3d/lightmap_gi.cpp +++ b/scene/3d/lightmap_gi.cpp @@ -665,7 +665,7 @@ void LightmapGI::_plot_triangle_into_octree(GenProbesOctree *p_cell, float p_cel } } -void LightmapGI::_gen_new_positions_from_octree(const GenProbesOctree *p_cell, float p_cell_size, const Vector &probe_positions, LocalVector &new_probe_positions, HashMap &positions_used, const AABB &p_bounds) { +void LightmapGI::_gen_new_positions_from_octree(const GenProbesOctree *p_cell, float p_cell_size, const Vector &probe_positions, LocalVector &new_probe_positions, HashMap &positions_used, const AABB &p_bounds) { for (int i = 0; i < 8; i++) { Vector3i pos = p_cell->offset; if (i & 1) { @@ -934,7 +934,7 @@ LightmapGI::BakeError LightmapGI::bake(Node *p_from_node, String p_image_data_pa } LocalVector new_probe_positions; - HashMap positions_used; + HashMap positions_used; for (uint32_t i = 0; i < 8; i++) { //insert bounding endpoints Vector3i pos; if (i & 1) { diff --git a/scene/3d/lightmap_gi.h b/scene/3d/lightmap_gi.h index b39cde429d..f7a23c776a 100644 --- a/scene/3d/lightmap_gi.h +++ b/scene/3d/lightmap_gi.h @@ -212,16 +212,8 @@ private: } }; - struct Vector3iHash { - _FORCE_INLINE_ static uint32_t hash(const Vector3i &p_vtx) { - uint32_t h = hash_djb2_one_32(p_vtx.x); - h = hash_djb2_one_32(p_vtx.y, h); - return hash_djb2_one_32(p_vtx.z, h); - } - }; - void _plot_triangle_into_octree(GenProbesOctree *p_cell, float p_cell_size, const Vector3 *p_triangle); - void _gen_new_positions_from_octree(const GenProbesOctree *p_cell, float p_cell_size, const Vector &probe_positions, LocalVector &new_probe_positions, HashMap &positions_used, const AABB &p_bounds); + void _gen_new_positions_from_octree(const GenProbesOctree *p_cell, float p_cell_size, const Vector &probe_positions, LocalVector &new_probe_positions, HashMap &positions_used, const AABB &p_bounds); protected: void _validate_property(PropertyInfo &property) const override; diff --git a/scene/animation/animation_player.h b/scene/animation/animation_player.h index 7e4bda14e5..d3eb37a345 100644 --- a/scene/animation/animation_player.h +++ b/scene/animation/animation_player.h @@ -155,8 +155,8 @@ private: static uint32_t hash(const TrackNodeCacheKey &p_key) { uint32_t h = hash_one_uint64(p_key.id); - h = hash_djb2_one_32(p_key.bone_idx, h); - return hash_djb2_one_32(p_key.blend_shape_idx, h); + h = hash_murmur3_one_32(p_key.bone_idx, h); + return hash_fmix32(hash_murmur3_one_32(p_key.blend_shape_idx, h)); } inline bool operator==(const TrackNodeCacheKey &p_right) const { diff --git a/scene/resources/canvas_item_material.h b/scene/resources/canvas_item_material.h index 7c44c125a8..160c67d6b1 100644 --- a/scene/resources/canvas_item_material.h +++ b/scene/resources/canvas_item_material.h @@ -64,7 +64,7 @@ private: uint32_t key = 0; static uint32_t hash(const MaterialKey &p_key) { - return hash_djb2_one_32(p_key.key); + return hash_murmur3_one_32(p_key.key); } bool operator==(const MaterialKey &p_key) const { return key == p_key.key; diff --git a/scene/resources/concave_polygon_shape_3d.h b/scene/resources/concave_polygon_shape_3d.h index 4711e38468..a265590edd 100644 --- a/scene/resources/concave_polygon_shape_3d.h +++ b/scene/resources/concave_polygon_shape_3d.h @@ -43,8 +43,8 @@ class ConcavePolygonShape3D : public Shape3D { Vector3 a; Vector3 b; static uint32_t hash(const DrawEdge &p_edge) { - uint32_t h = hash_djb2_one_32(HashMapHasherDefault::hash(p_edge.a)); - return hash_djb2_one_32(HashMapHasherDefault::hash(p_edge.b), h); + uint32_t h = hash_murmur3_one_32(HashMapHasherDefault::hash(p_edge.a)); + return hash_murmur3_one_32(HashMapHasherDefault::hash(p_edge.b), h); } bool operator==(const DrawEdge &p_edge) const { return (a == p_edge.a && b == p_edge.b); diff --git a/scene/resources/font.cpp b/scene/resources/font.cpp index 8a353f4b49..46f23424dd 100644 --- a/scene/resources/font.cpp +++ b/scene/resources/font.cpp @@ -2273,7 +2273,7 @@ Size2 Font::get_string_size(const String &p_text, int p_size, HorizontalAlignmen uint64_t hash = p_text.hash64(); if (p_alignment == HORIZONTAL_ALIGNMENT_FILL) { - hash = hash_djb2_one_64(hash_djb2_one_float(p_width), hash); + hash = hash_djb2_one_64(hash_murmur3_one_float(p_width), hash); hash = hash_djb2_one_64(p_flags, hash); } hash = hash_djb2_one_64(p_size, hash); @@ -2297,7 +2297,7 @@ Size2 Font::get_multiline_string_size(const String &p_text, float p_width, int p } uint64_t hash = p_text.hash64(); - uint64_t wrp_hash = hash_djb2_one_64(hash_djb2_one_float(p_width), hash); + uint64_t wrp_hash = hash_djb2_one_64(hash_murmur3_one_float(p_width), hash); wrp_hash = hash_djb2_one_64(p_flags, wrp_hash); wrp_hash = hash_djb2_one_64(p_size, wrp_hash); @@ -2335,7 +2335,7 @@ void Font::draw_string(RID p_canvas_item, const Point2 &p_pos, const String &p_t uint64_t hash = p_text.hash64(); if (p_alignment == HORIZONTAL_ALIGNMENT_FILL) { - hash = hash_djb2_one_64(hash_djb2_one_float(p_width), hash); + hash = hash_djb2_one_64(hash_murmur3_one_float(p_width), hash); hash = hash_djb2_one_64(p_flags, hash); } hash = hash_djb2_one_64(p_size, hash); @@ -2374,7 +2374,7 @@ void Font::draw_multiline_string(RID p_canvas_item, const Point2 &p_pos, const S } uint64_t hash = p_text.hash64(); - uint64_t wrp_hash = hash_djb2_one_64(hash_djb2_one_float(p_width), hash); + uint64_t wrp_hash = hash_djb2_one_64(hash_murmur3_one_float(p_width), hash); wrp_hash = hash_djb2_one_64(p_flags, wrp_hash); wrp_hash = hash_djb2_one_64(p_size, wrp_hash); diff --git a/scene/resources/material.cpp b/scene/resources/material.cpp index fc207d358e..b7a3b677f5 100644 --- a/scene/resources/material.cpp +++ b/scene/resources/material.cpp @@ -2209,7 +2209,7 @@ Ref BaseMaterial3D::get_material_for_2d(bool p_shaded, bool p_transpar if (p_fixed_size) { hash |= 1 << 9; } - hash = hash_djb2_one_64(p_filter, hash); + hash = hash_murmur3_one_64(p_filter, hash); if (materials_for_2d.has(hash)) { if (r_shader_rid) { diff --git a/scene/resources/particles_material.h b/scene/resources/particles_material.h index 24341d964d..af45593f38 100644 --- a/scene/resources/particles_material.h +++ b/scene/resources/particles_material.h @@ -110,7 +110,7 @@ private: uint32_t key = 0; static uint32_t hash(const MaterialKey &p_key) { - return hash_djb2_one_32(p_key.key); + return hash_murmur3_one_32(p_key.key); } bool operator==(const MaterialKey &p_key) const { diff --git a/scene/resources/primitive_meshes.cpp b/scene/resources/primitive_meshes.cpp index f8fb51ae42..b2fd8eb895 100644 --- a/scene/resources/primitive_meshes.cpp +++ b/scene/resources/primitive_meshes.cpp @@ -2435,7 +2435,7 @@ void TextMesh::_create_mesh_array(Array &p_arr) const { } if (glyphs[i].font_rid != RID()) { uint32_t hash = hash_one_uint64(glyphs[i].font_rid.get_id()); - hash = hash_djb2_one_32(glyphs[i].index, hash); + hash = hash_murmur3_one_32(glyphs[i].index, hash); _generate_glyph_mesh_data(hash, glyphs[i]); GlyphMeshData &gl_data = cache[hash]; @@ -2494,7 +2494,7 @@ void TextMesh::_create_mesh_array(Array &p_arr) const { } if (glyphs[i].font_rid != RID()) { uint32_t hash = hash_one_uint64(glyphs[i].font_rid.get_id()); - hash = hash_djb2_one_32(glyphs[i].index, hash); + hash = hash_murmur3_one_32(glyphs[i].index, hash); const GlyphMeshData &gl_data = cache[hash]; diff --git a/scene/resources/surface_tool.cpp b/scene/resources/surface_tool.cpp index 77d6e3c6f9..9829c7e86b 100644 --- a/scene/resources/surface_tool.cpp +++ b/scene/resources/surface_tool.cpp @@ -141,7 +141,8 @@ uint32_t SurfaceTool::VertexHasher::hash(const Vertex &p_vtx) { h = hash_djb2_buffer((const uint8_t *)p_vtx.bones.ptr(), p_vtx.bones.size() * sizeof(int), h); h = hash_djb2_buffer((const uint8_t *)p_vtx.weights.ptr(), p_vtx.weights.size() * sizeof(float), h); h = hash_djb2_buffer((const uint8_t *)&p_vtx.custom[0], sizeof(Color) * RS::ARRAY_CUSTOM_COUNT, h); - h = hash_djb2_one_32(p_vtx.smooth_group, h); + h = hash_murmur3_one_32(p_vtx.smooth_group, h); + h = hash_fmix32(h); return h; } diff --git a/servers/physics_2d/godot_area_2d.h b/servers/physics_2d/godot_area_2d.h index 35dad9d2c3..221982cf78 100644 --- a/servers/physics_2d/godot_area_2d.h +++ b/servers/physics_2d/godot_area_2d.h @@ -70,9 +70,9 @@ class GodotArea2D : public GodotCollisionObject2D { static uint32_t hash(const BodyKey &p_key) { uint32_t h = hash_one_uint64(p_key.rid.get_id()); - h = hash_djb2_one_64(p_key.instance_id, h); - h = hash_djb2_one_32(p_key.area_shape, h); - return hash_djb2_one_32(p_key.body_shape, h); + h = hash_murmur3_one_64(p_key.instance_id, h); + h = hash_murmur3_one_32(p_key.area_shape, h); + return hash_fmix32(hash_murmur3_one_32(p_key.body_shape, h)); } _FORCE_INLINE_ bool operator==(const BodyKey &p_key) const { diff --git a/servers/physics_3d/godot_area_3d.h b/servers/physics_3d/godot_area_3d.h index a00451f602..51b435eb00 100644 --- a/servers/physics_3d/godot_area_3d.h +++ b/servers/physics_3d/godot_area_3d.h @@ -74,9 +74,9 @@ class GodotArea3D : public GodotCollisionObject3D { static uint32_t hash(const BodyKey &p_key) { uint32_t h = hash_one_uint64(p_key.rid.get_id()); - h = hash_djb2_one_64(p_key.instance_id, h); - h = hash_djb2_one_32(p_key.area_shape, h); - return hash_djb2_one_32(p_key.body_shape, h); + h = hash_murmur3_one_64(p_key.instance_id, h); + h = hash_murmur3_one_32(p_key.area_shape, h); + return hash_fmix32(hash_murmur3_one_32(p_key.body_shape, h)); } _FORCE_INLINE_ bool operator==(const BodyKey &p_key) const { diff --git a/servers/rendering/renderer_rd/uniform_set_cache_rd.h b/servers/rendering/renderer_rd/uniform_set_cache_rd.h index e49cf4dafa..af22a48716 100644 --- a/servers/rendering/renderer_rd/uniform_set_cache_rd.h +++ b/servers/rendering/renderer_rd/uniform_set_cache_rd.h @@ -57,13 +57,13 @@ class UniformSetCacheRD : public Object { Cache *hash_table[HASH_TABLE_SIZE] = {}; static _FORCE_INLINE_ uint32_t _hash_uniform(const RD::Uniform &u, uint32_t h) { - h = hash_djb2_one_32(u.uniform_type, h); - h = hash_djb2_one_32(u.binding, h); + h = hash_murmur3_one_32(u.uniform_type, h); + h = hash_murmur3_one_32(u.binding, h); uint32_t rsize = u.get_id_count(); for (uint32_t j = 0; j < rsize; j++) { - h = hash_djb2_one_64(u.get_id(j).get_id(), h); + h = hash_murmur3_one_64(u.get_id(j).get_id(), h); } - return h; + return hash_fmix32(h); } static _FORCE_INLINE_ bool _compare_uniform(const RD::Uniform &a, const RD::Uniform &b) { @@ -154,8 +154,8 @@ class UniformSetCacheRD : public Object { public: template RID get_cache(RID p_shader, uint32_t p_set, Args... args) { - uint32_t h = hash_djb2_one_64(p_shader.get_id()); - h = hash_djb2_one_32(p_set, h); + uint32_t h = hash_murmur3_one_64(p_shader.get_id()); + h = hash_murmur3_one_32(p_set, h); h = _hash_args(h, args...); uint32_t table_idx = h % HASH_TABLE_SIZE; @@ -180,12 +180,14 @@ public: template RID get_cache_vec(RID p_shader, uint32_t p_set, const Vector &p_uniforms) { - uint32_t h = hash_djb2_one_64(p_shader.get_id()); - h = hash_djb2_one_32(p_set, h); + uint32_t h = hash_murmur3_one_64(p_shader.get_id()); + h = hash_murmur3_one_32(p_set, h); for (int i = 0; i < p_uniforms.size(); i++) { h = _hash_uniform(p_uniforms[i], h); } + h = hash_fmix32(h); + uint32_t table_idx = h % HASH_TABLE_SIZE; { const Cache *c = hash_table[table_idx]; -- cgit v1.2.3