extensions/browser/content_hash_tree.cc

   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 = &current_nodes;
  49   }
  50   DCHECK_EQ(1u, current->size());
  51   return (*current)[0];
  52 }
  53
  54 }  // namespace extensions