Changeset View
Changeset View
Standalone View
Standalone View
src/bloom.cpp
Show First 20 Lines • Show All 256 Lines • ▼ Show 20 Lines | |||||
/* Similar to CBloomFilter::Hash */ | /* Similar to CBloomFilter::Hash */ | ||||
static inline uint32_t | static inline uint32_t | ||||
RollingBloomHash(uint32_t nHashNum, uint32_t nTweak, | RollingBloomHash(uint32_t nHashNum, uint32_t nTweak, | ||||
const std::vector<uint8_t> &vDataToHash) { | const std::vector<uint8_t> &vDataToHash) { | ||||
return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash); | 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<uint8_t> &vKey) { | void CRollingBloomFilter::insert(const std::vector<uint8_t> &vKey) { | ||||
if (nEntriesThisGeneration == nEntriesPerGeneration) { | if (nEntriesThisGeneration == nEntriesPerGeneration) { | ||||
nEntriesThisGeneration = 0; | nEntriesThisGeneration = 0; | ||||
nGeneration++; | nGeneration++; | ||||
if (nGeneration == 4) { | if (nGeneration == 4) { | ||||
nGeneration = 1; | nGeneration = 1; | ||||
} | } | ||||
uint64_t nGenerationMask1 = 0 - uint64_t(nGeneration & 1); | uint64_t nGenerationMask1 = 0 - uint64_t(nGeneration & 1); | ||||
uint64_t nGenerationMask2 = 0 - uint64_t(nGeneration >> 1); | uint64_t nGenerationMask2 = 0 - uint64_t(nGeneration >> 1); | ||||
/* Wipe old entries that used this generation number. */ | /* Wipe old entries that used this generation number. */ | ||||
for (uint32_t p = 0; p < data.size(); p += 2) { | for (uint32_t p = 0; p < data.size(); p += 2) { | ||||
uint64_t p1 = data[p], p2 = data[p + 1]; | uint64_t p1 = data[p], p2 = data[p + 1]; | ||||
uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2); | uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2); | ||||
data[p] = p1 & mask; | data[p] = p1 & mask; | ||||
data[p + 1] = p2 & mask; | data[p + 1] = p2 & mask; | ||||
} | } | ||||
} | } | ||||
nEntriesThisGeneration++; | nEntriesThisGeneration++; | ||||
for (int n = 0; n < nHashFuncs; n++) { | for (int n = 0; n < nHashFuncs; n++) { | ||||
uint32_t h = RollingBloomHash(n, nTweak, vKey); | uint32_t h = RollingBloomHash(n, nTweak, vKey); | ||||
int bit = h & 0x3F; | 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, | /* The lowest bit of pos is ignored, and set to zero for the first bit, | ||||
* and to one for the second. */ | * and to one for the second. */ | ||||
data[pos & ~1] = (data[pos & ~1] & ~(uint64_t(1) << bit)) | | data[pos & ~1] = (data[pos & ~1] & ~(uint64_t(1) << bit)) | | ||||
uint64_t(nGeneration & 1) << bit; | uint64_t(nGeneration & 1) << bit; | ||||
data[pos | 1] = (data[pos | 1] & ~(uint64_t(1) << bit)) | | data[pos | 1] = (data[pos | 1] & ~(uint64_t(1) << bit)) | | ||||
uint64_t(nGeneration >> 1) << bit; | uint64_t(nGeneration >> 1) << bit; | ||||
} | } | ||||
} | } | ||||
void CRollingBloomFilter::insert(const uint256 &hash) { | void CRollingBloomFilter::insert(const uint256 &hash) { | ||||
std::vector<uint8_t> vData(hash.begin(), hash.end()); | std::vector<uint8_t> vData(hash.begin(), hash.end()); | ||||
insert(vData); | insert(vData); | ||||
} | } | ||||
bool CRollingBloomFilter::contains(const std::vector<uint8_t> &vKey) const { | bool CRollingBloomFilter::contains(const std::vector<uint8_t> &vKey) const { | ||||
for (int n = 0; n < nHashFuncs; n++) { | for (int n = 0; n < nHashFuncs; n++) { | ||||
uint32_t h = RollingBloomHash(n, nTweak, vKey); | uint32_t h = RollingBloomHash(n, nTweak, vKey); | ||||
int bit = h & 0x3F; | 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 | | /* If the relevant bit is not set in either data[pos & ~1] or data[pos | | ||||
* 1], the filter does not contain vKey */ | * 1], the filter does not contain vKey */ | ||||
if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) { | if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) { | ||||
return false; | return false; | ||||
} | } | ||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
Show All 14 Lines |