ship: BitFifo

== Ports ===========================================================
in:   inEnqueue
in:   inEnqueueOp
  constant rev:      .......................1.............
  constant inv:      ........................1............
  constant count:    .........................nnnnnn......
  constant offset:   ...............................nnnnnn

out:  outDequeue
in:   inDequeueOp
  
== Sample Code ======================================================


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

== TeX ==============================================================

\begin{verbatim}
+-------------+   +---------------+   +------------+
| inEnqueue   |-->|               |-->| outDequeue |
+-------------+   |               |   +------------+
                  |    BitFifo    |
+-------------+   |               |   +-------------+
| inEnqueueOp |-->|               |<--| inDequeueOp |
+-------------+   +---------------+   +-------------+
\end{verbatim}

\section*{inEnqueueOp}
\setlength{\bitwidth}{6mm}
{\tt\footnotesize
\begin{bytefield}{14}
  \bitheader[b]{0,5,6,11,12,13}\\
  \bitbox{1}{Rev} 
  \bitbox{1}{Inv} 
  \bitbox{6}{Count} 
  \bitbox{6}{Offset} 
\end{bytefield}
}

\begin{itemize}
   \item [\tt Rev]    ({\bf Reverse Before Enqueue})
   \item [\tt Inv]    ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
   \item [\tt Count]  ({\bf Count of Bits To Enqueue})
   \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
\end{itemize}

By default, bits are enqueued {\it most significant bit first} (bits
in Sun byte order).  If {\tt Rev=1}, the bits are reversed before
performing the directions below.

If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
was actually {\tt 37-Offset-Count} for all directions below.



\pagebreak

\section*{inDequeueOp}
\setlength{\bitwidth}{6mm}
{\tt\scriptsize
\begin{bytefield}{23}
  \bitheader[b]{0,5,6,11-21,22}\\
  \bitbox{2}{Until} 
  \bitbox{1}{Sort} 
  \bitbox{1}{Get} 
  \bitbox{1}{Rev} 
  \bitbox{1}{Inv} 
  \bitbox{1}{Rst} 
  \bitbox{2}{Left\\ Fill} 
  \bitbox{2}{Right\\ Fill} 
  \bitbox{6}{Count} 
  \bitbox{6}{Offset} 
\end{bytefield}
}

\begin{itemize}
   \item [\tt Until]       ({\bf Shift until you see a (0, 1)})
   \item [\tt Sort]        ({\bf Sort the Bits})
   \item [\tt Get]         ({\bf Get the value of the counter})
   \item [\tt Rev]         ({\bf Reverse Before Enqueue})
   \item [\tt Inv]         ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
   \item [\tt Rst]         ({\bf Reset Counter Before Operation})
   \item [\tt Left Fill]   ({\bf Left Fill (0, 1, sign)})
   \item [\tt Right Fill]  ({\bf Right Fill (0, 1, sign)})
   \item [\tt Count]       ({\bf Count of Bits To Dequeue})
   \item [\tt Offset]      ({\bf Offset of Bits To Dequeue})
\end{itemize}


