ship: BitFifo

== Ports ===========================================================
in:   in
in:   inOp
  constant lsbFirst: ....................................1
  constant msbFirst: ....................................0
  constant drop:     .............................uuuuuu..
  constant take:     .......................uuuuuu........

out:  out
in:   outOp
  constant lsbFirst:   ....................................1
  constant msbFirst:   ....................................0
  constant signExtend: ...................................1.
  constant drop:       .............................uuuuuu..
  constant take:       ......................0uuuuuu........
  constant copy:       ......................1uuuuuu........

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

The BitFifo internally stores some number of bits in a fifo structure.
Its capacity is guaranteed to be at least two full machine words or
more.

\subsection*{Enqueueing}

Bits are enqueued by providing a word at the {\tt in} port and a code
word at the {\tt inOp} port (ports are named this way to take
advantage of the switch fabric opcode mechanism \cite{am25}).  As
shown in the constant diagram, this code word has fields {\tt
lsbFirst}, {\tt msbFirst}, {\tt drop}, and {\tt take}.

When a word is consumed from {\tt in}, it is ``oriented'' in either
Most Significant Bit First ({\tt msbFirst}) or Least Significant Bit
First ({\tt lsbFirst}) depending on whether or not these flags are
set.  Based on this orientation, the first {\tt drop} bits are
discarded.  Then the next {\tt take} bits are enqueued into the fifo.
Any remaining bits are discarded.  Attempting to drop or take beyond
the end of a word produces undefined results.

\subsection*{Dequeueing}

Bits are dequeued by providing a code word at the {\tt outOp} port
(despite its name, this is actually an {\it input port}).  As shown in
the constant diagram, this code word has fields {\tt lsbFirst}, {\tt
msbFirst}, {\tt signExtend}, {\tt drop}, {\tt take}, and {\tt copy}
fields.

Before additional processing, {\tt drop} bits are discarded from the
head of the fifo.  Next, bits are dequeued into an empty word-width
register.  If the {\tt msbFirst} flag is set, bits will be deposited
into this register starting with the most significant bit of the
register and working towards the least significant bit.  If the {\tt
lsbFirst} flag is set, bits will be deposited into this register
starting with the {\it least} significant bit of the register and
working towards the {\it most} significant bit.  The number of bits
dequeued is specified by the {\tt take} field.  If the {\tt copy}
field is specified instead, the bits will be {\it copied} out of the
fifo rather than being removed.

Finally, if the {\tt signExtend} bit is set, all bits in the register
which were not filled by bits dequeued from the fifo will be filled
with a copy of {\it the last bit dequeued from the fifo}.

As a final addendum to the above, whenever a request arrives at {\tt
outOp} which requires more bits than are available in the fifo, the
operation will wait until enough bits are present.

\subsection*{To Do}

The text above regarding sign extending and dequeueing
msbFirst/lsbFirst is wrong.


== 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 peekTailBit() {
    int entry = (((numbits-1) + start) / 64) % bits.length;
    int off = ((numbits-1) + start) % 64;
    int maxadd = 64 - off;
    long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
    return (bits[entry] & ~mask) != 0;
  }
  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 Queue bits = new LinkedList<Boolean>();
boolean last = false;

// dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
private void add(boolean bit) {
  bits.add(bit);
  last = bit;
}
private boolean get() {
  return ((Boolean)bits.remove());
}
boolean haveBoxOutOp;
long  boxOutOp;
public void service() {
  if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
    long op    = box_inOp.removeDataForShip();
    long data  = box_in.removeDataForShip();

    boolean rev = (op & 1) != 0;
    int drop    = (int)((op >> 2) & (~(0xffffffffL << 6)));
    int take    = (int)((op >> 8) & (~(0xffffffffL << 6)));
    if (take==0) { add(last); return; }

    if (!rev)
      for(long i=take-1-drop; i>=0; i--)
        add( (data & (1L<<i)) != 0);
    if (rev)
      for(long i=WORDSIZE-take+drop; i<WORDSIZE; i++)
        add( (data & (1L<<i)) != 0);
    return;
  }

  if (!haveBoxOutOp && box_outOp.dataReadyForShip()) {
     boxOutOp = box_outOp.removeDataForShip();
     haveBoxOutOp = true;
  }

  if (haveBoxOutOp && box_out.readyForDataFromShip()) {
    long op = boxOutOp;
    boolean rev  = (op & 1) != 0;
    boolean sign = (op & 2) != 0;
    boolean copy = (op & (1<<8)) != 0;
    int drop     = (int)((op >> 2) & (~(0xffffffffL << 6)));
    int take     = (int)((op >> 8) & (~(0xffffffffL << 6)));
    if (bits.size() >= take+drop) {
      // FIXME: copy
      for(int i=0; i<drop; i++) get();
      long ret = 0;
      if (!rev) {
        for(long i=take-1; i>=0; i--)
          if (get()) ret |= 1L<<i;
        if (sign && (ret & (1L<<(take-1)))!=0)
          ret |= (0xffffffffffffffffL << take);
      } else {
        for(long i=WORDSIZE-take; i<WORDSIZE; i++)
          if (get()) ret |= 1L<<i;
        // FIXME: sign-extend!
      }
      box_out.addDataFromShip(ret);
      haveBoxOutOp = false;
    }
  }
}


