finite-fields 0.5.2

/// Specifies the dependencies and common traits required for finite field
/// types. Not used directly, since type macros use it themselves.
#[macro_export] macro_rules! field_common_deps {
  () => {
    #[macro_use] extern crate newtype_derive;
    
    use std::fmt;
    use std::cmp::Ordering;
    use std::ops::{Add, Sub, Mul, Div, BitXor, Index, IndexMut};
   
    use finite_fields::error::{DivisionError, OverflowError};

    /// Peano arithmetic operators.
    pub trait Peano where Self: Sized {
      /// Produces the next integer value in the field of self (i.e.,
      /// increment).
      fn successor(&self) -> Result<Self, OverflowError>;
      /// Produces the previous integer value in the field of self (i.e.,
      /// decrement).
      fn predecessor(&self) -> Result<Self, OverflowError>;
      /// Total ordering function.
      fn cmp (&self, other: &Self) -> Ordering;
    }
  }
}

/// Implements arithmetic on a unit binary newtype with overflow and division by
/// zero errors.
#[macro_export] macro_rules! unit_binary_arithmetic {
  () => {
    impl Peano for b1 {
      fn successor(&self) -> Result<b1, OverflowError> {
        match self {
          &ZERO => Ok(ONE),
          &ONE => Err(OverflowError::Default { arg1: self.to_string(),
                                               arg2: ONE.to_string() })
        }
      }

      /// Peano arithmetic function.
      fn predecessor(&self) -> Result<b1, OverflowError> {
        match self {
          &ONE => Ok(ZERO),
          &ZERO => Err(OverflowError::Default { arg1: self.to_string(),
                                                arg2: ONE.to_string() })
        }
      }

      /// Total ordering function.
      fn cmp (&self, other: &Self) -> Ordering {
        if &self == other { Ordering::Equal }
        else if let &Ok(next) = &self.successor() {
          if next == other { Ordering::Less }
          else { Ordering::Greater }
        }
        else { Ordering::Greater }
      }
    }

    impl PartialOrd for b1 {
      fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
      }
    }

    /// Arithmetic addition with overflow error.
    impl Add for b1 {
      type Output = Result<b1, OverflowError>;
      fn add(self, other: b1) -> Result<b1, OverflowError> {
        match other {
          ZERO => Ok(self),
          ONE => self.successor()
        }
      }
    }
    impl<'a> Add<b1> for &'a b1 {
      type Output = Result<b1, OverflowError>;
      fn add(self, other: b1) -> Result<b1, OverflowError> {
        match other {
          ZERO => Ok(*self),
          ONE => self.successor()
        }    
      }
    }
    impl<'a> Add<&'a b1> for &'a b1 {
      type Output = Result<b1, OverflowError>;
      fn add(self, other: &b1) -> Result<b1, OverflowError> {
        match other {
          &ZERO => Ok(ZERO),
          &ONE => self.successor()
        }
      }
    }

    /// Arithmetic subtraction with overflow as error.
    impl Sub for b1 {
      type Output = Result<b1, OverflowError>;
      fn sub(self, other: b1) -> Result<b1, OverflowError> {
        match other {
          ZERO => Ok(self),
          ONE => self.predecessor()
        }
      }
    }
    impl<'a> Sub<b1> for &'a b1 {
      type Output = Result<b1, OverflowError>;
      fn sub(self, other: b1) -> Result<b1, OverflowError> {
        match other {
          ZERO => Ok(*self),
          ONE => self.predecessor()
        }
      }
    }
    impl<'a> Sub<&'a b1> for &'a b1 {
      type Output = Result<b1, OverflowError>;
      fn sub(self, other: &b1) -> Result<b1, OverflowError> {
        match other {
          &ZERO => Ok(*self),
          &ONE => self.predecessor()
        }
      }
    }

    impl Mul for b1 {
      type Output = Result<Self, OverflowError>;
      fn mul(self, other: b1) -> Result<b1, OverflowError> {
        Ok(b1(self.0 && other.0))
      }
    }
    impl<'a> Mul<b1> for &'a b1 {
      type Output = Result<b1, OverflowError>;
      fn mul(self, other: b1) -> Result<b1, OverflowError> {
        Ok(b1(self.0 && other.0))
      }

    }
    impl<'a> Mul<&'a b1> for &'a b1 {
      type Output = Result<b1, OverflowError>;
      fn mul(self, other: &b1) -> Result<b1, OverflowError> {
        Ok(b1(self.0 && other.0))
      }
    }

    impl Div for b1 {
      type Output = Result<Self, DivisionError>;
      fn div(self, other: b1) -> Result<b1, DivisionError> {
        if other == ZERO {
          Err(DivisionError::DivideByZeroError {
            arg1: self.to_string()
          })
        } else { Ok(self) }
      }
    }
    impl<'a> Div<b1> for &'a b1 {
      type Output = Result<b1, DivisionError>;
      fn div(self, other: b1) -> Result<b1, DivisionError> {
        if other == ZERO {
          Err(DivisionError::DivideByZeroError {
            arg1: self.to_string()
          })
        } else { Ok(*self) }
      }

    }
    impl<'a> Div<&'a b1> for &'a b1 {
      type Output = Result<b1, DivisionError>;
      fn div(self, other: &b1) -> Result<b1, DivisionError> {
        if other == ZERO {
          Err(DivisionError::DivideByZeroError {
            arg1: self.to_string()
          })
        } else { Ok(*self) }
      }
    }
  }
}

