intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

5 files changed, 116 insertions, 0 deletions

diff --git a/library/cpp/digest/sfh/sfh.cpp b/library/cpp/digest/sfh/sfh.cpp
new file mode 100644
index 0000000000..c10062105b
--- /dev/null
+++ b/library/cpp/digest/sfh/sfh.cpp
@@ -0,0 +1 @@
+#include "sfh.h"
diff --git a/library/cpp/digest/sfh/sfh.h b/library/cpp/digest/sfh/sfh.h
new file mode 100644
index 0000000000..372938654c
--- /dev/null
+++ b/library/cpp/digest/sfh/sfh.h
@@ -0,0 +1,51 @@
+#pragma once
+
+#include <util/system/defaults.h>
+#include <util/system/unaligned_mem.h>
+
+inline ui32 SuperFastHash(const void* d, size_t l) noexcept {
+    ui32 hash = (ui32)l;
+    ui32 tmp;
+
+    if (!l || !d)
+        return 0;
+
+    TUnalignedMemoryIterator<ui16, 4> iter(d, l);
+
+    while (!iter.AtEnd()) {
+        hash += (ui32)iter.Next();
+        tmp = ((ui32)iter.Next() << 11) ^ hash;
+        hash = (hash << 16) ^ tmp;
+        hash += hash >> 11;
+    }
+
+    switch (iter.Left()) {
+        case 3:
+            hash += (ui32)iter.Next();
+            hash ^= hash << 16;
+            hash ^= ((ui32)(i32) * (const i8*)iter.Last()) << 18;
+            hash += hash >> 11;
+            break;
+
+        case 2:
+            hash += (ui32)iter.Cur();
+            hash ^= hash << 11;
+            hash += hash >> 17;
+            break;
+
+        case 1:
+            hash += *((const i8*)iter.Last());
+            hash ^= hash << 10;
+            hash += hash >> 1;
+    }
+
+    /* Force "avalanching" of final 127 bits */
+    hash ^= hash << 3;
+    hash += hash >> 5;
+    hash ^= hash << 4;
+    hash += hash >> 17;
+    hash ^= hash << 25;
+    hash += hash >> 6;
+
+    return hash;
+}
diff --git a/library/cpp/digest/sfh/sfh_ut.cpp b/library/cpp/digest/sfh/sfh_ut.cpp
new file mode 100644
index 0000000000..912999bae7
--- /dev/null
+++ b/library/cpp/digest/sfh/sfh_ut.cpp
@@ -0,0 +1,40 @@
+#include "sfh.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/stream/output.h>
+
+class TSfhTest: public TTestBase {
+    UNIT_TEST_SUITE(TSfhTest);
+    UNIT_TEST(TestSfh)
+    UNIT_TEST_SUITE_END();
+
+private:
+    inline void TestSfh() {
+        ui8 buf[256];
+
+        for (size_t i = 0; i < 256; ++i) {
+            buf[i] = i;
+        }
+
+        Test(buf, 256, 3840866583UL);
+        Test(buf, 255, 325350515UL);
+        Test(buf, 254, 2920741773UL);
+        Test(buf, 253, 3586628615UL);
+    }
+
+private:
+    inline void Test(const void* data, size_t len, ui32 expected) {
+        const ui32 res = SuperFastHash(data, len);
+
+        try {
+            UNIT_ASSERT_EQUAL(res, expected);
+        } catch (...) {
+            Cerr << res << ", " << expected << Endl;
+
+            throw;
+        }
+    }
+};
+
+UNIT_TEST_SUITE_REGISTRATION(TSfhTest);
diff --git a/library/cpp/digest/sfh/ut/ya.make b/library/cpp/digest/sfh/ut/ya.make
new file mode 100644
index 0000000000..256a66295a
--- /dev/null
+++ b/library/cpp/digest/sfh/ut/ya.make
@@ -0,0 +1,12 @@
+UNITTEST_FOR(library/cpp/digest/sfh)
+
+OWNER(
+    pg
+    g:util
+)
+
+SRCS(
+    sfh_ut.cpp
+)
+
+END()
diff --git a/library/cpp/digest/sfh/ya.make b/library/cpp/digest/sfh/ya.make
new file mode 100644
index 0000000000..b906cd1577
--- /dev/null
+++ b/library/cpp/digest/sfh/ya.make
@@ -0,0 +1,12 @@
+LIBRARY()
+
+OWNER(
+    pg
+    g:util
+)
+
+SRCS(
+    sfh.cpp
+)
+
+END()