diff options
Diffstat (limited to 'src/bloom.cpp')
| -rw-r--r-- | src/bloom.cpp | 34 |
1 files changed, 16 insertions, 18 deletions
diff --git a/src/bloom.cpp b/src/bloom.cpp index f07b5b6066..7732cee275 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -1,4 +1,4 @@ -// Copyright (c) 2012-2017 The Bitcoin Core developers +// Copyright (c) 2012-2018 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. @@ -38,17 +38,6 @@ CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, c { } -// Private constructor used by CRollingBloomFilter -CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweakIn) : - vData((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)) / 8), - isFull(false), - isEmpty(true), - nHashFuncs((unsigned int)(vData.size() * 8 / nElements * LN2)), - nTweak(nTweakIn), - nFlags(BLOOM_UPDATE_NONE) -{ -} - inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const { // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values. @@ -148,7 +137,7 @@ bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx) const CTxOut& txout = tx.vout[i]; // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx // If this matches, also add the specific output that was matched. - // This means clients don't have to update the filter themselves when a new relevant tx + // This means clients don't have to update the filter themselves when a new relevant tx // is discovered in order to find spending transactions, which avoids round-tripping and race conditions. CScript::const_iterator pc = txout.scriptPubKey.begin(); std::vector<unsigned char> data; @@ -164,11 +153,11 @@ bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx) insert(COutPoint(hash, i)); else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY) { - txnouttype type; std::vector<std::vector<unsigned char> > vSolutions; - if (Solver(txout.scriptPubKey, type, vSolutions) && - (type == TX_PUBKEY || type == TX_MULTISIG)) + txnouttype type = Solver(txout.scriptPubKey, vSolutions); + if (type == TX_PUBKEY || type == TX_MULTISIG) { insert(COutPoint(hash, i)); + } } break; } @@ -245,6 +234,14 @@ static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash); } + +// A replacement for x % n. This assumes that x and n are 32bit integers, and x is a uniformly random distributed 32bit value +// which should be the case for a good hash. +// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ +static inline uint32_t FastMod(uint32_t x, size_t n) { + return ((uint64_t)x * (uint64_t)n) >> 32; +} + void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey) { if (nEntriesThisGeneration == nEntriesPerGeneration) { @@ -268,7 +265,8 @@ void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey) for (int n = 0; n < nHashFuncs; n++) { uint32_t h = RollingBloomHash(n, nTweak, vKey); int bit = h & 0x3F; - uint32_t pos = (h >> 6) % data.size(); + /* FastMod works with the upper bits of h, so it is safe to ignore that the lower bits of h are already used for bit. */ + uint32_t pos = FastMod(h, data.size()); /* The lowest bit of pos is ignored, and set to zero for the first bit, and to one for the second. */ data[pos & ~1] = (data[pos & ~1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration & 1)) << bit; data[pos | 1] = (data[pos | 1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration >> 1)) << bit; @@ -286,7 +284,7 @@ bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const for (int n = 0; n < nHashFuncs; n++) { uint32_t h = RollingBloomHash(n, nTweak, vKey); int bit = h & 0x3F; - uint32_t pos = (h >> 6) % data.size(); + uint32_t pos = FastMod(h, data.size()); /* If the relevant bit is not set in either data[pos & ~1] or data[pos | 1], the filter does not contain vKey */ if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) { return false; |