intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

39 files changed, 2138 insertions, 0 deletions

diff --git a/util/random/benchmark/prng/main.cpp b/util/random/benchmark/prng/main.cpp
new file mode 100644
index 0000000000..2c6279ff71
--- /dev/null
+++ b/util/random/benchmark/prng/main.cpp
@@ -0,0 +1,123 @@
+#include <library/cpp/testing/benchmark/bench.h>
+
+#include <util/random/entropy.h>
+#include <util/random/fast.h>
+#include <util/random/normal.h>
+#include <util/random/mersenne.h>
+#include <util/system/compiler.h>
+#include <util/generic/xrange.h>
+
+#include <random>
+
+// double part
+Y_CPU_BENCHMARK(Mersenne32_Double, p) {
+    TMersenne<ui32> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRandReal1());
+    }
+}
+
+Y_CPU_BENCHMARK(Mersenne64_Double, p) {
+    TMersenne<ui64> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRandReal1());
+    }
+}
+
+Y_CPU_BENCHMARK(Fast32_Double, p) {
+    TFastRng<ui32> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRandReal1());
+    }
+}
+
+Y_CPU_BENCHMARK(Fast64_Double, p) {
+    TFastRng<ui64> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRandReal1());
+    }
+}
+
+// integer part
+Y_CPU_BENCHMARK(mt19937_32, p) {
+    std::mt19937 mt;
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+
+        Y_DO_NOT_OPTIMIZE_AWAY(mt());
+    }
+}
+
+Y_CPU_BENCHMARK(mt19937_64, p) {
+    std::mt19937_64 mt;
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+
+        Y_DO_NOT_OPTIMIZE_AWAY(mt());
+    }
+}
+
+Y_CPU_BENCHMARK(Mersenne32_GenRand, p) {
+    TMersenne<ui32> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRand());
+    }
+}
+
+Y_CPU_BENCHMARK(Mersenne64_GenRand, p) {
+    TMersenne<ui64> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRand());
+    }
+}
+
+Y_CPU_BENCHMARK(Fast32_GenRand, p) {
+    TFastRng<ui32> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRand());
+    }
+}
+
+Y_CPU_BENCHMARK(Fast64_GenRand, p) {
+    TFastRng<ui64> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(rng.GenRand());
+    }
+}
+
+Y_CPU_BENCHMARK(StlNormal, p) {
+    TFastRng<ui64> rng(Seed());
+    std::normal_distribution<double> d(1.0, 0.0);
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(d(rng));
+    }
+}
+
+Y_CPU_BENCHMARK(UtilNormal, p) {
+    TFastRng<ui64> rng(Seed());
+
+    for (auto i : xrange<size_t>(0, p.Iterations())) {
+        (void)i;
+        Y_DO_NOT_OPTIMIZE_AWAY(NormalDistribution<double>(rng, 1.0, 0.0));
+    }
+}
diff --git a/util/random/benchmark/prng/metrics/main.py b/util/random/benchmark/prng/metrics/main.py
new file mode 100644
index 0000000000..15b371fe75
--- /dev/null
+++ b/util/random/benchmark/prng/metrics/main.py
@@ -0,0 +1,5 @@
+import yatest.common as yc
+
+
+def test_export_metrics(metrics):
+    metrics.set_benchmark(yc.execute_benchmark('util/random/benchmark/prng/prng', threads=8))
diff --git a/util/random/benchmark/prng/metrics/ya.make b/util/random/benchmark/prng/metrics/ya.make
new file mode 100644
index 0000000000..1f56aac0bd
--- /dev/null
+++ b/util/random/benchmark/prng/metrics/ya.make
@@ -0,0 +1,21 @@
+OWNER(
+    yazevnul
+    g:util
+)
+SUBSCRIBER(g:util-subscribers)
+
+PY2TEST()
+
+SIZE(LARGE)
+
+TAG(
+    ya:force_sandbox
+    sb:intel_e5_2660v1
+    ya:fat
+)
+
+TEST_SRCS(main.py)
+
+DEPENDS(util/random/benchmark/prng)
+
+END()
diff --git a/util/random/benchmark/prng/ya.make b/util/random/benchmark/prng/ya.make
new file mode 100644
index 0000000000..976977014f
--- /dev/null
+++ b/util/random/benchmark/prng/ya.make
@@ -0,0 +1,13 @@
+OWNER(
+    yazevnul
+    g:util
+)
+SUBSCRIBER(g:util-subscribers)
+
+Y_BENCHMARK()
+
+SRCS(
+    main.cpp
+)
+
+END()
diff --git a/util/random/benchmark/ya.make b/util/random/benchmark/ya.make
new file mode 100644
index 0000000000..7d753ae6e7
--- /dev/null
+++ b/util/random/benchmark/ya.make
@@ -0,0 +1,10 @@
+OWNER(
+    yazevnul
+    g:util
+)
+SUBSCRIBER(g:util-subscribers)
+
+RECURSE(
+    prng
+    prng/metrics
+)
diff --git a/util/random/common_ops.cpp b/util/random/common_ops.cpp
new file mode 100644
index 0000000000..f856a76cbc
--- /dev/null
+++ b/util/random/common_ops.cpp
@@ -0,0 +1 @@
+#include "common_ops.h"
diff --git a/util/random/common_ops.h b/util/random/common_ops.h
new file mode 100644
index 0000000000..602eede351
--- /dev/null
+++ b/util/random/common_ops.h
@@ -0,0 +1,130 @@
+#pragma once
+
+#include <util/system/defaults.h>
+#include <util/system/yassert.h>
+
+namespace NPrivate {
+    constexpr double ToRandReal1(const ui32 x) noexcept {
+        return x * (double)(1.0 / 4294967295.0);
+    }
+
+    constexpr double ToRandReal2(const ui32 x) noexcept {
+        return x * (double)(1.0 / 4294967296.0);
+    }
+
+    constexpr double ToRandReal3(const ui32 x) noexcept {
+        return ((double)x + 0.5) * (double)(1.0 / 4294967296.0);
+    }
+
+    constexpr double ToRandReal1(const ui64 x) noexcept {
+        return (x >> 11) * (double)(1.0 / 9007199254740991.0);
+    }
+
+    constexpr double ToRandReal2(const ui64 x) noexcept {
+        return (x >> 11) * (double)(1.0 / 9007199254740992.0);
+    }
+
+    constexpr double ToRandReal3(const ui64 x) noexcept {
+        return ((x >> 12) + 0.5) * (double)(1.0 / 4503599627370496.0);
+    }
+
+    constexpr double ToRandReal4(const ui64 x) noexcept {
+        return double(x * (double)(1.0 / 18446744073709551616.0L));
+    }
+
+    template <class T>
+    static inline ui64 ToRand64(T&& rng, ui32 x) noexcept {
+        return ((ui64)x) | (((ui64)rng.GenRand()) << 32);
+    }
+
+    template <class T>
+    static constexpr ui64 ToRand64(T&&, ui64 x) noexcept {
+        return x;
+    }
+
+    /*
+     * return value in range [0, max) from any generator
+     */
+    template <class T, class TRandGen>
+    static T GenUniform(T max, TRandGen&& gen) {
+        Y_VERIFY(max > 0, "Invalid random number range [0, 0)");
+
+        const T randmax = gen.RandMax() - gen.RandMax() % max;
+        T rand;
+
+        while ((rand = gen.GenRand()) >= randmax) {
+            /* no-op */
+        }
+
+        return rand % max;
+    }
+}
+
+template <class TRandType, class T>
+struct TCommonRNG {
+    using TResult = TRandType;
+    using result_type = TRandType;
+
+    inline T& Engine() noexcept {
+        return static_cast<T&>(*this);
+    }
+
+    static constexpr TResult _Min = TResult(0);
+    static constexpr TResult _Max = TResult(-1);
+
+    static constexpr TResult RandMax() noexcept {
+        return _Max;
+    }
+
+    static constexpr TResult RandMin() noexcept {
+        return _Min;
+    }
+
+    /* generates uniformly distributed random number on [0, t) interval */
+    inline TResult Uniform(TResult t) noexcept {
+        return ::NPrivate::GenUniform(t, Engine());
+    }
+
+    /* generates uniformly distributed random number on [f, t) interval */
+    inline TResult Uniform(TResult f, TResult t) noexcept {
+        return f + Uniform(t - f);
+    }
+
+    /* generates 64-bit random number for current(may be 32 bit) rng */
+    inline ui64 GenRand64() noexcept {
+        return ::NPrivate::ToRand64(Engine(), Engine().GenRand());
+    }
+
+    /* generates a random number on [0, 1]-real-interval */
+    inline double GenRandReal1() noexcept {
+        return ::NPrivate::ToRandReal1(Engine().GenRand());
+    }
+
+    /* generates a random number on [0, 1)-real-interval */
+    inline double GenRandReal2() noexcept {
+        return ::NPrivate::ToRandReal2(Engine().GenRand());
+    }
+
+    /* generates a random number on (0, 1)-real-interval */
+    inline double GenRandReal3() noexcept {
+        return ::NPrivate::ToRandReal3(Engine().GenRand());
+    }
+
+    /* generates a random number on [0, 1) with 53-bit resolution */
+    inline double GenRandReal4() noexcept {
+        return ::NPrivate::ToRandReal4(Engine().GenRand64());
+    }
+
+    //compatibility stuff
+    inline TResult operator()() noexcept {
+        return Engine().GenRand();
+    }
+
+    static constexpr TResult max() noexcept {
+        return T::RandMax();
+    }
+
+    static constexpr TResult min() noexcept {
+        return T::RandMin();
+    }
+};
diff --git a/util/random/common_ops_ut.cpp b/util/random/common_ops_ut.cpp
new file mode 100644
index 0000000000..905912bd1e
--- /dev/null
+++ b/util/random/common_ops_ut.cpp
@@ -0,0 +1,69 @@
+#include "common_ops.h"
+#include "random.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/digest/numeric.h>
+
+#include <random>
+
+Y_UNIT_TEST_SUITE(TestCommonRNG) {
+    template <class T>
+    struct TRng: public TCommonRNG<T, TRng<T>> {
+        inline T GenRand() noexcept {
+            return IntHash(C_++);
+        }
+
+        T C_ = RandomNumber<T>();
+    };
+
+    Y_UNIT_TEST(TestUniform1) {
+        TRng<ui32> r;
+
+        for (size_t i = 0; i < 1000; ++i) {
+            UNIT_ASSERT(r.Uniform(10) < 10);
+        }
+    }
+
+    Y_UNIT_TEST(TestUniform2) {
+        TRng<ui32> r;
+
+        for (size_t i = 0; i < 1000; ++i) {
+            UNIT_ASSERT(r.Uniform(1) == 0);
+        }
+    }
+
+    Y_UNIT_TEST(TestUniform3) {
+        TRng<ui32> r;
+
+        for (size_t i = 0; i < 1000; ++i) {
+            auto x = r.Uniform(100, 200);
+
+            UNIT_ASSERT(x >= 100);
+            UNIT_ASSERT(x < 200);
+        }
+    }
+
+    Y_UNIT_TEST(TestStlCompatibility) {
+        {
+            TRng<ui32> r;
+            r.C_ = 17;
+            std::normal_distribution<float> nd(0, 1);
+            UNIT_ASSERT_DOUBLES_EQUAL(nd(r), -0.877167, 0.01);
+        }
+
+        {
+            TRng<ui64> r;
+            r.C_ = 17;
+            std::normal_distribution<double> nd(0, 1);
+            UNIT_ASSERT_DOUBLES_EQUAL(nd(r), -0.5615566731, 0.01);
+        }
+
+        {
+            TRng<ui16> r;
+            r.C_ = 17;
+            std::normal_distribution<long double> nd(0, 1);
+            UNIT_ASSERT_DOUBLES_EQUAL(nd(r), -0.430375088, 0.01);
+        }
+    }
+}
diff --git a/util/random/easy.cpp b/util/random/easy.cpp
new file mode 100644
index 0000000000..a92f4e9017
--- /dev/null
+++ b/util/random/easy.cpp
@@ -0,0 +1 @@
+#include "easy.h"
diff --git a/util/random/easy.h b/util/random/easy.h
new file mode 100644
index 0000000000..fd5b826fbe
--- /dev/null
+++ b/util/random/easy.h
@@ -0,0 +1,47 @@
+#pragma once
+
+#include "random.h"
+
+namespace NPrivate {
+    struct TRandom {
+        inline operator unsigned char() {
+            return RandomNumber<unsigned char>();
+        }
+
+        inline operator unsigned short() {
+            return RandomNumber<unsigned short>();
+        }
+
+        inline operator unsigned int() {
+            return RandomNumber<unsigned int>();
+        }
+
+        inline operator unsigned long() {
+            return RandomNumber<unsigned long>();
+        }
+
+        inline operator unsigned long long() {
+            return RandomNumber<unsigned long long>();
+        }
+
+        inline operator bool() {
+            return RandomNumber<bool>();
+        }
+
+        inline operator float() {
+            return RandomNumber<float>();
+        }
+
+        inline operator double() {
+            return RandomNumber<double>();
+        }
+
+        inline operator long double() {
+            return RandomNumber<long double>();
+        }
+    };
+}
+
+static inline ::NPrivate::TRandom Random() noexcept {
+    return {};
+}
diff --git a/util/random/easy_ut.cpp b/util/random/easy_ut.cpp
new file mode 100644
index 0000000000..d1d024a91f
--- /dev/null
+++ b/util/random/easy_ut.cpp
@@ -0,0 +1,35 @@
+#include "easy.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+Y_UNIT_TEST_SUITE(TEasyRndInterface) {
+    Y_UNIT_TEST(Test1) {
+        {
+            ui32 x = 0;
+
+            x = Random();
+
+            if (!x) {
+                x = Random();
+            }
+
+            UNIT_ASSERT(x != 0);
+        }
+
+        {
+            ui64 x = 0;
+
+            x = Random();
+
+            UNIT_ASSERT(x != 0);
+        }
+
+        {
+            long double x = 0;
+
+            x = Random();
+
+            UNIT_ASSERT(x != 0);
+        }
+    }
+}
diff --git a/util/random/entropy.cpp b/util/random/entropy.cpp
new file mode 100644
index 0000000000..3617edb83d
--- /dev/null
+++ b/util/random/entropy.cpp
@@ -0,0 +1,221 @@
+#include "fast.h"
+#include "random.h"
+#include "entropy.h"
+#include "mersenne.h"
+#include "shuffle.h"
+#include "init_atfork.h"
+
+#include <util/stream/output.h>
+#include <util/stream/mem.h>
+#include <util/stream/zlib.h>
+#include <util/stream/buffer.h>
+
+#include <util/system/fs.h>
+#include <util/system/info.h>
+#include <util/system/spinlock.h>
+#include <util/system/thread.h>
+#include <util/system/execpath.h>
+#include <util/system/datetime.h>
+#include <util/system/hostname.h>
+#include <util/system/getpid.h>
+#include <util/system/mem_info.h>
+#include <util/system/rusage.h>
+#include <util/system/cpu_id.h>
+#include <util/system/unaligned_mem.h>
+
+#include <util/generic/buffer.h>
+#include <util/generic/singleton.h>
+
+#include <util/digest/murmur.h>
+#include <util/digest/city.h>
+
+#include <util/ysaveload.h>
+
+namespace {
+    inline void Permute(char* buf, size_t len, ui32 seed) noexcept {
+        Shuffle(buf, buf + len, TReallyFastRng32(seed));
+    }
+
+    struct THostEntropy: public TBuffer {
+        inline THostEntropy() {
+            {
+                TBufferOutput buf(*this);
+                TZLibCompress out(&buf);
+
+                Save(&out, GetPID());
+                Save(&out, GetCycleCount());
+                Save(&out, MicroSeconds());
+                Save(&out, TThread::CurrentThreadId());
+                Save(&out, NSystemInfo::CachedNumberOfCpus());
+                Save(&out, NSystemInfo::TotalMemorySize());
+                Save(&out, HostName());
+
+                try {
+                    Save(&out, GetExecPath());
+                } catch (...) {
+                    //workaround - sometimes fails on FreeBSD
+                }
+
+                Save(&out, (size_t)Data());
+                Save(&out, (size_t)&buf);
+
+                {
+                    double la[3];
+
+                    NSystemInfo::LoadAverage(la, Y_ARRAY_SIZE(la));
+
+                    out.Write(la, sizeof(la));
+                }
+
+                {
+                    auto mi = NMemInfo::GetMemInfo();
+
+                    out.Write(&mi, sizeof(mi));
+                }
+
+                {
+                    auto ru = TRusage::Get();
+
+                    out.Write(&ru, sizeof(ru));
+                }
+
+                {
+                    ui32 store[12];
+
+                    out << TStringBuf(CpuBrand(store));
+                }
+
+                out << NFs::CurrentWorkingDirectory();
+
+                out.Finish();
+            }
+
+            {
+                TMemoryOutput out(Data(), Size());
+
+                //replace zlib header with hash
+                Save(&out, CityHash64(Data(), Size()));
+            }
+
+            Permute(Data(), Size(), MurmurHash<ui32>(Data(), Size()));
+        }
+    };
+
+    //not thread-safe
+    class TMersenneInput: public IInputStream {
+        using TKey = ui64;
+        using TRnd = TMersenne<TKey>;
+
+    public:
+        inline explicit TMersenneInput(const TBuffer& rnd)
+            : Rnd_((const TKey*)rnd.Data(), rnd.Size() / sizeof(TKey))
+        {
+        }
+
+        ~TMersenneInput() override = default;
+
+        size_t DoRead(void* buf, size_t len) override {
+            size_t toRead = len;
+
+            while (toRead) {
+                const TKey next = Rnd_.GenRand();
+                const size_t toCopy = Min(toRead, sizeof(next));
+
+                memcpy(buf, &next, toCopy);
+
+                buf = (char*)buf + toCopy;
+                toRead -= toCopy;
+            }
+
+            return len;
+        }
+
+    private:
+        TRnd Rnd_;
+    };
+
+    class TEntropyPoolStream: public IInputStream {
+    public:
+        inline explicit TEntropyPoolStream(const TBuffer& buffer)
+            : Mi_(buffer)
+            , Bi_(&Mi_, 8192)
+        {
+        }
+
+        size_t DoRead(void* buf, size_t len) override {
+            auto guard = Guard(Mutex_);
+
+            return Bi_.Read(buf, len);
+        }
+
+    private:
+        TAdaptiveLock Mutex_;
+        TMersenneInput Mi_;
+        TBufferedInput Bi_;
+    };
+
+    struct TSeedStream: public IInputStream {
+        size_t DoRead(void* inbuf, size_t len) override {
+            char* buf = (char*)inbuf;
+
+#define DO_STEP(type)                                    \
+    while (len >= sizeof(type)) {                        \
+        WriteUnaligned<type>(buf, RandomNumber<type>()); \
+        buf += sizeof(type);                             \
+        len -= sizeof(type);                             \
+    }
+
+            DO_STEP(ui64);
+            DO_STEP(ui32);
+            DO_STEP(ui16);
+            DO_STEP(ui8);
+
+#undef DO_STEP
+
+            return buf - (char*)inbuf;
+        }
+    };
+
+    struct TDefaultTraits {
+        THolder<TEntropyPoolStream> EP;
+        TSeedStream SS;
+
+        inline TDefaultTraits() {
+            Reset();
+        }
+
+        inline IInputStream& EntropyPool() noexcept {
+            return *EP;
+        }
+
+        inline IInputStream& Seed() noexcept {
+            return SS;
+        }
+
+        inline void Reset() noexcept {
+            EP.Reset(new TEntropyPoolStream(THostEntropy()));
+        }
+
+        static inline TDefaultTraits& Instance() {
+            auto res = SingletonWithPriority<TDefaultTraits, 0>();
+
+            RNGInitAtForkHandlers();
+
+            return *res;
+        }
+    };
+
+    using TRandomTraits = TDefaultTraits;
+}
+
+IInputStream& EntropyPool() {
+    return TRandomTraits::Instance().EntropyPool();
+}
+
+IInputStream& Seed() {
+    return TRandomTraits::Instance().Seed();
+}
+
+void ResetEntropyPool() {
+    TRandomTraits::Instance().Reset();
+}
diff --git a/util/random/entropy.h b/util/random/entropy.h
new file mode 100644
index 0000000000..62029c1b63
--- /dev/null
+++ b/util/random/entropy.h
@@ -0,0 +1,21 @@
+#pragma once
+
+class TBuffer;
+class IInputStream;
+
+/*
+ * fast entropy pool, based on good prng, can lock for some time
+ * initialized with some bits from system entropy pool
+ * think as /dev/urandom replacement
+ */
+IInputStream& EntropyPool();
+
+/*
+ * fast(non-blocking) entropy pool, useful for seeding PRNGs
+ */
+IInputStream& Seed();
+
+/*
+ * Re-initialize entropy pool - useful after forking in multi-process programs.
+ */
+void ResetEntropyPool();
diff --git a/util/random/entropy_ut.cpp b/util/random/entropy_ut.cpp
new file mode 100644
index 0000000000..1ff27203f0
--- /dev/null
+++ b/util/random/entropy_ut.cpp
@@ -0,0 +1,13 @@
+#include "entropy.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+Y_UNIT_TEST_SUITE(TestEntropy) {
+    Y_UNIT_TEST(TestSeed) {
+        char buf[100];
+
+        for (size_t i = 0; i < sizeof(buf); ++i) {
+            Seed().LoadOrFail(buf, i);
+        }
+    }
+}
diff --git a/util/random/fast.cpp b/util/random/fast.cpp
new file mode 100644
index 0000000000..2f98dfc5d3
--- /dev/null
+++ b/util/random/fast.cpp
@@ -0,0 +1,52 @@
+#include "fast.h"
+
+#include <util/stream/input.h>
+
+static inline ui32 FixSeq(ui32 seq1, ui32 seq2) noexcept {
+    const ui32 mask = (~(ui32)(0)) >> 1;
+
+    if ((seq1 & mask) == (seq2 & mask)) {
+        return ~seq2;
+    }
+
+    return seq2;
+}
+
+TFastRng64::TFastRng64(ui64 seed1, ui32 seq1, ui64 seed2, ui32 seq2) noexcept
+    : R1_(seed1, seq1)
+    , R2_(seed2, FixSeq(seq1, seq2))
+{
+}
+
+TFastRng64::TArgs::TArgs(ui64 seed) noexcept {
+    TReallyFastRng32 rng(seed);
+
+    Seed1 = rng.GenRand64();
+    Seq1 = rng.GenRand();
+    Seed2 = rng.GenRand64();
+    Seq2 = rng.GenRand();
+}
+
+TFastRng64::TArgs::TArgs(IInputStream& entropy) {
+    static_assert(sizeof(*this) == 3 * sizeof(ui64), "please, fix me");
+    entropy.LoadOrFail(this, sizeof(*this));
+}
+
+template <class T>
+static inline T Read(IInputStream& in) noexcept {
+    T t = T();
+
+    in.LoadOrFail(&t, sizeof(t));
+
+    return t;
+}
+
+TFastRng32::TFastRng32(IInputStream& entropy)
+    : TFastRng32(Read<ui64>(entropy), Read<ui32>(entropy))
+{
+}
+
+TReallyFastRng32::TReallyFastRng32(IInputStream& entropy)
+    : TReallyFastRng32(Read<ui64>(entropy))
+{
+}
diff --git a/util/random/fast.h b/util/random/fast.h
new file mode 100644
index 0000000000..ddc5711641
--- /dev/null
+++ b/util/random/fast.h
@@ -0,0 +1,101 @@
+#pragma once
+
+#include "lcg_engine.h"
+#include "common_ops.h"
+
+#include <util/generic/bitops.h>
+#include <util/system/platform.h>
+
+// based on http://www.pcg-random.org/. See T*FastRng* family below.
+
+struct TPCGMixer {
+    static inline ui32 Mix(ui64 x) noexcept {
+        const ui32 xorshifted = ((x >> 18u) ^ x) >> 27u;
+        const ui32 rot = x >> 59u;
+
+        return RotateBitsRight(xorshifted, rot);
+    }
+};
+
+using TFastRng32Base = TLcgRngBase<TLcgIterator<ui64, ULL(6364136223846793005)>, TPCGMixer>;
+using TReallyFastRng32Base = TLcgRngBase<TFastLcgIterator<ui64, ULL(6364136223846793005), ULL(1)>, TPCGMixer>;
+
+class IInputStream;
+
+struct TFastRng32: public TCommonRNG<ui32, TFastRng32>, public TFastRng32Base {
+    inline TFastRng32(ui64 seed, ui32 seq)
+        : TFastRng32Base(seed, seq)
+    {
+    }
+
+    TFastRng32(IInputStream& entropy);
+};
+
+// faster than TFastRng32, but have only one possible stream sequence
+struct TReallyFastRng32: public TCommonRNG<ui32, TReallyFastRng32>, public TReallyFastRng32Base {
+    inline TReallyFastRng32(ui64 seed)
+        : TReallyFastRng32Base(seed)
+    {
+    }
+
+    TReallyFastRng32(IInputStream& entropy);
+};
+
+class TFastRng64: public TCommonRNG<ui64, TFastRng64> {
+public:
+    struct TArgs {
+        TArgs(ui64 seed) noexcept;
+        TArgs(IInputStream& entropy);
+
+        ui64 Seed1;
+        ui64 Seed2;
+        ui32 Seq1;
+        ui32 Seq2;
+    };
+
+    TFastRng64(ui64 seed1, ui32 seq1, ui64 seed2, ui32 seq2) noexcept;
+
+    /*
+     * simplify constructions like
+     *     TFastRng64 rng(17);
+     *     TFastRng64 rng(Seek()); //from any IInputStream
+     */
+    inline TFastRng64(const TArgs& args) noexcept
+        : TFastRng64(args.Seed1, args.Seq1, args.Seed2, args.Seq2)
+    {
+    }
+
+    inline ui64 GenRand() noexcept {
+        const ui64 x = R1_.GenRand();
+        const ui64 y = R2_.GenRand();
+
+        return (x << 32) | y;
+    }
+
+    inline void Advance(ui64 delta) noexcept {
+        R1_.Advance(delta);
+        R2_.Advance(delta);
+    }
+
+private:
+    TFastRng32Base R1_;
+    TFastRng32Base R2_;
+};
+
+namespace NPrivate {
+    template <typename T>
+    struct TFastRngTraits;
+
+    template <>
+    struct TFastRngTraits<ui32> {
+        using TResult = TReallyFastRng32;
+    };
+
+    template <>
+    struct TFastRngTraits<ui64> {
+        using TResult = TFastRng64;
+    };
+}
+
+template <typename T>
+using TFastRng = typename ::NPrivate::TFastRngTraits<T>::TResult;
diff --git a/util/random/fast_ut.cpp b/util/random/fast_ut.cpp
new file mode 100644
index 0000000000..60994a98b0
--- /dev/null
+++ b/util/random/fast_ut.cpp
@@ -0,0 +1,119 @@
+#include "fast.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+Y_UNIT_TEST_SUITE(TTestFastRng) {
+    Y_UNIT_TEST(Test1) {
+        TFastRng32 rng1(17, 0);
+        TReallyFastRng32 rng2(17);
+
+        for (size_t i = 0; i < 1000; ++i) {
+            UNIT_ASSERT_VALUES_EQUAL(rng1.GenRand(), rng2.GenRand());
+        }
+    }
+
+    static ui64 R1[] = {
+        37,
+        43,
+        76,
+        17,
+        12,
+        87,
+        60,
+        4,
+        83,
+        47,
+        57,
+        81,
+        28,
+        45,
+        66,
+        74,
+        18,
+        17,
+        18,
+        75,
+    };
+
+    Y_UNIT_TEST(Test2) {
+        TFastRng64 rng(0, 1, 2, 3);
+
+        for (auto& i : R1) {
+            UNIT_ASSERT_VALUES_EQUAL(rng.Uniform(100u), i);
+        }
+    }
+
+    Y_UNIT_TEST(TestAdvance) {
+        TReallyFastRng32 rng1(17);
+        TReallyFastRng32 rng2(17);
+        for (size_t i = 0; i < 100; i++) {
+            rng1.GenRand();
+        }
+        rng2.Advance(100);
+        UNIT_ASSERT_VALUES_EQUAL(rng1.GenRand(), rng2.GenRand());
+
+        TFastRng64 rng3(0, 1, 2, 3);
+        TFastRng64 rng4(0, 1, 2, 3);
+        for (size_t i = 0; i < 100; i++) {
+            rng3.GenRand();
+        }
+        rng4.Advance(100);
+        UNIT_ASSERT_VALUES_EQUAL(rng3.GenRand(), rng4.GenRand());
+    }
+
+    Y_UNIT_TEST(TestAdvanceBoundaries) {
+        TReallyFastRng32 rng1(17);
+        TReallyFastRng32 rng2(17);
+        TReallyFastRng32 rng3(17);
+        rng2.Advance(0);
+        rng3.Advance(1);
+        UNIT_ASSERT_VALUES_EQUAL(rng1.GenRand(), rng2.GenRand());
+        UNIT_ASSERT_VALUES_EQUAL(rng1.GenRand(), rng3.GenRand());
+    }
+
+    Y_UNIT_TEST(TestCopy) {
+        TReallyFastRng32 r1(1);
+        TReallyFastRng32 r2(2);
+
+        UNIT_ASSERT_VALUES_UNEQUAL(r1.GenRand(), r2.GenRand());
+
+        r2 = r1;
+
+        UNIT_ASSERT_VALUES_EQUAL(r1.GenRand(), r2.GenRand());
+    }
+
+    Y_UNIT_TEST(Test3) {
+        TFastRng64 rng(17);
+
+        UNIT_ASSERT_VALUES_EQUAL(rng.GenRand(), ULL(14895365814383052362));
+    }
+
+    Y_UNIT_TEST(TestCompile) {
+        TFastRng<ui32> rng1(1);
+        TFastRng<ui64> rng2(2);
+        TFastRng<size_t> rng3(3);
+
+        rng1.GenRand();
+        rng2.GenRand();
+        rng3.GenRand();
+    }
+
+    const char* RNG_DATA = "At the top of the department store I,"
+                           "I bought a fur coat with fur I"
+                           "But apparently I made a blunder here -"
+                           "Doha does not warm ... Absolutely.";
+
+    Y_UNIT_TEST(TestStreamCtor1) {
+        TMemoryInput mi(RNG_DATA, strlen(RNG_DATA));
+        TFastRng<ui32> rng(mi);
+
+        UNIT_ASSERT_VALUES_EQUAL(rng.GenRand(), 1449109131u);
+    }
+
+    Y_UNIT_TEST(TestStreamCtor2) {
+        TMemoryInput mi(RNG_DATA, strlen(RNG_DATA));
+        TFastRng<ui64> rng(mi);
+
+        UNIT_ASSERT_VALUES_EQUAL(rng.GenRand(), ULL(6223876579076085114));
+    }
+}
diff --git a/util/random/init_atfork.cpp b/util/random/init_atfork.cpp
new file mode 100644
index 0000000000..0faa3d119a
--- /dev/null
+++ b/util/random/init_atfork.cpp
@@ -0,0 +1,30 @@
+#include "init_atfork.h"
+#include "random.h"
+#include "entropy.h"
+
+#include <util/generic/singleton.h>
+#include <util/system/yassert.h>
+
+#if defined(_unix_)
+    #include <pthread.h>
+#endif
+
+namespace {
+    struct TInit {
+        inline TInit() noexcept {
+            (void)&AtFork;
+
+#if defined(_unix_)
+            Y_VERIFY(pthread_atfork(nullptr, AtFork, nullptr) == 0, "it happens");
+#endif
+        }
+
+        static void AtFork() noexcept {
+            ResetRandomState();
+        }
+    };
+}
+
+void RNGInitAtForkHandlers() {
+    SingletonWithPriority<TInit, 0>();
+}
diff --git a/util/random/init_atfork.h b/util/random/init_atfork.h
new file mode 100644
index 0000000000..be3506b4a0
--- /dev/null
+++ b/util/random/init_atfork.h
@@ -0,0 +1,3 @@
+#pragma once
+
+void RNGInitAtForkHandlers();
diff --git a/util/random/lcg_engine.cpp b/util/random/lcg_engine.cpp
new file mode 100644
index 0000000000..e1469104fa
--- /dev/null
+++ b/util/random/lcg_engine.cpp
@@ -0,0 +1,30 @@
+#include "lcg_engine.h"
+
+namespace NPrivate {
+    template <typename T>
+    T LcgAdvance(T seed, T lcgBase, T lcgAddend, T delta) noexcept {
+        // seed[n+1] = A * seed[n] + B, A = lcgBase, B = lcgAddend
+        // seed[n] = A**n * seed[0] + (A**n - 1) / (A - 1) * B
+        // (initial value of n) = m * 2**k + (lower bits of n)
+        T mask = 1;
+        while (mask != (1ULL << (8 * sizeof(T) - 1)) && (mask << 1) <= delta) {
+            mask <<= 1;
+        }
+        T apow = 1; // A**m
+        T adiv = 0; // (A**m-1)/(A-1)
+        for (; mask; mask >>= 1) {
+            // m *= 2
+            adiv *= apow + 1;
+            apow *= apow;
+            if (delta & mask) {
+                // m++
+                adiv += apow;
+                apow *= lcgBase;
+            }
+        }
+        return seed * apow + lcgAddend * adiv;
+    }
+
+    template ui32 LcgAdvance<ui32>(ui32, ui32, ui32, ui32) noexcept;
+    template ui64 LcgAdvance<ui64>(ui64, ui64, ui64, ui64) noexcept;
+}
diff --git a/util/random/lcg_engine.h b/util/random/lcg_engine.h
new file mode 100644
index 0000000000..08cc93c845
--- /dev/null
+++ b/util/random/lcg_engine.h
@@ -0,0 +1,66 @@
+#pragma once
+
+#include <utility>
+#include <util/generic/typetraits.h>
+
+// common engine for lcg-based RNG's
+// http://en.wikipedia.org/wiki/Linear_congruential_generator
+
+namespace NPrivate {
+    template <typename T>
+    T LcgAdvance(T seed, T lcgBase, T lcgAddend, T delta) noexcept;
+};
+
+template <typename T, T A, T C>
+struct TFastLcgIterator {
+    static_assert(C % 2 == 1, "C must be odd");
+
+    static constexpr T Iterate(T x) noexcept {
+        return x * A + C;
+    }
+
+    static inline T IterateMultiple(T x, T delta) noexcept {
+        return ::NPrivate::LcgAdvance(x, A, C, delta);
+    }
+};
+
+template <typename T, T A>
+struct TLcgIterator {
+    inline TLcgIterator(T seq) noexcept
+        : C((seq << 1u) | (T)1) // C must be odd
+    {
+    }
+
+    inline T Iterate(T x) noexcept {
+        return x * A + C;
+    }
+
+    inline T IterateMultiple(T x, T delta) noexcept {
+        return ::NPrivate::LcgAdvance(x, A, C, delta);
+    }
+
+    const T C;
+};
+
+template <class TIterator, class TMixer>
+struct TLcgRngBase: public TIterator, public TMixer {
+    using TStateType = decltype(std::declval<TIterator>().Iterate(0));
+    using TResultType = decltype(std::declval<TMixer>().Mix(TStateType()));
+
+    template <typename... Args>
+    inline TLcgRngBase(TStateType seed, Args&&... args)
+        : TIterator(std::forward<Args>(args)...)
+        , X(seed)
+    {
+    }
+
+    inline TResultType GenRand() noexcept {
+        return this->Mix(X = this->Iterate(X));
+    }
+
+    inline void Advance(TStateType delta) noexcept {
+        X = this->IterateMultiple(X, delta);
+    }
+
+    TStateType X;
+};
diff --git a/util/random/mersenne.cpp b/util/random/mersenne.cpp
new file mode 100644
index 0000000000..59779c1ec1
--- /dev/null
+++ b/util/random/mersenne.cpp
@@ -0,0 +1 @@
+#include "mersenne.h"
diff --git a/util/random/mersenne.h b/util/random/mersenne.h
new file mode 100644
index 0000000000..b2044604ac
--- /dev/null
+++ b/util/random/mersenne.h
@@ -0,0 +1,46 @@
+#pragma once
+
+#include "mersenne64.h"
+#include "mersenne32.h"
+#include "common_ops.h"
+
+namespace NPrivate {
+    template <class T>
+    struct TMersenneTraits;
+
+    template <>
+    struct TMersenneTraits<ui64> {
+        using TImpl = TMersenne64;
+    };
+
+    template <>
+    struct TMersenneTraits<ui32> {
+        using TImpl = TMersenne32;
+    };
+}
+
+class IInputStream;
+
+template <class T>
+class TMersenne: public TCommonRNG<T, TMersenne<T>>, public ::NPrivate::TMersenneTraits<T>::TImpl {
+public:
+    using TBase = typename ::NPrivate::TMersenneTraits<T>::TImpl;
+
+    inline TMersenne() noexcept {
+    }
+
+    inline TMersenne(T seed) noexcept
+        : TBase(seed)
+    {
+    }
+
+    inline TMersenne(IInputStream& pool)
+        : TBase(pool)
+    {
+    }
+
+    inline TMersenne(const T* keys, size_t len) noexcept
+        : TBase(keys, len)
+    {
+    }
+};
diff --git a/util/random/mersenne32.cpp b/util/random/mersenne32.cpp
new file mode 100644
index 0000000000..cb8aad8b03
--- /dev/null
+++ b/util/random/mersenne32.cpp
@@ -0,0 +1,98 @@
+#include "mersenne32.h"
+
+#include <util/generic/array_size.h>
+#include <util/stream/input.h>
+
+using namespace NPrivate;
+
+#define M 397
+#define MATRIX_A 0x9908b0dfUL
+#define UPPER_MASK 0x80000000UL
+#define LOWER_MASK 0x7fffffffUL
+
+void TMersenne32::InitGenRand(ui32 s) noexcept {
+    mt[0] = s;
+
+    for (mti = 1; mti < N; ++mti) {
+        mt[mti] = (1812433253UL * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti);
+    }
+}
+
+void TMersenne32::InitByArray(const ui32 init_key[], size_t key_length) noexcept {
+    InitGenRand(19650218UL);
+
+    ui32 i = 1;
+    ui32 j = 0;
+    ui32 k = ui32(N > key_length ? N : key_length);
+
+    for (; k; k--) {
+        mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525UL)) + init_key[j] + j;
+
+        ++i;
+        ++j;
+
+        if (i >= N) {
+            mt[0] = mt[N - 1];
+            i = 1;
+        }
+
+        if (j >= key_length) {
+            j = 0;
+        }
+    }
+
+    for (k = N - 1; k; k--) {
+        mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941UL)) - i;
+
+        ++i;
+
+        if (i >= N) {
+            mt[0] = mt[N - 1];
+            i = 1;
+        }
+    }
+
+    mt[0] = 0x80000000UL;
+}
+
+void TMersenne32::InitNext() noexcept {
+    int kk;
+    ui32 y;
+    ui32 mag01[2] = {
+        0x0UL,
+        MATRIX_A,
+    };
+
+    if (mti == N + 1) {
+        InitGenRand(5489UL);
+    }
+
+    for (kk = 0; kk < N - M; ++kk) {
+        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
+        mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1UL];
+    }
+
+    for (; kk < N - 1; ++kk) {
+        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
+        mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
+    }
+
+    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
+    mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1UL];
+
+    mti = 0;
+}
+
+TMersenne32::TMersenne32(IInputStream& input)
+    : mti(N + 1)
+{
+    ui32 buf[128];
+
+    input.LoadOrFail(buf, sizeof(buf));
+    InitByArray(buf, Y_ARRAY_SIZE(buf));
+}
+
+#undef M
+#undef MATRIX_A
+#undef UPPER_MASK
+#undef LOWER_MASK
diff --git a/util/random/mersenne32.h b/util/random/mersenne32.h
new file mode 100644
index 0000000000..861f3a3d38
--- /dev/null
+++ b/util/random/mersenne32.h
@@ -0,0 +1,50 @@
+#pragma once
+
+#include <util/system/defaults.h>
+
+class IInputStream;
+
+namespace NPrivate {
+    class TMersenne32 {
+        static constexpr int N = 624;
+
+    public:
+        inline TMersenne32(ui32 s = 19650218UL) noexcept
+            : mti(N + 1)
+        {
+            InitGenRand(s);
+        }
+
+        inline TMersenne32(const ui32* init_key, size_t key_length) noexcept
+            : mti(N + 1)
+        {
+            InitByArray(init_key, key_length);
+        }
+
+        TMersenne32(IInputStream& input);
+
+        inline ui32 GenRand() noexcept {
+            if (mti >= N) {
+                InitNext();
+            }
+
+            ui32 y = mt[mti++];
+
+            y ^= (y >> 11);
+            y ^= (y << 7) & 0x9d2c5680UL;
+            y ^= (y << 15) & 0xefc60000UL;
+            y ^= (y >> 18);
+
+            return y;
+        }
+
+    private:
+        void InitNext() noexcept;
+        void InitGenRand(ui32 s) noexcept;
+        void InitByArray(const ui32* init_key, size_t key_length) noexcept;
+
+    private:
+        ui32 mt[N];
+        int mti;
+    };
+}
diff --git a/util/random/mersenne64.cpp b/util/random/mersenne64.cpp
new file mode 100644
index 0000000000..4ede2c6dca
--- /dev/null
+++ b/util/random/mersenne64.cpp
@@ -0,0 +1,100 @@
+#include "mersenne64.h"
+
+#include <util/generic/array_size.h>
+#include <util/stream/input.h>
+
+#define MM 156
+#define MATRIX_A ULL(0xB5026F5AA96619E9)
+#define UM ULL(0xFFFFFFFF80000000)
+#define LM ULL(0x7FFFFFFF)
+
+using namespace NPrivate;
+
+void TMersenne64::InitGenRand(ui64 seed) noexcept {
+    mt[0] = seed;
+
+    for (mti = 1; mti < NN; ++mti) {
+        mt[mti] = (ULL(6364136223846793005) * (mt[mti - 1] ^ (mt[mti - 1] >> 62)) + mti);
+    }
+}
+
+void TMersenne64::InitByArray(const ui64* init_key, size_t key_length) noexcept {
+    ui64 i = 1;
+    ui64 j = 0;
+    ui64 k;
+
+    InitGenRand(ULL(19650218));
+
+    k = NN > key_length ? NN : key_length;
+
+    for (; k; --k) {
+        mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 62)) * ULL(3935559000370003845))) + init_key[j] + j;
+
+        ++i;
+        ++j;
+
+        if (i >= NN) {
+            mt[0] = mt[NN - 1];
+            i = 1;
+        }
+
+        if (j >= key_length) {
+            j = 0;
+        }
+    }
+
+    for (k = NN - 1; k; --k) {
+        mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 62)) * ULL(2862933555777941757))) - i;
+
+        ++i;
+
+        if (i >= NN) {
+            mt[0] = mt[NN - 1];
+            i = 1;
+        }
+    }
+
+    mt[0] = ULL(1) << 63;
+}
+
+void TMersenne64::InitNext() noexcept {
+    int i;
+    ui64 x;
+    ui64 mag01[2] = {
+        ULL(0),
+        MATRIX_A,
+    };
+
+    if (mti == NN + 1) {
+        InitGenRand(ULL(5489));
+    }
+
+    for (i = 0; i < NN - MM; ++i) {
+        x = (mt[i] & UM) | (mt[i + 1] & LM);
+        mt[i] = mt[i + MM] ^ (x >> 1) ^ mag01[(int)(x & ULL(1))];
+    }
+
+    for (; i < NN - 1; ++i) {
+        x = (mt[i] & UM) | (mt[i + 1] & LM);
+        mt[i] = mt[i + (MM - NN)] ^ (x >> 1) ^ mag01[(int)(x & ULL(1))];
+    }
+
+    x = (mt[NN - 1] & UM) | (mt[0] & LM);
+    mt[NN - 1] = mt[MM - 1] ^ (x >> 1) ^ mag01[(int)(x & ULL(1))];
+
+    mti = 0;
+}
+
+TMersenne64::TMersenne64(IInputStream& input)
+    : mti(NN + 1)
+{
+    ui64 buf[128];
+
+    input.LoadOrFail(buf, sizeof(buf));
+    InitByArray(buf, Y_ARRAY_SIZE(buf));
+}
+
+#undef MM
+#undef MATRIX_A
+#undef UM
+#undef LM
diff --git a/util/random/mersenne64.h b/util/random/mersenne64.h
new file mode 100644
index 0000000000..12ca43b6af
--- /dev/null
+++ b/util/random/mersenne64.h
@@ -0,0 +1,50 @@
+#pragma once
+
+#include <util/system/defaults.h>
+
+class IInputStream;
+
+namespace NPrivate {
+    class TMersenne64 {
+        static constexpr int NN = 312;
+
+    public:
+        inline TMersenne64(ui64 s = ULL(19650218))
+            : mti(NN + 1)
+        {
+            InitGenRand(s);
+        }
+
+        inline TMersenne64(const ui64* keys, size_t len) noexcept
+            : mti(NN + 1)
+        {
+            InitByArray(keys, len);
+        }
+
+        TMersenne64(IInputStream& input);
+
+        inline ui64 GenRand() noexcept {
+            if (mti >= NN) {
+                InitNext();
+            }
+
+            ui64 x = mt[mti++];
+
+            x ^= (x >> 29) & ULL(0x5555555555555555);
+            x ^= (x << 17) & ULL(0x71D67FFFEDA60000);
+            x ^= (x << 37) & ULL(0xFFF7EEE000000000);
+            x ^= (x >> 43);
+
+            return x;
+        }
+
+    private:
+        void InitNext() noexcept;
+        void InitGenRand(ui64 seed) noexcept;
+        void InitByArray(const ui64* init_key, size_t key_length) noexcept;
+
+    private:
+        ui64 mt[NN];
+        int mti;
+    };
+}
diff --git a/util/random/mersenne_ut.cpp b/util/random/mersenne_ut.cpp
new file mode 100644
index 0000000000..a4b84efa3d
--- /dev/null
+++ b/util/random/mersenne_ut.cpp
@@ -0,0 +1,82 @@
+#include "mersenne.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/stream/output.h>
+
+#define UI32(x) x##ul
+
+Y_UNIT_TEST_SUITE(TMersenneRndTest) {
+    template <class T>
+    inline void Test(const T* res, size_t len) {
+        TMersenne<T> m;
+
+        for (size_t i = 0; i < len; ++i) {
+            UNIT_ASSERT_EQUAL(m.GenRand(), res[i]);
+        }
+    }
+
+    Y_UNIT_TEST(Test32) {
+        const ui32 res[] = {
+            UI32(2325592414),
+            UI32(482149846),
+            UI32(4177211283),
+            UI32(3872387439),
+            UI32(1663027210),
+            UI32(2005191859),
+            UI32(666881213),
+            UI32(3289399202),
+            UI32(2514534568),
+            UI32(3882134983),
+        };
+
+        Test<ui32>(res, Y_ARRAY_SIZE(res));
+    }
+
+    Y_UNIT_TEST(Test64) {
+        const ui64 res[] = {
+            ULL(13735441942630277712),
+            ULL(10468394322237346228),
+            ULL(5051557175812687784),
+            ULL(8252857936377966838),
+            ULL(4330799099585512958),
+            ULL(327094098846779408),
+            ULL(6143667654738189122),
+            ULL(6387112078486713335),
+            ULL(3862502196831460488),
+            ULL(11231499428520958715),
+        };
+
+        Test<ui64>(res, Y_ARRAY_SIZE(res));
+    }
+
+    Y_UNIT_TEST(TestGenRand64) {
+        TMersenne<ui32> rng;
+
+        for (size_t i = 0; i < 100; ++i) {
+            UNIT_ASSERT(rng.GenRand64() > ULL(12345678912));
+        }
+    }
+
+    Y_UNIT_TEST(TestCopy32) {
+        TMersenne<ui32> r1(1);
+        TMersenne<ui32> r2(2);
+
+        UNIT_ASSERT_VALUES_UNEQUAL(r1.GenRand(), r2.GenRand());
+
+        r2 = r1;
+
+        UNIT_ASSERT_VALUES_EQUAL(r1.GenRand(), r2.GenRand());
+    }
+
+    Y_UNIT_TEST(TestCopy64) {
+        TMersenne<ui64> r1(1);
+        TMersenne<ui64> r2(2);
+
+        UNIT_ASSERT_VALUES_UNEQUAL(r1.GenRand(), r2.GenRand());
+
+        r2 = r1;
+
+        UNIT_ASSERT_VALUES_EQUAL(r1.GenRand(), r2.GenRand());
+    }
+}
diff --git a/util/random/normal.cpp b/util/random/normal.cpp
new file mode 100644
index 0000000000..478b38fd25
--- /dev/null
+++ b/util/random/normal.cpp
@@ -0,0 +1,27 @@
+#include "normal.h"
+#include "common_ops.h"
+#include "random.h"
+
+namespace {
+    template <class T>
+    struct TSysRNG: public TCommonRNG<T, TSysRNG<T>> {
+        inline T GenRand() noexcept {
+            return RandomNumber<T>();
+        }
+    };
+}
+
+template <>
+float StdNormalRandom<float>() noexcept {
+    return StdNormalDistribution<float>(TSysRNG<ui64>());
+}
+
+template <>
+double StdNormalRandom<double>() noexcept {
+    return StdNormalDistribution<double>(TSysRNG<ui64>());
+}
+
+template <>
+long double StdNormalRandom<long double>() noexcept {
+    return StdNormalDistribution<long double>(TSysRNG<ui64>());
+}
diff --git a/util/random/normal.h b/util/random/normal.h
new file mode 100644
index 0000000000..1ed132b532
--- /dev/null
+++ b/util/random/normal.h
@@ -0,0 +1,38 @@
+#pragma once
+
+#include <cmath>
+
+// sometimes we need stateless normal distribution...
+
+/*
+ * normal distribution with Box-Muller transform
+ * http://www.design.caltech.edu/erik/Misc/Gaussian.html
+ */
+template <typename T, typename TRng>
+static inline T StdNormalDistribution(TRng&& rng) noexcept {
+    T x;
+    T y;
+    T r;
+
+    do {
+        x = (T)rng.GenRandReal1() * T(2) - T(1);
+        y = (T)rng.GenRandReal1() * T(2) - T(1);
+        r = x * x + y * y;
+    } while (r > T(1) || r <= T(0));
+
+    return x * std::sqrt(-T(2) * std::log(r) / r);
+}
+
+template <typename T, typename TRng>
+static inline T NormalDistribution(TRng&& rng, T m, T d) noexcept {
+    return StdNormalDistribution<T>(rng) * d + m;
+}
+
+// specialized for float, double, long double
+template <class T>
+T StdNormalRandom() noexcept;
+
+template <class T>
+static inline T NormalRandom(T m, T d) noexcept {
+    return StdNormalRandom<T>() * d + m;
+}
diff --git a/util/random/normal_ut.cpp b/util/random/normal_ut.cpp
new file mode 100644
index 0000000000..42b6cc4ba2
--- /dev/null
+++ b/util/random/normal_ut.cpp
@@ -0,0 +1,81 @@
+#include "normal.h"
+#include "fast.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/generic/vector.h>
+
+#include <functional>
+
+Y_UNIT_TEST_SUITE(TestNormalDistribution) {
+    Y_UNIT_TEST(TestDefined) {
+        volatile auto x = NormalRandom<float>(0, 1) + NormalRandom<double>(0, 1) + NormalRandom<long double>(0, 1);
+
+        (void)x;
+    }
+
+    template <class T>
+    static void TestMD(std::function<T()> f, T m, T d) {
+        TVector<T> v;
+
+        v.reserve(20000);
+
+        for (size_t i = 0; i < 20000; ++i) {
+            v.push_back(f());
+        }
+
+        long double mm = 0;
+        long double vv = 0;
+
+        for (auto x : v) {
+            mm += x;
+        }
+
+        mm /= v.size();
+
+        for (auto x : v) {
+            vv += (mm - x) * (mm - x);
+        }
+
+        vv /= v.size();
+
+        long double dd = std::sqrt(vv);
+
+        UNIT_ASSERT_DOUBLES_EQUAL(m, mm, (m + 1) * 0.05);
+        UNIT_ASSERT_DOUBLES_EQUAL(d, dd, (d + 1) * 0.05);
+    }
+
+    Y_UNIT_TEST(Test1) {
+        TestMD<float>(&StdNormalRandom<float>, 0, 1);
+        TestMD<double>(&StdNormalRandom<double>, 0, 1);
+        TestMD<long double>(&StdNormalRandom<long double>, 0, 1);
+    }
+
+    template <class T>
+    std::function<T()> GenFunc1(T m, T d) {
+        return [m, d]() {
+            return NormalRandom<T>(m, d);
+        };
+    }
+
+    template <class T>
+    std::function<T()> GenFunc2(T m, T d) {
+        TFastRng<ui64> rng(17);
+
+        return [rng, m, d]() mutable {
+            return NormalDistribution<T>(rng, m, d);
+        };
+    }
+
+    Y_UNIT_TEST(Test2) {
+        TestMD<float>(GenFunc1<float>(2, 3), 2, 3);
+        TestMD<double>(GenFunc1<double>(3, 4), 3, 4);
+        TestMD<long double>(GenFunc1<long double>(4, 5), 4, 5);
+    }
+
+    Y_UNIT_TEST(Test3) {
+        TestMD<float>(GenFunc2<float>(20, 30), 20, 30);
+        TestMD<double>(GenFunc2<double>(30, 40), 30, 40);
+        TestMD<long double>(GenFunc2<long double>(40, 50), 40, 50);
+    }
+}
diff --git a/util/random/random.cpp b/util/random/random.cpp
new file mode 100644
index 0000000000..71f9323856
--- /dev/null
+++ b/util/random/random.cpp
@@ -0,0 +1,125 @@
+#include "random.h"
+#include "entropy.h"
+#include "mersenne.h"
+
+#include <util/system/getpid.h>
+#include <util/thread/singleton.h>
+#include <util/stream/multi.h>
+#include <util/stream/mem.h>
+#include <util/digest/numeric.h>
+
+namespace {
+    struct TProcStream {
+        ui32 Extra;
+        TMemoryInput MI;
+        TMultiInput TI;
+
+        static inline ui32 ExtraData() noexcept {
+            ui32 data;
+
+            EntropyPool().LoadOrFail(&data, sizeof(data));
+
+            return IntHash(data ^ GetPID());
+        }
+
+        inline TProcStream() noexcept
+            : Extra(ExtraData())
+            , MI(&Extra, sizeof(Extra))
+            , TI(&MI, &EntropyPool())
+        {
+        }
+
+        inline IInputStream& S() noexcept {
+            return TI;
+        }
+    };
+
+    template <class T>
+    struct TRndGen: public TMersenne<T> {
+        inline TRndGen()
+            : TMersenne<T>(TProcStream().S())
+        {
+        }
+
+        inline TRndGen(T seed)
+            : TMersenne<T>(seed)
+        {
+        }
+    };
+
+    template <class T>
+    static inline TRndGen<T>* GetRndGen() {
+        return FastTlsSingletonWithPriority<TRndGen<T>, 2>();
+    }
+
+    template <unsigned N>
+    struct TToRealTypeBySize {
+        using TResult = ui32;
+    };
+
+    template <>
+    struct TToRealTypeBySize<8> {
+        using TResult = ui64;
+    };
+
+    template <class T>
+    struct TToRealType {
+        using TResult = typename TToRealTypeBySize<sizeof(T)>::TResult;
+    };
+}
+
+#define DEF_RND(TY)                                               \
+    template <>                                                   \
+    TY RandomNumber<TY>() {                                       \
+        return GetRndGen<TToRealType<TY>::TResult>()->GenRand();  \
+    }                                                             \
+                                                                  \
+    template <>                                                   \
+    TY RandomNumber<TY>(TY n) {                                   \
+        return GetRndGen<TToRealType<TY>::TResult>()->Uniform(n); \
+    }
+
+DEF_RND(char)
+DEF_RND(unsigned char)
+DEF_RND(unsigned int)
+DEF_RND(unsigned long)
+DEF_RND(unsigned short)
+DEF_RND(unsigned long long)
+
+#undef DEF_RND
+
+template <>
+bool RandomNumber<bool>() {
+    return RandomNumber<ui8>() % 2 == 0;
+}
+
+template <>
+float RandomNumber<float>() {
+    float ret;
+
+    do {
+        ret = (float)GetRndGen<ui64>()->GenRandReal2();
+    } while (ret >= 1);
+
+    return ret;
+}
+
+template <>
+double RandomNumber<double>() {
+    return GetRndGen<ui64>()->GenRandReal4();
+}
+
+template <>
+long double RandomNumber<long double>() {
+    return RandomNumber<double>();
+}
+
+void ResetRandomState() {
+    *GetRndGen<ui32>() = TRndGen<ui32>();
+    *GetRndGen<ui64>() = TRndGen<ui64>();
+}
+
+void SetRandomSeed(int seed) {
+    *GetRndGen<ui32>() = TRndGen<ui32>(seed);
+    *GetRndGen<ui64>() = TRndGen<ui64>(seed);
+}
diff --git a/util/random/random.h b/util/random/random.h
new file mode 100644
index 0000000000..16b52d3995
--- /dev/null
+++ b/util/random/random.h
@@ -0,0 +1,30 @@
+#pragma once
+
+/*
+ * thread-safe random number generator.
+ *
+ * specialized for:
+ *  all unsigned types (return value in range [0, MAX_VALUE_FOR_TYPE])
+ *  bool
+ *  long double (return value in range [0, 1))
+ *  double (return value in range [0, 1))
+ *  float (return value in range [0, 1))
+ */
+template <class T>
+T RandomNumber();
+
+/*
+ * returns value in range [0, max)
+ */
+template <class T>
+T RandomNumber(T max);
+
+/*
+ * Re-initialize random state - useful after forking in multi-process programs.
+ */
+void ResetRandomState();
+
+/*
+ * Set random SEED
+ */
+void SetRandomSeed(int seed);
diff --git a/util/random/random_ut.cpp b/util/random/random_ut.cpp
new file mode 100644
index 0000000000..30427676f3
--- /dev/null
+++ b/util/random/random_ut.cpp
@@ -0,0 +1,155 @@
+#include "random.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/generic/ylimits.h>
+
+template <class T>
+static inline void AssertRange(T v, T r1, T r2) {
+    UNIT_ASSERT(v >= r1);
+    UNIT_ASSERT(v < r2);
+}
+
+Y_UNIT_TEST_SUITE(TRandomNumberTest) {
+    template <typename T>
+    void TestAll(T n) {
+        for (T i = 0; i < n; ++i) {
+            while (RandomNumber<T>(n) != i) {
+            }
+        }
+    }
+
+    template <typename T>
+    void TestSome(T n) {
+        for (int i = 0; i < 100; ++i) {
+            UNIT_ASSERT(RandomNumber<T>(n) < n);
+        }
+    }
+
+    template <typename T>
+    void TestType() {
+        TestAll<T>(1);
+        TestAll<T>(2);
+        TestAll<T>(3);
+        TestAll<T>(4);
+        TestAll<T>(5);
+        TestAll<T>(6);
+        TestAll<T>(9);
+        TestAll<T>(15);
+        TestAll<T>(16);
+        TestSome<T>(Max<T>());
+        TestSome<T>(Max<T>() - 1);
+        TestSome<T>(Max<T>() - 2);
+        TestSome<T>(Max<T>() - 3);
+        TestSome<T>(Max<T>() - 4);
+        TestSome<T>(Max<T>() - 5);
+        TestSome<T>(Max<T>() - 7);
+        TestSome<T>(Max<T>() - 8);
+        TestSome<T>(Max<T>() - 2222);
+        TestSome<T>(Max<T>() - 22222);
+    }
+
+    Y_UNIT_TEST(TestWithLimit) {
+        TestType<unsigned short>();
+        TestType<unsigned int>();
+        TestType<unsigned long>();
+        TestType<unsigned long long>();
+    }
+
+    Y_UNIT_TEST(TestRandomNumberFloat) {
+        for (size_t i = 0; i < 1000; ++i) {
+            AssertRange<float>(RandomNumber<float>(), 0.0, 1.0);
+        }
+    }
+
+    Y_UNIT_TEST(TestRandomNumberDouble) {
+        for (size_t i = 0; i < 1000; ++i) {
+            AssertRange<double>(RandomNumber<double>(), 0.0, 1.0);
+        }
+    }
+
+    Y_UNIT_TEST(TestRandomNumberLongDouble) {
+        for (size_t i = 0; i < 1000; ++i) {
+            AssertRange<long double>(RandomNumber<long double>(), 0.0, 1.0);
+        }
+    }
+
+    Y_UNIT_TEST(TestBoolean) {
+        while (RandomNumber<bool>()) {
+        }
+        while (!RandomNumber<bool>()) {
+        }
+    }
+
+    Y_UNIT_TEST(TestResetSeed) {
+        SetRandomSeed(42);
+        for (const ui32 el : {
+                 102,
+                 179,
+                 92,
+                 14,
+                 106,
+                 71,
+                 188,
+                 20,
+                 102,
+                 121,
+                 210,
+                 214,
+                 74,
+                 202,
+                 87,
+                 116,
+                 99,
+                 103,
+                 151,
+                 130,
+                 149,
+                 52,
+                 1,
+                 87,
+                 235,
+                 157,
+                 37,
+                 129,
+                 191,
+                 187,
+                 20,
+                 160,
+                 203,
+                 57,
+                 21,
+                 252,
+                 235,
+                 88,
+                 48,
+                 218,
+                 58,
+                 254,
+                 169,
+                 255,
+                 219,
+                 187,
+                 207,
+                 14,
+                 189,
+                 189,
+                 174,
+                 189,
+                 50,
+                 107,
+                 54,
+                 243,
+                 63,
+                 248,
+                 130,
+                 228,
+                 50,
+                 134,
+                 20,
+                 72,
+             }) {
+            UNIT_ASSERT_EQUAL(RandomNumber<ui32>(1 << 8), el);
+        }
+    }
+}
diff --git a/util/random/shuffle.cpp b/util/random/shuffle.cpp
new file mode 100644
index 0000000000..fa35320973
--- /dev/null
+++ b/util/random/shuffle.cpp
@@ -0,0 +1 @@
+#include "shuffle.h"
diff --git a/util/random/shuffle.h b/util/random/shuffle.h
new file mode 100644
index 0000000000..274ac147c9
--- /dev/null
+++ b/util/random/shuffle.h
@@ -0,0 +1,43 @@
+#pragma once
+
+#include "fast.h"
+#include "entropy.h"
+
+#include <util/generic/utility.h>
+
+// some kind of https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm
+
+template <typename TRandIter, typename TRandIterEnd>
+inline void Shuffle(TRandIter begin, TRandIterEnd end) {
+    static_assert(sizeof(end - begin) <= sizeof(size_t), "fixme");
+    static_assert(sizeof(TReallyFastRng32::RandMax()) <= sizeof(size_t), "fixme");
+
+    if ((size_t)(end - begin) < (size_t)TReallyFastRng32::RandMax()) {
+        Shuffle(begin, end, TReallyFastRng32(Seed()));
+    } else {
+        Shuffle(begin, end, TFastRng64(Seed()));
+    }
+}
+
+template <typename TRandIter, typename TRandIterEnd, typename TRandGen>
+inline void Shuffle(TRandIter begin, TRandIterEnd end, TRandGen&& gen) {
+    const size_t sz = end - begin;
+
+    for (size_t i = 1; i < sz; ++i) {
+        DoSwap(*(begin + i), *(begin + gen.Uniform(i + 1)));
+    }
+}
+
+template <typename TRange>
+inline void ShuffleRange(TRange& range) {
+    auto b = range.begin();
+
+    Shuffle(b, range.end());
+}
+
+template <typename TRange, typename TRandGen>
+inline void ShuffleRange(TRange& range, TRandGen&& gen) {
+    auto b = range.begin();
+
+    Shuffle(b, range.end(), gen);
+}
diff --git a/util/random/shuffle_ut.cpp b/util/random/shuffle_ut.cpp
new file mode 100644
index 0000000000..87cbae94c0
--- /dev/null
+++ b/util/random/shuffle_ut.cpp
@@ -0,0 +1,75 @@
+#include "fast.h"
+#include "shuffle.h"
+#include "mersenne.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/generic/ylimits.h>
+
+Y_UNIT_TEST_SUITE(TRandUtilsTest) {
+    template <typename... A>
+    static void TestRange(A&&... args) {
+        TString s0, s1;
+        ShuffleRange(s1, args...);
+        s1 = "0";
+        ShuffleRange(s1, args...);
+        s1 = "01";
+        ShuffleRange(s1, args...);
+        s1 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
+        s0 = s1.copy();
+        ShuffleRange(s1, args...);
+        UNIT_ASSERT(s0 != s1); // if shuffle does work, chances it will fail are 1 to 64!.
+    }
+
+    template <typename... A>
+    static void TestIter(A&&... args) {
+        TString s0, s1;
+
+        auto f = [&]() {
+            auto b = s1.begin();
+            auto e = s1.end();
+
+            Shuffle(b, e, args...);
+        };
+
+        s1 = "0";
+        f();
+
+        s1 = "01";
+        f();
+
+        s1 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
+        s0 = s1.copy();
+        f();
+
+        UNIT_ASSERT(s0 != s1); // if shuffle does work, chances it will fail are 1 to 64!.
+    }
+
+    Y_UNIT_TEST(TestShuffle) {
+        TestRange();
+    }
+
+    Y_UNIT_TEST(TestShuffleMersenne64) {
+        TMersenne<ui64> prng(42);
+
+        TestRange(prng);
+    }
+
+    Y_UNIT_TEST(TestShuffleMersenne32) {
+        TMersenne<ui32> prng(24);
+
+        TestIter(prng);
+    }
+
+    Y_UNIT_TEST(TestShuffleFast32) {
+        TFastRng32 prng(24, 0);
+
+        TestIter(prng);
+    }
+
+    Y_UNIT_TEST(TestShuffleFast64) {
+        TFastRng64 prng(24, 0, 25, 1);
+
+        TestIter(prng);
+    }
+}
diff --git a/util/random/ut/ya.make b/util/random/ut/ya.make
new file mode 100644
index 0000000000..5080b339de
--- /dev/null
+++ b/util/random/ut/ya.make
@@ -0,0 +1,19 @@
+UNITTEST_FOR(util)
+
+OWNER(g:util)
+SUBSCRIBER(g:util-subscribers)
+
+SRCS(
+    random/common_ops_ut.cpp
+    random/easy_ut.cpp
+    random/entropy_ut.cpp
+    random/fast_ut.cpp
+    random/normal_ut.cpp
+    random/mersenne_ut.cpp
+    random/random_ut.cpp
+    random/shuffle_ut.cpp
+)
+
+INCLUDE(${ARCADIA_ROOT}/util/tests/ya_util_tests.inc)
+
+END()
diff --git a/util/random/ya.make b/util/random/ya.make
new file mode 100644
index 0000000000..79c9498ddd
--- /dev/null
+++ b/util/random/ya.make
@@ -0,0 +1,6 @@
+OWNER(g:util)
+SUBSCRIBER(g:util-subscribers)
+
+RECURSE_FOR_TESTS(
+    ut
+)