ship: Stack

== Ports ===========================================================
data  in:   push
data  out:  pop

== Constants ========================================================

== TeX ==============================================================
A stack ship with capacity for at least 16 elements.

Push operations are executed as soon as an inbound datum is delivered
to the {\tt push} port.  Completion of a push can be confirmed by
sending a token from the {\tt push} port after {\tt deliver}ing.

Pop operations are executed no earlier than the time at which the {\tt
pop} port attempts to {\tt take} data from the ship.

When the stack becomes full, it will simply not process any new {\tt
push} operations.  When the stack becomes empty, it will simply not
process any new {\tt pop} operations.  Phrased another way, if a {\tt
pop} is issued to an empty stack, that operation will wait for a {\tt
push} to occur; at some point after that, the {\tt pop} will proceed
to pop the pushed value.  There is no ``underflow'' or ``overflow.''

\subsection*{To Do}

There is some difficulty here when it comes to arbitration -- does the
execution of the instruction after the {\tt deliver} to the {\tt push}
port indicate that the value has been safely pushed?  This is much
tricker than it seems.

Perhaps there should be a single port, {\tt operation}, to which
either a {\sc PUSH} or {\sc POP} command is sent.  This would simplify
the arbitration issues.

== Fleeterpreter ====================================================
    private ArrayList<Long> stack = new ArrayList<Long>();
    public void service() {
        if (box_push.dataReadyForShip() && stack.size()<32) {
            stack.add(box_push.removeDataForShip());
        }
        if (box_pop.readyForDataFromShip() && stack.size() > 0) {
            box_pop.addDataFromShip(stack.get(stack.size()-1));
            stack.remove(stack.size()-1);
        }
    }

== FleetSim ==============================================================
== FPGA ==============================================================
/* FIXME: inefficient */
  reg    [(`DATAWIDTH-1):0] mem [4:0];
  reg    [5:0]              depth;
  reg    skip;
  initial depth = 0;

  always @(posedge clk or negedge rst) begin
    if (!rst) depth <= 0;
    else begin
    skip = 0;
    if (depth > 0) begin
      `onwrite(pop_r, pop_a)
        if (depth > 1) begin
          pop_d <= mem[depth-2];
        end
        depth <= depth - 1;
        skip = 1;
      end
    end
    if (!skip && depth < 32) begin
      `onread(push_r, push_a)
        pop_d      <= push_d;
        mem[depth] <= push_d;
        depth      <= depth + 1;
      end
    end
    end
  end


== Test ====================================================
#skip
#ship stack : Stack
#ship stack : Debug

#expect 4
#expect 3
#expect 2
#expect 1
#expect 0

debug.in:  [*] take, deliver;

stack.pop: wait; [*] take, sendto debug.in;

stack.push:
  literal 0; deliver;
  literal 1; deliver;
  literal 2; deliver;
  literal 3; deliver;
  literal 4; deliver;
  notify stack.pop;




== Contributors =========================================================
Adam Megacz <megacz@cs.berkeley.edu>