////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2019 Homework 4
//

 /// Assignment  https://www.ece.lsu.edu/koppel/v/2019/hw04.pdf

 /// Instructions:
  //
  // (1) Find the undergraduate workstation laboratory, room 2241 Patrick
  //     F. Taylor Hall. Machines to use are in the back.
  //
  // (2) Locate your account.  If you did not get an account please
  //     E-mail: koppel@ece.lsu.edu
  //
  // (3) Log in to a Linux workstation.
  //
  // (4) If you haven't already, follow the account setup instructions here:
  //     https://www.ece.lsu.edu/koppel/v/proc.html
  //
  // (5) Copy this assignment, local path name
  //     /home/faculty/koppel/pub/ee4755/hw/2019/hw04
  //     to a directory ~/hw04 in your class account. (~ is your home
  //     directory.) Use this file for your solution.
  ///      BE SURE THAT YOUR FILE IS CORRECTLY NAMED AND IN THE RIGHT PLACE.
  //
  // (6) Find the problems in this file and solve them.
  //
  //     Your entire solution should be in this file.
  //
  //     Do not change module names.
  //
  // (7) Your solution will automatically be copied from your account by
  //     the TA-bot.


 /// Additional Resources
  //
  // Verilog Documentation
  //    The Verilog Standard
  //      https://ieeexplore.ieee.org/document/8299595/
  //    Introductory Treatment (Warning: Does not include SystemVerilog)
  //      Brown & Vranesic, Fundamentals of Digital Logic with Verilog, 3rd Ed.
  //
  // Account Setup and Emacs (Text Editor) Instructions
  //      https://www.ece.lsu.edu/koppel/v/proc.html
  //      To learn Emacs look for Emacs tutorial.
  //
  // Unix Help (Very outdated.  Alternatives welcome.)
  //      https://www.ece.lsu.edu/koppel/v/4ltrwrd/


