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 12 namespace extensions { 13 14 std::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 = ¤t_nodes; 49 } 50 DCHECK_EQ(1u, current->size()); 51 return (*current)[0]; 52 } 53 54 } // namespace extensions 55