== FPGA ==============================================================
`define BITSTORAGE_SIZE 148
`define BITSTORAGE_BITS 16
`define OP_SIGNEXT 1
`define OP_LSBFIRST 0
`define OP_COUNT 13:8
`define OP_DROP  7:2
  reg [(`BITSTORAGE_SIZE-1):0] bitstorage;
  reg [(`BITSTORAGE_BITS-1):0] bitstorage_count;
  reg [(`BITSTORAGE_BITS-1):0] dequeue_remaining;
  reg [(`BITSTORAGE_BITS-1):0] enqueue_remaining;
  initial dequeue_remaining = 0;
  initial enqueue_remaining = 0;
  initial bitstorage_count = 0;

  always @(posedge clk) begin
    if (!in_r    && in_a)     in_a    <= 0;
    if (!inOp_r  && inOp_a)   inOp_a  <= 0;
    if (!outOp_r && outOp_a)  outOp_a <= 0;

    if (out_r    && out_a)    out_r   <= 0;

    if (dequeue_remaining > 0) begin
      if (dequeue_remaining <= outOp_d[`OP_COUNT])
      begin
        if (outOp_d[`OP_LSBFIRST]) begin
          out_d[`DATAWIDTH-1-(dequeue_remaining-1)] <= bitstorage[0];
        end else begin
          out_d[              dequeue_remaining-1 ] <= bitstorage[0];
        end
      end
      bitstorage[(`BITSTORAGE_SIZE-2):0] <= bitstorage[(`BITSTORAGE_SIZE-1):1];
      bitstorage_count  <= bitstorage_count - 1;
      if (dequeue_remaining == 1) begin
        out_r   <= 1;
        outOp_a <= 1;
      end
      dequeue_remaining <= dequeue_remaining - 1;

    end else if (enqueue_remaining > 0) begin
      bitstorage[bitstorage_count] <=
         inOp_d[`OP_LSBFIRST]
         ?  in_d[`DATAWIDTH-1-(inOp_d[`OP_DROP]+enqueue_remaining-1)]
         :  in_d[              inOp_d[`OP_DROP]+enqueue_remaining-1 ];
      bitstorage_count  <= bitstorage_count + 1;
      if (enqueue_remaining == 1) begin
        in_a   <= 1;
        inOp_a <= 1;
      end
      enqueue_remaining <= enqueue_remaining - 1;

    end else if (in_r && !in_a && inOp_r && !inOp_a && `BITSTORAGE_SIZE > bitstorage_count + inOp_d[`OP_COUNT]) begin
      // FIXME: zero count => lockup
      enqueue_remaining <= inOp_d[`OP_COUNT];

    end else if (!out_r && !out_a && outOp_r && !outOp_a && (bitstorage_count >= (outOp_d[`OP_COUNT]+outOp_d[`OP_DROP]))) begin
      dequeue_remaining <= outOp_d[`OP_COUNT] + outOp_d[`OP_DROP];
      out_d <= (outOp_d[`OP_SIGNEXT] && bitstorage[outOp_d[`OP_DROP]]) ? 37'b1111111111111111111111111111111111111 : 0;

    end
  end


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

// FIXME: this test case is woefully inadequate!!!!!

// expected output
#expect 1
#expect 68719476736
//#expect 12
//#expect 13

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

bitfifo.outOp:      literal BitFifo.outOp[take=37]; [*] deliver;
bitfifo.out:        [*] take, sendto debug.in;
debug.in:           [*] take, deliver;
bitfifo.in:         literal 1; load repeat counter with 2; deliver;

bitfifo.inOp:
  literal BitFifo.inOp[take=37];
  deliver;
  literal BitFifo.inOp[take=37,lsbFirst];
  deliver;


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