15280118615

//  Copyright 2021, The Tari Project
//
//  Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
//  following conditions are met:
//
//  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
//  disclaimer.
//
//  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
//  following disclaimer in the documentation and/or other materials provided with the distribution.
//
//  3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
//  products derived from this software without specific prior written permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
//  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
//  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
//  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
//  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
//  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
//  USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

use std::{
    convert::{TryFrom, TryInto},
    fmt,
    mem,
    str::FromStr,
};

use super::{node_id::NodeIdError, NodeId};

/// The distance metric used by the [PeerManager](super::PeerManager).
pub type NodeDistance = XorDistance;

/// The XOR distance metric.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Default)]
pub struct XorDistance(u128);

impl XorDistance {
    /// Construct a new zero distance
    pub fn new() -> Self {
        Self(0)
    }

    /// Calculate the distance between two node ids using the XOR metric.
    pub fn from_node_ids(x: &NodeId, y: &NodeId) -> Self {
        let arr = x ^ y;
        arr[..]
            .try_into()
            .expect("unreachable panic: NodeId::byte_size() <= NodeDistance::byte_size()")
    }

    /// Returns the maximum distance.
    pub const fn max_distance() -> Self {
        Self(u128::MAX)
    }

    /// Returns a zero distance.
    pub const fn zero() -> Self {
        Self(0)
    }

    /// Returns the number of bytes required to represent the `XorDistance`
    pub const fn byte_size() -> usize {
        mem::size_of::<u128>()
    }

    /// Returns the bucket that this distance falls between.
    /// The node distance falls between the `i`th bucket if 2^i <= distance < 2^(i+1).
    pub fn get_bucket_index(&self) -> u8 {
        ((u8::try_from(Self::byte_size()).unwrap() * 8) - u8::try_from(self.0.leading_zeros()).unwrap())
            .saturating_sub(1)
    }

    /// Byte representation of the distance value.
    pub fn to_bytes(&self) -> [u8; Self::byte_size()] {
        self.0.to_be_bytes()
    }

    /// Distance represented as a 128-bit unsigned integer.
    pub fn as_u128(&self) -> u128 {
        self.0
    }
}

impl TryFrom<&[u8]> for XorDistance {
    type Error = NodeIdError;

    /// Construct a node distance from a set of bytes
    fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {
        if bytes.len() > Self::byte_size() {
            return Err(NodeIdError::IncorrectByteCount);
        }

        let mut buf = [0; Self::byte_size()];
        // Big endian has the MSB at index 0, if size of `bytes` is less than byte_size it must be offset to have
        // leading 0 bytes
        let offset = Self::byte_size() - bytes.len();
        buf[offset..].copy_from_slice(bytes);
        Ok(XorDistance(u128::from_be_bytes(buf)))
    }
}

impl fmt::Display for NodeDistance {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl FromStr for XorDistance {
    type Err = std::num::ParseIntError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        u128::from_str_radix(s, 16).map(XorDistance)
    }
}

impl fmt::Debug for XorDistance {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut digits = 0;
        let mut suffix = "";
        loop {
            let prefix = self.0 / u128::pow(10, 3 * (digits + 1));

            if prefix == 0 || digits > 8 {
                return write!(f, "XorDist: {}{}", self.0 / u128::pow(10, 3 * digits), suffix);
            }

            digits += 1;
            suffix = match suffix {
                "" => "thousand",
                "thousand" => "million",
                "million" => "billion",
                "billion" => "trillion",
                "trillion" => "quadrillion",
                "quadrillion" => "quintillion",
                "quintillion" => "sextillion",
                "sextillion" => "septillion",
                "septillion" => "e24",
                _ => suffix,
            }
        }
    }
}

#[cfg(test)]
mod test {
    use rand::rngs::OsRng;

    use super::*;
    use crate::types::CommsPublicKey;

    mod ord {
        use super::*;

        #[test]
        fn it_uses_big_endian_ordering() {
            let a = NodeDistance::try_from(&[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1][..]).unwrap();
            let b = NodeDistance::try_from(&[1u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0][..]).unwrap();
            assert!(a < b);
        }
    }

    mod get_bucket_index {
        use super::*;

        #[test]
        fn it_returns_the_correct_index() {
            fn check_for_dist(lsb_dist: u8, expected: u8) {
                assert_eq!(
                    NodeDistance::try_from(&[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, lsb_dist][..])
                        .unwrap()
                        .get_bucket_index(),
                    expected,
                    "Failed for dist = {}",
                    lsb_dist
                );
            }

            assert_eq!(NodeDistance::max_distance().get_bucket_index(), 127);
            assert_eq!(NodeDistance::zero().get_bucket_index(), 0);

            check_for_dist(1, 0);
            for i in 2..4 {
                check_for_dist(i, 1);
            }
            for i in 4..8 {
                check_for_dist(i, 2);
            }
            for i in 8..16 {
                check_for_dist(i, 3);
            }
            assert_eq!(
                NodeDistance::try_from(&[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0b01000001, 0, 0][..])
                    .unwrap()
                    .get_bucket_index(),
                8 * 2 + 7 - 1
            );

            assert_eq!(
                NodeDistance::try_from(&[0b10000000u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0][..])
                    .unwrap()
                    .get_bucket_index(),
                103
            );
        }

