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