cpu/utils/hash_tree.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 // Detray test include(s)
0010 #include "detray/test/utils/hash_tree.hpp"
0011
0012 // GTest include(s)
0013 #include <gtest/gtest.h>
0014
0015 namespace {
0016
0017 template <typename hasher_t, typename digest_collection_t>
0018 void test_hash(std::size_t first_child, std::size_t n_prev_level,
0019                digest_collection_t &digests) {
0020   // base case
0021   if (n_prev_level <= 1u) {
0022     return;
0023   }
0024
0025   auto last_child = first_child + n_prev_level;
0026
0027   // Run over previous tree level to build the next level
0028   for (std::size_t i = first_child; i < last_child; i += 2u) {
0029     auto digest = hasher_t{}(digests[i], digests[i + 1u]);
0030     digests.push_back(digest);
0031   }
0032   auto n_level =
0033       static_cast<std::size_t>(0.5f * static_cast<float>(n_prev_level));
0034   // Need dummy leaf node for next level?
0035   if (n_level % 2u != 0u && n_level > 1u) {
0036     digests.push_back(0);
0037     n_level++;
0038   }
0039   // begin next time where we ended this time
0040   test_hash<hasher_t>(last_child, n_level, digests);
0041 }
0042
0043 }  // namespace
0044
0045 // This tests the correctness of the hash tree tool
0046 GTEST_TEST(detray_utils, hash_tree) {
0047   using namespace detray;
0048
0049   dvector<dindex> test_matrix = {1u, 1u, 1u, 1u, 1u, 1u};
0050
0051   auto ht = hash_tree(test_matrix);
0052   using hash_tree_t = decltype(ht);
0053   hash_tree_t::hash_function hasher{};
0054
0055   dvector<hash_tree_t::hash_type> digests{};
0056   // Build up first level
0057   for (auto input : test_matrix) {
0058     digests.push_back(hasher(input));
0059   }
0060   // Build the other levels
0061   test_hash<hash_tree_t::hash_function>(0, digests.size(), digests);
0062
0063   // Check this with graph
0064   EXPECT_EQ(ht.root(), 6);
0065
0066   const auto tree_data = ht.tree();
0067   EXPECT_EQ(digests.size(), tree_data.size());
0068   for (std::size_t n_idx = 0u; n_idx < tree_data.size(); ++n_idx) {
0069     EXPECT_EQ(digests[n_idx], tree_data[n_idx].key());
0070   }
0071 }