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 <type_traits> 23 #include <utility> 24 25 namespace perfetto { 26 namespace base { 27 28 // A helper class which computes a 64-bit hash of the input data. 29 // The algorithm used is FNV-1a as it is fast and easy to implement and has 30 // relatively few collisions. 31 // WARNING: This hash function should not be used for any cryptographic purpose. 32 class Hash { 33 public: 34 // Creates an empty hash object Hash()35 Hash() {} 36 37 // Hashes a numeric value. 38 template < 39 typename T, 40 typename std::enable_if<std::is_arithmetic<T>::value, bool>::type = true> Update(T data)41 void Update(T data) { 42 Update(reinterpret_cast<const char*>(&data), sizeof(data)); 43 } 44 45 // Using the loop instead of "Update(str, strlen(str))" to avoid looping twice Update(const char * str)46 void Update(const char* str) { 47 for (const auto* p = str; *p; ++p) 48 Update(*p); 49 } 50 51 // Hashes a byte array. Update(const char * data,size_t size)52 void Update(const char* data, size_t size) { 53 for (size_t i = 0; i < size; i++) { 54 result_ ^= static_cast<uint8_t>(data[i]); 55 // Note: Arithmetic overflow of unsigned integers is well defined in C++ 56 // standard unlike signed integers. 57 // https://stackoverflow.com/a/41280273 58 result_ *= kFnv1a64Prime; 59 } 60 } 61 digest()62 uint64_t digest() const { return result_; } 63 64 // Usage: 65 // uint64_t hashed_value = Hash::Combine(33, false, "ABC", 458L, 3u, 'x'); 66 template <typename... Ts> Combine(Ts &&...args)67 static uint64_t Combine(Ts&&... args) { 68 Hash hasher; 69 hasher.UpdateAll(std::forward<Ts>(args)...); 70 return hasher.digest(); 71 } 72 73 // `hasher.UpdateAll(33, false, "ABC")` is shorthand for: 74 // `hasher.Update(33); hasher.Update(false); hasher.Update("ABC");` UpdateAll()75 void UpdateAll() {} 76 77 template <typename T, typename... Ts> UpdateAll(T && arg,Ts &&...args)78 void UpdateAll(T&& arg, Ts&&... args) { 79 Update(arg); 80 UpdateAll(std::forward<Ts>(args)...); 81 } 82 83 private: 84 static constexpr uint64_t kFnv1a64OffsetBasis = 0xcbf29ce484222325; 85 static constexpr uint64_t kFnv1a64Prime = 0x100000001b3; 86 87 uint64_t result_ = kFnv1a64OffsetBasis; 88 }; 89 90 // This is for using already-hashed key into std::unordered_map and avoid the 91 // cost of re-hashing. Example: 92 // unordered_map<uint64_t, Value, AlreadyHashed> my_map. 93 template <typename T> 94 struct AlreadyHashed { operatorAlreadyHashed95 size_t operator()(const T& x) const { return static_cast<size_t>(x); } 96 }; 97 98 } // namespace base 99 } // namespace perfetto 100 101 #endif // INCLUDE_PERFETTO_EXT_BASE_HASH_H_ 102