123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 |
- // Copyright 2014 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "extensions/browser/content_hash_tree.h"
- #include <memory>
- #include "base/check_op.h"
- #include "crypto/secure_hash.h"
- #include "crypto/sha2.h"
- namespace extensions {
- std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes,
- int branch_factor) {
- if (leaf_hashes.empty() || branch_factor < 2)
- return std::string();
- // The nodes of the tree we're currently operating on.
- std::vector<std::string> current_nodes;
- // We avoid having to copy all of the input leaf nodes into |current_nodes|
- // by using a pointer. So the first iteration of the loop this points at
- // |leaf_hashes|, but thereafter it points at |current_nodes|.
- const std::vector<std::string>* current = &leaf_hashes;
- // Where we're inserting new hashes computed from the current level.
- std::vector<std::string> parent_nodes;
- while (current->size() > 1) {
- // Iterate over the current level of hashes, computing the hash of up to
- // |branch_factor| elements to form the hash of each parent node.
- auto i = current->cbegin();
- while (i != current->cend()) {
- std::unique_ptr<crypto::SecureHash> hash(
- crypto::SecureHash::Create(crypto::SecureHash::SHA256));
- for (int j = 0; j < branch_factor && i != current->end(); j++) {
- DCHECK_EQ(i->size(), crypto::kSHA256Length);
- hash->Update(i->data(), i->size());
- ++i;
- }
- parent_nodes.push_back(std::string(crypto::kSHA256Length, 0));
- hash->Finish(std::data(parent_nodes.back()), crypto::kSHA256Length);
- }
- current_nodes.swap(parent_nodes);
- parent_nodes.clear();
- current = ¤t_nodes;
- }
- DCHECK_EQ(1u, current->size());
- return (*current)[0];
- }
- } // namespace extensions
|