fuchsia_merkle/
util.rs

1// Copyright 2018 The Fuchsia 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
5use bssl_crypto::digest::Sha256;
6use std::mem::{size_of, size_of_val};
7
8use crate::{BLOCK_SIZE, HASH_SIZE, Hash};
9
10pub(crate) const HASHES_PER_BLOCK: usize = BLOCK_SIZE / HASH_SIZE;
11
12type BlockIdentity = [u8; size_of::<u64>() + size_of::<u32>()];
13
14/// Generate the bytes representing a block's identity.
15fn make_identity(length: usize, level: usize, offset: usize) -> BlockIdentity {
16    let offset_or_level = (offset as u64 | level as u64).to_le_bytes();
17    let length = (length as u32).to_le_bytes();
18    let mut ret: BlockIdentity = [0; size_of::<BlockIdentity>()];
19    let (ret_offset_or_level, ret_length) = ret.split_at_mut(size_of_val(&offset_or_level));
20    ret_offset_or_level.copy_from_slice(&offset_or_level);
21    ret_length.copy_from_slice(&length);
22    ret
23}
24
25/// Compute the merkle hash of a block of data.
26///
27/// A merkle hash is the SHA-256 hash of a block of data with a small header built from the length
28/// of the data, the level of the tree (0 for data blocks), and the offset into the level. The
29/// block will be zero filled if its len is less than [`BLOCK_SIZE`], except for when the first
30/// data block is completely empty.
31///
32/// # Panics
33///
34/// Panics if `block.len()` exceeds [`BLOCK_SIZE`] or if `offset` is not aligned to [`BLOCK_SIZE`]
35pub(crate) fn hash_block(block: &[u8], offset: usize) -> Hash {
36    assert!(block.len() <= BLOCK_SIZE);
37    assert!(offset.is_multiple_of(BLOCK_SIZE));
38
39    let mut hasher = Sha256::new();
40    hasher.update(&make_identity(block.len(), 0, offset));
41    hasher.update(block);
42    // Zero fill block up to BLOCK_SIZE. As a special case, if the first data block is completely
43    // empty, it is not zero filled.
44    if block.len() != BLOCK_SIZE && !(block.is_empty() && offset == 0) {
45        update_with_zeros(&mut hasher, BLOCK_SIZE - block.len());
46    }
47
48    Hash::from(hasher.digest())
49}
50
51/// Updates `hasher` with `count` zeros.
52pub(crate) fn update_with_zeros(hasher: &mut Sha256, mut count: usize) {
53    const BUF_SIZE: usize = 512;
54    const ZEROS: [u8; BUF_SIZE] = [0; BUF_SIZE];
55    while count >= BUF_SIZE {
56        count -= BUF_SIZE;
57        hasher.update(&ZEROS);
58    }
59    if count > 0 {
60        hasher.update(&ZEROS[0..count]);
61    }
62}
63
64/// Creates a new [`Sha256`] for hashing blocks of hashes. The hasher is initialized with the
65/// block's identity.
66pub(crate) fn make_hash_hasher(hashes_per_hash: usize, level: usize, offset: usize) -> Sha256 {
67    debug_assert!(level > 0);
68    let bytes_per_hash = hashes_per_hash * HASH_SIZE;
69    debug_assert!(offset.is_multiple_of(bytes_per_hash));
70    let mut hasher = Sha256::new();
71    hasher.update(&make_identity(bytes_per_hash, level, offset));
72    hasher
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_hash_block_empty() {
81        let block = [];
82        let hash = hash_block(&block[..], 0);
83        let expected =
84            "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b".parse().unwrap();
85        assert_eq!(hash, expected);
86    }
87
88    #[test]
89    fn test_hash_block_single() {
90        let block = vec![0xFF; 8192];
91        let hash = hash_block(&block[..], 0);
92        let expected =
93            "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737".parse().unwrap();
94        assert_eq!(hash, expected);
95    }
96}
fuchsia_merkle/util.rs

fuchsia_merkle/
util.rs
