FTL: Support ftl::stable_hash based on CityHash64
Extends stable hash from libui by increasing maximum string length
supported from 16 to 64 bytes (CityHash64 v1.0.1 - please see
http://code.google.com/p/cityhash/).
Bug: 185536303
Bug: 194863377
Test: ftl_test
Test: Compare with 64-bit std::hash<std::string_view>
Change-Id: Ib123d0690a0d2150aa51c91526784dcf77a65d46
diff --git a/include/ftl/details/hash.h b/include/ftl/details/hash.h
new file mode 100644
index 0000000..f9a7fa8
--- /dev/null
+++ b/include/ftl/details/hash.h
@@ -0,0 +1,119 @@
+/*
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <cinttypes>
+#include <cstring>
+
+namespace android::ftl::details {
+
+// Based on CityHash64 v1.0.1 (http://code.google.com/p/cityhash/), but slightly
+// modernized and trimmed for cases with bounded lengths.
+
+template <typename T = std::uint64_t>
+inline T read_unaligned(const void* ptr) {
+ T v;
+ std::memcpy(&v, ptr, sizeof(T));
+ return v;
+}
+
+template <bool NonZeroShift = false>
+constexpr std::uint64_t rotate(std::uint64_t v, std::uint8_t shift) {
+ if constexpr (!NonZeroShift) {
+ if (shift == 0) return v;
+ }
+ return (v >> shift) | (v << (64 - shift));
+}
+
+constexpr std::uint64_t shift_mix(std::uint64_t v) {
+ return v ^ (v >> 47);
+}
+
+constexpr std::uint64_t hash_length_16(std::uint64_t u, std::uint64_t v) {
+ constexpr std::uint64_t kPrime = 0x9ddfea08eb382d69ull;
+ auto a = (u ^ v) * kPrime;
+ a ^= (a >> 47);
+ auto b = (v ^ a) * kPrime;
+ b ^= (b >> 47);
+ b *= kPrime;
+ return b;
+}
+
+constexpr std::uint64_t kPrime0 = 0xc3a5c85c97cb3127ull;
+constexpr std::uint64_t kPrime1 = 0xb492b66fbe98f273ull;
+constexpr std::uint64_t kPrime2 = 0x9ae16a3b2f90404full;
+constexpr std::uint64_t kPrime3 = 0xc949d7c7509e6557ull;
+
+inline std::uint64_t hash_length_0_to_16(const char* str, std::uint64_t length) {
+ if (length > 8) {
+ const auto a = read_unaligned(str);
+ const auto b = read_unaligned(str + length - 8);
+ return hash_length_16(a, rotate<true>(b + length, static_cast<std::uint8_t>(length))) ^ b;
+ }
+ if (length >= 4) {
+ const auto a = read_unaligned<std::uint32_t>(str);
+ const auto b = read_unaligned<std::uint32_t>(str + length - 4);
+ return hash_length_16(length + (a << 3), b);
+ }
+ if (length > 0) {
+ const auto a = static_cast<unsigned char>(str[0]);
+ const auto b = static_cast<unsigned char>(str[length >> 1]);
+ const auto c = static_cast<unsigned char>(str[length - 1]);
+ const auto y = static_cast<std::uint32_t>(a) + (static_cast<std::uint32_t>(b) << 8);
+ const auto z = static_cast<std::uint32_t>(length) + (static_cast<std::uint32_t>(c) << 2);
+ return shift_mix(y * kPrime2 ^ z * kPrime3) * kPrime2;
+ }
+ return kPrime2;
+}
+
+inline std::uint64_t hash_length_17_to_32(const char* str, std::uint64_t length) {
+ const auto a = read_unaligned(str) * kPrime1;
+ const auto b = read_unaligned(str + 8);
+ const auto c = read_unaligned(str + length - 8) * kPrime2;
+ const auto d = read_unaligned(str + length - 16) * kPrime0;
+ return hash_length_16(rotate(a - b, 43) + rotate(c, 30) + d,
+ a + rotate(b ^ kPrime3, 20) - c + length);
+}
+
+inline std::uint64_t hash_length_33_to_64(const char* str, std::uint64_t length) {
+ auto z = read_unaligned(str + 24);
+ auto a = read_unaligned(str) + (length + read_unaligned(str + length - 16)) * kPrime0;
+ auto b = rotate(a + z, 52);
+ auto c = rotate(a, 37);
+
+ a += read_unaligned(str + 8);
+ c += rotate(a, 7);
+ a += read_unaligned(str + 16);
+
+ const auto vf = a + z;
+ const auto vs = b + rotate(a, 31) + c;
+
+ a = read_unaligned(str + 16) + read_unaligned(str + length - 32);
+ z += read_unaligned(str + length - 8);
+ b = rotate(a + z, 52);
+ c = rotate(a, 37);
+ a += read_unaligned(str + length - 24);
+ c += rotate(a, 7);
+ a += read_unaligned(str + length - 16);
+
+ const auto wf = a + z;
+ const auto ws = b + rotate(a, 31) + c;
+ const auto r = shift_mix((vf + ws) * kPrime2 + (wf + vs) * kPrime0);
+ return shift_mix(r * kPrime0 + vs) * kPrime2;
+}
+
+} // namespace android::ftl::details
diff --git a/include/ftl/hash.h b/include/ftl/hash.h
new file mode 100644
index 0000000..29a6f71
--- /dev/null
+++ b/include/ftl/hash.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <cinttypes>
+#include <optional>
+#include <string_view>
+
+#include <ftl/details/hash.h>
+
+namespace android::ftl {
+
+// Non-cryptographic hash function (namely CityHash64) for strings with at most 64 characters.
+// Unlike std::hash, which returns std::size_t and is only required to produce the same result
+// for the same input within a single execution of a program, this hash is stable.
+inline std::optional<std::uint64_t> stable_hash(std::string_view view) {
+ const auto length = view.length();
+ if (length <= 16) {
+ return details::hash_length_0_to_16(view.data(), length);
+ }
+ if (length <= 32) {
+ return details::hash_length_17_to_32(view.data(), length);
+ }
+ if (length <= 64) {
+ return details::hash_length_33_to_64(view.data(), length);
+ }
+ return {};
+}
+
+} // namespace android::ftl
diff --git a/libs/ftl/Android.bp b/libs/ftl/Android.bp
index 32b2b68..4b41152 100644
--- a/libs/ftl/Android.bp
+++ b/libs/ftl/Android.bp
@@ -24,6 +24,7 @@
"flags_test.cpp",
"function_test.cpp",
"future_test.cpp",
+ "hash_test.cpp",
"match_test.cpp",
"mixins_test.cpp",
"non_null_test.cpp",
diff --git a/libs/ftl/hash_test.cpp b/libs/ftl/hash_test.cpp
new file mode 100644
index 0000000..9c7b8c2
--- /dev/null
+++ b/libs/ftl/hash_test.cpp
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <ftl/hash.h>
+#include <gtest/gtest.h>
+
+#include <numeric>
+#include <string>
+
+namespace android::test {
+
+TEST(Hash, StableHash) {
+ EXPECT_EQ(11160318154034397263ull, (ftl::stable_hash({})));
+
+ std::string string(64, '?');
+ std::iota(string.begin(), string.end(), 'A');
+
+ // Maximum length is 64 characters.
+ EXPECT_FALSE(ftl::stable_hash(string + '\n'));
+
+ EXPECT_EQ(6278090252846864564ull, ftl::stable_hash(std::string_view(string).substr(0, 8)));
+ EXPECT_EQ(1883356980931444616ull, ftl::stable_hash(std::string_view(string).substr(0, 16)));
+ EXPECT_EQ(8073093283835059304ull, ftl::stable_hash(std::string_view(string).substr(0, 32)));
+ EXPECT_EQ(18197365392429149980ull, ftl::stable_hash(string));
+}
+
+} // namespace android::test