diff options
author | Mikhail Borisov <borisov.mikhail@gmail.com> | 2022-02-10 16:45:39 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:39 +0300 |
commit | a6a92afe03e02795227d2641b49819b687f088f8 (patch) | |
tree | f6984a1d27d5a7ec88a6fdd6e20cd5b7693b6ece /util/digest | |
parent | c6dc8b8bd530985bc4cce0137e9a5de32f1087cb (diff) | |
download | ydb-a6a92afe03e02795227d2641b49819b687f088f8.tar.gz |
Restoring authorship annotation for Mikhail Borisov <borisov.mikhail@gmail.com>. Commit 1 of 2.
Diffstat (limited to 'util/digest')
-rw-r--r-- | util/digest/multi_ut.pyx | 4 | ||||
-rw-r--r-- | util/digest/murmur.cpp | 228 | ||||
-rw-r--r-- | util/digest/murmur.h | 42 |
3 files changed, 137 insertions, 137 deletions
diff --git a/util/digest/multi_ut.pyx b/util/digest/multi_ut.pyx index 26faa0069b..6b032f5f86 100644 --- a/util/digest/multi_ut.pyx +++ b/util/digest/multi_ut.pyx @@ -8,11 +8,11 @@ import unittest class TestMultiHash(unittest.TestCase): def test_str_int(self): - value = MultiHash(TString(b"1234567"), 123) + value = MultiHash(TString(b"1234567"), 123) self.assertEquals(value, 17038203285960021630) def test_int_str(self): - value = MultiHash(123, TString(b"1234567")) + value = MultiHash(123, TString(b"1234567")) self.assertEquals(value, 9973288649881090712) def test_collision(self): diff --git a/util/digest/murmur.cpp b/util/digest/murmur.cpp index b041d3e5f2..84df22304d 100644 --- a/util/digest/murmur.cpp +++ b/util/digest/murmur.cpp @@ -2,130 +2,130 @@ #include <util/system/unaligned_mem.h> -namespace NMurmurPrivate { - //----------------------------------------------------------------------------- - // MurmurHash2, by Austin Appleby - - // Note - This code makes a few assumptions about how your machine behaves - - - // 1. We can read a 4-byte value from any address without crashing - // 2. sizeof(int) == 4 - - // And it has a few limitations - - - // 1. It will not work incrementally. - // 2. It will not produce the same results on little-endian and big-endian - // machines. - - Y_NO_INLINE ui32 MurmurHash32(const void* key, size_t len, ui32 seed) noexcept { - const ui32 m = 0x5bd1e995; - const int r = 24; - ui32 h = ui32(seed ^ len); - - TUnalignedMemoryIterator<ui32> iter(key, len); - - while (!iter.AtEnd()) { - ui32 k = iter.Next(); - - k *= m; - k ^= k >> r; - k *= m; - - h *= m; - h ^= k; - } - - const unsigned char* data = iter.Last(); - - switch (iter.Left()) { - case 3: - h ^= data[2] << 16; +namespace NMurmurPrivate { + //----------------------------------------------------------------------------- + // MurmurHash2, by Austin Appleby + + // Note - This code makes a few assumptions about how your machine behaves - + + // 1. We can read a 4-byte value from any address without crashing + // 2. sizeof(int) == 4 + + // And it has a few limitations - + + // 1. It will not work incrementally. + // 2. It will not produce the same results on little-endian and big-endian + // machines. + + Y_NO_INLINE ui32 MurmurHash32(const void* key, size_t len, ui32 seed) noexcept { + const ui32 m = 0x5bd1e995; + const int r = 24; + ui32 h = ui32(seed ^ len); + + TUnalignedMemoryIterator<ui32> iter(key, len); + + while (!iter.AtEnd()) { + ui32 k = iter.Next(); + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + } + + const unsigned char* data = iter.Last(); + + switch (iter.Left()) { + case 3: + h ^= data[2] << 16; [[fallthrough]]; - - case 2: - h ^= data[1] << 8; + + case 2: + h ^= data[1] << 8; [[fallthrough]]; - - case 1: - h ^= data[0]; - h *= m; + + case 1: + h ^= data[0]; + h *= m; break; - }; - - h ^= h >> 13; - h *= m; - h ^= h >> 15; - - return h; - } - - //----------------------------------------------------------------------------- - // MurmurHash2, 64-bit versions, by Austin Appleby - - // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment - // and endian-ness issues if used across multiple platforms. - - // 64-bit hash for 64-bit platforms - - Y_NO_INLINE ui64 MurmurHash64(const void* key, size_t len, ui64 seed) noexcept { - const ui64 m = ULL(0xc6a4a7935bd1e995); - const int r = 47; - - ui64 h = seed ^ (len * m); - TUnalignedMemoryIterator<ui64> iter(key, len); - - while (!iter.AtEnd()) { - ui64 k = iter.Next(); - - k *= m; - k ^= k >> r; - k *= m; - - h ^= k; - h *= m; - } - - const unsigned char* data2 = iter.Last(); - - switch (iter.Left()) { - case 7: - h ^= ui64(data2[6]) << 48; + }; + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; + } + + //----------------------------------------------------------------------------- + // MurmurHash2, 64-bit versions, by Austin Appleby + + // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment + // and endian-ness issues if used across multiple platforms. + + // 64-bit hash for 64-bit platforms + + Y_NO_INLINE ui64 MurmurHash64(const void* key, size_t len, ui64 seed) noexcept { + const ui64 m = ULL(0xc6a4a7935bd1e995); + const int r = 47; + + ui64 h = seed ^ (len * m); + TUnalignedMemoryIterator<ui64> iter(key, len); + + while (!iter.AtEnd()) { + ui64 k = iter.Next(); + + k *= m; + k ^= k >> r; + k *= m; + + h ^= k; + h *= m; + } + + const unsigned char* data2 = iter.Last(); + + switch (iter.Left()) { + case 7: + h ^= ui64(data2[6]) << 48; [[fallthrough]]; - - case 6: - h ^= ui64(data2[5]) << 40; + + case 6: + h ^= ui64(data2[5]) << 40; [[fallthrough]]; - - case 5: - h ^= ui64(data2[4]) << 32; + + case 5: + h ^= ui64(data2[4]) << 32; [[fallthrough]]; - - case 4: - h ^= ui64(data2[3]) << 24; + + case 4: + h ^= ui64(data2[3]) << 24; [[fallthrough]]; - - case 3: - h ^= ui64(data2[2]) << 16; + + case 3: + h ^= ui64(data2[2]) << 16; [[fallthrough]]; - - case 2: - h ^= ui64(data2[1]) << 8; + + case 2: + h ^= ui64(data2[1]) << 8; [[fallthrough]]; - - case 1: - h ^= ui64(data2[0]); - h *= m; + + case 1: + h ^= ui64(data2[0]); + h *= m; break; - } - - h ^= h >> r; - h *= m; - h ^= h >> r; - - return h; - } -} - + } + + h ^= h >> r; + h *= m; + h ^= h >> r; + + return h; + } +} + size_t MurmurHashSizeT(const char* buf, size_t len) noexcept { return MurmurHash<size_t>(buf, len); } diff --git a/util/digest/murmur.h b/util/digest/murmur.h index 6b519b430a..eec9bcc171 100644 --- a/util/digest/murmur.h +++ b/util/digest/murmur.h @@ -3,35 +3,35 @@ #include <util/system/defaults.h> #include <util/generic/array_ref.h> -/* - * murmur2 from http://murmurhash.googlepages.com/ - * +/* + * murmur2 from http://murmurhash.googlepages.com/ + * */ -namespace NMurmurPrivate { +namespace NMurmurPrivate { Y_PURE_FUNCTION ui32 MurmurHash32(const void* key, size_t len, ui32 seed) noexcept; Y_PURE_FUNCTION ui64 MurmurHash64(const void* key, size_t len, ui64 seed) noexcept; - template <unsigned N> - struct TMurHelper; - -#define DEF_MUR(t) \ - template <> \ - struct TMurHelper<t> { \ - static inline ui##t MurmurHash(const void* buf, size_t len, ui##t init) noexcept { \ - return MurmurHash##t(buf, len, init); \ - } \ - }; - - DEF_MUR(32) - DEF_MUR(64) - -#undef DEF_MUR + template <unsigned N> + struct TMurHelper; + +#define DEF_MUR(t) \ + template <> \ + struct TMurHelper<t> { \ + static inline ui##t MurmurHash(const void* buf, size_t len, ui##t init) noexcept { \ + return MurmurHash##t(buf, len, init); \ + } \ + }; + + DEF_MUR(32) + DEF_MUR(64) + +#undef DEF_MUR } template <class T> -static inline T MurmurHash(const void* buf, size_t len, T init) noexcept { - return (T)NMurmurPrivate::TMurHelper<8 * sizeof(T)>::MurmurHash(buf, len, init); +static inline T MurmurHash(const void* buf, size_t len, T init) noexcept { + return (T)NMurmurPrivate::TMurHelper<8 * sizeof(T)>::MurmurHash(buf, len, init); } template <class T> |