```////////////////////////////////////////////////////////////////////////////////
///
/// Solution to LSU EE 4702-1 Spring 2001 Homework 5
///

// Assignment: http://www.ee.lsu.edu/v/2001/hw05.pdf

////////////////////////////////////////////////////////////////////////////////

// The log_2 of the number of numbers stored by the bsearch module.
// Keep this small to limit synthesis time.
`define SIZELG 4
`define SIZE (1<<`SIZELG)       // The number of numbers stored by bsearch.
`define SIZERANGE `SIZELG-1:0
`define ELEMBITS 8              // The number of bits in each number stored.
`define ELEMRANGE `ELEMBITS-1:0
`define MAXELEM (1<<`ELEMBITS)

////////////////////////////////////////////////////////////////////////////////
//
// Original bsearch module.
//
// Not part of the solution, here for comparison to the other modules.
// This module is synthesizable (despite misleading macro names).  The
// synthesized hardware does the entire lookup in one cycle, which
// requires alot of hardware.

// Number of gates :                    5365
// clk                    : 50.7 MHz
// Critical path: num_2_ -> result[1], 19.18 ns

`define xNOT_SYN
`ifdef NOT_SYN
module bsearch(result,din,op,reset,clk);
input din, op, reset, clk;
output result;
wire [7:0] din;
wire [2:0] op;
reg [2:0]  result;

`include "bsearch_names.v"

reg [7:0]  dtable [0:`SIZE-1];
reg [`SIZELG:0] num;
reg [`SIZERANGE] current, try, delta;
reg [`ELEMRANGE] trydata;
reg              match;

// Bug workaround.  Needed to avoid a synthesis bug.
wire [`ELEMRANGE] bug_workaround = dtable[1];

always @( posedge clk )

if( reset ) begin

num = 0;
result = re_r_idle;

end else begin

case( op )

op_nop:;

op_reset:
begin
num = 0;
result = re_r_idle;
end

op_insert:
if( num == `SIZE ) begin
result = re_i_full;
end else if( num > 0 && dtable[num-1] >= din ) begin
result = re_i_misordered;
end else begin
dtable[num] = din;
num = num + 1;
result = re_i_inserted;
end

op_find:
begin
match   = 0;
current = 0;
delta   = 1 << ( `SIZELG - 1 );
begin:BLOOP forever begin
try = current | delta;
if( try < num ) begin
trydata = dtable[try];
match = trydata == din;
if( match ) disable BLOOP;
if( trydata < din ) current = try;
end
if( !delta ) disable BLOOP;
delta = delta >> 1;
end end

result = match ? re_f_present : re_f_absent;

end

endcase

end

endmodule
`endif

////////////////////////////////////////////////////////////////////////////////
//
// Problem 1:  Form 2 bsearch Module
//
// Synthesizable Form 2.
//
//
// Clock Frequency (MHz):                113.5 MHz
// Area (number of gates):              4275
// Worst-case time to find a number:    6 / 113.5 MHz = 52.9 ns
//

`define xFORM2
`ifdef FORM2

module bsearch(result,din,op,reset,clk);
input din, op, reset, clk;
output result;
wire [7:0] din;
wire [2:0] op;
reg [2:0]  result;

`include "bsearch_names.v"

reg        looping;

reg [7:0]  dtable [0:`SIZE-1];
reg [`SIZELG:0] num;
reg [`SIZERANGE] current, try, delta;
reg [`ELEMRANGE] trydata;
reg              match;

wire [`ELEMRANGE] bug_workaround = dtable[12];

always @( posedge clk )

if( reset ) begin

looping = 0;
num     = 0;
result  = re_r_idle;

end else if( looping ) begin

try = current + delta;
if( try < num ) begin
trydata = dtable[try];
match = trydata == din;
if( match ) looping = 0;
if( trydata < din ) current = try;
end
if( !delta ) looping = 0;
delta = delta >> 1;
if( !looping ) result = match ? re_f_present : re_f_absent;

end else begin

case( op )

op_nop:;

op_reset:
begin
num    = 0;
result = re_r_idle;
end

op_insert:
if( num == `SIZE ) begin
result = re_i_full;
end else if( num > 0 && dtable[num-1] >= din ) begin
result = re_i_misordered;
end else begin
dtable[num] = din;
num = num + 1;
result = re_i_inserted;
end

op_find:
begin
match   = 0;
current = 0;
delta   = 1 << ( `SIZELG - 1 );
result  = re_busy;
looping = 1;
end

endcase

end

endmodule
`endif

////////////////////////////////////////////////////////////////////////////////
//
// Problem 2:  Form 3 bsearch Module
//
// Synthesizable  Form 3.
// Module does one dtable lookup per cycle.
//
// Clock Frequency (MHz):                 109.1 MHz
// Area (number of gates):               4155
// Worst-case time to find a number:  5 / 109.1 MHz = 45.8 ns
//
// Critical path: reg_delta(1)/XQ to result[1], 8.47 ns

`define xFORM3
`ifdef FORM3
module bsearch(result,din,op,reset,clk);
input din, op, reset, clk;
output result;
wire [7:0] din;
wire [2:0] op;
reg [2:0]  result;

`include "bsearch_names.v"

reg [7:0]  dtable [0:`SIZE-1];
reg [`SIZELG:0] num;
reg [`SIZERANGE] current, try, delta;
reg [`ELEMRANGE] trydata;
reg              match;

always @( posedge clk )

if( reset ) begin

num = 0;
result = re_r_idle;

end else begin

case( op )

op_nop:;

op_reset:
begin
num = 0;
result = re_r_idle;
end

op_insert:
if( num == `SIZE ) begin
result = re_i_full;
end else if( num > 0 && dtable[num-1] >= din ) begin
result = re_i_misordered;
end else begin
dtable[num] = din;
num = num + 1;
result = re_i_inserted;
end

op_find:
begin
match   = 0;
current = 0;
delta   = 1 << ( `SIZELG - 1 );
result  = re_busy;

begin:BLOOP forever begin
@( posedge clk );
try = current + delta;
if( try < num ) begin
trydata = dtable[try];
// This would split the delta -> result path between two
// cycles, but it would take nearly twice as long to find
// a result.
//  @( posedge clk );
match = trydata == din;
if( match ) disable BLOOP;
if( trydata < din ) current = try;
end
if( !delta ) disable BLOOP;
delta = delta >> 1;
end end
result = match ? re_f_present : re_f_absent;

end

endcase

end

endmodule
`endif

////////////////////////////////////////////////////////////////////////////////
//
// Problem 3:  Form 3 bsearch Module, Speed Enhanced
//
// Synthesizable, Form 3.
// Module does two dtable lookups per cycle.
//

// Several solutions within module, area, time, and performance in comments
// next to code.

// Clock Frequency (MHz):
// Area (number of gates):
// Worst-case time to find a number:
//

`define FORM3_FAST
`ifdef FORM3_FAST
module bsearch(result,din,op,reset,clk);
input din, op, reset, clk;
output result;
wire [7:0] din;
wire [2:0] op;
reg [2:0]  result;

`include "bsearch_names.v"

reg [7:0]  dtable [0:`SIZE-1];
reg [`SIZELG:0] num;
reg [`SIZERANGE] current, try, delta;
reg [`SIZERANGE] try0, try1, delta2;
reg [`ELEMRANGE] trydata, trydata0, trydata1;
reg              match, match0, match1, m;

always @( posedge clk )

if( reset ) begin

num = 0;
result = re_r_idle;

end else begin

case( op )

op_nop:;

op_reset:
begin
num = 0;
result = re_r_idle;
end

op_insert:
if( num == `SIZE ) begin
result = re_i_full;
end else if( num > 0 && dtable[num-1] >= din ) begin
result = re_i_misordered;
end else begin
dtable[num] = din;
num = num + 1;
result = re_i_inserted;
end

op_find:
begin
current = 0;
delta   = 1 << ( `SIZELG - 1 );
result  = re_busy;

`define ALWAYS
`ifdef ALWAYS
// Two iterations per clock cycle, dtable lookups done simultaneously.
// Code below clk                    : 3 / 97.8 MHz = 30.7 ns
//  Number of gates :                    7513
delta2 = delta >> 1;
begin:BLOOP forever begin
@( posedge clk );
try = current + delta;

try0 = current + delta2;
try1 = try + delta2;
trydata = dtable[try];
trydata0 = dtable[try0];
trydata1 = dtable[try1];
match = trydata == din;
match0 = trydata0 == din;
match1 = trydata1 == din;
if( try < num ) begin
if( match ) begin m = 1; disable BLOOP; end
if( trydata > din )
begin
if( match0 ) begin m = 1; disable BLOOP; end
if( trydata0 < din ) current = try0;
end
else if( try1 < num )
begin
if( match1 ) begin m = 1; disable BLOOP; end
if( trydata1 < din ) current = try1;
else current = try;
end
else
current = try;
end else if( try0 < num ) begin
begin
if( match0 ) begin m = 1; disable BLOOP; end
if( trydata0 < din ) current = try0;
end
end
if( !delta ) begin m = 0; disable BLOOP; end
delta = delta >> 2;
delta2 = delta2 >> 2;
end end
`endif

`ifdef NEVER
// Completely unrolled, all five iterations in one cycle.
// Code below clk                    : 1/ 55.5 MHz  = 18.0 ns
//  Number of gates :                    5482
match = 0;
repeat ( `SIZELG + 1 ) begin
try = current + delta;
if( !match && try < num ) begin
trydata = dtable[try];
match = trydata == din;
if( trydata < din ) current = try;
end
delta = delta >> 1;
end
m = match;
`endif
`ifdef NEVER
// Original Code
//  Code below: clk                    : 5/ 109.1 MHz = 46.2 ns
//  Number of gates :                    4155
match = 0;
begin:BLOOP forever begin
@( posedge clk );
try = current + delta;
if( try < num ) begin
trydata = dtable[try];
match = trydata == din;
if( match ) disable BLOOP;
if( trydata < din ) current = try;
end
if( !delta ) disable BLOOP;
delta = delta >> 1;
end end
m = match;
`endif

`ifdef NEVER
// Two iterations per cycle.
// Iterations are sequential. (Second dtable lookup after first.)
//  clk                    : 3 / 63.7 MHz = 47.1 ns
// Number of gates :                    6465
match = 0;
begin:BLOOP forever begin
@( posedge clk );
repeat( 2 ) begin
try = current + delta;
if( !match && try < num ) begin
trydata = dtable[try];
match = trydata == din;
if( trydata < din ) current = try;
end
delta2 = delta;  delta = delta >> 1;
end
if( match ) disable BLOOP;
if( !delta2 ) disable BLOOP;
end end
m = match;
`endif

result = m ? re_f_present : re_f_absent;

end

endcase

end

endmodule
`endif

////////////////////////////////////////////////////////////////////////////////
//
// Testbench
//

// Testbench module is named testbsearch.

// The testbench can be copied into this file or another one and
// modified.  The testbench might be updated before the homework
// is due though.

`include "/home/classes/ee4702/files/v/hw05tb.v"

```