Add code to compute the root hash for a hash tree

extensions/browser/content_hash_tree.cc

+// 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 block_size) {
+  if (leaf_hashes.empty() || block_size % crypto::kSHA256Length != 0)
+    return std::string();
+
+  int children_per_parent = block_size / crypto::kSHA256Length;
+
+  // 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

[Marijn Kruisselbrink, 2014/05/12 17:53:45]

You could just use a pair of iterators instead of a pointer to the vector + an
index, but both work equally well of course.

[asargent_no_longer_on_chrome, 2014/05/12 21:58:58]

I switched to using an iterator instead of an index, but I think I find it more
understandable to still use a pointer for the current vector. 

+  // |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
+    // |children_per_parent| elements to form the hash of each parent node.
+    size_t i = 0;
+    while (i < current->size()) {
+      scoped_ptr<crypto::SecureHash> hash(
+          crypto::SecureHash::Create(crypto::SecureHash::SHA256));
+      int count = 0;

[Marijn Kruisselbrink, 2014/05/12 17:53:45]

What is count for? You don't seem to ever read its value.

[asargent_no_longer_on_chrome, 2014/05/12 21:58:58]

Good catch - probably left over from some printf-style debugging code or
something. Removed.

+      for (int j = 0; j < children_per_parent && i < current->size(); j++) {
+        hash->Update((*current)[i].data(), (*current)[i].size());
+        i++;
+        count++;
+      }
+      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 = &current_nodes;
+  }
+  DCHECK_EQ(1u, current->size());
+  return (*current)[0];
+}
+
+}  // namespace extensions