Line data    Source code

       1             : // Copyright (c) 2018-2022 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             : 
      18             : /** Fast range reduction with 32-bit input and 32-bit range. */
      19       74104 : static inline uint32_t FastRange32(uint32_t x, uint32_t n)
      20             : {
      21       74104 :     return (uint64_t{x} * n) >> 32;
      22             : }
      23             : 
      24             : /** Fast range reduction with 64-bit input and 64-bit range. */
      25           0 : static inline uint64_t FastRange64(uint64_t x, uint64_t n)
      26             : {
      27             : #ifdef __SIZEOF_INT128__
      28           0 :     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