diff options
author | fanquake <fanquake@gmail.com> | 2021-12-13 20:54:30 +0800 |
---|---|---|
committer | fanquake <fanquake@gmail.com> | 2021-12-23 15:05:22 +0800 |
commit | df2307cdc3d08233d17beb9a50c144baaef1f44e (patch) | |
tree | a7b6f171847f79a52c61c66deee7d5064c32b78a | |
parent | bf66e258a84e18935fde3ebb9a4b0392bf883222 (diff) | |
download | bitcoin-df2307cdc3d08233d17beb9a50c144baaef1f44e.tar.xz |
util: move MapIntoRange() for reuse in fuzz tests
-rw-r--r-- | src/blockfilter.cpp | 31 | ||||
-rw-r--r-- | src/test/fuzz/golomb_rice.cpp | 14 | ||||
-rw-r--r-- | src/util/golombrice.h | 31 |
3 files changed, 31 insertions, 45 deletions
diff --git a/src/blockfilter.cpp b/src/blockfilter.cpp index 69d4eacd87..b797639d12 100644 --- a/src/blockfilter.cpp +++ b/src/blockfilter.cpp @@ -24,37 +24,6 @@ static const std::map<BlockFilterType, std::string> g_filter_types = { {BlockFilterType::BASIC, "basic"}, }; -// 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 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 - uint64_t x_hi = x >> 32; - uint64_t x_lo = x & 0xFFFFFFFF; - uint64_t n_hi = n >> 32; - uint64_t n_lo = n & 0xFFFFFFFF; - - uint64_t ac = x_hi * n_hi; - uint64_t ad = x_hi * n_lo; - uint64_t bc = x_lo * n_hi; - uint64_t bd = x_lo * n_lo; - - uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF); - uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32); - return upper64; -#endif -} - uint64_t GCSFilter::HashToRange(const Element& element) const { uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1) diff --git a/src/test/fuzz/golomb_rice.cpp b/src/test/fuzz/golomb_rice.cpp index 746347ac95..d6480e7bcb 100644 --- a/src/test/fuzz/golomb_rice.cpp +++ b/src/test/fuzz/golomb_rice.cpp @@ -19,20 +19,6 @@ #include <vector> namespace { -uint64_t MapIntoRange(const uint64_t x, const uint64_t n) -{ - 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; -} uint64_t HashToRange(const std::vector<uint8_t>& element, const uint64_t f) { diff --git a/src/util/golombrice.h b/src/util/golombrice.h index 67d262406f..f14cb594db 100644 --- a/src/util/golombrice.h +++ b/src/util/golombrice.h @@ -40,4 +40,35 @@ uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P) return (q << P) + r; } +// 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_GOLOMBRICE_H |