finite-fields 0.10.3

/// 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;

    #[cfg(feature = "nightly")]
    use std::convert::TryFrom;
    #[cfg(feature = "nightly")]
    use finite_fields::error::ConversionError;
    
    use finite_fields::error::{DivisionError, OverflowError};    
    
    use std::cmp::Ordering;
    use std::iter::{FromIterator, IntoIterator, Iterator};
    use std::ops::{Add, Sub, Mul, Div, BitAnd, BitOr, BitXor, Index, IndexMut, Shl, Shr};    

    /// 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)
      }

      /// Reports the maximum unsigned integer expressible in this type.
      pub fn max(&self) -> usize {
        1
      }
    }

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

    #[cfg(feature = "nightly")]
    /// Fallible conversion by simple exhaustive matching.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    /// use std::convert::TryInto;
    ///
    /// unit_binary! {}
    ///
    /// fn main() {
    ///   let zero: b1 = (0 as usize).try_into().unwrap();
    ///   assert_eq!(zero, b1::new(false));
    ///   
    ///   let one: b1 = (1 as usize).try_into().unwrap();
    ///   assert_eq!(one, b1::new(true));
    /// }
    /// ```
    impl TryFrom<usize> for b1 {
      type Err = ConversionError;

      fn try_from(val: usize) -> Result<Self, Self::Err> {
        match val {
          0 => Ok(ZERO),
          1 => Ok(ONE),
          _ => Err(ConversionError::OverflowError { arg1: val.to_string() })
        }
      }
    }

    impl From<b1> for usize {
      fn from(val: b1) -> usize {
        match val {
          ZERO => 0,
          ONE => 1
        }
      }
    }

    impl BitAnd for b1 {
      type Output = Self;
      fn bitand(self, other: b1) -> Self {
        b1(self.0 & other.0)
      }
    }

    impl BitOr for b1 {
      type Output = Self;
      fn bitor(self, other: b1) -> Self {
        b1(self.0 | other.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 BitAnd for $tyname {
      type Output = Self;
      fn bitand(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
      }
    }
    impl<'a> BitAnd<$tyname> for &'a $tyname {
      type Output = $tyname;
      fn bitand(self, other: $tyname) -> $tyname {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] & other.0[place]
        }
        output
      }
    }
    impl<'a> BitAnd<&'a $tyname> for &'a $tyname {
      type Output = $tyname;
      fn bitand(self, other: &$tyname) -> $tyname {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] & other.0[place]
        }
        output
      }
    }

    impl BitOr for $tyname {
      type Output = Self;
      fn bitor(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
      }
    }
    impl<'a> BitOr<$tyname> for &'a $tyname {
      type Output = $tyname;
      fn bitor(self, other: $tyname) -> $tyname {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] | other.0[place]
        }
        output
      }
    }
    impl<'a> BitOr<&'a $tyname> for &'a $tyname {
      type Output = $tyname;
      fn bitor(self, other: &$tyname) -> $tyname {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] | other.0[place]
        }
        output
      }
    }

    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
      }
    }
    impl<'a> BitXor<$tyname> for &'a $tyname {
      type Output = $tyname;
      fn bitxor(self, other: $tyname) -> $tyname {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] ^ other.0[place]
        }
        output
      }
    }
    impl<'a> BitXor<&'a $tyname> for &'a $tyname {
      type Output = $tyname;
      fn bitxor(self, other: &$tyname) -> $tyname {
        let mut output = $tyname([ZERO; $fieldwidth]);
        for place in (0..other.0.len()).rev() {
          output.0[place] = self.0[place] ^ other.0[place]
        }
        output
      }
    }

    impl Shr<usize> for $tyname {
      type Output = Self;      
      fn shr(self, rhs: usize) -> Self {
        let mut dest_arr = [ZERO; $fieldwidth];
        for dest_ind in 0..dest_arr.len() {
          if dest_ind < rhs {
            dest_arr[dest_ind] = ZERO;
          } else {
            dest_arr[dest_ind] = self.0[dest_ind - rhs];
          }
        }
        $tyname(dest_arr)
      }
    }
    impl Shl<usize> for $tyname {
      type Output = Self;
      fn shl(self, rhs: usize) -> Self {
        let mut dest_arr = [ZERO; $fieldwidth];
        for dest_ind in 0..dest_arr.len() {
          if dest_ind < rhs {
            dest_arr[dest_ind] = self.0[dest_ind + rhs];
          } else {
            dest_arr[dest_ind] = ZERO;
          }
        }
        $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, Debug)]
    pub struct $tyname([b1; $fieldwidth]);

    impl $tyname {
      /// Array-based constructor.
      pub fn new(vals: [b1; $fieldwidth]) -> $tyname {
        $tyname(vals)
      }

      /// Reports the maximum unsigned integer expressible in this type.
      ///
      /// # Examples
      ///
      /// ```
      /// #![feature(try_from)]
      /// #[macro_use] extern crate finite_fields;
      ///
      /// binary_type! { b2, 2 }
      ///
      /// fn main() {
      ///   let num: b2 = b2::new([ZERO; 2]);
      ///   assert_eq!(num.max(), (2 as usize).pow(2) - 1);
      /// }
      /// ```
      pub fn max(&self) -> usize {
        (2 as usize).pow($fieldwidth) - 1
      }
      
      /// Reports the number of digits in this type.
      pub fn len(&self) -> usize {
        $fieldwidth
      }
      
      pub fn iter(self) -> Iter {
        Iter { data: self, index: 0, end: self.len() }
      }

      /// Copies out the internal data as a fixed-width array.
      pub fn bits(&self) -> [b1; $fieldwidth] {
        self.0
      }

      /// Shifts the leftmost digit off and pushes a new digit onto the
      /// right. Returns a modified copy.
      pub fn shift_concat(&self, val: b1) -> $tyname {
        let mut shifted_bin = *self << 1;
        shifted_bin[self.len() - 1] = val;
        shifted_bin
      }

      /// Pops the rightmost digit off and unshifts a new digit onto the
      /// left. Returns a modified copy.
      pub fn unshift_concat(&self, val: b1) -> $tyname {
        let mut unshifted_bin = *self >> 1;
        unshifted_bin[0] = val;
        unshifted_bin
      }
    }

    impl fmt::Display for $tyname {
      fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut bit_string = String::with_capacity(self.len());
        for bit in self.bits().iter() { bit_string.push_str(&bit.to_string()); }
        write!(f, "{}", bit_string)
      }
    }

    #[cfg(feature = "nightly")]
    /// Fallible conversion by successive division.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    /// use std::convert::TryInto;
    ///
    /// binary_type! { b2, 2 }
    ///
    /// fn main() {
    ///   let zero: b2 = (0 as usize).try_into().unwrap();
    ///   assert_eq!(zero, b2::new([ZERO, ZERO]));
    ///   
    ///   let one: b2 = (1 as usize).try_into().unwrap();
    ///   assert_eq!(one, b2::new([ZERO, ONE]));
    ///   
    ///   let two: b2 = (2 as usize).try_into().unwrap();
    ///   assert_eq!(two, b2::new([ONE, ZERO]));
    ///   
    ///   let three: b2 = (3 as usize).try_into().unwrap();
    ///   assert_eq!(three, b2::new([ONE, ONE]));
    ///   
    ///   let four = b2::try_from(4 as usize);
    ///   assert!(four.is_err());
    /// }
    /// ```
    impl TryFrom<usize> for $tyname {
      type Err = ConversionError;

      fn try_from(val: usize) -> Result<Self, Self::Err> {
        let mut out_val = $tyname::new([ZERO; $fieldwidth]);

        if val > out_val.max() {
          Err(ConversionError::OverflowError { arg1: val.to_string() })
        } else if val == 0 {
          Ok(out_val)
        } else {
          let mut dec = val.clone();
          if dec % 2 != 0 {
            out_val[$fieldwidth - 1] = ONE;
          }
          
          for place in 0..$fieldwidth {
            if dec > 1 {
              dec = dec / 2;
              out_val[place] = ONE;
            } else {
              break;          
            }
            // TODO figure out if this is ever necessary
            //
            // return Err(
            //   ConversionError::PrecisionError {
            //     arg1: val.to_string(),
            //     tgt_width: out_val_len.to_string()
            //   })
          }
          
          Ok(out_val)
        }
      }
    }

    /// Fallible conversion by successive division, but pretends like it's not
    /// since TryFrom is still unstable.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// binary_type! { b2, 2 }
    ///
    /// fn main() {
    ///   let zero: b2 = (0 as usize).into();
    ///   assert_eq!(zero, b2::new([ZERO, ZERO]));
    ///   
    ///   let one: b2 = (1 as usize).into();
    ///   assert_eq!(one, b2::new([ZERO, ONE]));
    ///   
    ///   let two: b2 = (2 as usize).into();
    ///   assert_eq!(two, b2::new([ONE, ZERO]));
    ///   
    ///   let three: b2 = (3 as usize).into();
    ///   assert_eq!(three, b2::new([ONE, ONE]));
    /// }
    /// ```
    ///
    /// # Panics
    ///
    /// Panics if the argument is larger than what b2 can hold.
    ///
    /// ```should_panic
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// binary_type! { b2, 2 }
    ///
    /// fn main() {
    ///   let four = b2::from(4 as usize);
    /// }
    /// ```
    impl From<usize> for $tyname {
      fn from(val: usize) -> Self {
        let mut out_val = $tyname::new([ZERO; $fieldwidth]);
        
        if val > out_val.max() {
          panic!("Can't convert {} to $tyname, it's too big.", val);
        } else if val == 0 {
          out_val
        } else {
          let mut dec = val.clone();
          if dec % 2 != 0 {
            out_val[$fieldwidth - 1] = ONE;
          }
          
          for place in 0..$fieldwidth {
            if dec > 1 {
              dec = dec / 2;
              out_val[place] = ONE;
            } else {
              break;          
            }      
          }
          
          out_val
        }
      }
    }

    #[cfg(feature = "nightly")]
    /// Fallible conversion by length-checked read through a slice reference.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    /// use std::convert::TryInto;
    ///
    /// binary_type! { b3, 3 }
    ///
    /// fn main() {
    ///   let mut zero_arr = [ZERO; 3];
    ///   let mut one_arr = zero_arr.clone();
    ///   one_arr[3 - 1] = ONE;
    ///   
    ///   let zero = b3::new([ZERO; 3]);
    ///   // TODO make these static
    ///   let mut one: b3 = b3([ZERO; 3]);
    ///   one[3 - 1] = ONE;
    ///   
    ///   assert_eq!(zero, (&zero_arr[0..]).try_into().unwrap());
    ///   assert_eq!(one, (&one_arr[0..]).try_into().unwrap());
    ///   
    ///   let bad_arr = [ZERO; 3 + 1];
    ///   assert!(b3::try_from(&bad_arr[0..]).is_err());
    /// }
    /// ```
    impl<'a> TryFrom <&'a [b1]> for $tyname {
      type Err = ConversionError;

      fn try_from(val: &[b1]) -> Result<Self, Self::Err> {
        if val.len() != $fieldwidth {
          Err(ConversionError::LengthError { arg1: val.len() })
        } else {
          let mut out_val = $tyname::new([ZERO; $fieldwidth]);
          for place in 0..out_val.len() {
            out_val[place] = val[place];
          }
          Ok(out_val)
        }
      }
    }

    /// Implements the conversion by converting the bits to `usize` and then
    /// summing.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// binary_type! { b2, 2 }
    ///
    /// fn main() {
    ///   let one: usize = b2::new([ZERO, ONE]).into();
    ///   assert_eq!(one, 1);
    /// }
    /// ```
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// binary_type! { b2, 2 }
    ///
    /// fn main() {
    ///   let three: usize = b2::new([ONE, ONE]).into();
    ///   assert_eq!(three, 3);
    /// }
    /// ```
    impl From<$tyname> for usize {
      fn from(val: $tyname) -> usize {
        val.bits().iter()
              .rev()
              .enumerate()
              .fold(0, |accum, (place_ind, &bit)| {
                usize::from(bit) *
                  (2 as usize).pow((place_ind) as u32) + accum
              })
      }
    }

    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]
      }
    }

    /// An iterator along the digits of $tyname.
    pub struct Iter {
      data: $tyname,
      index: usize,
      end: usize
    }

    impl Iterator for Iter {
      type Item = b1;

      // next() is the only required method
      fn next(&mut self) -> Option<b1> {
        self.index += 1;

        // check to see if we've finished counting or not.
        if self.index < $fieldwidth {
          Some(self.data.0[self.index])
        } else {
          None
        }
      }
    }

    impl DoubleEndedIterator for Iter {
      fn next_back(&mut self) -> Option<Self::Item> {
        if self.end > 0 {
          self.end -= 1;
          // Compare backwards against the forward index.
          if self.end >= self.index {
            Some(self.data.0[self.end])
          } else {
            None
          }
        } else {
          None
        }
      }
    }    

    impl IntoIterator for $tyname {
      type Item = b1;
      type IntoIter = ::std::vec::IntoIter<b1>;

      fn into_iter(self) -> Self::IntoIter {
        self.0.to_vec().into_iter()
      }
    }
    
    impl<'a> IntoIterator for &'a $tyname {
      type Item = &'a b1;
      type IntoIter = ::std::slice::Iter<'a,b1>;

      fn into_iter(self) -> Self::IntoIter {
        self.0.into_iter()
      }
    }

    impl FromIterator<b1> for $tyname {
      fn from_iter<I: IntoIterator<Item=b1>>(iter: I) -> Self {
        let mut collector = $tyname::new([ZERO; $fieldwidth]);
        
        for (ind, val) in (0..collector.len()).zip(iter) {
          collector[ind] = val;
        }
        
        collector
      }
    }

    binary_type_arithmetic! { $tyname, $fieldwidth }
  }
}