refactor code
Change-Id: Ia2bc49ed8742d79000fd59f7e95fa9b957573c54
diff --git a/.waf-tools/default-compiler-flags.py b/.waf-tools/default-compiler-flags.py
index bdf3b19..759fcc8 100644
--- a/.waf-tools/default-compiler-flags.py
+++ b/.waf-tools/default-compiler-flags.py
@@ -1,54 +1,59 @@
# -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
-from waflib import Logs, Configure
+from waflib import Logs, Configure, Utils
def options(opt):
opt.add_option('--debug', '--with-debug', action='store_true', default=False, dest='debug',
- help='''Compile in debugging mode without all optimizations (-O0)''')
- opt.add_option('--with-c++11', action='store_true', default=False, dest='use_cxx11',
- help='''Use C++ 11 features if available in the compiler''')
+ help='''Compile in debugging mode without optimizations (-O0 or -Og)''')
def configure(conf):
- areCustomCxxflagsPresent = (len(conf.env.CXXFLAGS) > 0)
- defaultFlags = []
-
- if conf.options.use_cxx11:
- defaultFlags += ['-std=c++0x', '-std=c++11']
+ cxx = conf.env['CXX_NAME'] # CXX_NAME represents generic name of the compiler
+ if cxx == 'gcc':
+ flags = GccFlags()
+ elif cxx == 'clang':
+ flags = ClangFlags()
else:
- defaultFlags += ['-std=c++03']
+ flags = CompilerFlags()
+ Logs.warn('The code has not been yet tested with %s compiler' % cxx)
- defaultFlags += ['-pedantic', '-Wall', '-Wno-long-long', '-Wno-unneeded-internal-declaration']
+ areCustomCxxflagsPresent = (len(conf.env.CXXFLAGS) > 0)
+ # General flags will alway be applied (e.g., selecting C++11 mode)
+ generalFlags = flags.getGeneralFlags(conf)
+ conf.add_supported_cxxflags(generalFlags['CXXFLAGS'])
+ conf.add_supported_linkflags(generalFlags['LINKFLAGS'])
+ conf.env.DEFINES += generalFlags['DEFINES']
+
+ # Debug or optimization CXXFLAGS and LINKFLAGS will be applied only if the
+ # corresponding environment variables are not set.
+ # DEFINES will be always applied
if conf.options.debug:
- conf.define('_DEBUG', 1)
- defaultFlags += ['-O0',
- '-Og', # gcc >= 4.8
- '-g3',
- '-fcolor-diagnostics', # clang
- '-fdiagnostics-color', # gcc >= 4.9
- '-Werror',
- '-Wno-error=deprecated-register',
- '-Wno-error=maybe-uninitialized', # Bug #1615
- ]
+ extraFlags = flags.getDebugFlags(conf)
+
if areCustomCxxflagsPresent:
- missingFlags = [x for x in defaultFlags if x not in conf.env.CXXFLAGS]
+ missingFlags = [x for x in extraFlags['CXXFLAGS'] if x not in conf.env.CXXFLAGS]
if len(missingFlags) > 0:
Logs.warn("Selected debug mode, but CXXFLAGS is set to a custom value '%s'"
% " ".join(conf.env.CXXFLAGS))
Logs.warn("Default flags '%s' are not activated" % " ".join(missingFlags))
- else:
- conf.add_supported_cxxflags(defaultFlags)
else:
- defaultFlags += ['-O2', '-g']
- if not areCustomCxxflagsPresent:
- conf.add_supported_cxxflags(defaultFlags)
+ extraFlags = flags.getOptimizedFlags(conf)
+
+ if not areCustomCxxflagsPresent:
+ conf.add_supported_cxxflags(extraFlags['CXXFLAGS'])
+ conf.add_supported_cxxflags(extraFlags['LINKFLAGS'])
+
+ conf.env.DEFINES += extraFlags['DEFINES']
@Configure.conf
def add_supported_cxxflags(self, cxxflags):
"""
Check which cxxflags are supported by compiler and add them to env.CXXFLAGS variable
"""
- self.start_msg('Checking allowed flags for c++ compiler')
+ if len(cxxflags) == 0:
+ return
+
+ self.start_msg('Checking supported CXXFLAGS')
supportedFlags = []
for flag in cxxflags:
@@ -57,3 +62,92 @@
self.end_msg(' '.join(supportedFlags))
self.env.CXXFLAGS = supportedFlags + self.env.CXXFLAGS
+
+@Configure.conf
+def add_supported_linkflags(self, linkflags):
+ """
+ Check which linkflags are supported by compiler and add them to env.LINKFLAGS variable
+ """
+ if len(linkflags) == 0:
+ return
+
+ self.start_msg('Checking supported LINKFLAGS')
+
+ supportedFlags = []
+ for flag in linkflags:
+ if self.check_cxx(linkflags=['-Werror', flag], mandatory=False):
+ supportedFlags += [flag]
+
+ self.end_msg(' '.join(supportedFlags))
+ self.env.LINKFLAGS = supportedFlags + self.env.LINKFLAGS
+
+
+class CompilerFlags(object):
+ def getGeneralFlags(self, conf):
+ """Get dict {'CXXFLAGS':[...], LINKFLAGS:[...], DEFINES:[...]} that are always needed"""
+ return {'CXXFLAGS': [], 'LINKFLAGS': [], 'DEFINES': []}
+
+ def getDebugFlags(self, conf):
+ """Get tuple {CXXFLAGS, LINKFLAGS, DEFINES} that are needed in debug mode"""
+ return {'CXXFLAGS': [], 'LINKFLAGS': [], 'DEFINES': ['_DEBUG']}
+
+ def getOptimizedFlags(self, conf):
+ """Get tuple {CXXFLAGS, LINKFLAGS, DEFINES} that are needed in optimized mode"""
+ return {'CXXFLAGS': [], 'LINKFLAGS': [], 'DEFINES': ['NDEBUG']}
+
+class GccBasicFlags(CompilerFlags):
+ """This class defines base flags that work for gcc and clang compiler"""
+ def getDebugFlags(self, conf):
+ flags = super(GccBasicFlags, self).getDebugFlags(conf)
+ flags['CXXFLAGS'] += ['-pedantic', '-Wall',
+ '-O0',
+ '-g3',
+ '-Werror',
+ '-Wno-error=maybe-uninitialized', # Bug #1615
+ ]
+ return flags
+
+ def getOptimizedFlags(self, conf):
+ flags = super(GccBasicFlags, self).getOptimizedFlags(conf)
+ flags['CXXFLAGS'] += ['-pedantic', '-Wall', '-O2', '-g']
+ return flags
+
+class GccFlags(GccBasicFlags):
+ def getGeneralFlags(self, conf):
+ flags = super(GccFlags, self).getGeneralFlags(conf)
+ version = tuple(int(i) for i in conf.env['CC_VERSION'])
+ if version < (4, 6, 0):
+ conf.fatal('The version of gcc you are using (%s) is too old.\n' %
+ '.'.join(conf.env['CC_VERSION']) +
+ 'The minimum supported gcc version is 4.6.0.')
+ elif version < (4, 7, 0):
+ flags['CXXFLAGS'] += ['-std=c++0x']
+ else:
+ flags['CXXFLAGS'] += ['-std=c++11']
+ if version < (4, 8, 0):
+ flags['DEFINES'] += ['_GLIBCXX_USE_NANOSLEEP'] # Bug #2499
+ return flags
+
+ def getDebugFlags(self, conf):
+ flags = super(GccFlags, self).getDebugFlags(conf)
+ flags['CXXFLAGS'] += ['-Og', # gcc >= 4.8
+ '-fdiagnostics-color', # gcc >= 4.9
+ ]
+ return flags
+
+class ClangFlags(GccBasicFlags):
+ def getGeneralFlags(self, conf):
+ flags = super(ClangFlags, self).getGeneralFlags(conf)
+ flags['CXXFLAGS'] += ['-std=c++11',
+ '-Wno-error=unneeded-internal-declaration', # Bug #1588
+ '-Wno-error=deprecated-register',
+ ]
+ if Utils.unversioned_sys_platform() == "darwin":
+ flags['CXXFLAGS'] += ['-stdlib=libc++']
+ flags['LINKFLAGS'] += ['-stdlib=libc++']
+ return flags
+
+ def getDebugFlags(self, conf):
+ flags = super(ClangFlags, self).getDebugFlags(conf)
+ flags['CXXFLAGS'] += ['-fcolor-diagnostics']
+ return flags
diff --git a/.waf-tools/sqlite3.py b/.waf-tools/sqlite3.py
index c47ae6f..3d4e46e 100644
--- a/.waf-tools/sqlite3.py
+++ b/.waf-tools/sqlite3.py
@@ -1,7 +1,7 @@
#! /usr/bin/env python
# encoding: utf-8
-from waflib import Options
+from waflib import Options, Logs
from waflib.Configure import conf
def options(opt):
@@ -26,6 +26,8 @@
try:
self.check_cfg(package='sqlite3',
args=['--cflags', '--libs'],
+ global_define=True,
+ define_name='HAVE_%s' % var,
uselib_store='SQLITE3',
mandatory=True)
except:
diff --git a/AUTHORS.md b/AUTHORS.md
index 611744c..65a6920 100644
--- a/AUTHORS.md
+++ b/AUTHORS.md
@@ -3,6 +3,9 @@
## The primary authors are (and/or have been):
+* Yingdi Yu <http://irl.cs.ucla.edu/~yingdi/>
+* Peizhen Guo <patrick.guopz@gmail.com>
+
## All project authors and contributors
diff --git a/common.hpp b/common.hpp
index f308e3a..13203cc 100644
--- a/common.hpp
+++ b/common.hpp
@@ -24,16 +24,16 @@
#include "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
+#ifdef NSL_HAVE_TESTS
+#define NSL_VIRTUAL_WITH_TESTS virtual
+#define NSL_PUBLIC_WITH_TESTS_ELSE_PROTECTED public
+#define NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE public
+#define NSL_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
+#define NSL_VIRTUAL_WITH_TESTS
+#define NSL_PUBLIC_WITH_TESTS_ELSE_PROTECTED protected
+#define NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE private
+#define NSL_PROTECTED_WITH_TESTS_ELSE_PRIVATE private
#endif
#include <cstddef>
@@ -61,26 +61,28 @@
using boost::noncopyable;
using boost::scoped_ptr;
-using ndn::shared_ptr;
-using ndn::weak_ptr;
-using ndn::enable_shared_from_this;
-using ndn::make_shared;
-using ndn::static_pointer_cast;
-using ndn::dynamic_pointer_cast;
-using ndn::const_pointer_cast;
-using ndn::function;
-using ndn::bind;
-using ndn::ref;
-using ndn::cref;
+using std::shared_ptr;
+using std::weak_ptr;
+using std::enable_shared_from_this;
+using std::make_shared;
+using std::static_pointer_cast;
+using std::dynamic_pointer_cast;
+using std::const_pointer_cast;
+using std::function;
+using std::bind;
+using std::ref;
+using std::cref;
using ndn::Interest;
using ndn::Data;
using ndn::Name;
using ndn::Exclude;
using ndn::Block;
+using ndn::Signature;
+using ndn::KeyLocator;
namespace tlv {
-using namespace ndn::Tlv;
+using namespace ndn::tlv;
}
namespace name = ndn::name;
diff --git a/core/auditor.cpp b/core/auditor.cpp
index d0afa62..34f85d0 100644
--- a/core/auditor.cpp
+++ b/core/auditor.cpp
@@ -16,175 +16,225 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
+
#include "auditor.hpp"
+#include <ndn-cxx/util/digest.hpp>
+
namespace nsl {
-ndn::ConstBufferPtr
-Auditor::computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r)
+bool
+Auditor::doesExist(const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash,
+ const NonNegativeInteger& rootNextSeqNo,
+ ndn::ConstBufferPtr rootHash,
+ const std::vector<shared_ptr<Data>>& proofs,
+ const Name& loggerName)
{
- ndn::Buffer tmp_buf = *hash_l;
- for (int i = 0; i < hash_r->size(); i++)
- {
- tmp_buf.push_back((*hash_r)[i]);
+ BOOST_ASSERT(rootHash != nullptr);
+ BOOST_ASSERT(hash != nullptr);
+
+ std::map<Node::Index, ConstSubTreeBinaryPtr> trees;
+
+ if (!loadProof(trees, proofs, loggerName))
+ return false;
+
+ // std::cerr << "Loaded" << std::endl;
+
+ size_t rootLevel = 0;
+ NonNegativeInteger tmpSeqNo = rootNextSeqNo - 1;
+ while (tmpSeqNo != 0) {
+ rootLevel++;
+ tmpSeqNo = tmpSeqNo >> 1;
+ }
+
+ if (rootLevel == 0) { // only one node
+ // std::cerr << "one level" << std::endl;
+ if (seqNo != 0)
+ return false;
+
+ auto it = trees.find(Node::Index(0, SubTreeBinary::SUB_TREE_DEPTH - 1));
+ if (it != trees.end()) {
+ // std::cerr << "find subtree" << std::endl;
+ auto node = it->second->getNode(Node::Index(0, 0));
+ if (node != nullptr && *node->getHash() == *hash && *hash == *rootHash)
+ return true;
+ else
+ return false;
}
- ndn::ConstBufferPtr digest = ndn::crypto::sha256(tmp_buf.buf(), tmp_buf.size());
- return digest;
+ else
+ return false;
+ }
+
+
+ NonNegativeInteger childSeqMask = 1;
+ NonNegativeInteger childSeqNo = seqNo;
+ size_t childLevel = 0;
+ ndn::ConstBufferPtr childHash = hash;
+
+ NonNegativeInteger parentSeqMask = (~0) << 1;
+ NonNegativeInteger parentSeqNo = childSeqNo & parentSeqMask;
+ size_t parentLevel = 1;
+
+ Node::Index treePeakIndex(0, 0);
+ ConstSubTreeBinaryPtr subTree;
+
+ do { // get parent hash
+ Node::Index tmpIndex =
+ SubTreeBinary::toSubTreePeakIndex(Node::Index(childSeqNo, childLevel));
+
+ // std::cerr << "peak: " << tmpIndex.level << ", " << tmpIndex.seqNo << std::endl;
+ if (tmpIndex != treePeakIndex) {
+ treePeakIndex = tmpIndex;
+ auto it = trees.find(treePeakIndex);
+ if (it != trees.end() && it->second != nullptr) {
+ subTree = it->second;
+ }
+ else
+ return false;
+ }
+
+ // std::cerr << "Hey" << std::endl;
+ // right child or left child
+ ndn::util::Sha256 sha256;
+ if (childSeqMask & seqNo) { // right child
+ // std::cerr << "right" << std::endl;
+ // std::cerr << parentSeqNo << ", " << childLevel << std::endl;
+ auto leftChild = subTree->getNode(Node::Index(parentSeqNo, childLevel));
+ if (leftChild == nullptr && leftChild->getHash() == nullptr)
+ return false;
+
+ // std::cerr << "found node" << std::endl;
+ sha256 << parentLevel << parentSeqNo;
+ sha256.update(leftChild->getHash()->buf(), leftChild->getHash()->size());
+ sha256.update(childHash->buf(), childHash->size());
+ }
+ else { // left child
+ // std::cerr << "left" << std::endl;
+ ndn::ConstBufferPtr rightChildHash = Node::getEmptyHash();
+ if (rootNextSeqNo > childSeqNo + (1 << childLevel)) {
+ // std::cerr << childSeqNo + (1 << childLevel) << ", " << childLevel << std::endl;
+ auto rightChild = subTree->getNode(Node::Index(childSeqNo + (1 << childLevel), childLevel));
+ if (rightChild == nullptr || rightChild->getHash() == nullptr)
+ return false;
+ rightChildHash = rightChild->getHash();
+ // std::cerr << "left done" << std::endl;
+ }
+
+ sha256 << parentLevel << parentSeqNo;
+ sha256.update(childHash->buf(), childHash->size());
+ sha256.update(rightChildHash->buf(), rightChildHash->size());
+ }
+
+ childSeqMask = childSeqMask << 1;
+ childSeqNo = parentSeqNo;
+ childLevel = parentLevel;
+ childHash = sha256.computeDigest();
+
+ parentSeqMask = parentSeqMask << 1;
+ parentSeqNo = childSeqNo & parentSeqMask;
+ parentLevel++;
+
+ } while (childLevel < rootLevel);
+
+ // std::cerr << "done" << std::endl;
+
+ return (*childHash == *rootHash);
}
-
-
-
-
-ndn::ConstBufferPtr
-Auditor::computeHashOneSide(ndn::ConstBufferPtr hash_l)
-{
- ndn::ConstBufferPtr digest = ndn::crypto::sha256(hash_l->buf(), hash_l->size());
- return digest;
-}
-
-
-
-
-
-
bool
-Auditor::verifyConsistency(uint64_t version1, uint64_t version2, ndn::ConstBufferPtr hash1,
- ndn::ConstBufferPtr hash2, std::vector<ConstNodePtr> proof)
+Auditor::isConsistent(const NonNegativeInteger& oldRootNextSeqNo,
+ ndn::ConstBufferPtr oldRootHash,
+ const NonNegativeInteger& newRootNextSeqNo,
+ ndn::ConstBufferPtr newRootHash,
+ const std::vector<shared_ptr<Data>>& proofs,
+ const Name& loggerName)
{
- // find version2's level
- uint64_t levelVer2 = 1;
- uint64_t ver2 = version2;
- while(ver2 >= 1)
- {
- ver2 = ver2 / 2;
- levelVer2 += 1;
- }
+ BOOST_ASSERT(oldRootHash != nullptr);
+ BOOST_ASSERT(newRootHash != nullptr);
- // compare version2's hash
- ndn::ConstBufferPtr hash_l;
- ndn::ConstBufferPtr hash_r;
- ndn::ConstBufferPtr tmp_hash;
- Index tmp_idx = proof[0]->getIndex();
- int isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
- if (isRight != 0)
- hash_r = proof[0]->getHash();
- else
- hash_l = proof[0]->getHash();
- uint64_t i_ = 1;
- for (; tmp_idx.level < levelVer2 - 1; )
- {
- if (isRight != 0)
- {
- hash_l = proof[i_]->getHash();
- tmp_hash = computeHash(hash_l, hash_r);
- i_++;
- }
- else
- {
- tmp_hash = computeHashOneSide(hash_l);
- }
- tmp_idx.level += 1;
- tmp_idx.number -= tmp_idx.number % int(pow(2, tmp_idx.level));
- isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
- if (isRight != 0)
- {
- hash_r = tmp_hash;
- }
- else
- {
- hash_l = tmp_hash;
- }
- }
- bool hash2_consis = true;
- if (isRight != 0)
- {
- for (int i = 0; i < hash_r->size() ; i++)
- {
- if ((*hash2)[i] != (*hash_r)[i])
- {
- hash2_consis = false;
- break;
- }
- }
- }
- else
- {
- for (int i = 0; i < hash_l->size() ; i++)
- {
- if ((*hash2)[i] != (*hash_l)[i])
- {
- hash2_consis = false;
- break;
- }
- }
- }
+ if (oldRootNextSeqNo > newRootNextSeqNo)
+ return false;
+ std::map<Node::Index, ConstSubTreeBinaryPtr> trees;
+ if (!loadProof(trees, proofs, loggerName))
+ return false;
+ // std::cerr << "1" << std::endl;
+ // get boundary leaf:
+ NonNegativeInteger leafSeqNo = oldRootNextSeqNo - 1;
+ NonNegativeInteger treeSeqNo = leafSeqNo & ((~0) << (SubTreeBinary::SUB_TREE_DEPTH - 1));
+ auto it = trees.find(Node::Index(treeSeqNo, SubTreeBinary::SUB_TREE_DEPTH - 1));
+ if (it == trees.end())
+ return false;
- // compare hash1
- tmp_idx = proof[i_]->getIndex();
- isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
- if (isRight != 0)
- hash_r = proof[i_]->getHash();
- else
- hash_l = proof[i_]->getHash();
- i_++;
- for (; i_ < proof.size(); )
- {
- if (isRight != 0)
- {
- hash_l = proof[i_]->getHash();
- tmp_hash = computeHash(hash_l, hash_r);
- i_++;
- }
- else
- {
- tmp_hash = computeHashOneSide(hash_l);
- }
- tmp_idx.level += 1;
- tmp_idx.number -= tmp_idx.number % int(pow(2, tmp_idx.level));
- isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
- if (isRight != 0)
- {
- hash_r = tmp_hash;
- }
- else
- {
- hash_l = tmp_hash;
- }
- }
+ auto leaf = it->second->getNode(Node::Index(leafSeqNo, 0));
+ if (leaf == nullptr || leaf->getHash() == nullptr)
+ return false;
- bool hash1_consis = true;
- if (isRight != 0)
- {
- for (int i = 0; i < hash_r->size() ; i++)
- {
- if ((*hash1)[i] != (*hash_r)[i])
- {
- hash1_consis = false;
- break;
- }
- }
- }
- else
- {
- for (int i = 0; i < hash_l->size() ; i++)
- {
- if ((*hash1)[i] != (*hash_l)[i])
- {
- hash1_consis = false;
- break;
- }
- }
- }
+ if (!doesExist(leafSeqNo, leaf->getHash(), oldRootNextSeqNo, oldRootHash,
+ proofs, loggerName))
+ return false;
- return hash1_consis && hash2_consis;
+ // std::cerr << "2" << std::endl;
+ if (oldRootNextSeqNo == newRootNextSeqNo) {
+ if (*oldRootHash == *newRootHash)
+ return true;
+ else
+ return false;
+ }
+
+ // std::cerr << "3" << std::endl;
+
+ if (!doesExist(leafSeqNo, leaf->getHash(), newRootNextSeqNo, newRootHash,
+ proofs, loggerName))
+ return false;
+
+ // std::cerr << "4" << std::endl;
+
+ return true;
}
+bool
+Auditor::loadProof(std::map<Node::Index, ConstSubTreeBinaryPtr>& trees,
+ const std::vector<shared_ptr<Data>>& proofs,
+ const Name& loggerName)
+{
+ try {
+ for (auto proof : proofs) {
+ // std::cerr << proof->getName() << std::endl;
+ auto subtree =
+ make_shared<SubTreeBinary>(loggerName,
+ [] (const Node::Index& idx) {},
+ [] (const Node::Index&,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {});
+ subtree->decode(*proof);
+
+ // std::cerr << subtree->getPeakIndex().level << ", " << subtree->getPeakIndex().seqNo << std::endl;
+ if (trees.find(subtree->getPeakIndex()) == trees.end())
+ trees[subtree->getPeakIndex()] = subtree;
+ else
+ return false;
+ }
+ }
+ catch (SubTreeBinary::Error& e) {
+ // std::cerr << e.what() << std::endl;
+ return false;
+ }
+ catch (Node::Error& e) {
+ // std::cerr << e.what() << std::endl;
+ return false;
+ }
+ catch (tlv::Error&) {
+ return false;
+ }
+
+ return true;
+}
} // namespace nsl
diff --git a/core/auditor.hpp b/core/auditor.hpp
index 8f2919a..9117d5d 100644
--- a/core/auditor.hpp
+++ b/core/auditor.hpp
@@ -16,59 +16,47 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#ifndef NLS_CORE_AUDITOR_HPP
-#define NLS_CORE_AUDITOR_HPP
-#include <string>
+#ifndef NSL_CORE_AUDITOR_HPP
+#define NSL_CORE_AUDITOR_HPP
+
+#include "common.hpp"
+#include "node.hpp"
+#include "sub-tree-binary.hpp"
+#include "util/non-negative-integer.hpp"
+#include <ndn-cxx/encoding/buffer.hpp>
#include <vector>
-#include <math.h>
-#include <stdint.h>
-
-#include <ndn-cxx/util/crypto.hpp>
-
-#include "node.hpp"
-
namespace nsl {
-typedef ndn::shared_ptr<const Node> ConstNodePtr;
-typedef ndn::shared_ptr<Node> NodePtr;
-
class Auditor
{
public:
- Auditor()
- {
- }
+ static bool
+ doesExist(const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash,
+ const NonNegativeInteger& rootNextSeqNo,
+ ndn::ConstBufferPtr rootHash,
+ const std::vector<shared_ptr<Data>>& proofs,
+ const Name& loggerName);
+ static bool
+ isConsistent(const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash,
+ const NonNegativeInteger& rootNextSeqNo,
+ ndn::ConstBufferPtr rootHash,
+ const std::vector<shared_ptr<Data>>& proofs,
+ const Name& loggerName);
- ~Auditor()
- {
- }
-
-
- bool
- verifyConsistency(uint64_t version1, uint64_t version2, ndn::ConstBufferPtr hash1,
- ndn::ConstBufferPtr hash2, std::vector<ConstNodePtr> proof);
-
-
- std::vector<Node*>
- queryByTime(time_t);
-
- ndn::ConstBufferPtr
- computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r);
-
-
- ndn::ConstBufferPtr
- computeHashOneSide(ndn::ConstBufferPtr hash_l);
-
-
-private:
-
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ static bool
+ loadProof(std::map<Node::Index, ConstSubTreeBinaryPtr>& trees,
+ const std::vector<shared_ptr<Data>>& proofs,
+ const Name& loggerName);
};
} // namespace nsl
-#endif // NLS_CORE_AUDITOR_HPP
+#endif // NSL_CORE_AUDITOR_HPP
diff --git a/core/db.cpp b/core/db.cpp
new file mode 100644
index 0000000..22361c5
--- /dev/null
+++ b/core/db.cpp
@@ -0,0 +1,309 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "db.hpp"
+
+#include <sqlite3.h>
+#include <string>
+#include <boost/filesystem.hpp>
+
+namespace nsl {
+
+static const std::string INITIALIZATION =
+ "CREATE TABLE IF NOT EXISTS \n"
+ " cTrees( \n"
+ " id INTEGER PRIMARY KEY,\n"
+ " level INTEGER NOT NULL, \n"
+ " seqNo INTEGER NOT NULL, \n"
+ " data BLOB NOT NULL \n"
+ " ); \n"
+ "CREATE UNIQUE INDEX IF NOT EXISTS \n"
+ " cTreeIndex ON cTrees(level, seqNo); \n"
+ "CREATE TRIGGER IF NOT EXISTS \n"
+ " cTrees_after_insert_trigger \n"
+ " AFTER INSERT ON cTrees \n"
+ " FOR EACH ROW \n"
+ " BEGIN \n"
+ " DELETE FROM pTrees \n"
+ " WHERE level=NEW.level AND seqNo=NEW.seqNo;\n"
+ " END; \n"
+ " \n"
+ "CREATE TABLE IF NOT EXISTS \n"
+ " pTrees( \n"
+ " id INTEGER PRIMARY KEY,\n"
+ " level INTEGER NOT NULL, \n"
+ " seqNo INTEGER NOT NULL, \n"
+ " nextLeafSeqNo INTEGER NOT NULL, \n"
+ " data BLOB NOT NULL \n"
+ " ); \n"
+ "CREATE UNIQUE INDEX IF NOT EXISTS \n"
+ " pTreeIndex ON pTrees(level, seqNo); \n"
+ " \n"
+ "CREATE TABLE IF NOT EXISTS \n"
+ " leaves( \n"
+ " id INTEGER PRIMARY KEY,\n"
+ " dataSeqNo INTEGER NOT NULL, \n"
+ " dataName BLOB NOT NULL, \n"
+ " signerSeqNo INTEGER NOT NULL, \n"
+ " timestamp INTEGER NOT NULL, \n"
+ " isCert INTEGER DEFAULT 0, \n"
+ " cert BLOB \n"
+ " ); \n"
+ "CREATE UNIQUE INDEX IF NOT EXISTS \n"
+ " leavesIndex ON leaves(dataSeqNo); \n";
+
+
+/**
+ * A utility function to call the normal sqlite3_bind_blob where the value and length are
+ * block.wire() and block.size().
+ */
+static int
+sqlite3_bind_block(sqlite3_stmt* statement,
+ int index,
+ const Block& block,
+ void(*destructor)(void*))
+{
+ return sqlite3_bind_blob(statement, index, block.wire(), block.size(), destructor);
+}
+
+/**
+ * A utility function to generate block by calling the normal sqlite3_column_text.
+ */
+static Block
+sqlite3_column_block(sqlite3_stmt* statement, int column)
+{
+ return Block(sqlite3_column_blob(statement, column), sqlite3_column_bytes(statement, column));
+}
+
+void
+Db::open(const std::string& dbDir)
+{
+ // Determine the path of logger database
+ if (dbDir == "")
+ throw Error("Db: empty db path");
+
+ boost::filesystem::path dir = boost::filesystem::path(dbDir);
+ boost::filesystem::create_directories(dir);
+
+ // Open database
+ int result = sqlite3_open_v2((dir / "sig-logger.db").c_str(), &m_db,
+ SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE,
+#ifdef NSL_DISABLE_SQLITE3_FS_LOCKING
+ "unix-dotfile"
+#else
+ nullptr
+#endif
+ );
+
+ if (result != SQLITE_OK)
+ throw Error("SigLogger DB cannot be opened/created: " + dbDir);
+
+ // initialize SigLogger specific tables
+ char* errorMessage = nullptr;
+ result = sqlite3_exec(m_db, INITIALIZATION.c_str(), nullptr, nullptr, &errorMessage);
+ if (result != SQLITE_OK && errorMessage != nullptr) {
+ sqlite3_free(errorMessage);
+ throw Error("SigLogger DB cannot be initialized");
+ }
+
+ getMaxLeafSeq();
+}
+
+bool
+Db::insertSubTreeData(size_t level, const NonNegativeInteger& seqNo,
+ const Data& data,
+ bool isFull, const NonNegativeInteger& nextLeafSeqNo)
+{
+ sqlite3_stmt* statement;
+ if (isFull) {
+ sqlite3_prepare_v2(m_db,
+ "INSERT INTO cTrees (level, seqNo, data) VALUES (?, ?, ?)",
+ -1, &statement, nullptr);
+ }
+ else {
+ sqlite3_prepare_v2(m_db,
+ "INSERT OR REPLACE INTO pTrees (level, seqNo, data, nextLeafSeqNo)\
+ VALUES (?, ?, ?, ?)",
+ -1, &statement, nullptr);
+ }
+ sqlite3_bind_int(statement, 1, level);
+ sqlite3_bind_int(statement, 2, seqNo);
+ sqlite3_bind_block(statement, 3, data.wireEncode(), SQLITE_TRANSIENT);
+ if (!isFull)
+ sqlite3_bind_int(statement, 4, nextLeafSeqNo);
+
+ int result = sqlite3_step(statement);
+ sqlite3_finalize(statement);
+
+ if (result == SQLITE_OK)
+ return true;
+ return false;
+}
+
+shared_ptr<Data>
+Db::getSubTreeData(size_t level, const NonNegativeInteger& seqNo)
+{
+ sqlite3_stmt* statement;
+ sqlite3_prepare_v2(m_db,
+ "SELECT data FROM cTrees WHERE level=? AND seqNo=?",
+ -1, &statement, nullptr);
+ sqlite3_bind_int(statement, 1, level);
+ sqlite3_bind_int(statement, 2, seqNo);
+
+ if (sqlite3_step(statement) == SQLITE_ROW) {
+ auto result = make_shared<Data>(sqlite3_column_block(statement, 0));
+ sqlite3_finalize(statement);
+ return result;
+ }
+
+ sqlite3_prepare_v2(m_db,
+ "SELECT data FROM pTrees WHERE level=? AND seqNo=?",
+ -1, &statement, nullptr);
+ sqlite3_bind_int(statement, 1, level);
+ sqlite3_bind_int(statement, 2, seqNo);
+
+ shared_ptr<Data> result;
+ if (sqlite3_step(statement) == SQLITE_ROW)
+ result = make_shared<Data>(sqlite3_column_block(statement, 0));
+
+ sqlite3_finalize(statement);
+ return result;
+}
+
+std::vector<shared_ptr<Data>>
+Db::getPendingSubTrees()
+{
+ sqlite3_stmt* statement;
+ sqlite3_prepare_v2(m_db,
+ "SELECT data FROM pTrees ORDER BY level DESC",
+ -1, &statement, nullptr);
+
+ std::vector<shared_ptr<Data>> datas;
+ while (sqlite3_step(statement) == SQLITE_ROW)
+ datas.push_back(make_shared<Data>(sqlite3_column_block(statement, 0)));
+
+ sqlite3_finalize(statement);
+ return datas;
+}
+
+bool
+Db::insertLeafData(const Leaf& leaf)
+{
+ if (leaf.getDataSeqNo() != m_nextLeafSeqNo)
+ return false;
+
+ sqlite3_stmt* statement;
+ sqlite3_prepare_v2(m_db,
+ "INSERT INTO leaves (dataSeqNo, dataName, signerSeqNo, timestamp, isCert)\
+ VALUES (?, ?, ?, ?, 0)",
+ -1, &statement, nullptr);
+
+ sqlite3_bind_int(statement, 1, leaf.getDataSeqNo());
+ sqlite3_bind_block(statement, 2, leaf.getDataName().wireEncode(), SQLITE_TRANSIENT);
+ sqlite3_bind_int(statement, 3, leaf.getSignerSeqNo());
+ sqlite3_bind_int(statement, 4, leaf.getTimestamp());
+
+ int result = sqlite3_step(statement);
+ sqlite3_finalize(statement);
+
+ if (result == SQLITE_OK || result == SQLITE_DONE) {
+ m_nextLeafSeqNo++;
+ return true;
+ }
+
+ return false;
+}
+
+bool
+Db::insertLeafData(const Leaf& leaf, const Data& data)
+{
+ if (leaf.getDataSeqNo() != m_nextLeafSeqNo)
+ return false;
+
+ sqlite3_stmt* statement;
+ sqlite3_prepare_v2(m_db,
+ "INSERT INTO leaves (dataSeqNo, dataName, signerSeqNo, timestamp, isCert, cert)\
+ VALUES (?, ?, ?, ?, 1, ?)",
+ -1, &statement, nullptr);
+
+ sqlite3_bind_int(statement, 1, leaf.getDataSeqNo());
+ sqlite3_bind_block(statement, 2, leaf.getDataName().wireEncode(), SQLITE_TRANSIENT);
+ sqlite3_bind_int(statement, 3, leaf.getSignerSeqNo());
+ sqlite3_bind_int(statement, 4, leaf.getTimestamp());
+ sqlite3_bind_block(statement, 5, data.wireEncode(), SQLITE_TRANSIENT);
+
+ int result = sqlite3_step(statement);
+ sqlite3_finalize(statement);
+
+ if (result == SQLITE_OK || result == SQLITE_DONE) {
+ m_nextLeafSeqNo++;
+ return true;
+ }
+
+ return false;
+}
+
+std::pair<shared_ptr<Leaf>, shared_ptr<Data>>
+Db::getLeaf(const NonNegativeInteger& seqNo)
+{
+ sqlite3_stmt* statement;
+ sqlite3_prepare_v2(m_db,
+ "SELECT dataName, signerSeqNo, timestamp, cert\
+ FROM leaves WHERE dataSeqNo=?",
+ -1, &statement, nullptr);
+
+ sqlite3_bind_int(statement, 1, seqNo);
+
+ if (sqlite3_step(statement) == SQLITE_ROW) {
+ auto leaf = make_shared<Leaf>(Name(sqlite3_column_block(statement, 0)),
+ sqlite3_column_int(statement, 2),
+ seqNo,
+ sqlite3_column_int(statement, 1));
+
+ shared_ptr<Data> data;
+ if (sqlite3_column_bytes(statement, 3) != 0) {
+ data = make_shared<Data>(sqlite3_column_block(statement, 3));
+ }
+ sqlite3_finalize(statement);
+ return std::make_pair(leaf, data);
+ }
+ else {
+ sqlite3_finalize(statement);
+ return std::make_pair(nullptr, nullptr);
+ }
+}
+
+const NonNegativeInteger&
+Db::getMaxLeafSeq()
+{
+ sqlite3_stmt* statement;
+
+ sqlite3_prepare_v2(m_db, "SELECT count(dataSeqNo) FROM leaves", -1, &statement, nullptr);
+ if (sqlite3_step(statement) == SQLITE_ROW)
+ m_nextLeafSeqNo = sqlite3_column_int(statement, 0);
+ else
+ throw Error("getMaxLeafSeq: db error");
+
+ sqlite3_finalize(statement);
+ return m_nextLeafSeqNo;
+}
+
+} // namespace nsl
diff --git a/core/db.hpp b/core/db.hpp
new file mode 100644
index 0000000..503b562
--- /dev/null
+++ b/core/db.hpp
@@ -0,0 +1,84 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_CORE_DB_HPP
+#define NSL_CORE_DB_HPP
+
+#include "common.hpp"
+#include "leaf.hpp"
+#include "util/non-negative-integer.hpp"
+#include <vector>
+
+struct sqlite3;
+
+namespace nsl {
+
+class Db : noncopyable
+{
+public:
+ class Error : public std::runtime_error
+ {
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
+
+public:
+ void
+ open(const std::string& dbDir);
+
+ bool
+ insertSubTreeData(size_t level, const NonNegativeInteger& seqNo,
+ const Data& data,
+ bool isFull = true,
+ const NonNegativeInteger& nextLeafSeqNo = 0);
+
+ shared_ptr<Data>
+ getSubTreeData(size_t level, const NonNegativeInteger& seqNo);
+
+ std::vector<shared_ptr<Data>>
+ getPendingSubTrees();
+
+ bool
+ insertLeafData(const Leaf& leaf);
+
+ bool
+ insertLeafData(const Leaf& leaf, const Data& data);
+
+ std::pair<shared_ptr<Leaf>, shared_ptr<Data>>
+ getLeaf(const NonNegativeInteger& seqNo);
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ const NonNegativeInteger&
+ getMaxLeafSeq();
+
+private:
+ sqlite3* m_db;
+
+ NonNegativeInteger m_nextLeafSeqNo;
+};
+
+} // namespace nsl
+
+#endif // NSL_CORE_DB_HPP
diff --git a/core/intermediate-node.cpp b/core/intermediate-node.cpp
deleted file mode 100644
index 11c37ff..0000000
--- a/core/intermediate-node.cpp
+++ /dev/null
@@ -1,72 +0,0 @@
-/* -*- 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 "intermediate-node.hpp"
-
-namespace nsl {
-
-bool
-IntermediateNode::isFull() const
-{
- return m_isFull;
-}
-
-
-
-bool
-IntermediateNode::setIsFull(uint64_t number)
-{
- Index info = this->getIndex();
- uint64_t num = info.number;
- uint64_t lev = info.level;
- if (double(num) + pow(2, lev) <= number)
- {
- m_isFull = true;
- return m_isFull;
- }
- else
- {
- m_isFull = false;
- return m_isFull;
- }
-
-}
-
-
-
-void
-IntermediateNode::computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r)
-{
- ndn::Buffer tmp_buf = *hash_l;
- for (int i = 0; i < hash_r->size(); i++)
- {
- tmp_buf.push_back((*hash_r)[i]);
- }
- ndn::ConstBufferPtr digest = ndn::crypto::sha256(tmp_buf.buf(), tmp_buf.size());
- this->setHash(digest);
-}
-
-void IntermediateNode::computeHashOneSide(ndn::ConstBufferPtr hash_l)
-{
- ndn::ConstBufferPtr digest = ndn::crypto::sha256(hash_l->buf(), hash_l->size());
- this->setHash(digest);
-}
-
-} // namespace nsl
diff --git a/core/intermediate-node.hpp b/core/intermediate-node.hpp
deleted file mode 100644
index c2c3c0b..0000000
--- a/core/intermediate-node.hpp
+++ /dev/null
@@ -1,76 +0,0 @@
-/* -*- 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>
- */
-#ifndef NLS_CORE_INTERMEDIATE_NODE_HPP
-#define NLS_CORE_INTERMEDIATE_NODE_HPP
-
-#include <stddef.h>
-#include <math.h>
-#include <ndn-cxx/util/crypto.hpp>
-#include "node.hpp"
-
-
-namespace nsl {
-
-
-class IntermediateNode : public Node
-{
-public:
-
- IntermediateNode()
- : Node()
- {
- }
-
- IntermediateNode(uint64_t sequenceNumber, uint64_t level, time_t timestamp)
- : Node(sequenceNumber, level, timestamp), m_isFull(false)
- {
- }
-
- IntermediateNode(const IntermediateNode& new_node)
- :Node(new_node.getIndex().number, new_node.getIndex().level, 0)
- {
- m_isFull = new_node.isFull();
- this->setHash(new_node.getHash());
- }
-
- ~IntermediateNode()
- {
- }
-
- bool
- setIsFull(uint64_t totalLeafNum);
-
- bool
- isFull() const;
-
- void
- computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r);
-
- void
- computeHashOneSide(ndn::ConstBufferPtr hash_l);
-
-private:
- bool m_isFull;
-};
-
-} // namespace nsl
-
-#endif // NLS_CORE_INTERMEDIATE_NODE_HPP
diff --git a/core/leaf.cpp b/core/leaf.cpp
index 33ee527..e862d37 100644
--- a/core/leaf.cpp
+++ b/core/leaf.cpp
@@ -16,25 +16,239 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
+
#include "leaf.hpp"
+#include "tlv.hpp"
+#include <ndn-cxx/security/digest-sha256.hpp>
+#include <ndn-cxx/encoding/block-helpers.hpp>
+#include <ndn-cxx/util/crypto.hpp>
-namespace nsl{
+namespace nsl {
-ndn::ConstBufferPtr
-Leaf::getData() const
+const Name Leaf::EMPTY_NAME;
+const size_t Leaf::N_LOGGER_LEAF_SUFFIX = 4;
+const ssize_t Leaf::OFFSET_LEAF_SEQNO = -2;
+const ssize_t Leaf::OFFSET_LEAF_HASH = -1;
+
+Leaf::Leaf()
{
- return m_data;
}
-
+Leaf::Leaf(const Name& dataName,
+ const Timestamp& timestamp,
+ const NonNegativeInteger& dataSeqNo,
+ const NonNegativeInteger& signerSeqNo,
+ const Name& loggerName)
+ : m_dataName(dataName)
+ , m_timestamp(timestamp)
+ , m_dataSeqNo(dataSeqNo)
+ , m_signerSeqNo(signerSeqNo)
+ , m_loggerName(loggerName)
+{
+ if (m_dataSeqNo < m_signerSeqNo)
+ throw Error("Leaf: signer seqNo should be less than the data seqNo");
+}
void
-Leaf::computeHash()
+Leaf::setDataSeqNo(const NonNegativeInteger& dataSeqNo)
{
- ndn::ConstBufferPtr digest = ndn::crypto::sha256(m_data->buf(), m_data->size());
- this->setHash(digest);
+ if (dataSeqNo < m_signerSeqNo)
+ throw Error("Leaf: signer seqNo should be less than the data seqNo");
+
+ m_wire.reset();
+ m_dataSeqNo = dataSeqNo;
+}
+
+void
+Leaf::setDataName(const Name& dataName)
+{
+ m_wire.reset();
+ m_dataName = dataName;
+}
+
+void
+Leaf::setTimestamp(const Timestamp& timestamp)
+{
+ m_wire.reset();
+ m_timestamp = timestamp;
+}
+
+void
+Leaf::setSignerSeqNo(const NonNegativeInteger& signerSeqNo)
+{
+ if (m_dataSeqNo < signerSeqNo)
+ throw Error("Leaf: signer seqNo should be less than the data seqNo");
+
+ m_wire.reset();
+ m_signerSeqNo = signerSeqNo;
+}
+
+void
+Leaf::setLoggerName(const Name& loggerName)
+{
+ m_loggerName = loggerName;
+}
+
+ndn::ConstBufferPtr
+Leaf::getHash() const
+{
+ wireEncode();
+ return ndn::crypto::sha256(m_wire.wire(), m_wire.size());
+}
+
+shared_ptr<Data>
+Leaf::encode() const
+{
+ auto data = make_shared<Data>();
+
+ ndn::ConstBufferPtr hash = getHash();
+
+ // Name
+ Name dataName = m_loggerName;
+ dataName.appendNumber(m_dataSeqNo).append(hash->buf(), hash->size());
+ data->setName(dataName);
+
+ // Content
+ data->setContent(wireEncode());
+
+ // Signature
+ ndn::DigestSha256 sig;
+ data->setSignature(sig);
+
+ Block sigValue(tlv::SignatureValue,
+ ndn::crypto::sha256(data->wireEncode().value(),
+ data->wireEncode().value_size() -
+ data->getSignature().getValue().size()));
+ data->setSignatureValue(sigValue);
+
+ data->wireEncode();
+
+ return data;
+}
+
+void
+Leaf::decode(const Data& data)
+{
+ const Name& dataName = data.getName();
+
+ if (!m_loggerName.isPrefixOf(dataName))
+ throw Error("decode: leaf data name does not match logger name");
+
+ if (m_loggerName.size() + N_LOGGER_LEAF_SUFFIX != dataName.size())
+ throw Error("decode: leaf data name does not follow the naming convention");
+
+ ndn::ConstBufferPtr leafHash;
+ NonNegativeInteger dataSeqNo;
+ try {
+ leafHash = make_shared<ndn::Buffer>(dataName.get(OFFSET_LEAF_HASH).value(),
+ dataName.get(OFFSET_LEAF_HASH).value_size());
+
+ dataSeqNo = dataName.get(OFFSET_LEAF_SEQNO).toNumber();
+ }
+ catch (tlv::Error&) {
+ throw Error("decode: logger name encoding error");
+ }
+
+ wireDecode(data.getContent().blockFromValue());
+
+ if (*leafHash != *getHash())
+ throw Error("decode: inconsistent hash");
+
+ if (m_dataSeqNo != dataSeqNo)
+ throw Error("decode: seqNo does not match");
+}
+
+template<ndn::encoding::Tag TAG>
+size_t
+Leaf::wireEncode(ndn::EncodingImpl<TAG>& block) const
+{
+ size_t totalLength = 0;
+
+ totalLength += ndn::prependNonNegativeIntegerBlock(block, tlv::SignerSeqNo, m_signerSeqNo);
+ totalLength += ndn::prependNonNegativeIntegerBlock(block, tlv::DataSeqNo, m_dataSeqNo);
+ totalLength += ndn::prependNonNegativeIntegerBlock(block, tlv::Timestamp, m_timestamp);
+ totalLength += m_dataName.wireEncode(block);
+
+ totalLength += block.prependVarNumber(totalLength);
+ totalLength += block.prependVarNumber(tlv::LoggerLeaf);
+
+ return totalLength;
+}
+
+template size_t
+Leaf::wireEncode<ndn::encoding::EncoderTag>(ndn::EncodingImpl<ndn::encoding::EncoderTag>&) const;
+
+template size_t
+Leaf::wireEncode<ndn::encoding::EstimatorTag>(ndn::EncodingImpl<ndn::encoding::EstimatorTag>&) const;
+
+
+const Block&
+Leaf::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;
+}
+
+void
+Leaf::wireDecode(const Block& wire)
+{
+ if (!wire.hasWire()) {
+ throw Error("The supplied block does not contain wire format");
+ }
+
+ m_wire = wire;
+ m_wire.parse();
+
+ if (m_wire.type() != tlv::LoggerLeaf)
+ throw tlv::Error("Unexpected TLV type when decoding logger leaf");
+
+ Block::element_const_iterator it = m_wire.elements_begin();
+
+ // the first block must be dataName
+ if (it != m_wire.elements_end() && it->type() == tlv::Name) {
+ m_dataName.wireDecode(*it);
+ it++;
+ }
+ else
+ throw Error("The first sub-TLV is not Name");
+
+ // the second block must be timestamp
+ if (it != m_wire.elements_end() && it->type() == tlv::Timestamp) {
+ m_timestamp = readNonNegativeInteger(*it);
+ it++;
+ }
+ else
+ throw Error("The second sub-TLV is not Timestamp");
+
+ // the third block must be DataSeqNo
+ if (it != m_wire.elements_end() && it->type() == tlv::DataSeqNo) {
+ m_dataSeqNo = readNonNegativeInteger(*it);
+ it++;
+ }
+ else
+ throw Error("The third sub-TLV is not DataSeqNo");
+
+ // the third block must be SignerSeqNo
+ if (it != m_wire.elements_end() && it->type() == tlv::SignerSeqNo) {
+ m_signerSeqNo = readNonNegativeInteger(*it);
+ it++;
+ }
+ else
+ throw Error("The fourth sub-TLV is not SignerSeqNo");
+
+ if (it != m_wire.elements_end())
+ throw Error("No more sub-TLV in LoggerLeaf");
}
} // namespace nsl
diff --git a/core/leaf.hpp b/core/leaf.hpp
index 9576c09..3f8b0a5 100644
--- a/core/leaf.hpp
+++ b/core/leaf.hpp
@@ -16,56 +16,128 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#ifndef NLS_CORE_LEAF_HPP
-#define NLS_CORE_LEAF_HPP
-#include <vector>
-#include <ndn-cxx/util/crypto.hpp>
-#include "node.hpp"
+#ifndef NSL_CORE_LEAF_HPP
+#define NSL_CORE_LEAF_HPP
+
+#include "common.hpp"
+#include "util/non-negative-integer.hpp"
+#include "util/timestamp.hpp"
+#include <ndn-cxx/encoding/buffer.hpp>
namespace nsl {
-class Leaf : public Node
+class Leaf
{
public:
-
- Leaf()
- : Node()
+ class Error : public std::runtime_error
{
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
+
+public:
+ Leaf();
+
+ Leaf(const Name& dataName,
+ const Timestamp& timestamp,
+ const NonNegativeInteger& leafSeqNo,
+ const NonNegativeInteger& signerSeqNo,
+ const Name& loggerName = EMPTY_NAME);
+
+ void
+ setDataSeqNo(const NonNegativeInteger& dataSeqNo);
+
+ const NonNegativeInteger&
+ getDataSeqNo() const
+ {
+ return m_dataSeqNo;
}
+ void
+ setDataName(const Name& dataName);
- Leaf(ndn::ConstBufferPtr data, uint64_t sequenceNumber, uint64_t level, time_t timestamp)
- : Node(sequenceNumber, level, timestamp), m_data(data)
+ const Name&
+ getDataName() const
{
+ return m_dataName;
}
+ void
+ setTimestamp(const Timestamp& timestamp);
- Leaf(const Leaf& new_leaf)
- : Node(new_leaf.getIndex().number, new_leaf.getIndex().level, new_leaf.getTimestamp())
+ const Timestamp&
+ getTimestamp() const
{
- m_data = new_leaf.getData();
- this->setHash(new_leaf.getHash());
+ return m_timestamp;
}
+ void
+ setSignerSeqNo(const NonNegativeInteger& signerSeqNo);
- ~Leaf()
+ const NonNegativeInteger&
+ getSignerSeqNo() const
{
+ return m_signerSeqNo;
+ }
+
+ void
+ setLoggerName(const Name& loggerName);
+
+ const Name&
+ getLoggerName() const
+ {
+ return m_loggerName;
}
ndn::ConstBufferPtr
- getData() const;
+ getHash() const;
+ shared_ptr<Data>
+ encode() const;
void
- computeHash();
+ decode(const Data& data);
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ /// @brief Encode to a wire format or estimate wire format
+ template<ndn::encoding::Tag TAG>
+ size_t
+ wireEncode(ndn::EncodingImpl<TAG>& block) const;
+
+ /// @brief Encode to a wire format
+ const Block&
+ wireEncode() const;
+
+ /// @brief Decode from a wire format
+ void
+ wireDecode(const Block& wire);
+
+public:
+ static const Name EMPTY_NAME;
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ static const size_t N_LOGGER_LEAF_SUFFIX;
+ static const ssize_t OFFSET_LEAF_SEQNO;
+ static const ssize_t OFFSET_LEAF_HASH;
private:
- ndn::ConstBufferPtr m_data;
+ Name m_dataName;
+ Timestamp m_timestamp;
+ NonNegativeInteger m_dataSeqNo;
+ NonNegativeInteger m_signerSeqNo;
+
+ mutable Block m_wire;
+
+ Name m_loggerName;
};
} // namespace nsl
-#endif // NLS_CORE_LEAF_HPP
+#endif // NSL_CORE_LEAF_HPP
diff --git a/core/merkle-tree-cache.cpp b/core/merkle-tree-cache.cpp
deleted file mode 100644
index a7f2dc0..0000000
--- a/core/merkle-tree-cache.cpp
+++ /dev/null
@@ -1,353 +0,0 @@
-/* -*- 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-cache.hpp"
-
-
-
-namespace nsl {
-
-typedef std::map<Index, int>::iterator tree_iter;
-typedef std::map<uint64_t, ndn::ConstBufferPtr>::iterator leaf_iter;
-
-Index
-MerkleTreeCache::findSubTree(Index nodeIndex)
-{
- if(nodeIndex.level % 6 == 0 && nodeIndex.level != 0)
- {
- return nodeIndex;
- }
- else
- {
- uint8_t step = (uint64_t(nodeIndex.level / 6) + 1) * 6 - nodeIndex.level;
- for (int i = 0; i < step; i++)
- {
- nodeIndex.number -= nodeIndex.number % int(pow(2, nodeIndex.level + 1));
- nodeIndex.level += 1;
- }
- return nodeIndex;
- }
-}
-
-Index
-MerkleTreeCache::getParentRootIndex(Index thisRootIndex)
-{
- Index parentIndex;
- parentIndex.number = thisRootIndex.number;
- parentIndex.level = thisRootIndex.level;
- for (int i = 0; i < 6; i++)
- {
- parentIndex.number -= parentIndex.number%int(pow(2, parentIndex.level + 1));
- parentIndex.level += 1;
- }
- return parentIndex;
-}
-
-
-void
-MerkleTreeCache::removeSubTree()
-{
- if (doesCacheFull() > 1)
- {
- // find out the least recent used subtree
- tree_iter _i = m_timeFromLastUse.begin();
- int idle_time_max = -1;
- Index rm_index_max = _i->first;
- int idle_time_min = _i->second;
- Index rm_index_min = _i->first;
- for (_i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
- {
- if (_i->second > idle_time_max && m_cachedTree[_i->first]->getRemainPosition() == 0)
- {
- idle_time_max = _i->second;
- rm_index_max = _i->first;
- }
- if (_i->second < idle_time_min)
- {
- idle_time_min = _i->second;
- rm_index_min = _i->first;
- }
- }
-
- // refresh the timer
- for (_i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
- {
- _i->second -= idle_time_min;
- }
- // update to database and remove subtree from cache and timer,only when there is full subtree
- if (m_cachedTree[rm_index_max]->getRemainPosition() == 0 && idle_time_max >= 0)
- {
- m_database.addSubTree(m_cachedTree[rm_index_max]);
- m_cachedTree.erase(rm_index_max);
- m_timeFromLastUse.erase(rm_index_max);
- }
- }
-}
-
-void
-MerkleTreeCache::removeLeaf()
-{
- if (doesCacheFull() % 2 != 0)
- {
- // randomly pick a old leaf to remove
- leaf_iter _i = m_leavesData.begin();
- while (_i->first == m_nLeaves - 1)
- {
- _i++;
- }
- m_database.addLeafInfo(_i->first, _i->second);
- m_leavesData.erase(_i->first);
- }
-}
-
-
-
-
-
-// Do not have to deal with NOT-IN-MEMORY issue because not full tree will not in database
-void
-MerkleTreeCache::addLeaf(Leaf newLeaf)
-{
- ndn::ConstBufferPtr data = newLeaf.getData();
- removeLeaf(); // test whether is full, if so, delete an old item
- m_leavesData[newLeaf.getIndex().number] = data;
- Index leafIndex = newLeaf.getIndex();
- ndn::ConstBufferPtr hash = newLeaf.getHash();
-
- Index subTreeRoot = findSubTree(leafIndex);
- if (m_nLeaves > 0)
- {
- // Not full so that always in memory
- m_cachedTree[subTreeRoot]->addNode(hash);
- m_nLeaves += 1;
- }
- else
- {
- SubTreePtr newTree(new SubTree(subTreeRoot,
- ndn::bind(&MerkleTreeCache::update, this,
- subTreeRoot, _1, _2)));
- newTree->addNode(hash);
- removeSubTree();
- m_cachedTree[subTreeRoot] = newTree;
- m_nLeaves = 1;
- m_nLevels = 1;
- }
-
- for (tree_iter _i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
- {
- _i->second += 1;
- }
- m_timeFromLastUse[subTreeRoot] = 0; // if not exist, automatically create one and set to 0
-}
-
-
-// Deal with loading from database
-// database update
-// consider add to database when a subtree is full
-void
-MerkleTreeCache::update(Index subRootIndex, uint8_t subRemainNum, ndn::ConstBufferPtr subRootHash)
-{
- if ((subRootIndex.level / 6) < m_nLevels)
- {
- Index parentRoot = getParentRootIndex(subRootIndex);
-
- // bring in memory if parentRoot not in
- if (m_cachedTree.count(parentRoot) <= 0)
- {
- loadSubTreeFromDatabase(parentRoot);
- }
- m_cachedTree[parentRoot]->updateLeafHash(subRootIndex, subRootHash);
- m_timeFromLastUse[parentRoot] = 0;
- }
-
- if (subRemainNum == 0) // add the current full subtree into the database
- {
- Index parentRoot = getParentRootIndex(subRootIndex);
- if ((subRootIndex.level / 6) >= m_nLevels) // if it is the top subtree
- {
- SubTreePtr newTree(new SubTree(parentRoot,
- ndn::bind(&MerkleTreeCache::update, this,
- parentRoot, _1, _2)));
- removeSubTree();
- m_cachedTree[parentRoot] = newTree;
- m_nLevels += 1;
- m_timeFromLastUse[parentRoot] = 0;
- m_cachedTree[parentRoot]->updateLeafHash(subRootIndex, subRootHash);
- }
- Index newRoot;
- newRoot.level = subRootIndex.level;
- newRoot.number = subRootIndex.number + int(pow(2, subRootIndex.level));
- // whether the updated subtree is already full,
- // but its child subtree is not full.
- // To avoid create multiple sibling new subtree
- if (m_cachedTree.count(newRoot) == 0)
- {
- SubTreePtr newTree(new SubTree(newRoot,
- ndn::bind(&MerkleTreeCache::update, this,
- newRoot, _1, _2)));
- removeSubTree();
- m_cachedTree[newRoot] = newTree;
- m_timeFromLastUse[newRoot] = 0;
- }
- }
-}
-
-
-NodePtr
-MerkleTreeCache::queryNode(Index nodeIndex)
-{
- // update timer
- for (tree_iter _i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
- {
- _i->second += 1;
- }
-
- Index rootIndex = findSubTree(nodeIndex);
- ndn::ConstBufferPtr hash;
- if (m_cachedTree.count(rootIndex) == 0)
- {
- loadSubTreeFromDatabase(rootIndex);
- }
- hash = m_cachedTree[rootIndex]->getHash(nodeIndex);
-
- if (nodeIndex.level == 0)
- {
- if (m_leavesData.count(nodeIndex.number) == 0)
- {
- loadLeafFromDatabase(nodeIndex.number);
- }
- NodePtr node_ptr(new Leaf(m_leavesData[nodeIndex.number],
- nodeIndex.number, nodeIndex.level, 0));
- node_ptr->setHash(hash);
- return node_ptr;
- }
- else
- {
- NodePtr node_ptr(new IntermediateNode(nodeIndex.number, nodeIndex.level, 0));
- node_ptr->setHash(hash);
- ((IntermediateNode*)node_ptr.get())->setIsFull(m_nLeaves);
- return node_ptr;
- }
-}
-
-
-bool
-MerkleTreeCache::doesNodeExist(Index nodeIndex)
-{
- Index rootIndex = findSubTree(nodeIndex);
- if (m_cachedTree.count(rootIndex) > 0)
- {
- return true;
- }
- else
- {
- bool result = m_database.doesSubTreeExist(rootIndex);
- return result;
- }
-}
-
-
-
-SubTreePtr
-MerkleTreeCache::decoding(std::string subTreeInfo)
-{
- uint64_t seq = 0;
- unsigned char tmp = 0;
- for (int i = 7; i >= 0; i--)
- {
- tmp = subTreeInfo[i];
- seq += tmp;
- seq = seq << 8;
- }
- seq = seq >> 8;
- uint64_t lev = 0;
- for (int i = 15; i >= 8; i--)
- {
- tmp = subTreeInfo[i];
- lev += tmp;
- lev = lev << 8;
- }
- lev = lev >> 8;
- Index rootIndex;
- rootIndex.number = seq;
- rootIndex.level = lev;
- SubTreePtr newTree(new SubTree(rootIndex,
- ndn::bind(&MerkleTreeCache::update, this,
- rootIndex, _1, _2)));
- uint8_t remain = subTreeInfo[16]; // not useful
- if (remain == 0)
- {
- std::vector<ndn::BufferPtr> hashes;
- for (int i = 0; i < 127; i++)
- {
- ndn::Buffer buf;
- for(int j = 17 + 32 * i; j < 49 + 32 * i; j++)
- {
- buf.push_back(subTreeInfo[j]);
- }
- ndn::BufferPtr thisBuf = ndn::make_shared<ndn::Buffer>(buf);
- hashes.push_back(thisBuf);
- }
- newTree->resumeFromString(remain, hashes);
- return newTree;
- }
- else
- {
- std::vector<ndn::BufferPtr> hashes;
- uint8_t lastNo = 126 - remain;
- for (int i = 63; i <= lastNo; i++)
- {
- ndn::Buffer buf;
- for(int j = 17 + 32 * i; j < 49 + 32 * i; j++)
- {
- buf.push_back(subTreeInfo[j]);
- }
- ndn::BufferPtr thisBuf = ndn::make_shared<ndn::Buffer>(buf);
- hashes.push_back(thisBuf);
- }
- newTree->resumeFromString(remain, hashes);
- return newTree;
- }
-}
-
-
-void
-MerkleTreeCache::loadSubTreeFromDatabase(Index rootIndex)
-{
- // Detect the cache limitation
- removeSubTree();
- std::string tmp_str = m_database.getSubTree(rootIndex);
- SubTreePtr newtree = decoding(tmp_str);
- m_cachedTree[rootIndex] = newtree;
- m_timeFromLastUse[rootIndex] = 0;
-}
-
-void
-MerkleTreeCache::loadLeafFromDatabase(uint64_t sequence)
-{
- // Detect the cache limitation
- removeLeaf();
- ndn::ConstBufferPtr newleaf = m_database.getLeafInfo(sequence);
- m_leavesData[sequence] = newleaf;
-}
-
-
-} // namespace nsl
diff --git a/core/merkle-tree-cache.hpp b/core/merkle-tree-cache.hpp
deleted file mode 100644
index 97e8908..0000000
--- a/core/merkle-tree-cache.hpp
+++ /dev/null
@@ -1,176 +0,0 @@
-/* -*- 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>
- */
-#ifndef NLS_CORE_MERKLE_TREE_CACHE_HPP
-#define NLS_CORE_MERKLE_TREE_CACHE_HPP
-
-#include <map>
-#include <vector>
-
-#include "sub-tree.hpp"
-#include "leaf.hpp"
-#include "intermediate-node.hpp"
-#include "merkle-tree-sqlite3.hpp"
-
-
-namespace nsl {
-
-
-typedef ndn::shared_ptr<const SubTree> ConstSubTreePtr;
-typedef ndn::shared_ptr<SubTree> SubTreePtr;
-typedef ndn::shared_ptr<const Node> ConstNodePtr;
-typedef ndn::shared_ptr<Node> NodePtr;
-
-class MerkleTreeCache
-{
-public:
-
- MerkleTreeCache()
- :m_nLevels(0),
- m_nLeaves(0)
- {
- }
-
- ~MerkleTreeCache()
- {
- }
-
- uint8_t
- getLevel()
- {
- return m_nLevels;
- }
-
- uint64_t
- getLeaves()
- {
- return m_nLeaves;
- }
-
- SubTreePtr
- getSubTree(Index rootIndex)
- {
- if (m_cachedTree.count(rootIndex) > 0)
- {
- //std::cout<<"I'm here!"<<int(m_cachedTree[rootIndex]->getRemainPosition())<<std::endl;
- return m_cachedTree[rootIndex];
- }
- else
- {
- std::string treeString = m_database.getSubTree(rootIndex);
- SubTreePtr newtree = decoding(treeString);
- return newtree;
- }
- }
-
- // Do the update when a subtree is full
- // Iteratively: find parent --> check full --> ... --> if not full -->
- // create subtree --> create subsubtree --> ... --> until down to the leaf
- // invoke a subtree.updateHash(), and decide whether to add new subtrees according to the callback
- // remainPosition value.
- void
- update(Index subRootIndex, uint8_t subRemainNum, ndn::ConstBufferPtr subRootHash);
-
- void
- addLeaf(Leaf newLeaf);
-
- NodePtr
- queryNode(Index nodeIndex);
-
- bool
- doesNodeExist(Index nodeIndex);
-
- void
- loadSubTreeFromDatabase(Index rootIndex);
-
- void
- loadLeafFromDatabase(uint64_t sequence);
-
-
-
- SubTreePtr
- decoding(std::string subTreeInfo);
-
- // remove the comment to test sqlite3 function
- // MerkleTreeSqlite3 m_database;
-
- // To show the exact size of the cache
- // std::map<Index, SubTreePtr> m_cachedTree;
- // std::map<uint64_t, ndn::ConstBufferPtr> m_leavesData;
-
-
-private:
-
- // find which subTree the node belongs to (not include root node)
- Index
- findSubTree(Index nodeIndex);
-
- // find a subTree's parent root index
- Index
- getParentRootIndex(Index thisRootIndex);
-
-
- // To be finished
- uint8_t
- doesCacheFull()
- {
- if (m_cachedTree.size() >= 3 && m_leavesData.size() >= 64)
- {
- return 3;
- }
- else if (m_cachedTree.size() >= 3 && m_leavesData.size() < 64)
- {
- return 2;
- }
- else if (m_cachedTree.size() < 3 && m_leavesData.size() >= 64)
- {
- return 1;
- }
- else
- {
- return 0;
- }
- }
-
- // choose a cache item to remove,
- // exactly remove items from cache only when: 1)have full subtrees 2)cache is full
- void
- removeSubTree();
-
- void
- removeLeaf();
-
-private:
- // partly in cache, completely in db
- std::map<Index, SubTreePtr> m_cachedTree;
- std::map<uint64_t, ndn::ConstBufferPtr> m_leavesData; //starts from 0(same as leaf)
-
- // completely in memory, add & delete with time
- std::map<Index, int> m_timeFromLastUse;
- uint8_t m_nLevels; // levels counted based on subtree unit
- uint64_t m_nLeaves; // sequence number + 1
-
- // sqlite3 database
- MerkleTreeSqlite3 m_database;
-};
-
-} // namespace nsl
-
-#endif // NLS_CORE_MERKLE_TREE_CACHE_HPP
diff --git a/core/merkle-tree-sqlite3.cpp b/core/merkle-tree-sqlite3.cpp
deleted file mode 100644
index 1844ad4..0000000
--- a/core/merkle-tree-sqlite3.cpp
+++ /dev/null
@@ -1,332 +0,0 @@
-/* -*- 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-sqlite3.hpp"
-#include <stdlib.h>
-#include <boost/filesystem.hpp>
-
-
-namespace nsl {
-
-static const std::string INIT_SUBTREE_TABLE = "\
-CREATE TABLE IF NOT EXISTS \n \
- SubTree( \n \
- subTree_sequence INTEGER, \n \
- subTree_level INTEGER, \n \
- subTree_info BLOB, \n \
- \
- PRIMARY KEY (subTree_sequence, subTree_level) \n \
- ); \n \
- \
-CREATE INDEX subTree_index ON SubTree(subTree_sequence); \n \
-";
-
-static const std::string INIT_LEAF_TABLE = "\
-CREATE TABLE IF NOT EXISTS \n \
- Leaf( \n \
- leaf_sequence INTEGER, \n \
- leaf_info BLOB, \n \
- \
- PRIMARY KEY (leaf_sequence) \n \
- ); \n \
- \
-CREATE INDEX leaf_index ON Leaf(leaf_sequence); \n \
-";
-
-/**
- * A utility function to call the normal sqlite3_bind_text where the value and length are
- * value.c_str() and value.size().
- */
-static int sqlite3_bind_text(sqlite3_stmt* statement,
- int index,
- const std::string& value,
- void(*destructor)(void*))
-{
- return sqlite3_bind_text(statement, index, value.c_str(), value.size(), destructor);
-}
-
-
-MerkleTreeSqlite3::MerkleTreeSqlite3()
-{
- boost::filesystem::path identityDir = boost::filesystem::path("/Users/GPZ/Develop/nslDB");
- boost::filesystem::create_directories(identityDir);
-
- /// @todo Add define for windows/unix in wscript. The following may completely fail on windows
- int res = sqlite3_open_v2((identityDir / "nsl-merkle-tree.db").c_str(), &m_database,
- SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE,
-#ifdef NDN_CXX_DISABLE_SQLITE3_FS_LOCKING
- "unix-dotfile"
-#else
- 0
-#endif
- );
-
- if (res != SQLITE_OK)
- std::cout << "DB cannot be opened/created";
-
- //Check if SubTree table exists;
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "SELECT name FROM sqlite_master WHERE type='table' And name='SubTree'",
- -1, &statement, 0);
- res = sqlite3_step(statement);
-
- bool SubTreeTableExists = false;
- if (res == SQLITE_ROW)
- SubTreeTableExists = true;
-
- sqlite3_finalize(statement);
-
- if (!SubTreeTableExists)
- {
- char* errorMessage = 0;
- res = sqlite3_exec(m_database, INIT_SUBTREE_TABLE.c_str(), NULL, NULL, &errorMessage);
-
- if (res != SQLITE_OK && errorMessage != 0)
- {
- sqlite3_free(errorMessage);
- }
- }
-
- //Check if Leaf table exists;
- sqlite3_prepare_v2(m_database,
- "SELECT name FROM sqlite_master WHERE type='table' And name='Leaf'",
- -1, &statement, 0);
- res = sqlite3_step(statement);
-
- bool LeafTableExists = false;
- if (res == SQLITE_ROW)
- LeafTableExists = true;
-
- sqlite3_finalize(statement);
-
- if (!LeafTableExists)
- {
- char* errorMessage = 0;
- res = sqlite3_exec(m_database, INIT_LEAF_TABLE.c_str(), NULL, NULL, &errorMessage);
-
- if (res != SQLITE_OK && errorMessage != 0)
- {
- sqlite3_free(errorMessage);
- }
- }
-
-}
-
-
-MerkleTreeSqlite3::~MerkleTreeSqlite3()
-{
-}
-
-
-void
-MerkleTreeSqlite3::addSubTree(SubTreePtr oldSubTree)
-{
- Index old_idx = oldSubTree->getRootIndex();
- std::string old_info = oldSubTree->encoding();
-
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "INSERT OR REPLACE INTO SubTree \
- (subTree_sequence, subTree_level, subTree_info) \
- values (?, ?, ?)",
- -1, &statement, 0);
- sqlite3_bind_int64(statement, 1, old_idx.number);
- sqlite3_bind_int64(statement, 2, old_idx.level);
- sqlite3_bind_text(statement, 3, old_info, SQLITE_TRANSIENT);
- sqlite3_step(statement);
- sqlite3_finalize(statement);
-}
-
-
-std::string
-MerkleTreeSqlite3::getSubTree(Index rootIndex)
-{
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "SELECT subTree_info FROM SubTree \
- WHERE subTree_sequence=? AND subTree_level=?",
- -1, &statement, 0);
- sqlite3_bind_int64(statement, 1, rootIndex.number);
- sqlite3_bind_int64(statement, 2, rootIndex.level);
- int res = sqlite3_step(statement);
- std::string result;
- if (res == SQLITE_ROW)
- {
- result = std::string(reinterpret_cast<const char *>(sqlite3_column_text(statement, 0)),
- sqlite3_column_bytes(statement, 0));
- sqlite3_finalize(statement);
- return result;
- }
- else
- {
- sqlite3_finalize(statement);
- return result;
- }
-}
-
-
-bool
-MerkleTreeSqlite3::doesSubTreeExist(Index rootIndex)
-{
- bool result = false;
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "SELECT count(*) FROM SubTree WHERE subTree_sequence=? AND subTree_level=?",
- -1, &statement, 0);
- sqlite3_bind_int64(statement, 1, rootIndex.number);
- sqlite3_bind_int64(statement, 2, rootIndex.level);
- int res = sqlite3_step(statement);
- if (res == SQLITE_ROW)
- {
- int countAll = sqlite3_column_int(statement, 0);
- if (countAll > 0)
- result = true;
- }
- sqlite3_finalize(statement);
- return result;
-}
-
-
-void
-MerkleTreeSqlite3::deleteSubTree(Index rootIndex)
-{
- sqlite3_stmt* stmt;
- sqlite3_prepare_v2(m_database, "DELETE FROM SubTree WHERE subTree_sequence=? AND subTree_level=?",
- -1, &stmt, 0);
- sqlite3_bind_int64(stmt, 1, rootIndex.number);
- sqlite3_bind_int64(stmt, 2, rootIndex.level);
- sqlite3_step(stmt);
- sqlite3_finalize(stmt);
-}
-
-
-void
-MerkleTreeSqlite3::getAllSubTree(std::vector<std::string> subTreeInfoList)
-{
- sqlite3_stmt* stmt;
- sqlite3_prepare_v2(m_database,
- "SELECT subTree_info FROM SubTree",
- -1, &stmt, 0);
- while (sqlite3_step(stmt) == SQLITE_ROW)
- subTreeInfoList.push_back(std::string(reinterpret_cast<const char *>
- (sqlite3_column_text(stmt, 0)),
- sqlite3_column_bytes(stmt, 0)));
-
- sqlite3_finalize(stmt);
-}
-
-
-// For leafInfo
-
-void
-MerkleTreeSqlite3::addLeafInfo(uint64_t sequence, ndn::ConstBufferPtr buf_ptr)
-{
-
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "INSERT OR REPLACE INTO Leaf \
- (leaf_sequence, leaf_info) \
- values (?, ?)", -1, &statement, 0);
- sqlite3_bind_int64(statement, 1, sequence);
- sqlite3_bind_blob(statement, 2, buf_ptr->buf(), buf_ptr->size(), SQLITE_STATIC);
- sqlite3_step(statement);
- sqlite3_finalize(statement);
-}
-
-
-ndn::ConstBufferPtr
-MerkleTreeSqlite3::getLeafInfo(uint64_t sequence)
-{
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "SELECT leaf_info FROM Leaf \
- WHERE leaf_sequence=?", -1, &statement, 0);
- sqlite3_bind_int64(statement, 1, sequence);
- int res = sqlite3_step(statement);
- if (res == SQLITE_ROW)
- {
- ndn::Buffer res_buf(sqlite3_column_blob(statement, 0), sqlite3_column_bytes(statement, 0));
- ndn::ConstBufferPtr result = ndn::make_shared<ndn::Buffer>(res_buf);
- sqlite3_finalize(statement);
- return result;
- }
- else
- {
- sqlite3_finalize(statement);
- return ndn::ConstBufferPtr();
- }
-}
-
-
-bool
-MerkleTreeSqlite3::doesLeafInfoExist(uint64_t sequence)
-{
- bool result = false;
- sqlite3_stmt* statement;
- sqlite3_prepare_v2(m_database,
- "SELECT count(*) FROM Leaf WHERE leaf_sequence=?",
- -1, &statement, 0);
- sqlite3_bind_int64(statement, 1, sequence);
- int res = sqlite3_step(statement);
- if (res == SQLITE_ROW)
- {
- int countAll = sqlite3_column_int(statement, 0);
- if (countAll > 0)
- result = true;
- }
- sqlite3_finalize(statement);
- return result;
-}
-
-
-void
-MerkleTreeSqlite3::deleteLeafInfo(uint64_t sequence)
-{
- sqlite3_stmt* stmt;
- sqlite3_prepare_v2(m_database, "DELETE FROM Leaf WHERE leaf_sequence=?",
- -1, &stmt, 0);
- sqlite3_bind_int64(stmt, 1, sequence);
- sqlite3_step(stmt);
- sqlite3_finalize(stmt);
-}
-
-
-void
-MerkleTreeSqlite3::getAllLeafInfo(std::map<uint64_t, ndn::ConstBufferPtr> leaves)
-{
- sqlite3_stmt* stmt;
- sqlite3_prepare_v2(m_database,
- "SELECT leaf_sequence, leaf_info FROM Leaf",
- -1, &stmt, 0);
- while (sqlite3_step(stmt) == SQLITE_ROW)
- {
- uint64_t seq = sqlite3_column_int64(stmt, 0);
- ndn::ConstBufferPtr buf = ndn::make_shared<ndn::Buffer>(sqlite3_column_blob(stmt, 1),
- sqlite3_column_bytes(stmt, 1));
- leaves[seq] = buf;
- }
-
- sqlite3_finalize(stmt);
-}
-
-
-} // namespace nsl
diff --git a/core/merkle-tree-sqlite3.hpp b/core/merkle-tree-sqlite3.hpp
deleted file mode 100644
index 617d20c..0000000
--- a/core/merkle-tree-sqlite3.hpp
+++ /dev/null
@@ -1,86 +0,0 @@
-/* -*- 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>
- */
-
-#ifndef NLS_CORE_MERKLE_TREE_SQLITE3_HPP
-#define NLS_CORE_MERKLE_TREE_SQLITE3_HPP
-
-#include <sqlite3.h>
-#include <map>
-#include "sub-tree.hpp"
-typedef ndn::shared_ptr<const nsl::SubTree> ConstSubTreePtr;
-typedef ndn::shared_ptr<nsl::SubTree> SubTreePtr;
-
-struct sqlite3;
-
-namespace nsl {
-
-class MerkleTreeSqlite3
-{
-public:
-
- MerkleTreeSqlite3();
-
- ~MerkleTreeSqlite3();
-
- // SubTree
- void
- addSubTree(SubTreePtr oldSubTree);
-
- std::string
- getSubTree(Index rootIndex);
-
- bool
- doesSubTreeExist(Index rootIndex);
-
- void
- deleteSubTree(Index rootIndex);
-
- void
- getAllSubTree(std::vector<std::string> subTreeInfoList);
-
-
- // LeafInfo (no need of encoding/decoding scheme)
- void
- addLeafInfo(uint64_t sequence, ndn::ConstBufferPtr buf_ptr);
-
- ndn::ConstBufferPtr
- getLeafInfo(uint64_t sequence);
-
- bool
- doesLeafInfoExist(uint64_t sequence);
-
- void
- deleteLeafInfo(uint64_t sequence);
-
- void
- getAllLeafInfo(std::map<uint64_t, ndn::ConstBufferPtr> leaves);
-
-
-private:
- sqlite3* m_database;
-
-};
-
-
-} // namespace nsl
-
-
-#endif // NLS_CORE_MERKLE_TREE_SQLITE3_HPP
diff --git a/core/merkle-tree.cpp b/core/merkle-tree.cpp
index f74af33..a579350 100644
--- a/core/merkle-tree.cpp
+++ b/core/merkle-tree.cpp
@@ -16,125 +16,205 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
+
#include "merkle-tree.hpp"
namespace nsl {
-MerkleTree::MerkleTree()
+MerkleTree::MerkleTree(Db& db)
+ : m_db(db)
+ , m_nextLeafSeqNo(0)
{
- m_nLevels = 0;
- m_nLeaves = 0;
}
-
-ConstNodePtr
-MerkleTree::getNode(const Index& index)
+MerkleTree::MerkleTree(const Name& loggerName, Db& db)
+ : m_loggerName(loggerName)
+ , m_db(db)
+ , m_nextLeafSeqNo(0)
{
- ConstNodePtr p_leav;
- if (m_cache.doesNodeExist(index))
- {
- p_leav = m_cache.queryNode(index);
- return p_leav;
+ loadPendingSubTrees();
+}
+
+MerkleTree::~MerkleTree()
+{
+ savePendingTree();
+}
+
+void
+MerkleTree::setLoggerName(const Name& loggerName)
+{
+ m_loggerName = loggerName;
+}
+
+bool
+MerkleTree::addLeaf(const NonNegativeInteger& seqNo, ndn::ConstBufferPtr hash)
+{
+ auto baseTree = m_pendingTrees[SubTreeBinary::SUB_TREE_DEPTH - 1];
+ BOOST_ASSERT(baseTree != nullptr);
+
+ NodePtr leaf = make_shared<Node>(seqNo, 0, seqNo + 1, hash);
+ return baseTree->addLeaf(leaf);
+}
+
+void
+MerkleTree::savePendingTree()
+{
+ size_t level = m_rootSubTree->getPeakIndex().level;
+ size_t step = SubTreeBinary::SUB_TREE_DEPTH - 1;
+
+ for (size_t i = level; i > 0; i -= step) {
+ auto pendingTree = m_pendingTrees[i];
+ BOOST_ASSERT(pendingTree != nullptr);
+
+ auto data = pendingTree->encode();
+ if (data != nullptr) {
+ m_db.insertSubTreeData(pendingTree->getPeakIndex().level, pendingTree->getPeakIndex().seqNo,
+ *data, false, pendingTree->getNextLeafSeqNo());
}
+ }
+}
+
+shared_ptr<Data>
+MerkleTree::getPendingSubTreeData(size_t level)
+{
+ auto it = m_pendingTrees.find(level);
+ if (it != m_pendingTrees.end())
+ return it->second->encode();
else
- return p_leav;
+ return nullptr;
}
-
-uint64_t
-MerkleTree::getLeafNum() const
+// private:
+void
+MerkleTree::loadPendingSubTrees()
{
- return m_nLeaves;
+ std::vector<shared_ptr<Data>> subtreeDatas = m_db.getPendingSubTrees();
+
+ shared_ptr<SubTreeBinary> subtree;
+ if (subtreeDatas.empty()) {
+ subtree = make_shared<SubTreeBinary>(m_loggerName,
+ Node::Index(0, SubTreeBinary::SUB_TREE_DEPTH - 1),
+ [this] (const Node::Index& idx) {
+ // std::cerr << "complete: " << idx.level << ", " << idx.seqNo << std::endl;
+ this->getNewRoot(idx);
+ },
+ [this] (const Node::Index& idx,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ // std::cerr << "update: " << idx.level << ", " << idx.seqNo << std::endl;
+ // std::cerr << "seqNo: " << seqNo << std::endl;
+ this->m_nextLeafSeqNo = seqNo;
+ this->m_hash = hash;
+ });
+ m_pendingTrees[SubTreeBinary::SUB_TREE_DEPTH - 1] = subtree;
+ m_rootSubTree = subtree;
+ return;
+ }
+
+ subtree = make_shared<SubTreeBinary>(m_loggerName,
+ [this] (const Node::Index& idx) { this->getNewRoot(idx); },
+ [this] (const Node::Index& idx,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ this->m_nextLeafSeqNo = seqNo;
+ this->m_hash = hash;
+ });
+
+ subtree->decode(*subtreeDatas[0]);
+ m_pendingTrees[subtree->getPeakIndex().level] = subtree;
+ m_rootSubTree = subtree;
+
+ shared_ptr<SubTreeBinary> parentTree = subtree;
+ for (size_t i = 1; i < subtreeDatas.size(); i++) {
+ subtree = make_shared<SubTreeBinary>(m_loggerName,
+ [this] (const Node::Index& idx) {
+ this->getNewSibling(idx);
+ },
+ [parentTree] (const Node::Index&,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ parentTree->updateLeaf(seqNo, hash);
+ });
+
+ subtree->decode(*subtreeDatas[i]);
+ if (parentTree->getPeakIndex().level + 1 - SubTreeBinary::SUB_TREE_DEPTH !=
+ subtree->getPeakIndex().level)
+ throw Error("loadPendingSubTrees: inconsistent pending subtree level");
+
+ if (parentTree->getNextLeafSeqNo() != subtree->getNextLeafSeqNo())
+ throw Error("loadPendingSubTrees: inconsistent pending subtree next leaf seqNo");
+
+ m_pendingTrees[subtree->getPeakIndex().level] = subtree;
+ parentTree = subtree;
+ }
}
-
-uint64_t
-MerkleTree::getLevel() const
+void
+MerkleTree::getNewRoot(const Node::Index& idx)
{
- return m_nLevels;
+ // save the old root tree into db
+ auto oldRoot = m_pendingTrees[idx.level];
+ BOOST_ASSERT(oldRoot != nullptr);
+ m_db.insertSubTreeData(idx.level, idx.seqNo, *oldRoot->encode());
+
+ // create a new root tree
+ Node::Index newRootIdx(0, idx.level + SubTreeBinary::SUB_TREE_DEPTH - 1);
+ auto newRoot = make_shared<SubTreeBinary>(m_loggerName, newRootIdx,
+ [this] (const Node::Index& idx) {
+ // std::cerr << "complete: " << idx.level << ", " << idx.seqNo << std::endl;
+ this->getNewRoot(idx);
+ },
+ [this] (const Node::Index& index,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ // std::cerr << "update: " << index.level << ", " << index.seqNo << std::endl;
+ // std::cerr << "seqNo: " << seqNo << std::endl;
+ this->m_nextLeafSeqNo = seqNo;
+ this->m_hash = hash;
+ });
+
+ m_pendingTrees[newRoot->getPeakIndex().level] = newRoot;
+ m_rootSubTree = newRoot;
+
+ bool result = newRoot->updateLeaf(idx.seqNo + idx.range, oldRoot->getRoot()->getHash());
+ BOOST_ASSERT(result);
+
+ // create a sibling
+ getNewSibling(idx);
}
-
-
-uint64_t
-MerkleTree::addLeaf(ndn::ConstBufferPtr info)
+void
+MerkleTree::getNewSibling(const Node::Index& idx)
{
- 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;
+ // save old sibling
+ auto oldSibling = m_pendingTrees[idx.level];
+ BOOST_ASSERT(oldSibling != nullptr);
+ m_db.insertSubTreeData(idx.level, idx.seqNo, *oldSibling->encode());
+
+ // get parent tree
+ Node::Index parentIdx(0, idx.level + SubTreeBinary::SUB_TREE_DEPTH - 1);
+ auto parent = m_pendingTrees[parentIdx.level];
+ BOOST_ASSERT(parent != nullptr);
+
+ // create a new sibling
+ Node::Index newSiblingIdx(idx.seqNo + idx.range, idx.level);
+ // std::cerr << "new Sibling: " << newSiblingIdx.level << ", " << newSiblingIdx.seqNo << std::endl;
+ auto newSibling = make_shared<SubTreeBinary>(m_loggerName, newSiblingIdx,
+ [this] (const Node::Index& idx) { this->getNewSibling(idx); },
+ [parent] (const Node::Index& index,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ // std::cerr << "update: " << index.level << ", " << index.seqNo << std::endl;
+ // std::cerr << "seqNo: " << seqNo << std::endl;
+ // std::cerr << "parent: " << parent->getRoot()->getIndex().level << ", " <<
+ // parent->getRoot()->getIndex().seqNo << std::endl;
+ bool result = parent->updateLeaf(seqNo, hash);
+ BOOST_ASSERT(result);
+ });
+
+ m_pendingTrees[newSibling->getPeakIndex().level] = newSibling;
}
-
-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
+}// namespace nsl
diff --git a/core/merkle-tree.hpp b/core/merkle-tree.hpp
index ccf73c5..3e877f1 100644
--- a/core/merkle-tree.hpp
+++ b/core/merkle-tree.hpp
@@ -16,60 +16,93 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#ifndef NLS_CORE_MERKLE_TREE_HPP
-#define NLS_CORE_MERKLE_TREE_HPP
-#include <map>
+#ifndef NSL_CORE_MERKLE_TREE_HPP
+#define NSL_CORE_MERKLE_TREE_HPP
+
+#include "common.hpp"
+#include "db.hpp"
+#include "sub-tree-binary.hpp"
#include <vector>
-#include <stddef.h>
-#include <stdint.h>
-#include <time.h>
-
-#include "leaf.hpp"
-#include "intermediate-node.hpp"
-#include "merkle-tree-cache.hpp"
-
namespace nsl {
class MerkleTree
{
public:
- MerkleTree();
-
- ~MerkleTree()
+ class Error : public std::runtime_error
{
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
+
+public:
+ /**
+ * @brief Constructor
+ */
+ MerkleTree(Db& db);
+
+ MerkleTree(const Name& loggerName, Db& db);
+
+ ~MerkleTree();
+
+ void
+ setLoggerName(const Name& loggerName);
+
+ const NonNegativeInteger&
+ getNextLeafSeqNo() const
+ {
+ return m_nextLeafSeqNo;
}
- ConstNodePtr
- getNode(const Index& index);
+ const ndn::ConstBufferPtr&
+ getRootHash() const
+ {
+ return m_hash;
+ }
- uint64_t
- getLeafNum() const;
+ bool
+ addLeaf(const NonNegativeInteger& seqNo, ndn::ConstBufferPtr hash);
- uint64_t
- getLevel() const;
+ void
+ loadPendingSubTrees();
+ void
+ savePendingTree();
- //return root hash value
- uint64_t
- addLeaf(ndn::ConstBufferPtr info);
+ shared_ptr<Data>
+ getPendingSubTreeData(size_t level);
+ std::vector<ConstSubTreeBinaryPtr>
+ getExistenceProof(const NonNegativeInteger& seqNo);
- std::vector<ConstNodePtr>
- generateProof(uint64_t version1, uint64_t version2); // version equals to leaf's index number
-
+ std::vector<ConstSubTreeBinaryPtr>
+ getConsistencyProof(const NonNegativeInteger& seqNo);
private:
- MerkleTreeCache m_cache;
- uint64_t m_nLevels;
- uint64_t m_nLeaves;
+ void
+ getNewRoot(const Node::Index& idx);
+ void
+ getNewSibling(const Node::Index& idx);
+
+private:
+ Name m_loggerName;
+ Db& m_db;
+
+ shared_ptr<SubTreeBinary> m_rootSubTree;
+ NonNegativeInteger m_nextLeafSeqNo;
+ ndn::ConstBufferPtr m_hash;
+
+ std::map<size_t, shared_ptr<SubTreeBinary>> m_pendingTrees;
};
+}// namespace nsl
-} // namespace nsl
-
-#endif // NLS_CORE_MERKLE_TREE_HPP
+#endif // NSL_CORE_MERKLE_TREE_HPP
diff --git a/core/node.cpp b/core/node.cpp
index 66921cd..11e1cd0 100644
--- a/core/node.cpp
+++ b/core/node.cpp
@@ -16,48 +16,108 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
#include "node.hpp"
+#include <ndn-cxx/util/digest.hpp>
+#include <boost/lexical_cast.hpp>
+
namespace nsl {
-Node::Node(uint64_t sequenceNumber, uint64_t level, time_t timestamp)
+ndn::ConstBufferPtr Node::EMPTY_HASH;
+
+Node::Index::Index(const NonNegativeInteger& nodeSeq, size_t nodeLevel)
+ : seqNo(nodeSeq)
+ , level(nodeLevel)
+ , range(1 << nodeLevel)
{
- m_index.number = sequenceNumber;
- m_index.level = level;
- m_timeStamp = timestamp;
+ if (seqNo % range != 0)
+ throw Error("Index: index level and seqNo do not match: (" +
+ boost::lexical_cast<std::string>(seqNo) + ", " +
+ boost::lexical_cast<std::string>(level) + ")");
}
-
-const Index&
-Node::getIndex() const
+bool
+Node::Index::operator<(const Index& other) const
{
- return m_index;
+ if (seqNo < other.seqNo) {
+ return true;
+ }
+ else if (seqNo == other.seqNo) {
+ return level < other.level;
+ }
+ else {
+ return false;
+ }
}
-
-
-time_t
-Node::getTimestamp() const
+bool
+Node::Index::operator==(const Index& other) const
{
- return m_timeStamp;
+ return equals(other);
}
+bool
+Node::Index::operator!=(const Index& other) const
+{
+ return !equals(other);
+}
+bool
+Node::Index::equals(const Index& other) const
+{
+ if (seqNo == other.seqNo && level == other.level) {
+ return true;
+ }
+ else {
+ return false;
+ }
+}
+
+Node::Node(const NonNegativeInteger& nodeSeqNo,
+ size_t nodeLevel,
+ const NonNegativeInteger& leafSeqNo,
+ ndn::ConstBufferPtr hash)
+ : m_index(nodeSeqNo, nodeLevel)
+ , m_hash(hash)
+{
+ if (leafSeqNo == 0 && m_index.seqNo > leafSeqNo)
+ m_leafSeqNo = m_index.seqNo;
+ else
+ setLeafSeqNo(leafSeqNo);
+}
void
-Node::setHash(ndn::ConstBufferPtr digest)
+Node::setLeafSeqNo(const NonNegativeInteger& leafSeqNo)
{
- m_hash = digest;
+ if (leafSeqNo > m_index.seqNo + m_index.range || leafSeqNo < m_index.seqNo)
+ throw Error("Node: leaf seqNo is out of range");
+
+ m_leafSeqNo = leafSeqNo;
}
+void
+Node::setHash(ndn::ConstBufferPtr hash)
+{
+ m_hash = hash;
+}
+bool
+Node::isFull() const
+{
+ return m_index.seqNo + m_index.range == m_leafSeqNo;
+}
ndn::ConstBufferPtr
-Node::getHash() const
+Node::getEmptyHash()
{
- return m_hash;
+ if (EMPTY_HASH == nullptr) {
+ ndn::util::Sha256 sha256;
+ EMPTY_HASH = sha256.computeDigest();
+ }
+
+ return EMPTY_HASH;
}
} // namespace nsl
diff --git a/core/node.hpp b/core/node.hpp
index be2ed92..c3d0572 100644
--- a/core/node.hpp
+++ b/core/node.hpp
@@ -16,92 +16,109 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#ifndef NLS_CORE_NODE_HPP
-#define NLS_CORE_NODE_HPP
-#include <stddef.h>
-#include <time.h>
+#ifndef NSL_CORE_NODE_HPP
+#define NSL_CORE_NODE_HPP
-#include <ndn-cxx/util/crypto.hpp>
+#include "common.hpp"
+#include "util/non-negative-integer.hpp"
+#include <ndn-cxx/encoding/buffer.hpp>
namespace nsl {
-class Index
-{
-public:
- Index()
- {
- }
-
- Index(const Index& idx)
- : number(idx.number),
- level(idx.level)
- {
- }
-
- bool operator<(const Index& other) const
- {
- if (number < other.number)
- {
- return true;
- }
- else if (number == other.number)
- {
- return level < other.level;
- }
- else
- {
- return false;
- }
-
- }
-
-public:
- uint64_t number;
- uint64_t level;
-};
-
-
class Node
{
public:
-
- Node()
+ class Error : public std::runtime_error
{
- }
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
-
- Node(uint64_t sequenceNumber, uint64_t level, time_t timestamp);
-
-
- ~Node()
+ class Index
{
- }
+ public:
+ explicit
+ Index(const NonNegativeInteger& seqNo = 0, size_t level = 0);
+ /**
+ * @brief compare two indices
+ *
+ * A index is larger than the other if its seqNo is larger than the other,
+ * or their seqNos are equal but its level is lower.
+ */
+ bool
+ operator<(const Index& other) const;
+
+ bool
+ operator==(const Index& other) const;
+
+ bool
+ operator!=(const Index& other) const;
+
+ bool
+ equals(const Index& other) const;
+
+ public:
+ NonNegativeInteger seqNo;
+ size_t level;
+ NonNegativeInteger range;
+ };
+
+public:
+ Node(const NonNegativeInteger& seqNo,
+ size_t level,
+ const NonNegativeInteger& leafSeqNo = 0,
+ ndn::ConstBufferPtr hash = nullptr);
const Index&
- getIndex() const;
-
-
- time_t
- getTimestamp() const;
-
+ getIndex() const
+ {
+ return m_index;
+ }
void
- setHash(ndn::ConstBufferPtr digest);
+ setLeafSeqNo(const NonNegativeInteger& leafSeqNo);
+ const NonNegativeInteger&
+ getLeafSeqNo() const
+ {
+ return m_leafSeqNo;
+ }
+
+ void
+ setHash(ndn::ConstBufferPtr hash);
ndn::ConstBufferPtr
- getHash() const;
+ getHash() const
+ {
+ return m_hash;
+ }
+
+ bool
+ isFull() const;
+
+ static ndn::ConstBufferPtr
+ getEmptyHash();
+
+protected:
+ Index m_index;
+ NonNegativeInteger m_leafSeqNo;
+ ndn::ConstBufferPtr m_hash;
private:
- ndn::ConstBufferPtr m_hash;
- Index m_index; // Node index.number starts from 0 (the index of current root)
- time_t m_timeStamp;
+ static ndn::ConstBufferPtr EMPTY_HASH;
};
+typedef shared_ptr<Node> NodePtr;
+typedef shared_ptr<const Node> ConstNodePtr;
+
} // namespace nsl
-#endif // NLS_CORE_NODE_HPP
+#endif // NSL_CORE_NODE_HPP
diff --git a/core/sub-tree-binary.cpp b/core/sub-tree-binary.cpp
new file mode 100644
index 0000000..be9c2d3
--- /dev/null
+++ b/core/sub-tree-binary.cpp
@@ -0,0 +1,471 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "sub-tree-binary.hpp"
+
+#include <ndn-cxx/util/digest.hpp>
+#include <ndn-cxx/util/crypto.hpp>
+#include <ndn-cxx/security/digest-sha256.hpp>
+
+namespace nsl {
+
+const time::milliseconds SubTreeBinary::INCOMPLETE_FRESHNESS_PERIOD(60000);
+const std::string SubTreeBinary::COMPONENT_COMPLETE("complete");
+const ssize_t SubTreeBinary::OFFSET_ROOTHASH = -1;
+const ssize_t SubTreeBinary::OFFSET_COMPLETE = -2;
+const ssize_t SubTreeBinary::OFFSET_SEQNO = -3;
+const ssize_t SubTreeBinary::OFFSET_LEVEL = -4;
+const size_t SubTreeBinary::N_LOGGER_SUFFIX = 4;
+const size_t SubTreeBinary::SUB_TREE_DEPTH = 6;
+
+
+SubTreeBinary::SubTreeBinary(const Name& loggerName,
+ const CompleteCallback& completeCallback,
+ const RootUpdateCallback& rootUpdateCallback)
+ : m_loggerName(loggerName)
+ , m_completeCallback(completeCallback)
+ , m_rootUpdateCallback(rootUpdateCallback)
+{
+}
+
+SubTreeBinary::SubTreeBinary(const Name& loggerName,
+ const Node::Index& peakIndex,
+ const CompleteCallback& completeCallback,
+ const RootUpdateCallback& rootUpdateCallback)
+ : m_loggerName(loggerName)
+ , m_completeCallback(completeCallback)
+ , m_rootUpdateCallback(rootUpdateCallback)
+{
+ initialize(peakIndex);
+}
+
+const NonNegativeInteger&
+SubTreeBinary::getNextLeafSeqNo() const
+{
+ if (m_actualRoot != nullptr)
+ return m_actualRoot->getLeafSeqNo();
+
+ return m_peakIndex.seqNo;
+}
+
+ndn::ConstBufferPtr
+SubTreeBinary::getRootHash() const
+{
+ if (m_actualRoot != nullptr)
+ return m_actualRoot->getHash();
+
+ return nullptr;
+}
+
+ConstNodePtr
+SubTreeBinary::getNode(const Node::Index& index) const
+{
+ auto it = m_nodes.find(index);
+ if (it != m_nodes.end()) {
+ return it->second;
+ }
+
+ return nullptr;
+}
+
+bool
+SubTreeBinary::addLeaf(NodePtr leaf)
+{
+ // sanity check: must be a valid leaf
+ if (leaf->getIndex().level != m_leafLevel ||
+ leaf->getIndex().seqNo < m_minSeqNo ||
+ leaf->getIndex().seqNo >= m_maxSeqNo)
+ return false;
+
+ // sanity check: must be the expected next leaf
+ if (leaf->getIndex().seqNo != m_pendingLeafSeqNo ||
+ !m_isPendingLeafEmpty)
+ return false;
+
+ // add the leaf
+ m_nodes[leaf->getIndex()] = leaf;
+
+ // update actual root (guarantee we will have a root)
+ updateActualRoot(leaf);
+
+ // update nodes and their hashes
+ updateParentNode(leaf);
+
+ if (leaf->isFull()) {
+ m_pendingLeafSeqNo = leaf->getIndex().seqNo + leaf->getIndex().range;
+ m_isPendingLeafEmpty = true;
+ }
+ else {
+ m_isPendingLeafEmpty = false;
+ }
+
+ return true;
+}
+
+bool
+SubTreeBinary::updateLeaf(const NonNegativeInteger& nextSeqNo, ndn::ConstBufferPtr hash)
+{
+ // std::cerr << "NextSeqNo: " << nextSeqNo << std::endl;
+ // std::cerr << "minSeqNo: " << m_minSeqNo << std::endl;
+ // std::cerr << "maxSeqNo: " << m_maxSeqNo << std::endl;
+
+ // sanity check
+ if (nextSeqNo < m_minSeqNo || nextSeqNo > m_maxSeqNo)
+ return false;
+
+ // std::cerr << "2" << std::endl;
+ // determine leaf index
+ NonNegativeInteger leafSeqNo = ((nextSeqNo - 1) >> m_leafLevel) << m_leafLevel;
+ if (m_pendingLeafSeqNo != leafSeqNo)
+ return false;
+
+ Node::Index index(leafSeqNo, m_leafLevel);
+ auto leaf = m_nodes[index];
+
+ if (leaf == nullptr) {
+ leaf = make_shared<Node>(leafSeqNo, m_leafLevel, nextSeqNo, hash);
+ m_nodes[index] = leaf;
+ updateActualRoot(leaf);
+ }
+ else {
+ leaf->setLeafSeqNo(nextSeqNo);
+ leaf->setHash(hash);
+ }
+
+ if (nextSeqNo == leafSeqNo + (1 << m_leafLevel)) {
+ m_pendingLeafSeqNo = nextSeqNo;
+ m_isPendingLeafEmpty = true;
+ }
+
+ updateParentNode(leaf);
+
+ return true;
+}
+
+bool
+SubTreeBinary::isFull() const
+{
+ if (m_actualRoot != nullptr &&
+ m_actualRoot->getIndex() == m_peakIndex &&
+ m_actualRoot->isFull())
+ return true;
+
+ return false;
+}
+
+shared_ptr<Data>
+SubTreeBinary::encode() const
+{
+ if (m_actualRoot == nullptr) {
+ auto emptyData = make_shared<Data>();
+ // Name
+ Name emptyName = m_loggerName;
+ emptyName.appendNumber(m_peakIndex.level)
+ .appendNumber(m_peakIndex.seqNo)
+ .appendNumber(m_peakIndex.seqNo)
+ .append(Node::getEmptyHash()->buf(), Node::getEmptyHash()->size());
+ emptyData->setName(emptyName);
+
+ // MetaInfo
+ emptyData->setFreshnessPeriod(time::milliseconds(0));
+
+ // Signature
+ ndn::DigestSha256 sig;
+ emptyData->setSignature(sig);
+
+ Block sigValue(tlv::SignatureValue,
+ ndn::crypto::sha256(emptyData->wireEncode().value(),
+ emptyData->wireEncode().value_size() -
+ emptyData->getSignature().getValue().size()));
+ emptyData->setSignatureValue(sigValue);
+
+ emptyData->wireEncode();
+
+ return emptyData;
+ }
+
+ // Name
+ Name dataName = m_loggerName;
+ dataName.appendNumber(m_actualRoot->getIndex().level)
+ .appendNumber(m_actualRoot->getIndex().seqNo);
+ if (isFull())
+ dataName.append(COMPONENT_COMPLETE.c_str());
+ else
+ dataName.appendNumber(m_actualRoot->getLeafSeqNo());
+ dataName.append(m_actualRoot->getHash()->buf(), m_actualRoot->getHash()->size());
+
+ auto data = make_shared<Data>(dataName);
+
+ // MetaInfo
+ if (!isFull())
+ data->setFreshnessPeriod(INCOMPLETE_FRESHNESS_PERIOD);
+
+ // Content
+ auto buffer = make_shared<ndn::Buffer>();
+ NonNegativeInteger range = 1 << m_leafLevel;
+ for (NonNegativeInteger i = m_minSeqNo; i < m_maxSeqNo; i += range) {
+ auto it = m_nodes.find(Node::Index(i, m_leafLevel));
+ if (it == m_nodes.end())
+ break;
+
+ auto leaf = it->second;
+ if (leaf == nullptr)
+ break;
+ BOOST_ASSERT(leaf->getHash() != nullptr);
+ BOOST_ASSERT(leaf->getHash()->size() == 32);
+ buffer->insert(buffer->end(), leaf->getHash()->begin(), leaf->getHash()->end());
+ }
+ data->setContent(buffer->buf(), buffer->size());
+
+ // Signature
+ ndn::DigestSha256 sig;
+ data->setSignature(sig);
+
+ Block sigValue(tlv::SignatureValue,
+ ndn::crypto::sha256(data->wireEncode().value(),
+ data->wireEncode().value_size() -
+ data->getSignature().getValue().size()));
+ data->setSignatureValue(sigValue);
+
+ data->wireEncode();
+ return data;
+}
+
+void
+SubTreeBinary::decode(const Data& data)
+{
+ bool isComplete = false;
+ NonNegativeInteger nextSeqNo;
+ ndn::ConstBufferPtr rootHash;
+ NonNegativeInteger seqNo;
+ size_t level;
+
+ const Name& dataName = data.getName();
+
+ if (!m_loggerName.isPrefixOf(dataName))
+ throw Error("decode: logger name does not match");
+
+ if (m_loggerName.size() + N_LOGGER_SUFFIX != dataName.size())
+ throw Error("decode: data name does not follow the naming convention");
+
+ try {
+ if (dataName.get(OFFSET_COMPLETE).toUri() == COMPONENT_COMPLETE)
+ isComplete = true;
+ else
+ nextSeqNo = dataName.get(OFFSET_COMPLETE).toNumber();
+
+ rootHash = make_shared<ndn::Buffer>(dataName.get(OFFSET_ROOTHASH).value(),
+ dataName.get(OFFSET_ROOTHASH).value_size());
+
+ seqNo = dataName.get(OFFSET_SEQNO).toNumber();
+ level = dataName.get(OFFSET_LEVEL).toNumber();
+ }
+ catch (tlv::Error&) {
+ throw Error("decode: logger name encoding error");
+ }
+
+ if (seqNo == 0) {
+ size_t peakLevel = 0;
+ if (level % (SUB_TREE_DEPTH - 1) != 0)
+ peakLevel = ((level + SUB_TREE_DEPTH - 1) / (SUB_TREE_DEPTH - 1)) * (SUB_TREE_DEPTH - 1);
+ else
+ peakLevel = level;
+
+ if (nextSeqNo == 1 << peakLevel)
+ peakLevel = peakLevel + SUB_TREE_DEPTH - 1;
+
+ initialize(Node::Index(seqNo, peakLevel));
+ }
+ else
+ initialize(Node::Index(seqNo, level));
+
+ if (isComplete)
+ nextSeqNo = seqNo + (1 << level);
+ else if (nextSeqNo == seqNo) // empty tree
+ return;
+
+ if (rootHash->size() != 32)
+ throw Error("decode: wrong root hash size");
+
+ if (nextSeqNo <= seqNo || nextSeqNo > seqNo + (1 << level))
+ throw Error("decode: wrong current leaf SeqNo");
+
+ int nLeaves = (nextSeqNo - seqNo - 1) / (1 << m_leafLevel) + 1;
+
+ // std::cerr << data.getName() << std::endl;
+ // std::cerr << nextSeqNo << std::endl;
+ // std::cerr << nLeaves * 32 << std::endl;
+ // std::cerr << data.getContent().value_size() << std::endl;
+
+ if (nLeaves * 32 != data.getContent().value_size())
+ throw Error("decode: inconsistent content");
+
+ const uint8_t* offset = data.getContent().value();
+ NonNegativeInteger seqNoInterval = 1 << m_leafLevel;
+ int i = 0;
+ for (; i < nLeaves - 1; i++) {
+ auto node = make_shared<Node>(seqNo + (i * seqNoInterval),
+ m_peakIndex.level + 1 - SUB_TREE_DEPTH,
+ seqNo + (i * seqNoInterval) + seqNoInterval,
+ make_shared<ndn::Buffer>(offset + (i * 32), 32));
+ addLeaf(node);
+ }
+
+ auto node = make_shared<Node>(seqNo + (i * seqNoInterval),
+ m_peakIndex.level + 1 - SUB_TREE_DEPTH,
+ nextSeqNo,
+ make_shared<ndn::Buffer>(offset + (i * 32), 32));
+ addLeaf(node);
+
+ if (*rootHash != *getRoot()->getHash())
+ throw Error("decode: Inconsistent hash");
+}
+
+Node::Index
+SubTreeBinary::toSubTreePeakIndex(const Node::Index& index, bool notRoot)
+{
+ size_t peakLevel =
+ ((index.level + SUB_TREE_DEPTH - 1) / (SUB_TREE_DEPTH - 1)) * (SUB_TREE_DEPTH - 1);
+
+ size_t leafLevel = peakLevel + 1 - SUB_TREE_DEPTH;
+
+ if (index.level % (SUB_TREE_DEPTH - 1) == 0 && index.level > 0 && !notRoot) {
+ peakLevel -= (SUB_TREE_DEPTH - 1);
+ leafLevel -= (SUB_TREE_DEPTH - 1);
+ }
+
+ NonNegativeInteger peakSeqNo = (index.seqNo >> peakLevel) << peakLevel;
+
+ return Node::Index(peakSeqNo, peakLevel);
+}
+
+void
+SubTreeBinary::initialize(const Node::Index& peakIndex)
+{
+ m_peakIndex = peakIndex;
+
+ if (peakIndex.level + 1 < SUB_TREE_DEPTH ||
+ peakIndex.level % (SUB_TREE_DEPTH - 1) != 0)
+ throw Error("SubTreeBinary: peak level does not match the depth");
+
+ m_leafLevel = peakIndex.level + 1 - SUB_TREE_DEPTH;
+
+ m_minSeqNo = peakIndex.seqNo;
+ m_maxSeqNo = peakIndex.seqNo + peakIndex.range;
+
+ m_pendingLeafSeqNo = m_minSeqNo;
+ m_isPendingLeafEmpty = true;
+}
+
+
+
+void
+SubTreeBinary::updateActualRoot(NodePtr node)
+{
+ if (m_actualRoot == nullptr) {
+ // if actual root is not set yet
+ if (node->getIndex().seqNo == 0) { // root sub-tree
+ m_actualRoot = node;
+ m_rootUpdateCallback(node->getIndex(), node->getLeafSeqNo(), node->getHash());
+ return;
+ }
+ else {
+ m_actualRoot = make_shared<Node>(m_peakIndex.seqNo, m_peakIndex.level);
+ m_nodes[m_actualRoot->getIndex()] = m_actualRoot;
+ return;
+ }
+ }
+
+ if (m_actualRoot->getIndex() == m_peakIndex)
+ return;
+
+ if ((node->getIndex().seqNo >> m_actualRoot->getIndex().level) != 0) {
+ // a new actual root at a higher is needed
+ m_actualRoot = make_shared<Node>(m_minSeqNo, m_actualRoot->getIndex().level + 1);
+ m_nodes[m_actualRoot->getIndex()] = m_actualRoot;
+ return;
+ }
+}
+
+void
+SubTreeBinary::updateParentNode(NodePtr node)
+{
+ if (node->getIndex() == m_actualRoot->getIndex()) { // root does not have a parent
+ return;
+ }
+
+ size_t parentLevel = node->getIndex().level + 1;
+ NodePtr parentNode;
+
+ if ((node->getIndex().seqNo >> node->getIndex().level) % 2 == 0) { // left child
+ // parent may not exist
+ Node::Index parentIndex(node->getIndex().seqNo, parentLevel);
+ parentNode = m_nodes[parentIndex];
+
+ ndn::util::Sha256 sha256;
+ sha256 << parentIndex.level << parentIndex.seqNo;
+ sha256.update(node->getHash()->buf(), node->getHash()->size());
+ sha256.update(Node::getEmptyHash()->buf(), Node::getEmptyHash()->size());
+
+ if (parentNode == nullptr) {
+ parentNode = make_shared<Node>(node->getIndex().seqNo,
+ parentLevel,
+ node->getLeafSeqNo(),
+ sha256.computeDigest());
+ }
+ else {
+ parentNode->setHash(sha256.computeDigest());
+ parentNode->setLeafSeqNo(node->getLeafSeqNo());
+ }
+
+ m_nodes[parentNode->getIndex()] = parentNode;
+ }
+ else { // right child
+ // parent must exist
+ NonNegativeInteger parentSeqNo = node->getIndex().seqNo - node->getIndex().range;
+
+ Node::Index parentIndex(parentSeqNo, parentLevel);
+ Node::Index siblingIndex(parentSeqNo, parentLevel - 1);
+
+ parentNode = m_nodes[parentIndex];
+ auto siblingNode = m_nodes[siblingIndex];
+
+ ndn::util::Sha256 sha256;
+ sha256 << parentNode->getIndex().level << parentNode->getIndex().seqNo;
+ sha256.update(siblingNode->getHash()->buf(), siblingNode->getHash()->size());
+ sha256.update(node->getHash()->buf(), node->getHash()->size());
+
+ parentNode->setHash(sha256.computeDigest());
+ parentNode->setLeafSeqNo(node->getLeafSeqNo());
+ }
+
+ if (parentNode->getIndex() == m_actualRoot->getIndex()) { // reach root
+ m_rootUpdateCallback(parentNode->getIndex(),
+ parentNode->getLeafSeqNo(),
+ parentNode->getHash());
+ if (parentNode->getIndex() == m_peakIndex && parentNode->isFull())
+ m_completeCallback(parentNode->getIndex());
+ }
+ else
+ updateParentNode(parentNode);
+}
+
+} // namespace nsl
diff --git a/core/sub-tree-binary.hpp b/core/sub-tree-binary.hpp
new file mode 100644
index 0000000..15a0e3e
--- /dev/null
+++ b/core/sub-tree-binary.hpp
@@ -0,0 +1,182 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_CORE_SUB_TREE_HPP
+#define NSL_CORE_SUB_TREE_HPP
+
+#include "node.hpp"
+
+namespace nsl {
+
+typedef std::function<void(const Node::Index&)> CompleteCallback;
+typedef std::function<void(const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr)> RootUpdateCallback;
+
+class SubTreeBinary
+{
+public:
+ class Error : public std::runtime_error
+ {
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
+
+public:
+ /**
+ * @brief Constructor
+ *
+ * Create an empty subtree.
+ *
+ * @param loggerName The name of logger
+ * @param completeCallback Callback when the subtree is complete
+ * @param rootUpdateCallback Callback when the subtree root is updated
+ */
+ SubTreeBinary(const Name& loggerName,
+ const CompleteCallback& completeCallback,
+ const RootUpdateCallback& rootUpdateCallback);
+ /**
+ * @brief Constructor
+ *
+ * Create a subtree with its first leaf node hash.
+ *
+ * @param loggerName The name of logger
+ * @param rootIndex The index of sub tree root when it is full
+ * @param completeCallback Callback when the subtree is complete
+ * @param rootUpdateCallback Callback when the subtree root is updated
+ */
+ SubTreeBinary(const Name& loggerName,
+ const Node::Index& rootIndex,
+ const CompleteCallback& completeCallback,
+ const RootUpdateCallback& rootUpdateCallback);
+
+ const Node::Index&
+ getPeakIndex() const
+ {
+ return m_peakIndex;
+ }
+
+ const NonNegativeInteger&
+ getMinSeqNo() const
+ {
+ return m_minSeqNo;
+ }
+
+ const NonNegativeInteger&
+ getMaxSeqNo() const
+ {
+ return m_maxSeqNo;
+ }
+
+ size_t
+ getLeafLevel() const
+ {
+ return m_leafLevel;
+ }
+
+ const NonNegativeInteger&
+ getNextLeafSeqNo() const;
+
+ /**
+ * @brief get the root of the subtree
+ *
+ * @return pointer to the root, nullptr if no leaf added
+ */
+ ConstNodePtr
+ getRoot() const
+ {
+ return m_actualRoot;
+ }
+
+ ndn::ConstBufferPtr
+ getRootHash() const;
+
+ ConstNodePtr
+ getNode(const Node::Index& index) const;
+
+ bool
+ addLeaf(NodePtr leaf);
+
+ bool
+ updateLeaf(const NonNegativeInteger& nextSeqNo, ndn::ConstBufferPtr hash);
+
+ bool
+ isFull() const;
+
+ shared_ptr<Data>
+ encode() const;
+
+ void
+ decode(const Data& data);
+
+public:
+ static Node::Index
+ toSubTreePeakIndex(const Node::Index& index, bool notRoot = true);
+
+private:
+ void
+ initialize(const Node::Index& peakIndex);
+
+ void
+ updateActualRoot(NodePtr node);
+
+ void
+ updateParentNode(NodePtr node);
+
+public:
+ static const size_t SUB_TREE_DEPTH;
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ static const time::milliseconds INCOMPLETE_FRESHNESS_PERIOD;
+ static const std::string COMPONENT_COMPLETE;
+ static const ssize_t OFFSET_ROOTHASH;
+ static const ssize_t OFFSET_COMPLETE;
+ static const ssize_t OFFSET_SEQNO;
+ static const ssize_t OFFSET_LEVEL;
+ static const size_t N_LOGGER_SUFFIX;
+
+private:
+ Name m_loggerName;
+ Node::Index m_peakIndex;
+ NonNegativeInteger m_minSeqNo;
+ NonNegativeInteger m_maxSeqNo;
+ size_t m_leafLevel;
+
+ CompleteCallback m_completeCallback;
+ RootUpdateCallback m_rootUpdateCallback;
+
+ NodePtr m_actualRoot;
+ bool m_isPendingLeafEmpty;
+ NonNegativeInteger m_pendingLeafSeqNo;
+
+ std::map<Node::Index, NodePtr> m_nodes;
+};
+
+typedef shared_ptr<SubTreeBinary> SubTreeBinaryPtr;
+typedef shared_ptr<const SubTreeBinary> ConstSubTreeBinaryPtr;
+
+} // namespace nsl
+
+#endif // NSL_CORE_SUB_TREE_HPP
diff --git a/core/sub-tree.cpp b/core/sub-tree.cpp
deleted file mode 100644
index 46f3f5c..0000000
--- a/core/sub-tree.cpp
+++ /dev/null
@@ -1,213 +0,0 @@
-/* -*- 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 "sub-tree.hpp"
-#include "Auditor.hpp"
-#include <math.h>
-
-
-namespace nsl {
-
-void
-SubTree::addNode(ndn::ConstBufferPtr hash_ptr)
-{
- if(m_remainPosition > 0)
- {
- uint8_t seqNo = 127 - m_remainPosition;
- m_nodeHashes[seqNo] = ndn::make_shared<ndn::Buffer>(*hash_ptr);
- m_remainPosition -= 1;
- updateHash();
- }
-}
-
-void
-SubTree::updateHash()
-{
- uint8_t i_ = 6;
- uint8_t lastNo = 126 - m_remainPosition;
- for (; i_ > 0; i_--)
- {
- for (int i = int(pow(2, i_)) - 1; i <= lastNo; i+= 2)
- {
- if ((i + 1) <= lastNo)
- {
- uint8_t up_idx = (i-1) / 2;
- Auditor hasher;
- ndn::ConstBufferPtr buf = hasher.computeHash(m_nodeHashes[i],
- m_nodeHashes[i + 1]);
- m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
- }
- else
- {
- uint8_t up_idx = (i-1) / 2;
- Auditor hasher;
- ndn::ConstBufferPtr buf = hasher.computeHashOneSide(m_nodeHashes[i]);
- m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
- }
- }
- lastNo = (lastNo - 1) / 2;
- }
- m_callBackUpdate(m_remainPosition, m_nodeHashes[0]);
-}
-
-
-
-
-void
-SubTree::updateLeafHash(Index subRootIndex, ndn::ConstBufferPtr hash)
-{
- uint8_t lastNo = 126 - m_remainPosition;
- uint64_t sequenceNo = subRootIndex.number;
- uint64_t level = subRootIndex.level;
- uint8_t indexBase = int(pow(2, m_root.level - level) - 1);
- uint8_t indexOffset = (sequenceNo - m_root.number) / int(pow(2, level));
- m_nodeHashes[indexBase + indexOffset] = ndn::make_shared<ndn::Buffer>(*hash);
- if (lastNo < indexBase + indexOffset) // update value ? add new value
- {
- m_remainPosition -= 1;
- }
- updateHash();
-}
-
-ndn::ConstBufferPtr
-SubTree::getHash(Index nodeIndex)
-{
- uint64_t sequenceNo = nodeIndex.number;
- uint64_t level = nodeIndex.level;
- uint8_t indexBase = int(pow(2, m_root.level - level) - 1);
- uint8_t indexOffset = (sequenceNo - m_root.number) / int(pow(2, level));
- return m_nodeHashes[indexBase + indexOffset];
-}
-
-
-
-
-Index
-SubTree::getRootIndex()
-{
- return m_root;
-}
-
-uint8_t
-SubTree::getRemainPosition()
-{
- return m_remainPosition;
-}
-
-Index
-SubTree::getParentRootIndex()
-{
- Index parentIndex;
- parentIndex.number = m_root.number;
- parentIndex.level = m_root.level;
- for (int i = 0; i < 6; i++)
- {
- parentIndex.number -= parentIndex.number%int(pow(2, parentIndex.level + 1));
- parentIndex.level += 1;
- }
- return parentIndex;
-}
-
-
-
-std::string
-SubTree::encoding()
-{
- std::string subTreeInfo = "";
- uint64_t seq = m_root.number;
- uint64_t lev = m_root.level;
- unsigned char div_seq[8];
- unsigned char div_lev[8];
- for (int i = 0; i < 8; i++)
- {
- div_seq[i] = (seq >> (8*i)) & 0xFF;
- div_lev[i] = (lev >> (8*i)) & 0xFF;
- }
- for (int i = 0; i < 8; i++)
- {
- subTreeInfo += div_seq[i];
- }
- for (int i = 0; i < 8; i++)
- {
- subTreeInfo += div_lev[i];
- }
- subTreeInfo += m_remainPosition;
- for (int i = 0; i < 127; i++)
- {
- for (int j = 0; j < m_nodeHashes[i]->size(); j++)
- {
- subTreeInfo += (*m_nodeHashes[i])[j];
- }
- uint8_t flag = 0;
- for (int j = m_nodeHashes[i]->size(); j < 32; j++)
- {
- subTreeInfo += flag;
- }
- }
- return subTreeInfo;
-}
-
-void
-SubTree::resumeFromString(uint8_t remain, std::vector<ndn::BufferPtr> hashes)
-{
- m_remainPosition = remain;
- if (remain == 0)
- {
- for (int i = 0; i < hashes.size(); i++)
- {
- m_nodeHashes[i] = hashes[i];
- }
- }
- else
- {
- for (int i = 0; i < hashes.size(); i++)
- {
- m_nodeHashes[63 + i] = hashes[i];
- }
- uint8_t i_ = 6;
- uint8_t lastNo = 126 - m_remainPosition;
- for (; i_ > 0; i_--)
- {
- for (int i = int(pow(2, i_)) - 1; i <= lastNo; i+= 2)
- {
- if ((i + 1) <= lastNo)
- {
- uint8_t up_idx = (i-1) / 2;
- Auditor hasher;
- ndn::ConstBufferPtr buf = hasher.computeHash(m_nodeHashes[i],
- m_nodeHashes[i + 1]);
- m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
- }
- else
- {
- uint8_t up_idx = (i-1) / 2;
- Auditor hasher;
- ndn::ConstBufferPtr buf = hasher.computeHashOneSide(m_nodeHashes[i]);
- m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
- }
- }
- lastNo = (lastNo - 1) / 2;
- }
- }
-}
-
-
-} // namespace nsl
diff --git a/core/sub-tree.hpp b/core/sub-tree.hpp
deleted file mode 100644
index 55a0f53..0000000
--- a/core/sub-tree.hpp
+++ /dev/null
@@ -1,105 +0,0 @@
-/* -*- 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>
- */
-#ifndef NLS_CORE_SUB_TREE_CACHE_HPP
-#define NLS_CORE_SUB_TREE_CACHE_HPP
-
-#include <ndn-cxx/encoding/buffer.hpp>
-#include <stdint.h>
-#include <string.h>
-
-#include "node.hpp"
-
-namespace nsl {
-
-typedef ndn::function<void(uint8_t, ndn::ConstBufferPtr)> CallBack;
-
-class SubTree
-{
-public:
- SubTree()
- {
- }
-
- SubTree(Index rootIndex, CallBack callBackFunction)
- : m_root(rootIndex),
- m_remainPosition(64),
- m_callBackUpdate(callBackFunction)
- {
- for (int i = 0; i < 127; i++)
- {
- m_nodeHashes.push_back(ndn::BufferPtr(new ndn::Buffer));
- }
- }
-
- ~SubTree()
- {
- }
-
- void
- addNode(ndn::ConstBufferPtr hash_ptr);
-
- Index
- getRootIndex();
-
- uint8_t
- getRemainPosition();
-
- Index
- getParentRootIndex();
-
- ndn::ConstBufferPtr
- getHash(Index nodeIndex);
-
- // change when subtree's root hash below it changes
- void
- updateLeafHash(Index subRootIndex, ndn::ConstBufferPtr hash);
-
-
- // decode is implemented in MerkleTreeCache class
- std::string
- encoding();
-
- void
- resumeFromString(uint8_t remain, std::vector<ndn::BufferPtr> hashes);
-
-private:
-
- void
- updateHash();
-
-
-private:
-
- //Based on the following sequence number
- // 0
- // 1 2
- // 3 4 5 6
- // 7 8 9 10 11 12 13 14
- std::vector<ndn::BufferPtr> m_nodeHashes;
- Index m_root;
- uint8_t m_remainPosition;
- CallBack m_callBackUpdate;
-};
-
-
-} // namespace nsl
-
-#endif // NLS_CORE_SUB_TREE_CACHE_HPP
diff --git a/core/tlv.hpp b/core/tlv.hpp
index e69de29..6dd7cac 100644
--- a/core/tlv.hpp
+++ b/core/tlv.hpp
@@ -0,0 +1,42 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+
+#ifndef NSL_CORE_TLV_HPP
+#define NSL_CORE_TLV_HPP
+
+namespace nsl {
+namespace tlv {
+
+/**
+ * @brief Type value of leaf related TLVs
+ */
+enum {
+ LoggerLeaf = 128, // 0x80
+ Timestamp = 129, // 0x81
+ DataSeqNo = 130, // 0x82
+ SignerSeqNo = 131 // 0x83
+};
+
+} // namespace tlv
+} // namespace nsl
+
+#endif // NSL_CORE_TLV_HPP
diff --git a/tests/core/test-merkle-tree-sqlite3.cpp b/core/util/non-negative-integer.hpp
similarity index 76%
copy from tests/core/test-merkle-tree-sqlite3.cpp
copy to core/util/non-negative-integer.hpp
index 683fa1d..eecef0f 100644
--- a/tests/core/test-merkle-tree-sqlite3.cpp
+++ b/core/util/non-negative-integer.hpp
@@ -16,23 +16,16 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#include <boost-test.hpp>
-#include <iostream>
-#include "merkle-tree-sqlite3.hpp"
-#include "sub-tree.hpp"
+#ifndef NSL_UTIL_NON_NEGATIVE_INTEGER_HPP
+#define NSL_UTIL_NON_NEGATIVE_INTEGER_HPP
namespace nsl {
-BOOST_AUTO_TEST_SUITE(TestSqlite3)
-
-BOOST_AUTO_TEST_CASE(TestInit)
-{
- MerkleTreeSqlite3 database;
-}
-
-BOOST_AUTO_TEST_SUITE_END()
+typedef uint64_t NonNegativeInteger;
} // namespace nsl
+
+#endif // NSL_UTIL_NON_NEGATIVE_INTEGER_HPP
diff --git a/tests/core/test-merkle-tree-sqlite3.cpp b/core/util/timestamp.hpp
similarity index 76%
rename from tests/core/test-merkle-tree-sqlite3.cpp
rename to core/util/timestamp.hpp
index 683fa1d..a955e1c 100644
--- a/tests/core/test-merkle-tree-sqlite3.cpp
+++ b/core/util/timestamp.hpp
@@ -16,23 +16,16 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#include <boost-test.hpp>
-#include <iostream>
-#include "merkle-tree-sqlite3.hpp"
-#include "sub-tree.hpp"
+#ifndef NSL_UTIL_TIMESTAMP_HPP
+#define NSL_UTIL_TIMESTAMP_HPP
namespace nsl {
-BOOST_AUTO_TEST_SUITE(TestSqlite3)
-
-BOOST_AUTO_TEST_CASE(TestInit)
-{
- MerkleTreeSqlite3 database;
-}
-
-BOOST_AUTO_TEST_SUITE_END()
+typedef uint64_t Timestamp;
} // namespace nsl
+
+#endif // NSL_UTIL_TIMESTAMP_HPP
diff --git a/cryptopp.hpp b/cryptopp.hpp
new file mode 100644
index 0000000..cebf7ac
--- /dev/null
+++ b/cryptopp.hpp
@@ -0,0 +1,45 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_CRYPTOPP_HPP
+#define NSL_CRYPTOPP_HPP
+
+// suppress CryptoPP warnings
+#pragma GCC system_header
+#pragma clang system_header
+
+#include <cryptopp/asn.h>
+#include <cryptopp/base64.h>
+#include <cryptopp/des.h>
+#include <cryptopp/files.h>
+#include <cryptopp/filters.h>
+#include <cryptopp/hex.h>
+#include <cryptopp/modes.h>
+#include <cryptopp/osrng.h>
+#include <cryptopp/pssr.h>
+#include <cryptopp/pwdbased.h>
+#include <cryptopp/rsa.h>
+#include <cryptopp/sha.h>
+#include <cryptopp/eccrypto.h>
+#include <cryptopp/oids.h>
+#include <cryptopp/dsa.h>
+
+#endif // NSL_CRYPTOPP_HPP
diff --git a/tests/core/auditor.t.cpp b/tests/core/auditor.t.cpp
new file mode 100644
index 0000000..51f588b
--- /dev/null
+++ b/tests/core/auditor.t.cpp
@@ -0,0 +1,213 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "auditor.hpp"
+#include "../tree-generator.hpp"
+#include "cryptopp.hpp"
+
+#include <boost/mpl/list.hpp>
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+BOOST_AUTO_TEST_SUITE(TestAuditor)
+
+void
+printHex(const uint8_t* buf, size_t size)
+{
+ using namespace CryptoPP;
+ StringSource ss(buf, size, true, new HexEncoder(new FileSink(std::cerr), false));
+ std::cerr << std::endl;
+}
+
+BOOST_AUTO_TEST_CASE(LoadProofTests)
+{
+ std::vector<shared_ptr<Data>> proofs;
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(32, 5), 64)->encode());
+
+ std::map<Node::Index, ConstSubTreeBinaryPtr> tree1;
+
+ BOOST_CHECK(Auditor::loadProof(tree1, proofs, TreeGenerator::LOGGER_NAME));
+
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(32, 5), 64)->encode());
+ std::map<Node::Index, ConstSubTreeBinaryPtr> tree2;
+ BOOST_CHECK_EQUAL(Auditor::loadProof(tree2, proofs, TreeGenerator::LOGGER_NAME), false);
+}
+
+size_t
+getRootLevel(const NonNegativeInteger& leafSeqNo) {
+ size_t rootLevel = 0;
+ NonNegativeInteger seqNo = leafSeqNo;
+ while (seqNo != 0) {
+ seqNo = seqNo >> 1;
+ rootLevel++;
+ }
+
+ return rootLevel;
+}
+
+template<NonNegativeInteger L, NonNegativeInteger O, NonNegativeInteger N>
+class AuditorProofParam1
+{
+public:
+ void
+ createProof()
+ {
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32, true)->encode());
+
+ leafHash = TreeGenerator::getHash(Node::Index(L, 0), L + 1, false);
+ oldHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(O - 1)), O, false);
+ newHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(N - 1)), N, false);
+ }
+
+ std::vector<shared_ptr<Data>> proofs;
+ const NonNegativeInteger leafSeqNo = L;
+ ndn::ConstBufferPtr leafHash;
+ const NonNegativeInteger oldNextSeqNo = O;
+ ndn::ConstBufferPtr oldHash;
+ const NonNegativeInteger newNextSeqNo = N;
+ ndn::ConstBufferPtr newHash;
+};
+
+template<NonNegativeInteger L, NonNegativeInteger O, NonNegativeInteger N>
+class AuditorProofParam2
+{
+public:
+ void
+ createProof()
+ {
+ // proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32, true)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(32, 5), 64, true)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 10), 64, true)->encode());
+
+ leafHash = TreeGenerator::getHash(Node::Index(L, 0), L + 1, false);
+ oldHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(O - 1)), O, false);
+ newHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(N - 1)), N, false);
+ }
+
+ std::vector<shared_ptr<Data>> proofs;
+ const NonNegativeInteger leafSeqNo = L;
+ ndn::ConstBufferPtr leafHash;
+ const NonNegativeInteger oldNextSeqNo = O;
+ ndn::ConstBufferPtr oldHash;
+ const NonNegativeInteger newNextSeqNo = N;
+ ndn::ConstBufferPtr newHash;
+};
+
+template<NonNegativeInteger L, NonNegativeInteger O, NonNegativeInteger N>
+class AuditorProofParam3
+{
+public:
+ void
+ createProof()
+ {
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32, true)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(32, 5), 33, true)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 10), 33, true)->encode());
+
+ leafHash = TreeGenerator::getHash(Node::Index(L, 0), L + 1, false);
+ oldHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(O - 1)), O, false);
+ newHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(N - 1)), N, false);
+ }
+
+ std::vector<shared_ptr<Data>> proofs;
+ const NonNegativeInteger leafSeqNo = L;
+ ndn::ConstBufferPtr leafHash;
+ const NonNegativeInteger oldNextSeqNo = O;
+ ndn::ConstBufferPtr oldHash;
+ const NonNegativeInteger newNextSeqNo = N;
+ ndn::ConstBufferPtr newHash;
+};
+
+typedef boost::mpl::list<AuditorProofParam1<0, 1, 1>,
+ AuditorProofParam1<0, 2, 2>,
+ AuditorProofParam1<0, 4, 4>,
+ AuditorProofParam1<1, 2, 2>,
+ AuditorProofParam1<1, 4, 4>,
+ AuditorProofParam1<2, 4, 4>,
+ AuditorProofParam1<3, 4, 4>,
+ AuditorProofParam1<4, 6, 6>,
+ AuditorProofParam1<31, 32, 32>,
+ AuditorProofParam3<0, 33, 33>,
+ AuditorProofParam2<32, 33, 33>,
+ AuditorProofParam2<48, 64, 64>> ExistenceProofTestParams;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(ExistenceProof, P, ExistenceProofTestParams)
+{
+ P params;
+ params.createProof();
+
+ BOOST_CHECK(Auditor::doesExist(params.leafSeqNo, params.leafHash,
+ params.newNextSeqNo, params.newHash,
+ params.proofs, TreeGenerator::LOGGER_NAME));
+}
+
+template<NonNegativeInteger L, NonNegativeInteger O, NonNegativeInteger N>
+class AuditorProofParam4
+{
+public:
+ void
+ createProof()
+ {
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32, true)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(32, 5), 64, true)->encode());
+ proofs.push_back(TreeGenerator::getSubTreeBinary(Node::Index(0, 10), 64, true)->encode());
+
+ leafHash = TreeGenerator::getHash(Node::Index(L, 0), L + 1, false);
+ oldHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(O - 1)), O, false);
+ newHash = TreeGenerator::getHash(Node::Index(0, getRootLevel(N - 1)), N, false);
+ }
+
+ std::vector<shared_ptr<Data>> proofs;
+ const NonNegativeInteger leafSeqNo = L;
+ ndn::ConstBufferPtr leafHash;
+ const NonNegativeInteger oldNextSeqNo = O;
+ ndn::ConstBufferPtr oldHash;
+ const NonNegativeInteger newNextSeqNo = N;
+ ndn::ConstBufferPtr newHash;
+};
+
+typedef boost::mpl::list<AuditorProofParam1<0, 1, 1>,
+ AuditorProofParam1<0, 1, 2>,
+ AuditorProofParam1<0, 1, 32>,
+ AuditorProofParam1<0, 2, 32>,
+ AuditorProofParam1<0, 31, 32>,
+ AuditorProofParam4<0, 32, 64>,
+ AuditorProofParam3<0, 1, 33>,
+ AuditorProofParam3<0, 31, 33>,
+ AuditorProofParam4<0, 1, 64>> ConsistencyProofTestParams;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(ConsistencyProof, P, ConsistencyProofTestParams)
+{
+ P params;
+ params.createProof();
+
+ BOOST_CHECK(Auditor::isConsistent(params.oldNextSeqNo, params.oldHash,
+ params.newNextSeqNo, params.newHash,
+ params.proofs, TreeGenerator::LOGGER_NAME));
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/core/test-merkle-tree-sqlite3.cpp b/tests/core/db-fixture.hpp
similarity index 63%
copy from tests/core/test-merkle-tree-sqlite3.cpp
copy to tests/core/db-fixture.hpp
index 683fa1d..5b6db55 100644
--- a/tests/core/test-merkle-tree-sqlite3.cpp
+++ b/tests/core/db-fixture.hpp
@@ -16,23 +16,40 @@
* 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>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
*/
-#include <boost-test.hpp>
-#include <iostream>
-#include "merkle-tree-sqlite3.hpp"
-#include "sub-tree.hpp"
+#ifndef NSL_TESTS_DB_FIXTURE_HPP
+#define NSL_TESTS_DB_FIXTURE_HPP
+
+#include "db.hpp"
+#include <boost/filesystem.hpp>
namespace nsl {
+namespace tests {
-BOOST_AUTO_TEST_SUITE(TestSqlite3)
-
-BOOST_AUTO_TEST_CASE(TestInit)
+class DbFixture
{
- MerkleTreeSqlite3 database;
-}
+public:
+ DbFixture()
+ : m_dbTmpPath(boost::filesystem::path(TEST_DB_PATH) / "DbTest")
+ {
+ db.open(m_dbTmpPath.c_str());
+ }
-BOOST_AUTO_TEST_SUITE_END()
+ ~DbFixture()
+ {
+ boost::filesystem::remove_all(m_dbTmpPath);
+ }
+protected:
+ boost::filesystem::path m_dbTmpPath;
+
+public:
+ Db db;
+};
+
+} // namespace tests
} // namespace nsl
+
+#endif // NSL_TESTS_DB_FIXTURE_HPP
diff --git a/tests/core/db.t.cpp b/tests/core/db.t.cpp
new file mode 100644
index 0000000..84ce74e
--- /dev/null
+++ b/tests/core/db.t.cpp
@@ -0,0 +1,167 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "db.hpp"
+#include "db-fixture.hpp"
+
+#include <ndn-cxx/security/digest-sha256.hpp>
+#include <ndn-cxx/encoding/buffer-stream.hpp>
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TestDb, DbFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+ ndn::DigestSha256 digest;
+ ndn::ConstBufferPtr hash = make_shared<ndn::Buffer>(32);
+ Data data1(Name("/logger/name/5/0/abcdabcdabcdabcdabcd/complete"));
+ data1.setSignature(digest);
+ data1.setSignatureValue(Block(tlv::SignatureValue, hash));
+ Data data2(Name("/logger/name/5/32/abcdabcdabcdabcdabcd/complete"));
+ data2.setSignature(digest);
+ data2.setSignatureValue(Block(tlv::SignatureValue, hash));
+ Data data3(Name("/logger/name/5/32/abcdabcdabcdabcdabcd/33"));
+ data3.setSignature(digest);
+ data3.setSignatureValue(Block(tlv::SignatureValue, hash));
+
+ BOOST_CHECK_EQUAL(db.getPendingSubTrees().size(), 0);
+ BOOST_CHECK(db.getSubTreeData(5, 0) == nullptr);
+ db.insertSubTreeData(5, 0, data1);
+ BOOST_REQUIRE(db.getSubTreeData(5, 0) != nullptr);
+ BOOST_CHECK(db.getSubTreeData(5, 0)->wireEncode() == data1.wireEncode());
+ BOOST_CHECK_EQUAL(db.getPendingSubTrees().size(), 0);
+
+ BOOST_CHECK(db.getSubTreeData(5, 32) == nullptr);
+ db.insertSubTreeData(5, 32, data3, false, 33);
+ BOOST_REQUIRE(db.getSubTreeData(5, 32) != nullptr);
+ BOOST_CHECK(db.getSubTreeData(5, 32)->wireEncode() == data3.wireEncode());
+ BOOST_CHECK_EQUAL(db.getPendingSubTrees().size(), 1);
+
+ db.insertSubTreeData(5, 32, data2);
+ BOOST_REQUIRE(db.getSubTreeData(5, 32) != nullptr);
+ BOOST_CHECK(db.getSubTreeData(5, 32)->wireEncode() == data2.wireEncode());
+ BOOST_CHECK_EQUAL(db.getPendingSubTrees().size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(Basic2)
+{
+ ndn::DigestSha256 digest;
+ ndn::ConstBufferPtr hash = make_shared<ndn::Buffer>(32);
+ Data data1(Name("/logger/name/10/0/abcdabcdabcdabcdabcd/33"));
+ data1.setSignature(digest);
+ data1.setSignatureValue(Block(tlv::SignatureValue, hash));
+ Data data2(Name("/logger/name/5/32/abcdabcdabcdabcdabcd/33"));
+ data2.setSignature(digest);
+ data2.setSignatureValue(Block(tlv::SignatureValue, hash));
+
+ db.insertSubTreeData(5, 32, data2, false, 33);
+ db.insertSubTreeData(10, 0, data1, false, 33);
+ std::vector<shared_ptr<Data>> subtrees = db.getPendingSubTrees();
+
+ BOOST_CHECK_EQUAL(subtrees.size(), 2);
+ BOOST_CHECK(subtrees[0]->wireEncode() == data1.wireEncode());
+ BOOST_CHECK(subtrees[1]->wireEncode() == data2.wireEncode());
+}
+
+const uint8_t Data1[] = {
+0x06, 0xc5, // NDN Data
+ 0x07, 0x14, // Name
+ 0x08, 0x05,
+ 0x6c, 0x6f, 0x63, 0x61, 0x6c,
+ 0x08, 0x03,
+ 0x6e, 0x64, 0x6e,
+ 0x08, 0x06,
+ 0x70, 0x72, 0x65, 0x66, 0x69, 0x78,
+ 0x14, 0x04, // MetaInfo
+ 0x19, 0x02, // FreshnessPeriod
+ 0x27, 0x10,
+ 0x15, 0x08, // Content
+ 0x53, 0x55, 0x43, 0x43, 0x45, 0x53, 0x53, 0x21,
+ 0x16, 0x1b, // SignatureInfo
+ 0x1b, 0x01, // SignatureType
+ 0x01,
+ 0x1c, 0x16, // KeyLocator
+ 0x07, 0x14, // Name
+ 0x08, 0x04,
+ 0x74, 0x65, 0x73, 0x74,
+ 0x08, 0x03,
+ 0x6b, 0x65, 0x79,
+ 0x08, 0x07,
+ 0x6c, 0x6f, 0x63, 0x61, 0x74, 0x6f, 0x72,
+ 0x17, 0x80, // SignatureValue
+ 0x2f, 0xd6, 0xf1, 0x6e, 0x80, 0x6f, 0x10, 0xbe, 0xb1, 0x6f, 0x3e, 0x31, 0xec,
+ 0xe3, 0xb9, 0xea, 0x83, 0x30, 0x40, 0x03, 0xfc, 0xa0, 0x13, 0xd9, 0xb3, 0xc6,
+ 0x25, 0x16, 0x2d, 0xa6, 0x58, 0x41, 0x69, 0x62, 0x56, 0xd8, 0xb3, 0x6a, 0x38,
+ 0x76, 0x56, 0xea, 0x61, 0xb2, 0x32, 0x70, 0x1c, 0xb6, 0x4d, 0x10, 0x1d, 0xdc,
+ 0x92, 0x8e, 0x52, 0xa5, 0x8a, 0x1d, 0xd9, 0x96, 0x5e, 0xc0, 0x62, 0x0b, 0xcf,
+ 0x3a, 0x9d, 0x7f, 0xca, 0xbe, 0xa1, 0x41, 0x71, 0x85, 0x7a, 0x8b, 0x5d, 0xa9,
+ 0x64, 0xd6, 0x66, 0xb4, 0xe9, 0x8d, 0x0c, 0x28, 0x43, 0xee, 0xa6, 0x64, 0xe8,
+ 0x55, 0xf6, 0x1c, 0x19, 0x0b, 0xef, 0x99, 0x25, 0x1e, 0xdc, 0x78, 0xb3, 0xa7,
+ 0xaa, 0x0d, 0x14, 0x58, 0x30, 0xe5, 0x37, 0x6a, 0x6d, 0xdb, 0x56, 0xac, 0xa3,
+ 0xfc, 0x90, 0x7a, 0xb8, 0x66, 0x9c, 0x0e, 0xf6, 0xb7, 0x64, 0xd1
+};
+
+BOOST_AUTO_TEST_CASE(Basic3)
+{
+ Name loggerName("/test/logger");
+ Name dataName("/test/data");
+ Block block(Data1, sizeof(Data1));
+ Data data(block);
+
+ BOOST_CHECK_EQUAL(db.getMaxLeafSeq(), 0);
+
+ Leaf leaf(dataName, 1, 0, 0, loggerName);
+ BOOST_CHECK(db.insertLeafData(leaf, data));
+ BOOST_CHECK_EQUAL(db.getMaxLeafSeq(), 1);
+
+ auto result = db.getLeaf(0);
+ BOOST_CHECK_EQUAL(result.first->getDataName(), dataName);
+ BOOST_CHECK_EQUAL(result.first->getTimestamp(), 1);
+ BOOST_CHECK_EQUAL(result.first->getDataSeqNo(), 0);
+ BOOST_CHECK_EQUAL(result.first->getSignerSeqNo(), 0);
+ BOOST_REQUIRE(result.second != nullptr);
+ BOOST_CHECK_EQUAL(result.second->getName(), data.getName());
+
+ Leaf leaf2(dataName, 2, 1, 0, loggerName);
+ BOOST_CHECK(db.insertLeafData(leaf2));
+ BOOST_CHECK_EQUAL(db.getMaxLeafSeq(), 2);
+
+ result = db.getLeaf(1);
+ BOOST_REQUIRE(result.first != nullptr);
+ BOOST_CHECK_EQUAL(result.first->getDataName(), dataName);
+ BOOST_CHECK_EQUAL(result.first->getTimestamp(), 2);
+ BOOST_CHECK_EQUAL(result.first->getDataSeqNo(), 1);
+ BOOST_CHECK_EQUAL(result.first->getSignerSeqNo(), 0);
+ BOOST_REQUIRE(result.second == nullptr);
+
+ Leaf leaf3(dataName, 2, 5, 0, loggerName);
+ BOOST_CHECK_EQUAL(db.insertLeafData(leaf), false);
+ BOOST_CHECK_EQUAL(db.insertLeafData(leaf2), false);
+ BOOST_CHECK_EQUAL(db.insertLeafData(leaf3), false);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/core/leaf.t.cpp b/tests/core/leaf.t.cpp
new file mode 100644
index 0000000..c55a118
--- /dev/null
+++ b/tests/core/leaf.t.cpp
@@ -0,0 +1,158 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "leaf.hpp"
+#include "cryptopp.hpp"
+
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+BOOST_AUTO_TEST_SUITE(TestLeaf)
+
+void
+printByte(const uint8_t* buf, size_t size)
+{
+ std::stringstream ss;
+ using namespace CryptoPP;
+ StringSource is(buf, size, true, new HexEncoder(new FileSink(ss), false));
+
+ std::string output = ss.str();
+ for (size_t i = 0; i < output.size(); i++) {
+ std::cerr << "0x" << output.at(i);
+ std::cerr << output.at(++i) << ", ";
+ if ((i + 1) % 32 == 0)
+ std::cerr << std::endl;
+ }
+}
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+ Name loggerName("/test/logger");
+ Name dataName("/test/data");
+
+ BOOST_CHECK_NO_THROW(Leaf(dataName, 0, 1, 1, loggerName));
+ BOOST_CHECK_NO_THROW(Leaf(dataName, 0, 2, 1, loggerName));
+ BOOST_CHECK_THROW(Leaf(dataName, 0, 2, 3, loggerName), Leaf::Error);
+
+ Leaf leaf(dataName, 0, 2, 1, loggerName);
+
+ BOOST_CHECK_EQUAL(leaf.getDataName(), dataName);
+ BOOST_CHECK_EQUAL(leaf.getTimestamp(), 0);
+ BOOST_CHECK_EQUAL(leaf.getDataSeqNo(), 2);
+ BOOST_CHECK_EQUAL(leaf.getSignerSeqNo(), 1);
+
+ BOOST_CHECK_THROW(leaf.setDataSeqNo(0), Leaf::Error);
+ BOOST_CHECK_THROW(leaf.setSignerSeqNo(5), Leaf::Error);
+}
+
+uint8_t LEAF_BLOCK[] = {
+ 0x80, 0x17,
+ 0x07, 0x0c,
+ 0x08, 0x04, 0x74, 0x65, 0x73, 0x74,
+ 0x08, 0x04, 0x64, 0x61, 0x74, 0x61,
+ 0x81, 0x01, 0x00,
+ 0x82, 0x01, 0x02,
+ 0x83, 0x01, 0x01
+};
+
+uint8_t LEAF_HASH[] = {
+ 0x79, 0xcb, 0x54, 0xa7, 0x47, 0xa8, 0xea, 0x98, 0x92, 0x39, 0xdb, 0xcf, 0xd0, 0x9a, 0xbb, 0xbd,
+ 0xe3, 0x10, 0x82, 0x3b, 0x4d, 0x46, 0xc4, 0xc1, 0x39, 0x76, 0xbd, 0x3d, 0x17, 0xcc, 0xa9, 0x2b
+};
+
+uint8_t LEAF_DATA[] = {
+ 0x06, 0x79,
+ 0x07, 0x33,
+ 0x08, 0x04, 0x74, 0x65, 0x73, 0x74,
+ 0x08, 0x06, 0x6c, 0x6f, 0x67, 0x67, 0x65, 0x72,
+ 0x08, 0x01, 0x02,
+ 0x08, 0x20,
+ 0x79, 0xcb, 0x54, 0xa7, 0x47, 0xa8, 0xea, 0x98,
+ 0x92, 0x39, 0xdb, 0xcf, 0xd0, 0x9a, 0xbb, 0xbd,
+ 0xe3, 0x10, 0x82, 0x3b, 0x4d, 0x46, 0xc4, 0xc1,
+ 0x39, 0x76, 0xbd, 0x3d, 0x17, 0xcc, 0xa9, 0x2b,
+ 0x14, 0x00,
+ 0x15, 0x19,
+ 0x80, 0x17,
+ 0x07, 0x0c,
+ 0x08, 0x04, 0x74, 0x65, 0x73, 0x74,
+ 0x08, 0x04, 0x64, 0x61, 0x74, 0x61,
+ 0x81, 0x01, 0x00,
+ 0x82, 0x01, 0x02,
+ 0x83, 0x01, 0x01,
+ 0x16, 0x03,
+ 0x1b, 0x01, 0x00,
+ 0x17, 0x20,
+ 0x96, 0x49, 0xe0, 0x62, 0x23, 0x72, 0xd0, 0x90, 0x85, 0x9c, 0x28, 0xda, 0xc8, 0x50, 0x6f, 0x48,
+ 0x56, 0x62, 0x14, 0x8d, 0x75, 0x20, 0x91, 0xa9, 0x0a, 0x46, 0xd6, 0xf8, 0xfc, 0x5d, 0x8e, 0x8e
+};
+
+BOOST_AUTO_TEST_CASE(Encoding)
+{
+ Name loggerName("/test/logger");
+ Name dataName("/test/data");
+
+ Leaf leaf(dataName, 0, 2, 1, loggerName);
+ const Block& block = leaf.wireEncode();
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(block.wire(), block.wire() + block.size(),
+ LEAF_BLOCK, LEAF_BLOCK + sizeof(LEAF_BLOCK));
+
+ ndn::ConstBufferPtr hash = leaf.getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash->begin(), hash->end(),
+ LEAF_HASH, LEAF_HASH + sizeof(LEAF_HASH));
+
+ auto data = leaf.encode();
+ BOOST_CHECK_EQUAL_COLLECTIONS(data->wireEncode().wire(),
+ data->wireEncode().wire() + data->wireEncode().size(),
+ LEAF_DATA,
+ LEAF_DATA + sizeof(LEAF_DATA));
+}
+
+BOOST_AUTO_TEST_CASE(Decoding)
+{
+ Name loggerName("/test/logger");
+ Name dataName("/test/data");
+
+
+ Block block(LEAF_DATA, sizeof(LEAF_DATA));
+ Data data(block);
+
+ Leaf leaf;
+ BOOST_REQUIRE_NO_THROW(leaf.decode(data));
+
+ BOOST_CHECK_EQUAL(leaf.getDataName(), dataName);
+ BOOST_CHECK_EQUAL(leaf.getTimestamp(), 0);
+ BOOST_CHECK_EQUAL(leaf.getDataSeqNo(), 2);
+ BOOST_CHECK_EQUAL(leaf.getSignerSeqNo(), 1);
+
+ ndn::ConstBufferPtr hash = leaf.getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash->begin(), hash->end(),
+ LEAF_HASH, LEAF_HASH + sizeof(LEAF_HASH));
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/core/merkle-tree.t.cpp b/tests/core/merkle-tree.t.cpp
new file mode 100644
index 0000000..278d3d2
--- /dev/null
+++ b/tests/core/merkle-tree.t.cpp
@@ -0,0 +1,249 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "merkle-tree.hpp"
+#include "../tree-generator.hpp"
+#include "db-fixture.hpp"
+
+#include <boost/mpl/list.hpp>
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TestMerkleTree, DbFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+ MerkleTree merkleTree(TreeGenerator::LOGGER_NAME, db);
+ BOOST_CHECK_EQUAL(merkleTree.getNextLeafSeqNo(), 0);
+ BOOST_CHECK(merkleTree.getRootHash() == nullptr);
+}
+
+template<NonNegativeInteger N, size_t L>
+struct MerkleTreeTestParam
+{
+ const NonNegativeInteger leafNo = N;
+ const size_t rootLevel = L;
+};
+
+typedef boost::mpl::list<MerkleTreeTestParam<5, 3>,
+ MerkleTreeTestParam<32, 5>,
+ MerkleTreeTestParam<33, 6>,
+ MerkleTreeTestParam<1024, 10>,
+ MerkleTreeTestParam<1025, 11>> AddLeafTestParams;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(AddLeaf, T, AddLeafTestParams)
+{
+ T param;
+
+ NonNegativeInteger leafNo = param.leafNo;
+ size_t rootLevel = param.rootLevel;
+
+ MerkleTree merkleTree(TreeGenerator::LOGGER_NAME, db);
+ for (NonNegativeInteger i = 0; i < leafNo ; i++) {
+ BOOST_REQUIRE(merkleTree.addLeaf(i, Node::getEmptyHash()));
+ }
+
+ auto hash1 = TreeGenerator::getHash(Node::Index(0, rootLevel), leafNo);
+ auto hash2 = merkleTree.getRootHash();
+
+ BOOST_REQUIRE(hash1 != nullptr);
+ BOOST_REQUIRE(hash2 != nullptr);
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+}
+
+class MerkleTreeLoadTestParam1
+{
+public:
+ void
+ insertData(Db& db)
+ {
+ // partial first sub-tree
+ auto subtree1 = TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 5);
+ db.insertSubTreeData(5, 0, *subtree1->encode(), false, 5);
+ }
+
+ const NonNegativeInteger seqNo = 0;
+ const size_t level = 3;
+ const NonNegativeInteger nextLeafSeqNo = 5;
+};
+
+class MerkleTreeLoadTestParam2
+{
+public:
+ void
+ insertData(Db& db)
+ {
+ // full first sub-tree
+ auto subtree1 = TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32);
+ auto subtree1Data = subtree1->encode();
+ db.insertSubTreeData(5, 0, *subtree1Data);
+
+ auto subtree2 = TreeGenerator::getSubTreeBinary(Node::Index(0, 10), 32);
+ auto subtree2Data = subtree2->encode();
+ db.insertSubTreeData(10, 0, *subtree2Data, false, 32);
+
+ auto subtree3 = make_shared<SubTreeBinary>(TreeGenerator::LOGGER_NAME,
+ Node::Index(32, 5),
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+ auto subtree3Data = subtree3->encode();
+
+ db.insertSubTreeData(5, 32, *subtree3Data, false, 32);
+ }
+
+ const NonNegativeInteger seqNo = 0;
+ const size_t level = 5;
+ const NonNegativeInteger nextLeafSeqNo = 32;
+};
+
+class MerkleTreeLoadTestParam3
+{
+public:
+ void
+ insertData(Db& db)
+ {
+ auto subtree1 = TreeGenerator::getSubTreeBinary(Node::Index(0, 15), 1025);
+ auto subtree1Data = subtree1->encode();
+ db.insertSubTreeData(15, 0, *subtree1Data, false, 1025);
+
+ auto subtree2 = TreeGenerator::getSubTreeBinary(Node::Index(1024, 10), 1025);
+ auto subtree2Data = subtree2->encode();
+ db.insertSubTreeData(10, 1024, *subtree2Data, false, 1025);
+
+ auto subtree3 = TreeGenerator::getSubTreeBinary(Node::Index(1024, 5), 1025);
+ auto subtree3Data = subtree3->encode();
+ db.insertSubTreeData(5, 1024, *subtree3Data, false, 1025);
+ }
+
+ const NonNegativeInteger seqNo = 0;
+ const size_t level = 11;
+ const NonNegativeInteger nextLeafSeqNo = 1025;
+};
+
+
+typedef boost::mpl::list<MerkleTreeLoadTestParam1,
+ MerkleTreeLoadTestParam2,
+ MerkleTreeLoadTestParam3> DbLoadTestParams;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(DbLoad, T, DbLoadTestParams)
+{
+ T param;
+
+ param.insertData(db);
+
+ MerkleTree merkleTree(TreeGenerator::LOGGER_NAME, db);
+
+ auto hash1 = TreeGenerator::getHash(Node::Index(param.seqNo, param.level), param.nextLeafSeqNo);
+ auto hash2 = merkleTree.getRootHash();
+
+ BOOST_REQUIRE(hash1 != nullptr);
+ BOOST_REQUIRE(hash2 != nullptr);
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+}
+
+BOOST_AUTO_TEST_CASE(DbSave1)
+{
+ MerkleTree merkleTree(TreeGenerator::LOGGER_NAME, db);
+ for (NonNegativeInteger i = 0; i < 5 ; i++) {
+ BOOST_REQUIRE(merkleTree.addLeaf(i, Node::getEmptyHash()));
+ }
+
+ merkleTree.savePendingTree();
+ auto data1 = db.getPendingSubTrees()[0];
+ auto data2 = TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 5)->encode();
+
+ BOOST_CHECK(data1->wireEncode() == data2->wireEncode());
+}
+
+BOOST_AUTO_TEST_CASE(DbSave2)
+{
+ MerkleTree merkleTree(TreeGenerator::LOGGER_NAME, db);
+ for (NonNegativeInteger i = 0; i < 32 ; i++) {
+ BOOST_REQUIRE(merkleTree.addLeaf(i, Node::getEmptyHash()));
+ }
+
+ merkleTree.savePendingTree();
+ auto data1 = db.getPendingSubTrees()[0];
+ auto data2 = TreeGenerator::getSubTreeBinary(Node::Index(0, 10), 32)->encode();
+
+ auto data3 = db.getPendingSubTrees()[1];
+ auto subtree = make_shared<SubTreeBinary>(TreeGenerator::LOGGER_NAME,
+ Node::Index(32, 5),
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+ auto data4 = subtree->encode();
+
+ BOOST_CHECK(data1->wireEncode() == data2->wireEncode());
+ BOOST_CHECK(data3->wireEncode() == data4->wireEncode());
+
+ auto dataA = TreeGenerator::getSubTreeBinary(Node::Index(0, 5), 32)->encode();
+ auto dataB = db.getSubTreeData(5, 0);
+
+ BOOST_CHECK(dataA->wireEncode() == dataB->wireEncode());
+}
+
+BOOST_AUTO_TEST_CASE(DbSave3)
+{
+ MerkleTree merkleTree(TreeGenerator::LOGGER_NAME, db);
+ for (NonNegativeInteger i = 0; i < 1025 ; i++) {
+ BOOST_REQUIRE(merkleTree.addLeaf(i, Node::getEmptyHash()));
+ }
+
+ merkleTree.savePendingTree();
+
+ auto data1 = db.getPendingSubTrees()[0];
+ auto data2 = TreeGenerator::getSubTreeBinary(Node::Index(0, 15), 1025)->encode();
+
+ auto data3 = db.getPendingSubTrees()[1];
+ auto data4 = TreeGenerator::getSubTreeBinary(Node::Index(1024, 10), 1025)->encode();
+
+ auto data5 = db.getPendingSubTrees()[2];
+ auto data6 = TreeGenerator::getSubTreeBinary(Node::Index(1024, 5), 1025)->encode();
+
+ BOOST_CHECK(data1->wireEncode() == data2->wireEncode());
+ BOOST_CHECK(data3->wireEncode() == data4->wireEncode());
+ BOOST_CHECK(data5->wireEncode() == data6->wireEncode());
+
+ for (NonNegativeInteger i = 0; i < 1024 ; i += 32) {
+ auto dataA = TreeGenerator::getSubTreeBinary(Node::Index(i, 5), i + 32)->encode();
+ auto dataB = db.getSubTreeData(5, i);
+
+ BOOST_CHECK(dataA->wireEncode() == dataB->wireEncode());
+ }
+
+ auto dataA = TreeGenerator::getSubTreeBinary(Node::Index(0, 10), 1024)->encode();
+ auto dataB = db.getSubTreeData(10, 0);
+
+ BOOST_CHECK(dataA->wireEncode() == dataB->wireEncode());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/core/node.t.cpp b/tests/core/node.t.cpp
new file mode 100644
index 0000000..9437489
--- /dev/null
+++ b/tests/core/node.t.cpp
@@ -0,0 +1,127 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "node.hpp"
+#include "cryptopp.hpp"
+
+#include <ndn-cxx/encoding/buffer-stream.hpp>
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+BOOST_AUTO_TEST_SUITE(TestNode)
+
+BOOST_AUTO_TEST_CASE(IndexTest1)
+{
+ Node::Index idx(0, 0);
+
+ BOOST_CHECK_EQUAL(idx.seqNo, 0);
+ BOOST_CHECK_EQUAL(idx.level, 0);
+ BOOST_CHECK_EQUAL(idx.range, 1);
+
+ Node::Index idx2(0, 1);
+ BOOST_CHECK_EQUAL(idx2.seqNo, 0);
+ BOOST_CHECK_EQUAL(idx2.level, 1);
+ BOOST_CHECK_EQUAL(idx2.range, 2);
+
+ Node::Index idx3(2, 1);
+ BOOST_CHECK_EQUAL(idx3.seqNo, 2);
+ BOOST_CHECK_EQUAL(idx3.level, 1);
+ BOOST_CHECK_EQUAL(idx3.range, 2);
+
+ Node::Index idx4(4, 2);
+ BOOST_CHECK_EQUAL(idx4.seqNo, 4);
+ BOOST_CHECK_EQUAL(idx4.level, 2);
+ BOOST_CHECK_EQUAL(idx4.range, 4);
+
+ BOOST_CHECK_THROW(Node::Index(1, 1), Node::Error);
+ BOOST_CHECK_THROW(Node::Index(2, 2), Node::Error);
+}
+
+BOOST_AUTO_TEST_CASE(IndexTest2)
+{
+ Node::Index idx1(0, 0);
+ Node::Index idx2(0, 1);
+ Node::Index idx3(2, 0);
+ Node::Index idx4(2, 1);
+
+ BOOST_CHECK(idx1 < idx2);
+ BOOST_CHECK(idx1 < idx3);
+ BOOST_CHECK(idx1 < idx4);
+ BOOST_CHECK(idx2 < idx3);
+ BOOST_CHECK(idx2 < idx4);
+ BOOST_CHECK(idx3 < idx4);
+
+ BOOST_CHECK(idx1 == idx1);
+ BOOST_CHECK_EQUAL(idx1 == idx2, false);
+ BOOST_CHECK_EQUAL(idx1 == idx3, false);
+ BOOST_CHECK_EQUAL(idx1 == idx4, false);
+}
+
+BOOST_AUTO_TEST_CASE(NodeTest1)
+{
+ std::string hash("ABCDEFGHIJKLMNOPabcdefghijklmno");
+ auto buffer = make_shared<const ndn::Buffer>(hash.c_str(), hash.size());
+
+ Node node(0, 0);
+ BOOST_CHECK(node.getIndex() == Node::Index(0, 0));
+ BOOST_CHECK(!node.isFull());
+ BOOST_CHECK_EQUAL(node.getLeafSeqNo(), 0);
+ BOOST_CHECK(node.getHash() == nullptr);
+
+ node.setLeafSeqNo(1);
+ BOOST_CHECK(node.isFull());
+ BOOST_CHECK_EQUAL(node.getLeafSeqNo(), 1);
+
+ Node node2(2, 1);
+ BOOST_CHECK(!node2.isFull());
+ BOOST_CHECK_EQUAL(node2.getLeafSeqNo(), 2);
+ BOOST_CHECK(node2.getHash() == nullptr);
+
+ Node node3(2, 1, 4);
+ BOOST_CHECK(node3.isFull());
+ BOOST_CHECK_EQUAL(node3.getLeafSeqNo(), 4);
+ BOOST_CHECK(node3.getHash() == nullptr);
+
+ Node node4(2, 1, 3, buffer);
+ BOOST_CHECK(!node4.isFull());
+ BOOST_CHECK_EQUAL(node4.getLeafSeqNo(), 3);
+ BOOST_CHECK_EQUAL_COLLECTIONS(node4.getHash()->begin(), node4.getHash()->end(),
+ buffer->begin(), buffer->end());
+
+
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string emptyHash("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855");
+ StringSource ss(reinterpret_cast<const uint8_t*>(emptyHash.c_str()), emptyHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(Node::getEmptyHash()->begin(), Node::getEmptyHash()->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/core/sub-tree-binary.t.cpp b/tests/core/sub-tree-binary.t.cpp
new file mode 100644
index 0000000..e110674
--- /dev/null
+++ b/tests/core/sub-tree-binary.t.cpp
@@ -0,0 +1,692 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "sub-tree-binary.hpp"
+
+#include <ndn-cxx/encoding/buffer-stream.hpp>
+#include <ndn-cxx/util/digest.hpp>
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+class SubTreeBinaryTestFixture
+{
+public:
+ NonNegativeInteger nextSeqNo;
+ NonNegativeInteger seqNoCount;
+
+ size_t nCompleteCalls;
+ size_t nUpdateCalls;
+
+ ndn::ConstBufferPtr eventualHash;
+};
+
+BOOST_FIXTURE_TEST_SUITE(TestSubTreeBinary, SubTreeBinaryTestFixture)
+
+ndn::ConstBufferPtr
+getTestHashRoot(const Node::Index& idx)
+{
+ if (idx.level == 0)
+ return Node::getEmptyHash();
+
+ auto hash1 = getTestHashRoot(Node::Index(idx.seqNo, idx.level - 1));
+ auto hash2 = getTestHashRoot(Node::Index(idx.seqNo + (idx.range >> 1), idx.level - 1));
+
+ ndn::util::Sha256 sha256;
+ sha256 << idx.level << idx.seqNo;
+ sha256.update(hash1->buf(), hash1->size());
+ sha256.update(hash2->buf(), hash2->size());
+
+ return sha256.computeDigest();
+}
+
+void
+printHex(const uint8_t* buf, size_t size)
+{
+ using namespace CryptoPP;
+ StringSource ss(buf, size, true, new HexEncoder(new FileSink(std::cerr), false));
+ std::cerr << std::endl;
+}
+
+void
+printByte(const uint8_t* buf, size_t size)
+{
+ std::stringstream ss;
+ using namespace CryptoPP;
+ StringSource is(buf, size, true, new HexEncoder(new FileSink(ss), false));
+
+ std::string output = ss.str();
+ for (size_t i = 0; i < output.size(); i++) {
+ std::cerr << "0x" << output.at(i);
+ std::cerr << output.at(++i) << ", ";
+ if ((i + 1) % 32 == 0)
+ std::cerr << std::endl;
+ }
+}
+
+
+BOOST_AUTO_TEST_CASE(BasicTest1)
+{
+ nextSeqNo = 0;
+ seqNoCount = 0;
+ nCompleteCalls = 0;
+ nUpdateCalls = 0;
+
+ Name loggerName("/logger/name");
+
+ Node::Index idx(0, 5);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index& index) {
+ BOOST_CHECK_EQUAL(this->seqNoCount, idx.range);
+ this->nCompleteCalls++;
+ },
+ [&] (const Node::Index&,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ BOOST_CHECK_EQUAL(this->nextSeqNo, seqNo);
+ this->nUpdateCalls++;
+ this->eventualHash = hash;
+ });
+
+ BOOST_CHECK(subTree.getPeakIndex() == idx);
+ BOOST_CHECK_EQUAL(subTree.getMinSeqNo(), 0);
+ BOOST_CHECK_EQUAL(subTree.getMaxSeqNo(), 32);
+ BOOST_CHECK_EQUAL(subTree.getLeafLevel(), 0);
+ BOOST_CHECK_EQUAL(subTree.getNextLeafSeqNo(), 0);
+
+ for (int i = 0; i < 32; i++) {
+ seqNoCount++;
+ nextSeqNo++;
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ BOOST_CHECK(subTree.addLeaf(node));
+ BOOST_CHECK_EQUAL(subTree.getNextLeafSeqNo(), i + 1);
+ }
+ BOOST_CHECK_EQUAL(subTree.isFull(), true);
+
+ BOOST_CHECK_EQUAL(nCompleteCalls, 1);
+ BOOST_CHECK_EQUAL(nUpdateCalls, 32);
+
+ auto actualHash = subTree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ eventualHash->begin(), eventualHash->end());
+
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string rootHash("989551ef13ce660c1c5ccdda770f4769966a6faf83722c91dfeac597c6fa2782");
+ StringSource ss(reinterpret_cast<const uint8_t*>(rootHash.c_str()), rootHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+
+}
+
+BOOST_AUTO_TEST_CASE(BasicTest2)
+{
+ nextSeqNo = 32;
+ seqNoCount = 0;
+ nCompleteCalls = 0;
+ nUpdateCalls = 0;
+
+ Name loggerName("/logger/name");
+
+ Node::Index idx(32, 5);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index& index) {
+ BOOST_CHECK_EQUAL(this->seqNoCount, idx.range);
+ this->nCompleteCalls++;
+ },
+ [&] (const Node::Index&,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ BOOST_CHECK(this->nextSeqNo >= (1 << (idx.level - 1)));
+ BOOST_CHECK_EQUAL(this->nextSeqNo, seqNo);
+ this->nUpdateCalls++;
+ this->eventualHash = hash;
+ });
+
+ BOOST_CHECK(subTree.getPeakIndex() == idx);
+ BOOST_CHECK_EQUAL(subTree.getMinSeqNo(), 32);
+ BOOST_CHECK_EQUAL(subTree.getMaxSeqNo(), 64);
+ BOOST_CHECK_EQUAL(subTree.getLeafLevel(), 0);
+ BOOST_CHECK_EQUAL(subTree.getNextLeafSeqNo(), 32);
+
+ for (int i = 32; i < 64; i++) {
+ seqNoCount++;
+ nextSeqNo++;
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ BOOST_CHECK(subTree.addLeaf(node));
+ BOOST_CHECK_EQUAL(subTree.getNextLeafSeqNo(), i + 1);
+ }
+ BOOST_CHECK_EQUAL(subTree.isFull(), true);
+
+ BOOST_CHECK_EQUAL(nCompleteCalls, 1);
+ BOOST_CHECK_EQUAL(nUpdateCalls, 32);
+
+ auto actualHash = subTree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ eventualHash->begin(), eventualHash->end());
+
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string rootHash("2657cd81c3acb8eb4489f0a2559d42532644ce737ae494f49f30452f47bcff53");
+ StringSource ss(reinterpret_cast<const uint8_t*>(rootHash.c_str()), rootHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+}
+
+BOOST_AUTO_TEST_CASE(BasicTest3)
+{
+ nextSeqNo = 0;
+ seqNoCount = 0;
+ nCompleteCalls = 0;
+ nUpdateCalls = 0;
+
+ Name loggerName("/logger/name");
+
+ Node::Index idx(0, 10);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index& index) {
+ BOOST_CHECK_EQUAL(this->seqNoCount, 32);
+ this->nCompleteCalls++;
+ },
+ [&] (const Node::Index&,
+ const NonNegativeInteger& seqNo,
+ ndn::ConstBufferPtr hash) {
+ BOOST_CHECK_EQUAL(this->nextSeqNo, seqNo);
+ this->nUpdateCalls++;
+ this->eventualHash = hash;
+ });
+
+ BOOST_CHECK(subTree.getPeakIndex() == idx);
+ BOOST_CHECK_EQUAL(subTree.getMinSeqNo(), 0);
+ BOOST_CHECK_EQUAL(subTree.getMaxSeqNo(), 1024);
+ BOOST_CHECK_EQUAL(subTree.getLeafLevel(), 5);
+ BOOST_CHECK_EQUAL(subTree.getNextLeafSeqNo(), 0);
+
+ for (int i = 0; i < 1024; i += 32) {
+ seqNoCount++;
+ nextSeqNo += 32;
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+ auto node = make_shared<Node>(i, 5, i + 32, getTestHashRoot(Node::Index(i, 5)));
+ BOOST_CHECK(subTree.addLeaf(node));
+ BOOST_CHECK_EQUAL(subTree.getNextLeafSeqNo(), i + 32);
+ }
+ BOOST_CHECK_EQUAL(subTree.isFull(), true);
+
+ BOOST_CHECK_EQUAL(nCompleteCalls, 1);
+ BOOST_CHECK_EQUAL(nUpdateCalls, 32);
+
+ auto actualHash = subTree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ eventualHash->begin(), eventualHash->end());
+
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string rootHash("dc138a319c197bc4ede89902ed9b46e4e17d732b5ace9fa3b8a398db5edb1e36");
+ StringSource ss(reinterpret_cast<const uint8_t*>(rootHash.c_str()), rootHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+}
+
+BOOST_AUTO_TEST_CASE(AddLeaf1)
+{
+ Name loggerName("/logger/name");
+
+ Node::Index idx(0, 10);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ auto node_0_5 = make_shared<Node>(0, 5, 32, getTestHashRoot(Node::Index(0, 5)));
+ auto node_32_5 = make_shared<Node>(32, 5, 64, getTestHashRoot(Node::Index(32, 5)));
+ auto node_64_5 = make_shared<Node>(64, 5, 96, getTestHashRoot(Node::Index(64, 5)));
+
+ Node::Index idx2(32, 5);
+ SubTreeBinary subTree2(loggerName,
+ idx2,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ auto node_32_0 = make_shared<Node>(32, 0, 33, Node::getEmptyHash());
+ auto node_33_0 = make_shared<Node>(33, 0, 34, Node::getEmptyHash());
+ auto node_34_0 = make_shared<Node>(34, 0, 35, Node::getEmptyHash());
+ BOOST_REQUIRE(subTree2.addLeaf(node_32_0));
+ BOOST_REQUIRE(subTree2.getRoot() != nullptr);
+ BOOST_REQUIRE(subTree2.getRoot()->getHash() != nullptr);
+ auto node_32_5_33 = make_shared<Node>(32, 5, 33, subTree2.getRoot()->getHash());
+ BOOST_REQUIRE(subTree2.addLeaf(node_33_0));
+ auto node_32_5_34 = make_shared<Node>(32, 5, 34, subTree2.getRoot()->getHash());
+ BOOST_REQUIRE(subTree2.addLeaf(node_34_0));
+ auto node_32_5_35 = make_shared<Node>(32, 5, 35, subTree2.getRoot()->getHash());
+
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_32_5), false);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_0_5), true);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_32_5_33), true);
+ BOOST_CHECK_EQUAL(subTree.updateLeaf(34, node_32_5_34->getHash()), true);
+ BOOST_CHECK_EQUAL(subTree.updateLeaf(35, node_32_5_35->getHash()), true);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_32_5), false);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_64_5), false);
+ BOOST_CHECK_EQUAL(subTree.updateLeaf(64, node_32_5->getHash()), true);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_64_5), true);
+
+ for (int i = 96; i < 1024; i += 32) {
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+ auto node = make_shared<Node>(i, 5, i + 32, getTestHashRoot(Node::Index(i, 5)));
+ BOOST_CHECK(subTree.addLeaf(node));
+ }
+ BOOST_CHECK_EQUAL(subTree.isFull(), true);
+
+ auto actualHash = subTree.getRoot()->getHash();
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string rootHash("dc138a319c197bc4ede89902ed9b46e4e17d732b5ace9fa3b8a398db5edb1e36");
+ StringSource ss(reinterpret_cast<const uint8_t*>(rootHash.c_str()), rootHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+}
+
+
+uint8_t SUBTREE_DATA[] = {
+ 0x06, 0xfd, 0x04, 0x6f, // Data
+ 0x07, 0x40, // Name /logger/name/5/0/complete/....
+ 0x08, 0x06, 0x6c, 0x6f, 0x67, 0x67, 0x65, 0x72,
+ 0x08, 0x04, 0x6e, 0x61, 0x6d, 0x65,
+ 0x08, 0x01, 0x05,
+ 0x08, 0x01, 0x00,
+ 0x08, 0x08, 0x63, 0x6f, 0x6d, 0x70, 0x6c, 0x65, 0x74, 0x65,
+ 0x08, 0x20,
+ 0x98, 0x95, 0x51, 0xef, 0x13, 0xce, 0x66, 0x0c,
+ 0x1c, 0x5c, 0xcd, 0xda, 0x77, 0x0f, 0x47, 0x69,
+ 0x96, 0x6a, 0x6f, 0xaf, 0x83, 0x72, 0x2c, 0x91,
+ 0xdf, 0xea, 0xc5, 0x97, 0xc6, 0xfa, 0x27, 0x82,
+ 0x14, 0x00, // MetaInfo
+ 0x15, 0xfd, 0x04, 0x00, // Content
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0x16, 0x03, 0x1b, 0x01, 0x00, // SigInfo
+ 0x17, 0x20, // SigValue
+ 0x2d, 0xda, 0xd1, 0xd3, 0x25, 0xd1, 0x7d, 0xf5, 0x64, 0xab, 0x58, 0x74, 0x3a, 0x01, 0xb9, 0x31,
+ 0x52, 0xcd, 0x55, 0xd2, 0xce, 0xea, 0xbc, 0x7c, 0x1a, 0x61, 0xe4, 0x7e, 0xff, 0x4a, 0x1f, 0xe7
+};
+
+BOOST_AUTO_TEST_CASE(Encoding1)
+{
+ Name loggerName("/logger/name");
+
+ Node::Index idx(0, 5);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ for (int i = 0; i < 32; i++) {
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ subTree.addLeaf(node);
+ }
+
+ shared_ptr<Data> data = subTree.encode();
+ BOOST_REQUIRE(data != nullptr);
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(data->wireEncode().wire(),
+ data->wireEncode().wire() + data->wireEncode().size(),
+ SUBTREE_DATA,
+ SUBTREE_DATA + sizeof(SUBTREE_DATA));
+}
+
+BOOST_AUTO_TEST_CASE(Decoding1)
+{
+ Name loggerName("/logger/name");
+ SubTreeBinary subtree(loggerName,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ Block block(SUBTREE_DATA, sizeof(SUBTREE_DATA));
+ Data data(block);
+
+ BOOST_REQUIRE_NO_THROW(subtree.decode(data));
+}
+
+uint8_t SUBTREE_DATA2[] = {
+ 0x06, 0xaa, // Data
+ 0x07, 0x39, // Name /logger/name/6/0/.../35
+ 0x08, 0x06, 0x6c, 0x6f, 0x67, 0x67, 0x65, 0x72,
+ 0x08, 0x04, 0x6e, 0x61, 0x6d, 0x65,
+ 0x08, 0x01, 0x06,
+ 0x08, 0x01, 0x00,
+ 0x08, 0x01, 0x23,
+ 0x08, 0x20,
+ 0x44, 0xb2, 0x25, 0x95, 0x79, 0x99, 0x8c, 0xd7,
+ 0xd9, 0x56, 0xc5, 0x22, 0x32, 0x53, 0xd0, 0x7f,
+ 0xf0, 0x09, 0x12, 0xd2, 0x17, 0x54, 0x81, 0x79,
+ 0xfc, 0xad, 0x40, 0x2f, 0x86, 0x0e, 0xa2, 0xef,
+ 0x14, 0x04, // MetaInfo
+ 0x19, 0x02, 0xea, 0x60, // 60000 ms
+ 0x15, 0x40, // Content
+ 0x98, 0x95, 0x51, 0xef, 0x13, 0xce, 0x66, 0x0c, 0x1c, 0x5c, 0xcd, 0xda, 0x77, 0x0f, 0x47, 0x69,
+ 0x96, 0x6a, 0x6f, 0xaf, 0x83, 0x72, 0x2c, 0x91, 0xdf, 0xea, 0xc5, 0x97, 0xc6, 0xfa, 0x27, 0x82,
+ 0xf8, 0x30, 0x5d, 0x94, 0xfa, 0x23, 0xe2, 0x49, 0x08, 0x73, 0x5a, 0xc2, 0x22, 0x34, 0xa1, 0xfd,
+ 0xc4, 0x46, 0xec, 0x07, 0x7c, 0x6c, 0xa2, 0x7e, 0x51, 0x70, 0x68, 0xa9, 0xbb, 0xc6, 0x56, 0x89,
+ 0x16, 0x03, // SigInfo
+ 0x1b, 0x01, 0x00,
+ 0x17, 0x20, // SigValue
+ 0xad, 0x00, 0xce, 0x0b, 0x31, 0x06, 0x9d, 0xee, 0x90, 0x28, 0x03, 0xbe, 0x3f, 0xcc, 0x0a, 0xd6,
+ 0x1b, 0x3e, 0xf6, 0x26, 0x07, 0x63, 0x9b, 0xdf, 0xb9, 0x5e, 0x82, 0xd4, 0xb0, 0xce, 0xc0, 0x9f
+};
+
+BOOST_AUTO_TEST_CASE(Encoding2)
+{
+ Name loggerName("/logger/name");
+
+ Node::Index idx(0, 10);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ auto node_0_5 = make_shared<Node>(0, 5, 32, getTestHashRoot(Node::Index(0, 5)));
+ auto node_32_5 = make_shared<Node>(32, 5, 64, getTestHashRoot(Node::Index(32, 5)));
+ auto node_64_5 = make_shared<Node>(64, 5, 96, getTestHashRoot(Node::Index(64, 5)));
+
+ Node::Index idx2(32, 5);
+ SubTreeBinary subTree2(loggerName,
+ idx2,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ auto node_32_0 = make_shared<Node>(32, 0, 33, Node::getEmptyHash());
+ auto node_33_0 = make_shared<Node>(33, 0, 34, Node::getEmptyHash());
+ auto node_34_0 = make_shared<Node>(34, 0, 35, Node::getEmptyHash());
+ BOOST_REQUIRE(subTree2.addLeaf(node_32_0));
+ BOOST_REQUIRE(subTree2.getRoot() != nullptr);
+ BOOST_REQUIRE(subTree2.getRoot()->getHash() != nullptr);
+ auto node_32_5_33 = make_shared<Node>(32, 5, 33, subTree2.getRoot()->getHash());
+ BOOST_REQUIRE(subTree2.addLeaf(node_33_0));
+ auto node_32_5_34 = make_shared<Node>(32, 5, 34, subTree2.getRoot()->getHash());
+ BOOST_REQUIRE(subTree2.addLeaf(node_34_0));
+ auto node_32_5_35 = make_shared<Node>(32, 5, 35, subTree2.getRoot()->getHash());
+
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_32_5), false);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_0_5), true);
+ BOOST_CHECK_EQUAL(subTree.addLeaf(node_32_5_33), true);
+ BOOST_CHECK_EQUAL(subTree.updateLeaf(34, node_32_5_34->getHash()), true);
+ BOOST_CHECK_EQUAL(subTree.updateLeaf(35, node_32_5_35->getHash()), true);
+
+ shared_ptr<Data> data = subTree.encode();
+ BOOST_REQUIRE(data != nullptr);
+
+ BOOST_CHECK_EQUAL(data->getName().get(SubTreeBinary::OFFSET_COMPLETE).toNumber(), 35);
+ BOOST_CHECK_EQUAL(data->getFreshnessPeriod(), time::milliseconds(60000));
+ BOOST_CHECK_EQUAL(data->getContent().value_size(), 32 * 2);
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(data->wireEncode().wire(),
+ data->wireEncode().wire() + data->wireEncode().size(),
+ SUBTREE_DATA2,
+ SUBTREE_DATA2 + sizeof(SUBTREE_DATA2));
+}
+
+BOOST_AUTO_TEST_CASE(Decoding2)
+{
+ Name loggerName("/logger/name");
+ SubTreeBinary subTree(loggerName,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ Block block(SUBTREE_DATA2, sizeof(SUBTREE_DATA2));
+ Data data(block);
+
+ BOOST_REQUIRE_NO_THROW(subTree.decode(data));
+
+ auto node_32_5 = make_shared<Node>(32, 5, 64, getTestHashRoot(Node::Index(32, 5)));
+ BOOST_CHECK_EQUAL(subTree.updateLeaf(64, node_32_5->getHash()), true);
+
+ for (int i = 64; i < 1024; i += 32) {
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+ auto node = make_shared<Node>(i, 5, i + 32, getTestHashRoot(Node::Index(i, 5)));
+ BOOST_CHECK(subTree.addLeaf(node));
+ }
+ BOOST_CHECK_EQUAL(subTree.isFull(), true);
+
+ auto actualHash = subTree.getRoot()->getHash();
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string rootHash("dc138a319c197bc4ede89902ed9b46e4e17d732b5ace9fa3b8a398db5edb1e36");
+ StringSource ss(reinterpret_cast<const uint8_t*>(rootHash.c_str()), rootHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+}
+
+uint8_t SUBTREE_DATA3[] = {
+ 0x06, 0x69,
+ 0x07, 0x39,
+ 0x08, 0x06, 0x6c, 0x6f, 0x67, 0x67, 0x65, 0x72,
+ 0x08, 0x04, 0x6e, 0x61, 0x6d, 0x65,
+ 0x08, 0x01, 0x05,
+ 0x08, 0x01, 0x00,
+ 0x08, 0x01, 0x00,
+ 0x08, 0x20,
+ 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14,
+ 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
+ 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c,
+ 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
+ 0x14, 0x03,
+ 0x19, 0x01, 0x00,
+ 0x15, 0x00,
+ 0x16, 0x03,
+ 0x1b, 0x01, 0x00,
+ 0x17, 0x20,
+ 0x42, 0x3d, 0x4b, 0xb2, 0xe8, 0x24, 0xd3, 0xf6, 0xb7, 0x20, 0x69, 0x8f, 0x70, 0xb3, 0x9f, 0xfb,
+ 0xdf, 0x71, 0x05, 0xdd, 0xcf, 0xdc, 0x4d, 0x08, 0xbb, 0x22, 0x2e, 0x89, 0x1a, 0x81, 0xef, 0xce
+};
+
+BOOST_AUTO_TEST_CASE(Encoding3)
+{
+ Name loggerName("/logger/name");
+
+ Node::Index idx(0, 5);
+ SubTreeBinary subTree(loggerName,
+ idx,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ shared_ptr<Data> data = subTree.encode();
+ BOOST_REQUIRE(data != nullptr);
+
+ BOOST_CHECK_EQUAL(data->getName().get(SubTreeBinary::OFFSET_COMPLETE).toNumber(), 0);
+ BOOST_CHECK_EQUAL(data->getFreshnessPeriod(), time::milliseconds(0));
+ BOOST_CHECK_EQUAL(data->getContent().value_size(), 0);
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(data->wireEncode().wire(),
+ data->wireEncode().wire() + data->wireEncode().size(),
+ SUBTREE_DATA3,
+ SUBTREE_DATA3 + sizeof(SUBTREE_DATA3));
+}
+
+BOOST_AUTO_TEST_CASE(Decoding3)
+{
+ Name loggerName("/logger/name");
+ SubTreeBinary subTree(loggerName,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ Block block(SUBTREE_DATA3, sizeof(SUBTREE_DATA3));
+ Data data(block);
+
+ try {
+ subTree.decode(data);
+ }
+ catch (std::runtime_error& e) {
+ std::cerr << e.what() << std::endl;
+ }
+
+ BOOST_REQUIRE_NO_THROW(subTree.decode(data));
+ BOOST_CHECK(subTree.getRoot() == nullptr);
+ BOOST_CHECK(subTree.getPeakIndex() == Node::Index(0, 5));
+ BOOST_CHECK_EQUAL(subTree.getLeafLevel(), 0);
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+
+ for (int i = 0; i < 32; i ++) {
+ BOOST_CHECK_EQUAL(subTree.isFull(), false);
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ BOOST_CHECK(subTree.addLeaf(node));
+ }
+ BOOST_CHECK_EQUAL(subTree.isFull(), true);
+
+ auto actualHash = subTree.getRoot()->getHash();
+ {
+ using namespace CryptoPP;
+
+ ndn::OBufferStream os;
+ std::string rootHash("989551ef13ce660c1c5ccdda770f4769966a6faf83722c91dfeac597c6fa2782");
+ StringSource ss(reinterpret_cast<const uint8_t*>(rootHash.c_str()), rootHash.size(),
+ true, new HexDecoder(new FileSink(os)));
+ BOOST_CHECK_EQUAL_COLLECTIONS(actualHash->begin(), actualHash->end(),
+ os.buf()->begin(), os.buf()->end());
+ }
+}
+
+BOOST_AUTO_TEST_CASE(SubTreePeakIndexConvert)
+{
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(0, 0)) == Node::Index(0, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(0, 1)) == Node::Index(0, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(0, 5), false) == Node::Index(0, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(0, 5)) == Node::Index(0, 10));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(1, 0)) == Node::Index(0, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(2, 1)) == Node::Index(0, 5));
+
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(32, 0)) == Node::Index(32, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(32, 1)) == Node::Index(32, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(32, 5), false) == Node::Index(32, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(32, 5)) == Node::Index(0, 10));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(33, 0)) == Node::Index(32, 5));
+ BOOST_CHECK(SubTreeBinary::toSubTreePeakIndex(Node::Index(34, 1)) == Node::Index(32, 5));
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/core/test-auditor.cpp b/tests/core/test-auditor.cpp
deleted file mode 100644
index 3c7f0a2..0000000
--- a/tests/core/test-auditor.cpp
+++ /dev/null
@@ -1,112 +0,0 @@
-/* -*- 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 <boost-test.hpp>
-#include <iostream>
-
-#include "auditor.hpp"
-#include "merkle-tree.hpp"
-
-namespace nsl {
-
-
-boost::test_tools::predicate_result check_hash(ndn::ConstBufferPtr ptr1, ndn::ConstBufferPtr ptr2)
-{
- bool result = true;
- for (int i = 0; i < ptr1->size(); i++)
- {
- if ((*ptr1)[i] != (*ptr2)[i])
- {
- result = false;
- break;
- }
- }
- return result;
-}
-
-
-BOOST_AUTO_TEST_SUITE(TestAuditor)
-
-
-BOOST_AUTO_TEST_CASE(TestVerify)
-{
-
- std::string str1 = "peizhen";
- std::string str2 = "guo";
- std::string str3 = "is";
- std::string str4 = "building";
- std::string str5 = "this";
- std::string str6 = "logging";
- std::string str7 = "system";
- ndn::Buffer buf1;
- ndn::Buffer buf2;
- ndn::Buffer buf3;
- ndn::Buffer buf4;
- ndn::Buffer buf5;
- ndn::Buffer buf6;
- ndn::Buffer buf7;
- for (int i=0; i < str1.size(); i++)
- buf1.push_back(uint8_t(str1[i]));
- for (int i=0; i < str2.size(); i++)
- buf2.push_back(uint8_t(str2[i]));
- for (int i=0; i < str3.size(); i++)
- buf3.push_back(uint8_t(str3[i]));
- for (int i=0; i < str4.size(); i++)
- buf4.push_back(uint8_t(str4[i]));
- for (int i=0; i < str5.size(); i++)
- buf5.push_back(uint8_t(str5[i]));
- for (int i=0; i < str6.size(); i++)
- buf6.push_back(uint8_t(str6[i]));
- for (int i=0; i < str7.size(); i++)
- buf7.push_back(uint8_t(str7[i]));
- ndn::ConstBufferPtr buf_p1 = boost::make_shared<ndn::Buffer>(buf1);
- ndn::ConstBufferPtr buf_p2 = boost::make_shared<ndn::Buffer>(buf2);
- ndn::ConstBufferPtr buf_p3 = boost::make_shared<ndn::Buffer>(buf3);
- ndn::ConstBufferPtr buf_p4 = boost::make_shared<ndn::Buffer>(buf4);
- ndn::ConstBufferPtr buf_p5 = boost::make_shared<ndn::Buffer>(buf5);
- ndn::ConstBufferPtr buf_p6 = boost::make_shared<ndn::Buffer>(buf6);
- ndn::ConstBufferPtr buf_p7 = boost::make_shared<ndn::Buffer>(buf7);
-
- // Test genProof function
- Auditor validator;
- MerkleTree merkle_tree;
- Index version1, version2;
- merkle_tree.addLeaf(buf_p1);
- merkle_tree.addLeaf(buf_p2);
- merkle_tree.addLeaf(buf_p3);
- merkle_tree.addLeaf(buf_p4);
- version1.number = 0; version1.level = merkle_tree.getLevel() - 1;
- const Index ver1 = version1;
- ndn::ConstBufferPtr rootHash1 = merkle_tree.getNode(ver1)->getHash();
- merkle_tree.addLeaf(buf_p5);
- merkle_tree.addLeaf(buf_p6);
- merkle_tree.addLeaf(buf_p7);
- version2.number = 0; version2.level = merkle_tree.getLevel() - 1;
- const Index ver2 = version2;
- ndn::ConstBufferPtr rootHash2 = merkle_tree.getNode(ver2)->getHash();
-
- std::vector<ConstNodePtr> evidence = merkle_tree.generateProof(3, 6);
- bool isConsistent = validator.verifyConsistency(3, 6, rootHash1, rootHash2, evidence);
- BOOST_CHECK(isConsistent== true);
-}
-
-BOOST_AUTO_TEST_SUITE_END()
-
-} // namespace nsl
diff --git a/tests/core/test-merkle-tree-cache.cpp b/tests/core/test-merkle-tree-cache.cpp
deleted file mode 100644
index 12e534a..0000000
--- a/tests/core/test-merkle-tree-cache.cpp
+++ /dev/null
@@ -1,143 +0,0 @@
-/* -*- 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 <boost-test.hpp>
-#include <iostream>
-
-#include "merkle-tree-cache.hpp"
-#include "Auditor.hpp"
-
-
-namespace nsl {
-
-boost::test_tools::predicate_result check_buffer_cache(ndn::ConstBufferPtr ptr1,
- ndn::ConstBufferPtr ptr2)
-{
- bool result = true;
- for (int i = 0; i < ptr1->size(); i++)
- {
- if ((*ptr1)[i] != (*ptr2)[i])
- {
- result = false;
- break;
- }
- }
- return result;
-}
-
-BOOST_AUTO_TEST_SUITE(TestCache)
-
-BOOST_AUTO_TEST_CASE(TestFunction)
-{
- // Test build
- ndn::Buffer buf[200];
- Index idx[200];
- for (uint8_t i = 0; i < 200; i++)
- {
- buf[i].push_back(i);
- idx[i].number = i;
- idx[i].level = 0;
- }
- MerkleTreeCache treeCache;
- for (int i = 0; i < 200; i++)
- {
- ndn::ConstBufferPtr p_buf = ndn::make_shared<ndn::Buffer>(buf[i]);
- Leaf newleaf(p_buf, idx[i].number, idx[i].level, 0);
- newleaf.computeHash();
- treeCache.addLeaf(newleaf);
- BOOST_CHECK(treeCache.getLeaves() == i + 1);
- }
- BOOST_CHECK(treeCache.getLevel() == 2 && treeCache.getLeaves() == 200);
- // std::cout<<treeCache.m_cachedTree.size()<<' '<<treeCache.m_leavesData.size()<<std::endl;
-
- // Test query
- ndn::ConstBufferPtr data_buf90 = ((Leaf*)(treeCache.queryNode(idx[90]).get()))->getData();
- BOOST_CHECK(int((*data_buf90)[0]) == 90);
- ndn::ConstBufferPtr data_buf10 = ((Leaf*)(treeCache.queryNode(idx[10]).get()))->getData();
- BOOST_CHECK(int((*data_buf10)[0]) == 10);
-
- ndn::ConstBufferPtr hash_buf1 = ((Leaf*)(treeCache.queryNode(idx[0]).get()))->getHash();
- ndn::ConstBufferPtr hash_buf2 = ((Leaf*)(treeCache.queryNode(idx[1]).get()))->getHash();
- ndn::ConstBufferPtr hash_buf3 = ((Leaf*)(treeCache.queryNode(idx[2]).get()))->getHash();
- ndn::ConstBufferPtr hash_buf4 = ((Leaf*)(treeCache.queryNode(idx[3]).get()))->getHash();
- Auditor audit;
- ndn::ConstBufferPtr hash_buf5 = audit.computeHash(hash_buf1, hash_buf2);
- ndn::ConstBufferPtr hash_buf6 = audit.computeHash(hash_buf3, hash_buf4);
- ndn::ConstBufferPtr hash_buf7 = audit.computeHash(hash_buf5, hash_buf6);
- Index idx1;
- idx1.number = 0; idx1.level = 2;
- ndn::ConstBufferPtr hash_buf8 = ((IntermediateNode*)(treeCache.queryNode(idx1).get()))->getHash();
- BOOST_CHECK(check_buffer_cache(hash_buf7, hash_buf8));
- idx1.number = 70; idx1.level = 1;
- ndn::ConstBufferPtr hash_buf70 = ((Leaf*)(treeCache.queryNode(idx[70]).get()))->getHash();
- ndn::ConstBufferPtr hash_buf71 = ((Leaf*)(treeCache.queryNode(idx[71]).get()))->getHash();
- ndn::ConstBufferPtr hash_buf72 = audit.computeHash(hash_buf70, hash_buf71);
- ndn::ConstBufferPtr hash_buf73 = ((IntermediateNode*)
- (treeCache.queryNode(idx1).get()))->getHash();
- BOOST_CHECK(check_buffer_cache(hash_buf72, hash_buf73));
-
- // Test Encoding Decoding
- idx1.number = 0; idx1.level = 12;
- SubTreePtr sub_ptr1 = treeCache.getSubTree(idx1);
- std::string tmp_str = sub_ptr1->encoding();
- SubTreePtr sub_ptr2 = treeCache.decoding(tmp_str);
- BOOST_CHECK(sub_ptr1->getRootIndex().number == sub_ptr2->getRootIndex().number &&
- sub_ptr1->getRootIndex().level == sub_ptr2->getRootIndex().level);
- BOOST_CHECK(sub_ptr1->getRemainPosition() == sub_ptr2->getRemainPosition());
- idx1.number = 0; idx1.level = 10;
- ndn::ConstBufferPtr origin_buf = sub_ptr1->getHash(idx1);
- ndn::ConstBufferPtr resume_buf = sub_ptr2->getHash(idx1);
- BOOST_CHECK(check_buffer_cache(origin_buf, resume_buf));
-
-
- // Test Sqlite3 (move m_database to public to test)
- /*
- idx1.number = 0; idx1.level = 12;
- treeCache.m_database.addSubTree(sub_ptr1);
- std::string str = treeCache.m_database.getSubTree(idx1);
- SubTreePtr sub_ptr_sql = treeCache.decoding(str);
- BOOST_CHECK(sub_ptr1->getRootIndex().number == sub_ptr_sql->getRootIndex().number &&
- sub_ptr1->getRootIndex().level == sub_ptr_sql->getRootIndex().level);
- BOOST_CHECK(sub_ptr1->getRemainPosition() == sub_ptr_sql->getRemainPosition());
- idx1.number = 0; idx1.level = 10;
- origin_buf = sub_ptr1->getHash(idx1);
- resume_buf = sub_ptr_sql->getHash(idx1);
- BOOST_CHECK(check_buffer_cache(origin_buf, resume_buf));
- idx1.number = 0; idx1.level = 12;
- BOOST_CHECK(treeCache.m_database.doesSubTreeExist(idx1) == true);
- idx1.number = 300; idx1.level = 2;
- BOOST_CHECK(treeCache.m_database.doesSubTreeExist(idx1) == false);
-
- uint64_t sequence = 90;
- treeCache.m_database.addLeafInfo(sequence, data_buf90);
- ndn::ConstBufferPtr data_buf_sql = treeCache.m_database.getLeafInfo(sequence);
- BOOST_CHECK(int((*data_buf_sql)[0]) == 90);
- BOOST_CHECK(treeCache.m_database.doesLeafInfoExist(400) == false);
- // insert update
- treeCache.m_database.addLeafInfo(sequence, data_buf10);
- data_buf_sql = treeCache.m_database.getLeafInfo(sequence);
- BOOST_CHECK(int((*data_buf_sql)[0]) == 10);
- */
-}
-
-
-BOOST_AUTO_TEST_SUITE_END()
-
-} // namespace nsl
diff --git a/tests/core/test-merkle-tree.cpp b/tests/core/test-merkle-tree.cpp
deleted file mode 100644
index 2260ccf..0000000
--- a/tests/core/test-merkle-tree.cpp
+++ /dev/null
@@ -1,198 +0,0 @@
-/* -*- 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 <boost-test.hpp>
-#include <iostream>
-
-#include "merkle-tree.hpp"
-
-namespace nsl {
-
-boost::test_tools::predicate_result check_buffer(ndn::ConstBufferPtr ptr1, ndn::ConstBufferPtr ptr2)
-{
- bool result = true;
- for (int i = 0; i < ptr1->size(); i++)
- {
- if ((*ptr1)[i] != (*ptr2)[i])
- {
- result = false;
- break;
- }
- }
- return result;
-}
-
-BOOST_AUTO_TEST_SUITE(TestTree)
-
-
-BOOST_AUTO_TEST_CASE(TestBuild)
-{
- std::string str1 = "peizhen";
- std::string str2 = "guo";
- std::string str3 = "is";
- std::string str4 = "building";
- std::string str5 = "this";
- std::string str6 = "logging";
- std::string str7 = "system";
- ndn::Buffer buf1;
- ndn::Buffer buf2;
- ndn::Buffer buf3;
- ndn::Buffer buf4;
- ndn::Buffer buf5;
- ndn::Buffer buf6;
- ndn::Buffer buf7;
- for (int i=0; i < str1.size(); i++)
- buf1.push_back(uint8_t(str1[i]));
- for (int i=0; i < str2.size(); i++)
- buf2.push_back(uint8_t(str2[i]));
- for (int i=0; i < str3.size(); i++)
- buf3.push_back(uint8_t(str3[i]));
- for (int i=0; i < str4.size(); i++)
- buf4.push_back(uint8_t(str4[i]));
- for (int i=0; i < str5.size(); i++)
- buf5.push_back(uint8_t(str5[i]));
- for (int i=0; i < str6.size(); i++)
- buf6.push_back(uint8_t(str6[i]));
- for (int i=0; i < str7.size(); i++)
- buf7.push_back(uint8_t(str7[i]));
- ndn::ConstBufferPtr buf_p1 = boost::make_shared<ndn::Buffer>(buf1);
- ndn::ConstBufferPtr buf_p2 = boost::make_shared<ndn::Buffer>(buf2);
- ndn::ConstBufferPtr buf_p3 = boost::make_shared<ndn::Buffer>(buf3);
- ndn::ConstBufferPtr buf_p4 = boost::make_shared<ndn::Buffer>(buf4);
- ndn::ConstBufferPtr buf_p5 = boost::make_shared<ndn::Buffer>(buf5);
- ndn::ConstBufferPtr buf_p6 = boost::make_shared<ndn::Buffer>(buf6);
- ndn::ConstBufferPtr buf_p7 = boost::make_shared<ndn::Buffer>(buf7);
-
- //Test add/get function
- MerkleTree merkle_tree;
- merkle_tree.addLeaf(buf_p1);
- Index idx;
- idx.number = 0;
- idx.level = 0;
- ndn::ConstBufferPtr tmp_ptr = ((Leaf*)(merkle_tree.getNode(idx).get()))->getData();
- BOOST_CHECK(merkle_tree.getLeafNum() == 1 && merkle_tree.getLevel() == 1
- && merkle_tree.getLevel() == idx.level + 1);
- BOOST_CHECK(check_buffer(tmp_ptr, buf_p1));
-
- merkle_tree.addLeaf(buf_p2);
- idx.number += 1;
- BOOST_CHECK(check_buffer(((Leaf*)(merkle_tree.getNode(idx).get()))->getData(), buf_p2));
- idx.number = 0;
- idx.level = 1;
- BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == true
- && merkle_tree.getLeafNum() == 2 && merkle_tree.getLevel() == 2
- && merkle_tree.getLevel() == idx.level + 1);
-
-
- merkle_tree.addLeaf(buf_p3);
- idx.number = 2; idx.level = 0;
- BOOST_CHECK(check_buffer(((Leaf*)(merkle_tree.getNode(idx).get()))->getData(), buf_p3));
- idx.level = 1;
- BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == false);
- idx.number = 0;
- BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == true);
- BOOST_CHECK(merkle_tree.getLeafNum() == 3 && merkle_tree.getLevel() == 3);
-
-
- merkle_tree.addLeaf(buf_p4);
- merkle_tree.addLeaf(buf_p5);
- merkle_tree.addLeaf(buf_p6);
- merkle_tree.addLeaf(buf_p7);
- BOOST_CHECK(merkle_tree.getLeafNum() == 7 && merkle_tree.getLevel() == 4);
- idx.level = 2;
- idx.number = 4;
- BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == false);
- idx.level = 1;
- idx.number = 2;
- BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == true);
-}
-
-
-
-BOOST_AUTO_TEST_CASE(TestGenerateProof)
-{
-
- std::string str1 = "peizhen";
- std::string str2 = "guo";
- std::string str3 = "is";
- std::string str4 = "building";
- std::string str5 = "this";
- std::string str6 = "logging";
- std::string str7 = "system";
- ndn::Buffer buf1;
- ndn::Buffer buf2;
- ndn::Buffer buf3;
- ndn::Buffer buf4;
- ndn::Buffer buf5;
- ndn::Buffer buf6;
- ndn::Buffer buf7;
- for (int i=0; i < str1.size(); i++)
- buf1.push_back(uint8_t(str1[i]));
- for (int i=0; i < str2.size(); i++)
- buf2.push_back(uint8_t(str2[i]));
- for (int i=0; i < str3.size(); i++)
- buf3.push_back(uint8_t(str3[i]));
- for (int i=0; i < str4.size(); i++)
- buf4.push_back(uint8_t(str4[i]));
- for (int i=0; i < str5.size(); i++)
- buf5.push_back(uint8_t(str5[i]));
- for (int i=0; i < str6.size(); i++)
- buf6.push_back(uint8_t(str6[i]));
- for (int i=0; i < str7.size(); i++)
- buf7.push_back(uint8_t(str7[i]));
- ndn::ConstBufferPtr buf_p1 = boost::make_shared<ndn::Buffer>(buf1);
- ndn::ConstBufferPtr buf_p2 = boost::make_shared<ndn::Buffer>(buf2);
- ndn::ConstBufferPtr buf_p3 = boost::make_shared<ndn::Buffer>(buf3);
- ndn::ConstBufferPtr buf_p4 = boost::make_shared<ndn::Buffer>(buf4);
- ndn::ConstBufferPtr buf_p5 = boost::make_shared<ndn::Buffer>(buf5);
- ndn::ConstBufferPtr buf_p6 = boost::make_shared<ndn::Buffer>(buf6);
- ndn::ConstBufferPtr buf_p7 = boost::make_shared<ndn::Buffer>(buf7);
-
-
- // Test genProof function
- MerkleTree merkle_tree;
- merkle_tree.addLeaf(buf_p1);
- merkle_tree.addLeaf(buf_p2);
- merkle_tree.addLeaf(buf_p3);
- merkle_tree.addLeaf(buf_p4);
- merkle_tree.addLeaf(buf_p5);
- merkle_tree.addLeaf(buf_p6);
- merkle_tree.addLeaf(buf_p7);
- std::vector<ConstNodePtr> verifyPathPresent = merkle_tree.generateProof(2, 5);
- std::vector<ConstNodePtr> verifyPathPrevious = merkle_tree.generateProof(4, 6);
- Index idx;
- for (int i = 0; i < verifyPathPresent.size(); i++)
- {
- idx = (verifyPathPresent[i])->getIndex();
- std::cout << idx.number << "," << idx.level << std::endl;
- }
- std::cout << std::endl;
- for (int i = 0; i < verifyPathPrevious.size(); i++)
- {
- idx = (verifyPathPrevious[i])->getIndex();
- std::cout << idx.number << "," << idx.level << std::endl;
- }
-}
-
-
-
-BOOST_AUTO_TEST_SUITE_END()
-
-} // namespace nsl
diff --git a/tests/core/test-node.cpp b/tests/core/test-node.cpp
deleted file mode 100644
index 9476d86..0000000
--- a/tests/core/test-node.cpp
+++ /dev/null
@@ -1,79 +0,0 @@
-/* -*- 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 <stdint.h>
-#include <iostream>
-#include <boost-test.hpp>
-
-#include "leaf.hpp"
-#include "intermediate-node.hpp"
-
-namespace nsl {
-
-
-BOOST_AUTO_TEST_SUITE(NodeTest)
-
-
-BOOST_AUTO_TEST_CASE(LeafTest)
-{
- //Test the constructor & getFunc
- Index idx;
- idx.number = 1;
- idx.level = 0;
- ndn::Buffer buffer;
- for (int i = 0; i < 10; i++)
- {
- buffer.push_back(i + 65); // from A to J
- }
- ndn::ConstBufferPtr p_buf = boost::make_shared<const ndn::Buffer>(buffer);
- Leaf leaf_node(p_buf, idx.number, idx.level, 0);
- BOOST_CHECK(leaf_node.getIndex().number == 1);
- BOOST_CHECK(leaf_node.getIndex().level == 0);
- ndn::ConstBufferPtr data = leaf_node.getData();
- for (int i = 0; i < data->size(); i++)
- {
- std::cout<<(*data)[i]<<' ';
- }
- std::cout<<"Data Finished"<<std::endl;
- //Test hash computation
- leaf_node.computeHash();
- ndn::ConstBufferPtr hash = leaf_node.getHash();
- for (int i = 0; i < hash->size(); i++)
- {
- std::cout<<int((*hash)[i])<<' ';
- }
- std::cout<<"Hash Finished"<<std::endl;
-}
-
-BOOST_AUTO_TEST_CASE(IntermediateNodeTest)
-{
- //Test update full condition
- IntermediateNode inter_node(2,1,0);
- inter_node.setIsFull(4);
- BOOST_CHECK(inter_node.isFull() == true);
- inter_node.setIsFull(2);
- BOOST_CHECK(inter_node.isFull() == false);
-}
-
-BOOST_AUTO_TEST_SUITE_END()
-
-
-
-} // namespace nsl
diff --git a/tests/core/tree-generation-fixture.t.cpp b/tests/core/tree-generation-fixture.t.cpp
new file mode 100644
index 0000000..a1a9959
--- /dev/null
+++ b/tests/core/tree-generation-fixture.t.cpp
@@ -0,0 +1,112 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "../tree-generator.hpp"
+
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+BOOST_AUTO_TEST_SUITE(TestTreeGenerator)
+
+BOOST_AUTO_TEST_CASE(HashGeneration)
+{
+ for (size_t n = 5; n <= 8; n++) {
+ auto hash1 = TreeGenerator::getHash(Node::Index(0, 3), n);
+ SubTreeBinary tree(TreeGenerator::LOGGER_NAME, Node::Index(0, 5),
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+ for (size_t i = 0; i < n; i++) {
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ tree.addLeaf(node);
+ }
+ auto hash2 = tree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+ }
+
+ for (size_t n = 33; n <= 64; n++) {
+ auto hash1 = TreeGenerator::getHash(Node::Index(32, 5), n);
+ SubTreeBinary tree(TreeGenerator::LOGGER_NAME, Node::Index(32, 5),
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+ for (size_t i = 32; i < n; i++) {
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ tree.addLeaf(node);
+ }
+ auto hash2 = tree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+ }
+}
+
+BOOST_AUTO_TEST_CASE(TreeGeneration)
+{
+ for (size_t n = 1; n <= 32; n++) {
+ auto hash1 = TreeGenerator::getSubTreeBinary(Node::Index(0, 5), n)->getRoot()->getHash();
+ SubTreeBinary tree(TreeGenerator::LOGGER_NAME, Node::Index(0, 5),
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+ for (size_t i = 0; i < n; i++) {
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ tree.addLeaf(node);
+ }
+ auto hash2 = tree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+ }
+
+ for (size_t n = 33; n <= 64; n++) {
+ auto hash1 = TreeGenerator::getSubTreeBinary(Node::Index(32, 5), n)->getRoot()->getHash();
+ SubTreeBinary tree(TreeGenerator::LOGGER_NAME, Node::Index(32, 5),
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+ for (size_t i = 32; i < n; i++) {
+ auto node = make_shared<Node>(i, 0, i + 1, Node::getEmptyHash());
+ tree.addLeaf(node);
+ }
+ auto hash2 = tree.getRoot()->getHash();
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+ }
+
+ for (size_t n = 513; n <= 1024; n++) {
+ auto hash1 = TreeGenerator::getSubTreeBinary(Node::Index(0, 10), n)->getRoot()->getHash();
+ auto hash2 = TreeGenerator::getHash(Node::Index(0, 10), n);
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+ }
+
+ for (size_t n = 1025; n <= 2048; n++) {
+ auto hash1 = TreeGenerator::getSubTreeBinary(Node::Index(1024, 10), n)->getRoot()->getHash();
+ auto hash2 = TreeGenerator::getHash(Node::Index(1024, 10), n);
+ BOOST_CHECK_EQUAL_COLLECTIONS(hash1->begin(), hash1->end(), hash2->begin(), hash2->end());
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/home-env-fixture.cpp b/tests/home-env-fixture.cpp
new file mode 100644
index 0000000..26a484b
--- /dev/null
+++ b/tests/home-env-fixture.cpp
@@ -0,0 +1,61 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "common.hpp"
+#include <boost/filesystem.hpp>
+
+#include "boost-test.hpp"
+
+namespace nsl {
+namespace tests {
+
+class HomeEnvFixture
+{
+public:
+ HomeEnvFixture()
+ {
+ // initialize KeyChain from test specific HOME: TEST_HOME_PATH
+ if (std::getenv("HOME"))
+ m_HOME = std::getenv("HOME");
+
+ setenv("HOME", "tests/test-home", 1);
+ }
+
+ ~HomeEnvFixture()
+ {
+ boost::filesystem::remove_all(boost::filesystem::path("/tmp/test/nsl"));
+
+ if (!m_HOME.empty())
+ setenv("HOME", m_HOME.c_str(), 1);
+ else
+ unsetenv("HOME");
+ }
+
+private:
+ std::string m_HOME;
+
+ Name m_newIdentity;
+};
+
+BOOST_GLOBAL_FIXTURE(HomeEnvFixture)
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/test-home/.ndn/client.conf b/tests/test-home/.ndn/client.conf
new file mode 100644
index 0000000..c2b84c1
--- /dev/null
+++ b/tests/test-home/.ndn/client.conf
@@ -0,0 +1,2 @@
+pib=pib-sqlite3:/tmp/test/nsl
+tpm=tpm-file:/tmp/test/nsl
\ No newline at end of file
diff --git a/tests/tree-generator.cpp b/tests/tree-generator.cpp
new file mode 100644
index 0000000..462a6a0
--- /dev/null
+++ b/tests/tree-generator.cpp
@@ -0,0 +1,116 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "tree-generator.hpp"
+#include <ndn-cxx/util/digest.hpp>
+
+namespace nsl {
+namespace tests {
+
+const Name TreeGenerator::LOGGER_NAME("/logger/name");
+ndn::ConstBufferPtr TreeGenerator::LEAF_HASH;
+
+ndn::ConstBufferPtr
+TreeGenerator::getHash(const Node::Index& idx,
+ const NonNegativeInteger& nextLeafSeqNo,
+ bool useEmpty)
+{
+ if (idx.level == 0) {
+ if (useEmpty)
+ return Node::getEmptyHash();
+
+ return Node::getEmptyHash();
+ }
+
+ NonNegativeInteger leftChildSeqNo = idx.seqNo;
+ NonNegativeInteger rightChildSeqNo = idx.seqNo + (idx.range >> 1);
+
+ if (idx.seqNo == 0 && nextLeafSeqNo <= rightChildSeqNo) {
+ BOOST_ASSERT(false);
+ }
+
+ ndn::util::Sha256 sha256;
+ sha256 << idx.level << idx.seqNo;
+
+ auto hash1 = getHash(Node::Index(leftChildSeqNo, idx.level - 1),
+ nextLeafSeqNo,
+ useEmpty);
+ sha256.update(hash1->buf(), hash1->size());
+
+ if (nextLeafSeqNo > rightChildSeqNo) {
+ auto hash2 = getHash(Node::Index(rightChildSeqNo, idx.level - 1),
+ nextLeafSeqNo,
+ useEmpty);
+ sha256.update(hash2->buf(), hash2->size());
+ }
+ else {
+ auto hash2 = Node::getEmptyHash();
+ sha256.update(hash2->buf(), hash2->size());
+ }
+ return sha256.computeDigest();
+}
+
+shared_ptr<SubTreeBinary>
+TreeGenerator::getSubTreeBinary(const Node::Index& index,
+ const NonNegativeInteger& nextLeafSeqNo,
+ bool useEmpty)
+{
+ auto subtree = make_shared<SubTreeBinary>(LOGGER_NAME, index,
+ [&] (const Node::Index&) {},
+ [&] (const Node::Index&,
+ const NonNegativeInteger&,
+ ndn::ConstBufferPtr) {});
+
+ size_t leafLevel = index.level + 1 - SubTreeBinary::SUB_TREE_DEPTH;
+ NonNegativeInteger step = 1 << leafLevel;
+
+ for (NonNegativeInteger i = index.seqNo; i < nextLeafSeqNo - step; i += step) {
+ auto node = make_shared<Node>(i, leafLevel, i + step,
+ getHash(Node::Index(i, leafLevel),
+ i + step,
+ useEmpty));
+ subtree->addLeaf(node);
+ }
+
+ NonNegativeInteger childSeqNo = ((nextLeafSeqNo - 1) >> leafLevel) << leafLevel;
+ auto node = make_shared<Node>(childSeqNo, leafLevel, nextLeafSeqNo,
+ getHash(Node::Index(childSeqNo, leafLevel),
+ nextLeafSeqNo,
+ useEmpty));
+ subtree->addLeaf(node);
+
+ return subtree;
+}
+
+ndn::ConstBufferPtr
+TreeGenerator::getLeafHash()
+{
+ if (LEAF_HASH == nullptr) {
+ ndn::util::Sha256 sha256;
+ sha256 << 1;
+ LEAF_HASH = sha256.computeDigest();
+ }
+
+ return LEAF_HASH;
+}
+
+} // namespace tests
+} // namespace nsl
diff --git a/tests/tree-generator.hpp b/tests/tree-generator.hpp
new file mode 100644
index 0000000..3544ac7
--- /dev/null
+++ b/tests/tree-generator.hpp
@@ -0,0 +1,56 @@
+/* -*- 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/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_TESTS_TREE_GENERATOR_HPP
+#define NSL_TESTS_TREE_GENERATOR_HPP
+
+#include "sub-tree-binary.hpp"
+
+namespace nsl {
+namespace tests {
+
+class TreeGenerator
+{
+public:
+ static ndn::ConstBufferPtr
+ getHash(const Node::Index& idx,
+ const NonNegativeInteger& nextLeafSeqNo,
+ bool useEmpty = true);
+
+ static shared_ptr<SubTreeBinary>
+ getSubTreeBinary(const Node::Index& index,
+ const NonNegativeInteger& nextLeafSeqNo,
+ bool useEmpty = true);
+
+ static ndn::ConstBufferPtr
+ getLeafHash();
+
+public:
+ static const Name LOGGER_NAME;
+
+private:
+ static ndn::ConstBufferPtr LEAF_HASH;
+};
+
+} // namespace tests
+} // namespace nsl
+
+#endif // NSL_TESTS_TREE_GENERATOR_HPP
diff --git a/tests/wscript b/tests/wscript
index 0a53f7c..f924b5e 100644
--- a/tests/wscript
+++ b/tests/wscript
@@ -42,14 +42,18 @@
use='core-objects',
headers='../common.hpp boost-test.hpp',
install_path=None,
+ defines=['TEST_HOME_PATH=\"%s/home-tests\"' %(bld.bldnode)],
)
# unit tests
unit_tests = bld.program(
target='../unit-tests',
features='cxx cxxprogram',
- source=bld.path.ant_glob(['core/**/*.cpp', 'daemon/**/*.cpp']),
+ source=bld.path.ant_glob(['core/**/*.t.cpp', 'daemon/**/*.t.cpp']),
use='core-objects daemon-objects unit-tests-base unit-tests-main',
includes='.',
install_path=None,
+ defines=['TEST_DB_PATH=\"%s/db-tests\"' %(bld.bldnode),
+ 'TEST_KEYCHAIN_PATH=\"%s/keychain-tests\"' %(bld.bldnode),
+ 'TEST_LOGGER_PATH=\"%s/logger-tests\"' %(bld.bldnode)],
)
diff --git a/wscript b/wscript
index 31e5c0e..b9601cd 100644
--- a/wscript
+++ b/wscript
@@ -80,7 +80,7 @@
conf.define('DEFAULT_CONFIG_FILE', '%s/ndn/nsl.conf' % conf.env['SYSCONFDIR'])
- conf.write_config_header('config.hpp')
+ conf.write_config_header('config.hpp', define_prefix='NSL_')
def build(bld):
version(bld)