| // 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. | |
| #ifndef SRC_LIB_DIGEST_NODE_DIGEST_H_ | |
| #define SRC_LIB_DIGEST_NODE_DIGEST_H_ | |
| #include <lib/stdcompat/bit.h> | |
| #include <stddef.h> | |
| #include <stdint.h> | |
| #include <zircon/types.h> | |
| #include <fbl/algorithm.h> | |
| #include <fbl/macros.h> | |
| #include "src/lib/digest/digest.h" | |
| namespace digest { | |
| const size_t kMinNodeSize = 512; | |
| const size_t kDefaultNodeSize = 8192; | |
| const size_t kMaxNodeSize = 32768; | |
| // Digest wrapper functions for hashing data organized into "nodes" of a fixed size. The specific | |
| // algorithm is backwards compatible with BlobFS: | |
| // digest = Hash((id | data_off) + (data_len - data_off) + node_data + padding) | |
| // where: | |
| // * id is usage-specific (e.g. the tree level when used in a Merkle tree). | |
| // * data_off is the offset for a specific node. | |
| // * data_len is the total length of the data. | |
| // * node_data is the actual bytes from the node. | |
| // * padding is |kNodeSize - length| zeros. | |
| class NodeDigest { | |
| public: | |
| NodeDigest() = default; | |
| ~NodeDigest() = default; | |
| DISALLOW_COPY_ASSIGN_AND_MOVE(NodeDigest); | |
| const Digest& get() const { return digest_; } | |
| size_t len() const { return digest_.len(); } | |
| uint64_t id() const { return id_; } | |
| size_t node_size() const { return node_size_; } | |
| void set_id(uint64_t id) { id_ = id; } | |
| // Sets the node size if |node_size| satisfies |IsValidNodeSize|. | |
| zx_status_t SetNodeSize(size_t node_size); | |
| // Returns true if |data_off| is aligned to a node boundary. | |
| bool IsAligned(size_t data_off) const { return data_off % node_size_ == 0; } | |
| // Returns the node number for a given |data_off|. | |
| size_t ToNode(size_t data_off) const { return data_off / node_size_; } | |
| // Returns the greatest node boundary that is not greater than |data_off|. Returns |data_off| if | |
| // it is node-aligned. | |
| size_t PrevAligned(size_t data_off) const { return fbl::round_down(data_off, node_size_); } | |
| // Returns the smallest node boundary that is not less than |data_off|. Returns |data_off| if it | |
| // is node-aligned. | |
| size_t NextAligned(size_t data_off) const { return fbl::round_up(data_off, node_size_); } | |
| // Returns the largest node-aligned offset. | |
| size_t MaxAligned() const { return PrevAligned(SIZE_MAX); } | |
| // Wrapper for Digest::Init. This primes the working |digest_| initializing it | |
| // and hashing two values: the "locality", which is the bitwise-XOR of the |id_| and |data_off|, | |
| // and the "length", which is the |node_size_| or |data_len| - |data-off|, whichever is less. | |
| zx_status_t Reset(size_t data_off, size_t data_len); | |
| // Wrapper for Digest::Update. This will hash data up to |buf_len| bytes from |buf|, and return | |
| // the number of bytes hashed. | |
| size_t Append(const void* buf, size_t buf_len); | |
| // Appends zeros to fill up the rest of the node. | |
| void PadWithZeros(); | |
| // Returns |true| if |node_size| is a power of 2 between |kMinNodeSize| and |kMaxNodeSize|. | |
| static constexpr bool IsValidNodeSize(size_t node_size) { | |
| return node_size >= kMinNodeSize && node_size <= kMaxNodeSize && | |
| cpp20::has_single_bit(node_size); | |
| } | |
| private: | |
| // The underlying digest used to hash the data. | |
| Digest digest_; | |
| // Number of bytes per node. | |
| size_t node_size_ = kDefaultNodeSize; | |
| // Caller-supplied identifier that is mixed into the hash. | |
| uint64_t id_ = 0; | |
| // Remaining bytes to consume. | |
| size_t to_append_ = 0; | |
| // Length of padding when finalizing the digest. | |
| size_t pad_len_ = 0; | |
| }; | |
| } // namespace digest | |
| #endif // SRC_LIB_DIGEST_NODE_DIGEST_H_ |