19 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455 20 #define LN2 0.6931471805599453094172321214581765680755001343602552 36 const uint32_t nTweakIn, uint8_t nFlagsIn)
37 : vData(
std::min<uint32_t>(-1 /
LN2SQUARED * nElements * log(nFPRate),
40 isFull(false), isEmpty(true),
41 nHashFuncs(
std::min<uint32_t>(vData.size() * 8 / nElements *
LN2,
43 nTweak(nTweakIn), nFlags(nFlagsIn) {}
47 const std::vector<uint8_t> &vDataToHash)
const {
60 uint32_t nIndex =
Hash(i, vKey);
62 vData[nIndex >> 3] |= (1 << (7 & nIndex));
70 std::vector<uint8_t> data(stream.
begin(), stream.
end());
75 std::vector<uint8_t> data(hash.
begin(), hash.
end());
87 uint32_t nIndex =
Hash(i, vKey);
89 if (!(
vData[nIndex >> 3] & (1 << (7 & nIndex)))) {
99 std::vector<uint8_t> data(stream.
begin(), stream.
end());
104 std::vector<uint8_t> data(hash.
begin(), hash.
end());
140 for (
size_t i = 0; i < tx.
vout.size(); i++) {
149 std::vector<uint8_t> data;
155 if (data.size() != 0 &&
contains(data)) {
159 }
else if ((
nFlags & BLOOM_UPDATE_MASK) ==
161 std::vector<std::vector<uint8_t>> vSolutions;
189 std::vector<uint8_t> data;
195 if (data.size() != 0 &&
contains(data)) {
207 for (
const auto d :
vData) {
216 const double fpRate) {
217 double logFpRate = log(fpRate);
220 nHashFuncs = std::max(1, std::min<int>(round(logFpRate / log(0.5)), 50));
223 nEntriesPerGeneration = (nElements + 1) / 2;
224 uint32_t nMaxElements = nEntriesPerGeneration * 3;
238 uint32_t nFilterBits =
239 uint32_t(ceil(-1.0 *
nHashFuncs * nMaxElements /
247 data.resize(((nFilterBits + 63) / 64) << 1);
252 static inline uint32_t
254 const std::vector<uint8_t> &vDataToHash) {
255 return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
262 static inline uint32_t
FastMod(uint32_t x,
size_t n) {
263 return (uint64_t(x) * uint64_t(n)) >> 32;
267 if (nEntriesThisGeneration == nEntriesPerGeneration) {
268 nEntriesThisGeneration = 0;
270 if (nGeneration == 4) {
273 uint64_t nGenerationMask1 = 0 - uint64_t(nGeneration & 1);
274 uint64_t nGenerationMask2 = 0 - uint64_t(nGeneration >> 1);
276 for (uint32_t p = 0; p < data.size(); p += 2) {
277 uint64_t p1 = data[p], p2 = data[p + 1];
278 uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
280 data[p + 1] = p2 & mask;
283 nEntriesThisGeneration++;
290 uint32_t pos =
FastMod(h, data.size());
293 data[pos & ~1] = (data[pos & ~1] & ~(uint64_t(1) << bit)) |
294 uint64_t(nGeneration & 1) << bit;
295 data[pos | 1] = (data[pos | 1] & ~(uint64_t(1) << bit)) |
296 uint64_t(nGeneration >> 1) << bit;
309 uint32_t pos =
FastMod(h, data.size());
312 if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) {
326 nEntriesThisGeneration = 0;
328 std::fill(data.begin(), data.end(), 0);
txnouttype Solver(const CScript &scriptPubKey, std::vector< std::vector< uint8_t >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
uint64_t GetRand(uint64_t nMax) noexcept
uint32_t MurmurHash3(uint32_t nHashSeed, const std::vector< uint8_t > &vDataToHash)
static uint32_t RollingBloomHash(uint32_t nHashNum, uint32_t nTweak, const std::vector< uint8_t > &vDataToHash)
bool contains(const std::vector< uint8_t > &vKey) const
Double ended buffer combining vector and stream-like interfaces.
void insert(const std::vector< uint8_t > &vKey)
std::vector< uint8_t > vData
const std::vector< CTxIn > vin
void reset(const uint32_t nNewTweak)
static const uint32_t MAX_HASH_FUNCS
uint32_t Hash(uint32_t nHashNum, const std::vector< uint8_t > &vDataToHash) const
bool MatchAndInsertOutputs(const CTransaction &tx)
Scans output scripts for matches and adds those outpoints to the filter for spend detection...
opcodetype
Script opcodes.
An input of a transaction.
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.
void insert(const std::vector< uint8_t > &vKey)
const_iterator end() const
const_iterator begin() const
A TxId is the identifier of a transaction.
static const int PROTOCOL_VERSION
network protocol versioning
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< uint8_t > &vchRet) const
void UpdateEmptyFull()
Checks for empty and full filters to avoid wasting cpu.
static const uint32_t MAX_BLOOM_FILTER_SIZE
20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
static uint32_t FastMod(uint32_t x, size_t n)
The basic transaction that is broadcasted on the network and contained in blocks. ...
bool contains(const std::vector< uint8_t > &vKey) const
bool MatchInputs(const CTransaction &tx)
Scan inputs to see if the spent outpoints are a match, or the input scripts contain matching elements...
CRollingBloomFilter(const uint32_t nElements, const double nFPRate)
bool IsWithinSizeConstraints() const
True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (c...