]>
git.proxmox.com Git - ceph.git/blob - 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).
6 // fastrange/FastRange: A faster alternative to % for mapping a hash value
7 // to an arbitrary range. See https://github.com/lemire/fastrange
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).
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.
23 #include <type_traits>
25 #ifdef TEST_UINT128_COMPAT
26 #undef HAVE_UINT128_EXTENSION
29 namespace ROCKSDB_NAMESPACE
{
33 // Using a class template to support partial specialization
34 template <typename Hash
, typename Range
>
35 struct FastRangeGenericImpl
{
36 // only reach this on no supported specialization
39 template <typename Range
>
40 struct FastRangeGenericImpl
<uint32_t, Range
> {
41 static inline Range
Fn(uint32_t hash
, Range range
) {
42 static_assert(std::is_unsigned
<Range
>::value
, "must be unsigned");
43 static_assert(sizeof(Range
) <= sizeof(uint32_t),
44 "cannot be larger than hash (32 bits)");
46 uint64_t product
= uint64_t{range
} * hash
;
47 return static_cast<Range
>(product
>> 32);
51 template <typename Range
>
52 struct FastRangeGenericImpl
<uint64_t, Range
> {
53 static inline Range
Fn(uint64_t hash
, Range range
) {
54 static_assert(std::is_unsigned
<Range
>::value
, "must be unsigned");
55 static_assert(sizeof(Range
) <= sizeof(uint64_t),
56 "cannot be larger than hash (64 bits)");
58 #ifdef HAVE_UINT128_EXTENSION
59 // Can use compiler's 128-bit type. Trust it to do the right thing.
60 __uint128_t wide
= __uint128_t
{range
} * hash
;
61 return static_cast<Range
>(wide
>> 64);
63 // Fall back: full decomposition.
64 // NOTE: GCC seems to fully understand this code as 64-bit x 64-bit
65 // -> 128-bit multiplication and optimize it appropriately
66 uint64_t range64
= range
; // ok to shift by 32, even if Range is 32-bit
67 uint64_t tmp
= uint64_t{range64
& 0xffffFFFF} * uint64_t{hash
& 0xffffFFFF};
69 tmp
+= uint64_t{range64
& 0xffffFFFF} * uint64_t{hash
>> 32};
70 // Avoid overflow: first add lower 32 of tmp2, and later upper 32
71 uint64_t tmp2
= uint64_t{range64
>> 32} * uint64_t{hash
& 0xffffFFFF};
72 tmp
+= static_cast<uint32_t>(tmp2
);
75 tmp
+= uint64_t{range64
>> 32} * uint64_t{hash
>> 32};
76 return static_cast<Range
>(tmp
);
83 // Now an omnibus templated function (yay parameter inference).
86 // This templated version is not recommended for typical use because
87 // of the potential to mix a 64-bit FastRange with a 32-bit bit hash,
88 // most likely because you put your 32-bit hash in an "unsigned long"
89 // which is 64 bits on some platforms. That doesn't really matter for
90 // an operation like %, but 64-bit FastRange gives extremely bad results,
91 // mostly zero, on 32-bit hash values. And because good hashing is not
92 // generally required for correctness, this kind of mistake could go
93 // unnoticed with just unit tests. Plus it could vary by platform.
94 template <typename Hash
, typename Range
>
95 inline Range
FastRangeGeneric(Hash hash
, Range range
) {
96 return detail::FastRangeGenericImpl
<Hash
, Range
>::Fn(hash
, range
);
99 // The most popular / convenient / recommended variants:
101 // Map a quality 64-bit hash value down to an arbitrary size_t range.
102 // (size_t is standard for mapping to things in memory.)
103 inline size_t FastRange64(uint64_t hash
, size_t range
) {
104 return FastRangeGeneric(hash
, range
);
107 // Map a quality 32-bit hash value down to an arbitrary uint32_t range.
108 inline uint32_t FastRange32(uint32_t hash
, uint32_t range
) {
109 return FastRangeGeneric(hash
, range
);
112 } // namespace ROCKSDB_NAMESPACE