////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2016 Homework 4
//

 /// Assignment  http://www.ece.lsu.edu/koppel/v/2016/hw04.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.
  //
  // (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/2016/hw04
  //     to a directory ~/hw04 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.


`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 0
//
 //  Look over but don't modify this module.


module lookup_behav
  #( int charsz = 8,
     int nelts = 15,
     int idx_sz = $clog2(nelts) )
   ( output logic found,
     output logic [idx_sz-1:0] index,
     input uwire [charsz-1:0] char,
     input uwire [charsz-1:0] chars[nelts] );

   always_comb begin
      found = 0;
      index = 0;
      for ( int i=0; i<nelts; i++ )
        if ( chars[i] == char ) begin
           index = i;
           found = 1;
        end
   end

endmodule


//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
 /// Complete lookup_linear so that it does the lookup using instantiated lookup_elt.
//
//     [ ] The code must be synthesizable.
//     [ ] The code must synthesize to combinational logic. (No latches.)
//     [ ] Make sure that the testbench does not report errors.
//     [ ] Can use behavioral or implicit structural code.
//     [ ] Do not rename modules or change ports.


module lookup_elt
  #( int charsz = 4 )
   ( output logic match,
     input uwire [charsz-1:0] char_lookup,
     input uwire [charsz-1:0] char_elt);
   /// Don't modify this module.
   always_comb match = char_lookup == char_elt;

endmodule

module lookup_linear
  #( int charsz = 8,
     int nelts = 15,
     int idx_sz = $clog2(nelts) )
   ( output logic found,
     output logic [idx_sz-1:0] index,
     input uwire [charsz-1:0] char,
     input uwire [charsz-1:0] chars[nelts-1:0] );

   /// Solution goes here.



endmodule


//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
 /// Complete lookup_tree so that it does the lookup using recursive
 /// instantiations of itself.
//
//     [ ] The code must be synthesizable.
//     [ ] The code must synthesize to combinational logic. (No latches.)
//     [ ] Make sure that the testbench does not report errors.
//     [ ] Can use behavioral or implicit structural code.
//     [ ] Do not rename modules or change ports.


module lookup_tree
  #( int charsz = 8,
     int nelts = 15,
     int idx_sz = $clog2(nelts) )
   ( output uwire found,
     output uwire [idx_sz-1:0] index,
     input uwire [charsz-1:0] char,
     input uwire [charsz-1:0] chars[nelts] );

   /// Solution goes here.



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. (One might modify the testbench
//  so that the first tests it performs are thoe 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

function automatic int min( int a, int b );
         min = a <= b ? a : b;
endfunction

module testbench();

   localparam int nelts[] = { 4, 5, 10, 15,  16, 30, 40, 64 };
   localparam int nnelts = 8;

   logic      start_done[-1:nnelts];

   for ( genvar i = 0; i < nnelts; i++ )
     testbench_sz #(nelts[i]) aa(start_done[i],start_done[i-1]);

   initial begin

      if ( nnelts != nelts.size() ) begin
        $write("Value of nnelts, %0d, different than number of elts in nelts, %0d. (See module testbench.\n",
               nnelts, nelts.size());
         $fatal(1);
      end

      start_done[-1] = 1;

   end

endmodule

module testbench_sz
  #( int nelts = 100 )
   ( output logic done, input uwire start );

   localparam int telts = nelts * 2;
   localparam int idx_sz = $clog2(nelts);
   localparam int charsz = 8;
   localparam int charmk = ( 1 << charsz ) - 1;

   localparam int num_tests = min(nelts,500);
   localparam int stride = nelts/num_tests;
   localparam int nmuts = 3;

   logic [charsz-1:0] char, chars[telts-1:0];

   uwire              found[nmuts];
   uwire [idx_sz-1:0] idx[nmuts];
   logic              shadow_found;
   logic [idx_sz-1:0] shadow_idx;

   lookup_behav #(charsz,nelts) l00(found[0],idx[0],char,chars[nelts-1:0]);
   lookup_linear #(charsz,nelts) l01(found[1],idx[1],char,chars[nelts-1:0]);
   lookup_tree #(charsz,nelts) l02(found[2],idx[2],char,chars[nelts-1:0]);

   string mutnames[] = { "lookup_behav", "lookup_linear", "lookup_tree" };

   int err[nmuts];

   initial begin

      automatic int tot_errors = 0;
      localparam int gap = charmk / telts;
      chars[0] = {$random} % gap;
      for ( int i=1; i<telts; i++ )
        chars[i] = chars[i-1] + 1 + {$random} % gap;
      for ( int i=0; i<telts; i++ ) begin
         automatic int idx = {$random} % telts;
         {chars[i],chars[idx]} = {chars[idx],chars[i]};
      end

      wait ( start == 1 );

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

         automatic int idx_try = {$random} % telts;
         char = chars[idx_try];
         shadow_found = idx_try < nelts;
         shadow_idx = idx_try;
         #1;

         for ( int mut=0; mut<3; mut++ ) begin

            automatic int cr_fnd = shadow_found === found[mut];
            automatic int cr_idx = shadow_idx === idx[mut];

            if ( cr_fnd && ( shadow_found == 0 || cr_idx ) ) continue;
            if ( err[mut] > 100 ) break;

            $write("Mod %s nelts %0d test %3d char %h: wrong %s. Found %h%s%h (correct) idx %4d %s %4d (correct)\n",
                   mutnames[mut], nelts, i, char,
                   cr_idx ? "found" : "index",
                   found[mut],
                   cr_fnd ? "==" : "!=",
                   shadow_found,
                   idx[mut], cr_fnd ? "!=" : "??", shadow_idx);

            err[mut]++;

         end

      end
      for ( int i=0; i<num_tests; i++ ) tot_errors += err[i];
      $write("For nelts %0d performed %0d tests, %0d errors found.\n",
             nelts, num_tests, tot_errors);

      done = 1;
   end

endmodule

// cadence translate_on