`default_nettype none
module batcher_sort
#( int n = 4, int w = 8 )
( output uwire [w-1:0] x[n], input uwire [w-1:0] a[n] );
assign x = a;
endmodule
module behav_merge
#( int n = 4, int w = 8 )
( output logic [w-1:0] x[2*n], input uwire [w-1:0] a[n], b[n] );
logic [$clog2(n+1)-1:0] ia, ib;
always_comb begin
ia = 0; ib = 0;
for ( int i = 0; i < 2*n; i++ )
x[i] = a[ia] <= b[ib] ? a[ia++] : b[ib++];
for ( int i = 0; i < 2*n; i++ )
x[i] = ib == n || ia < n && a[ia] <= b[ib] ? a[ia++] : b[ib++];
end
endmodule
module batcher_merge
#( int n = 4, int w = 8 )
( output uwire [w-1:0] x[2*n], input uwire [w-1:0] a[n], b[n] );
assign x = {a,b};
endmodule
module sort2
#( 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
cadence
module sortx
#( int n = 5,
int modnum = 0,
int mut_idx = 0,
int w = 8,
int max_muts = 3,
int max_n = n)
( output uwire [w-1:0] xlong[max_muts][max_n],
input uwire [w-1:0] a[n] );
localparam int nlo = n/2;
localparam int nhi = n - nlo;
uwire [w-1:0] x[n];
assign xlong[mut_idx][0:n-1] = x;
uwire [w-1:0] alo[nlo] = a[0:nlo-1];
uwire [w-1:0] ahi[nhi] = a[nlo:n-1];
if ( modnum == 2 ) begin:A
localparam string name = "behav_merge";
localparam bit merge = 1;
behav_merge #(nlo,w) s(x,alo,ahi);
end else if ( modnum == 1 ) begin:A
localparam string name = "batcher_sort";
localparam bit merge = 0;
batcher_sort #(n,w) s(x,a);
end else if ( modnum == 0 ) begin:A
localparam string name = "batcher_merge";
localparam bit merge = 1;
batcher_merge #(nlo,w) s(x,alo,ahi);
end else begin:A
localparam string name = "sort4";
localparam bit merge = 0;
end
endmodule
module testbench;
localparam int w = 10;
localparam int n_tests = 10;
localparam int max_n = 32;
localparam int max_muts = 12;
logic [w-1:0] a[max_n];
uwire [w-1:0] x[max_muts][max_n];
typedef struct { int idx; string name; bit merge; int n; } Info;
Info pi[$];
for ( genvar i=0; i<2; i++ ) begin
for ( genvar nlg = 1; nlg < 6; nlg++ ) begin
localparam int n = 1 << nlg;
localparam int idx = i * 6 + nlg;
sortx #(n,i,idx,w,max_muts,max_n) s(x,a[0:n-1]);
initial pi.push_back( '{ idx, s.A.name, s.A.merge, s.n } );
end
end
initial begin
automatic int g_elt_err_count = 0;
automatic int g_sort_err_count = 0;
$write("Starting testbench.\n");
for ( int e = 0; e < max_n; e++ ) a[e] = 'haaaaaaaa;
foreach ( pi[idx] ) begin
automatic Info p = pi[idx];
automatic string mut = p.name;
automatic int n = p.n;
automatic int s_size = n;
automatic int nlo = n/2;
automatic int nhi = n - nlo;
automatic logic [w-1:0] shadow[] = new[s_size];
automatic logic [w-1:0] alo[] = new[nlo];
automatic logic [w-1:0] ahi[] = new[nhi];
automatic int this_sort_err_count = 0;
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];
if ( e < nlo ) alo[e] = a[e]; else ahi[e-nlo] = a[e];
end
if ( p.merge ) begin
alo.sort();
ahi.sort();
for ( int e=0; e<nlo; e++ ) a[e] = alo[e];
for ( int e=nlo; e<n; e++ ) a[e] = ahi[e-nlo];
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, n=%0d, sort %2d idx %2d, wrong elt %d != %d (correct)\n",
mut, n, i, e, elt, shadow[e]);
end
if ( this_elt_err_count ) this_sort_err_count++;
end
if ( this_sort_err_count ) g_sort_err_count++;
$write("Tests for %s (idx %0d) n=%0d done, errors in %0d of %0d sorts.\n",
mut, p.idx, n, this_sort_err_count, n_tests);
end
$write("Done with all tests, errors on %0d sorters.\n",
g_sort_err_count);
end
endmodule
cadence