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   return hash_string_cs_software(arKey, nKeyLength);
  49 }
  50
  51 NEVER_INLINE
  52 strhash_t hash_string_i_fallback(const char *arKey, uint32_t nKeyLength) {
  53 #ifdef USE_HWCRC
  54   if (IsHWHashSupported()) {
  55     return hash_string_i_unaligned_crc(arKey, nKeyLength);
  56   }
  57 #endif
  58   return hash_string_i_software(arKey, nKeyLength);
  59 }
  60
  61 #endif
  62
  63 strhash_t hash_string_cs_software(const char *arKey, uint32_t nKeyLength) {
  64   uint64_t h[2];
  65   MurmurHash3::hash128<true>(arKey, nKeyLength, 0, h);
  66   return strhash_t(h[0] & STRHASH_MASK);
  67 }
  68
  69 strhash_t hash_string_i_software(const char *arKey, uint32_t nKeyLength) {
  70   uint64_t h[2];
  71   MurmurHash3::hash128<false>(arKey, nKeyLength, 0, h);
  72   return strhash_t(h[0] & STRHASH_MASK);
  73 }
  74
  75 ///////////////////////////////////////////////////////////////////////////////
  76
  77 // This hash is based on "A Fast, Minimal Memory, Consistent Hash
  78 // Algorithm" by John Lamping and Eric Veach.
  79 size_t consistent_hash(int64_t key, size_t buckets, int64_t salt) {
  80   assertx(buckets > 0);
  81   assertx(buckets < std::numeric_limits<size_t>::max());
  82   std::seed_seq seed{key, salt};
  83   std::minstd_rand gen{seed};
  84   size_t b;
  85   size_t j = 0;
  86   do {
  87     b = j;
  88     auto const r =
  89       std::generate_canonical<double, std::numeric_limits<double>::digits>(gen);
  90     j = std::floor((b + 1) / r);
  91   } while (j < buckets);
  92   return b;
  93 }
  94
  95 ///////////////////////////////////////////////////////////////////////////////
  96
  97 }