/root/bitcoin/src/util/fastrange.h
Line | Count | Source |
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 | | static inline uint32_t FastRange32(uint32_t x, uint32_t n) |
20 | 0 | { |
21 | 0 | return (uint64_t{x} * n) >> 32; |
22 | 0 | } Unexecuted instantiation: block.cpp:_ZL11FastRange32jj Unexecuted instantiation: block_index.cpp:_ZL11FastRange32jj Unexecuted instantiation: cuckoocache.cpp:_ZL11FastRange32jj Unexecuted instantiation: golomb_rice.cpp:_ZL11FastRange32jj Unexecuted instantiation: headerssync.cpp:_ZL11FastRange32jj Unexecuted instantiation: load_external_block_file.cpp:_ZL11FastRange32jj Unexecuted instantiation: mini_miner.cpp:_ZL11FastRange32jj Unexecuted instantiation: p2p_handshake.cpp:_ZL11FastRange32jj Unexecuted instantiation: p2p_headers_presync.cpp:_ZL11FastRange32jj Unexecuted instantiation: package_eval.cpp:_ZL11FastRange32jj Unexecuted instantiation: partially_downloaded_block.cpp:_ZL11FastRange32jj Unexecuted instantiation: policy_estimator.cpp:_ZL11FastRange32jj Unexecuted instantiation: process_message.cpp:_ZL11FastRange32jj Unexecuted instantiation: process_messages.cpp:_ZL11FastRange32jj Unexecuted instantiation: rbf.cpp:_ZL11FastRange32jj Unexecuted instantiation: script_sigcache.cpp:_ZL11FastRange32jj Unexecuted instantiation: transaction.cpp:_ZL11FastRange32jj Unexecuted instantiation: txdownloadman.cpp:_ZL11FastRange32jj Unexecuted instantiation: tx_pool.cpp:_ZL11FastRange32jj Unexecuted instantiation: utxo_snapshot.cpp:_ZL11FastRange32jj Unexecuted instantiation: utxo_total_supply.cpp:_ZL11FastRange32jj Unexecuted instantiation: validation_load_mempool.cpp:_ZL11FastRange32jj Unexecuted instantiation: fees.cpp:_ZL11FastRange32jj Unexecuted instantiation: scriptpubkeyman.cpp:_ZL11FastRange32jj Unexecuted instantiation: spend.cpp:_ZL11FastRange32jj Unexecuted instantiation: mempool.cpp:_ZL11FastRange32jj Unexecuted instantiation: bloom.cpp:_ZL11FastRange32jj Unexecuted instantiation: transactions.cpp:_ZL11FastRange32jj Unexecuted instantiation: mining.cpp:_ZL11FastRange32jj Unexecuted instantiation: setup_common.cpp:_ZL11FastRange32jj Unexecuted instantiation: txmempool.cpp:_ZL11FastRange32jj Unexecuted instantiation: validation.cpp:_ZL11FastRange32jj Unexecuted instantiation: blockencodings.cpp:_ZL11FastRange32jj Unexecuted instantiation: blockfilter.cpp:_ZL11FastRange32jj Unexecuted instantiation: init.cpp:_ZL11FastRange32jj Unexecuted instantiation: coinstats.cpp:_ZL11FastRange32jj Unexecuted instantiation: net_processing.cpp:_ZL11FastRange32jj Unexecuted instantiation: blockmanager_args.cpp:_ZL11FastRange32jj Unexecuted instantiation: blockstorage.cpp:_ZL11FastRange32jj Unexecuted instantiation: chainstate.cpp:_ZL11FastRange32jj Unexecuted instantiation: chainstatemanager_args.cpp:_ZL11FastRange32jj Unexecuted instantiation: context.cpp:_ZL11FastRange32jj Unexecuted instantiation: interfaces.cpp:_ZL11FastRange32jj Unexecuted instantiation: mempool_persist.cpp:_ZL11FastRange32jj Unexecuted instantiation: mempool_persist_args.cpp:_ZL11FastRange32jj Unexecuted instantiation: miner.cpp:_ZL11FastRange32jj Unexecuted instantiation: txdownloadman_impl.cpp:_ZL11FastRange32jj Unexecuted instantiation: rest.cpp:_ZL11FastRange32jj Unexecuted instantiation: blockchain.cpp:_ZL11FastRange32jj Unexecuted instantiation: net.cpp:_ZL11FastRange32jj Unexecuted instantiation: rawtransaction.cpp:_ZL11FastRange32jj Unexecuted instantiation: server.cpp:_ZL11FastRange32jj Unexecuted instantiation: server_util.cpp:_ZL11FastRange32jj Unexecuted instantiation: txoutproof.cpp:_ZL11FastRange32jj Unexecuted instantiation: sigcache.cpp:_ZL11FastRange32jj Unexecuted instantiation: base.cpp:_ZL11FastRange32jj Unexecuted instantiation: blockfilterindex.cpp:_ZL11FastRange32jj Unexecuted instantiation: coinstatsindex.cpp:_ZL11FastRange32jj Unexecuted instantiation: txindex.cpp:_ZL11FastRange32jj Unexecuted instantiation: coin.cpp:_ZL11FastRange32jj |
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 | 0 | { |
27 | 0 | #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 | 0 | } Unexecuted instantiation: block.cpp:_ZL11FastRange64mm Unexecuted instantiation: block_index.cpp:_ZL11FastRange64mm Unexecuted instantiation: cuckoocache.cpp:_ZL11FastRange64mm Unexecuted instantiation: golomb_rice.cpp:_ZL11FastRange64mm Unexecuted instantiation: headerssync.cpp:_ZL11FastRange64mm Unexecuted instantiation: load_external_block_file.cpp:_ZL11FastRange64mm Unexecuted instantiation: mini_miner.cpp:_ZL11FastRange64mm Unexecuted instantiation: p2p_handshake.cpp:_ZL11FastRange64mm Unexecuted instantiation: p2p_headers_presync.cpp:_ZL11FastRange64mm Unexecuted instantiation: package_eval.cpp:_ZL11FastRange64mm Unexecuted instantiation: partially_downloaded_block.cpp:_ZL11FastRange64mm Unexecuted instantiation: policy_estimator.cpp:_ZL11FastRange64mm Unexecuted instantiation: process_message.cpp:_ZL11FastRange64mm Unexecuted instantiation: process_messages.cpp:_ZL11FastRange64mm Unexecuted instantiation: rbf.cpp:_ZL11FastRange64mm Unexecuted instantiation: script_sigcache.cpp:_ZL11FastRange64mm Unexecuted instantiation: transaction.cpp:_ZL11FastRange64mm Unexecuted instantiation: txdownloadman.cpp:_ZL11FastRange64mm Unexecuted instantiation: tx_pool.cpp:_ZL11FastRange64mm Unexecuted instantiation: utxo_snapshot.cpp:_ZL11FastRange64mm Unexecuted instantiation: utxo_total_supply.cpp:_ZL11FastRange64mm Unexecuted instantiation: validation_load_mempool.cpp:_ZL11FastRange64mm Unexecuted instantiation: fees.cpp:_ZL11FastRange64mm Unexecuted instantiation: scriptpubkeyman.cpp:_ZL11FastRange64mm Unexecuted instantiation: spend.cpp:_ZL11FastRange64mm Unexecuted instantiation: mempool.cpp:_ZL11FastRange64mm Unexecuted instantiation: bloom.cpp:_ZL11FastRange64mm Unexecuted instantiation: transactions.cpp:_ZL11FastRange64mm Unexecuted instantiation: mining.cpp:_ZL11FastRange64mm Unexecuted instantiation: setup_common.cpp:_ZL11FastRange64mm Unexecuted instantiation: txmempool.cpp:_ZL11FastRange64mm Unexecuted instantiation: validation.cpp:_ZL11FastRange64mm Unexecuted instantiation: blockencodings.cpp:_ZL11FastRange64mm Unexecuted instantiation: blockfilter.cpp:_ZL11FastRange64mm Unexecuted instantiation: init.cpp:_ZL11FastRange64mm Unexecuted instantiation: coinstats.cpp:_ZL11FastRange64mm Unexecuted instantiation: net_processing.cpp:_ZL11FastRange64mm Unexecuted instantiation: blockmanager_args.cpp:_ZL11FastRange64mm Unexecuted instantiation: blockstorage.cpp:_ZL11FastRange64mm Unexecuted instantiation: chainstate.cpp:_ZL11FastRange64mm Unexecuted instantiation: chainstatemanager_args.cpp:_ZL11FastRange64mm Unexecuted instantiation: context.cpp:_ZL11FastRange64mm Unexecuted instantiation: interfaces.cpp:_ZL11FastRange64mm Unexecuted instantiation: mempool_persist.cpp:_ZL11FastRange64mm Unexecuted instantiation: mempool_persist_args.cpp:_ZL11FastRange64mm Unexecuted instantiation: miner.cpp:_ZL11FastRange64mm Unexecuted instantiation: txdownloadman_impl.cpp:_ZL11FastRange64mm Unexecuted instantiation: rest.cpp:_ZL11FastRange64mm Unexecuted instantiation: blockchain.cpp:_ZL11FastRange64mm Unexecuted instantiation: net.cpp:_ZL11FastRange64mm Unexecuted instantiation: rawtransaction.cpp:_ZL11FastRange64mm Unexecuted instantiation: server.cpp:_ZL11FastRange64mm Unexecuted instantiation: server_util.cpp:_ZL11FastRange64mm Unexecuted instantiation: txoutproof.cpp:_ZL11FastRange64mm Unexecuted instantiation: sigcache.cpp:_ZL11FastRange64mm Unexecuted instantiation: base.cpp:_ZL11FastRange64mm Unexecuted instantiation: blockfilterindex.cpp:_ZL11FastRange64mm Unexecuted instantiation: coinstatsindex.cpp:_ZL11FastRange64mm Unexecuted instantiation: txindex.cpp:_ZL11FastRange64mm Unexecuted instantiation: coin.cpp:_ZL11FastRange64mm |
50 | | |
51 | | #endif // BITCOIN_UTIL_FASTRANGE_H |