1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "extensions/browser/content_hash_tree.h"
6
7#include "base/memory/scoped_ptr.h"
8#include "base/stl_util.h"
9#include "crypto/secure_hash.h"
10#include "crypto/sha2.h"
11
12namespace extensions {
13
14std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes,
15                                int branch_factor) {
16  if (leaf_hashes.empty() || branch_factor < 2)
17    return std::string();
18
19  // The nodes of the tree we're currently operating on.
20  std::vector<std::string> current_nodes;
21
22  // We avoid having to copy all of the input leaf nodes into |current_nodes|
23  // by using a pointer. So the first iteration of the loop this points at
24  // |leaf_hashes|, but thereafter it points at |current_nodes|.
25  const std::vector<std::string>* current = &leaf_hashes;
26
27  // Where we're inserting new hashes computed from the current level.
28  std::vector<std::string> parent_nodes;
29
30  while (current->size() > 1) {
31    // Iterate over the current level of hashes, computing the hash of up to
32    // |branch_factor| elements to form the hash of each parent node.
33    std::vector<std::string>::const_iterator i = current->begin();
34    while (i != current->end()) {
35      scoped_ptr<crypto::SecureHash> hash(
36          crypto::SecureHash::Create(crypto::SecureHash::SHA256));
37      for (int j = 0; j < branch_factor && i != current->end(); j++) {
38        DCHECK_EQ(i->size(), crypto::kSHA256Length);
39        hash->Update(i->data(), i->size());
40        ++i;
41      }
42      parent_nodes.push_back(std::string(crypto::kSHA256Length, 0));
43      std::string* output = &(parent_nodes.back());
44      hash->Finish(string_as_array(output), output->size());
45    }
46    current_nodes.swap(parent_nodes);
47    parent_nodes.clear();
48    current = &current_nodes;
49  }
50  DCHECK_EQ(1u, current->size());
51  return (*current)[0];
52}
53
54}  // namespace extensions
55