restricted_sparse_merkle_tree/
h256.rs

1use core::cmp::Ordering;
2
3/// Represent 256 bits
4#[derive(Eq, PartialEq, Debug, Default, Hash, Clone, Copy)]
5pub struct H256([u8; 32]);
6
7const ZERO: H256 = H256([0u8; 32]);
8const BYTE_SIZE: u8 = 8;
9
10impl H256 {
11    pub const fn zero() -> Self {
12        ZERO
13    }
14
15    pub fn is_zero(&self) -> bool {
16        self == &ZERO
17    }
18
19    #[inline]
20    pub fn get_bit(&self, i: u8) -> bool {
21        let byte_pos = i / BYTE_SIZE;
22        let bit_pos = i % BYTE_SIZE;
23        let bit = self.0[byte_pos as usize] >> bit_pos & 1;
24        bit != 0
25    }
26
27    #[inline]
28    pub fn set_bit(&mut self, i: u8) {
29        let byte_pos = i / BYTE_SIZE;
30        let bit_pos = i % BYTE_SIZE;
31        self.0[byte_pos as usize] |= 1 << bit_pos as u8;
32    }
33
34    #[inline]
35    pub fn clear_bit(&mut self, i: u8) {
36        let byte_pos = i / BYTE_SIZE;
37        let bit_pos = i % BYTE_SIZE;
38        self.0[byte_pos as usize] &= !((1 << bit_pos) as u8);
39    }
40
41    pub fn as_slice(&self) -> &[u8] {
42        &self.0[..]
43    }
44
45    /// Treat H256 as a path in a tree
46    /// fork height is the number of common bits(from heigher to lower: 255..=0) of two H256
47    pub fn fork_height(&self, key: &H256) -> u8 {
48        for h in (0..=core::u8::MAX).rev() {
49            if self.get_bit(h) != key.get_bit(h) {
50                return h;
51            }
52        }
53        0
54    }
55
56    /// Treat H256 as a path in a tree
57    /// return parent_path of self
58    pub fn parent_path(&self, height: u8) -> Self {
59        if height == core::u8::MAX {
60            H256::zero()
61        } else {
62            self.copy_bits(height + 1)
63        }
64    }
65
66    /// Copy bits and return a new H256
67    pub fn copy_bits(&self, start: u8) -> Self {
68        let mut target = H256::zero();
69
70        let start_byte = (start / BYTE_SIZE) as usize;
71        // copy bytes
72        target.0[start_byte..].copy_from_slice(&self.0[start_byte..]);
73
74        // reset remain bytes
75        let remain = start % BYTE_SIZE;
76        if remain > 0 {
77            target.0[start_byte] &= 0b11111111 << remain
78        }
79
80        target
81    }
82}
83
84impl PartialOrd for H256 {
85    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
86        Some(self.cmp(other))
87    }
88}
89
90impl Ord for H256 {
91    fn cmp(&self, other: &Self) -> Ordering {
92        // Compare bits from heigher to lower (255..0)
93        self.0.iter().rev().cmp(other.0.iter().rev())
94    }
95}
96
97impl From<[u8; 32]> for H256 {
98    fn from(v: [u8; 32]) -> H256 {
99        H256(v)
100    }
101}
102
103impl Into<[u8; 32]> for H256 {
104    fn into(self: H256) -> [u8; 32] {
105        self.0
106    }
107}
restricted_sparse_merkle_tree/h256.rs

restricted_sparse_merkle_tree/
h256.rs
