G8.10.1 A Stack That Refuses to Overflow

EasyImplementIcarus Verilog + Yosys · serverReview the topic

Build an eight-word stack that refuses a push when full and a pop when empty. A push and pop together replace the top.

Hardware context: The operand stack of a hardware expression evaluator, eight words deep. Build a stack with one pointer that survives too many pushes and too many pops.

An expression evaluator keeps its operands on a small hardware stack. Bad input can push too many operands or pop too many. The stack must survive both and keep its words.

This is an Implement problem. Write stack8: eight words of 8 bits, with one pointer. A push when full and a pop when empty are refused and change nothing.

A push and a pop in the same cycle replace the top word with din. The test checks the top, the count and both flags after every clock edge.

Signals in the Timeline

SignalWidthRole
ins240input of each check
Full specification
The module you write (keep the name and the ports)
module stack8 (
  input  logic       clk,
  input  logic       rst,       // synchronous, active high: the stack becomes empty
  input  logic       push,
  input  logic       pop,
  input  logic [7:0] din,
  output logic [7:0] top,       // the word on top; 00 when the stack is empty
  output logic [3:0] count,     // the number of words: 0 to 8
  output logic       full,
  output logic       empty
);
  // your design
endmodule
pushpopEffect at the rising edge
10din goes on top. Refused when the stack holds 8 words.
01The top word is removed. Refused when the stack is empty.
11The top word is replaced by din; the count does not change. On an empty stack this is a plain push.
00Nothing.
OutputDefinition
topThe newest word on the stack; 00 when empty.
countThe number of words, 0 to 8.
full, emptycount = 8, and count = 0.
ResetAt a rising edge with rst = 1 the stack becomes empty.

Each test resets the stack and then runs 24 cycles. The outputs are checked just after every edge. The result has three fields.

FieldMeaning
wrong_topHow many cycles showed the wrong top word.
wrong_countHow many cycles showed the wrong count.
wrong_flagsHow many cycles showed a wrong full or empty.

Examples

Example 1

Push Three, Pop Three
Input
push 10, push 11, push 12, pop, pop, pop, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -
Output
wrong_top = 0, wrong_count = 0, wrong_flags = 0, cycles = 24

The words come back newest first: 12, then 11, then 10. After the third pop the stack is empty and top is 00.

Example 2

One Push Too Many
Input
push 20, push 21, push 22, push 23, push 24, push 25, push 26, push 27, push 28, push 29, pop, pop, -, -, -, -, -, -, -, -, -, -, -, -
Output
wrong_top = 0, wrong_count = 0, wrong_flags = 0, cycles = 24

Eight pushes fill the stack. The ninth and tenth are refused: count stays 8 and the top stays 27.

Example 3

Pops from an Empty Stack
Input
pop, pop, push 31, pop, pop, push 32, push 33, pop, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -
Output
wrong_top = 0, wrong_count = 0, wrong_flags = 0, cycles = 24

The first two pops find nothing and are refused. A stack whose pointer wraps here loses the pushes that follow.

Constraints and Contract

  • The inputs are known 0/1 values. They change while the clock is low.
  • Keep the module name and the ports.

Hints

Hint 1

One pointer is enough. Let it count the words: 0 is empty and 8 is full. It needs 4 bits.

Hint 2

The next free slot is mem[sp], and the top word is mem[sp - 1]. Take the slot index from the low 3 bits.

Hint 3

Check the case of push and pop together first: replace mem[sp - 1] and leave the pointer alone.

What the grader checks: Six directed and eight seeded scripts of 24 cycles. Every output is compared with a JavaScript model just after every edge. An overflow error output and a stack held in an SRAM macro are outside this problem.

The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.

14 checks on Icarus Verilog + Yosys · 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 1 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Push Three, Pop Three

Input
push 10, push 11, push 12, pop, pop, pop, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -
Expected output
wrong_top = 0, wrong_count = 0, wrong_flags = 0, cycles = 24

The words come back newest first: 12, then 11, then 10. After the third pop the stack is empty and top is 00.

Run samples executes all 3 public checks. Check all tests runs 14 checks on the server.

Icarus Verilog + Yosys · server