nam_sparse_merkle_tree/
h256.rs

1use crate::InternalKey;
2#[cfg(feature = "borsh")]
3use borsh::{BorshDeserialize, BorshSerialize};
4
5/// Represent 256 bits
6#[derive(Eq, PartialEq, Debug, Default, Hash, Clone, Copy, PartialOrd, Ord)]
7#[cfg_attr(feature = "borsh", derive(BorshSerialize, BorshDeserialize))]
8pub struct H256([u8; 32]);
9
10const ZERO: H256 = H256([0u8; 32]);
11const MAX_INDEX: u8 = 31;
12const BYTE_SIZE: u8 = 8;
13
14impl H256 {
15    pub const fn zero() -> Self {
16        ZERO
17    }
18
19    pub fn is_zero(&self) -> bool {
20        self == &ZERO
21    }
22
23    #[inline]
24    pub fn get_bit(&self, i: u8) -> bool {
25        let byte_pos = MAX_INDEX - i / BYTE_SIZE;
26        let bit_pos = i % BYTE_SIZE;
27        let bit = self.0[byte_pos as usize] >> bit_pos & 1;
28        bit != 0
29    }
30
31    #[inline]
32    pub fn set_bit(&mut self, i: u8) {
33        let byte_pos = MAX_INDEX - i / BYTE_SIZE;
34        let bit_pos = i % BYTE_SIZE;
35        self.0[byte_pos as usize] |= 1 << bit_pos as u8;
36    }
37
38    #[inline]
39    pub fn clear_bit(&mut self, i: u8) {
40        let byte_pos = MAX_INDEX - i / BYTE_SIZE;
41        let bit_pos = i % BYTE_SIZE;
42        self.0[byte_pos as usize] &= !((1 << bit_pos) as u8);
43    }
44
45    pub fn as_slice(&self) -> &[u8] {
46        &self.0[..]
47    }
48
49    /// Treat H256 as a path in a tree
50    /// fork height is the number of common bits(from heigher to lower: 255..=0)
51    /// of two H256
52    pub fn fork_height(&self, key: &H256) -> u8 {
53        for h in (0..=core::u8::MAX).rev() {
54            if self.get_bit(h) != key.get_bit(h) {
55                return h;
56            }
57        }
58        0
59    }
60
61    /// Treat H256 as a path in a tree
62    /// return parent_path of self
63    pub fn parent_path(&self, height: u8) -> Self {
64        height
65            .checked_add(1)
66            .map(|i| self.copy_bits(i..))
67            .unwrap_or_else(H256::zero)
68    }
69
70    /// Copy bits and return a new H256
71    pub fn copy_bits(&self, range: impl core::ops::RangeBounds<u8>) -> Self {
72        const MAX: usize = 256;
73        const ARRAY_SIZE: usize = 32;
74        const BYTE: usize = 8;
75        use core::ops::Bound;
76
77        let mut target = H256::zero();
78        let start = match range.start_bound() {
79            Bound::Included(&i) => i as usize,
80            Bound::Excluded(&i) => panic!("do not allows excluded start: {}", i),
81            Bound::Unbounded => 0,
82        };
83
84        let mut end = match range.end_bound() {
85            Bound::Included(&i) => i.saturating_add(1) as usize,
86            Bound::Excluded(&i) => i as usize,
87            Bound::Unbounded => MAX,
88        };
89
90        if start >= MAX {
91            return target;
92        } else if end > MAX {
93            end = MAX;
94        }
95
96        if end < start {
97            panic!("end can't less than start: start {} end {}", start, end);
98        }
99
100        let end_byte = {
101            let remain = if start % BYTE != 0 { 1 } else { 0 };
102            ARRAY_SIZE - start / BYTE - remain
103        };
104        let start_byte = ARRAY_SIZE - end / BYTE;
105        // copy bytes
106        if start_byte < self.0.len() && start_byte <= end_byte {
107            target.0[start_byte..end_byte].copy_from_slice(&self.0[start_byte..end_byte]);
108        }
109
110        // copy remain bits
111        for i in (start..core::cmp::min((ARRAY_SIZE - end_byte) * BYTE, end))
112            .chain(core::cmp::max((ARRAY_SIZE - start_byte) * BYTE, start)..end)
113        {
114            if self.get_bit(i as u8) {
115                target.set_bit(i as u8)
116            }
117        }
118        target
119    }
120}
121
122impl From<[u8; 32]> for H256 {
123    fn from(v: [u8; 32]) -> H256 {
124        H256(v)
125    }
126}
127
128impl From<H256> for [u8; 32] {
129    fn from(v: H256) -> [u8; 32] {
130        v.0
131    }
132}
133
134/// A wrapper type for using a hash an internal key
135#[derive(Eq, PartialEq, Debug, Hash, Clone, Copy, PartialOrd, Ord)]
136#[cfg_attr(feature = "borsh", derive(BorshSerialize, BorshDeserialize))]
137pub struct Hash(InternalKey<32>);
138
139impl core::ops::Deref for Hash {
140    type Target = InternalKey<32>;
141
142    fn deref(&self) -> &Self::Target {
143        &self.0
144    }
145}
146
147impl From<H256> for Hash {
148    fn from(hash: H256) -> Self {
149        let hash: [u8; 32] = hash.into();
150        Self(hash.into())
151    }
152}
153
154impl From<[u8; 32]> for Hash {
155    fn from(hash: [u8; 32]) -> Self {
156        Self(hash.into())
157    }
158}
nam_sparse_merkle_tree/h256.rs

nam_sparse_merkle_tree/
h256.rs
