 |
Bitcoin Core
21.99.0
P2P Digital Currency
|
Go to the documentation of this file.
34 #ifdef __SIZEOF_INT128__
35 return (
static_cast<unsigned __int128
>(x) *
static_cast<unsigned __int128
>(n)) >> 64;
42 uint64_t x_hi = x >> 32;
43 uint64_t x_lo = x & 0xFFFFFFFF;
44 uint64_t n_hi = n >> 32;
45 uint64_t n_lo = n & 0xFFFFFFFF;
47 uint64_t ac = x_hi * n_hi;
48 uint64_t ad = x_hi * n_lo;
49 uint64_t bc = x_lo * n_hi;
50 uint64_t bd = x_lo * n_lo;
52 uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
53 uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
61 .
Write(element.data(), element.size())
68 std::vector<uint64_t> hashed_elements;
69 hashed_elements.reserve(elements.size());
70 for (
const Element& element : elements) {
73 std::sort(hashed_elements.begin(), hashed_elements.end());
74 return hashed_elements;
78 : m_params(params), m_N(0), m_F(0), m_encoded{0}
82 : m_params(params), m_encoded(std::move(encoded_filter))
87 m_N =
static_cast<uint32_t
>(N);
89 throw std::ios_base::failure(
"N must be <2^32");
96 for (uint64_t i = 0; i <
m_N; ++i) {
99 if (!stream.
empty()) {
100 throw std::ios_base::failure(
"encoded_filter contains excess data");
107 size_t N = elements.size();
108 m_N =
static_cast<uint32_t
>(N);
110 throw std::invalid_argument(
"N must be <2^32");
118 if (elements.empty()) {
124 uint64_t last_value = 0;
126 uint64_t delta = value - last_value;
145 size_t hashes_index = 0;
146 for (uint32_t i = 0; i <
m_N; ++i) {
151 if (hashes_index == size) {
153 }
else if (element_hashes[hashes_index] == value) {
155 }
else if (element_hashes[hashes_index] > value) {
180 static std::string unknown_retval =
"";
187 if (entry.second ==
name) {
188 filter_type = entry.first;
197 static std::set<BlockFilterType> types;
199 static std::once_flag flag;
200 std::call_once(flag, []() {
202 types.insert(entry.first);
211 static std::string type_list;
213 static std::once_flag flag;
214 std::call_once(flag, []() {
215 std::stringstream ret;
218 if (!first) ret <<
", ";
222 type_list = ret.str();
234 for (
const CTxOut& txout : tx->vout) {
237 elements.emplace(script.
begin(), script.
end());
244 if (script.
empty())
continue;
245 elements.emplace(script.
begin(), script.
end());
253 std::vector<unsigned char> filter)
254 : m_filter_type(filter_type), m_block_hash(block_hash)
258 throw std::invalid_argument(
"unknown filter_type");
264 : m_filter_type(filter_type), m_block_hash(block.GetHash())
268 throw std::invalid_argument(
"unknown filter_type");
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
bool BuildParams(GCSFilter::Params ¶ms) const
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
uint64_t m_F
Range of element hashes, F = N * M.
bool Match(const Element &element) const
Checks if the element may be in the set.
void Flush()
Flush any unwritten bits to the output stream, padding with 0's to the next byte boundary.
constexpr uint32_t BASIC_FILTER_M
CHash256 & Write(Span< const unsigned char > input)
Undo information for a CTransaction.
static uint64_t MapIntoRange(uint64_t x, uint64_t n)
const std::vector< unsigned char > & GetEncodedFilter() const
static const std::map< BlockFilterType, std::string > g_filter_types
uint64_t GetUint64(int pos) const
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
uint64_t ReadCompactSize(Stream &is, bool range_check=true)
Decode a CompactSize-encoded variable-length integer.
std::shared_ptr< const CTransaction > CTransactionRef
GCSFilter(const Params ¶ms=Params())
Constructs an empty filter.
Minimal stream for reading from an existing vector by reference.
std::vector< CTxUndo > vtxundo
CTxOut out
unspent transaction output
uint32_t m_M
Inverse false positive rate.
This implements a Golomb-coded set as defined in BIP 158.
uint8_t m_P
Golomb-Rice coding parameter.
An output of a transaction.
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
bool MatchInternal(const uint64_t *sorted_element_hashes, size_t size) const
Helper method used to implement Match and MatchAny.
std::vector< unsigned char > m_encoded
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
void Finalize(Span< unsigned char > output)
uint32_t m_N
Number of elements in the filter.
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
static GCSFilter::ElementSet BasicFilterElements(const CBlock &block, const CBlockUndo &block_undo)
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
Serialized script, used inside transaction inputs and outputs.
uint256 GetHash() const
Compute the filter hash.
uint64_t HashToRange(const Element &element) const
Hash a data element to an integer in the range [0, N * M).
std::vector< Coin > vprevout
std::vector< CTransactionRef > vtx
BlockFilterType m_filter_type
std::unordered_set< Element, ByteVectorHash > ElementSet
static constexpr int GCS_SER_VERSION
Protocol version used to serialize parameters in GCS filter encoding.
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
constexpr uint8_t BASIC_FILTER_P
A hasher class for Bitcoin's 256-bit hash (double SHA-256).
static constexpr int GCS_SER_TYPE
SerType used to serialize parameters in GCS filter encoding.
std::vector< unsigned char > Element
assert(std::addressof(::ChainstateActive().CoinsTip())==std::addressof(coins_cache))
Undo information for a CBlock.
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data It is treated as if this was the little-endian interpretation of ...