Changeset View
Changeset View
Standalone View
Standalone View
src/bloom.cpp
Show First 20 Lines • Show All 74 Lines • ▼ Show 20 Lines | |||||
} | } | ||||
void CBloomFilter::insert(const uint256 &hash) { | void CBloomFilter::insert(const uint256 &hash) { | ||||
std::vector<uint8_t> data(hash.begin(), hash.end()); | std::vector<uint8_t> data(hash.begin(), hash.end()); | ||||
insert(data); | insert(data); | ||||
} | } | ||||
bool CBloomFilter::contains(const std::vector<uint8_t> &vKey) const { | bool CBloomFilter::contains(const std::vector<uint8_t> &vKey) const { | ||||
if (isFull) return true; | if (isFull) { | ||||
if (isEmpty) return false; | return true; | ||||
} | |||||
if (isEmpty) { | |||||
return false; | |||||
} | |||||
for (unsigned int i = 0; i < nHashFuncs; i++) { | for (unsigned int i = 0; i < nHashFuncs; i++) { | ||||
unsigned int nIndex = Hash(i, vKey); | unsigned int nIndex = Hash(i, vKey); | ||||
// Checks bit nIndex of vData | // Checks bit nIndex of vData | ||||
if (!(vData[nIndex >> 3] & (1 << (7 & nIndex)))) return false; | if (!(vData[nIndex >> 3] & (1 << (7 & nIndex)))) { | ||||
return false; | |||||
} | |||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
bool CBloomFilter::contains(const COutPoint &outpoint) const { | bool CBloomFilter::contains(const COutPoint &outpoint) const { | ||||
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); | CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); | ||||
stream << outpoint; | stream << outpoint; | ||||
std::vector<uint8_t> data(stream.begin(), stream.end()); | std::vector<uint8_t> data(stream.begin(), stream.end()); | ||||
Show All 20 Lines | bool CBloomFilter::IsWithinSizeConstraints() const { | ||||
return vData.size() <= MAX_BLOOM_FILTER_SIZE && | return vData.size() <= MAX_BLOOM_FILTER_SIZE && | ||||
nHashFuncs <= MAX_HASH_FUNCS; | nHashFuncs <= MAX_HASH_FUNCS; | ||||
} | } | ||||
bool CBloomFilter::IsRelevantAndUpdate(const CTransaction &tx) { | bool CBloomFilter::IsRelevantAndUpdate(const CTransaction &tx) { | ||||
bool fFound = false; | bool fFound = false; | ||||
// Match if the filter contains the hash of tx for finding tx when they | // Match if the filter contains the hash of tx for finding tx when they | ||||
// appear in a block | // appear in a block | ||||
if (isFull) return true; | if (isFull) { | ||||
if (isEmpty) return false; | return true; | ||||
} | |||||
if (isEmpty) { | |||||
return false; | |||||
} | |||||
const uint256 &txid = tx.GetId(); | const uint256 &txid = tx.GetId(); | ||||
if (contains(txid)) fFound = true; | if (contains(txid)) { | ||||
fFound = true; | |||||
} | |||||
for (unsigned int i = 0; i < tx.vout.size(); i++) { | for (size_t i = 0; i < tx.vout.size(); i++) { | ||||
const CTxOut &txout = tx.vout[i]; | const CTxOut &txout = tx.vout[i]; | ||||
// Match if the filter contains any arbitrary script data element in any | // Match if the filter contains any arbitrary script data element in any | ||||
// scriptPubKey in tx. If this matches, also add the specific output | // scriptPubKey in tx. If this matches, also add the specific output | ||||
// that was matched. This means clients don't have to update the filter | // that was matched. This means clients don't have to update the filter | ||||
// themselves when a new relevant tx is discovered in order to find | // themselves when a new relevant tx is discovered in order to find | ||||
// spending transactions, which avoids round-tripping and race | // spending transactions, which avoids round-tripping and race | ||||
// conditions. | // conditions. | ||||
CScript::const_iterator pc = txout.scriptPubKey.begin(); | CScript::const_iterator pc = txout.scriptPubKey.begin(); | ||||
std::vector<uint8_t> data; | std::vector<uint8_t> data; | ||||
while (pc < txout.scriptPubKey.end()) { | while (pc < txout.scriptPubKey.end()) { | ||||
opcodetype opcode; | opcodetype opcode; | ||||
if (!txout.scriptPubKey.GetOp(pc, opcode, data)) break; | if (!txout.scriptPubKey.GetOp(pc, opcode, data)) { | ||||
break; | |||||
} | |||||
if (data.size() != 0 && contains(data)) { | if (data.size() != 0 && contains(data)) { | ||||
fFound = true; | fFound = true; | ||||
if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL) | if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL) { | ||||
insert(COutPoint(txid, i)); | insert(COutPoint(txid, i)); | ||||
else if ((nFlags & BLOOM_UPDATE_MASK) == | } else if ((nFlags & BLOOM_UPDATE_MASK) == | ||||
BLOOM_UPDATE_P2PUBKEY_ONLY) { | BLOOM_UPDATE_P2PUBKEY_ONLY) { | ||||
txnouttype type; | txnouttype type; | ||||
std::vector<std::vector<uint8_t>> vSolutions; | std::vector<std::vector<uint8_t>> vSolutions; | ||||
if (Solver(txout.scriptPubKey, type, vSolutions) && | if (Solver(txout.scriptPubKey, type, vSolutions) && | ||||
(type == TX_PUBKEY || type == TX_MULTISIG)) | (type == TX_PUBKEY || type == TX_MULTISIG)) { | ||||
insert(COutPoint(txid, i)); | insert(COutPoint(txid, i)); | ||||
} | } | ||||
} | |||||
break; | break; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
if (fFound) return true; | if (fFound) { | ||||
return true; | |||||
} | |||||
for (const CTxIn &txin : tx.vin) { | for (const CTxIn &txin : tx.vin) { | ||||
// Match if the filter contains an outpoint tx spends | // Match if the filter contains an outpoint tx spends | ||||
if (contains(txin.prevout)) return true; | if (contains(txin.prevout)) { | ||||
return true; | |||||
} | |||||
// Match if the filter contains any arbitrary script data element in any | // Match if the filter contains any arbitrary script data element in any | ||||
// scriptSig in tx | // scriptSig in tx | ||||
CScript::const_iterator pc = txin.scriptSig.begin(); | CScript::const_iterator pc = txin.scriptSig.begin(); | ||||
std::vector<uint8_t> data; | std::vector<uint8_t> data; | ||||
while (pc < txin.scriptSig.end()) { | while (pc < txin.scriptSig.end()) { | ||||
opcodetype opcode; | opcodetype opcode; | ||||
if (!txin.scriptSig.GetOp(pc, opcode, data)) break; | if (!txin.scriptSig.GetOp(pc, opcode, data)) { | ||||
if (data.size() != 0 && contains(data)) return true; | break; | ||||
} | |||||
if (data.size() != 0 && contains(data)) { | |||||
return true; | |||||
} | |||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
void CBloomFilter::UpdateEmptyFull() { | void CBloomFilter::UpdateEmptyFull() { | ||||
bool full = true; | bool full = true; | ||||
bool empty = true; | bool empty = true; | ||||
for (unsigned int i = 0; i < vData.size(); i++) { | for (const auto d : vData) { | ||||
full &= vData[i] == 0xff; | full &= (d == 0xff); | ||||
empty &= vData[i] == 0; | empty &= (d == 0); | ||||
} | } | ||||
isFull = full; | isFull = full; | ||||
isEmpty = empty; | isEmpty = empty; | ||||
} | } | ||||
CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, | CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, | ||||
double fpRate) { | double fpRate) { | ||||
double logFpRate = log(fpRate); | double logFpRate = log(fpRate); | ||||
Show All 39 Lines | |||||
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 = -(uint64_t)(nGeneration & 1); | uint64_t nGenerationMask1 = -uint64_t(nGeneration & 1); | ||||
uint64_t nGenerationMask2 = -(uint64_t)(nGeneration >> 1); | uint64_t nGenerationMask2 = -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(); | uint32_t pos = (h >> 6) % 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); | ||||
} | } | ||||
Show All 15 Lines | bool CRollingBloomFilter::contains(const uint256 &hash) const { | ||||
std::vector<uint8_t> vData(hash.begin(), hash.end()); | std::vector<uint8_t> vData(hash.begin(), hash.end()); | ||||
return contains(vData); | return contains(vData); | ||||
} | } | ||||
void CRollingBloomFilter::reset() { | void CRollingBloomFilter::reset() { | ||||
nTweak = GetRand(std::numeric_limits<unsigned int>::max()); | nTweak = GetRand(std::numeric_limits<unsigned int>::max()); | ||||
nEntriesThisGeneration = 0; | nEntriesThisGeneration = 0; | ||||
nGeneration = 1; | nGeneration = 1; | ||||
for (std::vector<uint64_t>::iterator it = data.begin(); it != data.end(); | for (auto &d : data) { | ||||
it++) { | d = 0; | ||||
*it = 0; | |||||
} | } | ||||
} | } |