bitcoin/util/
hash.rs

1// Rust Bitcoin Library
2// Written in 2014 by
3//     Andrew Poelstra <apoelstra@wpsoftware.net>
4// To the extent possible under law, the author(s) have dedicated all
5// copyright and related and neighboring rights to this software to
6// the public domain worldwide. This software is distributed without
7// any warranty.
8//
9// You should have received a copy of the CC0 Public Domain Dedication
10// along with this software.
11// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
12//
13
14//! Hash functions
15//!
16//! Utility functions related to hashing data, including merkleization
17
18use std::cmp::min;
19use std::io;
20
21use hashes::Hash;
22use consensus::encode::Encodable;
23
24/// Calculates the merkle root of a list of hashes inline
25/// into the allocated slice.
26///
27/// In most cases, you'll want to use [bitcoin_merkle_root] instead.
28pub fn bitcoin_merkle_root_inline<T>(data: &mut [T]) -> T
29    where T: Hash + Encodable,
30          <T as Hash>::Engine: io::Write,
31{
32    // Base case
33    if data.is_empty() {
34        return Default::default();
35    }
36    if data.len() < 2 {
37        return T::from_inner(data[0].into_inner());
38    }
39    // Recursion
40    for idx in 0..((data.len() + 1) / 2) {
41        let idx1 = 2 * idx;
42        let idx2 = min(idx1 + 1, data.len() - 1);
43        let mut encoder = T::engine();
44        data[idx1].consensus_encode(&mut encoder).unwrap();
45        data[idx2].consensus_encode(&mut encoder).unwrap();
46        data[idx] = T::from_engine(encoder);
47    }
48    let half_len = data.len() / 2 + data.len() % 2;
49    bitcoin_merkle_root_inline(&mut data[0..half_len])
50}
51
52/// Calculates the merkle root of an iterator of hashes.
53pub fn bitcoin_merkle_root<T, I>(mut iter: I) -> T
54    where T: Hash + Encodable,
55          <T as Hash>::Engine: io::Write,
56          I: ExactSizeIterator<Item = T>,
57{
58    // Base case
59    if iter.len() == 0 {
60        return Default::default();
61    }
62    if iter.len() == 1 {
63        return T::from_inner(iter.next().unwrap().into_inner());
64    }
65    // Recursion
66    let half_len = iter.len() / 2 + iter.len() % 2;
67    let mut alloc = Vec::with_capacity(half_len);
68    while let Some(hash1) = iter.next() {
69        // If the size is odd, use the last element twice.
70        let hash2 = iter.next().unwrap_or(hash1);
71        let mut encoder = T::engine();
72        hash1.consensus_encode(&mut encoder).unwrap();
73        hash2.consensus_encode(&mut encoder).unwrap();
74        alloc.push(T::from_engine(encoder));
75    }
76    bitcoin_merkle_root_inline(&mut alloc)
77}
bitcoin/util/hash.rs

bitcoin/util/
hash.rs
