commit 188f3e27d06c6b045fda77244523cc25ed8e1a20
parent 0b9c12113b4e19ea0b9d581fe0598bebc8f00987
Author: Brian Swetland <swetland@frotz.net>
Date: Sun, 26 Jan 2020 04:04:46 -0800
sync_fifo: simple synchronous fifo 2^N deep
- initial implementation
- passes test, which I believe exercises all the corners
Diffstat:
4 files changed, 346 insertions(+), 0 deletions(-)
diff --git a/hdl/sync_fifo.sv b/hdl/sync_fifo.sv
@@ -0,0 +1,117 @@
+// Copyright 2020, Brian Swetland <swetland@frotz.net>
+// Licensed under the Apache License, Version 2.0.
+
+`default_nettype none
+
+// basic fifo with power-of-two storage elements
+
+module sync_fifo #(
+ parameter WIDTH = 8, // data width in bits
+ parameter DEPTH = 8 // capacity 2^DEPTH
+ ) (
+ input wire clk,
+
+ input wire [WIDTH-1:0]wr_data,
+ input wire wr_valid,
+ output reg wr_ready = 0,
+
+ output wire [WIDTH-1:0]rd_data,
+ output reg rd_valid = 0,
+ input wire rd_ready
+);
+
+localparam PTRONE = { {DEPTH{1'b0}}, 1'b1 };
+
+wire do_wr = (wr_valid & wr_ready);
+wire do_rd = (rd_valid & rd_ready);
+
+// pointers are one bit wider so the high bit
+// can help compute full / empty
+reg [DEPTH:0]wr_ptr = 0;
+reg [DEPTH:0]rd_ptr = 0;
+
+// prepare the new r/w pointer values
+wire [DEPTH:0]wr_ptr_next = do_wr ? (wr_ptr + PTRONE) : wr_ptr;
+wire [DEPTH:0]rd_ptr_next = do_rd ? (rd_ptr + PTRONE) : rd_ptr;
+
+// compute the new full/empty states
+wire full_or_empty_next = (rd_ptr_next[DEPTH-1:0] == wr_ptr_next[DEPTH-1:0]);
+wire full_next = full_or_empty_next & (rd_ptr_next[DEPTH] != wr_ptr_next[DEPTH]);
+wire empty_next = full_or_empty_next & (rd_ptr_next[DEPTH] == wr_ptr_next[DEPTH]);
+wire one_next = ((wr_ptr_next - rd_ptr_next) == PTRONE);
+
+localparam EMPTY = 2'd0;
+localparam ONE = 2'd1;
+localparam MANY = 2'd2;
+localparam FULL = 2'd3;
+
+reg [1:0]state = EMPTY;
+reg [1:0]state_next;
+reg rd_valid_next;
+reg wr_ready_next;
+
+always_comb begin
+ state_next = state;
+ rd_valid_next = rd_valid;
+ wr_ready_next = wr_ready;
+
+ case (state)
+ EMPTY: begin
+ wr_ready_next = 1;
+ if (do_wr) begin
+ state_next = ONE;
+ end
+ end
+ ONE: begin
+ if (do_rd & do_wr) begin
+ rd_valid_next = 0;
+ end else if (do_rd) begin
+ state_next = EMPTY;
+ rd_valid_next = 0;
+ end else if (do_wr) begin
+ state_next = MANY;
+ rd_valid_next = 1;
+ end else begin
+ rd_valid_next = 1;
+ end
+ end
+ MANY: begin
+ if (one_next) begin
+ state_next = ONE;
+ end else if (full_next) begin
+ state_next = FULL;
+ wr_ready_next = 0;
+ end
+ end
+ FULL: begin
+ if (do_rd) begin
+ state_next = MANY;
+ wr_ready_next = 1;
+ end
+ end
+ endcase
+end
+
+always_ff @(posedge clk) begin
+ state <= state_next;
+ rd_ptr <= rd_ptr_next;
+ wr_ptr <= wr_ptr_next;
+ wr_ready <= wr_ready_next;
+ rd_valid <= rd_valid_next;
+end
+
+// fifo storage
+reg [WIDTH-1:0]memory[0:2**DEPTH-1];
+reg [WIDTH-1:0]data;
+
+always_ff @(posedge clk) begin
+ if (wr_valid & wr_ready)
+ memory[wr_ptr[DEPTH-1:0]] <= wr_data;
+
+ data <= memory[rd_ptr_next[DEPTH-1:0]];
+end
+
+assign rd_data = data;
+
+endmodule
+
diff --git a/hdl/sync_fifo_test.sv b/hdl/sync_fifo_test.sv
@@ -0,0 +1,199 @@
+// Copyright 2020, Brian Swetland <swetland@frotz.net>
+// Licensed under the Apache License, Version 2.0.
+
+`default_nettype none
+
+module testbench(
+ input wire clk,
+ output reg error = 0,
+ output reg done = 0
+);
+
+wire [31:0]wr_data;
+wire wr_ready;
+reg wr_valid = 0;
+
+wire [31:0]rd_data;
+wire rd_valid;
+reg rd_ready = 0;
+
+wire [31:0]chk_data;
+
+reg [31:0]count = 0;
+reg [31:0]rd_count = 0;
+
+reg [31:0]rd_count_n;
+reg rd_ready_n;
+reg wr_valid_n;
+reg done_n;
+reg error_n;
+
+always_comb begin
+ rd_count_n = rd_count;
+ rd_ready_n = rd_ready;
+ wr_valid_n = wr_valid;
+ done_n = 0;
+ error_n = 0;
+
+ $display("%3d: W(%08x) %s %s --> R(%08x) %s %s C(%08x) RX(%3d)",
+ count,
+ wr_data, wr_valid ? "V" : "-", wr_ready ? "r" : "-",
+ rd_data, rd_valid ? "v" : "-", rd_ready ? "R" : "-",
+ chk_data, rd_count);
+
+ if (rd_valid && rd_ready) begin
+ if (rd_data != chk_data) begin
+ $display("%d: rd_data(%08x) != chk_data(%08x)",
+ count, rd_data, chk_data);
+ error_n = 1;
+ end else begin
+ rd_count_n = rd_count + 32'd1;
+ end
+ end
+
+ case (count)
+ 32'd2: wr_valid_n = 1;
+ 32'd3: wr_valid_n = 0;
+ 32'd4: wr_valid_n = 1;
+ 32'd12: wr_valid_n = 0;
+ 32'd14: rd_ready_n = 1;
+ 32'd24: rd_ready_n = 0;
+ 32'd26: wr_valid_n = 1;
+ 32'd46: rd_ready_n = 1;
+ 32'd47: rd_ready_n = 0;
+ 32'd50: rd_ready_n = 1;
+ 32'd68: wr_valid_n = 0;
+ 32'd74: rd_ready_n = 0;
+ 32'd77: rd_ready_n = 1;
+ 32'd90: wr_valid_n = 1;
+ 32'd110: rd_ready_n = 0;
+ 32'd111: rd_ready_n = 1;
+ 32'd112: rd_ready_n = 0;
+ 32'd113: rd_ready_n = 1;
+ 32'd114: rd_ready_n = 0;
+ 32'd115: rd_ready_n = 0;
+ 32'd116: rd_ready_n = 1;
+ 32'd117: rd_ready_n = 1;
+ 32'd118: rd_ready_n = 0;
+ 32'd119: rd_ready_n = 0;
+ 32'd120: rd_ready_n = 0;
+ 32'd121: rd_ready_n = 1;
+ 32'd122: rd_ready_n = 1;
+ 32'd123: rd_ready_n = 1;
+ 32'd134: wr_valid_n = 0;
+ 32'd150: wr_valid_n = 1;
+ 32'd151: wr_valid_n = 0;
+ 32'd152: wr_valid_n = 1;
+ 32'd153: wr_valid_n = 1;
+ 32'd154: wr_valid_n = 0;
+ 32'd155: wr_valid_n = 0;
+ 32'd156: wr_valid_n = 0;
+ 32'd157: wr_valid_n = 1;
+ 32'd158: wr_valid_n = 1;
+ 32'd159: wr_valid_n = 1;
+ 32'd170: rd_ready_n = 0;
+ 32'd173: begin rd_ready_n = 1; wr_valid_n = 1; end
+ 32'd174: begin rd_ready_n = 0; wr_valid_n = 0; end
+ 32'd180: rd_ready_n = 1;
+ 32'd187: rd_ready_n = 0;
+ 32'd200: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd201: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd202: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd203: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd204: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd205: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd206: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd207: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd208: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd209: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd210: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd211: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd212: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd213: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd214: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd215: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd216: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd217: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd218: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd219: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd220: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd221: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd222: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd223: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd224: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd225: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd226: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd227: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd228: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd229: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd230: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd231: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd232: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd233: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd234: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd236: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd237: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd238: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd240: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd241: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd242: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd243: begin wr_valid_n = 0; rd_ready_n = 0; end
+ 32'd244: begin wr_valid_n = 1; rd_ready_n = 1; end
+ 32'd245: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd246: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd247: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd248: begin wr_valid_n = 1; rd_ready_n = 0; end
+ 32'd249: begin wr_valid_n = 0; rd_ready_n = 1; end
+ 32'd255: begin wr_valid_n = 1; rd_ready_n = 1; end
+
+ 32'd500: begin
+ $display("did not read all data");
+ error_n = 1;
+ end
+ default: ;
+ endcase
+
+ if (rd_count == 128) done_n = 1;
+end
+
+always_ff @(posedge clk) begin
+ count <= count + 32'd1;
+ rd_count <= rd_count_n;
+ rd_ready <= rd_ready_n;
+ wr_valid <= wr_valid_n;
+ done = done_n;
+ error = error_n;
+end
+
+sync_fifo #(
+ .WIDTH(32),
+ .DEPTH(4)
+ ) fifo (
+ .clk(clk),
+ .wr_data(wr_data),
+ .wr_valid(wr_valid),
+ .wr_ready(wr_ready),
+ .rd_data(rd_data),
+ .rd_valid(rd_valid),
+ .rd_ready(rd_ready)
+);
+
+// write data stream
+// cue up a new value next clock, whenever
+// the current value would have been accepted
+xorshift32 xs32wr (
+ .clk(clk),
+ .ready(wr_valid & wr_ready),
+ .data(wr_data)
+);
+
+// read verification data stream
+// cue up a new value next clock, whenever
+// the current value would have been checked
+xorshift32 xs32rd (
+ .clk(clk),
+ .ready(rd_valid & rd_ready),
+ .data(chk_data)
+);
+
+endmodule
diff --git a/hdl/xorshift.sv b/hdl/xorshift.sv
@@ -0,0 +1,25 @@
+// Copyright 2020, Brian Swetland <swetland@frotz.net>
+// Licensed under the Apache License, Version 2.0.
+
+`default_nettype none
+
+module xorshift32 #(
+ parameter INITVAL = 32'hebd5a728
+ ) (
+ input wire clk,
+ input wire ready,
+ output reg [31:0]data = INITVAL
+);
+
+// $ echo -n xorshiftrulz | sha256sum | cut -c 1-8
+// ebd5a728
+
+wire [31:0] nxt1 = data ^ { data[18:0], 13'd0 };
+wire [31:0] nxt2 = nxt1 ^ { 17'd0, nxt1[31:17] };
+wire [31:0] nxt3 = nxt2 ^ { nxt2[26:0], 5'd0 };
+
+always_ff @(posedge clk)
+ if (ready) data <= nxt3;
+
+endmodule
+
diff --git a/project/test-sync-fifo.def b/project/test-sync-fifo.def
@@ -0,0 +1,5 @@
+
+PROJECT_TYPE := verilator-sim
+
+PROJECT_SRCS := hdl/sync_fifo_test.sv hdl/sync_fifo.sv hdl/xorshift.sv
+
