From ad3d4a0a3260b90e281bc134725a0327d7b8a4fa Mon Sep 17 00:00:00 2001 From: adam Date: Fri, 24 Aug 2007 02:37:32 +0100 Subject: [PATCH] implement bitfifo (software only for now) --- ships/Alu3.ship | 28 +- ships/BitFifo.ship | 312 +++++++++----------- src/edu/berkeley/fleet/assembler/fleet.g | 2 +- .../berkeley/fleet/doc/BenkoBoxDescription.java | 5 +- src/edu/berkeley/fleet/doc/Constant.java | 2 +- src/edu/berkeley/fleet/interpreter/Inbox.java | 2 +- 6 files changed, 172 insertions(+), 179 deletions(-) diff --git a/ships/Alu3.ship b/ships/Alu3.ship index b79ef58..13733c6 100644 --- a/ships/Alu3.ship +++ b/ships/Alu3.ship @@ -110,6 +110,7 @@ public void service() { #ship lut3 : Lut3 #ship bitfifo : BitFifo #ship debug : Debug +#ship fifo : Fifo #expect 31509911677 #expect 1855678 @@ -119,12 +120,27 @@ public void service() { // 1: 111000101000011000011 // r: 111000100110111000000 -1000000: sendto bitfifo.inEnqueue; -0: sendto bitfifo.inEnqueue; -bitfifo.inEnqueue: [*] take, deliver; -bitfifo.outDequeue: [*] wait, take, sendto lut3.in2; -lut3.in2: [4] notify bitfifo.outDequeue; - [74] take, deliver, notify bitfifo.outDequeue; +1000000: sendto bitfifo.in; +0: sendto bitfifo.in; + +bitfifo.in: + deliver; // deliver a junk word + take; // wait for the argument + [37] deliver; // deliver it 37 times (once per bit) + take; // wait for the zero-word + [38] deliver; // deliver it 37 times + +// insert bits in lsb order +BitFifo.inOp[lsbFirst,take=37]: sendto bitfifo.inOp; +bitfifo.inOp: take; [*] deliver; + +// toss out 37 bits, take one, repeat. sign extend the result +BitFifo.outOp[drop=37,take=1,signExtend]: sendto bitfifo.outOp; +bitfifo.outOp: take; [*] deliver; + +bitfifo.out: [*] wait, take, sendto lut3.in2; +lut3.in2: [4] notify bitfifo.out; + [74] take, deliver, notify bitfifo.out; // mux on second input 226: sendto lut3.inLut; diff --git a/ships/BitFifo.ship b/ships/BitFifo.ship index facf07d..3b742de 100644 --- a/ships/BitFifo.ship +++ b/ships/BitFifo.ship @@ -1,93 +1,54 @@ ship: BitFifo == Ports =========================================================== -in: inEnqueue -in: inEnqueueOp - constant rev: .......................1............. - constant inv: ........................1............ - constant count: .........................nnnnnn...... - constant offset: ...............................nnnnnn - -out: outDequeue -in: inDequeueOp +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........ + -== 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 ======================================================== +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. -== TeX ============================================================== +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. -\begin{verbatim} -+-------------+ +---------------+ +------------+ -| inEnqueue |-->| |-->| outDequeue | -+-------------+ | | +------------+ - | BitFifo | -+-------------+ | | +-------------+ -| inEnqueueOp |-->| |<--| inDequeueOp | -+-------------+ +---------------+ +-------------+ -\end{verbatim} +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. -\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} -} +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. -\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} -} +Whenever a full word is present in the fifo, it will be made available +for dequeueing at the {\tt out} port. -\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} +\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} == Fleeterpreter ==================================================== @@ -105,6 +66,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; @@ -306,63 +274,70 @@ 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! -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); - return; - } - if (box_outDequeue.readyForDataFromShip() && bits.size() > 0) { - long data = bits.get(1) == 0 ? 0L : 0x1FFFFFFFFFL; - box_outDequeue.addDataFromShip(data); - return; - } +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 (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<> (64 - val); + 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<> 1; end end @@ -388,52 +363,51 @@ public void service() { == 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 +#expect 1 +#expect 68719476736 +#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.out: [*] take, sendto debug.in; debug.in: [*] take, deliver; -99: sendto bitfifo.inEnqueue; -bitfifo.inEnqueue: take, deliver; -bitfifo.outDequeue: [*] take, sendto debug.in; + == Contributors ========================================================= Amir Kamil diff --git a/src/edu/berkeley/fleet/assembler/fleet.g b/src/edu/berkeley/fleet/assembler/fleet.g index 4158d18..e22fa02 100644 --- a/src/edu/berkeley/fleet/assembler/fleet.g +++ b/src/edu/berkeley/fleet/assembler/fleet.g @@ -46,7 +46,7 @@ Port = Port:: shipname "." portname | ^"()" SSLSpec:: = SSLElement +/ "," -SSLElement = "":: [a-zA-Z0-9=_]++ +SSLElement = "":: [a-zA-Z0-9=_\-]++ CodeBagBody:: = Statement +/ ws CodeBag = CodeBagRef:: CodeBagName diff --git a/src/edu/berkeley/fleet/doc/BenkoBoxDescription.java b/src/edu/berkeley/fleet/doc/BenkoBoxDescription.java index 8cead4b..f86c016 100644 --- a/src/edu/berkeley/fleet/doc/BenkoBoxDescription.java +++ b/src/edu/berkeley/fleet/doc/BenkoBoxDescription.java @@ -47,15 +47,18 @@ public class BenkoBoxDescription implements Iterable { public long resolveLiteral(String s) { long val = 0; long ret = 0; + boolean hasval = false; if (s.indexOf('=') != -1) { val = Long.parseLong(s.substring(s.indexOf('=')+1)); s = s.substring(0, s.indexOf('=')); + hasval = true; } Constant c = getConstant(s); if (c==null) throw new RuntimeException("no constant " + s + " on benkobox " + this); ret |= c.setbits; ret &= ~c.clearbits; - // FIXME: val + if (hasval) + ret |= ((~(0xffffffffffffffffL << c.numberWidth)) & val) << c.numberOffset; return ret; } } diff --git a/src/edu/berkeley/fleet/doc/Constant.java b/src/edu/berkeley/fleet/doc/Constant.java index 5756ea9..f6d04a0 100644 --- a/src/edu/berkeley/fleet/doc/Constant.java +++ b/src/edu/berkeley/fleet/doc/Constant.java @@ -16,7 +16,7 @@ public class Constant { setbits = Long.parseLong(s.substring(2), 16); clearbits = ~setbits; } else if (s.length() == 37) { - for(int i=0; i<37; i++) { + for(int i=36; i>=0; i--) { char c = s.charAt(36-i); switch(c) { case '0': clearbits |= (1< itemsFromFabric = new LinkedList(); -- 1.7.10.4