////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2018 Homework 1
//
 /// Live version, solved in class 20 September 2021.

 /// Assignment  https://www.ece.lsu.edu/koppel/v/2018/hw01.pdf

`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
 /// Modify sort2 so that it implements a 2-input sorting network ..
 /// .. using explicitly structural code only.
//
//     [✔] Make sure that the testbench does not report errors.
//     [✔] Use structural code only ..
//     [✔] .. instantiate mux2 and compare_le as needed.
//     [✔] Pay attention to bit widths.
//     [ ] Module must be synthesizable. Use command: genus -files syn.tcl


module sort2
  #( int w = 8 )
   ( output uwire [w-1:0] x0, x1,
     input uwire [w-1:0] a0, a1 );

   /// Place Problem 1 Solution Here

   uwire s, sn;
   mux2 #(w) m1(x0,s,a0,a1);
   mux2 #(w) m2(x1,sn,a0,a1);

   compare_le #(w) le(s,a1,a0);
   not n1(sn,s);

endmodule

module mux2
  #( int w = 4 )
   ( output uwire [w-1:0] x,
     input uwire select,
     input uwire [w-1:0] a0, a1 );
   assign x = select ? a1 : a0;
endmodule

module compare_le
  #( int w = 2 )
   ( output uwire c,
     input uwire [w-1:0] a, b );
   assign c = a <= b;
endmodule



//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
 /// Modify sort4 so that it implements a 4-input sorting network ..
 /// .. using explicitly structural code only.  See sort3 below.
//
//     [✔] Make sure that the testbench does not report errors.
//     [✔] Use structural code only.
//     [✔] Instantiate only sort2, sort2_is, and sort3 modules.
//     [✔] Pay attention to bit widths.
//     [ ] Module must be synthesizable. Use command: genus -files syn.tcl
//     [✔] The critical path length should be 4 or fewer sort2 modules.

module sort4
  #( int w = 8 )
   ( output uwire [w-1:0] x0, x1, x2, x3,
     input uwire [w-1:0] a0, a1, a2, a3 );

   // Put solution here.

   uwire [w-1:0] l01,m01,l23,m23,x12a,x12b;
   sort2 #(w) s01(l01,m01,a0,a1);
   sort2 #(w) s23(l23,m23,a2,a3);
   sort2 #(w) sx2(x0,x12a,l01,l23);
   sort2 #(w) sx3(x12b,x3,m01,m23);
   sort2 #(w) s24(x1,x2,x12a,x12b);


endmodule



// Correctly functioning 2-input sorter.
module sort2_is
  #( int w = 8 )
   ( output uwire [w-1:0] x0, x1,
     input uwire [w-1:0] a0, a1 );

   assign {x0, x1} = a0 <= a1 ? { a0, a1 } : { a1, a0 };

endmodule

module sort3
  #( int w = 8 )
   ( output uwire [w-1:0] x0, x1, x2,
     input uwire [w-1:0] a0, a1, a2 );

   uwire [w-1:0] i10, i11, i21;

   sort2_is #(w) s0_01( i10, i11,   a0, a1 );
   sort2_is #(w) s1_12( i21, x2,  i11, a2  );
   sort2_is #(w) s2_01( x0, x1,  i10, i21  );

endmodule



//////////////////////////////////////////////////////////////////////////////
/// Testbench Code
//
//  The code below instantiates some of the modules above,
//  provides test inputs, and verifies the outputs.
//
//  The testbench may be modified to facilitate your solution. For
//  example, one might modify the testbench so that the first tests it
//  performs are those which make it easier to determine what the
//  problem is, for example, test inputs that are all 0's or all 1's.
//
//  Of course, the removal of tests which your module fails is not a
//  method of fixing a broken module.  The TA-bot will test your
//  code using a fresh copy of the testbench, not the one below.


// cadence translate_off

module sortx
  #( int max_size = 5,
     int modnum = 0,
     int w = 8,
     int max_muts = 3)
   ( output uwire [w-1:0] xlong[max_muts][max_size],
     input uwire [w-1:0] a[max_size] );

   uwire [w-1:0] x[max_size];
   assign xlong[modnum] = x;

   if ( modnum == 0 ) begin:A

      localparam int s_size = 2;
      localparam string name = "sort2";
      sort2 #(w) s(x[0],x[1],a[0],a[1]);

   end else if ( modnum == 1 ) begin:A

      localparam int s_size = 2;
      localparam string name = "sort2_is";
      sort2_is #(w) s(x[0],x[1],a[0],a[1]);

   end else if ( modnum == 2 ) begin:A

      localparam int s_size = 3;
      localparam string name = "sort3";
      sort3 #(w) s(x[0],x[1],x[2],a[0],a[1],a[2]);

   end else begin:A

      localparam int s_size = 4;
      localparam string name = "sort4";
      sort4 #(w) s(x[0],x[1],x[2],x[3],a[0],a[1],a[2],a[3]);

   end

endmodule


module testbench;

   localparam int w = 8;
   localparam int n_tests = 100;
   localparam int max_size = 4;
   localparam int max_muts = 4;

   logic [w-1:0] a[max_size];
   uwire [w-1:0] x[max_muts][max_size];

   typedef struct { int idx; string name; int s_size; } Info;
   Info pi[$];

   for ( genvar i=0; i<4; i++ ) begin
      sortx #(max_size,i,w,max_muts) s(x,a);
      initial pi.push_back( '{ i, s.A.name, s.A.s_size} );
   end

   initial begin

      // Initialize the input to a recognizable pattern, which should
      // be overwritten but if not, we can tell. If we print the value in
      // hex.
      for ( int e = 0; e < max_size; e++ ) a[e] = 'haaaaaaaa;

      foreach ( pi[idx] ) begin

         automatic int g_elt_err_count = 0;
         automatic int g_sort_err_count = 0;
         automatic Info p = pi[idx];
         automatic string mut = p.name;
         automatic int s_size = p.s_size;
         automatic logic [w-1:0] shadow[] = new[s_size];

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

            automatic int this_elt_err_count = 0;

            // To make sure that the comparison is correct restrict the
            // key to a subset of bits.
            automatic int n_bits = {$random} % w + 1;
            automatic int mask = ( 1 << n_bits ) - 1;

            for ( int i=0; i<w; i++ ) begin
               automatic int b = {$random} % w;
               {mask[b],mask[i]} = {mask[i],mask[b]};
            end

            for ( int e = 0; e < s_size; e++ )
              begin a[e] = {$random} & mask; shadow[e] = a[e]; end

            #1;

            shadow.sort();

            for ( int e = 0; e < s_size; e++ ) begin
               automatic logic [w-1:0] elt = x[p.idx][e];
               if ( shadow[e] === elt ) continue;
               this_elt_err_count++;
               g_elt_err_count++;
               if ( g_elt_err_count > 5 ) continue;
               $write
                 ("Mod %s, sort %2d index %2d, wrong elt %d != %d (correct)\n",
                  mut,i, e, elt, shadow[e]);
            end

            if ( this_elt_err_count ) g_sort_err_count++;

         end

         $write("Tests for %s done, errors in %d of %d sorts.\n",
                mut,  g_sort_err_count, n_tests);

      end

   end

endmodule

// cadence translate_on