////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2015 Homework 2 -- SOLUTION
//

 /// Assignment  http://www.ece.lsu.edu/koppel/v/2015/hw02.pdf
 /// Solution http://www.ece.lsu.edu/koppel/v/2015/hw02_sol.pdf

 /// Instructions:
  //
  // (1) Find the undergraduate workstation laboratory, room 126 EE
  //     Building.
  //
  // (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.
  //     The account should start up with a WIMP interface (windows, icons,
  //     mouse, pull-down menus)  ( :-) ) but one or two things need
  //     to be done from a command-line shell.  If you need to brush up
  //     on Unix commands follow http://www.ece.lsu.edu/koppel/v/4ltrwrd/.
  //
  // (4) If you haven't already, follow the account setup instructions here:
  //     http://www.ece.lsu.edu/koppel/v/proc.html
  //
  // (5) Copy this assignment, local path name
  //     /home/faculty/koppel/pub/ee4755/hw/2015f/hw02
  //     to a directory ~/hw02 in your class account. (~ is your home
  //     directory.) Use this file for your solution.
  //
  // (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
  //      http://standards.ieee.org/getieee/1800/download/1800-2012.pdf
  //    Introductory Treatment (Warning: Does not include SystemVerilog)
  //      Brown & Vranesic, Fundamentals of Digital Logic with Verilog, 3rd Ed.
  //
  // Account Setup and Emacs (Text Editor) Instructions
  //      http://www.ece.lsu.edu/koppel/v/proc.html
  //      To learn Emacs look for Emacs tutorial.
  //
  // Unix Help
  //      http://www.ece.lsu.edu/koppel/v/4ltrwrd/


//  `default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 0
//
 /// Minimum Modules
//
//   Look over the code below.
//   There is nothing to turn in for this problem.
//


 /// Behavioral elt_count-input Minimum Module
//
module min_b
  #( int elt_bits = 4,
     int elt_count = 8 )
   ( output logic [elt_bits-1:0] elt_min,
     input wire [elt_bits-1:0] elts[elt_count] );

   always @* begin

      elt_min = elts[0];
      
      for ( int i=1; i<elt_count; i++ )
        if ( elts[i] < elt_min ) elt_min = elts[i];

   end

endmodule


 /// Implicit Structural 2-Input Minimum Module
//
module min_2
  #( int elt_bits = 4 )
   ( output wire [elt_bits-1:0] elt_min,
     input wire [elt_bits-1:0] elt_0,
     input wire [elt_bits-1:0] elt_1 );

   assign                 elt_min = elt_0 < elt_1 ? elt_0 : elt_1;
   
endmodule

 /// Explicit Structural 4-Input Minimum Module
//
module min_4
  #( int elt_bits = 4 )
   ( output wire [elt_bits-1:0] elt_min,
     input wire [elt_bits-1:0] elts [4] );

   wire [elt_bits-1:0]    im1, im2;
   min_2 #(elt_bits) m1( im1, elts[0], elts[1] );
   min_2 #(elt_bits) m2( im2, elts[2], elts[3] );
   min_2 #(elt_bits) m3( elt_min, im1, im2 );

endmodule

//////////////////////////////////////////////////////////////////////////////
///  Problem 1 -- SOLUTION
//
 /// Linear Generate minimum module.
//
//   Complete the module.
//
//     [x] Use a generate loop.
//     [x] The code must be synthesizable.
//     [x] Make sure that the testbench does not report errors.

module min_n
  #( int elt_bits = 4,
     int elt_count = 8 )
   ( output wire [elt_bits-1:0] elt_min,
     input wire [elt_bits-1:0] elts [ elt_count ] );

   /// SOLUTION

   // Declare wires to interconnect the instances of min_2 instantiated
   // in the genvar loop.
   //
   wire [elt_bits-1:0] im[elt_count:0];  // im: Inter-Module
   assign              im[0] = elts[0];

   // Instantiate elt_count-1 min_2 modules. The inputs of the first
   // module (i=1) connect to elt[0] and elt[1]. Subsequent modules
   // connect to an elt and the module instantiated in the previous
   // iteration.
   //
   for ( genvar i = 1; i < elt_count; i++ )
     min_2 #(elt_bits) m(im[i], elts[i], im[i-1] );

   // Connect the output of the last instance to the module output.
   //
   assign        elt_min = im[elt_count-1];

