Add Murmur2A hashing feature to BLI

Murmur2a is a very fast hashing function generation int32 hashes.
It also features a very good distribution of generated hashes.

However, it is not endianness-agnostic, meaning it will usually generate
different hashes for a same key on big- and little-endian architectures.
Consequently, **it shall not be used to generate persistent hashes**
(never store them in .blend file e.g.).

This implementation supports incremental hashing, and is a direct
adaptation of reference implementation (in c++):
https://smhasher.googlecode.com/svn-history/r130/trunk/MurmurHash2.cpp

That cpp code was also used to generate reference values in gtests file.

Reviewers: sergey, campbellbarton

Reviewed By: campbellbarton

Projects: #bf_blender

Differential Revision: https://developer.blender.org/D892

1 files changed, 75 insertions, 0 deletions

diff --git a/tests/gtests/blenlib/BLI_hash_mm2a_test.cc b/tests/gtests/blenlib/BLI_hash_mm2a_test.cc
new file mode 100644
index 00000000000..b35a1a809d6
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_hash_mm2a_test.cc
@@ -0,0 +1,75 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+extern "C" {
+#include "BLI_hash_mm2a.h"
+}
+
+/* Note: Reference results are taken from reference implementation (cpp code, CMurmurHash2A variant):
+ *       https://smhasher.googlecode.com/svn-history/r130/trunk/MurmurHash2.cpp
+ */
+
+TEST(hash_mm2a, MM2ABasic)
+{
+	BLI_HashMurmur2A mm2;
+
+	const char *data = "Blender";
+
+	BLI_hash_mm2a_init(&mm2, 0);
+	BLI_hash_mm2a_add(&mm2, (const unsigned char *)data, strlen(data));
+#ifdef __LITTLE_ENDIAN__
+	EXPECT_EQ(1633988145, BLI_hash_mm2a_end(&mm2));
+#else
+	EXPECT_EQ(959283772, BLI_hash_mm2a_end(&mm2));
+#endif
+}
+
+TEST(hash_mm2a, MM2AConcatenateStrings)
+{
+	BLI_HashMurmur2A mm2;
+	uint32_t hash;
+
+	const char *data1 = "Blender";
+	const char *data2 = " is ";
+	const char *data3 = "FaNtAsTiC";
+	const char *data123 = "Blender is FaNtAsTiC";
+
+	BLI_hash_mm2a_init(&mm2, 0);
+	BLI_hash_mm2a_add(&mm2, (const unsigned char *)data1, strlen(data1));
+	BLI_hash_mm2a_add(&mm2, (const unsigned char *)data2, strlen(data2));
+	BLI_hash_mm2a_add(&mm2, (const unsigned char *)data3, strlen(data3));
+	hash = BLI_hash_mm2a_end(&mm2);
+	BLI_hash_mm2a_init(&mm2, 0);
+	BLI_hash_mm2a_add(&mm2, (const unsigned char *)data123, strlen(data123));
+#ifdef __LITTLE_ENDIAN__
+	EXPECT_EQ(1545105348, hash);
+#else
+	EXPECT_EQ(2604964730, hash);
+#endif
+	EXPECT_EQ(hash, BLI_hash_mm2a_end(&mm2));
+}
+
+TEST(hash_mm2a, MM2AIntegers)
+{
+	BLI_HashMurmur2A mm2;
+	uint32_t hash;
+
+	const int ints[4] = {1, 2, 3, 4};
+
+	BLI_hash_mm2a_init(&mm2, 0);
+	BLI_hash_mm2a_add_int(&mm2, ints[0]);
+	BLI_hash_mm2a_add_int(&mm2, ints[1]);
+	BLI_hash_mm2a_add_int(&mm2, ints[2]);
+	BLI_hash_mm2a_add_int(&mm2, ints[3]);
+	hash = BLI_hash_mm2a_end(&mm2);
+	BLI_hash_mm2a_init(&mm2, 0);
+	BLI_hash_mm2a_add(&mm2, (const unsigned char *)ints, sizeof(ints));
+	/* Yes, same hash here on little and big endian. */
+#ifdef __LITTLE_ENDIAN__
+	EXPECT_EQ(405493096, hash);
+#else
+	EXPECT_EQ(405493096, hash);
+#endif
+	EXPECT_EQ(hash, BLI_hash_mm2a_end(&mm2));
+}