hphp/util/hash.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/util/hash.h"
  17
  18 #include "hphp/util/assertions.h"
  19
  20 #include <folly/CpuId.h>
  21
  22 #include <random>
  23
  24 namespace HPHP {
  25
  26 bool IsHWHashSupported() {
  27 #ifdef USE_HWCRC
  28 #if defined __SSE4_2__
  29   return true;
  30 #else
  31   static folly::CpuId cpuid;
  32   return cpuid.sse42();
  33 #endif
  34 #else
  35   return false;
  36 #endif
  37 }
  38
  39 #if !defined(USE_HWCRC) || !(defined(__SSE4_2__) || \
  40                              defined(ENABLE_AARCH64_CRC))
  41 NEVER_INLINE
  42 strhash_t hash_string_cs_fallback(const char *arKey, uint32_t nKeyLength) {
  43 #ifdef USE_HWCRC
  44   if (IsHWHashSupported()) {
  45     return hash_string_cs_unaligned_crc(arKey, nKeyLength);
  46   }
  47 #endif
  48   uint64_t h[2];
  49   MurmurHash3::hash128<true>(arKey, nKeyLength, 0, h);
  50   return strhash_t(h[0] & STRHASH_MASK);
  51 }
  52
  53 NEVER_INLINE
  54 strhash_t hash_string_i_fallback(const char *arKey, uint32_t nKeyLength) {
  55 #ifdef USE_HWCRC
  56   if (IsHWHashSupported()) {
  57     return hash_string_i_unaligned_crc(arKey, nKeyLength);
  58   }
  59 #endif
  60   uint64_t h[2];
  61   MurmurHash3::hash128<false>(arKey, nKeyLength, 0, h);
  62   return strhash_t(h[0] & STRHASH_MASK);
  63 }
  64
  65 #endif
  66
  67 ///////////////////////////////////////////////////////////////////////////////
  68
  69 // This hash is based on "A Fast, Minimal Memory, Consistent Hash
  70 // Algorithm" by John Lamping and Eric Veach.
  71 size_t consistent_hash(int64_t key, size_t buckets, int64_t salt) {
  72   assertx(buckets > 0);
  73   assertx(buckets < std::numeric_limits<size_t>::max());
  74   std::seed_seq seed{key, salt};
  75   std::minstd_rand gen{seed};
  76   size_t b;
  77   size_t j = 0;
  78   do {
  79     b = j;
  80     auto const r =
  81       std::generate_canonical<double, std::numeric_limits<double>::digits>(gen);
  82     j = std::floor((b + 1) / r);
  83   } while (j < buckets);
  84   return b;
  85 }
  86
  87 ///////////////////////////////////////////////////////////////////////////////
  88
  89 }