19 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455 20 #define LN2 0.6931471805599453094172321214581765680755001343602552 28 vData(
std::min((unsigned int)(-1 /
LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
36 nHashFuncs(
std::min((unsigned int)(vData.size() * 8 / nElements *
LN2), MAX_HASH_FUNCS)),
53 inline unsigned int CBloomFilter::Hash(
unsigned int nHashNum,
const std::vector<unsigned char>& vDataToHash)
const 65 unsigned int nIndex =
Hash(i, vKey);
67 vData[nIndex >> 3] |= (1 << (7 & nIndex));
76 std::vector<unsigned char> data(stream.
begin(), stream.
end());
82 std::vector<unsigned char> data(hash.
begin(), hash.
end());
94 unsigned int nIndex =
Hash(i, vKey);
96 if (!(
vData[nIndex >> 3] & (1 << (7 & nIndex))))
106 std::vector<unsigned char> data(stream.
begin(), stream.
end());
112 std::vector<unsigned char> data(hash.
begin(), hash.
end());
131 return vData.size() <= MAX_BLOOM_FILTER_SIZE &&
nHashFuncs <= MAX_HASH_FUNCS;
147 for (
unsigned int i = 0; i < tx.
vout.size(); i++)
155 std::vector<unsigned char> data;
161 if (data.size() != 0 &&
contains(data))
169 std::vector<std::vector<unsigned char> > vSolutions;
190 std::vector<unsigned char> data;
196 if (data.size() != 0 &&
contains(data))
208 for (
unsigned int i = 0; i <
vData.size(); i++)
210 full &=
vData[i] == 0xff;
211 empty &=
vData[i] == 0;
219 double logFpRate = log(fpRate);
222 nHashFuncs = std::max(1, std::min((
int)round(logFpRate / log(0.5)), 50));
224 nEntriesPerGeneration = (nElements + 1) / 2;
225 uint32_t nMaxElements = nEntriesPerGeneration * 3;
233 uint32_t nFilterBits = (uint32_t)ceil(-1.0 *
nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate /
nHashFuncs)));
240 data.resize(((nFilterBits + 63) / 64) << 1);
245 static inline uint32_t RollingBloomHash(
unsigned int nHashNum, uint32_t
nTweak,
const std::vector<unsigned char>& vDataToHash) {
251 if (nEntriesThisGeneration == nEntriesPerGeneration) {
252 nEntriesThisGeneration = 0;
254 if (nGeneration == 4) {
257 uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
258 uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
260 for (uint32_t p = 0; p < data.size(); p += 2) {
261 uint64_t p1 = data[p], p2 = data[p + 1];
262 uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
264 data[p + 1] = p2 & mask;
267 nEntriesThisGeneration++;
270 uint32_t h = RollingBloomHash(n,
nTweak, vKey);
272 uint32_t pos = (h >> 6) % data.size();
274 data[pos & ~1] = (data[pos & ~1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration & 1)) << bit;
275 data[pos | 1] = (data[pos | 1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration >> 1)) << bit;
288 uint32_t h = RollingBloomHash(n,
nTweak, vKey);
290 uint32_t pos = (h >> 6) % data.size();
292 if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) {
308 nEntriesThisGeneration = 0;
310 for (std::vector<uint64_t>::iterator it = data.begin(); it != data.end(); it++) {
CRollingBloomFilter(const unsigned int nElements, const double nFPRate)
void insert(const std::vector< unsigned char > &vKey)
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes) ...
std::vector< unsigned char > vData
unsigned int Hash(unsigned int nHashNum, const std::vector< unsigned char > &vDataToHash) const
void reset(const unsigned int nNewTweak)
Double ended buffer combining vector and stream-like interfaces.
void insert(const std::vector< unsigned char > &vKey)
const std::vector< CTxIn > vin
bool contains(const std::vector< unsigned char > &vKey) const
unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector< unsigned char > &vDataToHash)
opcodetype
Script opcodes.
An input of a transaction.
const uint256 & GetHash() const
const std::vector< CTxOut > vout
An output of a transaction.
An outpoint - a combination of a transaction hash and an index n into its vout.
bool Solver(const CScript &scriptPubKey, txnouttype &typeRet, std::vector< std::vector< unsigned char > > &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
const_iterator end() const
const_iterator begin() const
void UpdateEmptyFull()
Checks for empty and full filters to avoid wasting cpu.
bool GetOp(iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet)
The basic transaction that is broadcasted on the network and contained in blocks. ...
bool IsWithinSizeConstraints() const
True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (c...
uint64_t GetRand(uint64_t nMax)
bool contains(const std::vector< unsigned char > &vKey) const