core: Add Mtree
Change-Id: I80205fb0d1f4ee5bcbc6c73651bb697fe854bf53
diff --git a/core/merkle-tree.cpp b/core/merkle-tree.cpp
new file mode 100644
index 0000000..f74af33
--- /dev/null
+++ b/core/merkle-tree.cpp
@@ -0,0 +1,140 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL 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.
+ *
+ * NSL 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
+ * NSL, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * @author Peizhen Guo <patrick.guopz@gmail.com>
+ */
+#include "merkle-tree.hpp"
+
+namespace nsl {
+
+MerkleTree::MerkleTree()
+{
+ m_nLevels = 0;
+ m_nLeaves = 0;
+}
+
+
+ConstNodePtr
+MerkleTree::getNode(const Index& index)
+{
+ ConstNodePtr p_leav;
+ if (m_cache.doesNodeExist(index))
+ {
+ p_leav = m_cache.queryNode(index);
+ return p_leav;
+ }
+ else
+ return p_leav;
+}
+
+
+uint64_t
+MerkleTree::getLeafNum() const
+{
+ return m_nLeaves;
+}
+
+
+uint64_t
+MerkleTree::getLevel() const
+{
+ return m_nLevels;
+}
+
+
+
+uint64_t
+MerkleTree::addLeaf(ndn::ConstBufferPtr info)
+{
+ Leaf new_leaf(info, m_nLeaves, 0, 0);
+ new_leaf.computeHash(); // computeHash() has been written.
+ m_nLeaves++;
+ if (m_nLeaves > int(pow(2, int(m_nLevels) - 1)))
+ {
+ m_nLevels++;
+ }
+ m_cache.addLeaf(new_leaf);
+ return m_nLeaves - 1;
+}
+
+
+std::vector<ConstNodePtr>
+MerkleTree::generateProof(uint64_t version1, uint64_t version2)
+{
+ std::vector<ConstNodePtr> proof;
+ if (version1 >= version2)
+ {
+ return proof;
+ }
+
+ //add a memberproof from version2
+ Index this_idx;
+ this_idx.number = version2;
+ this_idx.level = 0;
+ ConstNodePtr p_leav;
+ p_leav = m_cache.queryNode(this_idx);
+ proof.push_back(p_leav);
+ if ((this_idx.number % 2) != 0)
+ {
+ this_idx.number -= 1;
+ p_leav = m_cache.queryNode(this_idx);
+ proof.push_back(p_leav);
+ }
+ this_idx.level += 1;
+ this_idx.number -= this_idx.number % 2;
+ for (int i = 1; i < m_nLevels - 1 ; i++)
+ {
+ if (this_idx.number % int(pow(2, i + 1)) != 0)
+ {
+ this_idx.number -= int(pow(2, i));
+ p_leav = m_cache.queryNode(this_idx);
+ proof.push_back(p_leav);
+ }
+ this_idx.level += 1;
+ this_idx.number -= this_idx.number % int(pow(2, i + 1));
+ }
+
+ //add another path from version1
+ this_idx.number = version1;
+ this_idx.level = 0;
+ p_leav = m_cache.queryNode(this_idx);
+ proof.push_back(p_leav);
+ if ((this_idx.number % 2) != 0)
+ {
+ this_idx.number -= 1;
+ p_leav = m_cache.queryNode(this_idx);
+ proof.push_back(p_leav);
+ }
+ this_idx.level += 1;
+ this_idx.number -= this_idx.number % 2;
+ for (int i = 1; i < m_nLevels - 1 ; i++)
+ {
+ if (this_idx.number % int(pow(2, i + 1)) != 0)
+ {
+ this_idx.number -= int(pow(2, i));
+ p_leav = m_cache.queryNode(this_idx);
+ proof.push_back(p_leav);
+ }
+ this_idx.level += 1;
+ this_idx.number -= this_idx.number % int(pow(2, i + 1));
+ }
+
+ return proof;
+}
+
+} // namespace nsl