content_hash_tree.cc 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
  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. #include "extensions/browser/content_hash_tree.h"
  5. #include <memory>
  6. #include "base/check_op.h"
  7. #include "crypto/secure_hash.h"
  8. #include "crypto/sha2.h"
  9. namespace extensions {
  10. std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes,
  11. int branch_factor) {
  12. if (leaf_hashes.empty() || branch_factor < 2)
  13. return std::string();
  14. // The nodes of the tree we're currently operating on.
  15. std::vector<std::string> current_nodes;
  16. // We avoid having to copy all of the input leaf nodes into |current_nodes|
  17. // by using a pointer. So the first iteration of the loop this points at
  18. // |leaf_hashes|, but thereafter it points at |current_nodes|.
  19. const std::vector<std::string>* current = &leaf_hashes;
  20. // Where we're inserting new hashes computed from the current level.
  21. std::vector<std::string> parent_nodes;
  22. while (current->size() > 1) {
  23. // Iterate over the current level of hashes, computing the hash of up to
  24. // |branch_factor| elements to form the hash of each parent node.
  25. auto i = current->cbegin();
  26. while (i != current->cend()) {
  27. std::unique_ptr<crypto::SecureHash> hash(
  28. crypto::SecureHash::Create(crypto::SecureHash::SHA256));
  29. for (int j = 0; j < branch_factor && i != current->end(); j++) {
  30. DCHECK_EQ(i->size(), crypto::kSHA256Length);
  31. hash->Update(i->data(), i->size());
  32. ++i;
  33. }
  34. parent_nodes.push_back(std::string(crypto::kSHA256Length, 0));
  35. hash->Finish(std::data(parent_nodes.back()), crypto::kSHA256Length);
  36. }
  37. current_nodes.swap(parent_nodes);
  38. parent_nodes.clear();
  39. current = &current_nodes;
  40. }
  41. DCHECK_EQ(1u, current->size());
  42. return (*current)[0];
  43. }
  44. } // namespace extensions