1 /*
2 * Copyright (c) 2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef API_BASE_UTIL_HASH_H
17 #define API_BASE_UTIL_HASH_H
18
19 #include <cstdint>
20
21 #include <base/containers/type_traits.h>
22 #include <base/namespace.h>
23
24 BASE_BEGIN_NAMESPACE()
25 constexpr uint64_t FNV_OFFSET_BASIS = 0xcbf29ce484222325ull;
26 constexpr uint64_t FNV_PRIME = 1099511628211ull;
27 constexpr uint32_t FNV_OFFSET_BASIS_32 = 0x811c9dc5u;
28 constexpr uint32_t FNV_PRIME_32 = 16777619u;
29
30 template<typename T>
31 uint64_t hash(const T& value);
32
33 template<>
hash(const uint8_t & value)34 inline uint64_t hash(const uint8_t& value)
35 {
36 return value;
37 }
38 template<>
hash(const uint16_t & value)39 inline uint64_t hash(const uint16_t& value)
40 {
41 return value;
42 }
43 template<>
hash(const uint32_t & value)44 inline uint64_t hash(const uint32_t& value)
45 {
46 return value;
47 }
48 template<>
hash(const uint64_t & value)49 inline uint64_t hash(const uint64_t& value)
50 {
51 return value;
52 }
53 #ifdef __APPLE__
54 template<>
hash(const unsigned long & value)55 inline uint64_t hash(const unsigned long& value)
56 {
57 return value;
58 }
59 #endif
60 template<>
hash(const int8_t & value)61 inline uint64_t hash(const int8_t& value)
62 {
63 return static_cast<uint64_t>(value);
64 }
65 template<>
hash(const int16_t & value)66 inline uint64_t hash(const int16_t& value)
67 {
68 return static_cast<uint64_t>(value);
69 }
70 template<>
hash(const int32_t & value)71 inline uint64_t hash(const int32_t& value)
72 {
73 return static_cast<uint64_t>(value);
74 }
75 template<>
hash(const int64_t & value)76 inline uint64_t hash(const int64_t& value)
77 {
78 return static_cast<uint64_t>(value);
79 }
80 template<>
hash(void * const & value)81 inline uint64_t hash(void* const& value)
82 {
83 return static_cast<size_t>(reinterpret_cast<uintptr_t>(value));
84 }
85 template<typename T>
hash(T * const & value)86 inline uint64_t hash(T* const& value)
87 {
88 return static_cast<size_t>(reinterpret_cast<uintptr_t>(value));
89 }
90
FNV1a32Hash(const uint8_t * data,size_t len)91 inline uint32_t FNV1a32Hash(const uint8_t* data, size_t len)
92 {
93 // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
94 uint32_t hash = FNV_OFFSET_BASIS_32;
95 while (len--) {
96 hash ^= *data;
97 hash *= FNV_PRIME_32;
98 ++data;
99 }
100 return hash;
101 }
102
103 template<class T>
FNV1a32Hash(const T * data,size_t len)104 inline uint32_t FNV1a32Hash(const T* data, size_t len)
105 {
106 return FNV1a32Hash(reinterpret_cast<const uint8_t*>(data), len * sizeof(T));
107 }
108
109 template<class T>
FNV1a32Hash(const T & data)110 inline uint32_t FNV1a32Hash(const T& data)
111 {
112 return FNV1a32Hash(&reinterpret_cast<const uint8_t&>(data), sizeof(T));
113 }
114
FNV1aHash(const uint8_t * data,size_t len)115 inline uint64_t FNV1aHash(const uint8_t* data, size_t len)
116 {
117 // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
118 uint64_t hash = FNV_OFFSET_BASIS;
119 while (len--) {
120 hash ^= *data;
121 hash *= FNV_PRIME;
122 ++data;
123 }
124 return hash;
125 }
126
127 template<class T>
FNV1aHash(const T * data,size_t len)128 inline uint64_t FNV1aHash(const T* data, size_t len)
129 {
130 return FNV1aHash(reinterpret_cast<const uint8_t*>(data), len * sizeof(T));
131 }
132
133 template<class T>
FNV1aHash(const T & data)134 inline uint64_t FNV1aHash(const T& data)
135 {
136 return FNV1aHash(&reinterpret_cast<const uint8_t&>(data), sizeof(T));
137 }
138
139 template<typename T>
HashCombine(uint64_t & seed,const T & v)140 inline void HashCombine(uint64_t& seed, const T& v)
141 {
142 constexpr const uint64_t GOLDEN_RATIO = 0x9e3779b9;
143 constexpr const uint64_t ROTL = 6;
144 constexpr const uint64_t ROTR = 2;
145 seed ^= hash(v) + GOLDEN_RATIO + (seed << ROTL) + (seed >> ROTR);
146 }
147
148 template<typename... Rest>
HashCombine(uint64_t & seed,const Rest &...rest)149 inline void HashCombine(uint64_t& seed, const Rest&... rest)
150 {
151 (HashCombine(seed, rest), ...);
152 }
153
154 template<typename... Rest>
Hash(Rest &&...rest)155 inline uint64_t Hash(Rest&&... rest)
156 {
157 uint64_t seed = 0;
158 (HashCombine(seed, BASE_NS::forward<Rest>(rest)), ...);
159 return seed;
160 }
161
162 template<typename Iter>
HashRange(Iter first,Iter last)163 inline uint64_t HashRange(Iter first, Iter last)
164 {
165 uint64_t seed = 0;
166 for (; first != last; ++first) {
167 HashCombine(seed, *first);
168 }
169
170 return seed;
171 }
172
173 template<typename Iter>
HashRange(uint64_t & seed,Iter first,Iter last)174 inline void HashRange(uint64_t& seed, Iter first, Iter last)
175 {
176 for (; first != last; ++first) {
177 HashCombine(seed, *first);
178 }
179 }
180 BASE_END_NAMESPACE()
181 #endif // API_BASE_UTIL_COMPILE_TIME_HASHES_H