663 lines
18 KiB
Systemverilog
663 lines
18 KiB
Systemverilog
// Max maze size parameter; must be power of 2
|
|
`define MAX_SIZE 16
|
|
|
|
// Start of FSM
|
|
// Step 0a - Create a module with input / output variable
|
|
module fsm_design (
|
|
// Step 1b - Define all inputs and outputs
|
|
input logic [0:0] back_flag,
|
|
input logic clk,
|
|
input logic input_enable,
|
|
input logic no_walls,
|
|
input logic rst,
|
|
input logic stack_ptrs_eq,
|
|
input logic start,
|
|
input logic val_move,
|
|
|
|
output logic cur_wall_reg_en,
|
|
output logic next_addr_reg_en,
|
|
output logic rel_move_reg_en,
|
|
output logic abs_move_buf_en,
|
|
output logic req_next_addr,
|
|
output logic sol_reg_en,
|
|
output logic stack_en,
|
|
output logic stack_op,
|
|
output logic stack_sol_inc,
|
|
output logic update_reg,
|
|
output logic [1:0] move_sel,
|
|
output logic done,
|
|
output logic out_val
|
|
);
|
|
|
|
// step 2 - Create the State Machine Information
|
|
|
|
// Step 2a - Create the enum for all the states
|
|
// Note: It is industry convention to put IDLE first, but I put S0 ... S7 first
|
|
// So that the output waveforms are easier to read for students (S0 being state 0, and so on)
|
|
typedef enum logic [3:0] {
|
|
IDLE, INPUT, LOAD, RIGHT, UP, LEFT, DOWN, CHECK, PUSH, POP, UPDATE, LAST, OUTPUT, DONE
|
|
} state_t;
|
|
|
|
// Step 2b - Create the state variables for the current and next states
|
|
state_t state, next_state;
|
|
|
|
always_ff @(posedge clk) begin
|
|
if (rst) state <= IDLE;
|
|
else state <= next_state;
|
|
end
|
|
|
|
always_comb begin
|
|
next_state = state;
|
|
|
|
req_next_addr = 1'b0;
|
|
cur_wall_reg_en = 1'b0;
|
|
rel_move_reg_en = 1'b0;
|
|
next_addr_reg_en = 1'b0;
|
|
update_reg = 1'b0;
|
|
stack_en = 1'b0;
|
|
stack_op = 1'b0;
|
|
stack_sol_inc = 1'b0;
|
|
sol_reg_en = 1'b0;
|
|
move_sel = 2'b00;
|
|
done = 1'b0;
|
|
out_val = 1'b0;
|
|
abs_move_buf_en = 1'b0;
|
|
|
|
case(state)
|
|
IDLE:
|
|
begin
|
|
if (start) begin
|
|
next_state = INPUT;
|
|
end else begin
|
|
next_state = IDLE;
|
|
end
|
|
end
|
|
|
|
INPUT:
|
|
begin
|
|
req_next_addr = 1'b1;
|
|
if (input_enable) begin
|
|
next_state = LOAD;
|
|
end else begin
|
|
next_state = INPUT;
|
|
end
|
|
end
|
|
|
|
LOAD:
|
|
begin
|
|
cur_wall_reg_en = 1'b1;
|
|
if (no_walls) begin
|
|
next_state = LAST;
|
|
end
|
|
else begin
|
|
next_state = RIGHT;
|
|
end
|
|
end
|
|
|
|
RIGHT:
|
|
begin
|
|
move_sel = 2'b01;
|
|
rel_move_reg_en = val_move;
|
|
if (val_move) begin
|
|
next_state = CHECK;
|
|
end
|
|
else begin
|
|
next_state = UP;
|
|
end
|
|
end
|
|
|
|
UP:
|
|
begin
|
|
move_sel = 2'b00;
|
|
rel_move_reg_en = val_move;
|
|
if (val_move) begin
|
|
next_state = CHECK;
|
|
end
|
|
else begin
|
|
next_state = LEFT;
|
|
end
|
|
end
|
|
|
|
LEFT:
|
|
begin
|
|
move_sel = 2'b11;
|
|
rel_move_reg_en = val_move;
|
|
if (val_move) begin
|
|
next_state = CHECK;
|
|
end
|
|
else begin
|
|
next_state = DOWN;
|
|
end
|
|
end
|
|
|
|
DOWN:
|
|
begin
|
|
move_sel = 2'b10;
|
|
rel_move_reg_en = val_move;
|
|
begin
|
|
next_state = CHECK;
|
|
end
|
|
end
|
|
|
|
CHECK:
|
|
begin
|
|
abs_move_buf_en = 1'b1;
|
|
if (back_flag && !stack_ptrs_eq) begin
|
|
next_state = POP;
|
|
end
|
|
else begin
|
|
next_state = PUSH;
|
|
end
|
|
end
|
|
|
|
PUSH:
|
|
begin
|
|
stack_en = 1'b1;
|
|
stack_op = 1'b0;
|
|
next_addr_reg_en = 1'b1;
|
|
begin
|
|
next_state = UPDATE;
|
|
end
|
|
end
|
|
|
|
POP:
|
|
begin
|
|
stack_en = 1'b1;
|
|
stack_op = 1'b1;
|
|
next_addr_reg_en = 1'b1;
|
|
begin
|
|
next_state = UPDATE;
|
|
end
|
|
end
|
|
|
|
UPDATE:
|
|
begin
|
|
update_reg = 1'b1;
|
|
begin
|
|
next_state = INPUT;
|
|
end
|
|
end
|
|
|
|
LAST:
|
|
begin
|
|
sol_reg_en = 1'b1;
|
|
if (stack_ptrs_eq) begin
|
|
next_state = DONE;
|
|
end
|
|
else begin
|
|
next_state = OUTPUT;
|
|
end
|
|
end
|
|
|
|
OUTPUT:
|
|
begin
|
|
stack_sol_inc = 1'b1;
|
|
out_val = 1'b1;
|
|
begin
|
|
next_state = LAST;
|
|
end
|
|
end
|
|
|
|
DONE:
|
|
begin
|
|
done = 1'b1;
|
|
next_state = DONE;
|
|
end
|
|
endcase
|
|
end
|
|
|
|
endmodule
|
|
|
|
// Start of datapath
|
|
module reg_nbit #(
|
|
parameter N = 8 // default to 8 bits
|
|
) (
|
|
input wire reg_clk,
|
|
input wire reg_en,
|
|
input wire reg_rst,
|
|
input wire [N-1:0] reg_in,
|
|
|
|
output logic [N-1:0] reg_out
|
|
);
|
|
|
|
always_comb begin
|
|
if (reg_rst) begin
|
|
reg_out <= {N{1'b0}}; // zero register on rst signal
|
|
end
|
|
else if (reg_en) begin
|
|
reg_out <= reg_in; // update reg on en signal
|
|
end
|
|
end
|
|
|
|
endmodule
|
|
|
|
module add_sub_wrap_nbit #(
|
|
parameter N = 2
|
|
) (
|
|
input wire [N-1:0] a_in,
|
|
input wire [N-1:0] b_in,
|
|
input wire add_sub_sel, // 0 = add, 1 = sub
|
|
|
|
output logic [N-1:0] result
|
|
);
|
|
assign result = add_sub_sel ? (a_in - b_in) : (a_in + b_in);
|
|
endmodule
|
|
|
|
module rot_left_4bit (
|
|
input wire [3:0] rot_in,
|
|
input wire [1:0] rot_val, // value to rotate by
|
|
|
|
output logic [3:0] rot_out
|
|
);
|
|
|
|
assign rot_out = (rot_in << rot_val) | (rot_in >> (4 - rot_val));
|
|
|
|
endmodule
|
|
|
|
module bit_sel_4bit (
|
|
input wire [3:0] sel_in,
|
|
input wire [1:0] sel_val, // bit to select
|
|
|
|
output logic sel_out
|
|
);
|
|
|
|
always_comb begin
|
|
case (sel_val)
|
|
2'b00: sel_out = sel_in[3]; // "up" direction
|
|
2'b01: sel_out = sel_in[2]; // "right" direction
|
|
2'b10: sel_out = sel_in[1]; // "left" direction
|
|
2'b11: sel_out = sel_in[0]; // "down" direction
|
|
|
|
default: sel_out = 1'b0; // default case
|
|
endcase
|
|
end
|
|
|
|
endmodule
|
|
|
|
module not_4bit (
|
|
input wire [3:0] not_in,
|
|
|
|
output logic [3:0] not_out
|
|
);
|
|
|
|
assign not_out = ~not_in;
|
|
|
|
endmodule
|
|
|
|
module nor_4bit (
|
|
input wire [3:0] nor_in,
|
|
|
|
output logic nor_out
|
|
);
|
|
|
|
assign nor_out = ~(|nor_in);
|
|
|
|
endmodule
|
|
|
|
module move_conv_logic #(
|
|
parameter COOR_WIDTH = 4
|
|
) (
|
|
input wire [1:0] move_in,
|
|
|
|
output logic [(COOR_WIDTH*2)-1:0] x_y,
|
|
output logic add_sub // 0 for add, 1 for sub
|
|
);
|
|
|
|
logic [COOR_WIDTH-1:0] add_x;
|
|
logic [COOR_WIDTH-1:0] add_y;
|
|
|
|
always_comb begin
|
|
case (move_in)
|
|
2'b00: begin // up
|
|
add_sub = 0;
|
|
add_x = 0;
|
|
add_y = 1;
|
|
end
|
|
|
|
2'b01: begin // right
|
|
add_sub = 0;
|
|
add_x = 1;
|
|
add_y = 0;
|
|
end
|
|
|
|
2'b10: begin // down
|
|
add_sub = 1;
|
|
add_x = 0;
|
|
add_y = 1;
|
|
end
|
|
|
|
2'b11: begin // left
|
|
add_sub = 1;
|
|
add_x = 1;
|
|
add_y = 0;
|
|
end
|
|
|
|
default: begin // default case
|
|
add_sub = 0;
|
|
add_x = 0;
|
|
add_y = 0;
|
|
end
|
|
endcase
|
|
end
|
|
|
|
assign x_y = {add_x, add_y}; // recombine x and y into one output
|
|
|
|
endmodule
|
|
|
|
module back_test_logic (
|
|
input wire [1:0] cur_in,
|
|
input wire [1:0] prev_in,
|
|
|
|
output logic backtrack
|
|
);
|
|
// If cur_in and prev_in are different but have the same LSB, chip is backtracking
|
|
assign backtrack = (cur_in != prev_in) && (cur_in[0] == prev_in[0]);
|
|
|
|
endmodule
|
|
|
|
module split_1_to_2_nbit #(
|
|
parameter N = 8
|
|
) (
|
|
input wire [N-1:0] split_in,
|
|
output wire [(N-1)/2:0] split_high_out,
|
|
output wire [(N-1)/2:0] split_low_out
|
|
);
|
|
|
|
assign split_high_out = split_in[N-1:N/2];
|
|
assign split_low_out = split_in[(N/2)-1:0];
|
|
|
|
endmodule
|
|
|
|
module stack_ncell #(
|
|
parameter CELLS = 256
|
|
) (
|
|
input wire clk,
|
|
input wire rst_stack,
|
|
input wire stack_en, // High to enable push/pop operations
|
|
input wire stack_op, // 0 for push, 1 for pop
|
|
input wire [1:0] stack_in,
|
|
input wire stack_sol_inc,
|
|
output logic [1:0] stack_out,
|
|
output logic [1:0] stack_sol,
|
|
output logic stack_ptrs_eq
|
|
);
|
|
|
|
localparam PTR_WIDTH = $clog2(CELLS);
|
|
|
|
logic [1:0] mem [0:CELLS-1];
|
|
logic [PTR_WIDTH-1:0] stack_ptr;
|
|
logic [PTR_WIDTH-1:0] stack_sol_ptr;
|
|
|
|
always_ff @(posedge clk or posedge rst_stack) begin
|
|
if (rst_stack) begin
|
|
stack_ptr <= 0;
|
|
stack_sol_ptr <= 0;
|
|
mem <= '{default:2'b00};
|
|
end else if (stack_sol_inc) begin
|
|
stack_sol_ptr <= stack_sol_ptr + 1;
|
|
end else if (stack_en) begin
|
|
if (!stack_op) begin // Push Operation (stack_op is 0)
|
|
// 1. Increment the stack pointer
|
|
stack_ptr <= stack_ptr + 1;
|
|
// 2. Write the input data to the new top location
|
|
mem[stack_ptr + 1] <= stack_in;
|
|
end else begin // Pop Operation (stack_op is 1)
|
|
stack_ptr <= stack_ptr - 1;
|
|
end
|
|
end
|
|
end
|
|
|
|
assign stack_out = mem[stack_ptr];
|
|
assign stack_sol = mem[stack_sol_ptr + 1];
|
|
assign stack_ptrs_eq = (stack_ptr == stack_sol_ptr);
|
|
|
|
endmodule
|
|
|
|
module datapath_design (
|
|
input wire [3:0] cur_wall,
|
|
input wire cur_wall_reg_en,
|
|
input wire [1:0] move_sel,
|
|
input wire rel_move_reg_en,
|
|
input wire abs_move_buf_en,
|
|
input wire rst,
|
|
input wire update_reg,
|
|
input wire stack_en,
|
|
input wire stack_op,
|
|
input wire stack_sol_inc,
|
|
input wire sol_reg_en,
|
|
input wire next_addr_reg_en,
|
|
input wire clk,
|
|
|
|
output logic [$clog2(`MAX_SIZE)-1:0] next_x,
|
|
output logic [$clog2(`MAX_SIZE)-1:0] next_y,
|
|
output logic [1:0] solution,
|
|
output logic val_move,
|
|
output logic stack_ptrs_eq,
|
|
output logic no_walls,
|
|
output logic [0:0] back_flag
|
|
);
|
|
|
|
// Internal Wires
|
|
logic [3:0] absolute_walls_wire;
|
|
logic [1:0] absolute_dir_wire;
|
|
logic [3:0] relative_walls_wire;
|
|
logic [3:0] relative_walls_inv_wire;
|
|
logic [1:0] absolute_move_wire;
|
|
logic [1:0] absolute_move_buf_wire;
|
|
logic [1:0] relative_move_wire;
|
|
logic [($clog2(`MAX_SIZE)*2)-1:0] x_y_wire;
|
|
logic add_sub_wire;
|
|
logic [($clog2(`MAX_SIZE)*2)-1:0] current_address_wire;
|
|
logic [($clog2(`MAX_SIZE)*2)-1:0] next_address_wire;
|
|
logic [($clog2(`MAX_SIZE)*2)-1:0] next_full_wire;
|
|
logic [1:0] prev_move_wire;
|
|
logic [1:0] solution_wire;
|
|
|
|
reg_nbit #(.N(4)) cur_wall_reg (
|
|
.reg_clk (clk),
|
|
.reg_en (cur_wall_reg_en),
|
|
.reg_rst (rst),
|
|
.reg_in (cur_wall),
|
|
.reg_out (absolute_walls_wire)
|
|
);
|
|
|
|
rot_left_4bit rotate_wall (
|
|
.rot_in (absolute_walls_wire),
|
|
.rot_val (absolute_dir_wire),
|
|
.rot_out (relative_walls_wire)
|
|
);
|
|
|
|
reg_nbit #(.N(2)) abs_dir_reg (
|
|
.reg_clk (clk),
|
|
.reg_en (update_reg),
|
|
.reg_rst (rst),
|
|
.reg_in (absolute_move_buf_wire),
|
|
.reg_out (absolute_dir_wire)
|
|
);
|
|
|
|
not_4bit wall_invert (
|
|
.not_in (relative_walls_wire),
|
|
.not_out (relative_walls_inv_wire)
|
|
);
|
|
|
|
bit_sel_4bit test_move (
|
|
.sel_in (relative_walls_inv_wire),
|
|
.sel_val (move_sel),
|
|
.sel_out (val_move)
|
|
);
|
|
|
|
nor_4bit wall_check (
|
|
.nor_in (absolute_walls_wire),
|
|
.nor_out (no_walls)
|
|
);
|
|
|
|
reg_nbit #(.N(2)) rel_move_reg (
|
|
.reg_clk (clk),
|
|
.reg_en (rel_move_reg_en),
|
|
.reg_rst (rst),
|
|
.reg_in (move_sel),
|
|
.reg_out (relative_move_wire)
|
|
);
|
|
|
|
reg_nbit #(.N(2)) abs_move_buf (
|
|
.reg_clk (clk),
|
|
.reg_en (abs_move_buf_en),
|
|
.reg_rst (rst),
|
|
.reg_in (absolute_move_wire),
|
|
.reg_out (absolute_move_buf_wire)
|
|
);
|
|
|
|
add_sub_wrap_nbit #(.N(2)) rel_to_abs_alu (
|
|
.a_in (relative_move_wire),
|
|
.b_in (absolute_dir_wire),
|
|
.add_sub_sel (1'b0),
|
|
.result (absolute_move_wire)
|
|
);
|
|
|
|
move_conv_logic #(.COOR_WIDTH($clog2(`MAX_SIZE))) move_conv (
|
|
.move_in (absolute_move_buf_wire),
|
|
.x_y (x_y_wire),
|
|
.add_sub (add_sub_wire)
|
|
);
|
|
|
|
add_sub_wrap_nbit #(.N($clog2(`MAX_SIZE)*2)) cur_to_next_alu (
|
|
.a_in (current_address_wire),
|
|
.b_in (x_y_wire),
|
|
.add_sub_sel (add_sub_wire),
|
|
.result (next_address_wire)
|
|
);
|
|
|
|
reg_nbit #(.N($clog2(`MAX_SIZE)*2)) cur_addr_reg (
|
|
.reg_clk (clk),
|
|
.reg_en (update_reg),
|
|
.reg_rst (rst),
|
|
.reg_in (next_full_wire),
|
|
.reg_out (current_address_wire)
|
|
);
|
|
|
|
reg_nbit #(.N($clog2(`MAX_SIZE)*2)) next_addr_reg (
|
|
.reg_clk (clk),
|
|
.reg_en (next_addr_reg_en),
|
|
.reg_rst (rst),
|
|
.reg_in (next_address_wire),
|
|
.reg_out (next_full_wire)
|
|
);
|
|
|
|
split_1_to_2_nbit #(.N($clog2(`MAX_SIZE)*2)) addr_split (
|
|
.split_in (next_full_wire),
|
|
.split_high_out (next_x),
|
|
.split_low_out (next_y)
|
|
);
|
|
|
|
back_test_logic back_test (
|
|
.cur_in (absolute_move_buf_wire),
|
|
.prev_in (prev_move_wire),
|
|
.backtrack (back_flag)
|
|
);
|
|
|
|
stack_ncell #(.CELLS(`MAX_SIZE*`MAX_SIZE)) stack (
|
|
.clk (clk),
|
|
.rst_stack (rst),
|
|
.stack_op (stack_op),
|
|
.stack_en (stack_en),
|
|
.stack_in (absolute_move_buf_wire),
|
|
.stack_sol_inc (stack_sol_inc),
|
|
.stack_out (prev_move_wire),
|
|
.stack_sol (solution_wire),
|
|
.stack_ptrs_eq (stack_ptrs_eq)
|
|
);
|
|
|
|
reg_nbit #(.N(2)) sol_reg (
|
|
.reg_clk (clk),
|
|
.reg_en (sol_reg_en),
|
|
.reg_rst (rst),
|
|
.reg_in (solution_wire),
|
|
.reg_out (solution)
|
|
);
|
|
|
|
endmodule
|
|
|
|
// Start of overall chip
|
|
module chip_design (
|
|
input logic clk,
|
|
input logic [3:0] cur_wall,
|
|
input logic input_enable,
|
|
input logic rst,
|
|
input logic start,
|
|
|
|
output logic req_next_addr,
|
|
output logic [$clog2(`MAX_SIZE)-1:0] next_x,
|
|
output logic [$clog2(`MAX_SIZE)-1:0] next_y,
|
|
output logic [1:0] solution,
|
|
output logic out_val,
|
|
output logic done
|
|
);
|
|
|
|
// Internal wires
|
|
logic rel_move_reg_en_wire;
|
|
logic abs_move_buf_en_wire;
|
|
logic cur_wall_reg_en_wire;
|
|
logic next_addr_reg_en_wire;
|
|
logic [1:0] move_sel_wire;
|
|
logic update_reg_wire;
|
|
logic val_move_wire;
|
|
logic stack_ptrs_eq_wire;
|
|
logic no_walls_wire;
|
|
logic [0:0] back_flag_wire;
|
|
logic stack_en_wire;
|
|
logic stack_op_wire;
|
|
logic stack_sol_inc_wire;
|
|
logic sol_reg_en_wire;
|
|
|
|
// Controller instance
|
|
fsm_design controller (
|
|
.clk (clk),
|
|
.rst (rst),
|
|
.start (start),
|
|
.input_enable (input_enable),
|
|
.no_walls (no_walls_wire),
|
|
.val_move (val_move_wire),
|
|
.back_flag (back_flag_wire),
|
|
.stack_ptrs_eq (stack_ptrs_eq_wire),
|
|
|
|
.req_next_addr (req_next_addr),
|
|
.cur_wall_reg_en (cur_wall_reg_en_wire),
|
|
.rel_move_reg_en (rel_move_reg_en_wire),
|
|
.abs_move_buf_en (abs_move_buf_en_wire),
|
|
.next_addr_reg_en (next_addr_reg_en_wire),
|
|
.update_reg (update_reg_wire),
|
|
.stack_en (stack_en_wire),
|
|
.stack_op (stack_op_wire),
|
|
.stack_sol_inc (stack_sol_inc_wire),
|
|
.sol_reg_en (sol_reg_en_wire),
|
|
.move_sel (move_sel_wire),
|
|
.done (done),
|
|
.out_val (out_val)
|
|
);
|
|
|
|
// Datapath instance
|
|
datapath_design datapath (
|
|
.cur_wall (cur_wall),
|
|
.move_sel (move_sel_wire),
|
|
.cur_wall_reg_en (cur_wall_reg_en_wire),
|
|
.rel_move_reg_en (rel_move_reg_en_wire),
|
|
.abs_move_buf_en (abs_move_buf_en_wire),
|
|
.rst (rst),
|
|
.update_reg (update_reg_wire),
|
|
.stack_en (stack_en_wire),
|
|
.stack_op (stack_op_wire),
|
|
.stack_sol_inc (stack_sol_inc_wire),
|
|
.sol_reg_en (sol_reg_en_wire),
|
|
.next_addr_reg_en (next_addr_reg_en_wire),
|
|
.clk (clk),
|
|
|
|
.next_x (next_x),
|
|
.next_y (next_y),
|
|
.solution (solution),
|
|
.val_move (val_move_wire),
|
|
.stack_ptrs_eq (stack_ptrs_eq_wire),
|
|
.no_walls (no_walls_wire),
|
|
.back_flag (back_flag_wire)
|
|
);
|
|
|
|
endmodule
|