1 /*
2 * Copyright 2024 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #pragma once
18
19 #include <cinttypes>
20 #include <cstring>
21
22 namespace android::ftl::details {
23
24 // Based on CityHash64 v1.0.1 (http://code.google.com/p/cityhash/), but slightly
25 // modernized and trimmed for cases with bounded lengths.
26
27 template <typename T = std::uint64_t>
read_unaligned(const void * ptr)28 inline T read_unaligned(const void* ptr) {
29 T v;
30 std::memcpy(&v, ptr, sizeof(T));
31 return v;
32 }
33
34 template <bool NonZeroShift = false>
rotate(std::uint64_t v,std::uint8_t shift)35 constexpr std::uint64_t rotate(std::uint64_t v, std::uint8_t shift) {
36 if constexpr (!NonZeroShift) {
37 if (shift == 0) return v;
38 }
39 return (v >> shift) | (v << (64 - shift));
40 }
41
shift_mix(std::uint64_t v)42 constexpr std::uint64_t shift_mix(std::uint64_t v) {
43 return v ^ (v >> 47);
44 }
45
46 __attribute__((no_sanitize("unsigned-integer-overflow")))
hash_length_16(std::uint64_t u,std::uint64_t v)47 constexpr std::uint64_t hash_length_16(std::uint64_t u, std::uint64_t v) {
48 constexpr std::uint64_t kPrime = 0x9ddfea08eb382d69ull;
49 auto a = (u ^ v) * kPrime;
50 a ^= (a >> 47);
51 auto b = (v ^ a) * kPrime;
52 b ^= (b >> 47);
53 b *= kPrime;
54 return b;
55 }
56
57 constexpr std::uint64_t kPrime0 = 0xc3a5c85c97cb3127ull;
58 constexpr std::uint64_t kPrime1 = 0xb492b66fbe98f273ull;
59 constexpr std::uint64_t kPrime2 = 0x9ae16a3b2f90404full;
60 constexpr std::uint64_t kPrime3 = 0xc949d7c7509e6557ull;
61
62 __attribute__((no_sanitize("unsigned-integer-overflow")))
hash_length_0_to_16(const char * str,std::uint64_t length)63 inline std::uint64_t hash_length_0_to_16(const char* str, std::uint64_t length) {
64 if (length > 8) {
65 const auto a = read_unaligned(str);
66 const auto b = read_unaligned(str + length - 8);
67 return hash_length_16(a, rotate<true>(b + length, static_cast<std::uint8_t>(length))) ^ b;
68 }
69 if (length >= 4) {
70 const auto a = read_unaligned<std::uint32_t>(str);
71 const auto b = read_unaligned<std::uint32_t>(str + length - 4);
72 return hash_length_16(length + (a << 3), b);
73 }
74 if (length > 0) {
75 const auto a = static_cast<unsigned char>(str[0]);
76 const auto b = static_cast<unsigned char>(str[length >> 1]);
77 const auto c = static_cast<unsigned char>(str[length - 1]);
78 const auto y = static_cast<std::uint32_t>(a) + (static_cast<std::uint32_t>(b) << 8);
79 const auto z = static_cast<std::uint32_t>(length) + (static_cast<std::uint32_t>(c) << 2);
80 return shift_mix(y * kPrime2 ^ z * kPrime3) * kPrime2;
81 }
82 return kPrime2;
83 }
84
85 __attribute__((no_sanitize("unsigned-integer-overflow")))
hash_length_17_to_32(const char * str,std::uint64_t length)86 inline std::uint64_t hash_length_17_to_32(const char* str, std::uint64_t length) {
87 const auto a = read_unaligned(str) * kPrime1;
88 const auto b = read_unaligned(str + 8);
89 const auto c = read_unaligned(str + length - 8) * kPrime2;
90 const auto d = read_unaligned(str + length - 16) * kPrime0;
91 return hash_length_16(rotate(a - b, 43) + rotate(c, 30) + d,
92 a + rotate(b ^ kPrime3, 20) - c + length);
93 }
94
95 __attribute__((no_sanitize("unsigned-integer-overflow")))
hash_length_33_to_64(const char * str,std::uint64_t length)96 inline std::uint64_t hash_length_33_to_64(const char* str, std::uint64_t length) {
97 auto z = read_unaligned(str + 24);
98 auto a = read_unaligned(str) + (length + read_unaligned(str + length - 16)) * kPrime0;
99 auto b = rotate(a + z, 52);
100 auto c = rotate(a, 37);
101
102 a += read_unaligned(str + 8);
103 c += rotate(a, 7);
104 a += read_unaligned(str + 16);
105
106 const auto vf = a + z;
107 const auto vs = b + rotate(a, 31) + c;
108
109 a = read_unaligned(str + 16) + read_unaligned(str + length - 32);
110 z += read_unaligned(str + length - 8);
111 b = rotate(a + z, 52);
112 c = rotate(a, 37);
113 a += read_unaligned(str + length - 24);
114 c += rotate(a, 7);
115 a += read_unaligned(str + length - 16);
116
117 const auto wf = a + z;
118 const auto ws = b + rotate(a, 31) + c;
119 const auto r = shift_mix((vf + ws) * kPrime2 + (wf + vs) * kPrime0);
120 return shift_mix(r * kPrime0 + vs) * kPrime2;
121 }
122
123 } // namespace android::ftl::details
124