49 #include <ndn-cxx/util/exception.hpp>
53 namespace be = boost::endian;
76 : m_compressionScheme(scheme)
79 size_t nEntries = expectedNumEntries + expectedNumEntries / 2;
81 size_t remainder = nEntries %
N_HASH;
83 nEntries += (
N_HASH - remainder);
86 m_hashTable.resize(nEntries);
92 auto decompressed =
decompress(m_compressionScheme, ibltName.value_bytes());
93 if (decompressed->size() !=
ENTRY_SIZE * m_hashTable.size()) {
94 NDN_THROW(
Error(
"Received IBF cannot be decoded!"));
97 const uint8_t* input = decompressed->data();
98 for (
auto& entry : m_hashTable) {
99 entry.count = be::endian_load<int32_t, sizeof(int32_t), be::order::big>(input);
100 input +=
sizeof(entry.count);
102 entry.keySum = be::endian_load<uint32_t, sizeof(uint32_t), be::order::big>(input);
103 input +=
sizeof(entry.keySum);
105 entry.keyCheck = be::endian_load<uint32_t, sizeof(uint32_t), be::order::big>(input);
106 input +=
sizeof(entry.keyCheck);
111 ibltUpdate(std::vector<HashTableEntry>& ht, int32_t plusOrMinus, uint32_t key)
113 size_t bucketsPerHash = ht.size() /
N_HASH;
115 for (
size_t i = 0; i <
N_HASH; i++) {
116 size_t startEntry = i * bucketsPerHash;
119 entry.
count += plusOrMinus;
128 ibltUpdate(m_hashTable, 1, key);
134 ibltUpdate(m_hashTable, -1, key);
140 std::vector<uint8_t> buffer(
ENTRY_SIZE * m_hashTable.size());
141 uint8_t* output = buffer.data();
142 for (
const auto& entry : m_hashTable) {
143 be::endian_store<int32_t, sizeof(int32_t), be::order::big>(output, entry.
count);
144 output +=
sizeof(entry.
count);
146 be::endian_store<uint32_t, sizeof(uint32_t), be::order::big>(output, entry.
keySum);
147 output +=
sizeof(entry.
keySum);
149 be::endian_store<uint32_t, sizeof(uint32_t), be::order::big>(output, entry.
keyCheck);
153 auto compressed =
compress(m_compressionScheme, buffer);
154 name.append(ndn::name::Component(std::move(compressed)));
160 os <<
"count keySum keyCheckMatch\n";
174 BOOST_ASSERT(lht.size() == rht.size());
176 std::vector<HashTableEntry> peeled(lht.size());
177 std::transform(lht.begin(), lht.end(), rht.begin(), peeled.begin(),
180 diff.count = lhe.count - rhe.count;
181 diff.keySum = lhe.keySum ^ rhe.keySum;
182 diff.keyCheck = lhe.keyCheck ^ rhe.keyCheck;
187 std::set<uint32_t> positive;
188 std::set<uint32_t> negative;
193 for (
const auto& entry : peeled) {
195 if (entry.
count == 1) {
196 positive.insert(entry.
keySum);
199 negative.insert(entry.
keySum);
205 }
while (nErased > 0);
209 bool canDecode = std::all_of(peeled.begin(), peeled.end(),
211 return {canDecode, std::move(positive), std::move(negative)};
Invertible Bloom Lookup Table (Invertible Bloom Filter)
IBLT(size_t expectedNumEntries, CompressionScheme scheme)
constructor
void insert(uint32_t key)
const std::vector< HashTableEntry > & getHashTable() const
void initialize(const ndn::name::Component &ibltName)
Populate the hash table using the vector representation of IBLT.
void appendToName(ndn::Name &name) const
Appends self to name.
uint32_t murmurHash3(const void *key, size_t len, uint32_t seed)
constexpr size_t N_HASHCHECK
std::ostream & operator<<(std::ostream &os, const IBLT &iblt)
IBLTDiff operator-(const IBLT &lhs, const IBLT &rhs)
Compute the difference between two IBLTs.
std::shared_ptr< ndn::Buffer > compress(CompressionScheme scheme, ndn::span< const uint8_t > buffer)
std::shared_ptr< ndn::Buffer > decompress(CompressionScheme scheme, ndn::span< const uint8_t > buffer)
constexpr size_t ENTRY_SIZE