diff options
Diffstat (limited to 'chromium/extensions/browser/content_hash_tree.cc')
-rw-r--r-- | chromium/extensions/browser/content_hash_tree.cc | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/chromium/extensions/browser/content_hash_tree.cc b/chromium/extensions/browser/content_hash_tree.cc new file mode 100644 index 00000000000..9831c12e7f8 --- /dev/null +++ b/chromium/extensions/browser/content_hash_tree.cc @@ -0,0 +1,54 @@ +// 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 "base/memory/scoped_ptr.h" +#include "base/stl_util.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. + std::vector<std::string>::const_iterator i = current->begin(); + while (i != current->end()) { + scoped_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)); + std::string* output = &(parent_nodes.back()); + hash->Finish(string_as_array(output), output->size()); + } + current_nodes.swap(parent_nodes); + parent_nodes.clear(); + current = ¤t_nodes; + } + DCHECK_EQ(1u, current->size()); + return (*current)[0]; +} + +} // namespace extensions |