1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2 // -*- mode: C++ -*- 3 // 4 // Copyright 2022 Google LLC 5 // 6 // Licensed under the Apache License v2.0 with LLVM Exceptions (the 7 // "License"); you may not use this file except in compliance with the 8 // License. You may obtain a copy of the License at 9 // 10 // https://llvm.org/LICENSE.txt 11 // 12 // Unless required by applicable law or agreed to in writing, software 13 // distributed under the License is distributed on an "AS IS" BASIS, 14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 // See the License for the specific language governing permissions and 16 // limitations under the License. 17 // 18 // Author: Giuliano Procida 19 // Author: Siddharth Nayyar 20 21 #ifndef STG_HASHING_H_ 22 #define STG_HASHING_H_ 23 24 #include <cstddef> 25 #include <cstdint> 26 #include <functional> 27 #include <string> 28 #include <string_view> 29 30 namespace stg { 31 32 struct HashValue { HashValueHashValue33 constexpr explicit HashValue(uint32_t value) : value(value) {} 34 auto operator<=>(const HashValue&) const = default; 35 uint32_t value; 36 }; 37 38 } // namespace stg 39 40 namespace std { 41 42 template <> 43 struct hash<stg::HashValue> { 44 size_t operator()(const stg::HashValue& hv) const { 45 // do not overhash 46 return hv.value; 47 } 48 }; 49 50 } // namespace std 51 52 namespace stg { 53 54 struct Hash { 55 constexpr HashValue operator()(HashValue hash_value) const { 56 return hash_value; 57 } 58 59 // Hash boolean by converting to int. 60 constexpr HashValue operator()(bool x) const { 61 return x ? (*this)(1) : (*this)(0); 62 } 63 64 // Hash unsigned 64 bits by splitting, hashing and combining. 65 constexpr HashValue operator()(uint64_t x) const { 66 const uint32_t lo = x; 67 const uint32_t hi = x >> 32; 68 return (*this)(lo, hi); 69 } 70 71 // Hash signed 64 bits by casting to unsigned 64 bits. 72 constexpr HashValue operator()(int64_t x) const { 73 return (*this)(static_cast<uint64_t>(x)); 74 } 75 76 // See https://github.com/skeeto/hash-prospector. 77 constexpr HashValue operator()(uint32_t x) const { 78 x ^= x >> 16; 79 x *= 0x21f0aaad; 80 x ^= x >> 15; 81 x *= 0xd35a2d97; 82 x ^= x >> 15; 83 return HashValue(x); 84 } 85 86 // Hash signed 32 bits by casting to unsigned 32 bits. 87 constexpr HashValue operator()(int32_t x) const { 88 return (*this)(static_cast<uint32_t>(x)); 89 } 90 91 // Hash 8 bits by zero extending to 32 bits. 92 constexpr HashValue operator()(char x) const { 93 return (*this)(static_cast<uint32_t>(static_cast<unsigned char>(x))); 94 } 95 96 // 32-bit FNV-1a. See https://wikipedia.org/wiki/Fowler-Noll-Vo_hash_function. 97 constexpr HashValue operator()(const std::string_view x) const { 98 uint32_t h = 0x811c9dc5; 99 for (auto ch : x) { 100 h ^= static_cast<unsigned char>(ch); 101 h *= 0x01000193; 102 } 103 return HashValue(h); 104 } 105 106 // Hash std::string by constructing a std::string_view. 107 HashValue operator()(const std::string& x) const { 108 return (*this)(std::string_view(x)); 109 } 110 111 // Hash C string by constructing a std::string_view. 112 constexpr HashValue operator()(const char* x) const { 113 return (*this)(std::string_view(x)); 114 } 115 116 // Reverse order Boost hash_combine (must be used with good hashes). 117 template <typename Arg, typename... Args> 118 constexpr HashValue operator()(Arg arg, Args... args) const { 119 const uint32_t seed = (*this)(args...).value; 120 const uint32_t hash = (*this)(arg).value; 121 return HashValue(seed ^ (hash + 0x9e3779b9 + (seed << 6) + (seed >> 2))); 122 } 123 }; 124 125 } // namespace stg 126 127 #endif // STG_HASHING_H_ 128