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 // TODO: bool operator==(const HashValue&) const = default; 35 bool operator==(const HashValue& other) const { 36 return value == other.value; 37 } 38 bool operator!=(const HashValue& other) const { 39 return value != other.value; 40 } 41 42 uint32_t value; 43 }; 44 45 } // namespace stg 46 47 namespace std { 48 49 template <> 50 struct hash<stg::HashValue> { 51 size_t operator()(const stg::HashValue& hv) const { 52 // do not overhash 53 return hv.value; 54 } 55 }; 56 57 } // namespace std 58 59 namespace stg { 60 61 struct Hash { 62 constexpr HashValue operator()(HashValue hash_value) const { 63 return hash_value; 64 } 65 66 // Hash boolean by converting to int. 67 constexpr HashValue operator()(bool x) const { 68 return x ? (*this)(1) : (*this)(0); 69 } 70 71 // Hash unsigned 64 bits by splitting, hashing and combining. 72 constexpr HashValue operator()(uint64_t x) const { 73 const uint32_t lo = x; 74 const uint32_t hi = x >> 32; 75 return (*this)(lo, hi); 76 } 77 78 // Hash signed 64 bits by casting to unsigned 64 bits. 79 constexpr HashValue operator()(int64_t x) const { 80 return (*this)(static_cast<uint64_t>(x)); 81 } 82 83 // See https://github.com/skeeto/hash-prospector. 84 constexpr HashValue operator()(uint32_t x) const { 85 x ^= x >> 16; 86 x *= 0x21f0aaad; 87 x ^= x >> 15; 88 x *= 0xd35a2d97; 89 x ^= x >> 15; 90 return HashValue(x); 91 } 92 93 // Hash signed 32 bits by casting to unsigned 32 bits. 94 constexpr HashValue operator()(int32_t x) const { 95 return (*this)(static_cast<uint32_t>(x)); 96 } 97 98 // Hash 8 bits by zero extending to 32 bits. 99 constexpr HashValue operator()(char x) const { 100 return (*this)(static_cast<uint32_t>(static_cast<unsigned char>(x))); 101 } 102 103 // 32-bit FNV-1a. See https://wikipedia.org/wiki/Fowler-Noll-Vo_hash_function. 104 constexpr HashValue operator()(const std::string_view x) const { 105 uint32_t h = 0x811c9dc5; 106 for (auto ch : x) { 107 h ^= static_cast<unsigned char>(ch); 108 h *= 0x01000193; 109 } 110 return HashValue(h); 111 } 112 113 // Hash std::string by constructing a std::string_view. 114 HashValue operator()(const std::string& x) const { 115 return (*this)(std::string_view(x)); 116 } 117 118 // Hash C string by constructing a std::string_view. 119 constexpr HashValue operator()(const char* x) const { 120 return (*this)(std::string_view(x)); 121 } 122 123 // Reverse order Boost hash_combine (must be used with good hashes). 124 template <typename Arg, typename... Args> 125 constexpr HashValue operator()(Arg arg, Args... args) const { 126 const uint32_t seed = (*this)(args...).value; 127 const uint32_t hash = (*this)(arg).value; 128 return HashValue(seed ^ (hash + 0x9e3779b9 + (seed << 6) + (seed >> 2))); 129 } 130 }; 131 132 } // namespace stg 133 134 #endif // STG_HASHING_H_ 135