////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2025 Homework 2
//

 /// Assignment  https://www.ece.lsu.edu/koppel/v/2025/hw02.pdf

 /// Instructions:
  //
  // (1) Find the undergraduate workstation laboratory, room 2241 Patrick
  //     F. Taylor Hall.
  //
  // (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/2025/hw02
  //     to a directory ~/hw02 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 to 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/10458102
  //    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.
  //


`default_nettype none

localparam logic [1:0] incr = 2, decr = 1;

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
  /// Complete is_sorted_to_iter.
  //  
//
//     [ ] Complete is_sorted_to_iter so that it computes the correct outputs.
//     [ ] It CAN NOT use expressions such as a[i] < a[i+1], 
//     [ ] .. instead it must use the outputs of ist_compare instantiations.
//     [ ] Use a generate loop to instantiate enough ist_compare instances.
//     [ ] The module can use procedural code, but not for comparisons.
//
//     [ ] Make sure that the testbench does not report errors.
//     [ ] The module must be synthesizable.
//
//     [ ] Code must be written clearly.
//     [ ] Pay attention to cost and performance.


module ist_compare
  #( int w = 15 )
   ( output uwire [1:0] gl, input uwire [w-1:0] a, b );
   assign gl = { a < b, a > b };
   // Do not modify this module.
endmodule

module is_sorted_to_iter
  #( int n = 12, int w = 32, int wi = $clog2(n) )
   ( output logic [wi-1:0] sidx, eidx,
     output logic [1:0] trend,
     input uwire [w-1:0] a[n-1:0] );

   // Put solution here.


endmodule


module is_sorted_to_proc
  #( int n = 12, int w = 32, int wi = $clog2(n) )
   ( output logic [wi-1:0] sidx, eidx,
     output logic [1:0] trend,
     input uwire [w-1:0] a[n-1:0] );

   // Do not modify this module.

   always_comb begin
      sidx = n-1;
      eidx = 0;
      trend = 0; // 2: increasing, 1: decreasing.
      for ( int i=1; i<n; i++ ) begin
         if ( a[i] > a[i-1] ) begin
            if ( trend == decr  ) begin sidx = i - 1; break; end
            trend = incr;
         end
         if ( a[i] < a[i-1] ) begin
            if ( trend == incr  ) begin sidx = i - 1; break; end
            trend = decr;
         end
         if ( trend == 0 ) eidx = i;
      end
   end

endmodule


//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
  /// Complete is_sorted_to_tree
  //  
//
//     [ ] Module is_sorted_to_tree must instantiate ist_compare somewhere.
//     [ ] Use recursion to form a tree.
//     [ ] Choose recursive instance sizes to simplify adders ..
//     [ ] .. for example, in expressions like " nlo + valhi ",
//     [ ] .. make constant nlo a power of 2.
//     [ ] The module can use procedural code, but not for comparisons.
//
//     [ ] Make sure that the testbench does not report errors.
//     [ ] The module must be synthesizable.
//
//     [ ] Pay attention to cost and performance.
//     [ ] Code must be written clearly.



module is_sorted_to_tree
  #( int n = 12, int w = 32, int wi = $clog2(n) )
   ( output logic [wi-1:0] sidx, eidx,
     output logic [1:0] trend,
     input uwire [w-1:0] a[n-1:0] );

   // Replace the silly code below with your solution.

   always_comb begin
      // A stopped clock is correct twice a day!
      trend = 0;
      eidx = n-1;
      sidx = n-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 no one will be
// accused of dishonesty for modifying the testbench below. If you do
// modify the testbench be sure to make sure all of the original tests
// are performed to make sure that your code passes the original
// testbench.


// cadence translate_off

// Module names. (Used by the testbench.)
//
typedef enum { M_proc, M_iter, M_tree } M_Type;

module testbench;

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

   localparam int nmsets = 3;
   localparam M_Type mset[3] = '{ M_iter, M_tree, M_proc };

   string mtype_str[M_Type] =
          '{ M_proc: "is_sorted_to_proc",
             M_iter: "is_sorted_to_iter", M_tree: "is_sorted_to_tree" };
   string mtype_abbr[M_Type] =
          '{ M_proc: "func", M_iter: "iter", M_tree: "tree" };

   int t_errs_each_tr[M_Type][int];
   int t_errs_each_sidx[M_Type][int];
   int t_errs_each_eidx[M_Type][int];
   int t_errs_tr, t_errs_sidx, t_errs_eidx;

   localparam int nsets = npsets * nmsets;

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

   initial begin
      t_errs_tr = 0;
      t_errs_sidx = 0;
      t_errs_eidx = 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_tr[mset[m]][n] = 0;
           t_errs_each_sidx[mset[m]][n] = 0;
           t_errs_each_eidx[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=%2d: Errors: %0d trend, %0d sidx, %0d eidx.\n",
                  mtype_str[m], n,
                  t_errs_each_tr[m][n],
                  t_errs_each_sidx[m][n],
                  t_errs_each_eidx[m][n]);
           t_errs_tr += t_errs_each_tr[m][n];
           t_errs_sidx += t_errs_each_sidx[m][n];
           t_errs_eidx += t_errs_each_eidx[m][n];
        end

      $write("Grand Total Errors:  %0d trend, %0d sidx, %0d eidx.\n",
             t_errs_tr, t_errs_sidx, t_errs_eidx);

   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]), .w(pset[i][1]), .mtype(mset[m]) )
        t2( .done(d[idx]), .tstart(d[idx-1]) );
     end

endmodule

module testbench_n
  #( int n = 6, w = 6, M_Type mtype = M_proc )
   ( output logic done, input uwire tstart );

   localparam int wi = $clog2(n);
   localparam int num_tests = 10000;

   logic [w-1:0] a[n-1:0];
   uwire [1:0] trend;
   uwire [wi-1:0] sidx, eidx;

   case ( mtype )
     M_proc:
       is_sorted_to_proc #(n,w) isi( sidx, eidx, trend, a );
     M_iter:
       is_sorted_to_iter #(n,w) isi( sidx, eidx, trend, a );
     M_tree:
       is_sorted_to_tree #(n,w) isi( sidx, eidx, trend, a );
   endcase

   int seed;
   initial seed = 47552025;

   function automatic bit rand_bern( int period );
      rand_bern = $dist_uniform(seed,1,period) == 1;
   endfunction

   function automatic int rand_n( int n );
      rand_n = $dist_uniform(seed,0,n-1);
   endfunction

   function automatic int rand_w( int w );
      rand_w = $dist_uniform(seed,0,2**w-1);
   endfunction


   initial begin

      automatic int n_err_trend =0, n_err_sidx = 0, n_err_eidx = 0;
      automatic string prefix_txt =
        $sformatf("%s n=%0d, w=%0d",testbench.mtype_str[mtype],n,w);
      automatic string prefix_abbr_txt =
        $sformatf("%s n=%0d, w=%0d",testbench.mtype_abbr[mtype],n,w);

      automatic string trend_str[int] =
        '{ 0: "equal", 2'b10: "increasing",
           2'b01: "decreasing", 2'b11: "Error" };
      automatic int n_samples_trend[int];

      localparam int n_samples = 2;

      bit show_sample;

      wait( tstart );

      $write("Starting tests for %s.\n", prefix_txt);

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

         bit err_trend, err_sidx, err_eidx;

         automatic int shadow_sidx = $dist_uniform(seed,1,n-1);
         automatic bit all_sorted = shadow_sidx == n - 1;

         automatic int n_distinct =
           all_sorted && rand_bern(5) ? 1 :
             shadow_sidx == 1 ? 2 : $dist_uniform(seed, 2, 2+shadow_sidx/2 );
         logic [1:0] shadow_trend;
         int shadow_eidx;
         bit all_equal;

         automatic int dist_elts[] = new [ n_distinct ];
         automatic int prefix[] = new [shadow_sidx+1];
         foreach ( dist_elts[i] ) dist_elts[i] = rand_w( w );
         // Make sure that there are at least two distinct elements.
         dist_elts.sort();
         if ( !all_sorted && dist_elts[0] == dist_elts[n_distinct-1] )
           dist_elts[0]++;
         all_equal = all_sorted && dist_elts[0] == dist_elts[n_distinct-1];
         shadow_trend = all_equal ? 0 : $dist_uniform(seed,1,2);
         foreach ( prefix[j] )
           prefix[j] = dist_elts[ j < n_distinct ? j : rand_n(n_distinct)];
         if ( shadow_trend == incr ) prefix.sort(); else prefix.rsort();
         foreach ( prefix[i] ) a[i] = prefix[i];
         if ( !all_sorted )
           a[shadow_sidx+1] = shadow_trend == incr
             ? a[shadow_sidx] - 1 : a[shadow_sidx] + 1;
         for ( int i=shadow_sidx+2; i<n; i++ ) a[i] = rand_w(w);

         for ( int j=0; j<n; j++ )
           if ( a[j] == a[0] ) shadow_eidx = j; else break;

         #1;

         err_trend = shadow_trend !== trend;
         err_sidx = shadow_sidx !== sidx;
         err_eidx = shadow_eidx !== eidx;
         if ( err_trend ) n_err_trend++;
         if ( err_sidx ) n_err_sidx++;
         if ( err_eidx ) n_err_eidx++;

         show_sample = 0;

         if ( err_trend && n_err_trend < 5 ) begin
            show_sample = 1;
            $write( "Error trend %b != %b (correct)\n", trend, shadow_trend);
         end
         if ( err_sidx && n_err_sidx < 5 ) begin
            show_sample = 1;
            $write( "Error sidx %0d != %0d (correct)\n", sidx, shadow_sidx);
         end
         if ( err_eidx && n_err_eidx < 5 ) begin
            show_sample = 1;
            $write( "Error eidx %0d != %0d (correct)\n", eidx, shadow_eidx);
         end

         if ( !show_sample && n_samples_trend[shadow_trend] < n_samples ) begin
            show_sample = 1;
            $write( "Output below is correct, it shows trend %2b -- %s.\n",
                    shadow_trend, trend_str[shadow_trend] );
         end

         if ( show_sample ) begin
            n_samples_trend[shadow_trend]++;
            for ( int j=0; j<n; j++ ) begin
               $write(" %2d%0s",
                      j, j == shadow_eidx && j == shadow_sidx ? "es" :
                      j == shadow_eidx ? "e" :
                      j == shadow_sidx ? "s" : " " );
            end
            $write("\n");
            for ( int j=0; j<n; j++ ) begin
               $write(" %3d",a[j]);
            end
            $write("\n");
         end

      end

      $write("Did %0d tests of %s. Errors %0d trend, %0d sidx, %0d eidx.\n",
             num_tests, prefix_abbr_txt, n_err_trend, n_err_sidx, n_err_eidx);

      testbench.t_errs_each_tr[mtype][n] = n_err_trend;
      testbench.t_errs_each_sidx[mtype][n] = n_err_sidx;
      testbench.t_errs_each_eidx[mtype][n] = n_err_eidx;

      done = 1;

   end

endmodule

// cadence translate_on