blob: 219551d97245004a59e90addad44e3d1295e3f16 [file] [log] [blame] [edit]
// Copyright 2019 The Fuchsia 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 <stddef.h>
#include <stdint.h>
#include <zircon/assert.h>
#include <zircon/errors.h>
#include <zircon/types.h>
#include <memory>
#include <digest/digest.h>
#include <digest/hash-list.h>
#include <digest/merkle-tree.h>
#include <fbl/algorithm.h>
#include <fbl/alloc_checker.h>
namespace digest {
namespace internal {
// MerkleTree
template <typename T, typename VP, class MT, class HL>
zx_status_t MerkleTree<T, VP, MT, HL>::SetDataLength(size_t data_len) {
zx_status_t rc = hash_list_.SetDataLength(data_len);
if (rc != ZX_OK) {
return rc;
}
size_t list_len = hash_list_.GetListLength();
if (list_len == hash_list_.GetDigestSize()) {
return ZX_OK;
}
fbl::AllocChecker ac;
next_.reset(new (&ac) MT());
if (!ac.check()) {
return ZX_ERR_NO_MEMORY;
}
next_->hash_list_.SetNodeId(hash_list_.GetNodeId() + 1);
next_->SetNodeSize(GetNodeSize());
next_->SetUseCompactFormat(use_compact_format_);
size_t next_len = use_compact_format_ ? list_len : fbl::round_up(list_len, GetNodeSize());
return next_->SetDataLength(next_len);
}
template <typename T, typename VP, class MT, class HL>
size_t MerkleTree<T, VP, MT, HL>::GetTreeLength() const {
if (next_.get() == nullptr) {
return 0;
}
size_t list_len = next_->hash_list_.data_len();
return list_len + next_->GetTreeLength();
}
template <typename T, typename VP, class MT, class HL>
zx_status_t MerkleTree<T, VP, MT, HL>::SetTree(VP tree, size_t tree_len, VP root, size_t root_len) {
if (next_ == nullptr) {
return hash_list_.SetList(static_cast<T *>(root), root_len);
}
size_t list_len = next_->hash_list_.data_len();
if (tree_len < list_len) {
return ZX_ERR_BUFFER_TOO_SMALL;
}
T *list = static_cast<T *>(tree);
zx_status_t rc = hash_list_.SetList(list, list_len);
if (rc != ZX_OK) {
return rc;
}
return next_->SetTree(list + list_len, tree_len - list_len, root, root_len);
}
template <typename T, typename VP, class MT, class HL>
void MerkleTree<T, VP, MT, HL>::SetUseCompactFormat(bool use_compact_format) {
use_compact_format_ = use_compact_format;
// The data is only padded to the node size when creating a hash list of a hash list and not
// when creating a hash list of the leaf data.
hash_list_.SetPadDataToNodeSize(use_compact_format_ && hash_list_.GetNodeId());
}
} // namespace internal
// MerkleTreeCreator
// Forward declarations for templates
template zx_status_t internal::MerkleTree<uint8_t, void *, MerkleTreeCreator,
HashListCreator>::SetDataLength(size_t data_len);
template size_t
internal::MerkleTree<uint8_t, void *, MerkleTreeCreator, HashListCreator>::GetTreeLength() const;
template zx_status_t internal::MerkleTree<uint8_t, void *, MerkleTreeCreator,
HashListCreator>::SetTree(void *tree, size_t tree_len,
void *root, size_t root_len);
template void internal::MerkleTree<uint8_t, void *, MerkleTreeCreator,
HashListCreator>::SetUseCompactFormat(bool use_compact_format);
// static
zx_status_t MerkleTreeCreator::Create(const void *data, size_t data_len,
std::unique_ptr<uint8_t[]> *out_tree, size_t *out_tree_len,
Digest *out_root) {
if (out_tree == nullptr || out_tree_len == nullptr || out_root == nullptr) {
return ZX_ERR_INVALID_ARGS;
}
uint8_t root[kSha256Length];
MerkleTreeCreator creator;
zx_status_t rc = creator.SetDataLength(data_len);
if (rc != ZX_OK) {
return rc;
}
size_t tree_len = creator.GetTreeLength();
std::unique_ptr<uint8_t[]> tree(nullptr);
if (tree_len > 0) {
fbl::AllocChecker ac;
tree.reset(new (&ac) uint8_t[tree_len]);
if (!ac.check()) {
return ZX_ERR_NO_MEMORY;
}
}
if ((rc = creator.SetTree(tree.get(), tree_len, root, sizeof(root))) != ZX_OK ||
(rc = creator.Append(data, data_len)) != ZX_OK) {
return rc;
}
*out_tree = std::move(tree);
*out_tree_len = tree_len;
*out_root = root;
return ZX_OK;
}
zx_status_t MerkleTreeCreator::Append(const void *buf, size_t buf_len) {
if (buf_len == 0) {
return ZX_OK;
}
size_t list_off = hash_list_.list_off();
zx_status_t rc = hash_list_.Append(buf, buf_len);
if (rc != ZX_OK) {
return rc;
}
if (next_.get() == nullptr) {
return ZX_OK;
}
auto list = hash_list_.list() + list_off;
auto list_len = hash_list_.list_off() - list_off;
if ((rc = next_->Append(list, list_len)) != ZX_OK) {
return rc;
}
if (hash_list_.data_off() != hash_list_.data_len()) {
return ZX_OK;
}
if (!GetUseCompactFormat()) {
list = hash_list_.list() + hash_list_.list_off();
list_len = hash_list_.list_len() - hash_list_.list_off();
memset(list, 0, list_len);
return next_->Append(list, list_len);
}
return ZX_OK;
}
// MerkleTreeVerifier
// Forward declarations for templates
template zx_status_t internal::MerkleTree<const uint8_t, const void *, MerkleTreeVerifier,
HashListVerifier>::SetDataLength(size_t data_len);
template size_t internal::MerkleTree<const uint8_t, const void *, MerkleTreeVerifier,
HashListVerifier>::GetTreeLength() const;
template zx_status_t
internal::MerkleTree<const uint8_t, const void *, MerkleTreeVerifier, HashListVerifier>::SetTree(
const void *tree, size_t tree_len, const void *root, size_t root_len);
template void internal::MerkleTree<const uint8_t, const void *, MerkleTreeVerifier,
HashListVerifier>::SetUseCompactFormat(bool use_compact_format);
// static
zx_status_t MerkleTreeVerifier::Verify(const void *buf, size_t buf_len, size_t data_off,
size_t data_len, const void *tree, size_t tree_len,
const Digest &root) {
zx_status_t rc;
MerkleTreeVerifier verifier;
if ((rc = verifier.SetDataLength(data_len)) != ZX_OK ||
(rc = verifier.SetTree(tree, tree_len, root.get(), root.len())) != ZX_OK ||
(rc = verifier.Verify(buf, buf_len, data_off)) != ZX_OK) {
return rc;
}
return ZX_OK;
}
zx_status_t MerkleTreeVerifier::Verify(const void *buf, size_t buf_len, size_t data_off) {
zx_status_t rc = hash_list_.Verify(buf, buf_len, data_off);
if (rc != ZX_OK) {
return rc;
}
if (next_.get() == nullptr) {
return ZX_OK;
}
data_off = hash_list_.GetListOffset(data_off);
buf_len = hash_list_.list_off() - data_off;
if ((rc = next_->hash_list_.Align(&data_off, &buf_len)) != ZX_OK) {
return rc;
}
buf = hash_list_.list() + data_off;
return next_->Verify(buf, buf_len, data_off);
}
size_t CalculateMerkleTreeSize(size_t data_size, size_t node_size, bool use_compact_format) {
ZX_ASSERT_MSG(NodeDigest::IsValidNodeSize(node_size), "node_size=%lu", node_size);
size_t merkle_tree_size = 0;
while (data_size > node_size) {
size_t list_size = CalculateHashListSize(data_size, node_size);
// The non compact format pads the hash list to be a multiple of the node size.
data_size = use_compact_format ? list_size : fbl::round_up(list_size, node_size);
merkle_tree_size += data_size;
}
return merkle_tree_size;
}
} // namespace digest