Branch data     Line data    Source code

#       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                 :            : 
#      18                 :            : /** Fast range reduction with 32-bit input and 32-bit range. */
#      19                 :            : static inline uint32_t FastRange32(uint32_t x, uint32_t n)
#      20                 :   69408209 : {
#      21                 :   69408209 :     return (uint64_t{x} * n) >> 32;
#      22                 :   69408209 : }
#      23                 :            : 
#      24                 :            : /** Fast range reduction with 64-bit input and 64-bit range. */
#      25                 :            : static inline uint64_t FastRange64(uint64_t x, uint64_t n)
#      26                 :      27224 : {
#      27                 :      27224 : #ifdef __SIZEOF_INT128__
#      28                 :      27224 :     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                 :      27224 : }
#      50                 :            : 
#      51                 :            : #endif // BITCOIN_UTIL_FASTRANGE_H