`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
 ///    Complete best_match so that it computes the best_match over wv cycles.
//
//     [ ] Put your solution in best_match. No other modules should
//         be modified. (Except the testbench, to help debug.)
//
//     [ ] Set the ready output to 0 when start is 1 at a positive edge ..
//         .. and set it to 1 when pos and err are available.
//
//     [ ] best_match should take about wv - wk cycles (see the params)
//         to find |pos| and |err|.
//
//     [ ] best_match must use a pop module to compute err.
//
//     [ ] Avoid designs that use a non-constant shifter or large mux.
//
//     [ ] Make sure that the testbench does not report errors.
//     [ ] Module must be synthesizable. Use command: genus -files syn.tcl
//
//     [ ] As always, avoid costly, slow, and confusing code.
//     [ ] As always, don't assume parameters will be at their default values.



module best_match
  #( int wv = 32, int wk = 10,
     int wvb = $clog2(wv), int wkv = $clog2(wk+1) )
   ( output logic [wvb:1] pos,
     output logic [wkv:1] err,
     output logic ready,
     input uwire [wv-1:0] val,
     input uwire [wk-1:0] k,
     input uwire start, clk );

   // Put your solution here.

endmodule


// Use this design for reference.
module best_match_behavioral
  #( int wv = 32, int wk = 10,
     int wvb = $clog2(wv), int wkv = $clog2(wk+1) )
   ( output logic [wvb:1] pos,  // Position of best match.
     output logic [wkv:1] err,  // Number of non-matching bits.
     input uwire [wv-1:0] val,
     input uwire [wk-1:0] k );

   always_comb begin

      automatic int best_err = wk + 1;
      automatic int best_pos = -1;

      for ( int p=0; p<=wv-wk; p++ ) begin
         automatic int e = 0;
         for ( int b=0; b<wk; b++ ) e += k[b] !== val[p+b];
         if ( e < best_err ) begin
            best_err = e;
            best_pos = p;
         end
      end
      err = best_err;
      pos = best_pos;

   end

endmodule

module pop
  #( int w = 5, int wp = $clog2(w+1) )
   ( output uwire [wp:1] n, input uwire [w:1] a );
   // Set n to the number of 1's in a.
   // That is, n = a[1] + a[2] + ... + a[w];
   // For example, if a=4'b0110, n = 2,
   //              if a=4'b0001, n = 1,
   //              if a=4'b1111, n = 4.

   if ( w == 1 )
     assign n = a;
   else begin
      localparam int wlo = w/2;
      localparam int whi = w - wlo;
      localparam int wwlo = $clog2(wlo+1);
      localparam int wwhi = $clog2(whi+1);
      uwire [wwlo:1] nlo;
      uwire [wwhi:1] nhi;
      pop #(wlo) plo(nlo,a[wlo:1]);
      pop #(whi) phi(nhi,a[w:wlo+1]);
      assign n = nlo + nhi;
   end

endmodule



// cadence translate_off

module testbench;

   localparam int ntests = 1000;

   localparam int wv = 64;
   localparam int wk = 8;
   localparam int wvb = 8;
   localparam int wkb = 8;
   var logic [wv-1:0] val;
   var logic [wk-1:0] k;
   var logic clk, start;
   uwire [wvb-1:0] pos[2];
   uwire [wkb-1:0] err[2];
   uwire ready[2];

   int cycle, cycle_limit;
   bit done;
   initial begin
      cycle = 0;
      cycle_limit = 1 << 30;
      clk = 0;
      done = 0;
      while ( !done && cycle < cycle_limit ) #1 if ( ++clk ) cycle++;
      $write("Exit from clock loop at cycle %0d, limit %0d.  %s\n",
             cycle, cycle_limit,
             cycle == cycle_limit ? "** CYCLE LIMIT EXCEEDED **" : "");
   end

   best_match_behavioral #(wv,wk,wvb,wkb) bmb(pos[0],err[0],val,k);
   best_match #(wv,wk,wvb,wkb) bm(pos[1],err[1],ready[1],val,k,start,clk);
   string mnames[] = { "best_match_behavioral", "best_match" };

   initial begin
      automatic int n_err[2] = '{0,0};

      for ( int i=0; i<ntests; i++ ) begin


         for ( int j=0; j<(wv+31)/32; j++ ) val = { val[wv-1-32:0], {$random} };

         k = {$random};

         cycle_limit = cycle + 2 * wv;

         @( negedge clk );
         start = 1;
         while ( ready[1] !== 0 ) @( negedge clk );
         start = 0;
         while ( ready[1] !== 1 ) @( negedge clk );

         for ( int mut=0; mut<2; mut++ ) begin

            automatic logic [wvb-1:0] cpos = pos[mut];
            automatic logic [wkb-1:0] cerr = err[mut];
            automatic string msg_pfx =
              $sformatf("Error in %s, test # %5d",mnames[mut],i);

            if ( cpos >= 0 && cpos <= wv-wk ) begin
               automatic int sh_err = 0;
               for ( int b=0; b<wk; b++ ) sh_err += val[b+cpos]!==k[b];
               if ( sh_err !== cerr ) begin
                  if ( n_err[mut] < 5 )
                    $write
                      ("%s, err wrong %0d != %0d (correct) pos %d  %h ^ %h\n",
                       msg_pfx, cerr, sh_err, cpos, val[cpos +: wk], k );
                  n_err[mut]++;
               end else if ( mut > 0 && err[mut] !== err[0] ) begin
                  if ( n_err[mut] < 5 )
                    $write
                      ( "%s, non-min match. \
err %d != %d (correct) pos %d, %d (behav) bits  %h  k %h\n",
                        msg_pfx,
                        err[mut],err[0], cpos,pos[0],
                        val[cpos +: wk], k);
                  n_err[mut]++;
               end

            end else begin
               if ( n_err[mut] < 5 )
                 $write("%s, pos out of range: 0x%h\n", msg_pfx, cpos);
               n_err[mut]++;
            end

         end

      end

      for ( int m=0; m<2; m++ )
        $write("Done with %s tests, %d errors found.\n",
               mnames[m], n_err[m]);

      done = 1;

   end

endmodule

// cadence translate_on