== Fleeterpreter ====================================================
// Internal storage
static class BitStorage {
  long[] bits;
  int numbits = 0;
  int start = 0;
  BitStorage(int size) {
    bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  }
  int size() {
    return numbits;
  }
  boolean hasSpace(int num) {
    return bits.length * 64 - numbits >= num;
  }
  boolean add(long data, int num) {
    if (!hasSpace(num)) return false;
    int entry = ((numbits + start) / 64) % bits.length;
    int off = (numbits + start) % 64;
    int maxadd = 64 - off;
    long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
    bits[entry] = (bits[entry] & mask) | (data << off);
    if (num > maxadd) {
      numbits += maxadd;
      return add(data >>> maxadd, num - maxadd);
    } else {
      numbits += num;
      return true;
    }
  }
  long get(int num) {
    assert size() >= num : "too few bits in storage";
    int entry = start / 64;
    int off = start % 64;
    int max = 64 - off;
    int n = num > max ? max : num;
    long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
    long res = (bits[entry] >>> off) & mask;
    int oldstart = start;
    if (n < num) {
      int n2 = num - n;
      long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
      res |= (bits[(entry + 1) % bits.length] & mask2) << n;
    }
    start = (start + num) % (64 * bits.length);
    numbits -= num;
    return res;
  }
  int capacity() {
    return 64 * bits.length;
  }
  // Test code for BitStorage
  static void test3(String[] args) {
      BitStorage bs = new BitStorage(37);
      Random rand = new Random();
      Vector ins = new Vector();
      Vector ret = new Vector();
      StringBuffer sbi = new StringBuffer();
      StringBuffer sbr = new StringBuffer();
      System.out.println("==== Test #3 ====");
      System.out.println("inserting...");
      long data = rand.nextLong();
      bs.add(data, 0);
      ins.add(new Integer(0));
      data = rand.nextLong();
      int num = rand.nextInt(37);
      int s = bs.size();
      bs.add(data, num);
      assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
      ins.add(new Integer(num));
      add(sbi, data, num);
      print(data, num);
      System.out.println("\nretrieving...");
      num = bs.size();
      data = bs.get(num);
      ret.add(new Integer(num));
      add(sbr, data, num);
      print(data, num);
      System.out.println("\ninsertion sequence:");
      for (int i = 0; i < ins.size(); i++) {
	  System.out.print(" " + ins.get(i));
      }
      System.out.println("\nretrieval sequence:");
      for (int i = 0; i < ret.size(); i++) {
	  System.out.print(" " + ret.get(i));
      }
      System.out.println();
      check(sbi, sbr);
  }
  static void test2(String[] args) {
      int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
      BitStorage bs = new BitStorage(37 * iters);
      Random rand = new Random();
      Vector ins = new Vector();
      Vector ret = new Vector();
      StringBuffer sbi = new StringBuffer();
      StringBuffer sbr = new StringBuffer();
      System.out.println("==== Test #2 ====");
      for (int i = 0; i < iters; i++) {
	  long data = rand.nextLong();
	  int num = rand.nextInt(37);
	  int s = bs.size();
	  bs.add(data, num);
	  assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
	  ins.add(new Integer(num));
	  add(sbi, data, num);
	  num = rand.nextInt(Math.min(37, bs.size()));
	  s = bs.size();
	  data = bs.get(num);
	  assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
	  ret.add(new Integer(num));
	  add(sbr, data, num);
      }
      //for (int i = 0; i < iters; i++) {
      while (bs.size() > 0) {
	  int num = Math.min(rand.nextInt(37), bs.size());
	  //int num = Math.min(33, bs.size());
	  int s = bs.size();
	  long data = bs.get(num);
	  assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
	  ret.add(new Integer(num));
	  add(sbr, data, num);
      }
      System.out.println("inserted:");
      System.out.println(sbi);
      System.out.println("retrieved:");
      System.out.println(sbr);
      System.out.println("insertion sequence:");
      for (int i = 0; i < ins.size(); i++) {
	  System.out.print(" " + ins.get(i));
      }
      System.out.println("\nretrieval sequence:");
      for (int i = 0; i < ret.size(); i++) {
	  System.out.print(" " + ret.get(i));
      }
      System.out.println();
      check(sbi, sbr);
  }
  static void test1(String[] args) {
      int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
      BitStorage bs = new BitStorage(37 * iters);
      Random rand = new Random();
      Vector ins = new Vector();
      Vector ret = new Vector();
      StringBuffer sbi = new StringBuffer();
      StringBuffer sbr = new StringBuffer();
      System.out.println("==== Test #1 ====");
      System.out.println("inserting...");
      for (int i = 0; i < iters; i++) {
	  long data = rand.nextLong();
	  int num = rand.nextInt(37);
	  int s = bs.size();
	  bs.add(data, num);
	  assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
	  ins.add(new Integer(num));
	  add(sbi, data, num);
	  print(data, num);
      }
      System.out.println("\nretrieving...");
      //for (int i = 0; i < iters; i++) {
      while (bs.size() > 0) {
	  int num = Math.min(rand.nextInt(37), bs.size());
	  //int num = Math.min(33, bs.size());
	  int s = bs.size();
	  long data = bs.get(num);
	  assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
	  ret.add(new Integer(num));
	  add(sbr, data, num);
	  print(data, num);
      }
      System.out.println("\ninsertion sequence:");
      for (int i = 0; i < ins.size(); i++) {
	  System.out.print(" " + ins.get(i));
      }
      System.out.println("\nretrieval sequence:");
      for (int i = 0; i < ret.size(); i++) {
	  System.out.print(" " + ret.get(i));
      }
      System.out.println();
      check(sbi, sbr);
  }
  static void print(long data, int num) {
      for (int i = 0; i < num; i++) {
	  System.out.print((data >>> i) & 0x1);
      }
  }
  static void add(StringBuffer sb, long data, int num) {
      for (int i = 0; i < num; i++) {
	  sb.append((int) ((data >>> i) & 0x1));
      }
  }
  static void check(StringBuffer sb1, StringBuffer sb2) {
      int len = sb2.length();
      if (len > sb1.length()) {
	  System.out.println("error: retrieval sequence is longer than insertion sequence");
	  len = sb1.length();
      }
      for (int i = 0; i < sb2.length(); i++) {
	  if (sb1.charAt(i) != sb2.charAt(i)) {
	      System.out.println("error: bit at position " + i + " does not match");
	  }
      }
  }
}