endmodule


//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
 /// Tree Generate minimum module.
//
//   Complete the module.
//
//     [/] Use recursion: the module should instantiate itself or a min_2.
//     [x] The code must be synthesizable.
//     [x] Make sure that the testbench does not report errors.


module min_t
  #( int elt_bits = 4,
     int elt_count = 8 )
   ( output wire [elt_bits-1:0] elt_min,
     input [elt_bits-1:0] elts [ elt_count-1:0 ] );

   /// SOLUTION

   if ( elt_count == 1 ) begin

      // Recursion ends here with one elt. Of course, it is the
      // minimum. (And the maximum, and the average, and the median.)
      //
      assign elt_min = elts[0];

   end else begin

      // If there are at least two elements instantiate two smaller
      // modules.

      // Compute the number of elements to be handled by each
      // module. (Note that elt_count can be odd, which is why we need
      // a separate elt_hi and elt_lo.)
      //
      localparam int elt_hi = elt_count / 2;
      localparam int elt_lo = elt_count - elt_hi;

      // Wires for interconnection of modules.
      wire [elt_bits-1:0] minl, minh;

      // Recursively declare two modules.
      //
      min_t #(elt_bits,elt_hi) mhi(minl,elts[elt_count-1:elt_lo]);
      min_t #(elt_bits,elt_lo) mlo(minh,elts[elt_lo-1:0]);

      // Combine the output of the two modules above.
      //
      min_2 #(elt_bits) m2(elt_min,minl,minh);

   end

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. Of
//  course, the removal of tests which your module fails is not a
//  method of fixing a broken module. (The idea is to put in tests
//  which make it easier to determine what the problem is, for
//  example, test inputs that are all 0's or all 1's.)

// cadence translate_off

module testbench;

   testbench_sz #(1,4) t0();
   testbench_sz #(4,4) t1();
   testbench_sz #(8,32) t2();
   testbench_sz #(7,17) t3();

endmodule

module testbench_sz
  #( int elt_bits = 8,
     int elt_count = 80 );
   
   localparam int mut_cnt_max = 5;

   logic [elt_bits-1:0] elts[elt_count];

   wire [elt_bits-1:0]  elt_m[mut_cnt_max];
   struct { int err_cnt = 0; int idx; } md[string];

   min_b #(elt_bits,elt_count) m0(elt_m[0],elts);
   min_n #(elt_bits,elt_count) m1(elt_m[1],elts);
   if ( elt_count == 4 )
     min_4 #(elt_bits) m2(elt_m[2],elts);

   min_t #(elt_bits,elt_count) m3(elt_m[3],elts);
   
   localparam int num_tests = 10000;

   initial begin

      md["Linear Generate"].idx = 1;
      md["Tree Generate"].idx = 3;
      if ( elt_count == 4 )
        md["Four-Element"].idx = 2;

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

         for ( int j=0; j<elt_count; j++ ) elts[j] = $random();

         #1;

         foreach ( md[mut] ) begin

            if ( elt_m[0] !== elt_m[md[mut].idx] ) begin

               md[mut].err_cnt++;
               if ( md[mut].err_cnt < 5 )
                 $write("Error test %0d for %s, 0x%x != 0x%x (correct)\n",
                          i, mut, elt_m[md[mut].idx], elt_m[0] );
            end

         end

      end

      foreach ( md[mut] )
         $write("Tests completed for %s at %0d x %0d, error count %0d\n",
                  mut, elt_bits, elt_count, md[mut].err_cnt );

   end

endmodule

// cadence translate_on