1 /*
2 * Copyright (C) 2023 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_COMPILE_TIME_HASHES_H
17 #define API_BASE_UTIL_COMPILE_TIME_HASHES_H
18
19 #include <cstdint>
20
21 #include <base/containers/type_traits.h>
22 #include <base/namespace.h>
23
BASE_BEGIN_NAMESPACE()24 BASE_BEGIN_NAMESPACE()
25 namespace CompileTime {
26 constexpr uint64_t FNV_OFFSET_BASIS = 0xcbf29ce484222325ull;
27 constexpr uint64_t FNV_PRIME = 1099511628211ull;
28
29 constexpr uint64_t lo(uint64_t x)
30 {
31 return x & 0xFFFFFFFF;
32 }
33
34 constexpr uint64_t hi(uint64_t x)
35 {
36 return x >> 32ull;
37 }
38
39 constexpr uint64_t mulu64(uint64_t a, uint64_t b)
40 {
41 return 0 + (lo(a) * lo(b) & uint32_t(-1)) +
42 (((((hi(lo(a) * lo(b)) + lo(a) * hi(b)) & uint32_t(-1)) + hi(a) * lo(b)) & uint32_t(-1)) << 32ull);
43 }
44
45 inline constexpr uint64_t FNV1aHash(const char* const first, uint64_t hash = FNV_OFFSET_BASIS)
46 {
47 if (*first == 0) {
48 return hash;
49 }
50 hash ^= (uint64_t)*first;
51 // Using custom 64 bit multiply to silence "constant integer overflow" warning.
52 hash = mulu64(hash, FNV_PRIME);
53 return FNV1aHash(first + 1, hash);
54 }
55 } // namespace CompileTime
56
57 template<typename T>
58 uint64_t hash(const T& b);
59
60 template<>
hash(const uint8_t & value)61 inline uint64_t hash(const uint8_t& value)
62 {
63 return value;
64 }
65 template<>
hash(const uint16_t & value)66 inline uint64_t hash(const uint16_t& value)
67 {
68 return value;
69 }
70 template<>
hash(const uint32_t & value)71 inline uint64_t hash(const uint32_t& value)
72 {
73 return value;
74 }
75 template<>
hash(const uint64_t & value)76 inline uint64_t hash(const uint64_t& value)
77 {
78 return value;
79 }
80 #ifdef __APPLE__
81 template<>
hash(const unsigned long & value)82 inline uint64_t hash(const unsigned long& value)
83 {
84 return value;
85 }
86 #endif
87 template<>
hash(const int8_t & value)88 inline uint64_t hash(const int8_t& value)
89 {
90 return value;
91 }
92 template<>
hash(const int16_t & value)93 inline uint64_t hash(const int16_t& value)
94 {
95 return value;
96 }
97 template<>
hash(const int32_t & value)98 inline uint64_t hash(const int32_t& value)
99 {
100 return value;
101 }
102 template<>
hash(const int64_t & value)103 inline uint64_t hash(const int64_t& value)
104 {
105 return value;
106 }
107 template<>
hash(void * const & value)108 inline uint64_t hash(void* const& value)
109 {
110 return static_cast<size_t>(reinterpret_cast<uintptr_t>(value));
111 }
112 template<typename T>
hash(T * const & value)113 inline uint64_t hash(T* const& value)
114 {
115 return static_cast<size_t>(reinterpret_cast<uintptr_t>(value));
116 }
117
118 inline uint64_t FNV1aHash(const uint8_t* aData, size_t aLen, uint64_t hash = CompileTime::FNV_OFFSET_BASIS)
119 {
120 // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
121 const uint8_t* src = aData;
122 while (aLen--) {
123 hash ^= *src;
124 hash *= CompileTime::FNV_PRIME;
125 src++;
126 }
127 return hash;
128 }
129
130 template<class T>
131 inline uint64_t FNV1aHash(const T* aData, size_t aLen, uint64_t hash = CompileTime::FNV_OFFSET_BASIS)
132 {
133 return FNV1aHash(reinterpret_cast<const uint8_t*>(aData), aLen * sizeof(T), hash);
134 }
135
136 template<class T>
137 inline uint64_t FNV1aHash(const T& aData, uint64_t hash = CompileTime::FNV_OFFSET_BASIS)
138 {
139 return FNV1aHash(&reinterpret_cast<const uint8_t&>(aData), sizeof(T), hash);
140 }
141
142 template<typename T>
HashCombine(uint64_t & seed,const T & v)143 inline void HashCombine(uint64_t& seed, const T& v)
144 {
145 constexpr const uint64_t GOLDEN_RATIO = 0x9e3779b9;
146 constexpr const uint64_t ROTL = 6;
147 constexpr const uint64_t ROTR = 2;
148 seed ^= hash(v) + GOLDEN_RATIO + (seed << ROTL) + (seed >> ROTR);
149 }
150
151 template<typename... Rest>
HashCombine(uint64_t & seed,const Rest &...rest)152 inline void HashCombine(uint64_t& seed, const Rest&... rest)
153 {
154 (HashCombine(seed, rest), ...);
155 }
156
157 template<typename... Rest>
Hash(Rest &&...rest)158 inline uint64_t Hash(Rest&&... rest)
159 {
160 uint64_t seed = 0;
161 (HashCombine(seed, BASE_NS::forward<Rest>(rest)), ...);
162 return seed;
163 }
164
165 template<typename Iter>
HashRange(Iter first,Iter last)166 inline uint64_t HashRange(Iter first, Iter last)
167 {
168 size_t seed = 0;
169 for (; first != last; ++first) {
170 HashCombine(seed, *first);
171 }
172
173 return seed;
174 }
175
176 template<typename Iter>
HashRange(uint64_t & seed,Iter first,Iter last)177 inline void HashRange(uint64_t& seed, Iter first, Iter last)
178 {
179 for (; first != last; ++first) {
180 HashCombine(seed, *first);
181 }
182 }
183 BASE_END_NAMESPACE()
184 #endif // API_BASE_UTIL_COMPILE_TIME_HASHES_H