X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ships%2FBitFifo.ship;h=371abe976b92f674e66fd229abb614c61124f5ba;hb=36d5276927e1e3f1cd6e12e2db7d7e73f69821da;hp=287692a3a60c03de3a04de91919cdbee72e96c07;hpb=b2659591cbf030b6e6fc5ff68e8f4bcceaafc58c;p=fleet.git diff --git a/ships/BitFifo.ship b/ships/BitFifo.ship index 287692a..371abe9 100644 --- a/ships/BitFifo.ship +++ b/ships/BitFifo.ship @@ -7,6 +7,7 @@ in: inOp constant msbFirst: ....................................0 constant drop: .............................uuuuuu.. constant take: .......................uuuuuu........ + out: out in: outOp constant lsbFirst: ....................................1 @@ -23,32 +24,54 @@ 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. -Bits are enqueued by providing a word at the {\tt in} port and a count -at the {\tt inOp} port (ports are named this way to take advantage of -the switch fabric opcode mechanism). The {\tt inOp} count may be -positive, negative, or zero. +\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. -If the {\tt inOp} count is positive, a word will be taken from the -{\tt in} port and its {\tt count} least significant bits will be -enqueued most-significant-bit first. +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. -If the {\tt inOp} count is zero, a word will be {\it discarded} from -the {\tt in} port and a duplicate copy of the bit at the {\it tail} of -the fifo is enqueued. If the fifo is empty, an undefined bit will be -enqueued. This mechanism is used for sign-extending words. +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}. -If the {\tt inOp} count is negative, a word will be taken from the -{\tt in} port and its {\tt |count|} most significant bits will be -enqueued least-significant-bit first. +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. -Whenever a full word is present in the fifo, it will be made available -for dequeueing at the {\tt out} port. +\subsection*{To Do} -\begin{verbatim} -FIXMEs -- previously I noted that it would be nice to be able to dequeue bits - without consuming them (ie copy-out). What was this needed for? -\end{verbatim} +The text above regarding sign extending and dequeueing +msbFirst/lsbFirst is wrong. == Fleeterpreter ==================================================== @@ -372,11 +395,11 @@ public void service() { end bitstorage[(`BITSTORAGE_SIZE-2):0] <= bitstorage[(`BITSTORAGE_SIZE-1):1]; bitstorage_count <= bitstorage_count - 1; - dequeue_remaining <= dequeue_remaining - 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] <= @@ -384,11 +407,11 @@ public void service() { ? 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; - enqueue_remaining <= enqueue_remaining - 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 @@ -416,42 +439,16 @@ public void service() { #ship debug : Debug #ship bitfifo : BitFifo -BitFifo.outOp[take=37]: sendto bitfifo.outOp; -bitfifo.outOp: take; [*] deliver; - -bitfifo.in: [*] take, deliver; -bitfifo.inOp: [*] take, deliver; +bitfifo.outOp: literal BitFifo.outOp[take=37]; [*] deliver; bitfifo.out: [*] take, sendto debug.in; debug.in: [*] take, deliver; +bitfifo.in: literal 1; [2] deliver; -// FIXME: test the drop capability - -// enqueue -1: sendto bitfifo.in; -BitFifo.inOp[take=37]: sendto bitfifo.inOp; - -// enqueue reversed -1: sendto bitfifo.in; -BitFifo.inOp[take=37,lsbFirst]: sendto bitfifo.inOp; - -// test copy-last-bit -//0: sendto bitfifo.in; -//BitFifo.inOp[take=33]: sendto bitfifo.inOp; -//1: sendto bitfifo.in; -//BitFifo.inOp[take=1]: sendto bitfifo.inOp; -//1: sendto bitfifo.in; -//BitFifo.inOp[take=0]: sendto bitfifo.inOp; -//0: sendto bitfifo.in; -//BitFifo.inOp[take=1]: sendto bitfifo.inOp; -//1: sendto bitfifo.in; -//BitFifo.inOp[take=0]: sendto bitfifo.inOp; -// -//// ordering -//0: sendto bitfifo.in; -//BitFifo.inOp[take=33]: sendto bitfifo.inOp; -//13: sendto bitfifo.in; -//BitFifo.inOp[take=4]: sendto bitfifo.inOp; -// +bitfifo.inOp: + literal BitFifo.inOp[take=37]; + deliver; + literal BitFifo.inOp[take=37,lsbFirst]; + deliver; == Contributors =========================================================