#![doc(
html_logo_url = "https://raw.githubusercontent.com/maidsafe/QA/master/Images/maidsafe_logo.png",
html_favicon_url = "http://maidsafe.net/img/favicon.ico",
html_root_url = "http://maidsafe.github.io/xor_name"
)]
#![forbid(
mutable_transmutes,
no_mangle_const_items,
unknown_crate_types,
warnings
)]
#![deny(
deprecated,
improper_ctypes,
missing_docs,
non_shorthand_field_patterns,
overflowing_literals,
stable_features,
unconditional_recursion,
unknown_lints,
unsafe_code,
unused,
unused_allocation,
unused_attributes,
unused_comparisons,
unused_features,
unused_parens,
while_true
)]
#![warn(
trivial_casts,
trivial_numeric_casts,
unused_extern_crates,
unused_import_braces,
unused_qualifications,
unused_results
)]
#![allow(
box_pointers,
missing_copy_implementations,
missing_debug_implementations,
variant_size_differences
)]
#![cfg_attr(feature = "clippy", feature(plugin))]
#![cfg_attr(feature = "clippy", plugin(clippy))]
#![cfg_attr(feature = "clippy", deny(clippy, clippy_pedantic))]
#![cfg_attr(feature = "clippy", allow(use_debug))]
#![allow(unused_extern_crates)]
#[macro_use]
mod prefix;
mod xorable;
use hex::{FromHex, FromHexError, ToHex};
use log::error;
use num_bigint::BigUint;
pub use prefix::Prefix;
use rand::{
distributions::{Distribution, Standard},
Rng,
};
use serde::{Deserialize, Serialize};
use std::cmp::Ordering;
use std::fmt;
use std::ops;
pub use xorable::Xorable;
pub(crate) fn slice_as_u8_32_array(slice: &[u8]) -> [u8; 32] {
let mut arr = [0u8; 32];
arr.clone_from_slice(slice);
arr
}
pub const XOR_NAME_LEN: usize = 32;
#[derive(Debug)]
pub enum XorNameFromHexError {
InvalidCharacter(char, usize),
WrongLength,
}
#[derive(Eq, Copy, Clone, Default, Hash, Ord, PartialEq, PartialOrd, Serialize, Deserialize)]
pub struct XorName(pub [u8; XOR_NAME_LEN]);
impl XorName {
pub fn to_hex(&self) -> String {
self.0.to_hex()
}
pub fn count_differing_bits(&self, other: &Self) -> u32 {
self.0
.iter()
.zip(other.0.iter())
.fold(0, |acc, (a, b)| acc + (a ^ b).count_ones())
}
pub fn from_hex(s: &str) -> Result<Self, XorNameFromHexError> {
let data: Vec<u8> = match FromHex::from_hex(&s) {
Ok(v) => v,
Err(FromHexError::InvalidHexCharacter { c, index }) => {
return Err(XorNameFromHexError::InvalidCharacter(c, index));
}
Err(FromHexError::InvalidHexLength) => return Err(XorNameFromHexError::WrongLength),
};
if data.len() != XOR_NAME_LEN {
return Err(XorNameFromHexError::WrongLength);
}
Ok(Self(slice_as_u8_32_array(&data[..])))
}
pub fn closer(&self, lhs: &Self, rhs: &Self) -> bool {
self.cmp_distance(lhs, rhs) == Ordering::Less
}
pub fn closer_or_equal(&self, lhs: &Self, rhs: &Self) -> bool {
self.cmp_distance(lhs, rhs) != Ordering::Greater
}
fn get_debug_id(&self) -> String {
format!("{:02x}{:02x}{:02x}..", self.0[0], self.0[1], self.0[2])
}
fn from_big_uint(value: BigUint) -> Self {
let little_endian_value = value.to_bytes_le();
if little_endian_value.len() > XOR_NAME_LEN {
error!("This BigUint value exceeds the maximum capable of being held as an XorName.");
}
let mut xor_name = Self::default();
for (xor_name_elt, little_endian_elt) in
xor_name.0.iter_mut().rev().zip(little_endian_value.iter())
{
*xor_name_elt = *little_endian_elt;
}
xor_name
}
}
impl Xorable for XorName {
fn common_prefix(&self, other: &Self) -> usize {
self.0.common_prefix(&other.0)
}
fn cmp_distance(&self, lhs: &Self, rhs: &Self) -> Ordering {
self.0.cmp_distance(&lhs.0, &rhs.0)
}
fn bit(&self, i: usize) -> bool {
self.0.bit(i)
}
fn differs_in_bit(&self, name: &Self, i: usize) -> bool {
self.0.differs_in_bit(&name.0, i)
}
fn with_flipped_bit(self, i: usize) -> Self {
Self(self.0.with_flipped_bit(i))
}
fn with_bit(self, i: usize, bit: bool) -> Self {
Self(self.0.with_bit(i, bit))
}
fn binary(&self) -> String {
self.0.binary()
}
fn debug_binary(&self) -> String {
self.0.debug_binary()
}
fn set_remaining(self, n: usize, val: bool) -> Self {
Self(self.0.set_remaining(n, val))
}
fn from_hash<T: AsRef<[u8]>>(hash: T) -> Self {
Self(Xorable::from_hash(hash))
}
}
impl fmt::Debug for XorName {
fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
write!(formatter, "{}", self.get_debug_id())
}
}
impl fmt::Display for XorName {
fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
write!(formatter, "{}", self.get_debug_id())
}
}
impl fmt::Binary for XorName {
fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
write!(formatter, "{}", self.debug_binary())
}
}
impl Distribution<XorName> for Standard {
fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> XorName {
let mut ret = [0u8; XOR_NAME_LEN];
for r in ret[..].iter_mut() {
*r = rng.gen::<u8>();
}
XorName(ret)
}
}
impl ops::Index<ops::Range<usize>> for XorName {
type Output = [u8];
fn index(&self, index: ops::Range<usize>) -> &[u8] {
let Self(b) = self;
b.index(index)
}
}
impl ops::Index<ops::RangeTo<usize>> for XorName {
type Output = [u8];
fn index(&self, index: ops::RangeTo<usize>) -> &[u8] {
let Self(b) = self;
b.index(index)
}
}
impl ops::Index<ops::RangeFrom<usize>> for XorName {
type Output = [u8];
fn index(&self, index: ops::RangeFrom<usize>) -> &[u8] {
let Self(b) = self;
b.index(index)
}
}
impl ops::Index<ops::RangeFull> for XorName {
type Output = [u8];
fn index(&self, index: ops::RangeFull) -> &[u8] {
let Self(b) = self;
b.index(index)
}
}
impl ops::Not for XorName {
type Output = Self;
fn not(mut self) -> Self {
for byte in &mut self.0 {
*byte = !*byte;
}
self
}
}
impl ops::Sub for XorName {
type Output = Self;
fn sub(self, rhs: Self) -> Self::Output {
(&self).sub(&rhs)
}
}
impl<'a> ops::Sub for &'a XorName {
type Output = XorName;
fn sub(self, rhs: &XorName) -> Self::Output {
XorName::from_big_uint(BigUint::from_bytes_be(&self.0) - BigUint::from_bytes_be(&rhs.0))
}
}
impl ops::Div<u32> for XorName {
type Output = Self;
fn div(self, rhs: u32) -> Self::Output {
(&self).div(&rhs)
}
}
impl<'a> ops::Div<&'a u32> for &'a XorName {
type Output = XorName;
fn div(self, rhs: &u32) -> Self::Output {
XorName::from_big_uint(BigUint::from_bytes_be(&self.0) / BigUint::new(vec![*rhs]))
}
}
impl AsRef<XorName> for XorName {
fn as_ref(&self) -> &Self {
self
}
}
#[cfg(test)]
mod tests {
use super::*;
use bincode::{deserialize, serialize};
use std::cmp::Ordering;
const XOR_NAME_BITS: usize = XOR_NAME_LEN * 8;
#[test]
fn serialisation_xor_name() {
let mut rng = rand::thread_rng();
let obj_before: XorName = rng.gen();
let data = serialize(&obj_before).unwrap();
assert_eq!(data.len(), XOR_NAME_LEN);
let obj_after: XorName = deserialize(&data).unwrap();
assert_eq!(obj_before, obj_after);
}
#[test]
#[allow(clippy::eq_op)]
fn xor_name_ord() {
let type1: XorName = XorName([1u8; XOR_NAME_LEN]);
let type2: XorName = XorName([2u8; XOR_NAME_LEN]);
assert_eq!(Ord::cmp(&type1, &type1), Ordering::Equal);
assert_eq!(Ord::cmp(&type1, &type2), Ordering::Less);
assert_eq!(Ord::cmp(&type2, &type1), Ordering::Greater);
assert!(type1 < type2);
assert!(type1 <= type2);
assert!(type1 <= type1);
assert!(type2 > type1);
assert!(type2 >= type1);
assert!(type1 >= type1);
assert!(!(type2 < type1));
assert!(!(type2 <= type1));
assert!(!(type1 > type2));
assert!(!(type1 >= type2));
}
#[test]
fn xor_name_equal_assertion() {
let mut rng = rand::thread_rng();
let type1: XorName = rng.gen();
let type1_clone = type1;
let type2: XorName = rng.gen();
assert_eq!(type1, type1_clone);
assert!(!(type1 != type1_clone));
assert_ne!(type1, type2);
}
#[test]
fn closeness() {
let mut rng = rand::thread_rng();
let obj0: XorName = rng.gen();
let obj0_clone = obj0;
let obj1: XorName = rng.gen();
assert!(obj0.closer(&obj0_clone, &obj1));
assert!(!obj0.closer(&obj1, &obj0_clone));
}
#[test]
fn format_nametype() {
let mut rng = rand::thread_rng();
for _ in 0..5 {
let my_name: XorName = rng.gen();
let debug_id = my_name.get_debug_id();
let full_id = my_name.to_hex();
assert_eq!(debug_id.len(), 8);
assert_eq!(full_id.len(), 2 * XOR_NAME_LEN);
assert_eq!(&debug_id[0..6].to_owned(), &full_id[0..6]);
}
}
#[test]
fn format_fixed_low_char_nametype() {
let low_char_id = [1u8; XOR_NAME_LEN];
let my_low_char_name = XorName(low_char_id);
let debug_id = my_low_char_name.get_debug_id();
let full_id = my_low_char_name.to_hex();
assert_eq!(debug_id.len(), 8);
assert_eq!(full_id.len(), 2 * XOR_NAME_LEN);
assert_eq!(&debug_id[0..6], &full_id[0..6].to_owned());
}
#[test]
fn with_flipped_bit() {
let mut rng = rand::thread_rng();
let name: XorName = rng.gen();
for i in 0..18 {
assert_eq!(i, name.common_prefix(&name.with_flipped_bit(i)));
}
for i in 0..10 {
assert_eq!(19 * i, name.common_prefix(&name.with_flipped_bit(19 * i)));
}
assert_eq!(name, name.with_flipped_bit(XOR_NAME_BITS));
assert_eq!(name, name.with_flipped_bit(XOR_NAME_BITS + 1000));
}
#[test]
fn count_differing_bits() {
let mut rng = rand::thread_rng();
let name: XorName = rng.gen();
assert_eq!(0, name.count_differing_bits(&name));
let one_bit = name.with_flipped_bit(5);
assert_eq!(1, name.count_differing_bits(&one_bit));
let two_bits = one_bit.with_flipped_bit(100);
assert_eq!(2, name.count_differing_bits(&two_bits));
}
#[test]
fn subtraction() {
let mut rng = rand::thread_rng();
for _ in 0..100_000 {
let x = rng.gen();
let y = rng.gen();
let (larger, smaller) = if x > y { (x, y) } else { (y, x) };
assert_eq!(
&xor_from_int(larger - smaller)[..],
&(xor_from_int(larger) - xor_from_int(smaller))[..]
);
assert_eq!(XorName::default(), xor_from_int(x) - xor_from_int(x));
}
}
#[test]
#[should_panic]
fn subtraction_underflow() {
let _ = xor_from_int(1_000_001) - xor_from_int(1_000_002);
}
#[test]
fn division() {
let mut rng = rand::thread_rng();
for _ in 0..100_000 {
let x = rng.gen();
let y = rng.gen::<u32>().saturating_add(1);
assert_eq!(xor_from_int(x / u64::from(y)), xor_from_int(x) / y);
assert_eq!(xor_from_int(1), xor_from_int(u64::from(y)) / y);
}
}
#[test]
fn from_int() {
assert_eq!(
&xor_from_int(0xab_cdef)[XOR_NAME_LEN - 3..],
&[0xab, 0xcd, 0xef]
);
assert_eq!(
xor_from_int(0xab_cdef)[..XOR_NAME_LEN - 3],
XorName::default()[..XOR_NAME_LEN - 3]
);
}
fn xor_from_int(x: u64) -> XorName {
let mut name = XorName::default();
for i in 0..8 {
name.0[XOR_NAME_LEN - 1 - i] = ((x >> (8 * i)) & 0xff) as u8;
}
name
}
}