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    #[inline]
42    pub fn is_right(&self, height: u8) -> bool {
43        self.get_bit(height)
44    }
45
46    pub fn as_slice(&self) -> &[u8] {
47        &self.0[..]
48    }
49
50    /// Treat H256 as a path in a tree
51    /// fork height is the number of common bits(from heigher to lower: 255..=0) 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        if height == core::u8::MAX {
65            H256::zero()
66        } else {
67            self.copy_bits(height + 1)
68        }
69    }
70
71    /// Copy bits and return a new H256
72    pub fn copy_bits(&self, start: u8) -> Self {
73        let mut target = H256::zero();
74
75        let start_byte = (start / BYTE_SIZE) as usize;
76        // copy bytes
77        target.0[start_byte..].copy_from_slice(&self.0[start_byte..]);
78
79        // reset remain bytes
80        let remain = start % BYTE_SIZE;
81        if remain > 0 {
82            target.0[start_byte] &= 0b11111111 << remain
83        }
84
85        target
86    }
87}
88
89impl PartialOrd for H256 {
90    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
91        Some(self.cmp(other))
92    }
93}
94
95impl Ord for H256 {
96    fn cmp(&self, other: &Self) -> Ordering {
97        // Compare bits from heigher to lower (255..0)
98        self.0.iter().rev().cmp(other.0.iter().rev())
99    }
100}
101
102impl From<[u8; 32]> for H256 {
103    fn from(v: [u8; 32]) -> H256 {
104        H256(v)
105    }
106}
107
108impl From<H256> for [u8; 32] {
109    fn from(h256: H256) -> [u8; 32] {
110        h256.0
111    }
112}
sparse_merkle_tree/h256.rs

sparse_merkle_tree/
h256.rs
