1 /* 2 * Copyright (C) 2019 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 #ifndef INCLUDE_PERFETTO_EXT_BASE_HASH_H_ 18 #define INCLUDE_PERFETTO_EXT_BASE_HASH_H_ 19 20 #include <stddef.h> 21 #include <stdint.h> 22 #include <string> 23 #include <string_view> 24 #include <type_traits> 25 #include <utility> 26 27 namespace perfetto { 28 namespace base { 29 30 // A helper class which computes a 64-bit hash of the input data. 31 // The algorithm used is FNV-1a as it is fast and easy to implement and has 32 // relatively few collisions. 33 // WARNING: This hash function should not be used for any cryptographic purpose. 34 class Hasher { 35 public: 36 // Creates an empty hash object 37 constexpr Hasher() = default; 38 39 // Hashes a numeric value. 40 template < 41 typename T, 42 typename std::enable_if<std::is_arithmetic<T>::value, bool>::type = true> Update(T data)43 void Update(T data) { 44 Update(reinterpret_cast<const char*>(&data), sizeof(data)); 45 } 46 Update(char c)47 constexpr void Update(char c) { return Update(&c, 1); } 48 49 // Using the loop instead of "Update(str, strlen(str))" to avoid looping twice Update(const char * str)50 constexpr void Update(const char* str) { 51 for (const auto* p = str; *p; ++p) 52 Update(*p); 53 } 54 55 // Hashes a byte array. Update(const char * data,size_t size)56 constexpr void Update(const char* data, size_t size) { 57 for (size_t i = 0; i < size; i++) { 58 result_ ^= static_cast<uint8_t>(data[i]); 59 // Note: Arithmetic overflow of unsigned integers is well defined in C++ 60 // standard unlike signed integers. 61 // https://stackoverflow.com/a/41280273 62 result_ *= kFnv1a64Prime; 63 } 64 } 65 66 // Allow hashing anything that has `data` and `size` and has the kHashable 67 // trait (e.g., base::StringView). 68 template <typename T, typename = std::enable_if_t<T::kHashable>> Update(const T & t)69 constexpr void Update(const T& t) { 70 if constexpr (std::is_member_function_pointer_v<decltype(&T::data)>) { 71 Update(t.data(), t.size()); 72 } else { 73 Update(t.data, t.size); 74 } 75 } 76 Update(std::string_view s)77 constexpr void Update(std::string_view s) { Update(s.data(), s.size()); } 78 digest()79 constexpr uint64_t digest() const { return result_; } 80 81 // Usage: 82 // uint64_t hashed_value = Hash::Combine(33, false, "ABC", 458L, 3u, 'x'); 83 template <typename... Ts> Combine(Ts &&...args)84 static constexpr uint64_t Combine(Ts&&... args) { 85 Hasher hasher; 86 hasher.UpdateAll(std::forward<Ts>(args)...); 87 return hasher.digest(); 88 } 89 90 // Creates a hasher with `args` already hashed. 91 // 92 // Usage: 93 // Hasher partial = Hash::CreatePartial(33, false, "ABC", 458L); 94 template <typename... Ts> CreatePartial(Ts &&...args)95 static constexpr Hasher CreatePartial(Ts&&... args) { 96 Hasher hasher; 97 hasher.UpdateAll(std::forward<Ts>(args)...); 98 return hasher; 99 } 100 101 // `hasher.UpdateAll(33, false, "ABC")` is shorthand for: 102 // `hasher.Update(33); hasher.Update(false); hasher.Update("ABC");` UpdateAll()103 constexpr void UpdateAll() {} 104 105 template <typename T, typename... Ts> UpdateAll(T && arg,Ts &&...args)106 constexpr void UpdateAll(T&& arg, Ts&&... args) { 107 Update(arg); 108 UpdateAll(std::forward<Ts>(args)...); 109 } 110 111 private: 112 static constexpr uint64_t kFnv1a64OffsetBasis = 0xcbf29ce484222325; 113 static constexpr uint64_t kFnv1a64Prime = 0x100000001b3; 114 115 uint64_t result_ = kFnv1a64OffsetBasis; 116 }; 117 118 // This is for using already-hashed key into std::unordered_map and avoid the 119 // cost of re-hashing. Example: 120 // unordered_map<uint64_t, Value, AlreadyHashed> my_map. 121 template <typename T> 122 struct AlreadyHashed { operatorAlreadyHashed123 size_t operator()(const T& x) const { return static_cast<size_t>(x); } 124 }; 125 126 // base::Hash uses base::Hasher for integer values and falls base to std::hash 127 // for other types. This is needed as std::hash for integers is just the 128 // identity function and Perfetto uses open-addressing hash table, which are 129 // very sensitive to hash quality and are known to degrade in performance 130 // when using std::hash. 131 template <typename T> 132 struct Hash { 133 // Version for ints, using base::Hasher. 134 template <typename U = T> 135 auto operator()(const U& x) -> 136 typename std::enable_if<std::is_arithmetic<U>::value, size_t>::type 137 const { 138 Hasher hash; 139 hash.Update(x); 140 return static_cast<size_t>(hash.digest()); 141 } 142 143 // Version for non-ints, falling back to std::hash. 144 template <typename U = T> 145 auto operator()(const U& x) -> 146 typename std::enable_if<!std::is_arithmetic<U>::value, size_t>::type 147 const { 148 return std::hash<U>()(x); 149 } 150 }; 151 152 } // namespace base 153 } // namespace perfetto 154 155 #endif // INCLUDE_PERFETTO_EXT_BASE_HASH_H_ 156