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
111/// Get `i`-th bit from bytes slice. Index `i` starts from 0.
112pub fn bit<T: PrimInt + NumCast>(bytes: &[u8], i: T) -> bool {
113    let q = i.to_usize().expect("bit(): usize") / 8;
114    let r = i.to_u8().expect("bit(): u8") % 8;
115    (bytes[q] >> (7 - r)) & 0x01 == 0x01
116}
117
118/// Get the required length of bytes from a `Range`, bits indices across the bytes.
119pub fn nbytes_across<T: PrimInt + NumCast>(start: T, end: T) -> T {
120    let n = (end - (start - start % cast(8))) / cast(8);
121
122    if end % cast(8) == cast(0) {
123        n
124    } else {
125        n + cast(1)
126    }
127}
128
129/// Adjust the bytes representation for `Bits` when shifted.
130/// Returns a bytes shift, `n` and thereby resulting shifted range, `R`.
131pub fn offsets<T: PrimInt + NumCast>(range: &Range<T>, n: T, tail: bool) -> (T, Range<T>) {
132    let x = range.start + n;
133    let e: T = cast(8);
134    if tail {
135        (nbytes_across(range.start, x), range.start..x)
136    } else {
137        (x / e, x % e..range.end - e * (x / e))
138    }
139}
140
141/// Convert big-endian bytes into base10 or decimal number.
142pub fn bytes_to_int<T: PrimInt + NumCast>(bytes: &[u8]) -> T {
143    let l = bytes.len();
144    let sum = (0..l).fold(0, |sum, i| sum + (1 << ((l - i - 1) * 8)) * bytes[i] as usize);
145    cast(sum)
146}
147
148/// Get a compressed bytes (leading-zero-truncated big-endian bytes) from a `u64`.
149pub fn int_to_bytes(number: u64) -> Vec<u8> {
150    match number {
151        0 => vec![0x00],
152        _ => number.to_be_bytes().iter().skip_while(|&x| *x == 0x00).copied().collect(),
153    }
154}
155
156/// Convert a Vec slice of bit or `bool` into a number as `usize`.
157pub fn bits_to_usize(bits: &[bool]) -> usize {
158    let l = bits.len();
159    (0..l).fold(0, |sum, i| sum + ((bits[i] as usize) << (l - 1 - i)))
160}
161
162/// Convert a bytes slice into a Vec of bit.
163pub fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
164    bytes_to_slicebit(bytes, &(0..bytes.len() * 8))
165}
166
167/// Convert (bytes slice + Range) representation into bits in forms of `Vec<bool>`.
168pub fn bytes_to_slicebit<T>(bytes: &[u8], range: &Range<T>) -> Vec<bool>
169where
170    T: PrimInt + NumCast,
171    Range<T>: Iterator<Item = T>,
172{
173    range.clone().map(|x| bit(bytes, x)).collect()
174}
175
176/// Convert bits, Vec slice of `bool` into bytes, `Vec<u8>`.
177pub fn bits_to_bytes(bits: &[bool]) -> Vec<u8> {
178    bits.rchunks(8).rev().map(|v| bits_to_usize(v) as u8).collect()
179}
darkfi_sdk/monotree/utils.rs

darkfi_sdk/monotree/
utils.rs
