// 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