Subversion Repositories bluespec-reedsolomon

//----------------------------------------------------------------------//
// The MIT License 
// 
// Copyright (c) 2008 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 
{  CALC_D, 
   CALC_LAMBDA, 
   CALC_LAMBDA_2, 
   CALC_LAMBDA_3,
   START,
   BERLEKAMP_DONE
} Stage deriving (Bits, Eq);

// ---------------------------------------------------------
// Reed-Solomon Berlekamp algoritm interface 
// ---------------------------------------------------------
interface IBerlekamp;
   // input methods
   method Action                     t_in(Byte t_new);
   method Action                     s_in(Syndrome#(TwoT) syndrome_new);
   
   // output methods
   method ActionValue#(Bool)         no_error_flag_out();
   method ActionValue#(Syndrome#(T)) lambda_out();
   method ActionValue#(Syndrome#(T)) omega_out();
endinterface

// ---------------------------------------------------------
// Reed-Solomon Berlekamp module 
// ---------------------------------------------------------
(* synthesize *)
module mkBerlekamp(IBerlekamp);
   
   // state elements
   // ------------------------------------------------
   // input fifos, to increase throughput, can have size > 1
   FIFO#(Byte)                     t_q             <- mkSizedFIFO(1);
   FIFO#(Syndrome#(TwoT))          syndrome_q      <- mkSizedFIFO(1);
   
   // output fifos, for correctness, size need to be 1
   MFIFO#(1,Syndrome#(TPlusTwo))   c_q             <- mkMFIFO1(); // lambda
   MFIFO#(1,Syndrome#(TPlusTwo))   w_q             <- mkMFIFO1(); // omega
   MFIFO#(1,Bool)                  no_error_flag_q <- mkMFIFO1();
  
   // regs
   Reg#(Syndrome#(TPlusTwo))       syn_shf_reg     <- mkRegU;
    
   Reg#(Syndrome#(TPlusTwo))       p               <- mkRegU; // B
   Reg#(Syndrome#(TPlusTwo))       a               <- mkRegU; // A

   Reg#(Byte)                      d               <- mkRegU;
   Reg#(Byte)                      dstar           <- mkRegU;
   Reg#(Byte)                      d_dstar         <- mkRegU;

   Reg#(Byte)                      i               <- mkRegU;
   Reg#(Byte)                      l               <- mkRegU;
   Reg#(Bool)                      is_i_gt_2l      <- mkRegU; // is i + 1 > 2*l?
   Reg#(Stage)                     stage           <- mkReg(BERLEKAMP_DONE);
   Reg#(Byte)                      block_number    <- mkReg(0);
   
   // function wrapper (for resource sharing)
   // ------------------------------------------------
   Wrapper2#(Syndrome#(TPlusTwo),
             Syndrome#(TPlusTwo),
             Syndrome#(TPlusTwo))    gf_mult_vec  <- mkUniqueWrapper2(zipWith(gf_mult_inst));   
   Wrapper2#(Syndrome#(TPlusTwo),
             Syndrome#(TPlusTwo),
             Syndrome#(TPlusTwo))    gf_add_vec   <- mkUniqueWrapper2(zipWith(gf_add_inst));   
   
   // define constants
   // ------------------------------------------------
   Syndrome#(TPlusTwo) p_init = replicate(0);
   Syndrome#(TPlusTwo) c_init = replicate(0);
   Syndrome#(TPlusTwo) w_init = replicate(0);
   Syndrome#(TPlusTwo) a_init = replicate(0);
   c_init[0] = 1;
   p_init[0] = 1;
   a_init[0] = 1;
   let t = t_q.first();
   let syndrome = syndrome_q.first();
   Reg#(Syndrome#(TPlusTwo)) c = c_q.first;
   Reg#(Syndrome#(TPlusTwo)) w = w_q.first;
   Reg#(Bool) no_error_flag = no_error_flag_q.first;
   
   // ------------------------------------------------
   rule calc_d (stage == CALC_D);
      let syn             = syndrome[i];
      let newSynShiftReg  = shiftInAt0(syn_shf_reg,syn); // shift in one syndrome input to syn
      let d_vec          <- gf_mult_vec.func(c, newSynShiftReg); // get convolution
      let new_d           = fold( \^ ,d_vec);
      let new_no_err_flag = no_error_flag && syndrome[i] == 0;
      
      if (i < 2 * t)
         begin
            syn_shf_reg <= newSynShiftReg;
            d <= new_d;
            stage <= CALC_LAMBDA;
            i <= i + 1;
            no_error_flag <= new_no_err_flag;
         end
      else // i == 2 * t
         begin
            stage <= BERLEKAMP_DONE;
            t_q.deq();
            syndrome_q.deq();
            if (no_error_flag) // no error, don't need to send lambda and omega
               begin
                  c_q.deq();
                  w_q.deq();
               end
         end
      
      $display ("  [berlekamp %d]  calc_d, L = %d, i = %d, d = %d, s [%d] = %d", 
                block_number, l, i, new_d, i, syn);       
   endrule

   // ------------------------------------------------
   rule calc_lambda (stage == CALC_LAMBDA);   
      stage <= (d == 0) ? CALC_D : CALC_LAMBDA_2;
      d_dstar <= gf_mult_inst(d, dstar); // d_dstar = d * dstar
      p <= shiftInAt0(p,0); // increase polynomial p degree by 1
      a <= shiftInAt0(a,0); // increase polynomial a degree by 1
      is_i_gt_2l <= (i > 2 * l); // check i + 2 > 2 * l?

      //$display ("  [berlekamp %d]  calc_lambda. d = %d, dstar = %d, i(%d) > 2*L(%d)?", block_number, d, dstar, i, l);
   endrule
   
   // ------------------------------------------------
   rule calc_lambda_2 (stage == CALC_LAMBDA_2);
      let d_dstar_p <- gf_mult_vec.func(replicate(d_dstar),p);
      let new_c     <- gf_add_vec.func(c,d_dstar_p);
      c <= new_c;
      stage <= CALC_LAMBDA_3;
      if (is_i_gt_2l)  // p = old_c only if i + 1 > 2 * l
         p <= c;

      //$display ("  [berlekamp %d] calc_lambda_2. c (%x) = d_d* (%x) x p (%x)", block_number, new_c, d_dstar, p);      
   endrule
   
   // ------------------------------------------------
   rule calc_lambda_3 (stage == CALC_LAMBDA_3);      
      let d_dstar_a <- gf_mult_vec.func(replicate(d_dstar),a);
      let new_w     <- gf_add_vec.func(w,d_dstar_a);
      w <= new_w;
      stage <= CALC_D;
      if (is_i_gt_2l)  // a = old_w only if i + 1 > 2 * l
         begin
            a <= w;
            l <= i - l;
            dstar <= gf_inv(d);
         end

      //$display ("  [berlekamp %d] calc_lambda_3. w (%x) = d_d* (%x) x a (%x)", block_number, new_w, d_dstar, a);      
   endrule      

   // ------------------------------------------------
   rule start_new_syndrome (stage == START);
      //$display ("  [berlekamp %d] start_new_syndrome t : %d, s : %x", block_number, t, syndrome);      

      block_number <= block_number + 1;
      // initiatize state
      p <= p_init;
      a <= a_init;
      c_q.enq(c_init);
      w_q.enq(w_init);
      no_error_flag_q.enq(True);
      d <= 0;
      dstar <= 1;
      i <= 0;
      l <= 0;
      syn_shf_reg <= replicate(0);
      // next state becomes calc_d
      stage <= CALC_D;
   endrule
   
   // ------------------------------------------------
   method Action t_in (Byte t_new);      
      $display ("  [berlekamp %d]  t_in : %d", block_number, t_new);
      
      t_q.enq(t_new);
   endmethod
   
   // ------------------------------------------------
   method Action s_in(Syndrome#(TwoT) syndrome_new) if (stage == BERLEKAMP_DONE);      
      //$display ("  [berlekamp %d]  s_in : %x", block_number, syndrome_new);
      stage <= START;
      syndrome_q.enq(syndrome_new);
   endmethod   
   
   // ------------------------------------------------
   method ActionValue#(Bool) no_error_flag_out() if (stage == BERLEKAMP_DONE);
      $display ("  [berlekamp %d]  no_error_flag_out : %d", block_number, no_error_flag);
      
      no_error_flag_q.deq();
      return no_error_flag;
   endmethod
   
   // ------------------------------------------------
   method ActionValue#(Syndrome#(T)) lambda_out() if (stage == BERLEKAMP_DONE);                       
      //$display ("  [berlekamp %d]  lambda_out : %x", block_number, c);
      
      c_q.deq();      
      return take(tail(c)); // drop lsb && msb
   endmethod
   
   // ------------------------------------------------
   method ActionValue#(Syndrome#(T)) omega_out() if (stage == BERLEKAMP_DONE);
      //$display ("  [berlekamp %d]  omega_out : %x", block_number, w);
      
      w_q.deq();
      return take(tail(w)); // drop lsb && msb
   endmethod
   
endmodule