19 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455 20 #define LN2 0.6931471805599453094172321214581765680755001343602552 40 inline unsigned int CBloomFilter::Hash(
unsigned int nHashNum,
const std::vector<unsigned char>& vDataToHash)
const 52 unsigned int nIndex =
Hash(i, vKey);
54 vData[nIndex >> 3] |= (1 << (7 & nIndex));
62 std::vector<unsigned char> data(stream.
begin(), stream.
end());
68 std::vector<unsigned char> data(hash.
begin(), hash.
end());
78 unsigned int nIndex =
Hash(i, vKey);
80 if (!(
vData[nIndex >> 3] & (1 << (7 & nIndex))))
90 std::vector<unsigned char> data(stream.
begin(), stream.
end());
96 std::vector<unsigned char> data(hash.
begin(), hash.
end());
116 for (
unsigned int i = 0; i < tx.
vout.size(); i++)
124 std::vector<unsigned char> data;
130 if (data.size() != 0 &&
contains(data))
137 std::vector<std::vector<unsigned char> > vSolutions;
159 std::vector<unsigned char> data;
165 if (data.size() != 0 &&
contains(data))
175 double logFpRate = log(fpRate);
178 nHashFuncs = std::max(1, std::min((
int)round(logFpRate / log(0.5)), 50));
180 nEntriesPerGeneration = (nElements + 1) / 2;
181 uint32_t nMaxElements = nEntriesPerGeneration * 3;
189 uint32_t nFilterBits = (uint32_t)ceil(-1.0 *
nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate /
nHashFuncs)));
196 data.resize(((nFilterBits + 63) / 64) << 1);
201 static inline uint32_t
RollingBloomHash(
unsigned int nHashNum, uint32_t
nTweak,
const std::vector<unsigned char>& vDataToHash) {
202 return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
209 static inline uint32_t
FastMod(uint32_t x,
size_t n) {
210 return ((uint64_t)x * (uint64_t)n) >> 32;
215 if (nEntriesThisGeneration == nEntriesPerGeneration) {
216 nEntriesThisGeneration = 0;
218 if (nGeneration == 4) {
221 uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
222 uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
224 for (uint32_t p = 0; p < data.size(); p += 2) {
225 uint64_t p1 = data[p], p2 = data[p + 1];
226 uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
228 data[p + 1] = p2 & mask;
231 nEntriesThisGeneration++;
237 uint32_t pos =
FastMod(h, data.size());
239 data[pos & ~1] = (data[pos & ~1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration & 1)) << bit;
240 data[pos | 1] = (data[pos | 1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration >> 1)) << bit;
255 uint32_t pos =
FastMod(h, data.size());
257 if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) {
273 nEntriesThisGeneration = 0;
275 std::fill(data.begin(), data.end(), 0);
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
CRollingBloomFilter(const unsigned int nElements, const double nFPRate)
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet) const
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) ...
static const unsigned int MAX_BLOOM_FILTER_SIZE
20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
std::vector< unsigned char > vData
unsigned int Hash(unsigned int nHashNum, const std::vector< unsigned char > &vDataToHash) const
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
opcodetype
Script opcodes.
unsigned int MurmurHash3(unsigned int nHashSeed, Span< const unsigned char > vDataToHash)
An input of a transaction.
const uint256 & GetHash() const
static uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector< unsigned char > &vDataToHash)
const std::vector< CTxOut > vout
An output of a transaction.
static const unsigned int MAX_HASH_FUNCS
An outpoint - a combination of a transaction hash and an index n into its vout.
const_iterator end() const
const_iterator begin() const
static const int PROTOCOL_VERSION
network protocol versioning
TxoutType Solver(const CScript &scriptPubKey, std::vector< std::vector< unsigned char >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
static uint32_t FastMod(uint32_t x, size_t n)
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...
bool contains(const std::vector< unsigned char > &vKey) const