turbo 0.4.2

#![feature(use_extern_macros)]
#![allow(non_camel_case_types)]
#[macro_use] extern crate finite_fields;
extern crate daggy;
extern crate rand;

finite_fields::binary_type! { b3, 3 }

/// Descriptor for code types.
pub enum CodeType {
  FIRCode,
  IIRCode
}

/// A description of a binary convolutional code, either nonrecursive (FIR), or
/// recursive (IIR), including start state.
pub struct Code {
  /// The starting state of the registers.
  pub start_state: Vec<b1>, // TODO make n-1 width type (see issue)
  /// Storage of the binary polynomial coefficients. Each polynomial corresponds
  /// to an output bit in the order in which they are stored.
  ///
  /// Coefficients are defined in order of increasing delay, e.g. `polys[0][0]`
  /// is applied to `signal[n]`, and `coefs[1]` is applied to `signal[n-1]`, and
  /// so on.
  pub polys: Vec<b3>, // TODO make static length array
  /// Enum describing the type of the code (FIR or IIR).
  pub code_type: CodeType
}

impl Code {
  /// Computes the adjacency matrix of states the code passes through. The
  /// output is a matrix indexed by `[start_index][destination_index]`, with a
  /// unit binary digit in each position (`1` if there is an edge, `0` if there
  /// is not).
  ///
  /// This turns out to be easy for an FIR encoder, because the transitions can
  /// be expressed solely as "pushes" onto an array of previous states that only
  /// differ by the next input bit. For example, for a 3-digit state register,
  /// the adjacency matrix looks like this:
  ///
  /// ```text
  /// 1 1 0 0 0 0 0 0
  /// 0 0 1 1 0 0 0 0
  /// 0 0 0 0 1 1 0 0
  /// 0 0 0 0 0 0 1 1
  /// 1 1 0 0 0 0 0 0
  /// 0 0 1 1 0 0 0 0
  /// 0 0 0 0 1 1 0 0
  /// 0 0 0 0 0 0 1 1
  /// ```
  ///
  /// # Examples
  ///
  /// ```
  /// use turbo::{Code, CodeType, b3, ONE, ZERO};
  ///
  /// let toy_code = Code {
  ///   start_state: vec![ZERO, ZERO],
  ///   polys: vec![b3::new([ZERO, ZERO, ONE]),
  ///               b3::new([ONE, ONE, ZERO])],
  ///   code_type: CodeType::FIRCode
  /// };
  ///
  /// assert_eq!(toy_code.state_adjacency(),
  ///            vec![vec![ONE, ONE, ZERO, ZERO],
  ///                 vec![ZERO, ZERO, ONE, ONE],
  ///                 vec![ONE, ONE, ZERO, ZERO],
  ///                 vec![ZERO, ZERO, ONE, ONE]]);
  /// ```
  pub fn state_adjacency(&self) -> Vec<Vec<b1>> {
    match self.code_type {
      CodeType::FIRCode => {
        // The dimension of the (square) adjacency matrix.
        let state_dim = 2usize.pow(self.start_state.len() as u32);

        (0..state_dim).map(|col_ind| {
          zero_padded_vec(state_dim, vec![ONE, ONE], col_ind * 2)
        }).collect()
      },
      CodeType::IIRCode => vec![vec![ZERO]] // FIXME placeholder
    }
  }

  /// Computes the next states indices reachable given an index corresponding to
  /// an existing state index (numbered in monotonic ascending order).
  ///
  ///
  /// # Examples
  ///
  /// ```
  /// use turbo::{Code, CodeType, b3, ONE, ZERO};
  ///
  /// let toy_code = Code {
  ///   start_state: vec![ZERO, ZERO],
  ///   polys: vec![b3::new([ZERO, ZERO, ONE]),
  ///               b3::new([ONE, ONE, ZERO])],
  ///   code_type: CodeType::FIRCode
  /// };
  ///
  /// assert_eq!(toy_code.next_states(0),
  ///            vec![0, 1]);
  /// assert_eq!(toy_code.next_states(1),
  ///            vec![2, 3]);
  /// assert_eq!(toy_code.next_states(2),
  ///            vec![0, 1]);
  /// assert_eq!(toy_code.next_states(3),
  ///            vec![2, 3]);
  /// ```
  pub fn next_states(&self, state_ind: usize) -> Vec<usize> {
    match self.code_type {
      CodeType::FIRCode => {
        let state_count = 2usize.pow(self.start_state.len() as u32);
        let first_next = (state_ind * 2) % state_count; // 2 here is arity
        vec![first_next, &first_next + 1]
      }, // TODO do more than binary
      CodeType::IIRCode => vec![0] // FIXME placeholder
    }
  }
}

pub mod encoders;
pub mod viterbi;
// pub mod bcjr;

fn zero_padded_vec(vec_len: usize, vals: Vec<b1>, offset: usize) -> Vec<b1> {
  let mut out_vec = vec![ZERO; offset % vec_len];

  for val in vals { out_vec.push(val); }
  for _ in 0..(vec_len - out_vec.len()) { out_vec.push(ZERO); }

  out_vec
}