`default_nettype none
module sort2
#( int w = 8 )
( output uwire [w-1:0] x0, x1,
input uwire [w-1:0] a0, a1 );
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
module sort4
#( int w = 8 )
( output uwire [w-1:0] x0, x1, x2, x3,
input uwire [w-1:0] a0, a1, a2, a3 );
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
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
cadence
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
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;
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;
{mask[b],mask[i]} = {mask[i],mask[b]};
end
for ( int e = 0; e < s_size; e++ )
begin a[e] = {$random} & mask; shadow[e] = a[e]; end
#1;
shadow.sort();
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",
mut,i, e, elt, shadow[e]);
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
cadence