ship: BitFifo
== Ports ===========================================================
-data in: in
+in: inEnqueue
+in: inEnqueueOp
+ constant rev: .......................1.............
+ constant inv: ........................1............
+ constant count: .........................nnnnnn......
+ constant offset: ...............................nnnnnn
-data in: cmd.drop
-data in: cmd.dropInv
-data in: cmd.takeFillZeros
-data in: cmd.takeInvFillZeros
-data in: cmd.takeFillOnes
-data in: cmd.takeInvFillOnes
-data in: cmd.takeSignExtend
-data in: cmd.takeInvSignExtend
+out: outDequeue
+in: inDequeueOp
+
+== Sample Code ======================================================
-data out: out
== Constants ========================================================
== TeX ==============================================================
-+------+ +--------------+ +-------+
-|inData|---| |---|outData|
-+------+ | | +-------+
- | |
-+------+ | | +-------+
-| inOp |---| |---| outOp |
-+------+ +--------------+ +-------+
-
-inOp
-+---+
-| | -- reverse before enqueue
-+---+
-| | -- count := (37-offset-count)
-+---+
-| | -- count (6 bits)
-| |
-| |
-| |
-| |
-+---+
-| | -- offset (6 bits)
-| |
-| |
-| |
-| |
-+---+
-
-outOp
-+---+
-| | -- shift until you see a "Z" (2 bits)
-+---+
-| | -- sort the digits
-+---+
-| | -- give me the count
-+---+
-| | -- reverse after dequeue
-+---+
-| | -- count := 37-off-count
-+---+
-| | -- reset the counter before operation
-+---+
-| | -- fill left with (1,0,sign) (2 bits)
-+---+
-| | -- fill right with (1,0,sign) (2 bits)
-+---+
-| | -- count (6 bits)
-| |
-| |
-| |
-| |
-+---+
-| | -- offset (6 bits)
-| |
-| |
-| |
-| |
-+---+
+\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
-private static class BitStorage {
+static class BitStorage {
long[] bits;
int numbits = 0;
int start = 0;
int entry = ((numbits + start) / 64) % bits.length;
int off = (numbits + start) % 64;
int maxadd = 64 - off;
- bits[entry] = (bits[entry] & (-1L >>> maxadd)) | (data << 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);
int off = start % 64;
int max = 64 - off;
int n = num > max ? max : num;
- long res = (bits[entry] >>> off) & (-1L >>> (64 - n));
+ long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
+ long res = (bits[entry] >>> off) & mask;
int oldstart = start;
if (n < num) {
int n2 = num - n;
- res |= (bits[(entry + 1) % bits.length] & (-1L >>> (64 - n2))) << 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 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);
public static void main(String[] args) {
BitStorage.test1(args);
BitStorage.test2(args);
+ BitStorage.test3(args);
}
// Ship implementation
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_out.readyForDataFromShip() && !box_in.dataReadyForShip()) return;
- if (box_in.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
- long data = box_in.removeDataForShip();
+ 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 (selector == null && !box_cmd.dataReadyForShip()) return;
- if (selector == null) selector = box_cmd.removePacketForShip();
+ 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("take")) {
- if (!box_out.readyForDataFromShip()) return;
+ 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_out.addDataFromShip(data);
+ box_outDequeue.addDataFromShip(data);
selector = null;
return;
} else {
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>
projects / fleet.git / blobdiff