Revert D6050464: [Folly] Move folly/Hash.h to folly/hash/
[folly.git] / folly / Hash.h
1 /*
2  * Copyright 2017 Facebook, Inc.
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 #pragma once
18
19 #include <cstdint>
20 #include <cstring>
21 #include <limits>
22 #include <string>
23 #include <tuple>
24 #include <type_traits>
25 #include <utility>
26
27 #include <folly/ApplyTuple.h>
28 #include <folly/Bits.h>
29 #include <folly/hash/SpookyHashV1.h>
30 #include <folly/hash/SpookyHashV2.h>
31
32 /*
33  * Various hashing functions.
34  */
35
36 namespace folly { namespace hash {
37
38 // This is a general-purpose way to create a single hash from multiple
39 // hashable objects. hash_combine_generic takes a class Hasher implementing
40 // hash<T>; hash_combine uses a default hasher StdHasher that uses std::hash.
41 // hash_combine_generic hashes each argument and combines those hashes in
42 // an order-dependent way to yield a new hash.
43
44
45 // This is the Hash128to64 function from Google's cityhash (available
46 // under the MIT License).  We use it to reduce multiple 64 bit hashes
47 // into a single hash.
48 inline uint64_t hash_128_to_64(const uint64_t upper, const uint64_t lower) {
49   // Murmur-inspired hashing.
50   const uint64_t kMul = 0x9ddfea08eb382d69ULL;
51   uint64_t a = (lower ^ upper) * kMul;
52   a ^= (a >> 47);
53   uint64_t b = (upper ^ a) * kMul;
54   b ^= (b >> 47);
55   b *= kMul;
56   return b;
57 }
58
59 // Never used, but gcc demands it.
60 template <class Hasher>
61 inline size_t hash_combine_generic() {
62   return 0;
63 }
64
65 template <
66     class Iter,
67     class Hash = std::hash<typename std::iterator_traits<Iter>::value_type>>
68 uint64_t hash_range(Iter begin,
69                     Iter end,
70                     uint64_t hash = 0,
71                     Hash hasher = Hash()) {
72   for (; begin != end; ++begin) {
73     hash = hash_128_to_64(hash, hasher(*begin));
74   }
75   return hash;
76 }
77
78 inline uint32_t twang_32from64(uint64_t key);
79
80 template <class Hasher, typename T, typename... Ts>
81 size_t hash_combine_generic(const T& t, const Ts&... ts) {
82   size_t seed = Hasher::hash(t);
83   if (sizeof...(ts) == 0) {
84     return seed;
85   }
86   size_t remainder = hash_combine_generic<Hasher>(ts...);
87   /* static */ if (sizeof(size_t) == sizeof(uint32_t)) {
88     return twang_32from64((uint64_t(seed) << 32) | remainder);
89   } else {
90     return static_cast<size_t>(hash_128_to_64(seed, remainder));
91   }
92 }
93
94 // Simply uses std::hash to hash.  Note that std::hash is not guaranteed
95 // to be a very good hash function; provided std::hash doesn't collide on
96 // the individual inputs, you are fine, but that won't be true for, say,
97 // strings or pairs
98 class StdHasher {
99  public:
100   template <typename T>
101   static size_t hash(const T& t) {
102     return std::hash<T>()(t);
103   }
104 };
105
106 template <typename T, typename... Ts>
107 size_t hash_combine(const T& t, const Ts&... ts) {
108   return hash_combine_generic<StdHasher>(t, ts...);
109 }
110
111 //////////////////////////////////////////////////////////////////////
112
113 /*
114  * Thomas Wang 64 bit mix hash function
115  */
116
117 inline uint64_t twang_mix64(uint64_t key) {
118   key = (~key) + (key << 21);  // key *= (1 << 21) - 1; key -= 1;
119   key = key ^ (key >> 24);
120   key = key + (key << 3) + (key << 8);  // key *= 1 + (1 << 3) + (1 << 8)
121   key = key ^ (key >> 14);
122   key = key + (key << 2) + (key << 4);  // key *= 1 + (1 << 2) + (1 << 4)
123   key = key ^ (key >> 28);
124   key = key + (key << 31);  // key *= 1 + (1 << 31)
125   return key;
126 }
127
128 /*
129  * Inverse of twang_mix64
130  *
131  * Note that twang_unmix64 is significantly slower than twang_mix64.
132  */
133
134 inline uint64_t twang_unmix64(uint64_t key) {
135   // See the comments in jenkins_rev_unmix32 for an explanation as to how this
136   // was generated
137   key *= 4611686016279904257U;
138   key ^= (key >> 28) ^ (key >> 56);
139   key *= 14933078535860113213U;
140   key ^= (key >> 14) ^ (key >> 28) ^ (key >> 42) ^ (key >> 56);
141   key *= 15244667743933553977U;
142   key ^= (key >> 24) ^ (key >> 48);
143   key = (key + 1) * 9223367638806167551U;
144   return key;
145 }
146
147 /*
148  * Thomas Wang downscaling hash function
149  */
150
151 inline uint32_t twang_32from64(uint64_t key) {
152   key = (~key) + (key << 18);
153   key = key ^ (key >> 31);
154   key = key * 21;
155   key = key ^ (key >> 11);
156   key = key + (key << 6);
157   key = key ^ (key >> 22);
158   return (uint32_t) key;
159 }
160
161 /*
162  * Robert Jenkins' reversible 32 bit mix hash function
163  */
164
165 inline uint32_t jenkins_rev_mix32(uint32_t key) {
166   key += (key << 12);  // key *= (1 + (1 << 12))
167   key ^= (key >> 22);
168   key += (key << 4);   // key *= (1 + (1 << 4))
169   key ^= (key >> 9);
170   key += (key << 10);  // key *= (1 + (1 << 10))
171   key ^= (key >> 2);
172   // key *= (1 + (1 << 7)) * (1 + (1 << 12))
173   key += (key << 7);
174   key += (key << 12);
175   return key;
176 }
177
178 /*
179  * Inverse of jenkins_rev_mix32
180  *
181  * Note that jenkinks_rev_unmix32 is significantly slower than
182  * jenkins_rev_mix32.
183  */
184
185 inline uint32_t jenkins_rev_unmix32(uint32_t key) {
186   // These are the modular multiplicative inverses (in Z_2^32) of the
187   // multiplication factors in jenkins_rev_mix32, in reverse order.  They were
188   // computed using the Extended Euclidean algorithm, see
189   // http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
190   key *= 2364026753U;
191
192   // The inverse of a ^= (a >> n) is
193   // b = a
194   // for (int i = n; i < 32; i += n) {
195   //   b ^= (a >> i);
196   // }
197   key ^=
198     (key >> 2) ^ (key >> 4) ^ (key >> 6) ^ (key >> 8) ^
199     (key >> 10) ^ (key >> 12) ^ (key >> 14) ^ (key >> 16) ^
200     (key >> 18) ^ (key >> 20) ^ (key >> 22) ^ (key >> 24) ^
201     (key >> 26) ^ (key >> 28) ^ (key >> 30);
202   key *= 3222273025U;
203   key ^= (key >> 9) ^ (key >> 18) ^ (key >> 27);
204   key *= 4042322161U;
205   key ^= (key >> 22);
206   key *= 16773121U;
207   return key;
208 }
209
210 /*
211  * Fowler / Noll / Vo (FNV) Hash
212  *     http://www.isthe.com/chongo/tech/comp/fnv/
213  */
214
215 const uint32_t FNV_32_HASH_START = 2166136261UL;
216 const uint64_t FNV_64_HASH_START = 14695981039346656037ULL;
217 const uint64_t FNVA_64_HASH_START = 14695981039346656037ULL;
218
219 inline uint32_t fnv32(const char* buf, uint32_t hash = FNV_32_HASH_START) {
220   // forcing signed char, since other platforms can use unsigned
221   const signed char* s = reinterpret_cast<const signed char*>(buf);
222
223   for (; *s; ++s) {
224     hash += (hash << 1) + (hash << 4) + (hash << 7) +
225             (hash << 8) + (hash << 24);
226     hash ^= *s;
227   }
228   return hash;
229 }
230
231 inline uint32_t fnv32_buf(const void* buf,
232                           size_t n,
233                           uint32_t hash = FNV_32_HASH_START) {
234   // forcing signed char, since other platforms can use unsigned
235   const signed char* char_buf = reinterpret_cast<const signed char*>(buf);
236
237   for (size_t i = 0; i < n; ++i) {
238     hash += (hash << 1) + (hash << 4) + (hash << 7) +
239             (hash << 8) + (hash << 24);
240     hash ^= char_buf[i];
241   }
242
243   return hash;
244 }
245
246 inline uint32_t fnv32(const std::string& str,
247                       uint32_t hash = FNV_32_HASH_START) {
248   return fnv32_buf(str.data(), str.size(), hash);
249 }
250
251 inline uint64_t fnv64(const char* buf, uint64_t hash = FNV_64_HASH_START) {
252   // forcing signed char, since other platforms can use unsigned
253   const signed char* s = reinterpret_cast<const signed char*>(buf);
254
255   for (; *s; ++s) {
256     hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
257       (hash << 8) + (hash << 40);
258     hash ^= *s;
259   }
260   return hash;
261 }
262
263 inline uint64_t fnv64_buf(const void* buf,
264                           size_t n,
265                           uint64_t hash = FNV_64_HASH_START) {
266   // forcing signed char, since other platforms can use unsigned
267   const signed char* char_buf = reinterpret_cast<const signed char*>(buf);
268
269   for (size_t i = 0; i < n; ++i) {
270     hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
271       (hash << 8) + (hash << 40);
272     hash ^= char_buf[i];
273   }
274   return hash;
275 }
276
277 inline uint64_t fnv64(const std::string& str,
278                       uint64_t hash = FNV_64_HASH_START) {
279   return fnv64_buf(str.data(), str.size(), hash);
280 }
281
282 inline uint64_t fnva64_buf(const void* buf,
283                            size_t n,
284                            uint64_t hash = FNVA_64_HASH_START) {
285   const uint8_t* char_buf = reinterpret_cast<const uint8_t*>(buf);
286
287   for (size_t i = 0; i < n; ++i) {
288     hash ^= char_buf[i];
289     hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
290             (hash << 8) + (hash << 40);
291   }
292   return hash;
293 }
294
295 inline uint64_t fnva64(const std::string& str,
296                        uint64_t hash = FNVA_64_HASH_START) {
297   return fnva64_buf(str.data(), str.size(), hash);
298 }
299
300 /*
301  * Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html
302  */
303
304 #define get16bits(d) folly::loadUnaligned<uint16_t>(d)
305
306 inline uint32_t hsieh_hash32_buf(const void* buf, size_t len) {
307   // forcing signed char, since other platforms can use unsigned
308   const unsigned char* s = reinterpret_cast<const unsigned char*>(buf);
309   uint32_t hash = static_cast<uint32_t>(len);
310   uint32_t tmp;
311   size_t rem;
312
313   if (len <= 0 || buf == nullptr) {
314     return 0;
315   }
316
317   rem = len & 3;
318   len >>= 2;
319
320   /* Main loop */
321   for (;len > 0; len--) {
322     hash  += get16bits (s);
323     tmp    = (get16bits (s+2) << 11) ^ hash;
324     hash   = (hash << 16) ^ tmp;
325     s  += 2*sizeof (uint16_t);
326     hash  += hash >> 11;
327   }
328
329   /* Handle end cases */
330   switch (rem) {
331   case 3:
332     hash += get16bits(s);
333     hash ^= hash << 16;
334     hash ^= s[sizeof (uint16_t)] << 18;
335     hash += hash >> 11;
336     break;
337   case 2:
338     hash += get16bits(s);
339     hash ^= hash << 11;
340     hash += hash >> 17;
341     break;
342   case 1:
343     hash += *s;
344     hash ^= hash << 10;
345     hash += hash >> 1;
346   }
347
348   /* Force "avalanching" of final 127 bits */
349   hash ^= hash << 3;
350   hash += hash >> 5;
351   hash ^= hash << 4;
352   hash += hash >> 17;
353   hash ^= hash << 25;
354   hash += hash >> 6;
355
356   return hash;
357 };
358
359 #undef get16bits
360
361 inline uint32_t hsieh_hash32(const char* s) {
362   return hsieh_hash32_buf(s, std::strlen(s));
363 }
364
365 inline uint32_t hsieh_hash32_str(const std::string& str) {
366   return hsieh_hash32_buf(str.data(), str.size());
367 }
368
369 //////////////////////////////////////////////////////////////////////
370
371 } // namespace hash
372
373 namespace detail {
374 struct integral_hasher {
375   template <typename I>
376   size_t operator()(I const& i) const {
377     static_assert(sizeof(I) <= 8, "input type is too wide");
378     if (sizeof(I) <= 4) { // the branch taken is known at compile time
379       auto const i32 = static_cast<int32_t>(i); // impl accident: sign-extends
380       auto const u32 = static_cast<uint32_t>(i32);
381       return static_cast<size_t>(hash::jenkins_rev_mix32(u32));
382     } else {
383       auto const u64 = static_cast<uint64_t>(i);
384       return static_cast<size_t>(hash::twang_mix64(u64));
385     }
386   }
387 };
388 } // namespace detail
389
390 template <class Key, class Enable = void>
391 struct hasher;
392
393 struct Hash {
394   template <class T>
395   size_t operator()(const T& v) const {
396     return hasher<T>()(v);
397   }
398
399   template <class T, class... Ts>
400   size_t operator()(const T& t, const Ts&... ts) const {
401     return hash::hash_128_to_64((*this)(t), (*this)(ts...));
402   }
403 };
404
405 template <>
406 struct hasher<bool> {
407   size_t operator()(bool key) const {
408     // Make sure that all the output bits depend on the input.
409     return key ? std::numeric_limits<size_t>::max() : 0;
410   }
411 };
412
413 template <>
414 struct hasher<unsigned long long> : detail::integral_hasher {};
415
416 template <>
417 struct hasher<signed long long> : detail::integral_hasher {};
418
419 template <>
420 struct hasher<unsigned long> : detail::integral_hasher {};
421
422 template <>
423 struct hasher<signed long> : detail::integral_hasher {};
424
425 template <>
426 struct hasher<unsigned int> : detail::integral_hasher {};
427
428 template <>
429 struct hasher<signed int> : detail::integral_hasher {};
430
431 template <>
432 struct hasher<unsigned short> : detail::integral_hasher {};
433
434 template <>
435 struct hasher<signed short> : detail::integral_hasher {};
436
437 template <>
438 struct hasher<unsigned char> : detail::integral_hasher {};
439
440 template <>
441 struct hasher<signed char> : detail::integral_hasher {};
442
443 template <> // char is a different type from both signed char and unsigned char
444 struct hasher<char> : detail::integral_hasher {};
445
446 template <> struct hasher<std::string> {
447   size_t operator()(const std::string& key) const {
448     return static_cast<size_t>(
449         hash::SpookyHashV2::Hash64(key.data(), key.size(), 0));
450   }
451 };
452
453 template <class T>
454 struct hasher<T, typename std::enable_if<std::is_enum<T>::value, void>::type> {
455   size_t operator()(T key) const {
456     return Hash()(static_cast<typename std::underlying_type<T>::type>(key));
457   }
458 };
459
460 template <class T1, class T2>
461 struct hasher<std::pair<T1, T2>> {
462   size_t operator()(const std::pair<T1, T2>& key) const {
463     return Hash()(key.first, key.second);
464   }
465 };
466
467 template <typename... Ts>
468 struct hasher<std::tuple<Ts...>> {
469   size_t operator() (const std::tuple<Ts...>& key) const {
470     return applyTuple(Hash(), key);
471   }
472 };
473
474 // recursion
475 template <size_t index, typename... Ts>
476 struct TupleHasher {
477   size_t operator()(std::tuple<Ts...> const& key) const {
478     return hash::hash_combine(
479       TupleHasher<index - 1, Ts...>()(key),
480       std::get<index>(key));
481   }
482 };
483
484 // base
485 template <typename... Ts>
486 struct TupleHasher<0, Ts...> {
487   size_t operator()(std::tuple<Ts...> const& key) const {
488     // we could do std::hash here directly, but hash_combine hides all the
489     // ugly templating implicitly
490     return hash::hash_combine(std::get<0>(key));
491   }
492 };
493
494 } // namespace folly
495
496 // Custom hash functions.
497 namespace std {
498   // Hash function for pairs. Requires default hash functions for both
499   // items in the pair.
500   template <typename T1, typename T2>
501   struct hash<std::pair<T1, T2> > {
502    public:
503     size_t operator()(const std::pair<T1, T2>& x) const {
504       return folly::hash::hash_combine(x.first, x.second);
505     }
506   };
507
508   // Hash function for tuples. Requires default hash functions for all types.
509   template <typename... Ts>
510   struct hash<std::tuple<Ts...>> {
511     size_t operator()(std::tuple<Ts...> const& key) const {
512       folly::TupleHasher<
513         std::tuple_size<std::tuple<Ts...>>::value - 1, // start index
514         Ts...> hasher;
515
516       return hasher(key);
517     }
518   };
519 } // namespace std