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! nary_field_common_deps {
  () => {
    #[macro_use] extern crate newtype_derive;

    use std::fmt;

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

    use finite_fields::error::{ConversionError, 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)
      }

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

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

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

      fn try_from(val: usize) -> Result<Self, Self::Err> {
        if val > $arity - 1 {
          Err(ConversionError::OverflowError { arg1: val.to_string() })
        } else {
          Ok((0..val).fold(ZERO, |accum, _| (accum + ONE).unwrap()))
        }
      }
    }

    /// Implements the conversion by converting the bits to `usize` and then
    /// summing.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// unit_nary! { t1, 3, u8 }
    ///
    /// fn main() {    
    ///   let one: usize = ONE.into();
    ///   assert_eq!(one, 1);
    /// }
    /// ```
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// unit_nary! { t1, 4, u8 }
    ///
    /// fn main() {
    ///   let three: usize = (ONE + ONE + ONE).unwrap().into();
    ///   assert_eq!(three, 3);
    /// }
    /// ```
    impl From<$tyname> for usize {
      fn from(val: $tyname) -> usize {
        usize::from(val.0)
      }
    }

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

    impl BitOr for $tyname {
      type Output = Self;
      fn bitor(self, other: $tyname) -> Self {
        $tyname(self.0 | other.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 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 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., `$unit_tyname`
/// 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, Debug)]
    pub struct $tyname([$unit_tyname; $fieldwidth]);

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

      /// Reports the maximum unsigned integer expressible in this type.
      ///
      /// # Examples
      ///
      /// ```
      /// #![feature(try_from)]
      /// #[macro_use] extern crate finite_fields;
      ///
      /// nary_type! { t3, t1, 3, u8, 3 }
      ///
      /// fn main() {
      ///   let num: t3 = t3::new([ZERO; 3]);
      ///   assert_eq!(num.max(), (3 as usize).pow(3) - 1);
      /// }
      /// ```
      pub fn max(&self) -> usize {
        ($arity 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: 0 }
      }

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

      /// Shifts the leftmost digit off and pushes a new digit onto the right.
      pub fn shift_concat(&self, val: $unit_tyname) -> $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.
      pub fn unshift_concat(&self, val: $unit_tyname) -> $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::{TryFrom, TryInto};
    ///
    /// nary_type! { t3, t1, 3, u8, 3 }
    ///
    /// fn main() {
    ///   let zero: t3 = (0 as usize).try_into().unwrap();
    ///   assert_eq!(zero, t3::new([ZERO; 3]);
    ///   
    ///   let one: t3 = (1 as usize).try_into().unwrap();
    ///   let safer_one = (t3::new([ZERO; 3]) + 1).unwrap();
    ///   assert_eq!(one, safer_one);
    ///   
    ///   let two: t3 = (2 as usize).try_into().unwrap();
    ///   assert_eq!(two, (safer_one * 2).unwrap());
    ///   
    ///   let three: t3 = (3 as usize).try_into().unwrap();
    ///   assert_eq!(three, (safer_one * 3).unwrap());
    ///   
    ///   let unit_overflow = t3::try_from((3 + 1) as usize);
    ///   assert!(unit_overflow.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 % $arity != 0 {
            out_val[$fieldwidth - 1] = ONE;
          }

          for place in 0..$fieldwidth {
            if dec > 1 {
              dec = dec / $arity;
              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;
    ///
    /// nary_type! { t3, t1, 3, u8, 3 }
    ///
    /// fn main() {
    ///   let zero: t3 = (0 as usize).into();
    ///   assert_eq!(zero, t3::new([ZERO, ZERO]));
    ///   
    ///   let one: t3 = (1 as usize).into();
    ///   assert_eq!(one, t3::new([ZERO, ONE]));
    ///   
    ///   let two: t3 = (2 as usize).into();
    ///   assert_eq!(two, t3::new([ONE, ZERO]));
    ///   
    ///   let three: t3 = (3 as usize).into();
    ///   assert_eq!(three, t3::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;
    ///
    /// nary_type! { t3, t1, 3, u8, 3 }
    ///
    /// fn main() {
    ///   let four = t3::from((3 + 1) 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 % $arity != 0 {
            out_val[$fieldwidth - 1] = ONE;
          }
          
          for place in 0..$fieldwidth {
            if dec > 1 {
              dec = dec / $arity;
              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)] extern crate finite_fields;
    /// use std::convert::{TryFrom, TryInto};
    ///
    /// nary_type! { t3, t1, 3, u8, 3 }
    ///
    /// fn main() {
    ///   let zero_arr = [ZERO; 3];
    ///   let one_arr = &zero_arr.shift_concat(ONE);
    ///   
    ///   let zero = t3::new([ZERO; 3]);
    ///   let one = (&zero + ONE).unwrap();
    ///   
    ///   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!(t3::try_from(&bad_arr[0..]).is_err());
    /// }
    /// ```
    impl<'a> TryFrom<&'a [$unit_tyname]> for $tyname {
      type Err = ConversionError;

      fn try_from(val: &[$unit_tyname]) -> 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;
    ///
    /// nary_type! { t3, t1, 3, u8, 3 }
    ///
    /// // TODO make these static
    /// let mut one: t3 = t3([ZERO; 3]);
    /// one[3 - 1] = ONE;
    ///
    /// let one_from: usize = one.into();
    /// assert_eq!(one_from, 1);
    /// ```
    ///
    /// ```
    /// #![feature(try_from)]
    /// #[macro_use] extern crate finite_fields;
    ///
    /// nary_type! { t3, t1, 3, u8, 3 }
    ///
    /// fn main() {
    ///   // TODO make these static
    ///   let mut one: t3 = t3([ZERO; 3]);
    ///   one[3 - 1] = ONE;
    ///   
    ///   let three_from: usize = (one + one + one).unwrap()).into();
    ///   
    ///   assert_eq!(three_from, 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 = $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]
      }
    }

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

    impl Iterator for Iter {
      type Item = $unit_tyname;

      // next() is the only required method
      fn next(&mut self) -> Option<$unit_tyname> {
        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 = $unit_tyname;
      type IntoIter = ::std::vec::IntoIter<$unit_tyname>;

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

    impl<'a> IntoIterator for &'a $tyname {
      type Item = &'a $unit_tyname;
      type IntoIter = ::std::slice::Iter<'a,$unit_tyname>;

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

    impl FromIterator<$unit_tyname> for $tyname {
      fn from_iter<I: IntoIterator<Item=$unit_tyname>>(iter: I) -> Self {
        let mut collector = $tyname::new([ZERO; $fieldwidth]);

        for (ind, val) in (0..collector.len()).zip(iter) {
          collector[ind] = val;
        }

        collector
      }
    }

    nary_type_arithmetic! { $tyname, $fieldwidth }
  }
}