////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2024 Homework 3 -- SOLUTION
//

 /// Assignment  https://www.ece.lsu.edu/koppel/v/2024/hw03.pdf

`default_nettype none

 /// Convenient Character Names
//
typedef enum logic [3:0]
  { Char_Blank, Char_Dot,
    Char_Open, Char_Close,
    Char_Open_Okay, Char_Close_Okay } Char;


//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
  ///  Complete pmatch_base.
//
//     [✔] The module can use procedural code.
//     [✔] The module must a recursive and describe tree-structured hardware.
//
//     [✔] 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.
//
//     [✔] As always, code must be written clearly.
//     [✔] As always, pay attention to cost and performance.


module pmatch_base
  #( int n = 5, wn = $clog2(n+1) )
   ( output logic [wn-1:0] left_out_n_unmat_close, right_out_n_unmat_open,
     input uwire [3:0] str[0:n-1] );

   /// SOLUTION

   if ( n == 1 ) begin

      assign left_out_n_unmat_close = str[0] == Char_Close;
      assign right_out_n_unmat_open = str[0] == Char_Open;

   end else begin

      localparam int n_left = n/2;
      localparam int n_right = n - n_left;
      localparam int wl = $clog2(n_left+1),  wr = $clog2(n_right+1);

      uwire [wl-1:0] lt_close, lt_open;
      uwire [wr-1:0] rt_close, rt_open;

      pmatch_base #(n_left,  wl) plt( lt_close, lt_open, str[0:n_left-1] );
      pmatch_base #(n_right, wr) prt( rt_close, rt_open, str[n_left:n-1] );

      uwire logic signed [wn-1:0] delta = lt_open - rt_close;
      assign left_out_n_unmat_close = delta >= 0 ? lt_close : lt_close - delta;
      assign right_out_n_unmat_open = delta < 0  ? rt_open  : rt_open + delta;

   end

endmodule



module pmatch_comb_base
  #( int n = 5, wn = $clog2(n) )
   ( output logic [wn-1:0] left_out_n_unmat_close, right_out_n_unmat_open,
     input uwire [3:0] str[0:n-1] );

   /// Reference Module
   //
   //  Examine this module to help understand how to solve the problem.
   //
   //  The solution should NOT BE placed in this module.

   always_comb begin

      left_out_n_unmat_close = 0;
      right_out_n_unmat_open = 0;

      // Scan string from left to right. (Leftmost character is at i=0.)
      for ( int i=0; i<n; i++ )

        if ( str[i] == Char_Close ) begin

           // We've found a closing parenthesis, ")".

           if ( right_out_n_unmat_open > 0 )
             right_out_n_unmat_open--;  // It matches an opening parenthesis.
           else
             left_out_n_unmat_close++;  // It's unmatched, update the count.

        end else if ( str[i] == Char_Open ) begin

           // We've found an opening parenthesis, "(".

           // Increment the count of unmatched open parentheses ..
           right_out_n_unmat_open++;
           // .. which might be decremented in a later iteration.

        end
   end

endmodule


//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
  ///  Complete pmatch_mark
//
//     [✔] The module can use procedural code.
//     [✔] The module must a recursive and describe tree-structured hardware.
//
//     [✔] 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.
//
//     [✔] As always, code must be written clearly.
//     [✔] As always, pay attention to cost and performance.


module pmatch_mark
  #( int n = 5, wn = $clog2(n+1) )
   ( output logic [wn-1:0] left_out_n_unmat_close, right_out_n_unmat_open,
     output uwire [3:0] str_marked [0:n-1],
     input uwire [wn-1:0] left_in_n_unmat_open, right_in_n_unmat_close,
     input uwire [3:0] str [0:n-1] );

   /// SOLUTION

   if ( n == 1 ) begin

      assign left_out_n_unmat_close = str[0] == Char_Close;
      assign right_out_n_unmat_open = str[0] == Char_Open;

      assign str_marked[0] =
             str[0] == Char_Close && left_in_n_unmat_open   ? Char_Close_Okay :
             str[0] == Char_Open  && right_in_n_unmat_close ? Char_Open_Okay  :
             str[0];

   end else begin

      localparam int n_left = n/2;
      localparam int n_right = n - n_left;
      localparam int wl = $clog2( n_left+1 );
      localparam int wr = $clog2( n_right+1 );

      localparam logic [wl-1:0] nl_max = ~(wl)'(0); // All 1's.
      localparam logic [wr-1:0] nr_max = ~(wr)'(0); // All 1's.

      `define min(a,limit) ( unsigned'(a) <= (limit) ? a : limit )

      // Recursive Instance Outputs
      //
      uwire [wl-1:0] lt_close, lt_open;
      uwire [wr-1:0] rt_close, rt_open;

      // Same as Problem 1
      //
      uwire signed [wn-1:0] delta = lt_open - rt_close;
      assign left_out_n_unmat_close = delta >= 0 ? lt_close : lt_close - delta;
      assign right_out_n_unmat_open = delta < 0  ? rt_open  : rt_open + delta;

      /// Problem 2
      //
      // Pass the incoming number of matched parentheses to the
      // recursive instances. Use min in case their values are too
      // large.
      //
      uwire [wl-1:0] lt_matched_cl = `min( left_in_n_unmat_open,   nl_max );
      uwire [wr-1:0] rt_matched_op = `min( right_in_n_unmat_close, nr_max );

      /// Compute Right Recursive Instance Input rt_matched_cl
      //
      // Compute the number of closing parentheses that could be
      // matched in the right recursive instance (rt_matched_cl) using
      // the incoming unmatched opening parentheses and unmatched
      // opening parentheses found in the left instance.
      //
      // First, compute more_op: the number of unmatched incoming open
      // parentheses that were not matched by the portion of str
      // connected to the left recursive instance (plt).
      //
      uwire signed [wn:0] more_op = left_in_n_unmat_open - lt_close;
      //
      // Then, compute the number of unmatched opening parentheses to
      // the left of position str[n_left], accounting for the opening
      // parentheses found by the left recursive instance (lt_open)
      // and still unmatched incoming open parentheses (more_op).
      //
      uwire [wr-1:0] rt_matched_cl =
             more_op < 0  ? lt_open  : `min( lt_open + more_op, nr_max );

      /// Compute Left Recursive Instance Input lt_matched_op
      //
      // Similar to the procedure above, compute the number of still
      // unmatched incoming closing parentheses (more_cl) and combine
      // it with the number of closing parentheses found in the right
      // recursive instance.
      //
      uwire signed [wn:0] more_cl = right_in_n_unmat_close - rt_open;
      uwire [wl-1:0] lt_matched_op =
             more_cl < 0  ? rt_close : `min( rt_close + more_cl, nl_max );

      /// Recursive Instantiations
      //
      pmatch_mark #(n_left,wl)
      plt( lt_close, lt_open, str_marked[0:n_left-1],
           lt_matched_cl, lt_matched_op, str[0:n_left-1] );
      pmatch_mark #(n_right,wr)
      prt( rt_close, rt_open, str_marked[n_left:n-1],
           rt_matched_cl, rt_matched_op, str[n_left:n-1] );

   end

endmodule



module pmatch_comb_mark
  #( int n = 5, wn = $clog2(n+1) )
   ( output logic [wn-1:0] left_out_n_unmat_close, right_out_n_unmat_open,
     output logic [3:0] str_marked [0:n-1],
     input uwire [wn-1:0] left_in_n_unmat_open, right_in_n_unmat_close,
     input uwire [3:0] str [0:n-1] );

   /// Reference Module
   //
   //  Examine this module to help understand how to solve the problem.
   //
   //  The solution should NOT BE placed in this module.

   always_comb begin
      automatic logic [wn-1:0] n_um_op = left_in_n_unmat_open;
      automatic logic [wn-1:0] n_um_cl = right_in_n_unmat_close;
      left_out_n_unmat_close = 0;
      right_out_n_unmat_open = 0;
      str_marked = str;

      // Scan string from left to right. (Leftmost character is at i=0.)
      //
      // The loop below is identical to the one in pmatch_comb_base.
      //
      for ( int i=0; i<n; i++ )

        if ( str[i] == Char_Close ) begin

           // We've found a closing parenthesis, ")".

           if ( right_out_n_unmat_open > 0 )
             right_out_n_unmat_open--;  // It matches an opening parenthesis.
           else
             left_out_n_unmat_close++;  // It's unmatched, update the count.

        end else if ( str[i] == Char_Open ) begin

           // We've found an opening parenthesis, "(".

           // Increment the count of unmatched open parentheses ..
           right_out_n_unmat_open++;
           // .. which might be decremented in a later iteration.

        end

      // Scan string forward and mark matched closing parentheses.
      //
      for ( int i=0; i<n; i++ )
        if ( str[i] == Char_Close  &&  n_um_op > 0 ) begin

           n_um_op--;
           str_marked[i] = Char_Close_Okay;

        end else if ( str[i] == Char_Open ) begin

           n_um_op++;

        end

      // Scan string backward and mark matched opening parentheses.
      //
      for ( int i=n-1; i>=0; i-- )
        if ( str[i] == Char_Open  &&  n_um_cl > 0 ) begin

           n_um_cl--;
           str_marked[i] = Char_Open_Okay;

        end else if ( str[i] == Char_Close ) begin

           n_um_cl++;

        end
   end

endmodule




//////////////////////////////////////////////////////////////////////////////
/// Testbench Code


// cadence translate_off

// Module names. (Used by the testbench.)
//
typedef enum { M_base, M_mark } M_Type;

module testbench;

   localparam int n_tests = 100000;

   localparam int npsets = 6; // This MUST be set to the size of pset.
   localparam int pset[npsets][1] =
              '{{ 4 }, { 5 }, { 7 }, { 8 }, { 9 }, { 17 }};

   localparam int nmsets = 2;
   localparam M_Type mset[2] = '{ M_base, M_mark };

   string mtype_str[M_Type] =
          '{ M_base: "pmatch_base", M_mark: "pmatch_mark" };
   string mtype_abbr[M_Type] = '{ M_base: "base", M_mark: "mark" };

   int t_errs_each_cl[M_Type][int];
   int t_errs_each_op[M_Type][int];
   int t_errs_each_mk[M_Type][int];
   int t_errs_cl, t_errs_op, t_errs_mk;

   localparam int nsets = npsets * nmsets;

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

   initial begin
      t_errs_cl = 0;
      t_errs_op = 0; t_errs_mk = 0;
      for ( int m=0; m<nmsets; m++ )
        for ( int i=0; i<npsets; i++ ) begin
           automatic int n = pset[i][0];
           t_errs_each_cl[mset[m]][n] = 0;
           t_errs_each_op[mset[m]][n] = 0;
           t_errs_each_mk[mset[m]][n] = 0;
        end

      d[-1] = 1;
   end

   final begin
      for ( int mi=0; mi<nmsets; mi++ )
        for ( int i=0; i<npsets; i++ ) begin
           automatic M_Type m = mset[mi];
           automatic int n = pset[i][0];
           $write("Total %s n=%0d: Errors: %0d cl, %0d op, %0d mk.\n",
                  mtype_str[m], n,
                  t_errs_each_cl[m][n],
                  t_errs_each_op[m][n],
                  t_errs_each_mk[m][n]);
        end

   end

   for ( genvar m=0; m<nmsets; m++ )
     for ( genvar i=0; i<npsets; i++ ) begin
        localparam int idx = m * npsets + i;
        testbench_n
          #( .n(pset[i][0]), .mtype(mset[m]) )
        t2( .done(d[idx]), .tstart(d[idx-1]) );
     end

endmodule



module testbench_n
  #( int n = 4, M_Type mtype = M_base )
   ( output logic done, input uwire tstart );

   localparam int wn = $clog2(n+1);
   localparam int n_tests = 2000;

   localparam int n_samples_show = 10;
   localparam int n_errors_show = 5;



   uwire [wn-1:0] n_cl_lt, n_op_rt;
   logic [wn-1:0] n_u_op, n_u_cl;
   logic [3:0] str[0:n-1];
   uwire [3:0] str_marked[0:n-1];

   string char_to_ascii[logic[3:0]] =
          '{ Char_Blank: " ",
             Char_Dot: ".",
             Char_Open: "(",
             Char_Open_Okay: "<",
             Char_Close: ")",
             Char_Close_Okay: ">" };
   logic [3:0] ascii_to_char[string];

   function automatic string char_to_string( logic [3:0] str[0:n-1] );
      automatic string str_txt = "";
      for ( int j=0; j<n; j++ ) str_txt = { str_txt, char_to_ascii[str[j]] };
      char_to_string = str_txt;
   endfunction

   case ( mtype )
     M_base:
       pmatch_base #(n,wn) pm( n_cl_lt, n_op_rt, str );
       // pmatch_comb_base #(n,wn) pcomb( n_cl_lt, n_op_rt, str );
     M_mark:
       pmatch_mark #(n,wn) pm(n_cl_lt,n_op_rt,str_marked,n_u_op,n_u_cl, str );
       //  pmatch_comb_mark #(n,wn) pm( n_cl_lt, n_op_rt, str_marked, n_u_op, n_u_cl, str );
   endcase



   string xstr_special[] =
          '{ "))", "((", "()", ")(", ")()(", ")()", "", ")", "(",
             ") )", "( (", " ) )", " ( (", ") ) ", "( ( ", "( )", ") (" };
   string str_special[] =
          '{ "()", ".( )", ")(",  ")", "))", "()))", "())(", "())(((",
            "))((", ")", "(", "))", "((", "()", ")()(", ")()" };

   initial begin

      automatic int n_errs_cl =0, n_errs_op = 0, n_errs_mk = 0;
      automatic int n_samples = 0;
      automatic string prefix_txt =
        $sformatf("%s n=%0d",testbench.mtype_str[mtype],n);
      automatic string prefix_txt_str;

      foreach ( char_to_ascii[c] ) ascii_to_char[char_to_ascii[c]] = c;

      wait( tstart );

      $write("Starting %s tests for n=%0d.\n",
             testbench.mtype_str[mtype], n);

      for ( int i=0; i<n_tests; i++ ) begin
         automatic int shadow_n_close_lt, shadow_n_open_rt;
         automatic int n_unm_op, n_unm_cl;
         automatic string str_txt;
         automatic logic [3:0] shadow_str_e[0:n-1];
         automatic bit err_cl, err_op, err_mk, err;

         n_u_op = 0;
         n_u_cl = 0;

         if ( i < str_special.size() ) begin

            automatic string spc = str_special[i];
            foreach ( spc[j] ) str[j] = ascii_to_char[spc[j]];
            for ( int j=spc.len(); j<n; j++ ) str[j] = Char_Blank;

         end else begin

            for ( int j=0; j<n; j++ ) str[j] = (4)'({$random} % 4);

         end

         str_txt = char_to_string( str );

         shadow_n_close_lt = 0;
         shadow_n_open_rt = 0;
         for ( int j=0; j<n; j++ ) begin
            if ( str[j] == Char_Close ) begin
              if ( shadow_n_open_rt ) shadow_n_open_rt--;
              else shadow_n_close_lt++;
            end
            if ( str[j] == Char_Open ) shadow_n_open_rt++;
         end

         n_unm_op = n_u_op;
         shadow_str_e = str;
         for ( int j=0; j<n; j++ ) begin
            if ( str[j] == Char_Close ) begin
               if ( n_unm_op > 0 ) begin
                  shadow_str_e[j] = Char_Close_Okay;
                  n_unm_op--;
               end
            end
            if ( str[j] == Char_Open ) n_unm_op++;
         end
         n_unm_cl = n_u_cl;
         for ( int j=n-1; j>=0; j-- ) begin
            if ( str[j] == Char_Open ) begin
               if ( n_unm_cl > 0 ) begin
                  shadow_str_e[j] = Char_Open_Okay;
                  n_unm_cl--;
               end
            end
            if ( str[j] == Char_Close ) n_unm_cl++;
         end

         #1;

         err_cl = n_cl_lt !== shadow_n_close_lt;
         err_op = n_op_rt !== shadow_n_open_rt;
         err_mk = mtype == M_mark && str_marked !== shadow_str_e;
         err = err_cl || err_op || err_mk;

         prefix_txt_str = $sformatf("%s '%s'",prefix_txt,str_txt);

         if ( !err && n_samples < n_samples_show ) begin
            n_samples++;
            $write("Sample %s: close = %0d,  open = %0d (both correct)\n",
                   prefix_txt_str, n_cl_lt, n_op_rt);

            if ( mtype == M_mark )
              $write("Sample %s '%s' (marked_outpuut)\n",
                     prefix_txt, char_to_string(shadow_str_e));
         end

         if ( err_cl ) begin
            n_errs_cl++;
            if ( n_errs_cl < n_errors_show )
              $write("Error %s: close  %0d != %0d (correct)\n",
                     prefix_txt_str, n_cl_lt, shadow_n_close_lt);
         end
         if ( err_op ) begin
            n_errs_op++;
            if ( n_errs_op < n_errors_show )
              $write("Error %s: open   %0d != %0d (correct)\n",
                     prefix_txt_str, n_op_rt, shadow_n_open_rt);
         end

         if ( err_mk ) begin
            n_errs_mk++;
            if ( n_errs_mk < n_errors_show ) begin
               $write("Error %s: '%s' != '%s' (correct)\n",
                      prefix_txt,
                      char_to_string(str_marked), char_to_string(shadow_str_e));
            end

         end

      end

      $write("Done with tests %s. Errors: %0d cl, %0d op, %0d mark.\n",
             prefix_txt,
             n_errs_cl, n_errs_op, n_errs_mk);

      testbench.t_errs_each_cl[mtype][n] = n_errs_cl;
      testbench.t_errs_each_op[mtype][n] = n_errs_op;
      testbench.t_errs_each_mk[mtype][n] = n_errs_mk;

      done = 1;

   end

endmodule

// cadence translate_on