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! nary_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 n-ary newtype with overflow and division by
/// zero errors.
///
/// There are three arguments: `$tyname`, `$arity` and `$storsize`. `$tyname` is
/// just the name of the resulting type. `$arity` defines the arity of the type
/// (e.g. `2` for binary), while `$storsize` defines the storage type used to
/// store the digit, since that is the underlying vocabulary Rust allows us to
/// work with. So it must be a valid numeric type large enough to store the
/// arity, and one that implements basic arithmetic (e.g., `u8`, `u16`).
#[macro_export] macro_rules! unit_nary_arithmetic {
  ($tyname:ident, $arity:expr, $storsize:ident) => {
    impl Peano for $tyname {
      fn successor(&self) -> Result<$tyname, OverflowError> {
        if self == &$tyname(($arity - 1) as $storsize) {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: ONE.to_string() })
        } else {
          Ok($tyname(self.0 + (1 as $storsize)))
        }
      }

      /// Peano arithmetic functions.
      fn predecessor(&self) -> Result<$tyname, OverflowError> {
        if self == &$tyname(0 as $storsize) {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: ONE.to_string() })
        } else {
          Ok($tyname(self.0 - (1 as $storsize)))
        }
      }

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

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

    /// Arithmetic addition with overflow error.
    impl Add for $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn add(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let sum = self.0 + other.0;
        if sum > $arity - 1 {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok($tyname(sum as $storsize))
        }
      }
    }
    impl<'a> Add<$tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn add(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let sum = self.0 + other.0;
        if sum > $arity - 1 {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok($tyname(sum as $storsize))
        }
      }
    }
    impl<'a> Add<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn add(self, other: &$tyname) -> Result<$tyname, OverflowError> {
        let sum = self.0 + other.0;
        if sum > $arity - 1 {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          Ok($tyname(sum as $storsize))
        }
      }
    }

    /// Arithmetic subtraction with overflow as error.
    impl Sub for $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn sub(self, other: $tyname) -> Result<$tyname, OverflowError> {
        if self.0 < other.0 {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          let diff = self.0 - other.0;
          Ok($tyname(diff as $storsize))
        }
      }
    }
    impl<'a> Sub<$tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn sub(self, other: $tyname) -> Result<$tyname, OverflowError> {
        if self.0 < other.0 {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          let diff = self.0 - other.0;
          Ok($tyname(diff as $storsize))
        }
      }
    }
    impl<'a> Sub<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn sub(self, other: &$tyname) -> Result<$tyname, OverflowError> {
        if self.0 < other.0 {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        } else {
          let diff = self.0 - other.0;
          Ok($tyname(diff as $storsize))
        }
      }
    }

    impl Mul for $tyname {
      type Output = Result<Self, OverflowError>;
      fn mul(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let prod = self.0 * other.0;
        if prod < $arity - 1 {
          Ok($tyname(prod as $storsize))
        } else {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        }
      }
    }
    impl<'a> Mul<$tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn mul(self, other: $tyname) -> Result<$tyname, OverflowError> {
        let prod = self.0 * other.0;
        if prod < $arity - 1 {
          Ok($tyname(prod as $storsize))
        } else {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        }
      }
    
    }
    impl<'a> Mul<&'a $tyname> for &'a $tyname {
      type Output = Result<$tyname, OverflowError>;
      fn mul(self, other: &$tyname) -> Result<$tyname, OverflowError> {
        let prod = self.0 * other.0;
        if prod < $arity - 1 {
          Ok($tyname(prod as $storsize))
        } else {
          Err(OverflowError::Default { arg1: self.to_string(),
                                       arg2: other.to_string() })
        }
      }
    }

    /// Implementation of division as repeated subtraction.
    impl Div for $tyname {
      type Output = Result<$tyname, DivisionError>;
      fn div(self, other: $tyname) -> Result<$tyname, DivisionError> {
        if other == ZERO {
          Err(DivisionError::DivideByZeroError {
            arg1: self.to_string()
          })
        } else if self < other {
          // division is guaranteed to overflow in this case
          Err(DivisionError::OverflowError { arg1: self.to_string(),
                                             arg2: other.to_string() })
        } else {
          // TODO make these static
          let one: $tyname = ONE;
          let mut sub_count: $tyname = ZERO;
          
          let mut div_lhs = other.clone();
          
          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> {
        if other == ZERO {
          Err(DivisionError::DivideByZeroError {
            arg1: self.to_string()
          })
        } else if self < &other {
          // division is guaranteed to overflow in this case
          Err(DivisionError::OverflowError { arg1: self.to_string(),
                                             arg2: other.to_string() })
        } else {
          // TODO make these static
          let one: $tyname = ONE;
          let mut sub_count: $tyname = ZERO;
          
          let mut div_lhs = other.clone();
          
          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> {
        if *other == ZERO {
          Err(DivisionError::DivideByZeroError {
            arg1: self.to_string()
          })
        } else if self < &other {
          // division is guaranteed to overflow in this case
          Err(DivisionError::OverflowError { arg1: self.to_string(),
                                             arg2: other.to_string() })
        } else {
          // TODO make these static
          let one: $tyname = ONE;
          let mut sub_count: $tyname = ZERO;
          
          let mut div_lhs = other.clone();
          
          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 unit-width n-ary type as a newtype struct, with
/// associated arithmetic traits. Used as a building block in other macros.
///
/// There are three arguments: `$tyname`, `$arity` and `$storsize`. `$tyname` is
/// just the name of the resulting type. `$arity` defines the arity of the type
/// (e.g. `2` for binary), while `$storsize` defines the storage type used to
/// store the digit, since that is the underlying vocabulary Rust allows us to
/// work with. So it must be a valid numeric type large enough to store the
/// arity, and one that implements basic arithmetic (e.g., `u8`, `u16`).
#[macro_export] macro_rules! unit_nary {
  ($tyname:ident, $arity:expr, $storsize:ident) => {
    nary_field_common_deps! {}
    
    /// The base n-ary type, a unit-width n-ary digit.
    #[derive(Clone,Copy,Debug,PartialEq,Eq)]
    pub struct $tyname($storsize);

    NewtypeFrom! {
      () pub struct $tyname($storsize);
    }

    impl $tyname {
      pub fn new(val: $storsize) -> $tyname {
        $tyname(val)
      }
    }

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

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

    /// Shorthand for zero in unit-width n-ary type.
    pub const ZERO: $tyname = $tyname(0 as $storsize);
    /// Shorthand for one in unit-width n-ary type.
    pub const ONE: $tyname = $tyname(1 as $storsize);

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

    unit_nary_arithmetic! { $tyname, $arity, $storsize }
  }
}

/// Implements arithmetic on an n-ary type, with overflow and division by zero
/// errors.
#[macro_export] macro_rules! nary_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 an n-ary field type.
///
/// The first argument is the desired type name as an unquoted string.
///
/// The second argument is the desired type name for a single digit (e.g., `b1`
/// for a bit), also as an unquoted string.
///
/// The second argument is the arity (e.g. `2` for binary). It should be
/// integral.
///
/// The third argument defines the storage type used to store the digit, since
/// that is the underlying vocabulary Rust allows us to work with. So it must be
/// a valid numeric type large enough to store the arity, and one that
/// implements basic arithmetic (e.g., `u8`, `u16`).
///
/// The fourth argument defines the field width, (i.e., the number of digits in
/// the number). For example, `3` will create a type with three digits of arity
/// defined in the second argument.
///
/// The result will be a newtype struct and associated arithmetic
/// implementations.
#[macro_export] macro_rules! nary_type {
  ($tyname:ident,
   $unit_tyname:ident,
   $arity:expr,
   $storsize:ident,
   $fieldwidth:expr) => {
    unit_nary! { $unit_tyname, $arity, $storsize }
    
    /// An n-ary number (of $fieldwidth digits).
    #[derive(Clone, Copy, PartialEq)]
    pub struct $tyname([$unit_tyname; $fieldwidth]);    

    impl $tyname {
      pub fn new(vals: [$unit_tyname; $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 = $unit_tyname;
    
      fn index<'b>(&'b self, idx: usize) -> &'b $unit_tyname {
        &self.0[idx]
      }
    }
    
    impl IndexMut<usize> for $tyname {
      fn index_mut<'a>(&'a mut self, index: usize) -> &'a mut $unit_tyname {
        &mut self.0[index]
      }
    }

    nary_type_arithmetic! { $tyname, $fieldwidth }
  }
}