xiiregexbuilder

  1`timescale 1ns / 1ps
  2
  3module regex_cpu #(
  4    parameter NUM_REGEX = 16
  5) (
  6    input wire       clk,
  7    input wire       rst,
  8    input wire       start,
  9    input wire       end_of_str,
 10    input wire [7:0] char_in,
 11    input wire       char_valid,
 12
 13    input wire        prog_en,
 14    input wire [ 7:0] prog_addr,
 15    input wire [31:0] prog_data,
 16
 17    output wire                 ready,
 18    output reg  [NUM_REGEX-1:0] match_bus
 19);
 20
 21  // --- Instruction Memory (BRAM Inferred) ---
 22  reg [31:0] imem[0:255];
 23  initial $readmemh("processor/build/imem.hex", imem);
 24
 25  always @(posedge clk) begin
 26    if (prog_en) imem[prog_addr] <= prog_data;
 27  end
 28
 29  // --- State Machine ---
 30  localparam STATE_IDLE = 3'd0;
 31  localparam STATE_START_INIT = 3'd1;
 32  localparam STATE_CHAR_MATCH = 3'd2;
 33  localparam STATE_EPSILON_RECURSE = 3'd3;
 34  localparam STATE_END_OF_STR = 3'd4;
 35
 36  reg [  2:0] state = STATE_IDLE;
 37  reg [255:0] active_candidates;
 38  reg [  5:0] recurse_count;
 39  reg [  7:0] pc_cnt;
 40  reg [255:0] next_set_buffer;
 41  reg [  7:0] char_reg;
 42  reg         recurse_changed;
 43
 44  assign ready = (state == STATE_IDLE);
 45
 46  // Single-port instruction fetch
 47  wire [31:0] current_instr = imem[pc_cnt];
 48  wire [ 7:0] p_char = current_instr[31:24];
 49  wire [ 7:0] p_next1 = current_instr[23:16];
 50  wire [ 7:0] p_next2 = current_instr[15:8];
 51  wire [ 3:0] p_mid = current_instr[7:4];
 52  wire        p_term = current_instr[3];
 53  wire        p_any = current_instr[0];
 54
 55  always @(posedge clk) begin
 56    if (rst) begin
 57      state <= STATE_IDLE;
 58      active_candidates <= 0;
 59      match_bus <= 0;
 60      recurse_count <= 0;
 61      char_reg <= 0;
 62      pc_cnt <= 0;
 63      next_set_buffer <= 0;
 64    end else begin
 65      case (state)
 66        STATE_IDLE: begin
 67          if (start) begin
 68            state <= STATE_START_INIT;
 69            match_bus <= 0;
 70          end else if (char_valid) begin
 71            char_reg <= char_in;
 72            pc_cnt <= 0;
 73            next_set_buffer <= 0;
 74            state <= STATE_CHAR_MATCH;
 75          end else if (end_of_str) begin
 76            pc_cnt <= 0;
 77            state  <= STATE_END_OF_STR;
 78          end
 79        end
 80
 81        STATE_START_INIT: begin
 82          active_candidates <= 256'd1;  // Start at Address 0 (the split chain)
 83          recurse_count <= 0;
 84          pc_cnt <= 0;
 85          recurse_changed <= 0;
 86          state <= STATE_EPSILON_RECURSE;
 87        end
 88
 89        STATE_CHAR_MATCH: begin
 90          if (active_candidates[pc_cnt]) begin
 91            if (p_any || (p_char != 0 && p_char == char_reg)) begin
 92              if (p_next1 != 0) next_set_buffer[p_next1] <= 1'b1;
 93              if (p_next2 != 0) next_set_buffer[p_next2] <= 1'b1;
 94            end
 95          end
 96
 97          if (pc_cnt == 8'd255) begin
 98            active_candidates <= next_set_buffer;
 99            recurse_count <= 0;
100            pc_cnt <= 0;
101            recurse_changed <= 1; // Force at least one pass of epsilon recurse
102            state <= STATE_EPSILON_RECURSE;
103          end else begin
104            pc_cnt <= pc_cnt + 1;
105          end
106        end
107
108        STATE_EPSILON_RECURSE: begin
109          // One pass over all nodes to expand epsilon transitions
110          if (active_candidates[pc_cnt] && p_char == 0 && !p_any && !p_term) begin
111            active_candidates[pc_cnt] <= 1'b0;  // Node consumed
112            if (p_next1 != 0) active_candidates[p_next1] <= 1'b1;
113            if (p_next2 != 0) active_candidates[p_next2] <= 1'b1;
114            recurse_changed <= 1;
115          end
116
117          if (pc_cnt == 8'd255) begin
118            if (recurse_count == 6'd63 || !recurse_changed) begin
119              state <= STATE_IDLE;
120            end else begin
121              recurse_count <= recurse_count + 1;
122              pc_cnt <= 0;
123              recurse_changed <= 0;
124            end
125          end else begin
126            pc_cnt <= pc_cnt + 1;
127          end
128        end
129
130        STATE_END_OF_STR: begin
131          if (active_candidates[pc_cnt] && p_term) begin
132            match_bus[p_mid] <= 1'b1;
133          end
134
135          if (pc_cnt == 8'd255) begin
136            state <= STATE_IDLE;
137          end else begin
138            pc_cnt <= pc_cnt + 1;
139          end
140        end
141
142        default: state <= STATE_IDLE;
143      endcase
144    end
145  end
146
147endmodule