constant msbFirst: ....................................0
constant drop: .............................uuuuuu..
constant take: .......................uuuuuu........
+
out: out
in: outOp
constant lsbFirst: ....................................1
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.
-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.
+\subsection*{Dequeueing}
-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.
+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 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.
+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.
-Whenever a full word is present in the fifo, it will be made available
-for dequeueing at the {\tt out} port.
+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}.
-\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}
+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 ====================================================
== FPGA ==============================================================
- reg [73:0] bitstorage;
- reg [7:0] bitstorage_count; initial bitstorage_count = 0;
+`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 (bitstorage_count == 0) begin
- `onread(in_r, in_a)
- bitstorage <= in_d;
- bitstorage_count <= 37;
- out_d <= (in_d[0] ? 37'b1111111111111111111111111111111111111 : 0);
+ 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
- end else begin
- `onwrite(out_r, out_a)
- bitstorage_count <= bitstorage_count - 1;
- out_d <= (bitstorage[1] ? 37'b1111111111111111111111111111111111111 : 0);
- bitstorage <= bitstorage >> 1;
+ 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
+//#expect 12
+//#expect 13
// ships required in order to run this code
#ship debug : Debug
#ship bitfifo : BitFifo
-BitFifo.outOp[take=37]: sendto bitfifo.outOp;
-bitfifo.outOp: take; [*] 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.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;
+
+bitfifo.inOp:
+ literal BitFifo.inOp[take=37];
+ deliver;
+ literal BitFifo.inOp[take=37,lsbFirst];
+ deliver;
== Contributors =========================================================