////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2023 Homework 5 -- SOLUTION
//

 /// Assignment  https://www.ece.lsu.edu/koppel/v/2023/hw05.pdf
`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
  ///  Complete uniq_vector_seq as described in the handout.
 ///
//
//     [✔] Only modify uniq_vector_seq
//     [✔] Remove the uniq_vector_comb instantiation.
//
//     [✔] Make sure that the testbench does not report errors.
//     [✔] Module must be synthesizable. Use command: genus -files syn.tcl
//
//     [✔] Don't assume any particular parameter values.
//
//     [✔] Code must be written clearly.
//     [✔] Pay attention to cost.
//     [✔] Make sure that cost is not proportional to n^2.


module uniq_vector_seq
  #( int we = 10, n = 5, wc = $clog2(n+1) )
   ( output logic [n-1:0] uniq_bvec,
     output logic [wc-1:0] n_match,
     input uwire [we-1:0] element,
     input uwire start, clk );

   /// SOLUTION
   logic [we-1:0] elements [n-1:0];
   logic [n-1:0] occ_bvec;
   logic [wc-1:0] uniq_at [n-1:0];

   always_ff @( posedge clk ) begin

      // Find minimum match_pos for which elements[match_pos] == element.
      //
      automatic logic [wc-1:0] match_pos = 0;

      // Number of existing elements matching element.
      n_match = 1;

      for ( int i=n-1; i>=1; i-- ) begin

         automatic logic next_occ_bvec = !start && occ_bvec[i-1];
         //
         // If next_occ_bvec == 0, this element had been reset.

         // Check whether element matches elements[i-1]
         //
         automatic logic match = next_occ_bvec && element == elements[i-1];
         //
         // There is no match if this elt had been reset.

         n_match += match;

         if ( match ) match_pos = n - i;

         elements[i] <= elements[i-1];
         occ_bvec[i] <= next_occ_bvec;

         // If match is true then elements[i-1] will never be unique. :-(
         //
         uniq_at[i] <= match ? n : uniq_at[i-1];

         // Update uniqueness
         //
         uniq_bvec[i] <= !next_occ_bvec || !match && i >= uniq_at[i-1];
         //
         // Future elements[i] is unique if:
         //   - It had been reset.
         //   - It is beyond its unique-at position (uniq_at).

      end

      elements[0] <= element;
      occ_bvec[0] <= 1;
      uniq_at[0] <= match_pos;
      uniq_bvec[0] <= match_pos == 0;
   end

endmodule


module uniq_vector_comb
  #( int we = 10, n = 5, wc = $clog2(n+1) )
   ( output logic [n-1:0] uniq_bvec,
     output logic [wc-1:0] n_match,
     input uwire [we-1:0] element [n-1:0] );

   /// This module is for reference. It should not be part of your solution.
   //  Modify this module only for experimentation.

   // Combinational version.
   always_comb
     for ( int i=0; i<n; i++ ) begin
        automatic logic [wc-1:0] occ = 0;
        for ( int j=0; j<n; j++ ) if ( element[i] == element[j] ) occ++;
        if ( i == 0 ) n_match = occ;
        uniq_bvec[i] = occ == 1;
     end

endmodule



//////////////////////////////////////////////////////////////////////////////
/// Testbench Code
//
// It is okay to modify the testbench code to facilitate the coding
// and debugging of your modules. Keep in mind that your submission
// will be tested using a different testbench, so on the one hand no
// one will be accused of dishonesty for modifying the testbench
// below. However be sure to restore any changes to make sure that
// your code passes the original testbench.


// cadence translate_off

program reactivate
   (output uwire clk_reactive, output int cycle_reactive,
    input uwire clk, input var int cycle);
   assign clk_reactive = clk;
   assign cycle_reactive = cycle;
endprogram

module testbench;
   localparam int npsets = 4; // This MUST be set to the size of pset.
   // { n we s }
   localparam int pset[npsets][3] =
              '{
                { 4, 4, 0 },
                { 4, 4, 1 },
                { 7, 6, 0 },
                { 7, 6, 1 }
                };

   logic d[npsets:-1]; // Start / Done signals.

   int t_errs_bvec[npsets];
   int t_errs_n_match[npsets];
   int t_n_tests[npsets];

   int t_errs;     // Total number of errors.
   initial begin
      t_errs = 0;
      for ( int i=0; i<npsets; i++ ) begin
         t_errs_bvec[i] = -1;
         t_errs_n_match[i] = -1;
         t_n_tests[i] = -1;
      end
      d[-1] = 1;

      wait( d[npsets-1] );

      for ( int p=0; p<npsets; p++ )
        $write("End of tests n=%2d, s=%0d: %0d bvec errors, %0d n_match errors for %0d tests.\n",
               pset[p][1], pset[p][2],
               t_errs_bvec[p], t_errs_n_match[p], t_n_tests[p]);

   end

   for ( genvar p=0; p<npsets; p++ ) begin
      testbench_n #( .we(pset[p][0]), .n(pset[p][1]), .s(pset[p][2]), .idx(p) )
      tb( .done(d[p]), .tstart(d[p-1]) );
   end

endmodule


module testbench_n
  #( int n = 12, we = 6, idx = 1, s = 1 )
   ( output logic done, input uwire tstart );

   localparam int wc = $clog2(n+1);

   localparam int n_tests = 100000;
   localparam int cyc_max = n_tests * 2 + 3*n;

   int seed;
   initial seed = 475501;

   function string sample( input string str );
      sample = str[ $dist_uniform( seed, 0, str.len()-1 ) ];
   endfunction

   bit clk;
   int cycle, cycle_limit;
   logic clk_reactive;
   int cycle_reactive;
   reactivate ra(clk_reactive,cycle_reactive,clk,cycle);
   string event_trace;

   initial begin
      clk = 0;
      cycle = 0;
      event_trace = "";

      done = 0;
      cycle_limit = cyc_max;
      wait( tstart );

      fork
         while ( !done ) #1 cycle += clk++;
         wait( cycle >= cycle_limit )
           $write("Exit from clock loop at cycle %0d, limit %0d.  %s\n %s\n",
                  cycle, cycle_limit, "** CYCLE LIMIT EXCEEDED **",
                  event_trace);
      join_any;

      done = 1;
   end


   typedef logic [we-1:0] Digit;
   Digit element_stream[$];
   bit start_stream[$];
   logic [we-1:0] element_stream_x[$];
   int element_most_recent_t[int];
   logic [n-1:0] shadow_uniq_bvec;
   int element_occ[int];

   uwire [n-1:0] uniq_bvec;
   uwire [wc-1:0] n_match;
   Digit element;
   logic start;

   uniq_vector_seq #(we,n) uvs( uniq_bvec, n_match, element, start, clk );

   int n_err_bvec, n_err_n_match;
   localparam int pre_n = 2;
   localparam int trace_len = 5;
   localparam int n_pre_check = 2 * n; // Number of inputs before testing.
   localparam int start_dups = 5 * n + n_pre_check;

   initial begin
      automatic int n_tests_done = 0;
      int tnum_last_start;
      bit err_bvec_here, err_n_match_here, show_trace;

      n_err_bvec = 0;
      n_err_n_match = 0;
      element = 1;
      start = 1;

      @( negedge clk );
      @( negedge clk );

      start = 0;

      wait( cycle > 2 );

      @( negedge clk );

      $write("\n** Starting tests for n=%0d, input start used = %0s **\n",
             n, s ? "Yes" : "No");

      for ( int tnum=0; tnum<n_tests; tnum++ ) begin

         automatic bit want_match =
           tnum > start_dups && $dist_uniform(seed,0,2) == 0;
         automatic bit want_reset =
           tnum == 0 || s && $dist_uniform(seed,0,1*n) == 0;

         automatic logic [we-1:0] next_element =
           want_match ? element_stream[ {$random} % (n-1) ] : {$random} % 100;
         automatic int n_starts_recent = 0;
         automatic int shadow_n_match = 0;
         bit err_here;

         @( negedge clk );

         if ( element_stream.size() >= n + pre_n ) begin
            automatic int old_element = element_stream.pop_back();
            automatic bit old_start = start_stream.pop_back();
         end

         if ( element_stream.size() >= n
              && tnum_last_start + n <= tnum )
           element_occ[element_stream[n-1]]--;

         if ( want_reset ) tnum_last_start = tnum;
         element = next_element;
         start = want_reset;

         if ( want_reset ) element_occ.delete();

         element_occ[element]++;
         element_stream.push_front(element);
         start_stream.push_front(start);

         for ( int i=0; i<n; i++ ) begin
            if ( element_stream[i] == element && !n_starts_recent )
              shadow_n_match++;
            shadow_uniq_bvec[i] =
              n_starts_recent || element_occ[element_stream[i]] == 1;
            n_starts_recent += start_stream[i];
         end

         @( posedge clk_reactive );

         if ( tnum < n_pre_check ) continue;

         err_n_match_here = n_match !== shadow_n_match;
         if ( err_n_match_here ) n_err_n_match++;

         err_bvec_here = uniq_bvec !== shadow_uniq_bvec;

         if ( err_bvec_here ) n_err_bvec++;

         err_here = err_bvec_here || err_n_match_here;

         show_trace = tnum > start_dups + n && tnum < start_dups + n + trace_len
           || err_here && n_err_bvec < 5 && n_err_n_match < 5;

         n_tests_done++;

         if ( show_trace ) begin
            $write( "%s, uniq_bvec: t=%0d,  %b",
                    err_bvec_here ? "Error" : "Trace", tnum,
                    uniq_bvec);
            if ( err_bvec_here )
              $write( "!= %b ( correct )", shadow_uniq_bvec );
            if ( err_n_match_here )
              $write("\nError:  n_match: %0d != %0d (correct)",
                     n_match,shadow_n_match);
            $write("\n[");
            for ( int i=n+pre_n-1; i>=n; i-- )
              $write( "%2s%0s%0s ", "", i == n ? "]" : "", i ? "," : "" );
            for ( int i=n-1; i>=0; i-- )
              $write( "%1s%1h%0s%0s ",
                      uniq_bvec[i]===shadow_uniq_bvec[i] ? " " : "E",
                      uniq_bvec[i],
                      i == n ? "]" : "", i ? "," : "" );
            $write(" <-- uniq_bvec\n[");
            for ( int i=n+pre_n-1; i>=0; i-- )
              $write( "%2d%0s%0s ",
                      element_stream[i], i == n ? "]" : "", i ? "," : "" );
            $write(" <-- Element\n[");
            for ( int i=n+pre_n-1; i>=0; i-- )
              $write( "%2d%0s%0s ",
                      start_stream[i], i == n ? "]" : "", i ? "," : "" );

            $write(" <-- Start\n");
         end

      end

      $write
        ("For n=%0d, s=%0d: done with %0d tests. Errors: %0d bvec, %0d n_match.\n",
         n, s, n_tests, n_err_bvec, n_err_n_match);

      testbench.t_errs_bvec[idx] = n_err_bvec;
      testbench.t_errs_n_match[idx] = n_err_n_match;
      testbench.t_n_tests[idx] = n_tests_done;

      done = 1;

   end

endmodule

// cadence translate_on