```////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2018 Homework 1
//
/// Live version, solved in class 20 September 2021.

/// Assignment  https://www.ece.lsu.edu/koppel/v/2018/hw01.pdf

`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  Problem 1
//
/// Modify sort2 so that it implements a 2-input sorting network ..
/// .. using explicitly structural code only.
//
//     [✔] Use structural code only ..
//     [✔] .. instantiate mux2 and compare_le as needed.
//     [✔] Pay attention to bit widths.
//     [ ] Module must be synthesizable. Use command: genus -files syn.tcl

module sort2
#( int w = 8 )
( output uwire [w-1:0] x0, x1,
input uwire [w-1:0] a0, a1 );

/// Place Problem 1 Solution Here

uwire s, sn;
mux2 #(w) m1(x0,s,a0,a1);
mux2 #(w) m2(x1,sn,a0,a1);

compare_le #(w) le(s,a1,a0);
not n1(sn,s);

endmodule

module mux2
#( int w = 4 )
( output uwire [w-1:0] x,
input uwire select,
input uwire [w-1:0] a0, a1 );
assign x = select ? a1 : a0;
endmodule

module compare_le
#( int w = 2 )
( output uwire c,
input uwire [w-1:0] a, b );
assign c = a <= b;
endmodule

//////////////////////////////////////////////////////////////////////////////
///  Problem 2
//
/// Modify sort4 so that it implements a 4-input sorting network ..
/// .. using explicitly structural code only.  See sort3 below.
//
//     [✔] Use structural code only.
//     [✔] Instantiate only sort2, sort2_is, and sort3 modules.
//     [✔] Pay attention to bit widths.
//     [ ] Module must be synthesizable. Use command: genus -files syn.tcl
//     [✔] The critical path length should be 4 or fewer sort2 modules.

module sort4
#( int w = 8 )
( output uwire [w-1:0] x0, x1, x2, x3,
input uwire [w-1:0] a0, a1, a2, a3 );

// Put solution here.

uwire [w-1:0] l01,m01,l23,m23,x12a,x12b;
sort2 #(w) s01(l01,m01,a0,a1);
sort2 #(w) s23(l23,m23,a2,a3);
sort2 #(w) sx2(x0,x12a,l01,l23);
sort2 #(w) sx3(x12b,x3,m01,m23);
sort2 #(w) s24(x1,x2,x12a,x12b);

endmodule

// Correctly functioning 2-input sorter.
module sort2_is
#( int w = 8 )
( output uwire [w-1:0] x0, x1,
input uwire [w-1:0] a0, a1 );

assign {x0, x1} = a0 <= a1 ? { a0, a1 } : { a1, a0 };

endmodule

module sort3
#( int w = 8 )
( output uwire [w-1:0] x0, x1, x2,
input uwire [w-1:0] a0, a1, a2 );

uwire [w-1:0] i10, i11, i21;

sort2_is #(w) s0_01( i10, i11,   a0, a1 );
sort2_is #(w) s1_12( i21, x2,  i11, a2  );
sort2_is #(w) s2_01( x0, x1,  i10, i21  );

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. For
//  example, 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.
//
//  Of course, the removal of tests which your module fails is not a
//  method of fixing a broken module.  The TA-bot will test your
//  code using a fresh copy of the testbench, not the one below.

module sortx
#( int max_size = 5,
int modnum = 0,
int w = 8,
int max_muts = 3)
( output uwire [w-1:0] xlong[max_muts][max_size],
input uwire [w-1:0] a[max_size] );

uwire [w-1:0] x[max_size];
assign xlong[modnum] = x;

if ( modnum == 0 ) begin:A

localparam int s_size = 2;
localparam string name = "sort2";
sort2 #(w) s(x[0],x[1],a[0],a[1]);

end else if ( modnum == 1 ) begin:A

localparam int s_size = 2;
localparam string name = "sort2_is";
sort2_is #(w) s(x[0],x[1],a[0],a[1]);

end else if ( modnum == 2 ) begin:A

localparam int s_size = 3;
localparam string name = "sort3";
sort3 #(w) s(x[0],x[1],x[2],a[0],a[1],a[2]);

end else begin:A

localparam int s_size = 4;
localparam string name = "sort4";
sort4 #(w) s(x[0],x[1],x[2],x[3],a[0],a[1],a[2],a[3]);

end

endmodule

module testbench;

localparam int w = 8;
localparam int n_tests = 100;
localparam int max_size = 4;
localparam int max_muts = 4;

logic [w-1:0] a[max_size];
uwire [w-1:0] x[max_muts][max_size];

typedef struct { int idx; string name; int s_size; } Info;
Info pi[\$];

for ( genvar i=0; i<4; i++ ) begin
sortx #(max_size,i,w,max_muts) s(x,a);
initial pi.push_back( '{ i, s.A.name, s.A.s_size} );
end

initial begin

// Initialize the input to a recognizable pattern, which should
// be overwritten but if not, we can tell. If we print the value in
// hex.
for ( int e = 0; e < max_size; e++ ) a[e] = 'haaaaaaaa;

foreach ( pi[idx] ) begin

automatic int g_elt_err_count = 0;
automatic int g_sort_err_count = 0;
automatic Info p = pi[idx];
automatic string mut = p.name;
automatic int s_size = p.s_size;
automatic logic [w-1:0] shadow[] = new[s_size];

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

automatic int this_elt_err_count = 0;

// To make sure that the comparison is correct restrict the
// key to a subset of bits.
automatic int n_bits = {\$random} % w + 1;
automatic int mask = ( 1 << n_bits ) - 1;

for ( int i=0; i<w; i++ ) begin
automatic int b = {\$random} % w;
end

for ( int e = 0; e < s_size; e++ )

#1;

for ( int e = 0; e < s_size; e++ ) begin
automatic logic [w-1:0] elt = x[p.idx][e];
if ( shadow[e] === elt ) continue;
this_elt_err_count++;
g_elt_err_count++;
if ( g_elt_err_count > 5 ) continue;
\$write
("Mod %s, sort %2d index %2d, wrong elt %d != %d (correct)\n",
end

if ( this_elt_err_count ) g_sort_err_count++;

end

\$write("Tests for %s done, errors in %d of %d sorts.\n",
mut,  g_sort_err_count, n_tests);

end

end

endmodule