Bitcoin ABC  0.26.3 P2P Digital Currency
fastrange.h
Go to the documentation of this file.
1 // Copyright (c) 2018-2020 The Bitcoin Core developers
4
5 #ifndef BITCOIN_UTIL_FASTRANGE_H
6 #define BITCOIN_UTIL_FASTRANGE_H
7
8 #include <cstdint>
9
22 static inline uint32_t FastRange32(uint32_t x, uint32_t n) {
23  return (uint64_t{x} * n) >> 32;
24 }
25
27 static inline uint64_t FastRange64(uint64_t x, uint64_t n) {
28 #ifdef __SIZEOF_INT128__
29  return (static_cast<unsigned __int128>(x) *
30  static_cast<unsigned __int128>(n)) >>
31  64;
32 #else
33  // To perform the calculation on 64-bit numbers without losing the
34  // result to overflow, split the numbers into the most significant and
35  // least significant 32 bits and perform multiplication piece-wise.
36  //
37  // See: https://stackoverflow.com/a/26855440
38  const uint64_t x_hi = x >> 32;
39  const uint64_t x_lo = x & 0xFFFFFFFF;
40  const uint64_t n_hi = n >> 32;
41  const uint64_t n_lo = n & 0xFFFFFFFF;
42
43  const uint64_t ac = x_hi * n_hi;
44  const uint64_t ad = x_hi * n_lo;
45  const uint64_t bc = x_lo * n_hi;
46  const uint64_t bd = x_lo * n_lo;
47
48  const uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
49  const uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
50  return upper64;
51 #endif
52 }
53
54 #endif // BITCOIN_UTIL_FASTRANGE_H
static uint64_t FastRange64(uint64_t x, uint64_t n)
Fast range reduction with 64-bit input and 64-bit range.
Definition: fastrange.h:27
static uint32_t FastRange32(uint32_t x, uint32_t n)
This file offers implementations of the fast range reduction technique described in https://lemire....
Definition: fastrange.h:22