Add code to compute the root hash for a hash tree

extensions/browser/content_hash_tree.h

+// 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.
+
+#ifndef EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_
+#define EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_
+
+#include <string>
+#include <vector>
+
+namespace extensions {
+
+// This takes a list of sha256 hashes, considers them to be leaf nodes of a
+// hash tree (aka Merkle tree), and computes the root node of the tree using
+// the given branching factor to hash lower level nodes together. Tree hash
+// implementations differ in how they handle the case where the number of
+// leaves isn't an integral power of the branch factor. This implementation
+// just hashes together however many are left at a given level, even if that is
+// less than the branching factor (instead of, for instance, directly promoting
+// elements). E.g., imagine we use a branch factor of 3 for a vector of 4 leaf
+// nodes [A,B,C,D]. This implemention will compute the root hash G as follows:
+//
+// |      G      |
+// |     / \     |
+// |    E   F    |
+// |   /|\   \   |
+// |  A B C   D  |
+//
+// where E = Hash(A||B||C), F = Hash(D), and G = Hash(E||F)
+//
+// The one exception to this rule is when there is only one node left. This
+// means that the root hash of any vector with just one leaf is the same as
+// that leaf. Ie RootHash([A]) == A, not Hash(A).
+std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes,
+                                int branch_factor);
+
+}  // namespace extensions
+
+#endif  // EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_