ceph/src/rocksdb/util/fastrange.h

   1 //  Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5
   6 // fastrange/FastRange: A faster alternative to % for mapping a hash value
   7 // to an arbitrary range. See https://github.com/lemire/fastrange
   8 //
   9 // Generally recommended are FastRange32 for mapping results of 32-bit
  10 // hash functions and FastRange64 for mapping results of 64-bit hash
  11 // functions. FastRange is less forgiving than % if the input hashes are
  12 // not well distributed over the full range of the type (32 or 64 bits).
  13 //
  14 // Also included is a templated implementation FastRangeGeneric for use
  15 // in generic algorithms, but not otherwise recommended because of
  16 // potential ambiguity. Unlike with %, it is critical to use the right
  17 // FastRange variant for the output size of your hash function.
  18
  19 #pragma once
  20
  21 #include <cstddef>
  22 #include <cstdint>
  23 #include <type_traits>
  24
  25 #include "rocksdb/rocksdb_namespace.h"
  26
  27 #ifdef TEST_UINT128_COMPAT
  28 #undef HAVE_UINT128_EXTENSION
  29 #endif
  30
  31 namespace ROCKSDB_NAMESPACE {
  32
  33 namespace detail {
  34
  35 // Using a class template to support partial specialization
  36 template <typename Hash, typename Range>
  37 struct FastRangeGenericImpl {
  38   // only reach this on no supported specialization
  39 };
  40
  41 template <typename Range>
  42 struct FastRangeGenericImpl<uint32_t, Range> {
  43   static inline Range Fn(uint32_t hash, Range range) {
  44     static_assert(std::is_unsigned<Range>::value, "must be unsigned");
  45     static_assert(sizeof(Range) <= sizeof(uint32_t),
  46                   "cannot be larger than hash (32 bits)");
  47
  48     uint64_t product = uint64_t{range} * hash;
  49     return static_cast<Range>(product >> 32);
  50   }
  51 };
  52
  53 template <typename Range>
  54 struct FastRangeGenericImpl<uint64_t, Range> {
  55   static inline Range Fn(uint64_t hash, Range range) {
  56     static_assert(std::is_unsigned<Range>::value, "must be unsigned");
  57     static_assert(sizeof(Range) <= sizeof(uint64_t),
  58                   "cannot be larger than hash (64 bits)");
  59
  60 #ifdef HAVE_UINT128_EXTENSION
  61     // Can use compiler's 128-bit type. Trust it to do the right thing.
  62     __uint128_t wide = __uint128_t{range} * hash;
  63     return static_cast<Range>(wide >> 64);
  64 #else
  65     // Fall back: full decomposition.
  66     // NOTE: GCC seems to fully understand this code as 64-bit x 64-bit
  67     // -> 128-bit multiplication and optimize it appropriately
  68     uint64_t range64 = range;  // ok to shift by 32, even if Range is 32-bit
  69     uint64_t tmp = uint64_t{range64 & 0xffffFFFF} * uint64_t{hash & 0xffffFFFF};
  70     tmp >>= 32;
  71     tmp += uint64_t{range64 & 0xffffFFFF} * uint64_t{hash >> 32};
  72     // Avoid overflow: first add lower 32 of tmp2, and later upper 32
  73     uint64_t tmp2 = uint64_t{range64 >> 32} * uint64_t{hash & 0xffffFFFF};
  74     tmp += static_cast<uint32_t>(tmp2);
  75     tmp >>= 32;
  76     tmp += (tmp2 >> 32);
  77     tmp += uint64_t{range64 >> 32} * uint64_t{hash >> 32};
  78     return static_cast<Range>(tmp);
  79 #endif
  80   }
  81 };
  82
  83 }  // namespace detail
  84
  85 // Now an omnibus templated function (yay parameter inference).
  86 //
  87 // NOTICE:
  88 // This templated version is not recommended for typical use because
  89 // of the potential to mix a 64-bit FastRange with a 32-bit bit hash,
  90 // most likely because you put your 32-bit hash in an "unsigned long"
  91 // which is 64 bits on some platforms. That doesn't really matter for
  92 // an operation like %, but 64-bit FastRange gives extremely bad results,
  93 // mostly zero, on 32-bit hash values. And because good hashing is not
  94 // generally required for correctness, this kind of mistake could go
  95 // unnoticed with just unit tests. Plus it could vary by platform.
  96 template <typename Hash, typename Range>
  97 inline Range FastRangeGeneric(Hash hash, Range range) {
  98   return detail::FastRangeGenericImpl<Hash, Range>::Fn(hash, range);
  99 }
 100
 101 // The most popular / convenient / recommended variants:
 102
 103 // Map a quality 64-bit hash value down to an arbitrary size_t range.
 104 // (size_t is standard for mapping to things in memory.)
 105 inline size_t FastRange64(uint64_t hash, size_t range) {
 106   return FastRangeGeneric(hash, range);
 107 }
 108
 109 // Map a quality 32-bit hash value down to an arbitrary uint32_t range.
 110 inline uint32_t FastRange32(uint32_t hash, uint32_t range) {
 111   return FastRangeGeneric(hash, range);
 112 }
 113
 114 }  // namespace ROCKSDB_NAMESPACE