49 #include <ndn-cxx/util/exception.hpp>
60 static const std::size_t bits_per_char = 0x08;
62 static const unsigned char bit_mask[bits_per_char] = {
73 class bloom_parameters
79 maximum_size(std::numeric_limits<unsigned int>::max()),
80 minimum_number_of_hashes(1),
81 maximum_number_of_hashes(std::numeric_limits<unsigned int>::max()),
82 projected_element_count(200),
83 false_positive_probability(1.0 / projected_element_count),
84 random_seed(0xA5A5A5A55A5A5A5AULL)
87 inline bool operator!()
89 return (minimum_size > maximum_size) ||
90 (minimum_number_of_hashes > maximum_number_of_hashes) ||
91 (minimum_number_of_hashes < 1) ||
92 (0 == maximum_number_of_hashes) ||
93 (0 == projected_element_count) ||
94 (false_positive_probability < 0.0) ||
95 (std::numeric_limits<double>::infinity() == std::abs(false_positive_probability)) ||
97 (0xFFFFFFFFFFFFFFFFULL == random_seed);
101 unsigned int minimum_size;
102 unsigned int maximum_size;
105 unsigned int minimum_number_of_hashes;
106 unsigned int maximum_number_of_hashes;
111 unsigned int projected_element_count;
116 double false_positive_probability;
118 unsigned long long int random_seed;
120 struct optimal_parameters_t
122 optimal_parameters_t()
123 : number_of_hashes(0),
127 unsigned int number_of_hashes;
128 unsigned int table_size;
131 optimal_parameters_t optimal_parameters;
133 bool compute_optimal_parameters()
146 double min_m = std::numeric_limits<double>::infinity();
152 const double numerator = (- k * projected_element_count);
153 const double denominator = std::log(1.0 - std::pow(false_positive_probability, 1.0 / k));
155 const double curr_m = numerator / denominator;
166 optimal_parameters_t& optp = optimal_parameters;
168 optp.number_of_hashes =
static_cast<unsigned int>(min_k);
170 optp.table_size =
static_cast<unsigned int>(min_m);
172 optp.table_size += (((optp.table_size % bits_per_char) != 0) ? (bits_per_char - (optp.table_size % bits_per_char)) : 0);
174 if (optp.number_of_hashes < minimum_number_of_hashes)
175 optp.number_of_hashes = minimum_number_of_hashes;
176 else if (optp.number_of_hashes > maximum_number_of_hashes)
177 optp.number_of_hashes = maximum_number_of_hashes;
179 if (optp.table_size < minimum_size)
180 optp.table_size = minimum_size;
181 else if (optp.table_size > maximum_size)
182 optp.table_size = maximum_size;
191 : projected_element_count_(p.projected_element_count),
192 inserted_element_count_(0),
193 random_seed_((p.random_seed * 0xA5A5A5A5) + 1),
194 desired_false_positive_probability_(p.false_positive_probability)
196 salt_count_ = p.optimal_parameters.number_of_hashes;
197 table_size_ = p.optimal_parameters.table_size;
199 generate_unique_salt();
201 bit_table_.resize(table_size_ / bits_per_char,
static_cast<cell_type
>(0x00));
204 static bloom_parameters
205 makeParameters(
unsigned int projected_element_count,
206 double false_positive_probability)
209 p.projected_element_count = projected_element_count;
210 p.false_positive_probability = false_positive_probability;
212 if (!p.compute_optimal_parameters()) {
219 double false_positive_probability)
220 :
BloomFilter(makeParameters(projected_element_count, false_positive_probability))
225 double false_positive_probability,
226 const ndn::name::Component& bfName)
227 :
BloomFilter(projected_element_count, false_positive_probability)
229 std::vector<cell_type> table(bfName.value_begin(), bfName.value_end());
230 if (table.size() != table_size_ / bits_per_char) {
231 NDN_THROW(
Error(
"Bloom filter cannot be decoded!"));
233 bit_table_ = std::move(table);
239 name.appendNumber(projected_element_count_);
240 name.appendNumber(
static_cast<uint64_t
>(desired_false_positive_probability_ * 1000));
241 name.append(bit_table_.begin(), bit_table_.end());
247 std::fill(bit_table_.begin(), bit_table_.end(),
static_cast<cell_type
>(0x00));
248 inserted_element_count_ = 0;
254 std::size_t bit_index = 0;
257 for (std::size_t i = 0; i < salt_.size(); ++i)
259 compute_indices(
murmurHash3(salt_[i], key), bit_index, bit);
261 bit_table_[bit_index / bits_per_char] |= bit_mask[bit];
264 ++inserted_element_count_;
270 std::size_t bit_index = 0;
273 for (std::size_t i = 0; i < salt_.size(); ++i)
275 compute_indices(
murmurHash3(salt_[i], key), bit_index, bit);
277 if ((bit_table_[bit_index / bits_per_char] & bit_mask[bit]) != bit_mask[bit])
287 BloomFilter::compute_indices(
const bloom_type& hash, std::size_t& bit_index, std::size_t& bit)
const
289 bit_index = hash % table_size_;
290 bit = bit_index % bits_per_char;
294 BloomFilter::generate_unique_salt()
302 const unsigned int predef_salt_count = 128;
304 static const bloom_type predef_salt[predef_salt_count] =
306 0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
307 0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
308 0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
309 0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
310 0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
311 0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
312 0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
313 0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
314 0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
315 0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
316 0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
317 0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
318 0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
319 0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
320 0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
321 0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
322 0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
323 0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
324 0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
325 0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
326 0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
327 0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
328 0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
329 0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
330 0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
331 0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
332 0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
333 0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
334 0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
335 0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
336 0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
337 0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
340 if (salt_count_ <= predef_salt_count)
342 std::copy(predef_salt,
343 predef_salt + salt_count_,
344 std::back_inserter(salt_));
346 for (std::size_t i = 0; i < salt_.size(); ++i)
354 salt_[i] = salt_[i] * salt_[(i + 3) % salt_.size()] +
static_cast<bloom_type
>(random_seed_);
359 std::copy(predef_salt, predef_salt + predef_salt_count, std::back_inserter(salt_));
361 srand(
static_cast<unsigned int>(random_seed_));
363 while (salt_.size() < salt_count_)
365 bloom_type current_salt =
static_cast<bloom_type
>(rand()) *
static_cast<bloom_type
>(rand());
367 if (0 == current_salt)
370 if (salt_.end() == std::find(salt_.begin(), salt_.end(), current_salt))
372 salt_.push_back(current_salt);
void insert(const ndn::Name &key)
void appendToName(ndn::Name &name) const
Append our bloom filter to the given name.
bool contains(const ndn::Name &key) const
uint32_t murmurHash3(const void *key, size_t len, uint32_t seed)