17 #include <boost/foreach.hpp>
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)),
44 vData((unsigned int)(-1 /
LN2SQUARED * nElements * log(nFPRate)) / 8),
47 nHashFuncs((unsigned int)(vData.size() * 8 / nElements *
LN2)),
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;
182 BOOST_FOREACH(
const CTxIn& txin, tx.
vin)
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));
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) {
246 return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
257 uint64_t nGenerationMask1 = -(uint64_t)(
nGeneration & 1);
258 uint64_t nGenerationMask2 = -(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;
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;
281 std::vector<unsigned char> vData(hash.
begin(), hash.
end());
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)) {
301 std::vector<unsigned char> vData(hash.
begin(), hash.
end());
310 for (std::vector<uint64_t>::iterator it =
data.begin(); it !=
data.end(); it++) {
@ BLOOM_UPDATE_P2PUBKEY_ONLY
bool IsWithinSizeConstraints() const
True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (c...
unsigned int Hash(unsigned int nHashNum, const std::vector< unsigned char > &vDataToHash) const
void reset(unsigned int nNewTweak)
std::vector< unsigned char > vData
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)
void UpdateEmptyFull()
Checks for empty and full filters to avoid wasting cpu.
bool contains(const std::vector< unsigned char > &vKey) const
Double ended buffer combining vector and stream-like interfaces.
const_iterator begin() const
const_iterator end() const
An outpoint - a combination of a transaction hash and an index n into its vout.
void insert(const std::vector< unsigned char > &vKey)
bool contains(const std::vector< unsigned char > &vKey) const
CRollingBloomFilter(unsigned int nElements, double nFPRate)
int nEntriesPerGeneration
int nEntriesThisGeneration
std::vector< uint64_t > data
bool GetOp(iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet)
The basic transaction that is broadcasted on the network and contained in blocks.
const std::vector< CTxOut > vout
const uint256 & GetHash() const
const std::vector< CTxIn > vin
An input of a transaction.
An output of a transaction.
unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector< unsigned char > &vDataToHash)
uint64_t GetRand(uint64_t nMax)
opcodetype
Script opcodes.
bool Solver(const CScript &scriptPubKey, txnouttype &typeRet, vector< vector< unsigned char > > &vSolutionsRet)
Return public keys or hashes from scriptPubKey, for 'standard' transaction types.