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