```////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2019 Homework 2 -- SOLUTION
//

/// Assignment  https://www.ece.lsu.edu/koppel/v/2019/hw02.pdf
/// Solution Problem 2:  https://www.ece.lsu.edu/koppel/v/2019/hw02_sol.pdf

`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
///    Complete clz_tree so that it computes the clz of its input recursively.
//
//     [✔] Split the input between two recursive instantiations ..
//         .. and properly combine the results.
//     [✔] Don't forget the terminal case, maybe for w == 1.
//     [✔] For maximum credit, avoid any use of adders ..
//         .. by making the width of the "hi" module a power of 2.
//
//     [✔] Make sure that port connections are the correct size ..
//         .. mismatched ports are Verilog errors in this assignment.
//     [✔] Do not make port widths larger than needed.
//     [✔] Module must be synthesizable. Use command: genus -files syn.tcl
//
//     [✔] As always, avoid costly, slow, and confusing code.

/// Solution Discussion
//
// Two solutions appear below.
//
// The clz_tree_fat module is much simpler, but it uses an adder.
// Two points would be deducted if this were given as a solution
//
// The clz_tree module does not use an adder. It would get full credit.

/// SOLUTION -- With Adder. Two points would be deducted.
module clz_tree_fat
#( int w = 19,
int ww = \$clog2(w+1) )
( output uwire [ww:1] nlz,
input uwire [w:1] a );

if ( w == 1 ) begin

assign nlz = ~ a;

end else begin

localparam int wlo = w/2;
localparam int whi = w - wlo;
localparam int wwlo = \$clog2(wlo+1);
localparam int wwhi = \$clog2(whi+1);

uwire [wwlo:1] lz_lo;
uwire [wwhi:1] lz_hi;

clz_tree_fat #(wlo) clo( lz_lo, a[wlo:1]   );
clz_tree_fat #(whi) chi( lz_hi, a[w:wlo+1] );

assign nlz = lz_hi < whi ? lz_hi : whi + lz_lo;

end

endmodule

module clz_tree
#( int w = 19,
int ww = \$clog2(w+1) )
( output uwire [ww-1:0] nlz,
input uwire [w-1:0] a );

if ( w == 1 ) begin

assign nlz = !a[0];

end else if ( w == 2 ) begin

assign nlz = { !a[0] && !a[1], !a[1] && a[0] };

end else begin

// Set whi to the largest power of 2 strictly less than w.
//
localparam int lhi = \$clog2(w) - 1;
localparam int whi = 1 << lhi;
localparam int wwhi = lhi + 1;

// Then set wlo to the number of remaining bits.
//
localparam int wlo = w - whi;
localparam int wwlo = \$clog2(wlo+1);

uwire [wwlo-1:0] nlz_lo;
uwire [wwhi-1:0] nlz_hi;

// Instantiate recursive modules.
//
clz_tree #(wlo) clo( nlz_lo, a[wlo-1:0] );
clz_tree #(whi) chi( nlz_hi, a[w-1:wlo] );

// Split the nlz_lo and nlz_hi outputs into "overflow" bits,
// ov_lo and ov_hi, and the remaining bits lz_lo and lz_hi.
// There is no overflow bit if the size is not a power of two.
// Because whi is always a power of two it will always have an
// overflow bit.
//
uwire ov_lo, ov_hi;
uwire [lhi-1:0] lz_lo, lz_hi;

// The hi bits are easy because there's always an overflow.
assign {ov_hi,lz_hi} = nlz_hi;

if ( wlo == whi ) assign {ov_lo,lz_lo} = nlz_lo;
else              assign lz_lo = nlz_lo;

// If the high bits are all zeros, use the count from the lo
// bits and then further below effectively add whi to nlz.
//
assign nlz[lhi-1:0] = ov_hi ? lz_lo : lz_hi;

//
// The first case, wlo==whi, is for when both wlo and whi (and
// w) are all powers of two. In that case we must compute two
// more bits of nlz. If ov_hi is zero they are both zero because
// the number of leading zeros will be strictly less than whi.
// If ov_hi is one then the high two bits will be 1 + ov_lo.
//
// In the second case, (the else which means whi>wlo), there is
// no ov_lo bit. So the most significant bit is 0 if ov_hi is
// zero and 1 if ov_hi is one.

if ( wlo == whi )
assign nlz[lhi+1:lhi] = ov_hi ? { ov_lo, !ov_lo } : 2'b0;
else
assign nlz[lhi] = ov_hi;

end

endmodule

/// A Behavioral CLZ Description
module clz
#( int w = 19,
int ww = \$clog2(w+1) )
( output var logic [ww-1:0] nlz,
input uwire logic [w-1:0] a );

uwire [w:0] aa = { a, 1'b1 };
always_comb for ( int i=0; i<=w; i++ ) if ( aa[i] ) nlz = w-i;

endmodule

//////////////////////////////////////////////////////////////////////////////
/// Testbench Code

module testbench;

// The widths (values of w) at which the modules will be instantiated.
//
localparam int widths[] = { 1, 2, 5, 8, 13, 15, 17 };

//  localparam int nw = widths.size();
initial if ( nw != widths.size() )
\$fatal(1,"Constant nw should be %0d.\n",widths.size() );

int t_errs;     // Total number of errors.
initial t_errs = 0;
final \$write("Total number of errors: %0d\n",t_errs);

uwire d[nw:-1];    // Start / Done signals.
assign d[-1] = 1;  // Initialize first at true.

// Instantiate a testbench at each size.
//
for ( genvar i=0; i<nw; i++ )
testbench_n #(widths[i]) t2( .done(d[i]), .start(d[i-1]) );

endmodule

module testbench_n
#( int w = 20 )
( output logic done, input uwire start );

localparam int ww = \$clog2(w+1);

localparam int n_tests = w * 10;

uwire [ww:1] nlz;
logic [w-1:0] a;
clz_tree_fat #(w) c0(nlz,a);
//  clz #(w) c0(nlz,a);

initial begin

automatic int n_errs = 0;

wait( start );

\$write("** Starting tests for width %0d.\n",w);

for ( int t=0; t<n_tests; t++ ) begin

automatic int lz = {t} % ( w + 1 );
a = { 1'b1, (w)'({\$random}) } >> ( lz + 1 );

#1;

if ( nlz !== lz ) begin
n_errs++; testbench.t_errs++;
if ( testbench.t_errs < 5 || n_errs < 2 )
\$write("Error for width %2d: input %h:  %d != %0d (correct).\n",
w, a, nlz, lz);
end

end

\$write("Width %0d, done with %0d tests, %0d errors.\n",w,n_tests,n_errs);

done = 1;

end

endmodule