darkfi_sdk/monotree/
utils.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2025 Dyne.org foundation
4 * Copyright (C) 2021 MONOLOG (Taeho Francis Lim and Jongwhan Lee) MIT License
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU Affero General Public License as
8 * published by the Free Software Foundation, either version 3 of the
9 * License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU Affero General Public License for more details.
15 *
16 * You should have received a copy of the GNU Affero General Public License
17 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
18 */
19
20use std::{cmp, ops::Range};
21
22use num::{NumCast, PrimInt};
23use rand::Rng;
24
25use super::{Hash, HASH_LEN};
26
27#[macro_export]
28/// std::cmp::max() extension for use with multiple arguments.
29macro_rules! max {
30    ($x:expr) => ($x);
31    ($x:expr, $($e:expr),+) => (cmp::max($x, max!($($e),+)));
32}
33
34#[macro_export]
35/// std::cmp::min() extension for use with multiple arguments.
36macro_rules! min {
37    ($x:expr) => ($x);
38    ($x:expr, $($e:expr),+) => (cmp::min($x, min!($($e),+)));
39}
40
41/// Cast from a typed scalar to another based on `num_traits`
42pub fn cast<T: NumCast, U: NumCast>(n: T) -> U {
43    NumCast::from(n).expect("cast(): Numcast")
44}
45
46/// Generate a random byte based on `rand::random`.
47pub fn random_byte() -> u8 {
48    rand::random::<u8>()
49}
50
51/// Generate random bytes of the given length.
52pub fn random_bytes(n: usize) -> Vec<u8> {
53    (0..n).map(|_| random_byte()).collect()
54}
55
56/// Generate a random `Hash`, byte-array of `HASH_LEN` length.
57pub fn random_hash() -> Hash {
58    slice_to_hash(&random_bytes(HASH_LEN))
59}
60
61/// Generate a vector of random `Hash` with the given length.
62pub fn random_hashes(n: usize) -> Vec<Hash> {
63    (0..n).map(|_| random_hash()).collect()
64}
65
66/// Get a fixed length byte-array or `Hash` from slice.
67pub fn slice_to_hash(slice: &[u8]) -> Hash {
68    let mut hash = [0x00; HASH_LEN];
69    hash.copy_from_slice(slice);
70    hash
71}
72
73/// Shuffle a slice using _Fisher-Yates_ algorithm.
74pub fn shuffle<T: Clone>(slice: &mut [T]) {
75    let mut rng = rand::thread_rng();
76    let s = slice.len();
77    (0..s).for_each(|i| {
78        let q = rng.gen_range(0..s);
79        slice.swap(i, q);
80    });
81}
82
83/// Get sorted indices from unsorted slice.
84pub fn get_sorted_indices<T>(slice: &[T], reverse: bool) -> Vec<usize>
85where
86    T: Clone + cmp::Ord,
87{
88    let mut t: Vec<_> = slice.iter().enumerate().collect();
89
90    if reverse {
91        t.sort_unstable_by(|(_, a), (_, b)| b.cmp(a));
92    } else {
93        t.sort_unstable_by(|(_, a), (_, b)| a.cmp(b));
94    }
95
96    t.iter().map(|(i, _)| *i).collect()
97}
98
99/// Get length of the longest common prefix bits for the given two slices.
100pub fn len_lcp<T>(a: &[u8], m: &Range<T>, b: &[u8], n: &Range<T>) -> T
101where
102    T: PrimInt + NumCast,
103    Range<T>: Iterator<Item = T>,
104{
105    let count = (cast(0)..min!(m.end - m.start, n.end - n.start))
106        .take_while(|&i| bit(a, m.start + i) == bit(b, n.start + i))
107        .count();
108    cast(count)
109}
110
111static BIT_MASKS: [u8; 8] = [0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01];
112
113/// Get `i`-th bit from bytes slice. Index `i` starts from 0.
114#[inline]
115pub fn bit<T: PrimInt + NumCast>(bytes: &[u8], i: T) -> bool {
116    let i_usize = i.to_usize().unwrap();
117    let q = i_usize >> 3;
118    let r = i_usize & 7;
119    if q >= bytes.len() {
120        return false;
121    }
122    bytes[q] & BIT_MASKS[r] != 0
123}
124
125/// Get the required length of bytes from a `Range`, bits indices across the bytes.
126pub fn nbytes_across<T: PrimInt + NumCast>(start: T, end: T) -> T {
127    let eight = cast(8);
128    let bits = end - (start - start % eight);
129    (bits + eight - T::one()) / eight
130}
131
132/// Convert big-endian bytes into base10 or decimal number.
133pub fn bytes_to_int<T: PrimInt + NumCast>(bytes: &[u8]) -> T {
134    let l = bytes.len();
135    let sum = (0..l).fold(0, |sum, i| sum + (1 << ((l - i - 1) * 8)) * bytes[i] as usize);
136    cast(sum)
137}
138
139/// Get a compressed bytes (leading-zero-truncated big-endian bytes) from a `u64`.
140pub fn int_to_bytes(number: u64) -> Vec<u8> {
141    match number {
142        0 => vec![0x00],
143        _ => number.to_be_bytes().iter().skip_while(|&x| *x == 0x00).copied().collect(),
144    }
145}
146
147/// Convert a Vec slice of bit or `bool` into a number as `usize`.
148pub fn bits_to_usize(bits: &[bool]) -> usize {
149    let l = bits.len();
150    (0..l).fold(0, |sum, i| sum + ((bits[i] as usize) << (l - 1 - i)))
151}
152
153/// Convert a bytes slice into a Vec of bit.
154pub fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
155    bytes_to_slicebit(bytes, &(0..bytes.len() * 8))
156}
157
158/// Convert (bytes slice + Range) representation into bits in forms of `Vec<bool>`.
159pub fn bytes_to_slicebit<T>(bytes: &[u8], range: &Range<T>) -> Vec<bool>
160where
161    T: PrimInt + NumCast,
162    Range<T>: Iterator<Item = T>,
163{
164    range.clone().map(|x| bit(bytes, x)).collect()
165}
166
167/// Convert bits, Vec slice of `bool` into bytes, `Vec<u8>`.
168pub fn bits_to_bytes(bits: &[bool]) -> Vec<u8> {
169    bits.rchunks(8).rev().map(|v| bits_to_usize(v) as u8).collect()
170}
171
172#[cfg(test)]
173mod tests {
174    use super::*;
175    #[test]
176    fn test_bit() {
177        let bytes = [0x73, 0x6f, 0x66, 0x69, 0x61];
178        assert!(bit(&bytes, 10));
179        assert!(!bit(&bytes, 20));
180        assert!(!bit(&bytes, 30));
181    }
182
183    #[test]
184    fn test_nbyte_across() {
185        assert_eq!(nbytes_across(0, 8), 1);
186        assert_eq!(nbytes_across(1, 7), 1);
187        assert_eq!(nbytes_across(5, 9), 2);
188        assert_eq!(nbytes_across(9, 16), 1);
189        assert_eq!(nbytes_across(7, 19), 3);
190    }
191
192    #[test]
193    fn test_bytes_to_int() {
194        let number: usize = bytes_to_int(&[0x73, 0x6f, 0x66, 0x69, 0x61]);
195        assert_eq!(number, 495790221665usize);
196    }
197
198    #[test]
199    fn test_usize_to_bytes() {
200        assert_eq!(int_to_bytes(495790221665u64), [0x73, 0x6f, 0x66, 0x69, 0x61]);
201    }
202
203    #[test]
204    fn test_bytes_to_bits() {
205        assert_eq!(
206            bytes_to_bits(&[0x33, 0x33]),
207            [
208                false, false, true, true, false, false, true, true, false, false, true, true,
209                false, false, true, true,
210            ]
211        );
212    }
213
214    #[test]
215    fn test_bits_to_bytes() {
216        let bits = [
217            false, false, true, true, false, false, true, true, false, false, true, true, false,
218            false, true, true,
219        ];
220        assert_eq!(bits_to_bytes(&bits), [0x33, 0x33]);
221    }
222
223    #[test]
224    fn test_bits_to_usize() {
225        assert_eq!(
226            bits_to_usize(&[
227                false, false, true, true, false, false, true, true, false, false, true, true,
228                false, false, true, true,
229            ]),
230            13107usize
231        );
232    }
233
234    #[test]
235    fn test_len_lcp() {
236        let sofia = [0x73, 0x6f, 0x66, 0x69, 0x61];
237        let maria = [0x6d, 0x61, 0x72, 0x69, 0x61];
238        assert_eq!(len_lcp(&sofia, &(0..3), &maria, &(0..3)), 3);
239        assert_eq!(len_lcp(&sofia, &(0..3), &maria, &(5..9)), 0);
240        assert_eq!(len_lcp(&sofia, &(2..9), &maria, &(18..30)), 5);
241        assert_eq!(len_lcp(&sofia, &(20..30), &maria, &(3..15)), 4);
242    }
243}
darkfi_sdk/monotree/utils.rs

darkfi_sdk/monotree/
utils.rs
