bloock_types/

traits.rs

use crate::error::TypeError;
use std::cmp;
use std::cmp::Ordering;
use rand::Rng;


/// Trait that manages bitwise comparison operations on the implemented type.
///
/// # How can I implement Bitwise?
/// Bitwise requieres the methods get_bit, cmp_bits and get_first_different_bit
/// to be implemented.
/// ```
/// use std::cmp;
/// use std::cmp::Ordering;
///
/// pub trait Bitwise {
///     fn get_bit(&self, bit: u16) -> bool;
///     fn cmp_bits(a: &[u8], b: &[u8], from: &u16, to: &u16) -> Ordering;
///     fn get_first_different_bit(a: &[u8], b: &[u8]) -> usize;
/// }
/// impl Bitwise for [u8] {
///     fn get_bit(&self, bit: u16) -> bool {
///         if (bit / 8) >= self.len() as u16 {
///             panic!(
///                 "Overflow [get_bit({:?}, {:?})]: Bit must be lower than {:?}.",
///                 self,
///                 bit,
///                 self.len() * 8
///             );
///         }
///         (self[bit as usize / 8] & (1 << (7 - (bit % 8)))) > 0
///     }
///
///     fn cmp_bits(a: &[u8], b: &[u8], from: &u16, to: &u16) -> Ordering {
///         for depth in *from..*to {
///             if b.get_bit(depth) && !a.get_bit(depth) {
///                 return Ordering::Less;
///             } else if !b.get_bit(depth) && a.get_bit(depth) {
///                 return Ordering::Greater;
///             }
///         }
///         return Ordering::Equal;
///     }
///
///     fn get_first_different_bit(a: &[u8], b: &[u8]) -> usize {
///         let n = cmp::min(a.len(), b.len());
///         let mut bit: usize = 0;
///
///         for i in 0..n {
///             if a[i] != b[i] {
///                 let xor = a[i] ^ b[i];
///                 let lg_xor = 8 - xor.leading_zeros() - 1; // nbits - leading_zeros - 1 is equivalent to lg
///                 bit += 7 - (lg_xor as usize);
///                 return bit;
///             }
///             bit += 8;
///         }
///         bit
///     }
/// }
/// ```
pub trait Bitwise {
    type Error;
    /// Returns the bit at position `bit`.
    ///
    /// # Arguments
    /// * `self` - The object we want to read from
    /// * `bit` - An u16 representing the bit position to be read, being 0 the
    /// the value of the highest bit in the first byte.
    ///
    /// # Panics
    /// * If the `bit` value is higher than the object lenght.
    ///
    fn get_bit(&self, bit: u16) -> Result<bool, Self::Error>;

    /// Returns the and Ordering indicating wether `self` bits in the interval [`from`, `to`) is Higher, Lower or Equal than `slice` bits in the same interval.
    ///
    /// # Arguments
    /// * `a` - The object that's going to be compared.
    /// * `b` - The object that's going to be compare against.
    /// * `from` - The index of the first bit to be compared (inclusive).
    /// * `to`- The index of the last bit to be compared (exclusive).
    ///
    /// # Panics
    /// * If the `from` value is higher than the object length or than `to`.
    /// * If the `to` value is higher than the object length or lower than `from`.
    fn cmp_bits(a: &[u8], b: &[u8], from: &u16, to: &u16) -> Result<Ordering, Self::Error>;

    /// Returns the index of the first different bit between `a` and `slice`.
    ///
    /// # Arguments
    /// * `a` - The object that's going to be compared.
    /// * `b` - The object that's going to be compare against.
    fn get_first_different_bit(a: &[u8], b: &[u8]) -> usize;
}

/// Trait that manages the object creation for the implemented type with random values.
pub trait Random {
    /// Returns an object of the implemented type filled with random values.
    fn random() -> Self;
}

impl Bitwise for [u8] {
    type Error = TypeError;
    fn get_bit(&self, bit: u16) -> Result<bool, Self::Error> {
        if (bit / 8) >= self.len() as u16 {
            return Err(TypeError::BitOverflow {
                key: format!("{:?}", self),
                bit,
                maxbit: self.len() * 8usize,
            });
        }
        Ok((self[bit as usize / 8] & (1 << (7 - (bit % 8)))) > 0)
    }

    fn cmp_bits(a: &[u8], b: &[u8], from: &u16, to: &u16) -> Result<Ordering, Self::Error> {
        // s'ha de poder fer més eficient
        for depth in *from..*to {
            if b.get_bit(depth)? && !a.get_bit(depth)? {
                return Ok(Ordering::Less);
            } else if !b.get_bit(depth)? && a.get_bit(depth)? {
                return Ok(Ordering::Greater);
            }
        }
        Ok(Ordering::Equal)
    }

    fn get_first_different_bit(a: &[u8], b: &[u8]) -> usize {
        let n = cmp::min(a.len(), b.len());
        let mut bit: usize = 0;

        for i in 0..n {
            if a[i] != b[i] {
                let xor = a[i] ^ b[i];
                let lg_xor = 8 - xor.leading_zeros() - 1; // nbits - leading_zeros - 1 is equivalent to lg
                bit += 7 - (lg_xor as usize);
                return bit;
            }
            bit += 8;
        }
        bit
    }
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_first_different_bit_first_byte_first_bit() {
        let a: [u8; 1] = [128];
        let b: [u8; 1] = [64];
        assert_eq!(0, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_first_different_bit_first_byte_last_bit() {
        let a: [u8; 1] = [128];
        let b: [u8; 1] = [129];
        assert_eq!(7, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_first_different_bit_second_byte_first_bit() {
        let a: [u8; 2] = [0, 128];
        let b: [u8; 2] = [0, 64];
        assert_eq!(8, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_first_different_bit_second_byte_last_bit() {
        let a: [u8; 2] = [0, 128];
        let b: [u8; 2] = [0, 129];
        assert_eq!(15, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_first_different_bit_different_lenghts() {
        let a: [u8; 1] = [0];
        let b: [u8; 2] = [0, 129];
        assert_eq!(8, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_first_different_bit_multiple_different_bytes() {
        let a: [u8; 3] = [0, 128, 1];
        let b: [u8; 3] = [0, 129, 255];
        assert_eq!(15, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_first_different_bit_distant_difference() {
        let a: [u8; 32] = [
            1, 4, 255, 4, 183, 75, 225, 169, 26, 216, 79, 149, 29, 195, 120, 173, 46, 167, 91, 31,
            187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226, 120,
        ];
        let b: [u8; 32] = [
            1, 4, 255, 4, 183, 75, 225, 169, 26, 216, 79, 149, 29, 195, 120, 173, 46, 167, 91, 31,
            187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226, 121,
        ];
        assert_eq!(255, <[u8]>::get_first_different_bit(&a[..], &b[..]));
    }

    #[test]
    fn test_get_bit_error() {
        let a: [u8; 1] = [8u8];
        assert_eq!(
            a.get_bit(8).err().unwrap(),
            TypeError::BitOverflow {
                key: format!("{:?}", [8u8]),
                bit: 8,
                maxbit: 8
            },
            "Error types differ"
        );
    }
}