Bitcoin Core  22.99.0
P2P Digital Currency
fastrange.h
Go to the documentation of this file.
1 // Copyright (c) 2018-2020 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_UTIL_FASTRANGE_H
6 #define BITCOIN_UTIL_FASTRANGE_H
7 
8 #include <cstdint>
9 
10 /* This file offers implementations of the fast range reduction technique described
11  * in https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
12  *
13  * In short, they take an integer x and a range n, and return the upper bits of
14  * (x * n). If x is uniformly distributed over its domain, the result is as close to
15  * uniformly distributed over [0, n) as (x mod n) would be, but significantly faster.
16  */
17 
19 static inline uint32_t FastRange32(uint32_t x, uint32_t n)
20 {
21  return (uint64_t{x} * n) >> 32;
22 }
23 
25 static inline uint64_t FastRange64(uint64_t x, uint64_t n)
26 {
27 #ifdef __SIZEOF_INT128__
28  return (static_cast<unsigned __int128>(x) * static_cast<unsigned __int128>(n)) >> 64;
29 #else
30  // To perform the calculation on 64-bit numbers without losing the
31  // result to overflow, split the numbers into the most significant and
32  // least significant 32 bits and perform multiplication piece-wise.
33  //
34  // See: https://stackoverflow.com/a/26855440
35  const uint64_t x_hi = x >> 32;
36  const uint64_t x_lo = x & 0xFFFFFFFF;
37  const uint64_t n_hi = n >> 32;
38  const uint64_t n_lo = n & 0xFFFFFFFF;
39 
40  const uint64_t ac = x_hi * n_hi;
41  const uint64_t ad = x_hi * n_lo;
42  const uint64_t bc = x_lo * n_hi;
43  const uint64_t bd = x_lo * n_lo;
44 
45  const uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
46  const uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
47  return upper64;
48 #endif
49 }
50 
51 #endif // BITCOIN_UTIL_FASTRANGE_H
FastRange64
static uint64_t FastRange64(uint64_t x, uint64_t n)
Fast range reduction with 64-bit input and 64-bit range.
Definition: fastrange.h:25
FastRange32
static uint32_t FastRange32(uint32_t x, uint32_t n)
Fast range reduction with 32-bit input and 32-bit range.
Definition: fastrange.h:19