Fix a parameterized FIFO whose write pointer wraps at the wrong place when DEPTH is not a power of two.
Hardware context: Clocked FIFO plus ready/valid output adapter. Implement the actual parameterized FIFO RTL.
A FIFO passed every test at depth 4 and depth 8. At depth 3 it returned old data after the second fill. The bug is in how a pointer wraps.
The module submitted_fifo is a synchronous FIFO with parameters DEPTH and WIDTH. It keeps its entries in a ring of memory, with a write pointer and a read pointer. It has one bug. Find it and fix it.
The tests run five copies side by side. Their (DEPTH, WIDTH) pairs are (1, 1), (2, 8), (3, 8), (5, 17) and (8, 32). Each test drives 32 clock edges. An independent queue model checks every flag, response and reset after every edge.
The rules in brief: a write is accepted when the FIFO is not full, and a read when it is not empty. Both use the count from before the edge. A read returns its entry with read_valid = 1 right after the accepting edge. Reset wins and empties the FIFO.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
profile | 3 | input of each check |
controls | 96 | input of each check |
values0 | 256 | input of each check |
values1 | 256 | input of each check |
values2 | 256 | input of each check |
values3 | 256 | input of each check |
Full specification
module submitted_fifo #(parameter int DEPTH = 3, WIDTH = 8, FAULT = 0) (
input bit clk, initialize, reset, write_en, read_en,
input bit [31:0] write_data,
output wire full, empty, read_valid,
output wire [31:0] read_data);
// your FIFO
endmodule
| Rule | What a correct FIFO does |
|---|---|
| Write | Accepted when reset = 0, write_en = 1 and fewer than DEPTH entries are stored before the edge. write_data joins the back. |
| Read | Accepted when reset = 0, read_en = 1 and at least one entry is stored before the edge. The oldest entry leaves. |
| Both on one edge | Both decisions use the count before the edge. When empty, only the write is accepted. When full, only the read is accepted. Otherwise the read takes the oldest entry and the write joins the back. |
| Response | The edge that accepts a read loads the response registers. Right after that edge, read_valid = 1 and read_data holds the entry. This is true even when the read leaves the FIFO empty. |
| No read | After an edge that accepts no read, read_valid = 0. read_data may then hold any old value. |
| Reset | reset is synchronous, active high, and wins over both requests. It empties the FIFO and clears read_valid and read_data to 0. |
| Flags | full = 1 exactly when DEPTH entries are stored. empty = 1 exactly when none are. Both follow the count with no delay. |
| Design rule | Meaning |
|---|---|
| Storage | Clocked memory with nonblocking updates. Only addresses 0 to DEPTH - 1 hold entries. |
| Pointers | A pointer moves only when its request is accepted. It wraps from DEPTH - 1 back to 0, not at the next power of two. |
| Width | Only the low WIDTH bits of write_data are stored. read_data is the stored value with zeros above it. |
| Memory size | The memory array is rounded up to a power of two. The extra slots exist only so that a wrong wrap gives a repeatable result. |
| initialize | A test-only input. It clears everything, memory included, before each test. FAULT is unused and always 0. |
Depth 1 is legal. Avoid declaring a vector of zero width for it.
The result has error_edges, with bit i set when edge i broke a rule, counting edges from 0. It also counts accepted writes, accepted reads, entries thrown away by reset and reset edges. final_queued is the number of entries left, and depth names the copy under test.
Examples
Example 1
Depth 1 and Width 1- Input
(DEPTH, WIDTH) = (1, 1): write+read 0x11, read, write 0x30, write 0xee, write+read 0xef, write+read 0x71, reset with write+read 0x99, write 0x81, read, read, then idle
- Output
error_edges = {}, accepted_writes = 4, accepted_reads = 3, reset_discarded = 1, reset_edges = 1, final_queued = 0, depth = 1
Only the low bit of each value is stored. With one slot, full and empty swap on every accepted request. A write offered while full is refused. Reset throws away the stored entry before the last write and read.
Example 2
Depth 3 Keeps the Oldest Entry First- Input
(3, 8): write+read 0x11, read, write 0x30, 0x31, 0x32, write 0xee, write+read 0xef, write+read 0x71, reset with write+read 0x99, write 0x81, read, read, then idle
- Output
error_edges = {}, accepted_writes = 6, accepted_reads = 4, reset_discarded = 2, reset_edges = 1, final_queued = 0, depth = 3
When full, write+read 0xef returns 0x30 and refuses 0xef. The next write+read returns 0x31 and stores 0x71. Reset then throws away 0x32 and 0x71. The last response is 0x81.
Example 3
Width 17 Drops the High Bits- Input
(5, 17): write 0x1ffff, write 0x20000, read, read, reset with write+read 0xffffffff, then idle
- Output
error_edges = {}, accepted_writes = 2, accepted_reads = 2, reset_discarded = 0, reset_edges = 1, final_queued = 0, depth = 5
The two responses are 0x1ffff and 0x00000, because bit 17 is not stored. Reset accepts neither request and leaves the FIFO empty.
Example 4
A Second Fill Shows the Wrong Wrap- Input
(3, 8): write 0x11, 0x22, 0x33, read three times, write 0x44, 0x55, 0x66, read three times, then 20 idle edges
- Output
error_edges = {}, accepted_writes = 6, accepted_reads = 6, reset_discarded = 0, reset_edges = 0, final_queued = 0, depth = 3
All six writes and reads are accepted. The second drain must return 0x44, 0x55 and 0x66 in order. A write pointer that wraps at 4 puts 0x44 in slot 3, and the read returns old data.
Constraints and Contract
- Do not accept a request early. Do not pass write data straight to read_data when the FIFO is empty.
- Use only your ports. Do not read the state of the checker.
- Keep the module name, the parameters and the ports.
Hints
Hint 1
Work through depth 3 by hand: three writes, three reads, then three more writes. Where should the fourth write land?
Hint 2
For DEPTH = 3 the memory has four slots. A pointer that wraps with % over the memory size visits slot 3, which this FIFO must never use.
Hint 3
Wrap a pointer with a compare: if it equals DEPTH - 1, the next value is 0; otherwise add 1. Check that both pointers do this.
What the grader checks: Five copies with (DEPTH, WIDTH) of (1, 1), (2, 8), (3, 8), (5, 17) and (8, 32) run the same traces. An independent queue checks every flag, response, reset and value. The tests wrap the pointers many times, but they are not a proof for every parameter.
59 checks on Verilator · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 9 steps and the final capstone