////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2017 Homework 5 -- SOLUTION
//

 /// Assignment  http://www.ece.lsu.edu/koppel/v/2017/hw05.pdf

`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
 /// Complete so that lookup_char finds index of character.
//
//     [✔] Module must be synthesizable.
//     [✔] Code must be reasonably efficient.
//     [✔] Do not change module parameters.
//     [✔] Do not change ports, EXCEPT changing between var and net kinds.
//     [✔] The module must synthesize into combinational logic (no latches).
//     [✔] Don't assume that parameter values will match those used here.
//     [✔] See a 2016 homework assignment.

module lookup_char
  #( int w = 4,
     int n = 3,
     logic [w-1:0] chars[n] = '{ "a", "2", "g" },
     int c = $clog2(n) )
   ( output logic found,
     output logic [c-1:0] idx,
     input uwire [w-1:0] char );

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

endmodule

//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
 /// Complete so that nest checks for properly nested characters.
//
//     [✔] Use lookup_char in nest.
//     [✔] Module must be synthesizable.
//     [✔] Code must be reasonably efficient.
//     [✔] Do not change module parameters.
//     [✔] Do not change ports, EXCEPT changing between var and net kinds.
//     [✔] Outputs bad, level, and awaiting should change on positive clk edge.
//     [✔] Don't assume that parameter values will match those used here.


module nest
  #( int d = 8,
     int w = 8,
     int n = 2,
     logic [w-1:0] char_open[n] = { 1, 2 },
     logic [w-1:0] char_close[n] = { 3, 4 },
     int dw = $clog2(d+1) )
  ( output logic [dw-1:0] level,
    output uwire [w-1:0] awaiting,
    output uwire is_open, is_close,
    output logic bad,
    input uwire clk, reset,
    input uwire [w-1:0] in_char );

   localparam int nw = $clog2(n);

   uwire [nw-1:0] loidx, lcidx;

   lookup_char #(w,n,char_open) l1(is_open,loidx,in_char);
   lookup_char #(w,n,char_close) l2(is_close,lcidx,in_char);

   logic [nw-1:0] stack [1:d];

   assign awaiting = char_close[stack[level]];

   always_ff @( posedge clk ) begin

      if ( reset ) begin

         level = 0;
         bad = 0;

      end else begin

         if ( is_open ) begin

            if ( level == d ) bad = 1;
            level++;
            stack[level] = loidx;

         end else if ( is_close ) begin

            if ( awaiting != in_char || !level ) bad = 1;
            level--;

         end

      end

   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. (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.)


// cadence translate_off

program reactivate
   (output uwire clk_reactive, output int cycle_reactive,
    input uwire clk, input var int cycle);
   assign clk_reactive = clk;
   assign cycle_reactive = cycle;
endprogram


module testbench;

   localparam int w = 8;
   localparam int max_depth = 6;
   localparam int dw = $clog2(max_depth);

   // Maximum number of groups for which to show traces.
   //
   localparam int show_groups_bad = 3;
   localparam int show_groups_good = 2;

   localparam int num_seq = 1000;

   localparam int cycle_limit = num_seq * 1000;

   localparam logic [w-1:0] char_open[] =  { "(", "[", "{", "<" };
   localparam logic [w-1:0] char_close[] = { ")", "]", "}", ">" };
   localparam int num_pairs = 4;

   initial begin
      if ( num_pairs != char_open.size() )
        $error("Size of char_open, %0d, different than num_pairs., %0d",
               char_open.size(), num_pairs);
   end

   uwire is_op, is_cl, bad;
   logic [w-1:0] in_char;
   uwire [w-1:0] await;
   logic [dw-1:0] lev;

   logic clock, reset;
   bit done;
   int cycle;

   logic clk_reactive;
   int cycle_reactive;
   reactivate ra(clk_reactive,cycle_reactive,clock,cycle);

   int num_tests, errs_bad, errs_op, errs_cl, errs_lv, errs_await;

   initial begin

      clock = 0;
      cycle = 0;

      fork
         forever #10 cycle += clock++;
         wait( done );
         wait( cycle >= cycle_limit )
           $write("*** Cycle limit exceeded, ending.\n");
      join_any;

      $write
        ("End of %0d tests, errors: %0d + %0d + %0d + %0d + %0d = %0d\n",
         num_tests,
         errs_op, errs_cl, errs_bad, errs_lv, errs_await,
         errs_op + errs_cl + errs_bad + errs_lv + errs_await );

      $finish();
   end


   nest #(max_depth,w,num_pairs,char_open,char_close)
   n1(lev, await, is_op, is_cl, bad, clock, reset, in_char );

   localparam string oe[] = '{"  ","er"};
   logic [w-1:0] chars_plain[$];
   bit chars_br[int];
   int nchars_plain;

   initial begin

      automatic int groups_good_count = 0;
      automatic int groups_bad_count = 0;

      num_tests = 0;
      errs_bad = 0;
      errs_op = 0;
      errs_cl = 0;
      errs_lv = 0;
      errs_await = 0;

      foreach ( char_open[c] ) chars_br[c] = 1;
      foreach ( char_close[c] ) chars_br[c] = 1;
      for ( int i=0; i<26; i++ ) begin
         chars_plain.push_back("A" + i);
         chars_plain.push_back("a" + i);
      end

      nchars_plain = chars_plain.size();

      done = 0;
      reset = 0;
      in_char = 0;

      @( negedge clk_reactive );

      for ( int s=0; s<num_seq; s++ ) begin

         automatic int targ_depth = {$random} % max_depth;
         automatic int curr_depth = 0;
         automatic int stack[$];
         automatic bit hit_target = 0;
         automatic bit back_to_0 = 0;
         automatic int c = 0;
         automatic bit shadow_bad = 0;
         automatic bit botch_close = {$random} % 2;
         automatic int bad_cyc = 0;
         automatic byte shadow_await;
         automatic string trace_text[$];
         automatic int some_err = 0;
         automatic bit err_op;
         automatic bit err_cl;

         trace_text.push_back("\n");

         reset = 1;
         @( negedge clock );
         @( negedge clock );
         reset = 0;

         while ( !back_to_0 && c < 100 && bad_cyc < 3 ) begin

            automatic bit plain = {$random} & 1;

            automatic bit b_open
              = {$random} & 'hff > ( hit_target ? 'hc0 : 'h40 );

            if ( plain ) begin

               in_char = chars_plain[ {$random} % nchars_plain ];

            end else begin

               automatic int idx = {$random} % num_pairs;

               if ( b_open ) begin

                  in_char = char_open[ idx ];
                  curr_depth++;
                  stack.push_back(idx);
                  if ( curr_depth == targ_depth ) hit_target = 1;
                  if ( curr_depth > max_depth ) shadow_bad = 1;

               end else begin

                  automatic bit botch_this_close
                    = botch_close && {$random} & 'hff > 'h40;
                  automatic int tos = curr_depth > 0 ? stack.pop_back() : idx;
                  in_char
                    = char_close[ botch_this_close ? (tos+1)%num_pairs : tos ];
                  if ( curr_depth == 0 || botch_this_close ) shadow_bad = 1;
                  curr_depth--;
                  if ( curr_depth == 0 && hit_target ) back_to_0 = 1;

               end
            end

            shadow_await = char_close[stack.size() ? stack[stack.size()-1] : 0];

            #1;

            err_op = is_op !== ( !plain && b_open );
            err_cl = is_cl !== ( !plain && !b_open );

            @( posedge clk_reactive );

            begin

               automatic bit checkable = !bad && !shadow_bad;

               automatic bit err_bad = bad !== shadow_bad;
               automatic bit err_lv = checkable && lev !== curr_depth;
               automatic bit err_await
                 = checkable && lev && await !== shadow_await;
               string tr_txt;

               if ( err_op || err_cl || err_bad || err_lv || err_await )
                 some_err++;

               num_tests++;
               errs_op += err_op;
               errs_cl += err_cl;
               errs_bad += err_bad;
               errs_lv += err_lv;
               errs_await += err_await;

               if ( !checkable ) bad_cyc++;

               tr_txt
                 = $sformatf
                   ("cyc %4d  s.c %2d.%2d  %1s  op %1h %2s  cl %1h %2s  bad %1h %2s  lev %2d %2d %2s  await '%1s%1s' %2s\n",
                    cycle, s, c, in_char,
                    is_op, oe[err_op],
                    is_cl, oe[err_cl],
                    bad, oe[err_bad],
                    lev, curr_depth, oe[err_lv],
                    await, shadow_await, oe[err_await] );

               trace_text.push_back(tr_txt);

               if ( some_err && groups_bad_count < show_groups_bad )
                 while ( trace_text.size() ) $write( trace_text.pop_front() );
            end

            c++;
            @( negedge clock );
         end

         if ( !some_err && groups_good_count < show_groups_good )
                 while ( trace_text.size() ) $write( trace_text.pop_front() );

         if ( some_err ) groups_bad_count++; else groups_good_count++;

      end

      done = 1;

   end


endmodule

// cadence translate_on