intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

24 files changed, 1112 insertions, 0 deletions

diff --git a/util/digest/benchmark/murmur/main.cpp b/util/digest/benchmark/murmur/main.cpp
new file mode 100644
index 0000000000..1fe2fdcc21
--- /dev/null
+++ b/util/digest/benchmark/murmur/main.cpp
@@ -0,0 +1,27 @@
+#include <contrib/libs/benchmark/include/benchmark/benchmark.h>
+
+#include <util/digest/murmur.h>
+#include <util/system/types.h>
+
+#include <array>
+
+constexpr auto MakeTestData() {
+    std::array<ui64, 4096> result;
+    for (ui64 i = 0; i < result.size(); ++i) {
+        result[i] = i;
+    }
+    return result;
+}
+
+constexpr auto TEST_DATA = MakeTestData();
+
+template <typename Result>
+static void BenchmarkMurmurHash(benchmark::State& state) {
+    for (auto _ : state) {
+        Result hash = MurmurHash<Result>(TEST_DATA.data(), sizeof(TEST_DATA));
+        Y_DO_NOT_OPTIMIZE_AWAY(hash);
+    }
+}
+
+BENCHMARK_TEMPLATE(BenchmarkMurmurHash, ui32);
+BENCHMARK_TEMPLATE(BenchmarkMurmurHash, ui64);
diff --git a/util/digest/benchmark/murmur/ya.make b/util/digest/benchmark/murmur/ya.make
new file mode 100644
index 0000000000..39559996ab
--- /dev/null
+++ b/util/digest/benchmark/murmur/ya.make
@@ -0,0 +1,7 @@
+G_BENCHMARK()
+
+SRCS(
+    main.cpp
+)
+
+END()
diff --git a/util/digest/benchmark/ya.make b/util/digest/benchmark/ya.make
new file mode 100644
index 0000000000..bfc0faff9e
--- /dev/null
+++ b/util/digest/benchmark/ya.make
@@ -0,0 +1,3 @@
+RECURSE(
+    murmur
+)
diff --git a/util/digest/city.cpp b/util/digest/city.cpp
new file mode 100644
index 0000000000..c25f175d54
--- /dev/null
+++ b/util/digest/city.cpp
@@ -0,0 +1,323 @@
+#ifndef NO_CITYHASH
+
+// Copyright (c) 2011 Google, Inc.
+
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+
+// CityHash Version 1, by Geoff Pike and Jyrki Alakuijala
+
+// This file provides CityHash64() and related functions.
+
+// It's probably possible to create even faster hash functions by
+// writing a program that systematically explores some of the space of
+// possible hash functions, by using SIMD instructions, or by
+// compromising on hash quality.
+
+    #include "city.h"
+
+using uint8 = ui8;
+using uint32 = ui32;
+using uint64 = ui64;
+
+    #include <util/system/unaligned_mem.h>
+    #include <util/generic/algorithm.h>
+
+using namespace std;
+
+//#define UNALIGNED_LOAD64(p) (*(const uint64*)(p))
+//#define UNALIGNED_LOAD32(p) (*(const uint32*)(p))
+
+    #define UNALIGNED_LOAD64(p) (ReadUnaligned<uint64>((const void*)(p)))
+    #define UNALIGNED_LOAD32(p) (ReadUnaligned<uint32>((const void*)(p)))
+
+    #define LIKELY(x) Y_LIKELY(!!(x))
+
+// Some primes between 2^63 and 2^64 for various uses.
+static const uint64 k0 = 0xc3a5c85c97cb3127ULL;
+static const uint64 k1 = 0xb492b66fbe98f273ULL;
+static const uint64 k2 = 0x9ae16a3b2f90404fULL;
+static const uint64 k3 = 0xc949d7c7509e6557ULL;
+
+// Bitwise right rotate.  Normally this will compile to a single
+// instruction, especially if the shift is a manifest constant.
+static uint64 Rotate(uint64 val, int shift) {
+    // Avoid shifting by 64: doing so yields an undefined result.
+    return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
+}
+
+// Equivalent to Rotate(), but requires the second arg to be non-zero.
+// On x86-64, and probably others, it's possible for this to compile
+// to a single instruction if both args are already in registers.
+static uint64 RotateByAtLeast1(uint64 val, int shift) {
+    return (val >> shift) | (val << (64 - shift));
+}
+
+static uint64 ShiftMix(uint64 val) {
+    return val ^ (val >> 47);
+}
+
+static uint64 HashLen16(uint64 u, uint64 v) {
+    return Hash128to64(uint128(u, v));
+}
+
+static uint64 HashLen0to16(const char* s, size_t len) {
+    if (len > 8) {
+        uint64 a = UNALIGNED_LOAD64(s);
+        uint64 b = UNALIGNED_LOAD64(s + len - 8);
+        return HashLen16(a, RotateByAtLeast1(b + len, static_cast<int>(len))) ^ b;
+    }
+    if (len >= 4) {
+        uint64 a = UNALIGNED_LOAD32(s);
+        return HashLen16(len + (a << 3), UNALIGNED_LOAD32(s + len - 4));
+    }
+    if (len > 0) {
+        uint8 a = s[0];
+        uint8 b = s[len >> 1];
+        uint8 c = s[len - 1];
+        uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);
+        uint32 z = static_cast<uint32>(len) + (static_cast<uint32>(c) << 2);
+        return ShiftMix(y * k2 ^ z * k3) * k2;
+    }
+    return k2;
+}
+
+// This probably works well for 16-byte strings as well, but it may be overkill
+// in that case.
+static uint64 HashLen17to32(const char* s, size_t len) {
+    uint64 a = UNALIGNED_LOAD64(s) * k1;
+    uint64 b = UNALIGNED_LOAD64(s + 8);
+    uint64 c = UNALIGNED_LOAD64(s + len - 8) * k2;
+    uint64 d = UNALIGNED_LOAD64(s + len - 16) * k0;
+    return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d,
+                     a + Rotate(b ^ k3, 20) - c + len);
+}
+
+// Return a 16-byte hash for 48 bytes.  Quick and dirty.
+// Callers do best to use "random-looking" values for a and b.
+static pair<uint64, uint64> WeakHashLen32WithSeeds(
+    uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) {
+    a += w;
+    b = Rotate(b + a + z, 21);
+    uint64 c = a;
+    a += x;
+    a += y;
+    b += Rotate(a, 44);
+    return make_pair(a + z, b + c);
+}
+
+// Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
+static pair<uint64, uint64> WeakHashLen32WithSeeds(
+    const char* s, uint64 a, uint64 b) {
+    return WeakHashLen32WithSeeds(UNALIGNED_LOAD64(s),
+                                  UNALIGNED_LOAD64(s + 8),
+                                  UNALIGNED_LOAD64(s + 16),
+                                  UNALIGNED_LOAD64(s + 24),
+                                  a,
+                                  b);
+}
+
+// Return an 8-byte hash for 33 to 64 bytes.
+static uint64 HashLen33to64(const char* s, size_t len) {
+    uint64 z = UNALIGNED_LOAD64(s + 24);
+    uint64 a = UNALIGNED_LOAD64(s) + (len + UNALIGNED_LOAD64(s + len - 16)) * k0;
+    uint64 b = Rotate(a + z, 52);
+    uint64 c = Rotate(a, 37);
+    a += UNALIGNED_LOAD64(s + 8);
+    c += Rotate(a, 7);
+    a += UNALIGNED_LOAD64(s + 16);
+    uint64 vf = a + z;
+    uint64 vs = b + Rotate(a, 31) + c;
+    a = UNALIGNED_LOAD64(s + 16) + UNALIGNED_LOAD64(s + len - 32);
+    z = UNALIGNED_LOAD64(s + len - 8);
+    b = Rotate(a + z, 52);
+    c = Rotate(a, 37);
+    a += UNALIGNED_LOAD64(s + len - 24);
+    c += Rotate(a, 7);
+    a += UNALIGNED_LOAD64(s + len - 16);
+    uint64 wf = a + z;
+    uint64 ws = b + Rotate(a, 31) + c;
+    uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0);
+    return ShiftMix(r * k0 + vs) * k2;
+}
+
+uint64 CityHash64(const char* s, size_t len) noexcept {
+    if (len <= 32) {
+        if (len <= 16) {
+            return HashLen0to16(s, len);
+        } else {
+            return HashLen17to32(s, len);
+        }
+    } else if (len <= 64) {
+        return HashLen33to64(s, len);
+    }
+
+    // For strings over 64 bytes we hash the end first, and then as we
+    // loop we keep 56 bytes of state: v, w, x, y, and z.
+    uint64 x = UNALIGNED_LOAD64(s);
+    uint64 y = UNALIGNED_LOAD64(s + len - 16) ^ k1;
+    uint64 z = UNALIGNED_LOAD64(s + len - 56) ^ k0;
+    pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, y);
+    pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, len * k1, k0);
+    z += ShiftMix(v.second) * k1;
+    x = Rotate(z + x, 39) * k1;
+    y = Rotate(y, 33) * k1;
+
+    // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
+    len = (len - 1) & ~static_cast<size_t>(63);
+    do {
+        x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;
+        y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;
+        x ^= w.second;
+        y ^= v.first;
+        z = Rotate(z ^ w.first, 33);
+        v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+        w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
+        DoSwap(z, x);
+        s += 64;
+        len -= 64;
+    } while (len != 0);
+    return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
+                     HashLen16(v.second, w.second) + x);
+}
+
+uint64 CityHash64WithSeed(const char* s, size_t len, uint64 seed) noexcept {
+    return CityHash64WithSeeds(s, len, k2, seed);
+}
+
+uint64 CityHash64WithSeeds(const char* s, size_t len,
+                           uint64 seed0, uint64 seed1) noexcept {
+    return HashLen16(CityHash64(s, len) - seed0, seed1);
+}
+
+// A subroutine for CityHash128().  Returns a decent 128-bit hash for strings
+// of any length representable in ssize_t.  Based on City and Murmur.
+static uint128 CityMurmur(const char* s, size_t len, uint128 seed) {
+    uint64 a = Uint128Low64(seed);
+    uint64 b = Uint128High64(seed);
+    uint64 c = 0;
+    uint64 d = 0;
+    ssize_t l = len - 16;
+    if (l <= 0) { // len <= 16
+        c = b * k1 + HashLen0to16(s, len);
+        d = Rotate(a + (len >= 8 ? UNALIGNED_LOAD64(s) : c), 32);
+    } else { // len > 16
+        c = HashLen16(UNALIGNED_LOAD64(s + len - 8) + k1, a);
+        d = HashLen16(b + len, c + UNALIGNED_LOAD64(s + len - 16));
+        a += d;
+        do {
+            a ^= ShiftMix(UNALIGNED_LOAD64(s) * k1) * k1;
+            a *= k1;
+            b ^= a;
+            c ^= ShiftMix(UNALIGNED_LOAD64(s + 8) * k1) * k1;
+            c *= k1;
+            d ^= c;
+            s += 16;
+            l -= 16;
+        } while (l > 0);
+    }
+    a = HashLen16(a, c);
+    b = HashLen16(d, b);
+    return uint128(a ^ b, HashLen16(b, a));
+}
+
+uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed) noexcept {
+    if (len < 128) {
+        return CityMurmur(s, len, seed);
+    }
+
+    // We expect len >= 128 to be the common case.  Keep 56 bytes of state:
+    // v, w, x, y, and z.
+    pair<uint64, uint64> v, w;
+    uint64 x = Uint128Low64(seed);
+    uint64 y = Uint128High64(seed);
+    uint64 z = len * k1;
+    v.first = Rotate(y ^ k1, 49) * k1 + UNALIGNED_LOAD64(s);
+    v.second = Rotate(v.first, 42) * k1 + UNALIGNED_LOAD64(s + 8);
+    w.first = Rotate(y + z, 35) * k1 + x;
+    w.second = Rotate(x + UNALIGNED_LOAD64(s + 88), 53) * k1;
+
+    // This is the same inner loop as CityHash64(), manually unrolled.
+    do {
+        x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;
+        y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;
+        x ^= w.second;
+        y ^= v.first;
+        z = Rotate(z ^ w.first, 33);
+        v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+        w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
+        DoSwap(z, x);
+        s += 64;
+        x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;
+        y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;
+        x ^= w.second;
+        y ^= v.first;
+        z = Rotate(z ^ w.first, 33);
+        v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+        w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
+        DoSwap(z, x);
+        s += 64;
+        len -= 128;
+    } while (LIKELY(len >= 128));
+    y += Rotate(w.first, 37) * k0 + z;
+    x += Rotate(v.first + z, 49) * k0;
+    // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
+    for (size_t tail_done = 0; tail_done < len;) {
+        tail_done += 32;
+        y = Rotate(y - x, 42) * k0 + v.second;
+        w.first += UNALIGNED_LOAD64(s + len - tail_done + 16);
+        x = Rotate(x, 49) * k0 + w.first;
+        w.first += v.first;
+        v = WeakHashLen32WithSeeds(s + len - tail_done, v.first, v.second);
+    }
+    // At this point our 48 bytes of state should contain more than
+    // enough information for a strong 128-bit hash.  We use two
+    // different 48-byte-to-8-byte hashes to get a 16-byte final result.
+    x = HashLen16(x, v.first);
+    y = HashLen16(y, w.first);
+    return uint128(HashLen16(x + v.second, w.second) + y,
+                   HashLen16(x + w.second, y + v.second));
+}
+
+uint128 CityHash128(const char* s, size_t len) noexcept {
+    if (len >= 16) {
+        return CityHash128WithSeed(s + 16,
+                                   len - 16,
+                                   uint128(UNALIGNED_LOAD64(s) ^ k3,
+                                           UNALIGNED_LOAD64(s + 8)));
+    } else if (len >= 8) {
+        return CityHash128WithSeed(nullptr,
+                                   0,
+                                   uint128(UNALIGNED_LOAD64(s) ^ (len * k0),
+                                           UNALIGNED_LOAD64(s + len - 8) ^ k1));
+    } else {
+        return CityHash128WithSeed(s, len, uint128(k0, k1));
+    }
+}
+
+// TODO(yazevnul): move this function to unittests
+void TestCompilationOfCityHashTemplates() {
+    TStringBuf s;
+    CityHash64(s);
+    CityHash64WithSeed(s, 1);
+    CityHash64WithSeeds(s, 1, 2);
+    CityHash128(s);
+    CityHash128WithSeed(s, uint128(1, 2));
+}
+
+#endif
diff --git a/util/digest/city.h b/util/digest/city.h
new file mode 100644
index 0000000000..675a798074
--- /dev/null
+++ b/util/digest/city.h
@@ -0,0 +1,83 @@
+#pragma once
+
+#include <util/generic/utility.h>
+#include <util/generic/strbuf.h>
+
+#include <utility>
+
+// NOTE: These functions provide CityHash 1.0 implementation whose results are *different* from
+// the mainline version of CityHash.
+
+using uint128 = std::pair<ui64, ui64>;
+
+constexpr ui64 Uint128Low64(const uint128& x) {
+    return x.first;
+}
+
+constexpr ui64 Uint128High64(const uint128& x) {
+    return x.second;
+}
+
+// Hash functions for a byte array.
+// http://en.wikipedia.org/wiki/CityHash
+
+Y_PURE_FUNCTION ui64 CityHash64(const char* buf, size_t len) noexcept;
+
+Y_PURE_FUNCTION ui64 CityHash64WithSeed(const char* buf, size_t len, ui64 seed) noexcept;
+
+Y_PURE_FUNCTION ui64 CityHash64WithSeeds(const char* buf, size_t len, ui64 seed0, ui64 seed1) noexcept;
+
+Y_PURE_FUNCTION uint128 CityHash128(const char* s, size_t len) noexcept;
+
+Y_PURE_FUNCTION uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed) noexcept;
+
+// Hash 128 input bits down to 64 bits of output.
+// This is intended to be a reasonably good hash function.
+inline ui64 Hash128to64(const uint128& x) {
+    // Murmur-inspired hashing.
+    const ui64 kMul = 0x9ddfea08eb382d69ULL;
+    ui64 a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
+    a ^= (a >> 47);
+    ui64 b = (Uint128High64(x) ^ a) * kMul;
+    b ^= (b >> 47);
+    b *= kMul;
+    return b;
+}
+
+namespace NPrivateCityHash {
+    template <class TStringType>
+    inline TStringBuf GetBufFromStr(const TStringType& str) {
+        static_assert(std::is_integral<std::remove_reference_t<decltype(*str.data())>>::value, "invalid type passed to hash function");
+        return TStringBuf(reinterpret_cast<const char*>(str.data()), (str.size()) * sizeof(*str.data()));
+    }
+}
+
+template <class TStringType>
+inline ui64 CityHash64(const TStringType& str) {
+    TStringBuf buf = NPrivateCityHash::GetBufFromStr(str);
+    return CityHash64(buf.data(), buf.size());
+}
+
+template <class TStringType>
+inline ui64 CityHash64WithSeeds(const TStringType& str, ui64 seed0, ui64 seed1) {
+    TStringBuf buf = NPrivateCityHash::GetBufFromStr(str);
+    return CityHash64WithSeeds(buf.data(), buf.size(), seed0, seed1);
+}
+
+template <class TStringType>
+inline ui64 CityHash64WithSeed(const TStringType& str, ui64 seed) {
+    TStringBuf buf = NPrivateCityHash::GetBufFromStr(str);
+    return CityHash64WithSeed(buf.data(), buf.size(), seed);
+}
+
+template <class TStringType>
+inline uint128 CityHash128(const TStringType& str) {
+    TStringBuf buf = NPrivateCityHash::GetBufFromStr(str);
+    return CityHash128(buf.data(), buf.size());
+}
+
+template <class TStringType>
+inline uint128 CityHash128WithSeed(const TStringType& str, uint128 seed) {
+    TStringBuf buf = NPrivateCityHash::GetBufFromStr(str);
+    return CityHash128WithSeed(buf.data(), buf.size(), seed);
+}
diff --git a/util/digest/fnv.cpp b/util/digest/fnv.cpp
new file mode 100644
index 0000000000..57fc5964c3
--- /dev/null
+++ b/util/digest/fnv.cpp
@@ -0,0 +1 @@
+#include "fnv.h"
diff --git a/util/digest/fnv.h b/util/digest/fnv.h
new file mode 100644
index 0000000000..87b41a3de7
--- /dev/null
+++ b/util/digest/fnv.h
@@ -0,0 +1,73 @@
+#pragma once
+
+#include <util/system/defaults.h>
+
+#define FNV32INIT 2166136261U
+#define FNV32PRIME 16777619U
+#define FNV64INIT ULL(14695981039346656037)
+#define FNV64PRIME ULL(1099511628211)
+
+namespace NFnvPrivate {
+    template <class It>
+    constexpr ui32 FnvHash32(It b, It e, ui32 init) {
+        while (b != e) {
+            init = (init * FNV32PRIME) ^ (unsigned char)*b++;
+        }
+
+        return init;
+    }
+
+    template <class It>
+    constexpr ui64 FnvHash64(It b, It e, ui64 init) {
+        while (b != e) {
+            init = (init * FNV64PRIME) ^ (unsigned char)*b++;
+        }
+
+        return init;
+    }
+
+    template <unsigned N>
+    struct TFnvHelper;
+
+#define DEF_FNV(t)                                               \
+    template <>                                                  \
+    struct TFnvHelper<t> {                                       \
+        static const ui##t Init = FNV##t##INIT;                  \
+        template <class It>                                      \
+        static constexpr ui##t FnvHash(It b, It e, ui##t init) { \
+            return FnvHash##t(b, e, init);                       \
+        }                                                        \
+    };
+
+    DEF_FNV(32)
+    DEF_FNV(64)
+
+#undef DEF_FNV
+}
+
+template <class T, class It>
+static constexpr T FnvHash(It b, It e, T init) {
+    static_assert(sizeof(*b) == 1, "expect sizeof(*b) == 1");
+
+    return (T)NFnvPrivate::TFnvHelper<8 * sizeof(T)>::FnvHash(b, e, init);
+}
+
+template <class T, class It>
+static constexpr T FnvHash(It b, It e) {
+    return FnvHash<T>(b, e, (T)NFnvPrivate::TFnvHelper<8 * sizeof(T)>::Init);
+}
+
+template <class T>
+static constexpr T FnvHash(const void* buf, size_t len, T init) {
+    return FnvHash<T>((const unsigned char*)buf, (const unsigned char*)buf + len, init);
+}
+
+template <class T>
+static constexpr T FnvHash(const void* buf, size_t len) {
+    return FnvHash<T>((const unsigned char*)buf, (const unsigned char*)buf + len);
+}
+
+template <class T, class Buf>
+static constexpr T FnvHash(const Buf& buf) {
+    return FnvHash<T>(buf.data(), buf.size() * sizeof(*buf.data()));
+}
diff --git a/util/digest/fnv.pxd b/util/digest/fnv.pxd
new file mode 100644
index 0000000000..92396cf4d3
--- /dev/null
+++ b/util/digest/fnv.pxd
@@ -0,0 +1,2 @@
+cdef extern from "util/digest/fnv.h":
+    T FnvHash[T](const char* buf, size_t len) nogil
diff --git a/util/digest/fnv_ut.cpp b/util/digest/fnv_ut.cpp
new file mode 100644
index 0000000000..ce56642b3e
--- /dev/null
+++ b/util/digest/fnv_ut.cpp
@@ -0,0 +1,23 @@
+#include "fnv.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+Y_UNIT_TEST_SUITE(TFnvTest) {
+    Y_UNIT_TEST(TestFnv32) {
+        const auto h32 = ULL(2849763999);
+        UNIT_ASSERT_EQUAL(FnvHash<ui32>("1234567", 7), h32);
+        UNIT_ASSERT_EQUAL(FnvHash<ui32>(TStringBuf("1234567")), h32);
+
+        UNIT_ASSERT_EQUAL(FnvHash<ui32>(nullptr, 0), FNV32INIT);
+        UNIT_ASSERT_EQUAL(FnvHash<ui32>(TStringBuf()), FNV32INIT);
+    }
+
+    Y_UNIT_TEST(TestFnv64) {
+        const auto h64 = ULL(2449551094593701855);
+        UNIT_ASSERT_EQUAL(FnvHash<ui64>("1234567", 7), h64);
+        UNIT_ASSERT_EQUAL(FnvHash<ui64>(TStringBuf("1234567")), h64);
+
+        UNIT_ASSERT_EQUAL(FnvHash<ui64>(nullptr, 0), FNV64INIT);
+        UNIT_ASSERT_EQUAL(FnvHash<ui64>(TStringBuf()), FNV64INIT);
+    }
+};
diff --git a/util/digest/multi.cpp b/util/digest/multi.cpp
new file mode 100644
index 0000000000..e4a59f0e67
--- /dev/null
+++ b/util/digest/multi.cpp
@@ -0,0 +1 @@
+#include "multi.h"
diff --git a/util/digest/multi.h b/util/digest/multi.h
new file mode 100644
index 0000000000..8e4597c9dc
--- /dev/null
+++ b/util/digest/multi.h
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <util/str_stl.h>
+
+#include "numeric.h"
+
+template <typename TOne>
+constexpr size_t MultiHash(const TOne& one) noexcept {
+    return THash<TOne>()(one);
+}
+template <typename THead, typename... TTail>
+constexpr size_t MultiHash(const THead& head, const TTail&... tail) noexcept {
+    return CombineHashes(MultiHash(tail...), THash<THead>()(head));
+}
diff --git a/util/digest/multi.pxd b/util/digest/multi.pxd
new file mode 100644
index 0000000000..8b4fae5016
--- /dev/null
+++ b/util/digest/multi.pxd
@@ -0,0 +1,2 @@
+cdef extern from "<util/digest/multi.h>" nogil:
+    size_t MultiHash(...);
diff --git a/util/digest/multi_ut.cpp b/util/digest/multi_ut.cpp
new file mode 100644
index 0000000000..dff64ff0cc
--- /dev/null
+++ b/util/digest/multi_ut.cpp
@@ -0,0 +1,38 @@
+#include "multi.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/stream/output.h>
+
+class TMultiHashTest: public TTestBase {
+    UNIT_TEST_SUITE(TMultiHashTest);
+    UNIT_TEST(TestStrInt)
+    UNIT_TEST(TestIntStr)
+    UNIT_TEST(TestSimpleCollision)
+    UNIT_TEST(TestTypes)
+    UNIT_TEST_SUITE_END();
+
+private:
+    inline void TestStrInt() {
+        UNIT_ASSERT_EQUAL(MultiHash(TString("1234567"), static_cast<int>(123)), static_cast<size_t>(ULL(17038203285960021630)));
+    }
+
+    inline void TestIntStr() {
+        UNIT_ASSERT_EQUAL(MultiHash(static_cast<int>(123), TString("1234567")), static_cast<size_t>(ULL(9973288649881090712)));
+    }
+
+    inline void TestSimpleCollision() {
+        UNIT_ASSERT_UNEQUAL(MultiHash(1, 1, 0), MultiHash(2, 2, 0));
+    }
+
+    inline void TestTypes() {
+        UNIT_ASSERT_EQUAL(MultiHash("aaa", (ui64)123), MultiHash("aaa", 123));
+        UNIT_ASSERT_EQUAL(MultiHash("aaa", (i64)123), MultiHash("aaa", 123));
+        UNIT_ASSERT_EQUAL(MultiHash("aaa", (i32)123), MultiHash("aaa", 123));
+        UNIT_ASSERT_EQUAL(MultiHash("aaa", (ui32)123), MultiHash("aaa", 123));
+        UNIT_ASSERT_EQUAL(MultiHash("aaa", (i64)-123), MultiHash("aaa", -123));
+        UNIT_ASSERT_EQUAL(MultiHash("aaa", (i32)-123), MultiHash("aaa", -123));
+    }
+};
+
+UNIT_TEST_SUITE_REGISTRATION(TMultiHashTest);
diff --git a/util/digest/multi_ut.pyx b/util/digest/multi_ut.pyx
new file mode 100644
index 0000000000..26faa0069b
--- /dev/null
+++ b/util/digest/multi_ut.pyx
@@ -0,0 +1,19 @@
+from util.digest.multi cimport MultiHash
+from util.generic.string cimport TString
+
+import pytest
+import unittest
+
+
+class TestMultiHash(unittest.TestCase):
+
+    def test_str_int(self):
+        value = MultiHash(TString(b"1234567"), 123)
+        self.assertEquals(value, 17038203285960021630)
+
+    def test_int_str(self):
+        value = MultiHash(123, TString(b"1234567"))
+        self.assertEquals(value, 9973288649881090712)
+
+    def test_collision(self):
+        self.assertNotEquals(MultiHash(1, 1, 0), MultiHash(2, 2, 0))
diff --git a/util/digest/murmur.cpp b/util/digest/murmur.cpp
new file mode 100644
index 0000000000..b041d3e5f2
--- /dev/null
+++ b/util/digest/murmur.cpp
@@ -0,0 +1,131 @@
+#include "murmur.h"
+
+#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;
+                [[fallthrough]];
+
+            case 2:
+                h ^= data[1] << 8;
+                [[fallthrough]];
+
+            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;
+                [[fallthrough]];
+
+            case 6:
+                h ^= ui64(data2[5]) << 40;
+                [[fallthrough]];
+
+            case 5:
+                h ^= ui64(data2[4]) << 32;
+                [[fallthrough]];
+
+            case 4:
+                h ^= ui64(data2[3]) << 24;
+                [[fallthrough]];
+
+            case 3:
+                h ^= ui64(data2[2]) << 16;
+                [[fallthrough]];
+
+            case 2:
+                h ^= ui64(data2[1]) << 8;
+                [[fallthrough]];
+
+            case 1:
+                h ^= ui64(data2[0]);
+                h *= m;
+                break;
+        }
+
+        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
new file mode 100644
index 0000000000..6b519b430a
--- /dev/null
+++ b/util/digest/murmur.h
@@ -0,0 +1,55 @@
+#pragma once
+
+#include <util/system/defaults.h>
+#include <util/generic/array_ref.h>
+
+/*
+ * murmur2 from http://murmurhash.googlepages.com/
+ *
+ */
+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 <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);
+}
+
+template <class T>
+static inline T MurmurHash(const void* buf, size_t len) noexcept {
+    return MurmurHash<T>(buf, len, (T)0);
+}
+
+//non-inline version
+size_t MurmurHashSizeT(const char* buf, size_t len) noexcept;
+
+template <typename TOut = size_t>
+struct TMurmurHash {
+    TOut operator()(const void* buf, size_t len) const noexcept {
+        return MurmurHash<TOut>(buf, len);
+    }
+
+    template <typename ElementType>
+    TOut operator()(const TArrayRef<ElementType>& data) const noexcept {
+        return operator()(data.data(), data.size() * sizeof(ElementType));
+    }
+};
diff --git a/util/digest/murmur_ut.cpp b/util/digest/murmur_ut.cpp
new file mode 100644
index 0000000000..29287668bc
--- /dev/null
+++ b/util/digest/murmur_ut.cpp
@@ -0,0 +1,85 @@
+
+#include "murmur.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+class TMurmurHashTest: public TTestBase {
+    UNIT_TEST_SUITE(TMurmurHashTest);
+    UNIT_TEST(TestHash32)
+    UNIT_TEST(TestUnalignedHash32)
+    UNIT_TEST(TestHash64)
+    UNIT_TEST(TestUnalignedHash64)
+    UNIT_TEST(TestWrapperBiggerTypes)
+    UNIT_TEST_SUITE_END();
+
+private:
+    inline void TestHash32() {
+        ui8 buf[256];
+
+        for (size_t i = 0; i < 256; ++i) {
+            buf[i] = i;
+        }
+
+        Test<ui32>(buf, 256, 2373126550UL);
+        TestWrapper<ui8, ui32>({buf, buf + 256}, 2373126550UL);
+        Test<ui32>(buf, 255, 3301607533UL);
+        Test<ui32>(buf, 254, 2547410121UL);
+        Test<ui32>(buf, 253, 80030810UL);
+    }
+
+    inline void TestUnalignedHash32() {
+        ui8 buf[257];
+        ui8* unalignedBuf = buf + 1;
+
+        for (size_t i = 0; i < 256; ++i) {
+            unalignedBuf[i] = i;
+        }
+
+        Test<ui32>(unalignedBuf, 256, 2373126550UL);
+    }
+
+    inline void TestHash64() {
+        ui8 buf[256];
+
+        for (size_t i = 0; i < 256; ++i) {
+            buf[i] = i;
+        }
+
+        Test<ui64>(buf, 256, ULL(12604435678857905857));
+        TestWrapper<ui8, ui64>({buf, buf + 256}, ULL(12604435678857905857));
+        Test<ui64>(buf, 255, ULL(1708835094528446095));
+        Test<ui64>(buf, 254, ULL(5077937678736514994));
+        Test<ui64>(buf, 253, ULL(11553864555081396353));
+    }
+
+    inline void TestUnalignedHash64() {
+        ui8 buf[257];
+        ui8* unalignedBuf = buf + 1;
+
+        for (size_t i = 0; i < 256; ++i) {
+            unalignedBuf[i] = i;
+        }
+
+        Test<ui64>(unalignedBuf, 256, ULL(12604435678857905857));
+    }
+
+    inline void TestWrapperBiggerTypes() {
+        ui32 buf[] = {24, 42};
+        TestWrapper<ui32, ui32>({buf, buf + 2}, MurmurHash<ui32>(buf, sizeof(ui32) * 2));
+        TestWrapper<ui32, ui64>({buf, buf + 2}, MurmurHash<ui64>(buf, sizeof(ui32) * 2));
+    }
+
+private:
+    template <class T>
+    inline void Test(const void* data, size_t len, T expected) {
+        UNIT_ASSERT_STRINGS_EQUAL(ToString(MurmurHash<T>(data, len)), ToString(expected));
+    }
+
+    template <class E, class T>
+    inline void TestWrapper(const TArrayRef<E>& array, T expected) {
+        auto val = TMurmurHash<T>()(array);
+        UNIT_ASSERT_EQUAL(val, expected);
+    }
+};
+
+UNIT_TEST_SUITE_REGISTRATION(TMurmurHashTest);
diff --git a/util/digest/numeric.cpp b/util/digest/numeric.cpp
new file mode 100644
index 0000000000..d4d3f063fa
--- /dev/null
+++ b/util/digest/numeric.cpp
@@ -0,0 +1 @@
+#include "numeric.h"
diff --git a/util/digest/numeric.h b/util/digest/numeric.h
new file mode 100644
index 0000000000..e20bd908e4
--- /dev/null
+++ b/util/digest/numeric.h
@@ -0,0 +1,86 @@
+#pragma once
+
+#include <util/generic/typelist.h>
+#include <util/system/defaults.h>
+
+/*
+ * original url (now dead): http://www.cris.com/~Ttwang/tech/inthash.htm
+ * copy: https://gist.github.com/badboy/6267743
+ */
+
+static constexpr ui8 IntHashImpl(ui8 key8) noexcept {
+    size_t key = key8;
+
+    key += ~(key << 15);
+    key ^= (key >> 10);
+    key += (key << 3);
+    key ^= (key >> 6);
+    key += ~(key << 11);
+    key ^= (key >> 16);
+
+    return static_cast<ui8>(key);
+}
+
+static constexpr ui16 IntHashImpl(ui16 key16) noexcept {
+    size_t key = key16;
+
+    key += ~(key << 15);
+    key ^= (key >> 10);
+    key += (key << 3);
+    key ^= (key >> 6);
+    key += ~(key << 11);
+    key ^= (key >> 16);
+
+    return static_cast<ui16>(key);
+}
+
+static constexpr ui32 IntHashImpl(ui32 key) noexcept {
+    key += ~(key << 15);
+    key ^= (key >> 10);
+    key += (key << 3);
+    key ^= (key >> 6);
+    key += ~(key << 11);
+    key ^= (key >> 16);
+
+    return key;
+}
+
+static constexpr ui64 IntHashImpl(ui64 key) noexcept {
+    key += ~(key << 32);
+    key ^= (key >> 22);
+    key += ~(key << 13);
+    key ^= (key >> 8);
+    key += (key << 3);
+    key ^= (key >> 15);
+    key += ~(key << 27);
+    key ^= (key >> 31);
+
+    return key;
+}
+
+template <class T>
+static constexpr T IntHash(T t) noexcept {
+    using TCvt = TFixedWidthUnsignedInt<T>;
+
+    return IntHashImpl((TCvt)(t));
+}
+
+/*
+ * can handle floats && pointers
+ */
+template <class T>
+static constexpr size_t NumericHash(T t) noexcept {
+    using TCvt = TFixedWidthUnsignedInt<T>;
+
+    union Y_HIDDEN {
+        T t;
+        TCvt cvt;
+    } u{t};
+
+    return (size_t)IntHash(u.cvt);
+}
+
+template <class T>
+static constexpr T CombineHashes(T l, T r) noexcept {
+    return IntHash(l) ^ r;
+}
diff --git a/util/digest/sequence.cpp b/util/digest/sequence.cpp
new file mode 100644
index 0000000000..5ab731f9bd
--- /dev/null
+++ b/util/digest/sequence.cpp
@@ -0,0 +1 @@
+#include "sequence.h"
diff --git a/util/digest/sequence.h b/util/digest/sequence.h
new file mode 100644
index 0000000000..712331007b
--- /dev/null
+++ b/util/digest/sequence.h
@@ -0,0 +1,48 @@
+#pragma once
+
+#include "numeric.h"
+#include <util/generic/hash.h>
+#include <util/generic/array_ref.h>
+
+template <typename ElementHash = void>
+class TRangeHash {
+private:
+    template <typename ElementType>
+    using TBase = std::conditional_t<
+        !std::is_void<ElementHash>::value,
+        ElementHash,
+        THash<ElementType>>;
+
+public:
+    template <typename Range>
+    size_t operator()(const Range& range) const {
+        size_t accumulated = 0;
+        for (const auto& element : range) {
+            accumulated = CombineHashes(accumulated, TBase<typename Range::value_type>()(element));
+        }
+        return accumulated;
+    }
+};
+
+using TSimpleRangeHash = TRangeHash<>;
+
+template <typename RegionHash = void>
+class TContiguousHash {
+private:
+    template <typename ElementType>
+    using TBase = std::conditional_t<
+        !std::is_void<RegionHash>::value,
+        RegionHash,
+        TRangeHash<ElementType>>;
+
+public:
+    template <typename ContainerType>
+    auto operator()(const ContainerType& container) const {
+        return operator()(MakeArrayRef(container));
+    }
+
+    template <typename ElementType>
+    auto operator()(const TArrayRef<ElementType>& data) const {
+        return TBase<ElementType>()(data);
+    }
+};
diff --git a/util/digest/sequence_ut.cpp b/util/digest/sequence_ut.cpp
new file mode 100644
index 0000000000..87d6102ee5
--- /dev/null
+++ b/util/digest/sequence_ut.cpp
@@ -0,0 +1,62 @@
+#include "sequence.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+#include <util/generic/map.h>
+#include <util/generic/vector.h>
+
+class TRangeHashTest: public TTestBase {
+    UNIT_TEST_SUITE(TRangeHashTest);
+    UNIT_TEST(TestStrokaInt)
+    UNIT_TEST(TestIntVector)
+    UNIT_TEST(TestOneElement)
+    UNIT_TEST(TestMap);
+    UNIT_TEST(TestCollectionIndependancy);
+    UNIT_TEST_SUITE_END();
+
+private:
+    inline void TestStrokaInt() {
+        const size_t canonicalHash = static_cast<size_t>(ULL(12727184940294366172));
+        UNIT_ASSERT_EQUAL(canonicalHash, TRangeHash<>()(TString("12345")));
+    }
+
+    inline void TestIntVector() {
+        const size_t canonicalHash = static_cast<size_t>(ULL(1351128487744230578));
+        TVector<int> testVec = {1, 2, 4, 3};
+        UNIT_ASSERT_EQUAL(canonicalHash, TRangeHash<>()(testVec));
+    }
+
+    inline void TestOneElement() {
+        const int testVal = 42;
+        TVector<int> testVec = {testVal};
+        UNIT_ASSERT_UNEQUAL(THash<int>()(testVal), TRangeHash<>()(testVec));
+    }
+
+    inline void TestMap() {
+        const size_t canonicalHash = static_cast<size_t>(ULL(4415387926488545605));
+        TMap<TString, int> testMap{{"foo", 123}, {"bar", 456}};
+        UNIT_ASSERT_EQUAL(canonicalHash, TRangeHash<>()(testMap));
+    }
+
+    inline void TestCollectionIndependancy() {
+        TVector<char> testVec = {'a', 'b', 'c'};
+        TString testStroka = "abc";
+        UNIT_ASSERT_EQUAL(TRangeHash<>()(testVec), TRangeHash<>()(testStroka));
+    }
+};
+
+class TSequenceHashTest: public TTestBase {
+    UNIT_TEST_SUITE(TSequenceHashTest);
+    UNIT_TEST(TestSimpleBuffer)
+    UNIT_TEST_SUITE_END();
+
+private:
+    inline void TestSimpleBuffer() {
+        int arr[] = {1, 2, 3};
+        const size_t canonicalHash = static_cast<size_t>(ULL(3903918011533391876));
+        TContiguousHash<TSimpleRangeHash> hasher;
+        UNIT_ASSERT_EQUAL(canonicalHash, hasher(TArrayRef<int>(arr, arr + 3)));
+    }
+};
+
+UNIT_TEST_SUITE_REGISTRATION(TRangeHashTest);
+UNIT_TEST_SUITE_REGISTRATION(TSequenceHashTest);
diff --git a/util/digest/ut/ya.make b/util/digest/ut/ya.make
new file mode 100644
index 0000000000..245b2cf6d2
--- /dev/null
+++ b/util/digest/ut/ya.make
@@ -0,0 +1,15 @@
+UNITTEST_FOR(util)
+
+OWNER(g:util)
+SUBSCRIBER(g:util-subscribers)
+
+SRCS(
+    digest/fnv_ut.cpp
+    digest/murmur_ut.cpp
+    digest/multi_ut.cpp
+    digest/sequence_ut.cpp
+)
+
+INCLUDE(${ARCADIA_ROOT}/util/tests/ya_util_tests.inc)
+
+END()
diff --git a/util/digest/ya.make b/util/digest/ya.make
new file mode 100644
index 0000000000..e378a7e419
--- /dev/null
+++ b/util/digest/ya.make
@@ -0,0 +1,12 @@
+OWNER(g:util)
+SUBSCRIBER(g:util-subscribers)
+
+PROVIDES(cityhash)
+
+RECURSE(
+    benchmark
+)
+
+RECURSE_FOR_TESTS(
+    ut
+)