diff options
Diffstat (limited to 'src/util/fastrange.h')
-rw-r--r-- | src/util/fastrange.h | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/src/util/fastrange.h b/src/util/fastrange.h new file mode 100644 index 0000000000..57bb8e07dc --- /dev/null +++ b/src/util/fastrange.h @@ -0,0 +1,41 @@ +// Copyright (c) 2018-2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_UTIL_FASTRANGE_H +#define BITCOIN_UTIL_FASTRANGE_H + +#include <cstdint> + +// Map a value x that is uniformly distributed in the range [0, 2^64) to a +// value uniformly distributed in [0, n) by returning the upper 64 bits of +// x * n. +// +// See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ +static inline uint64_t MapIntoRange(uint64_t x, uint64_t n) +{ +#ifdef __SIZEOF_INT128__ + return (static_cast<unsigned __int128>(x) * static_cast<unsigned __int128>(n)) >> 64; +#else + // To perform the calculation on 64-bit numbers without losing the + // result to overflow, split the numbers into the most significant and + // least significant 32 bits and perform multiplication piece-wise. + // + // See: https://stackoverflow.com/a/26855440 + const uint64_t x_hi = x >> 32; + const uint64_t x_lo = x & 0xFFFFFFFF; + const uint64_t n_hi = n >> 32; + const uint64_t n_lo = n & 0xFFFFFFFF; + + const uint64_t ac = x_hi * n_hi; + const uint64_t ad = x_hi * n_lo; + const uint64_t bc = x_lo * n_hi; + const uint64_t bd = x_lo * n_lo; + + const uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF); + const uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32); + return upper64; +#endif +} + +#endif // BITCOIN_UTIL_FASTRANGE_H |