/// A macro that defines a unit-width binary type as a newtype struct, with
/// associated arithmetic traits. Used as a building block in other macros.
#[macro_export] macro_rules! unit_binary {
  () => {
    field_common_deps! {}
    
    /// The base binary type, a unit-width binary digit.
    #[derive(Clone,Copy,Debug,PartialEq,Eq)]
    pub struct b1(bool);

    NewtypeFrom! {
      () pub struct b1(bool);
    }

    impl b1 {
      pub fn new(val: bool) -> b1 {
        b1(val)
      }
    }

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

    impl BitXor for b1 {
      type Output = Self;
      fn bitxor(self, other: b1) -> Self {
        b1(self.0 ^ other.0)
      }
    }

    /// Shorthand for zero in unit-width binary type.
    pub const ZERO: b1 = b1(false);
    /// Shorthand for one in unit-width binary type.
    pub const ONE: b1 = b1(true);

    impl<'a> PartialEq<b1> for &'a b1 {
      fn eq(&self, other: &b1) -> bool {
        self.0 == other.0
      }
    }
    impl<'a> PartialEq<&'a b1> for b1 {
      fn eq(&self, other: &&'a b1) -> bool {
        self.0 == other.0
      }
    }

    unit_binary_arithmetic! {}
  }
}

/// Implements arithmetic on a binary type, with overflow and division by zero
/// errors.
#[macro_export] macro_rules! binary_type_arithmetic {
  ($tyname:ident, $fieldwidth:expr) => {
    /// Arithmetic addition with overflow error.
    impl Add for $tyname {
      type Output = Result<Self, OverflowError>;

      fn add(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut carry = false;
        
        for place in (0..other.0.len()).rev() {
          // Handle the carry flag first if true
          let augend = match carry {
            false => self.0[place].clone(),
            true => match self.0[place].successor() {
              Ok(res) => {
                res.clone()
              },
              Err(_) => {
                ZERO
              }
            }
          };

          // Do the addition
          match augend + other.0[place] {
            Ok(res) => {
              output.0[place] = res;
              carry = false;
            }
            Err(_) => {
              output.0[place] = ZERO;
              carry = true
            }
          }
        }

        if carry {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok(output)
        }
      }
    }
    impl<'a> Add<$tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;

      fn add(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut carry = false;
        
        for place in (0..other.0.len()).rev() {
          // Handle the carry flag first if true
          let augend = match carry {
            false => self.0[place].clone(),
            true => match self.0[place].successor() {
              Ok(res) => {
                res.clone()
              },
              Err(_) => {
                ZERO
              }
            }
          };

          // Do the addition
          match augend + other.0[place] {
            Ok(res) => {
              output.0[place] = res;
              carry = false;
            }
            Err(_) => {
              output.0[place] = ZERO;
              carry = true
            }
          }
        }

        if carry {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok(output)
        }
      }
    }
    impl<'a> Add<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;

      fn add(self, other: &$tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut carry = false;
        
        for place in (0..other.0.len()).rev() {
          // Handle the carry flag first if true
          let augend = match carry {
            false => self.0[place].clone(),
            true => match self.0[place].successor() {
              Ok(res) => {
                res.clone()
              },
              Err(_) => {
                ZERO
              }
            }
          };

          // Do the addition
          match augend + other.0[place] {
            Ok(res) => {
              output.0[place] = res;
              carry = false;
            }
            Err(_) => {
              output.0[place] = ZERO;
              carry = true
            }
          }
        }

        if carry {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok(output)
        }
      }
    }

    /// Arithmetic subtraction with overflow error.
    impl Sub for $tyname {
      type Output = Result<$tyname, OverflowError>;

      fn sub(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut carry = false;
        
        for place in (0..other.0.len()).rev() {
          // Handle the carry flag first if true
          let augend = match carry {
            false => self.0[place],
            true => match self.0[place].predecessor() {
              Ok(res) => {
                res
              },
              Err(_) => {
                ZERO
              }
            }
          };

          // Do the addition
          match augend - other.0[place] {
            Ok(res) => {
              output.0[place] = res;
              carry = false;
            }
            Err(_) => {
              output.0[place] = ONE;
              carry = true
            }
          }
        }

        if carry {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok(output)
        }
      }
    }
    impl<'a> Sub<$tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;

      fn sub(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut carry = false;
        
        for place in (0..other.0.len()).rev() {
          // Handle the carry flag first if true
          let augend = match carry {
            false => self.0[place],
            true => match self.0[place].predecessor() {
              Ok(res) => {
                res
              },
              Err(_) => {
                ZERO
              }
            }
          };

          // Do the addition
          match augend - other.0[place] {
            Ok(res) => {
              output.0[place] = res;
              carry = false;
            }
            Err(_) => {
              output.0[place] = ONE;
              carry = true
            }
          }
        }

        if carry {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok(output)
        }
      }
    }
    impl<'a> Sub<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;

      fn sub(self, other: &$tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut carry = false;
        
        for place in (0..other.0.len()).rev() {
          // Handle the carry flag first if true
          let augend = match carry {
            false => self.0[place],
            true => match self.0[place].predecessor() {
              Ok(res) => {
                res
              },
              Err(_) => {
                ZERO
              }
            }
          };

          // Do the addition
          match augend - other.0[place] {
            Ok(res) => {
              output.0[place] = res;
              carry = false;
            }
            Err(_) => {
              output.0[place] = ONE;
              carry = true
            }
          }
        }

        if carry {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok(output)
        }
      }
    }
    

    /// This implementation is done "in reverse" of the expected logical order;
    /// it uses the `Add` and `Sub` impls instead of the converse.
    impl Peano for $tyname {
      fn successor(&self) -> Result<$tyname, OverflowError> {
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        self + one
      }

      /// Peano arithmetic function.
      fn predecessor(&self) -> Result<$tyname, OverflowError> {
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        self - one
      }

      /// Total ordering function.
      fn cmp (&self, other: &Self) -> Ordering {
        if *self == *other { Ordering::Equal }
        else {
          match *self - *other {
            Ok(_) => Ordering::Greater,
            Err(_) => Ordering::Less
          }
        }
      }
    }

    impl PartialOrd for $tyname {
      fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
      }
    }

    impl BitXor for $tyname {
      type Output = Self;
      fn bitxor(self, other: $tyname) -> Self {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] ^ other.0[place]
        }
        output
      }
    }

    /// Bit shifting.
    pub trait Shift {
      /// Shifts the bit vector once to the right, padding with zero on the left
      /// and discarding on the right.
      fn shift_right(&self) -> Self;
      /// Shifts the bit vector once to the left, padding with zero on the right
      /// and discarding on the left.
      fn shift_left(&self) -> Self;
    }

    impl Shift for $tyname {
      // Thanks to Mustabah on #rust for clarifying how this needed to work
      fn shift_right(&self) -> Self {
        let concated_slices = [&[ZERO],
                               &self.0[0..($fieldwidth-1)]].concat();
        let mut dest_arr = [ZERO; $fieldwidth];
        dest_arr.clone_from_slice(concated_slices.as_slice());
        $tyname(dest_arr)
      }
      fn shift_left(&self) -> Self {
        let concated_slices = [&self.0[1..$fieldwidth],
                               &[ZERO]].concat();
        let mut dest_arr = [ZERO; $fieldwidth];
        dest_arr.clone_from_slice(concated_slices.as_slice());
        $tyname(dest_arr)
      }
    }

    /// Multiplication as repeated addition.
    impl Mul for $tyname {
      type Output = Result<$tyname, OverflowError>;
      
      fn mul(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut mult_rhs = other.clone();
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        
        let zero = $tyname([ZERO; $fieldwidth]);
        
        while mult_rhs > zero {
          if let Ok(sum) = output + self {
            output = sum
          } else {
            // overflow case
            return Err(OverflowError::Default { arg1: self.to_string(),
                                                arg2: other.to_string() })
          }
          // TODO check this for erroneous assumptions
          mult_rhs = (mult_rhs - one).unwrap();
        }
        
        Ok(output)
      }
    }
    impl<'a> Mul<$tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      
      fn mul(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut mult_rhs = other.clone();
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        
        let zero = $tyname([ZERO; $fieldwidth]);
        
        while mult_rhs > zero {
          if let Ok(sum) = output + *self {
            output = sum
          } else {
            // overflow case
            return Err(OverflowError::Default { arg1: self.to_string(),
                                                arg2: other.to_string() })
          }
          // TODO check this for erroneous assumptions
          mult_rhs = (mult_rhs - one).unwrap();
        }
        
        Ok(output)
      }
    }
    impl<'a> Mul<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      
      fn mul(self, other: &$tyname) -> Result<$tyname, OverflowError> {
        let mut output = $tyname([ZERO; $fieldwidth]);
        let mut mult_rhs = other.clone();
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        
        let zero = $tyname([ZERO; $fieldwidth]);
        
        while mult_rhs > zero {
          if let Ok(sum) = output + *self {
            output = sum
          } else {
            // overflow case
            return Err(OverflowError::Default { arg1: self.to_string(),
                                                arg2: other.to_string() })
          }
          // TODO check this for erroneous assumptions
          mult_rhs = (mult_rhs - one).unwrap();
        }
        
        Ok(output)
      }
    }
    

    /// Implementation of division as repeated subtraction.
    impl Div for $tyname {
      type Output = Result<$tyname, DivisionError>;
      
      fn div(self, other: $tyname) -> Result<$tyname, DivisionError> {
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        let zero = $tyname([ZERO; $fieldwidth]);

        if other == zero {
          return Err(DivisionError::DivideByZeroError { arg1: self.to_string() })
        } else if self < other {
          // division is guaranteed to overflow in this case
          return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                    arg2: other.to_string() })
        }
        
        let mut div_lhs = other.clone();
        let mut sub_count = zero;
        
        while div_lhs > other {
          if let Ok(difference) = div_lhs - other {
            div_lhs = difference;
            if let Ok(sum) = sub_count + one {
              sub_count = sum;
            } else {
              return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                        arg2: other.to_string() })
            }
          } else {
            break;
          }
        }

        Ok(sub_count)
      }
    }
    impl<'a> Div<$tyname> for &'a $tyname {
      type Output = Result<$tyname, DivisionError>;
      
      fn div(self, other: $tyname) -> Result<$tyname, DivisionError> {
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        let zero = $tyname([ZERO; $fieldwidth]);

        if other == zero {
          return Err(DivisionError::DivideByZeroError { arg1: self.to_string() })
        } else if self < &other {
          // division is guaranteed to overflow in this case
          return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                    arg2: other.to_string() })
        }
        
        let mut div_lhs = other.clone();
        let mut sub_count = zero;
        
        while div_lhs > other {
          if let Ok(difference) = div_lhs - other {
            div_lhs = difference;
            if let Ok(sum) = sub_count + one {
              sub_count = sum;
            } else {
              return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                        arg2: other.to_string() })
            }
          } else {
            break;
          }
        }

        Ok(sub_count)
      }
    }
    impl<'a> Div<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, DivisionError>;
      
      fn div(self, other: &$tyname) -> Result<$tyname, DivisionError> {
        // TODO make these static
        let mut one: $tyname = $tyname([ZERO; $fieldwidth]);
        one[$fieldwidth - 1] = ONE;
        let zero = $tyname([ZERO; $fieldwidth]);

        if *other == zero {
          return Err(DivisionError::DivideByZeroError { arg1: self.to_string() })
        } else if self < other {
          // division is guaranteed to overflow in this case
          return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                    arg2: other.to_string() })
        }
        
        let mut div_lhs = other.clone();
        let mut sub_count = zero;
        
        while div_lhs > *other {
          if let Ok(difference) = div_lhs - *other {
            div_lhs = difference;
            if let Ok(sum) = sub_count + one {
              sub_count = sum;
            } else {
              return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                        arg2: other.to_string() })
            }
          } else {
            break;
          }
        }

        Ok(sub_count)
      }
    }
  }
}

