Changeset View
Changeset View
Standalone View
Standalone View
src/blockfilter.cpp
Show First 20 Lines • Show All 74 Lines • ▼ Show 20 Lines | #else | ||||
uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF); | uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF); | ||||
uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32); | uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32); | ||||
return upper64; | return upper64; | ||||
#endif | #endif | ||||
} | } | ||||
uint64_t GCSFilter::HashToRange(const Element &element) const { | uint64_t GCSFilter::HashToRange(const Element &element) const { | ||||
uint64_t hash = CSipHasher(m_siphash_k0, m_siphash_k1) | uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1) | ||||
.Write(element.data(), element.size()) | .Write(element.data(), element.size()) | ||||
.Finalize(); | .Finalize(); | ||||
return MapIntoRange(hash, m_F); | return MapIntoRange(hash, m_F); | ||||
} | } | ||||
std::vector<uint64_t> | std::vector<uint64_t> | ||||
GCSFilter::BuildHashedSet(const ElementSet &elements) const { | GCSFilter::BuildHashedSet(const ElementSet &elements) const { | ||||
std::vector<uint64_t> hashed_elements; | std::vector<uint64_t> hashed_elements; | ||||
hashed_elements.reserve(elements.size()); | hashed_elements.reserve(elements.size()); | ||||
for (const Element &element : elements) { | for (const Element &element : elements) { | ||||
hashed_elements.push_back(HashToRange(element)); | hashed_elements.push_back(HashToRange(element)); | ||||
} | } | ||||
std::sort(hashed_elements.begin(), hashed_elements.end()); | std::sort(hashed_elements.begin(), hashed_elements.end()); | ||||
return hashed_elements; | return hashed_elements; | ||||
} | } | ||||
GCSFilter::GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, | GCSFilter::GCSFilter(const Params ¶ms) | ||||
uint32_t M) | : m_params(params), m_N(0), m_F(0), m_encoded{0} {} | ||||
: m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M), | |||||
m_N(0), m_F(0) {} | |||||
GCSFilter::GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, | |||||
uint32_t M, std::vector<uint8_t> encoded_filter) | |||||
: GCSFilter(siphash_k0, siphash_k1, P, M) { | |||||
m_encoded = std::move(encoded_filter); | |||||
GCSFilter::GCSFilter(const Params ¶ms, std::vector<uint8_t> encoded_filter) | |||||
: m_params(params), m_encoded(std::move(encoded_filter)) { | |||||
VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); | VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); | ||||
uint64_t N = ReadCompactSize(stream); | uint64_t N = ReadCompactSize(stream); | ||||
m_N = static_cast<uint32_t>(N); | m_N = static_cast<uint32_t>(N); | ||||
if (m_N != N) { | if (m_N != N) { | ||||
throw std::ios_base::failure("N must be <2^32"); | throw std::ios_base::failure("N must be <2^32"); | ||||
} | } | ||||
m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_M); | m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M); | ||||
// Verify that the encoded filter contains exactly N elements. If it has too | // Verify that the encoded filter contains exactly N elements. If it has too | ||||
// much or too little data, a std::ios_base::failure exception will be | // much or too little data, a std::ios_base::failure exception will be | ||||
// raised. | // raised. | ||||
BitStreamReader<VectorReader> bitreader(stream); | BitStreamReader<VectorReader> bitreader(stream); | ||||
for (uint64_t i = 0; i < m_N; ++i) { | for (uint64_t i = 0; i < m_N; ++i) { | ||||
GolombRiceDecode(bitreader, m_P); | GolombRiceDecode(bitreader, m_params.m_P); | ||||
} | } | ||||
if (!stream.empty()) { | if (!stream.empty()) { | ||||
throw std::ios_base::failure("encoded_filter contains excess data"); | throw std::ios_base::failure("encoded_filter contains excess data"); | ||||
} | } | ||||
} | } | ||||
GCSFilter::GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, | GCSFilter::GCSFilter(const Params ¶ms, const ElementSet &elements) | ||||
uint32_t M, const ElementSet &elements) | : m_params(params) { | ||||
: GCSFilter(siphash_k0, siphash_k1, P, M) { | |||||
size_t N = elements.size(); | size_t N = elements.size(); | ||||
m_N = static_cast<uint32_t>(N); | m_N = static_cast<uint32_t>(N); | ||||
if (m_N != N) { | if (m_N != N) { | ||||
throw std::invalid_argument("N must be <2^32"); | throw std::invalid_argument("N must be <2^32"); | ||||
} | } | ||||
m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_M); | m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M); | ||||
CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); | CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); | ||||
WriteCompactSize(stream, m_N); | WriteCompactSize(stream, m_N); | ||||
if (elements.empty()) { | if (elements.empty()) { | ||||
return; | return; | ||||
} | } | ||||
BitStreamWriter<CVectorWriter> bitwriter(stream); | BitStreamWriter<CVectorWriter> bitwriter(stream); | ||||
uint64_t last_value = 0; | uint64_t last_value = 0; | ||||
for (uint64_t value : BuildHashedSet(elements)) { | for (uint64_t value : BuildHashedSet(elements)) { | ||||
uint64_t delta = value - last_value; | uint64_t delta = value - last_value; | ||||
GolombRiceEncode(bitwriter, m_P, delta); | GolombRiceEncode(bitwriter, m_params.m_P, delta); | ||||
last_value = value; | last_value = value; | ||||
} | } | ||||
bitwriter.Flush(); | bitwriter.Flush(); | ||||
} | } | ||||
bool GCSFilter::MatchInternal(const uint64_t *element_hashes, | bool GCSFilter::MatchInternal(const uint64_t *element_hashes, | ||||
size_t size) const { | size_t size) const { | ||||
VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); | VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); | ||||
// Seek forward by size of N | // Seek forward by size of N | ||||
uint64_t N = ReadCompactSize(stream); | uint64_t N = ReadCompactSize(stream); | ||||
assert(N == m_N); | assert(N == m_N); | ||||
BitStreamReader<VectorReader> bitreader(stream); | BitStreamReader<VectorReader> bitreader(stream); | ||||
uint64_t value = 0; | uint64_t value = 0; | ||||
size_t hashes_index = 0; | size_t hashes_index = 0; | ||||
for (uint32_t i = 0; i < m_N; ++i) { | for (uint32_t i = 0; i < m_N; ++i) { | ||||
uint64_t delta = GolombRiceDecode(bitreader, m_P); | uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P); | ||||
value += delta; | value += delta; | ||||
while (true) { | while (true) { | ||||
if (hashes_index == size) { | if (hashes_index == size) { | ||||
return false; | return false; | ||||
} else if (element_hashes[hashes_index] == value) { | } else if (element_hashes[hashes_index] == value) { | ||||
return true; | return true; | ||||
} else if (element_hashes[hashes_index] > value) { | } else if (element_hashes[hashes_index] > value) { | ||||
Show All 39 Lines | for (const CTxUndo &tx_undo : block_undo.vtxundo) { | ||||
} | } | ||||
elements.emplace(script.begin(), script.end()); | elements.emplace(script.begin(), script.end()); | ||||
} | } | ||||
} | } | ||||
return elements; | return elements; | ||||
} | } | ||||
BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256 &block_hash, | |||||
std::vector<uint8_t> filter) | |||||
: m_filter_type(filter_type), m_block_hash(block_hash) { | |||||
GCSFilter::Params params; | |||||
if (!BuildParams(params)) { | |||||
throw std::invalid_argument("unknown filter_type"); | |||||
} | |||||
m_filter = GCSFilter(params, std::move(filter)); | |||||
} | |||||
BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock &block, | BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock &block, | ||||
const CBlockUndo &block_undo) | const CBlockUndo &block_undo) | ||||
: m_filter_type(filter_type), m_block_hash(block.GetHash()) { | : m_filter_type(filter_type), m_block_hash(block.GetHash()) { | ||||
GCSFilter::Params params; | |||||
if (!BuildParams(params)) { | |||||
throw std::invalid_argument("unknown filter_type"); | |||||
} | |||||
m_filter = GCSFilter(params, BasicFilterElements(block, block_undo)); | |||||
} | |||||
bool BlockFilter::BuildParams(GCSFilter::Params ¶ms) const { | |||||
switch (m_filter_type) { | switch (m_filter_type) { | ||||
case BlockFilterType::BASIC: | case BlockFilterType::BASIC: | ||||
m_filter = | params.m_siphash_k0 = m_block_hash.GetUint64(0); | ||||
GCSFilter(m_block_hash.GetUint64(0), m_block_hash.GetUint64(1), | params.m_siphash_k1 = m_block_hash.GetUint64(1); | ||||
BASIC_FILTER_P, BASIC_FILTER_M, | params.m_P = BASIC_FILTER_P; | ||||
BasicFilterElements(block, block_undo)); | params.m_M = BASIC_FILTER_M; | ||||
break; | return true; | ||||
default: | |||||
throw std::invalid_argument("unknown filter_type"); | |||||
} | } | ||||
return false; | |||||
} | } | ||||
uint256 BlockFilter::GetHash() const { | uint256 BlockFilter::GetHash() const { | ||||
const std::vector<uint8_t> &data = GetEncodedFilter(); | const std::vector<uint8_t> &data = GetEncodedFilter(); | ||||
uint256 result; | uint256 result; | ||||
CHash256().Write(data.data(), data.size()).Finalize(result.begin()); | CHash256().Write(data.data(), data.size()).Finalize(result.begin()); | ||||
return result; | return result; | ||||
Show All 12 Lines |