Fix a generator of the shortest write/read trace that exposes a FIFO pointer wrapping at the wrong place.
Hardware context: Clocked FIFO plus ready/valid output adapter. Expose incorrect binary pointer truncation in a non-power-of-two FIFO.
A good bug report has the shortest trace that shows the bug. This function builds that trace for a FIFO pointer that wraps at the next power of two instead of at DEPTH. Its traces stop too early, so they never show the bug.
wrap_witness(depth) returns a plan of length edges. Bit i of the write bitmap is 1 for a write on edge i and 0 for a read. The test writes the value payload_base + i on edge i. Every request in the plan must be accepted by a correct FIFO.
The tests replay the plan on a correct FIFO and on one with a bad pointer, at depth 3 or 5. The plan must make a read return a different value on the two FIFOs. It must also be the shortest such plan, and the first in order when writes sort before reads.
Find the bug and fix it. The specification explains why the shortest plan has 2 × DEPTH + 2 edges.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
profile | 1 | input of each check |
fault | 3 | input of each check |
payload_base | 8 | input of each check |
Full specification
function automatic bit [23:0] wrap_witness(input int depth); // returns {length[7:0], write_bitmap[15:0]}
| Plan rule | Meaning |
|---|---|
| Alphabet | Each edge is a write (W) or a read (R). There is no reset and no write+read on one edge. |
| Legal | A correct FIFO accepts every request in the plan. A write to a full FIFO is not allowed. |
| Shortest | No shorter legal plan shows a difference. |
| First in order | Among plans of that length, pick the first one when W sorts before R. |
| After the plan | Edges after length are idle. Bitmap bits at length and above are 0. |
| Faulty FIFO | What is wrong |
|---|---|
| Fault 6 | The write pointer wraps at the memory size, the next power of two, instead of at DEPTH. |
| Fault 7 | The read pointer wraps at the memory size instead of at DEPTH. |
| Memory | The memory has a power-of-two number of slots, all 0 at the start. A wrong pointer reads or writes a real slot. |
Why 2 × DEPTH + 2: a pointer first goes wrong on its DEPTH-th move. A wrong value shows only on a read after that, so the plan needs DEPTH + 1 reads. Those reads need DEPTH + 1 writes. So no plan is shorter than 2 × DEPTH + 2 edges.
payload_base is 1 to 224 and length is at most 16, so every written value is distinct and not 0.
The result shows your plan and the first edge where the two FIFOs differ. That edge counts from 1, and 0 means no difference. It also shows the value each FIFO returned there, the accepted reads and writes, and the depth.
Examples
Example 1
Depth 3 with a Bad Write Pointer- Input
Depth 3, fault 6, payload_base = 1
- Output
length = 8, write_bitmap = 'b0000000000010111, first_difference = 8, correct_data = 0x5, faulty_data = 0x1, accepted_reads = 4, accepted_writes = 4, depth = 3
The plan WWWRWRRR has 8 edges and bitmap 0x0017. The correct FIFO returns 1, 2, 3 and then 5. The faulty one returns old 1 for the last read, so they differ at edge 8.
Example 2
Depth 5 with a Bad Read Pointer- Input
Depth 5, fault 7, payload_base = 0x10
- Output
length = 12, write_bitmap = 'b0000000001011111, first_difference = 12, correct_data = 0x16, faulty_data = 0x0, accepted_reads = 6, accepted_writes = 6, depth = 5
The plan WWWWWRWRRRRR has 12 edges and bitmap 0x005f. The sixth read should return 0x16. The faulty reader visits empty slot 5 and returns 0, so they differ at edge 12.
Example 3
Distinct Data Keeps the Bug Visible- Input
Depth 3, fault 7, payload_base = 0x80
- Output
length = 8, write_bitmap = 'b0000000000010111, first_difference = 8, correct_data = 0x84, faulty_data = 0x0, accepted_reads = 4, accepted_writes = 4, depth = 3
The same 8-edge plan ends with 0x84 on the correct FIFO and 0 on the faulty one. Because no written value is 0, the difference cannot hide.
Constraints and Contract
- DEPTH is 3 or 5. Both must reach a real difference in read data, not just a different pointer.
- A blocked request is not allowed in the plan, even though the FIFO would ignore it safely.
- Keep the function name, the argument and the 24-bit return value.
Hints
Hint 1
Fill the FIFO as early as the ordering rule allows: DEPTH writes first.
Hint 2
The extra write needs room, so one read comes first. Then drain everything so that the wrapped slot is read.
Hint 3
Count the edges of WWWRWRRR for depth 3. Does the code return that length?
What the grader checks: The plan is replayed on real depth 3 and depth 5 FIFOs, correct and with one bad pointer. The tests also try every shorter legal plan and check the ordering rule. The result covers this write/read language only, not plans with reset or two bad pointers.
31 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