```////////////////////////////////////////////////////////////////////////////////
//
/// 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,
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;

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

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_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

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 );

\$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;

num_tests = 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 botch_close = {\$random} % 2;
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;

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 ];
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 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_lv += err_lv;
errs_await += err_await;

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],
lev, curr_depth, oe[err_lv],

trace_text.push_back(tr_txt);

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