aboutsummaryrefslogtreecommitdiffstats
path: root/util/digest
diff options
context:
space:
mode:
authorMikhail Borisov <borisov.mikhail@gmail.com>2022-02-10 16:45:39 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:45:39 +0300
commita6a92afe03e02795227d2641b49819b687f088f8 (patch)
treef6984a1d27d5a7ec88a6fdd6e20cd5b7693b6ece /util/digest
parentc6dc8b8bd530985bc4cce0137e9a5de32f1087cb (diff)
downloadydb-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.pyx4
-rw-r--r--util/digest/murmur.cpp228
-rw-r--r--util/digest/murmur.h42
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>