Subversion Repositories reedsolomon

//----------------------------------------------------------------------//
// The MIT License 
// 
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
// 
// Permission is hereby granted, free of charge, to any person 
// obtaining a copy of this software and associated documentation 
// files (the "Software"), to deal in the Software without 
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//

import FIFO::*;
import GFArith::*;
import GFTypes::*;
import MFIFO::*;
import UniqueWrappers::*;
import Vector::*;

typedef enum 
{ 
   LOC_SEARCH,
   LOC_DONE
} Stage deriving (Bits, Eq);

// ---------------------------------------------------------
// Reed-Solomon Chien Error Magnitude computer interface 
// ---------------------------------------------------------
interface IChienSearch;
   // input methods
   method Action                         t_in(Byte t_new);
   method Action                         k_in(Byte k_new);
   method Action                         no_error_flag_in(Bool no_error_new);
   method Action                         lambda_in(Syndrome#(T) lamdba_new);
      
   // output methods
   method ActionValue#(Maybe#(Byte))     loc_out();       // use Invalid to show new packet
   method ActionValue#(Maybe#(Byte))     alpha_inv_out(); // the alpha_inv of location that has error
   method ActionValue#(Bool)             cant_correct_flag_out();
   method ActionValue#(Syndrome#(T))     lambda_out();
endinterface

// ---------------------------------------------------------
// Auxiliary Function
// ---------------------------------------------------------
(* noinline *)
function Syndrome#(T) times_alpha_n_v(Syndrome#(T) lambda_a, Byte t);
   Syndrome#(T) lambda_a_new = lambda_a;
   for (Byte x = 0; x < fromInteger(valueOf(T)); x = x + 1)
      lambda_a_new[x] = times_alpha_n(lambda_a[x], x + 1) & ((x < t)? 8'hFF : 8'h00);
   return lambda_a_new;   
endfunction 

// ---------------------------------------------------------
// Reed-Solomon Chien Error Magnitude computer module 
// ---------------------------------------------------------
(* synthesize *)
module mkChienSearch (IChienSearch);
   
   // comb. circuit sharing
   Wrapper2#(Syndrome#(T),Byte,
             Syndrome#(T))       times_alpha_n_vec   <- mkUniqueWrapper2(times_alpha_n_v);
   
   // input queues
   FIFO#(Bool)                   no_error_flag_q     <- mkSizedFIFO(1);
   FIFO#(Byte)                   t_q                 <- mkSizedFIFO(1);
   FIFO#(Byte)                   k_q                 <- mkSizedFIFO(1);
   FIFO#(Syndrome#(T))           lambda_q            <- mkSizedFIFO(1);
   
   // output queues
   FIFO#(Bool)                   cant_correct_flag_q <- mkSizedFIFO(1);
   FIFO#(Maybe#(Byte))           loc_q               <- mkSizedFIFO(2);
   FIFO#(Maybe#(Byte))           alpha_inv_q         <- mkSizedFIFO(2);
   MFIFO#(1,Syndrome#(T))        lambda_a_q          <- mkMFIFO1();
   
   // book-keep state
   Reg#(Byte)                    i                   <- mkRegU();
   Reg#(Byte)                    count_error         <- mkRegU();
   Reg#(Stage)                   stage               <- mkReg(LOC_DONE);
   Reg#(Byte)                    block_number        <- mkReg(0);
   Reg#(Byte)                    alpha_inv           <- mkRegU();

   // variables   
   let no_error_flag = no_error_flag_q.first();
   let t = t_q.first();
   let k = k_q.first();
   Reg#(Syndrome#(T)) lambda_a = lambda_a_q.first;                       
   
   // ------------------------------------------------
   rule calc_loc (stage == LOC_SEARCH);
      $display ("  [chien %d]  calc_loc, i = %d", block_number, i);
      
      let zero_padding = (i >= k + 2 * t);
      let parity_bytes = (i < 2 * t);
      let process_error = ((i < k + 2 * t) && (i >= 2 * t));
      Byte result_location = 1;

      if (!no_error_flag)
         begin
            result_location = fold(gf_add, cons(1,lambda_a)); // lambda_a add up + 1
            alpha_inv <= times_alpha(alpha_inv);

            $display ("  [chien %d]  calc_loc, result location = %d", block_number, result_location);
         end
      
      let is_no_error = (result_location != 0);
      
      if (!is_no_error)
         count_error <= count_error + 1;
      
      if (i == 0)
         begin
            stage <= LOC_DONE; 
            cant_correct_flag_q.enq(count_error == 0);
            t_q.deq();
            k_q.deq();
            no_error_flag_q.deq();
            if (!no_error_flag)
               begin
                  lambda_a_q.deq();
                  loc_q.enq(tagged Invalid);
                  alpha_inv_q.enq(tagged Invalid);
               end
         end
      else
         begin
            i <= i - 1;
            if (!no_error_flag)
               begin                  
                  let lambda_a_new <- times_alpha_n_vec.func(lambda_a,t); 
                  lambda_a <= lambda_a_new;

                  //$display ("  [chien %d]  calc_loc, lambda_a = %d", block_number, lambda_a_new);
               end  
            if (process_error)
               begin
                  if (!is_no_error) // enq loc_q an alpha_inv_q if there is error
                     begin
                        alpha_inv_q.enq(tagged Valid alpha_inv);
                        loc_q.enq(tagged Valid (k + 2 * t - i - 1)); // process range 1 - k
                     end
         end

         end
   endrule
   
   // ------------------------------------------------
   rule start_next_chien (stage == LOC_DONE);
      $display ("Start Next Chien ");
      
      stage <= LOC_SEARCH;
      i <= 254;
      count_error <= no_error_flag ? 1 : 0;
      block_number <= block_number + 1;
      if (!no_error_flag)
         begin
            let lambda_a_new <- times_alpha_n_vec.func(lambda_a,t); 
            lambda_a <= lambda_a_new; // if correctable, initialize lambda_a  
            alpha_inv <= 2; // = alpha^(1) = alpha^(-254)
         end                                                                 
   endrule

   // ------------------------------------------------
   method Action no_error_flag_in (Bool no_error_new);
      $display ("  [chien %d]  no_error_in : %d", block_number, no_error_new);
      
      no_error_flag_q.enq(no_error_new);
   endmethod
   
   // ------------------------------------------------
   method Action t_in (Byte t_new);
      $display ("  [chien %d]  t_in : %d", block_number, t_new);

      t_q.enq(t_new);
   endmethod
   
   // ------------------------------------------------
   method Action k_in (Byte k_new);
      $display ("  [chien %d]  k_in : %d", block_number, k_new);
      
      k_q.enq(k_new);
   endmethod
    
   // ------------------------------------------------
   method Action lambda_in(Syndrome#(T) lambda_new);
      //$display ("  [chien %d]  lambda_in : %d", block_number, lambda_new);
   
      lambda_a_q.enq(lambda_new);
      lambda_q.enq(lambda_new);
   endmethod
   
   // ------------------------------------------------
   method ActionValue#(Maybe#(Byte)) loc_out();
      $display ("  [chien %d]  loc_out : %d, stage : %d", block_number, loc_q.first(), stage);
      loc_q.deq();
      $display ("No of Errors %d", count_error);
      
      return loc_q.first();
   endmethod
   
   // ------------------------------------------------
   method ActionValue#(Maybe#(Byte)) alpha_inv_out();
      $display ("  [chien %d]  alpha_inv_out : %d, stage : %d", block_number, alpha_inv_q.first(), stage);
      alpha_inv_q.deq();
      $display ("No of Errors %d", count_error);
      
      return alpha_inv_q.first();
   endmethod
   
   // ------------------------------------------------
   method ActionValue#(Bool) cant_correct_flag_out();
      $display ("  [chien %d]  Can't Correct Flag : %d", block_number, cant_correct_flag_q.first());

      cant_correct_flag_q.deq();
      return cant_correct_flag_q.first();
   endmethod
                       
   // ------------------------------------------------
   method ActionValue#(Syndrome#(T)) lambda_out();
      //$display ("  [chien %d]  lambda_out : %d", block_number, lambda_q.first());
                       
      lambda_q.deq();
      return lambda_q.first();
   endmethod                    
                       
endmodule