From 64c0c13e6e08c51e92504631468db864f553d9b5 Mon Sep 17 00:00:00 2001 From: Bastien Montagne Date: Fri, 14 Nov 2014 11:00:10 +0100 Subject: 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 --- tests/gtests/blenlib/BLI_hash_mm2a_test.cc | 75 ++++++++++++++++++++++++++++++ tests/gtests/blenlib/CMakeLists.txt | 1 + 2 files changed, 76 insertions(+) create mode 100644 tests/gtests/blenlib/BLI_hash_mm2a_test.cc (limited to 'tests') 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)); +} diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index c949c1e1f5c..3a86d3f770d 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -42,3 +42,4 @@ BLENDER_TEST(BLI_string "bf_blenlib") BLENDER_TEST(BLI_path_util "bf_blenlib;extern_wcwidth;${ZLIB_LIBRARIES}") BLENDER_TEST(BLI_polyfill2d "bf_blenlib") BLENDER_TEST(BLI_listbase "bf_blenlib") +BLENDER_TEST(BLI_hash_mm2a "bf_blenlib") -- cgit v1.2.3