PSync: initial commit
refs: #4641
Change-Id: Iabed3ad7632544d97559e6798547b7972b416784
diff --git a/src/detail/bloom-filter.cpp b/src/detail/bloom-filter.cpp
new file mode 100644
index 0000000..b74a00b
--- /dev/null
+++ b/src/detail/bloom-filter.cpp
@@ -0,0 +1,349 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+
+ * The MIT License (MIT)
+
+ * Copyright (c) 2000 Arash Partow
+
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+*/
+
+#include "bloom-filter.hpp"
+#include "util.hpp"
+
+#include <ndn-cxx/util/logger.hpp>
+
+#include <algorithm>
+#include <cmath>
+#include <cstddef>
+#include <iterator>
+#include <limits>
+#include <cstdlib>
+
+// https://github.com/ArashPartow/bloom
+
+NDN_LOG_INIT(psync.BloomFilter);
+
+namespace psync {
+
+static const std::size_t bits_per_char = 0x08;
+static const unsigned char bit_mask[bits_per_char] = {
+ 0x01, //00000001
+ 0x02, //00000010
+ 0x04, //00000100
+ 0x08, //00001000
+ 0x10, //00010000
+ 0x20, //00100000
+ 0x40, //01000000
+ 0x80 //10000000
+};
+
+BloomParameters::BloomParameters()
+: minimum_size(1)
+, maximum_size(std::numeric_limits<unsigned int>::max())
+, minimum_number_of_hashes(1)
+, maximum_number_of_hashes(std::numeric_limits<unsigned int>::max())
+, projected_element_count(200)
+, false_positive_probability(1.0 / projected_element_count)
+, random_seed(0xA5A5A5A55A5A5A5AULL)
+{}
+
+bool
+BloomParameters::compute_optimal_parameters()
+{
+ if (!(*this)) {
+ return false;
+ }
+
+ double min_m = std::numeric_limits<double>::infinity();
+ double min_k = 0.0;
+ double curr_m = 0.0;
+ double k = 1.0;
+
+ while (k < 1000.0)
+ {
+ double numerator = (- k * projected_element_count);
+ double denominator = std::log(1.0 - std::pow(false_positive_probability, 1.0 / k));
+ curr_m = numerator / denominator;
+ if (curr_m < min_m)
+ {
+ min_m = curr_m;
+ min_k = k;
+ }
+ k += 1.0;
+ }
+
+ optimal_parameters_t& optp = optimal_parameters;
+
+ optp.number_of_hashes = static_cast<unsigned int>(min_k);
+ optp.table_size = static_cast<unsigned int>(min_m);
+ optp.table_size += (((optp.table_size % bits_per_char) != 0) ? (bits_per_char - (optp.table_size % bits_per_char)) : 0);
+
+ if (optp.number_of_hashes < minimum_number_of_hashes)
+ optp.number_of_hashes = minimum_number_of_hashes;
+ else if (optp.number_of_hashes > maximum_number_of_hashes)
+ optp.number_of_hashes = maximum_number_of_hashes;
+
+ if (optp.table_size < minimum_size)
+ optp.table_size = minimum_size;
+ else if (optp.table_size > maximum_size)
+ optp.table_size = maximum_size;
+
+ return true;
+}
+
+BloomFilter::BloomFilter()
+ : bit_table_(0)
+ , salt_count_(0)
+ , table_size_(0)
+ , raw_table_size_(0)
+ , projected_element_count_(0)
+ , inserted_element_count_(0)
+ , random_seed_(0)
+ , desired_false_positive_probability_(0.0)
+{}
+
+BloomFilter::BloomFilter(const BloomParameters& p)
+ : bit_table_(0)
+ , projected_element_count_(p.projected_element_count)
+ , inserted_element_count_(0)
+ , random_seed_((p.random_seed * 0xA5A5A5A5) + 1)
+ , desired_false_positive_probability_(p.false_positive_probability)
+{
+ salt_count_ = p.optimal_parameters.number_of_hashes;
+ table_size_ = p.optimal_parameters.table_size;
+ generate_unique_salt();
+ raw_table_size_ = table_size_ / bits_per_char;
+ //bit_table_ = new cell_type[static_cast<std::size_t>(raw_table_size_)];
+ bit_table_.resize(static_cast<std::size_t>(raw_table_size_), 0x00);
+}
+
+BloomFilter::BloomFilter(unsigned int projected_element_count,
+ double false_positive_probability)
+ : BloomFilter(getParameters(projected_element_count, false_positive_probability))
+{
+}
+
+BloomFilter::BloomFilter(unsigned int projected_element_count,
+ double false_positive_probability,
+ const ndn::name::Component& bfName)
+ : BloomFilter(projected_element_count, false_positive_probability)
+{
+ std::vector<BloomFilter::cell_type> table(bfName.value_begin(), bfName.value_end());
+
+ if (table.size() != raw_table_size_) {
+ BOOST_THROW_EXCEPTION(Error("Received BloomFilter cannot be decoded!"));
+ }
+ bit_table_ = table;
+}
+
+BloomParameters
+BloomFilter::getParameters(unsigned int projected_element_count,
+ double false_positive_probability)
+{
+ BloomParameters opt;
+ opt.false_positive_probability = false_positive_probability;
+ opt.projected_element_count = projected_element_count;
+
+ if (!opt) {
+ NDN_LOG_WARN("Bloom parameters are not correct!");
+ }
+
+ opt.compute_optimal_parameters();
+ return opt;
+}
+
+void
+BloomFilter::appendToName(ndn::Name& name) const
+{
+ name.appendNumber(projected_element_count_);
+ name.appendNumber((int)(desired_false_positive_probability_ * 1000));
+ name.append(bit_table_.begin(), bit_table_.end());
+}
+
+void
+BloomFilter::clear()
+{
+ bit_table_.resize(static_cast<std::size_t>(raw_table_size_), 0x00);
+ inserted_element_count_ = 0;
+}
+
+void
+BloomFilter::insert(const std::string& key)
+{
+ std::size_t bit_index = 0;
+ std::size_t bit = 0;
+ for (std::size_t i = 0; i < salt_.size(); ++i)
+ {
+ compute_indices(murmurHash3(salt_[i], key), bit_index, bit);
+ bit_table_[bit_index/bits_per_char] |= bit_mask[bit];
+ }
+ ++inserted_element_count_;
+}
+
+bool
+BloomFilter::contains(const std::string& key) const
+{
+ std::size_t bit_index = 0;
+ std::size_t bit = 0;
+
+ for (std::size_t i = 0; i < salt_.size(); ++i)
+ {
+ compute_indices(murmurHash3(salt_[i], key), bit_index, bit);
+ if ((bit_table_[bit_index/bits_per_char] & bit_mask[bit]) != bit_mask[bit]) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+std::vector <BloomFilter::cell_type>
+BloomFilter::table() const
+{
+ return bit_table_;
+}
+
+void
+BloomFilter::generate_unique_salt()
+{
+ /*
+ Note:
+ A distinct hash function need not be implementation-wise
+ distinct. In the current implementation "seeding" a common
+ hash function with different values seems to be adequate.
+ */
+ const unsigned int predef_salt_count = 128;
+ static const bloom_type predef_salt[predef_salt_count] =
+ {
+ 0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
+ 0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
+ 0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
+ 0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
+ 0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
+ 0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
+ 0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
+ 0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
+ 0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
+ 0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
+ 0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
+ 0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
+ 0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
+ 0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
+ 0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
+ 0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
+ 0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
+ 0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
+ 0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
+ 0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
+ 0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
+ 0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
+ 0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
+ 0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
+ 0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
+ 0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
+ 0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
+ 0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
+ 0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
+ 0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
+ 0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
+ 0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
+ };
+
+ if (salt_count_ <= predef_salt_count)
+ {
+ std::copy(predef_salt,
+ predef_salt + salt_count_,
+ std::back_inserter(salt_));
+ for (unsigned int i = 0; i < salt_.size(); ++i)
+ {
+ salt_[i] = salt_[i] * salt_[(i + 3) % salt_.size()] + static_cast<bloom_type>(random_seed_);
+ }
+ }
+ else
+ {
+ std::copy(predef_salt,predef_salt + predef_salt_count,std::back_inserter(salt_));
+ srand(static_cast<unsigned int>(random_seed_));
+ while (salt_.size() < salt_count_)
+ {
+ bloom_type current_salt = static_cast<bloom_type>(rand()) * static_cast<bloom_type>(rand());
+ if (0 == current_salt) continue;
+ if (salt_.end() == std::find(salt_.begin(), salt_.end(), current_salt))
+ {
+ salt_.push_back(current_salt);
+ }
+ }
+ }
+}
+
+void
+BloomFilter::compute_indices(const bloom_type& hash,
+ std::size_t& bit_index, std::size_t& bit) const
+{
+ bit_index = hash % table_size_;
+ bit = bit_index % bits_per_char;
+}
+
+bool
+operator==(const BloomFilter& bf1, const BloomFilter& bf2)
+{
+ auto table1 = bf1.table();
+ auto table2 = bf2.table();
+
+ if (table1.size() != table2.size()) {
+ return false;
+ }
+
+ for (size_t i = 0; i < table1.size(); i++) {
+ if (table1[i] != table2[i]) {
+ return false;
+ }
+ }
+ return true;
+}
+
+std::ostream&
+operator<<(std::ostream& out, const BloomFilter& bf)
+{
+ for (const auto& element : bf.table()) {
+ out << unsigned(element);
+ }
+ return out;
+}
+
+} // namespace psync
\ No newline at end of file
diff --git a/src/detail/bloom-filter.hpp b/src/detail/bloom-filter.hpp
new file mode 100644
index 0000000..319f1c1
--- /dev/null
+++ b/src/detail/bloom-filter.hpp
@@ -0,0 +1,180 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+
+ * The MIT License (MIT)
+
+ * Copyright (c) 2000 Arash Partow
+
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+*/
+
+#ifndef PSYNC_BLOOM_FILTER_HPP
+#define PSYNC_BLOOM_FILTER_HPP
+
+#include <ndn-cxx/name.hpp>
+
+#include <string>
+#include <vector>
+#include <cmath>
+#include <cstdlib>
+
+namespace psync {
+
+struct optimal_parameters_t
+{
+ optimal_parameters_t()
+ : number_of_hashes(0),
+ table_size(0)
+ {}
+
+ unsigned int number_of_hashes;
+ unsigned int table_size;
+};
+
+class BloomParameters
+{
+public:
+ BloomParameters();
+
+ bool
+ compute_optimal_parameters();
+
+ bool operator!() const
+ {
+ return (minimum_size > maximum_size) ||
+ (minimum_number_of_hashes > maximum_number_of_hashes) ||
+ (minimum_number_of_hashes < 1) ||
+ (0 == maximum_number_of_hashes) ||
+ (0 == projected_element_count) ||
+ (false_positive_probability < 0.0) ||
+ (std::numeric_limits<double>::infinity() == std::abs(false_positive_probability)) ||
+ (0 == random_seed) ||
+ (0xFFFFFFFFFFFFFFFFULL == random_seed);
+ }
+
+ unsigned int minimum_size;
+ unsigned int maximum_size;
+ unsigned int minimum_number_of_hashes;
+ unsigned int maximum_number_of_hashes;
+ unsigned int projected_element_count;
+ double false_positive_probability;
+ unsigned long long int random_seed;
+ optimal_parameters_t optimal_parameters;
+};
+
+class BloomFilter
+{
+protected:
+ typedef uint32_t bloom_type;
+ typedef uint8_t cell_type;
+ typedef std::vector <cell_type>::iterator Iterator;
+
+public:
+ class Error : public std::runtime_error
+ {
+ public:
+ using std::runtime_error::runtime_error;
+ };
+
+ BloomFilter();
+
+ explicit BloomFilter(const BloomParameters& p);
+
+ BloomFilter(unsigned int projected_element_count,
+ double false_positive_probability);
+
+ BloomFilter(unsigned int projected_element_count,
+ double false_positive_probability,
+ const ndn::name::Component& bfName);
+
+ BloomParameters
+ getParameters(unsigned int projected_element_count,
+ double false_positive_probability);
+
+ /**
+ * @brief Append our bloom filter to the given name
+ *
+ * Append the count and false positive probability
+ * along with the bloom filter so that producer (PartialProducer) can construct a copy.
+ *
+ * @param name append bloom filter to this name
+ */
+ void
+ appendToName(ndn::Name& name) const;
+
+ void
+ clear();
+
+ void
+ insert(const std::string& key);
+
+ bool
+ contains(const std::string& key) const;
+
+ std::vector<cell_type>
+ table() const;
+
+private:
+ void
+ generate_unique_salt();
+
+ void
+ compute_indices(const bloom_type& hash,
+ std::size_t& bit_index, std::size_t& bit) const;
+
+private:
+ std::vector <bloom_type> salt_;
+ std::vector <cell_type> bit_table_;
+ unsigned int salt_count_;
+ unsigned int table_size_; // 8 * raw_table_size;
+ unsigned int raw_table_size_;
+ unsigned int projected_element_count_;
+ unsigned int inserted_element_count_;
+ unsigned long long int random_seed_;
+ double desired_false_positive_probability_;
+};
+
+bool
+operator==(const BloomFilter& bf1, const BloomFilter& bf2);
+
+std::ostream&
+operator<<(std::ostream& out, const BloomFilter& bf);
+
+} // namespace psync
+
+#endif // PSYNC_BLOOM_FILTER_HPP
\ No newline at end of file
diff --git a/src/detail/iblt.cpp b/src/detail/iblt.cpp
new file mode 100644
index 0000000..495c232
--- /dev/null
+++ b/src/detail/iblt.cpp
@@ -0,0 +1,277 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+
+ * The MIT License (MIT)
+
+ * Copyright (c) 2014 Gavin Andresen
+
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+*/
+
+#include "iblt.hpp"
+#include "util.hpp"
+
+#include <sstream>
+
+namespace psync {
+
+const size_t N_HASH(3);
+const size_t N_HASHCHECK(11);
+
+bool
+HashTableEntry::isPure() const
+{
+ if (count == 1 || count == -1) {
+ uint32_t check = murmurHash3(N_HASHCHECK, keySum);
+ return keyCheck == check;
+ }
+
+ return false;
+}
+
+bool
+HashTableEntry::isEmpty() const
+{
+ return count == 0 && keySum == 0 && keyCheck == 0;
+}
+
+IBLT::IBLT(size_t expectedNumEntries)
+{
+ // 1.5x expectedNumEntries gives very low probability of decoding failure
+ size_t nEntries = expectedNumEntries + expectedNumEntries / 2;
+ // make nEntries exactly divisible by N_HASH
+ size_t remainder = nEntries % N_HASH;
+ if (remainder != 0) {
+ nEntries += (N_HASH - remainder);
+ }
+
+ m_hashTable.resize(nEntries);
+}
+
+void
+IBLT::initialize(const ndn::name::Component& ibltName)
+{
+ const auto& values = extractValueFromName(ibltName);
+
+ if (3 * m_hashTable.size() != values.size()) {
+ BOOST_THROW_EXCEPTION(Error("Received IBF cannot be decoded!"));
+ }
+
+ for (size_t i = 0; i < m_hashTable.size(); i++) {
+ HashTableEntry& entry = m_hashTable.at(i);
+ if (values[i * 3] != 0) {
+ entry.count = values[i * 3];
+ entry.keySum = values[(i * 3) + 1];
+ entry.keyCheck = values[(i * 3) + 2];
+ }
+ }
+}
+
+void
+IBLT::update(int plusOrMinus, uint32_t key)
+{
+ size_t bucketsPerHash = m_hashTable.size() / N_HASH;
+
+ for (size_t i = 0; i < N_HASH; i++) {
+ size_t startEntry = i * bucketsPerHash;
+ uint32_t h = murmurHash3(i, key);
+ HashTableEntry& entry = m_hashTable.at(startEntry + (h % bucketsPerHash));
+ entry.count += plusOrMinus;
+ entry.keySum ^= key;
+ entry.keyCheck ^= murmurHash3(N_HASHCHECK, key);
+ }
+}
+
+void
+IBLT::insert(uint32_t key)
+{
+ update(INSERT, key);
+}
+
+void
+IBLT::erase(uint32_t key)
+{
+ update(ERASE, key);
+}
+
+bool
+IBLT::listEntries(std::set<uint32_t>& positive, std::set<uint32_t>& negative) const
+{
+ IBLT peeled = *this;
+
+ size_t nErased = 0;
+ do {
+ nErased = 0;
+ for (const auto& entry : peeled.m_hashTable) {
+ if (entry.isPure()) {
+ if (entry.count == 1) {
+ positive.insert(entry.keySum);
+ }
+ else {
+ negative.insert(entry.keySum);
+ }
+ peeled.update(-entry.count, entry.keySum);
+ ++nErased;
+ }
+ }
+ } while (nErased > 0);
+
+ // If any buckets for one of the hash functions is not empty,
+ // then we didn't peel them all:
+ for (const auto& entry : peeled.m_hashTable) {
+ if (entry.isEmpty() != true) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+IBLT
+IBLT::operator-(const IBLT& other) const
+{
+ BOOST_ASSERT(m_hashTable.size() == other.m_hashTable.size());
+
+ IBLT result(*this);
+ for (size_t i = 0; i < m_hashTable.size(); i++) {
+ HashTableEntry& e1 = result.m_hashTable.at(i);
+ const HashTableEntry& e2 = other.m_hashTable.at(i);
+ e1.count -= e2.count;
+ e1.keySum ^= e2.keySum;
+ e1.keyCheck ^= e2.keyCheck;
+ }
+
+ return result;
+}
+
+bool
+operator==(const IBLT& iblt1, const IBLT& iblt2)
+{
+ auto iblt1HashTable = iblt1.getHashTable();
+ auto iblt2HashTable = iblt2.getHashTable();
+ if (iblt1HashTable.size() != iblt2HashTable.size()) {
+ return false;
+ }
+
+ size_t N = iblt1HashTable.size();
+
+ for (size_t i = 0; i < N; i++) {
+ if (iblt1HashTable[i].count != iblt2HashTable[i].count ||
+ iblt1HashTable[i].keySum != iblt2HashTable[i].keySum ||
+ iblt1HashTable[i].keyCheck != iblt2HashTable[i].keyCheck)
+ return false;
+ }
+
+ return true;
+}
+
+bool
+operator!=(const IBLT& iblt1, const IBLT& iblt2)
+{
+ return !(iblt1 == iblt2);
+}
+
+std::ostream&
+operator<<(std::ostream& out, const IBLT& iblt)
+{
+ out << "count keySum keyCheckMatch\n";
+ for (const auto& entry : iblt.getHashTable()) {
+ out << entry.count << " " << entry.keySum << " ";
+ out << ((murmurHash3(N_HASHCHECK, entry.keySum) == entry.keyCheck) ||
+ (entry.isEmpty())? "true" : "false");
+ out << "\n";
+ }
+
+ return out;
+}
+
+void
+IBLT::appendToName(ndn::Name& name) const
+{
+ size_t n = m_hashTable.size();
+ size_t unitSize = (32 * 3) / 8; // hard coding
+ size_t tableSize = unitSize * n;
+
+ std::vector <uint8_t> table(tableSize);
+
+ for (size_t i = 0; i < n; i++) {
+ // table[i*12], table[i*12+1], table[i*12+2], table[i*12+3] --> hashTable[i].count
+
+ table[(i * unitSize)] = 0xFF & m_hashTable[i].count;
+ table[(i * unitSize) + 1] = 0xFF & (m_hashTable[i].count >> 8);
+ table[(i * unitSize) + 2] = 0xFF & (m_hashTable[i].count >> 16);
+ table[(i * unitSize) + 3] = 0xFF & (m_hashTable[i].count >> 24);
+
+ // table[i*12+4], table[i*12+5], table[i*12+6], table[i*12+7] --> hashTable[i].keySum
+
+ table[(i * unitSize) + 4] = 0xFF & m_hashTable[i].keySum;
+ table[(i * unitSize) + 5] = 0xFF & (m_hashTable[i].keySum >> 8);
+ table[(i * unitSize) + 6] = 0xFF & (m_hashTable[i].keySum >> 16);
+ table[(i * unitSize) + 7] = 0xFF & (m_hashTable[i].keySum >> 24);
+
+ // table[i*12+8], table[i*12+9], table[i*12+10], table[i*12+11] --> hashTable[i].keyCheck
+
+ table[(i * unitSize) + 8] = 0xFF & m_hashTable[i].keyCheck;
+ table[(i * unitSize) + 9] = 0xFF & (m_hashTable[i].keyCheck >> 8);
+ table[(i * unitSize) + 10] = 0xFF & (m_hashTable[i].keyCheck >> 16);
+ table[(i * unitSize) + 11] = 0xFF & (m_hashTable[i].keyCheck >> 24);
+ }
+
+ name.append(table.begin(), table.end());
+}
+
+std::vector<uint32_t>
+IBLT::extractValueFromName(const ndn::name::Component& ibltName) const
+{
+ std::vector<uint8_t> ibltValues(ibltName.value_begin(), ibltName.value_end());
+ size_t n = ibltValues.size() / 4;
+
+ std::vector<uint32_t> values(n, 0);
+
+ for (size_t i = 0; i < 4 * n; i += 4) {
+ uint32_t t = (ibltValues[i + 3] << 24) +
+ (ibltValues[i + 2] << 16) +
+ (ibltValues[i + 1] << 8) +
+ ibltValues[i];
+ values[i / 4] = t;
+ }
+
+ return values;
+}
+
+} // namespace psync
diff --git a/src/detail/iblt.hpp b/src/detail/iblt.hpp
new file mode 100644
index 0000000..f03797a
--- /dev/null
+++ b/src/detail/iblt.hpp
@@ -0,0 +1,181 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+
+ * The MIT License (MIT)
+
+ * Copyright (c) 2014 Gavin Andresen
+
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+*/
+
+#ifndef PSYNC_IBLT_HPP
+#define PSYNC_IBLT_HPP
+
+#include <ndn-cxx/name.hpp>
+
+#include <inttypes.h>
+#include <set>
+#include <vector>
+#include <string>
+
+namespace psync {
+
+class HashTableEntry
+{
+public:
+ int32_t count;
+ uint32_t keySum;
+ uint32_t keyCheck;
+
+ bool
+ isPure() const;
+
+ bool
+ isEmpty() const;
+};
+
+extern const size_t N_HASH;
+extern const size_t N_HASHCHECK;
+
+/**
+ * @brief Invertible Bloom Lookup Table (Invertible Bloom Filter)
+ *
+ * Used by Partial Sync (PartialProducer) and Full Sync (Full Producer)
+ */
+class IBLT
+{
+public:
+ class Error : public std::runtime_error
+ {
+ public:
+ using std::runtime_error::runtime_error;
+ };
+
+ /**
+ * @brief constructor
+ *
+ * @param expectedNumEntries the expected number of entries in the IBLT
+ */
+ explicit IBLT(size_t expectedNumEntries);
+
+ /**
+ * @brief Populate the hash table using the vector representation of IBLT
+ *
+ * @param ibltName the Component representation of IBLT
+ * @throws Error if size of values is not compatible with this IBF
+ */
+ void
+ initialize(const ndn::name::Component& ibltName);
+
+ void
+ insert(uint32_t key);
+
+ void
+ erase(uint32_t key);
+
+ /**
+ * @brief List all the entries in the IBLT
+ *
+ * This is called on a difference of two IBLTs: ownIBLT - rcvdIBLT
+ * Entries listed in positive are in ownIBLT but not in rcvdIBLT
+ * Entries listed in negative are in rcvdIBLT but not in ownIBLT
+ *
+ * @param positive
+ * @param negative
+ * @return true if decoding is complete successfully
+ */
+ bool
+ listEntries(std::set<uint32_t>& positive, std::set<uint32_t>& negative) const;
+
+ IBLT
+ operator-(const IBLT& other) const;
+
+ std::vector<HashTableEntry>
+ getHashTable() const
+ {
+ return m_hashTable;
+ }
+
+ /**
+ * @brief Appends self to name
+ *
+ * Encodes our hash table from uint32_t vector to uint8_t vector
+ * We create a uin8_t vector 12 times the size of uint32_t vector
+ * We put the first count in first 4 cells, keySum in next 4, and keyCheck in next 4.
+ * Repeat for all the other cells of the hash table.
+ * Then we append this uint8_t vector to the name.
+ *
+ * @param name
+ */
+ void
+ appendToName(ndn::Name& name) const;
+
+ /**
+ * @brief Extracts IBLT from name component
+ *
+ * Converts the name into a uint8_t vector which is then decoded to a
+ * a uint32_t vector.
+ *
+ * @param ibltName IBLT represented as a Name Component
+ * @return a uint32_t vector representing the hash table of the IBLT
+ */
+ std::vector<uint32_t>
+ extractValueFromName(const ndn::name::Component& ibltName) const;
+
+private:
+ void
+ update(int plusOrMinus, uint32_t key);
+
+private:
+ std::vector<HashTableEntry> m_hashTable;
+ static const int INSERT = 1;
+ static const int ERASE = -1;
+};
+
+bool
+operator==(const IBLT& iblt1, const IBLT& iblt2);
+
+bool
+operator!=(const IBLT& iblt1, const IBLT& iblt2);
+
+std::ostream&
+operator<<(std::ostream& out, const IBLT& iblt);
+
+} // namespace psync
+
+#endif // PSYNC_IBLT_HPP
\ No newline at end of file
diff --git a/src/detail/state.cpp b/src/detail/state.cpp
new file mode 100644
index 0000000..e5c6c47
--- /dev/null
+++ b/src/detail/state.cpp
@@ -0,0 +1,113 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "state.hpp"
+
+namespace psync {
+
+State::State(const ndn::Block& block)
+{
+ wireDecode(block);
+}
+
+void
+State::addContent(const ndn::Name& prefix)
+{
+ m_content.emplace_back(prefix);
+}
+
+const ndn::Block&
+State::wireEncode() const
+{
+ if (m_wire.hasWire()) {
+ return m_wire;
+ }
+
+ ndn::EncodingEstimator estimator;
+ size_t estimatedSize = wireEncode(estimator);
+
+ ndn::EncodingBuffer buffer(estimatedSize, 0);
+ wireEncode(buffer);
+
+ m_wire = buffer.block();
+ return m_wire;
+}
+
+template<ndn::encoding::Tag TAG>
+size_t
+State::wireEncode(ndn::EncodingImpl<TAG>& block) const
+{
+ size_t totalLength = 0;
+
+ for (std::vector<ndn::Name>::const_reverse_iterator it = m_content.rbegin();
+ it != m_content.rend(); ++it) {
+ totalLength += it->wireEncode(block);
+ }
+
+ totalLength += block.prependVarNumber(totalLength);
+ totalLength += block.prependVarNumber(tlv::PSyncContent);
+
+ return totalLength;
+}
+
+NDN_CXX_DEFINE_WIRE_ENCODE_INSTANTIATIONS(State);
+
+void
+State::wireDecode(const ndn::Block& wire)
+{
+ if (!wire.hasWire()) {
+ BOOST_THROW_EXCEPTION(ndn::tlv::Error("The supplied block does not contain wire format"));
+ }
+
+ wire.parse();
+ m_wire = wire;
+
+ auto it = m_wire.elements_begin();
+
+ if (it->type() != tlv::PSyncContent) {
+ BOOST_THROW_EXCEPTION(ndn::tlv::Error("Unexpected TLV type when decoding Content: " +
+ ndn::to_string(wire.type())));
+ }
+
+ it->parse();
+
+ for (auto val = it->elements_begin(); val != it->elements_end(); ++val) {
+ if (val->type() == ndn::tlv::Name) {
+ m_content.emplace_back(*val);
+ }
+ else {
+ BOOST_THROW_EXCEPTION(ndn::tlv::Error("Expected Name Block, but Block is of a different type: #" +
+ ndn::to_string(m_wire.type())));
+ }
+ }
+}
+
+std::ostream&
+operator<<(std::ostream& os, const State& state)
+{
+ std::vector<ndn::Name> content = state.getContent();
+
+ os << "[";
+ std::copy(content.begin(), content.end(), ndn::make_ostream_joiner(os, ", "));
+ os << "]";
+
+ return os;
+}
+
+} // namespace psync
diff --git a/src/detail/state.hpp b/src/detail/state.hpp
new file mode 100644
index 0000000..bdc6088
--- /dev/null
+++ b/src/detail/state.hpp
@@ -0,0 +1,73 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#ifndef PSYNC_STATE_HPP
+#define PSYNC_STATE_HPP
+
+#include <ndn-cxx/name.hpp>
+
+namespace psync {
+
+namespace tlv {
+
+enum {
+ PSyncContent = 128
+};
+
+} // namespace tlv
+
+class State
+{
+public:
+ explicit State(const ndn::Block& block);
+
+ State() = default;
+
+ void
+ addContent(const ndn::Name& prefix);
+
+ std::vector<ndn::Name>
+ getContent() const
+ {
+ return m_content;
+ }
+
+ const ndn::Block&
+ wireEncode() const;
+
+ template<ndn::encoding::Tag TAG>
+ size_t
+ wireEncode(ndn::EncodingImpl<TAG>& block) const;
+
+ void
+ wireDecode(const ndn::Block& wire);
+
+private:
+ std::vector<ndn::Name> m_content;
+ mutable ndn::Block m_wire;
+};
+
+NDN_CXX_DECLARE_WIRE_ENCODE_INSTANTIATIONS(State);
+
+std::ostream&
+operator<<(std::ostream& os, const State& State);
+
+} // namespace psync
+
+#endif // PSYNC_STATE_HPP
\ No newline at end of file
diff --git a/src/detail/test-access-control.hpp b/src/detail/test-access-control.hpp
new file mode 100644
index 0000000..5253a7a
--- /dev/null
+++ b/src/detail/test-access-control.hpp
@@ -0,0 +1,39 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2018, The University of Memphis,
+ * Regents of the University of California
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>
+ *
+ **/
+
+#ifndef PSYNC_TEST_ACCESS_CONTROL_HPP
+#define PSYNC_TEST_ACCESS_CONTROL_HPP
+
+#include "psync-config.hpp"
+
+#ifdef WITH_TESTS
+#define VIRTUAL_WITH_TESTS virtual
+#define PUBLIC_WITH_TESTS_ELSE_PROTECTED public
+#define PUBLIC_WITH_TESTS_ELSE_PRIVATE public
+#define PROTECTED_WITH_TESTS_ELSE_PRIVATE protected
+#else
+#define VIRTUAL_WITH_TESTS
+#define PUBLIC_WITH_TESTS_ELSE_PROTECTED protected
+#define PUBLIC_WITH_TESTS_ELSE_PRIVATE private
+#define PROTECTED_WITH_TESTS_ELSE_PRIVATE private
+#endif
+
+#endif // PSYNC_TEST_ACCESS_CONTROL_HPP
diff --git a/src/detail/util.cpp b/src/detail/util.cpp
new file mode 100644
index 0000000..ab2c541
--- /dev/null
+++ b/src/detail/util.cpp
@@ -0,0 +1,109 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * murmurHash3 was written by Austin Appleby, and is placed in the public
+ * domain. The author hereby disclaims copyright to this source code.
+ * https://github.com/aappleby/smhasher/blob/master/src/murmurHash3.cpp
+ **/
+
+#include "util.hpp"
+
+#include <ndn-cxx/util/backports.hpp>
+
+#include <string>
+
+namespace psync {
+
+static uint32_t
+ROTL32 ( uint32_t x, int8_t r )
+{
+ return (x << r) | (x >> (32 - r));
+}
+
+uint32_t
+murmurHash3(uint32_t nHashSeed, const std::vector<unsigned char>& vDataToHash)
+{
+ uint32_t h1 = nHashSeed;
+ const uint32_t c1 = 0xcc9e2d51;
+ const uint32_t c2 = 0x1b873593;
+
+ const size_t nblocks = vDataToHash.size() / 4;
+
+ //----------
+ // body
+ const uint32_t * blocks = (const uint32_t *)(&vDataToHash[0] + nblocks*4);
+
+ for (size_t i = -nblocks; i; i++) {
+ uint32_t k1 = blocks[i];
+
+ k1 *= c1;
+ k1 = ROTL32(k1,15);
+ k1 *= c2;
+
+ h1 ^= k1;
+ h1 = ROTL32(h1,13);
+ h1 = h1*5+0xe6546b64;
+ }
+
+ //----------
+ // tail
+ const uint8_t * tail = (const uint8_t*)(&vDataToHash[0] + nblocks*4);
+
+ uint32_t k1 = 0;
+
+ switch (vDataToHash.size() & 3) {
+ case 3:
+ k1 ^= tail[2] << 16;
+ NDN_CXX_FALLTHROUGH;
+
+ case 2:
+ k1 ^= tail[1] << 8;
+ NDN_CXX_FALLTHROUGH;
+
+ case 1:
+ k1 ^= tail[0];
+ k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
+ }
+
+ //----------
+ // finalization
+ h1 ^= vDataToHash.size();
+ h1 ^= h1 >> 16;
+ h1 *= 0x85ebca6b;
+ h1 ^= h1 >> 13;
+ h1 *= 0xc2b2ae35;
+ h1 ^= h1 >> 16;
+
+ return h1;
+}
+
+uint32_t
+murmurHash3(uint32_t nHashSeed, const std::string& str)
+{
+ return murmurHash3(nHashSeed, std::vector<unsigned char>(str.begin(), str.end()));
+}
+
+uint32_t
+murmurHash3(uint32_t nHashSeed, uint32_t value)
+{
+ return murmurHash3(nHashSeed,
+ std::vector<unsigned char>((unsigned char*)&value,
+ (unsigned char*)&value + sizeof(uint32_t)));
+}
+
+} // namespace psync
diff --git a/src/detail/util.hpp b/src/detail/util.hpp
new file mode 100644
index 0000000..980b6ed
--- /dev/null
+++ b/src/detail/util.hpp
@@ -0,0 +1,53 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2018, The University of Memphis
+ *
+ * This file is part of PSync.
+ * See AUTHORS.md for complete list of PSync authors and contributors.
+ *
+ * PSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * PSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * murmurHash3 was written by Austin Appleby, and is placed in the public
+ * domain. The author hereby disclaims copyright to this source code.
+ * https://github.com/aappleby/smhasher/blob/master/src/murmurHash3.cpp
+ **/
+
+#ifndef PSYNC_UTIL_HPP
+#define PSYNC_UTIL_HPP
+
+#include <ndn-cxx/name.hpp>
+
+#include <inttypes.h>
+#include <vector>
+#include <string>
+
+namespace psync {
+
+uint32_t
+murmurHash3(uint32_t nHashSeed, const std::vector<unsigned char>& vDataToHash);
+
+uint32_t
+murmurHash3(uint32_t nHashSeed, const std::string& str);
+
+uint32_t
+murmurHash3(uint32_t nHashSeed, uint32_t value);
+
+struct MissingDataInfo
+{
+ ndn::Name prefix;
+ uint64_t lowSeq;
+ uint64_t highSeq;
+};
+
+} // namespace psync
+
+#endif // PSYNC_UTIL_HPP