        #[test]
        fn correctness_fuzzing() {
            for _ in 0..100 {
                let (_, pk) = CommsPublicKey::random_keypair(&mut OsRng);
                let a = NodeId::from_public_key(&pk);
                let (_, pk) = CommsPublicKey::random_keypair(&mut OsRng);
                let b = NodeId::from_public_key(&pk);
                let dist = NodeDistance::from_node_ids(&a, &b);
                let i = u32::from(dist.get_bucket_index());
                let dist = dist.as_u128();
                assert!(2u128.pow(i) <= dist, "Failed for {}, i = {}", dist, i);
                assert!(dist < 2u128.pow(i + 1), "Failed for {}, i = {}", dist, i,);
            }
        }
    }
}

1	// Copyright 2021, The Tari Project
2	//
3	// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
4	// following conditions are met:
5	//
6	// 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
7	// disclaimer.
8	//
9	// 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
10	// following disclaimer in the documentation and/or other materials provided with the distribution.
11	//
12	// 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
13	// products derived from this software without specific prior written permission.
14	//
15	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
16	// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17	// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
18	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
19	// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
20	// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
21	// USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22
23	use std::{
24	convert::{TryFrom, TryInto},
25	fmt,
26	mem,
27	str::FromStr,
28	};
29
30	use super::{node_id::NodeIdError, NodeId};
31
32	/// The distance metric used by the [PeerManager](super::PeerManager).
33	pub type NodeDistance = XorDistance;
34
35	/// The XOR distance metric.
36	#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Default)]
37	pub struct XorDistance(u128);
38
39	impl XorDistance {
40	/// Construct a new zero distance
41	pub fn new() -> Self {	×
42	Self(0)	×
UNCOV 43	}	×
44
45	/// Calculate the distance between two node ids using the XOR metric.
46	pub fn from_node_ids(x: &NodeId, y: &NodeId) -> Self {	1,902,035✔
47	let arr = x ^ y;	1,902,035✔
48	arr[..]	1,902,035✔
49	.try_into()	1,902,035✔
50	.expect("unreachable panic: NodeId::byte_size() <= NodeDistance::byte_size()")	1,902,035✔
51	}	1,902,035✔
52
53	/// Returns the maximum distance.
54	pub const fn max_distance() -> Self {	940✔
55	Self(u128::MAX)	940✔
56	}	940✔
57
58	/// Returns a zero distance.
59	pub const fn zero() -> Self {	3✔
60	Self(0)	3✔
61	}	3✔
62
63	/// Returns the number of bytes required to represent the `XorDistance`
64	pub const fn byte_size() -> usize {	3,804,231✔
65	mem::size_of::<u128>()	3,804,231✔
66	}	3,804,231✔
67
68	/// Returns the bucket that this distance falls between.
69	/// The node distance falls between the `i`th bucket if 2^i <= distance < 2^(i+1).
70	pub fn get_bucket_index(&self) -> u8 {	119✔
71	((u8::try_from(Self::byte_size()).unwrap() * 8) - u8::try_from(self.0.leading_zeros()).unwrap())	119✔
72	.saturating_sub(1)	119✔
73	}	119✔
74
75	/// Byte representation of the distance value.
76	pub fn to_bytes(&self) -> [u8; Self::byte_size()] {	2✔
77	self.0.to_be_bytes()	2✔
78	}	2✔
79
80	/// Distance represented as a 128-bit unsigned integer.
81	pub fn as_u128(&self) -> u128 {	2,151✔
82	self.0	2,151✔
83	}	2,151✔
84	}
85
86	impl TryFrom<&[u8]> for XorDistance {
87	type Error = NodeIdError;
88
89	/// Construct a node distance from a set of bytes
90	fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {	1,902,056✔
91	if bytes.len() > Self::byte_size() {	1,902,056✔
UNCOV 92	return Err(NodeIdError::IncorrectByteCount);	×
93	}	1,902,056✔
94		1,902,056✔
95	let mut buf = [0; Self::byte_size()];	1,902,056✔
96	// Big endian has the MSB at index 0, if size of `bytes` is less than byte_size it must be offset to have	1,902,056✔
97	// leading 0 bytes	1,902,056✔
98	let offset = Self::byte_size() - bytes.len();	1,902,056✔
99	buf[offset..].copy_from_slice(bytes);	1,902,056✔
100	Ok(XorDistance(u128::from_be_bytes(buf)))	1,902,056✔
101	}	1,902,056✔
102	}
103
104	impl fmt::Display for NodeDistance {
105	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {	×
106	write!(f, "{}", self.0)	×
UNCOV 107	}	×
108	}
109
110	impl FromStr for XorDistance {
111	type Err = std::num::ParseIntError;
112
UNCOV 113	fn from_str(s: &str) -> Result<Self, Self::Err> {	×
114	u128::from_str_radix(s, 16).map(XorDistance)	×
115	}	×
116	}
117
118	impl fmt::Debug for XorDistance {
119	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {	×
120	let mut digits = 0;	×
121	let mut suffix = "";	×
122	loop {
123	let prefix = self.0 / u128::pow(10, 3 * (digits + 1));	×
124		×
125	if prefix == 0 \|\| digits > 8 {	×
126	return write!(f, "XorDist: {}{}", self.0 / u128::pow(10, 3 * digits), suffix);	×
127	}	×
128		×
129	digits += 1;	×
130	suffix = match suffix {	×
131	"" => "thousand",	×
UNCOV 132	"thousand" => "million",	×
UNCOV 133	"million" => "billion",	×
134	"billion" => "trillion",	×
UNCOV 135	"trillion" => "quadrillion",	×
UNCOV 136	"quadrillion" => "quintillion",	×
UNCOV 137	"quintillion" => "sextillion",	×
UNCOV 138	"sextillion" => "septillion",	×
UNCOV 139	"septillion" => "e24",	×
UNCOV 140	_ => suffix,	×
141	}
142	}
UNCOV 143	}	×
144	}
145
146	#[cfg(test)]
147	mod test {
148	use rand::rngs::OsRng;
149
150	use super::*;
151	use crate::types::CommsPublicKey;
152
153	mod ord {
154	use super::*;
155
156	#[test]
157	fn it_uses_big_endian_ordering() {	1✔
158	let a = NodeDistance::try_from(&[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1][..]).unwrap();	1✔
159	let b = NodeDistance::try_from(&[1u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0][..]).unwrap();	1✔
160	assert!(a < b);	1✔
161	}	1✔
162	}
163
164	mod get_bucket_index {
165	use super::*;
166
167	#[test]
168	fn it_returns_the_correct_index() {	1✔
169	fn check_for_dist(lsb_dist: u8, expected: u8) {	15✔
170	assert_eq!(	15✔
171	NodeDistance::try_from(&[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, lsb_dist][..])	15✔
172	.unwrap()	15✔
173	.get_bucket_index(),	15✔
174	expected,
UNCOV 175	"Failed for dist = {}",	×
176	lsb_dist
177	);
178	}	15✔
179
180	assert_eq!(NodeDistance::max_distance().get_bucket_index(), 127);	1✔
181	assert_eq!(NodeDistance::zero().get_bucket_index(), 0);	1✔
182
183	check_for_dist(1, 0);	1✔
184	for i in 2..4 {	3✔
185	check_for_dist(i, 1);	2✔
186	}	2✔
187	for i in 4..8 {	5✔
188	check_for_dist(i, 2);	4✔
189	}	4✔
190	for i in 8..16 {	9✔
191	check_for_dist(i, 3);	8✔
192	}	8✔
193	assert_eq!(	1✔
194	NodeDistance::try_from(&[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0b01000001, 0, 0][..])	1✔
195	.unwrap()	1✔
196	.get_bucket_index(),	1✔
197	8 * 2 + 7 - 1	1✔
198	);	1✔
199
200	assert_eq!(	1✔
201	NodeDistance::try_from(&[0b10000000u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0][..])	1✔
202	.unwrap()	1✔
203	.get_bucket_index(),	1✔
204	103	1✔
205	);	1✔
206	}	1✔
207
208	#[test]
209	fn correctness_fuzzing() {	1✔
210	for _ in 0..100 {	101✔
211	let (_, pk) = CommsPublicKey::random_keypair(&mut OsRng);	100✔
212	let a = NodeId::from_public_key(&pk);	100✔
213	let (_, pk) = CommsPublicKey::random_keypair(&mut OsRng);	100✔
214	let b = NodeId::from_public_key(&pk);	100✔
215	let dist = NodeDistance::from_node_ids(&a, &b);	100✔
216	let i = u32::from(dist.get_bucket_index());	100✔
217	let dist = dist.as_u128();	100✔
218	assert!(2u128.pow(i) <= dist, "Failed for {}, i = {}", dist, i);	100✔
219	assert!(dist < 2u128.pow(i + 1), "Failed for {}, i = {}", dist, i,);	100✔
220	}
221	}	1✔
222	}
223	}

tari-project / tari / 15280118615

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous