darkfi_sdk/monotree/
utils.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 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 crate::{ContractError, GenericResult};
23use num::{NumCast, PrimInt};
24use rand::Rng;
25
26use super::{Hash, HASH_LEN};
27
28#[macro_export]
29/// std::cmp::max() extension for use with multiple arguments.
30macro_rules! max {
31    ($x:expr) => ($x);
32    ($x:expr, $($e:expr),+) => (cmp::max($x, max!($($e),+)));
33}
34
35#[macro_export]
36/// std::cmp::min() extension for use with multiple arguments.
37macro_rules! min {
38    ($x:expr) => ($x);
39    ($x:expr, $($e:expr),+) => (cmp::min($x, min!($($e),+)));
40}
41
42/// Cast from a typed scalar to another based on `num_traits`
43pub fn cast<T: NumCast, U: NumCast>(n: T) -> GenericResult<U> {
44    NumCast::from(n).ok_or(ContractError::NumCastError)
45}
46
47/// Generate a random byte based on `rand::random`.
48pub fn random_byte() -> u8 {
49    rand::random::<u8>()
50}
51
52/// Generate random bytes of the given length.
53pub fn random_bytes(n: usize) -> Vec<u8> {
54    (0..n).map(|_| random_byte()).collect()
55}
56
57/// Generate a random `Hash`, byte-array of `HASH_LEN` length.
58pub fn random_hash() -> Hash {
59    slice_to_hash(&random_bytes(HASH_LEN))
60}
61
62/// Generate a vector of random `Hash` with the given length.
63pub fn random_hashes(n: usize) -> Vec<Hash> {
64    (0..n).map(|_| random_hash()).collect()
65}
66
67/// Get a fixed length byte-array or `Hash` from slice.
68pub fn slice_to_hash(slice: &[u8]) -> Hash {
69    let mut hash = [0x00; HASH_LEN];
70    hash.copy_from_slice(slice);
71    hash
72}
73
74/// Shuffle a slice using _Fisher-Yates_ algorithm.
75pub fn shuffle<T: Clone>(slice: &mut [T]) {
76    let mut rng = rand::thread_rng();
77    let s = slice.len();
78    (0..s).for_each(|i| {
79        let q = rng.gen_range(0..s);
80        slice.swap(i, q);
81    });
82}
83
84/// Get sorted indices from unsorted slice.
85pub fn get_sorted_indices<T>(slice: &[T], reverse: bool) -> Vec<usize>
86where
87    T: Clone + cmp::Ord,
88{
89    let mut t: Vec<_> = slice.iter().enumerate().collect();
90    t.sort_unstable_by_key(|(_, a)| *a);
91
92    if reverse {
93        t.iter().rev().map(|(i, _)| *i).collect()
94    } else {
95        t.iter().map(|(i, _)| *i).collect()
96    }
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>) -> GenericResult<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) -> GenericResult<T> {
127    let eight = cast(8)?;
128    let bits = end - (start - start % eight);
129    Ok((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]) -> GenericResult<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).unwrap(), 1);
186        assert_eq!(nbytes_across(1, 7).unwrap(), 1);
187        assert_eq!(nbytes_across(5, 9).unwrap(), 2);
188        assert_eq!(nbytes_across(9, 16).unwrap(), 1);
189        assert_eq!(nbytes_across(7, 19).unwrap(), 3);
190    }
191
192    #[test]
193    fn test_bytes_to_int() {
194        let number: usize = bytes_to_int(&[0x73, 0x6f, 0x66, 0x69, 0x61]).unwrap();
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)).unwrap(), 3);
239        assert_eq!(len_lcp(&sofia, &(0..3), &maria, &(5..9)).unwrap(), 0);
240        assert_eq!(len_lcp(&sofia, &(2..9), &maria, &(18..30)).unwrap(), 5);
241        assert_eq!(len_lcp(&sofia, &(20..30), &maria, &(3..15)).unwrap(), 4);
242    }
243}
darkfi_sdk/monotree/utils.rs

darkfi_sdk/monotree/
utils.rs