// Run BitStorage tests
public static void main(String[] args) {
    BitStorage.test1(args);
    BitStorage.test2(args);
    BitStorage.test3(args);
}

// Ship implementation
private Packet selector;
private static final int MAXBITS = 128;
private static final int WORDSIZE = 37;
private BitStorage bits = new BitStorage(MAXBITS);

// dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
public void service() {
  if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
  if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
    long data = box_inEnqueue.removeDataForShip();
    bits.add(data, WORDSIZE);
    return;
  }
  if (box_outDequeue.readyForDataFromShip() && bits.size() > 0) {
    long data = bits.get(1) == 0 ? 0L : 0x1FFFFFFFFFL;
    box_outDequeue.addDataFromShip(data);
    return;
  }
}

/*
public void service() {
  if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
  if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
    long data = box_inEnqueue.removeDataForShip();
    bits.add(data, WORDSIZE);
  }
  if (selector == null && !box_inEnqueueOp.dataReadyForShip()) return;
  if (selector == null) selector = box_inEnqueueOp.removePacketForShip();

  String port = selector.destination.getDestinationName();
  long val = selector.value; // check if <= 37?

  if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
    val = 37 - val;    
  }
  if (val < bits.size()) {
    return;
  }

  if (port.startsWith("take")) {
    if (!box_outDequeue.readyForDataFromShip()) return;
    long data = bits.get((int) val);
    if (port.endsWith("FillOnes")) {
      data |= (-1L << val);
    } else if (port.endsWith("SignExtend")) {
      data = (data << (64 - val)) >> (64 - val);
    }
    box_outDequeue.addDataFromShip(data);
    selector = null;
    return;
  } else {
    bits.get((int) val);
    selector = null;
    return;
  }
}
*/

== FleetSim ==============================================================

== FPGA ==============================================================
  reg [73:0] bitstorage;
  reg [7:0] bitstorage_count;          initial bitstorage_count = 0;

  always @(posedge clk) begin
    if (bitstorage_count == 0) begin
      `onread(inEnqueue_r, inEnqueue_a)
        bitstorage       <= inEnqueue_d;
        bitstorage_count <= 37;
        outDequeue_d     <= (inEnqueue_d[0] ? 37'b1111111111111111111111111111111111111 : 0);
      end
    end else begin
      `onwrite(outDequeue_r, outDequeue_a)
        bitstorage_count <= bitstorage_count - 1;
        outDequeue_d     <= (bitstorage[1] ? 37'b1111111111111111111111111111111111111 : 0);
        bitstorage       <= bitstorage >> 1;
      end
    end
  end


== Test ==============================================================

// expected output
#expect 137438953471
#expect 137438953471
#expect 0
#expect 0
#expect 0
#expect 137438953471
#expect 137438953471
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0
#expect 0

// ships required in order to run this code
#ship debug        : Debug
#ship bitfifo      : BitFifo

debug.in:           [*] take, deliver;
99:                 sendto bitfifo.inEnqueue;
bitfifo.inEnqueue:  take, deliver;
bitfifo.outDequeue: [*] take, sendto debug.in;

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