/// A macro that defines a binary field type.
///
/// The first argument is the desired type name, and the second the field width
/// (e.g, `2` for two-digit binary numbers). The second argument should be
/// integral.
///
/// The result will be a newtype struct and associated arithmetic
/// implementations.
#[macro_export] macro_rules! binary_type {
  ($tyname:ident, $fieldwidth:expr) => {
    unit_binary! {}
    
    /// A binary number ($fieldwidth digits).
    #[derive(Clone, Copy, PartialEq)]
    pub struct $tyname([b1; $fieldwidth]);

    impl $tyname {
      pub fn new(vals: [b1; $fieldwidth]) -> $tyname {
        $tyname(vals)
      }
    }

    impl fmt::Display for $tyname {
      fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // TODO improve this to recursively concatenate the digits
        write!(f, "{:?}", self.0)
      }
    }

    impl<'a> Index<usize> for $tyname {
      type Output = b1;

      fn index<'b>(&'b self, idx: usize) -> &'b b1 {
        &self.0[idx]
      }
    }

    impl IndexMut<usize> for $tyname {
      fn index_mut<'a>(&'a mut self, index: usize) -> &'a mut b1 {
        &mut self.0[index]
      }
    }

    binary_type_arithmetic! { $tyname, $fieldwidth }
  }
}