X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ships%2FBitFifo.ship;h=371abe976b92f674e66fd229abb614c61124f5ba;hb=8051845a0ac645f7629ac7d2c35b61db85d128c4;hp=21fb5289fb0b200669eead7be6d037a1a33dcd17;hpb=ab345c807ad1856b0b12f2d5fd72ee3d059d69c4;p=fleet.git diff --git a/ships/BitFifo.ship b/ships/BitFifo.ship index 21fb528..371abe9 100644 --- a/ships/BitFifo.ship +++ b/ships/BitFifo.ship @@ -1,95 +1,77 @@ ship: BitFifo == Ports =========================================================== -in: inEnqueue - sibling: inEnqueueOp +in: in +in: inOp + constant lsbFirst: ....................................1 + constant msbFirst: ....................................0 + constant drop: .............................uuuuuu.. + constant take: .......................uuuuuu........ -in: inEnqueueOp - constant rev: .......................1............. - constant inv: ........................1............ - constant count: .........................nnnnnn...... - constant offset: ...............................nnnnnn +out: out +in: outOp + constant lsbFirst: ....................................1 + constant msbFirst: ....................................0 + constant signExtend: ...................................1. + constant drop: .............................uuuuuu.. + constant take: ......................0uuuuuu........ + constant copy: ......................1uuuuuu........ -out: outDequeue -in: inDequeueOp -== Sample Code ====================================================== +== 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. -== Constants ======================================================== +\subsection*{Enqueueing} -== TeX ============================================================== +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}. -\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} -} +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. -\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} -} +\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} -\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 Enqueue}) - \item [\tt Offset] ({\bf Offset of Bits To Enqueue}) -\end{itemize} +The text above regarding sign extending and dequeueing +msbFirst/lsbFirst is wrong. == Fleeterpreter ==================================================== @@ -107,6 +89,13 @@ static class BitStorage { 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; @@ -308,48 +297,160 @@ public static void main(String[] args) { private Packet selector; private static final int MAXBITS = 128; private static final int WORDSIZE = 37; -private BitStorage bits = new BitStorage(MAXBITS); +private Queue bits = new LinkedList(); +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_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(); + if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) { + long op = box_inOp.removeDataForShip(); + long data = box_in.removeDataForShip(); - String port = selector.destination.getDestinationName(); - long val = selector.value; // check if <= 37? + 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 (port.startsWith("takeInv") || port.startsWith("dropInv")) { - val = 37 - val; - } - if (val < bits.size()) { + if (!rev) + for(long i=take-1-drop; i>=0; i--) + add( (data & (1L<> (64 - val); + 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=0; i--) + if (get()) ret |= 1L< 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; [2] deliver; + +bitfifo.inOp: + literal BitFifo.inOp[take=37]; + deliver; + literal BitFifo.inOp[take=37,lsbFirst]; + deliver; + == Contributors ========================================================= Amir Kamil +Adam Megacz