ships/BitFifo.ship

   1 ship: BitFifo
   2
   3 == Ports ===========================================================
   4 in:   inEnqueue
   5 in:   inEnqueueOp
   6   constant rev:      .......................1.............
   7   constant inv:      ........................1............
   8   constant count:    .........................nnnnnn......
   9   constant offset:   ...............................nnnnnn
  10
  11 out:  outDequeue
  12 in:   inDequeueOp
  13
  14 == Constants ========================================================
  15
  16 == TeX ==============================================================
  17
  18 \begin{verbatim}
  19 +-------------+   +---------------+   +------------+
  20 | inEnqueue   |-->|               |-->| outDequeue |
  21 +-------------+   |               |   +------------+
  22                   |    BitFifo    |
  23 +-------------+   |               |   +-------------+
  24 | inEnqueueOp |-->|               |<--| inDequeueOp |
  25 +-------------+   +---------------+   +-------------+
  26 \end{verbatim}
  27
  28 \section*{inEnqueueOp}
  29 \setlength{\bitwidth}{6mm}
  30 {\tt\footnotesize
  31 \begin{bytefield}{14}
  32   \bitheader[b]{0,5,6,11,12,13}\\
  33   \bitbox{1}{Rev}
  34   \bitbox{1}{Inv}
  35   \bitbox{6}{Count}
  36   \bitbox{6}{Offset}
  37 \end{bytefield}
  38 }
  39
  40 \begin{itemize}
  41    \item [\tt Rev]    ({\bf Reverse Before Enqueue})
  42    \item [\tt Inv]    ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
  43    \item [\tt Count]  ({\bf Count of Bits To Enqueue})
  44    \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
  45 \end{itemize}
  46
  47 By default, bits are enqueued {\it most significant bit first} (bits
  48 in Sun byte order).  If {\tt Rev=1}, the bits are reversed before
  49 performing the directions below.
  50
  51 If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
  52 was actually {\tt 37-Offset-Count} for all directions below.
  53
  54
  55
  56 \pagebreak
  57
  58 \section*{inDequeueOp}
  59 \setlength{\bitwidth}{6mm}
  60 {\tt\scriptsize
  61 \begin{bytefield}{23}
  62   \bitheader[b]{0,5,6,11-21,22}\\
  63   \bitbox{2}{Until}
  64   \bitbox{1}{Sort}
  65   \bitbox{1}{Get}
  66   \bitbox{1}{Rev}
  67   \bitbox{1}{Inv}
  68   \bitbox{1}{Rst}
  69   \bitbox{2}{Left\\ Fill}
  70   \bitbox{2}{Right\\ Fill}
  71   \bitbox{6}{Count}
  72   \bitbox{6}{Offset}
  73 \end{bytefield}
  74 }
  75
  76 \begin{itemize}
  77    \item [\tt Until]  ({\bf Shift until you see a (0, 1)})
  78    \item [\tt Sort]   ({\bf Sort the Bits})
  79    \item [\tt Get]    ({\bf Get the value of the counter})
  80    \item [\tt Rev]    ({\bf Reverse Before Enqueue})
  81    \item [\tt Inv]    ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
  82    \item [\tt Rst]    ({\bf Reset Counter Before Operation})
  83    \item [\tt Left Fill]  ({\bf Left Fill (0, 1, sign)})
  84    \item [\tt Right Fill]  ({\bf Right Fill (0, 1, sign)})
  85    \item [\tt Count]  ({\bf Count of Bits To Enqueue})
  86    \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
  87 \end{itemize}
  88
  89
  90 == Fleeterpreter ====================================================
  91 // Internal storage
  92 private static class BitStorage {
  93   long[] bits;
  94   int numbits = 0;
  95   int start = 0;
  96   BitStorage(int size) {
  97     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  98   }
  99   int size() {
 100     return numbits;
 101   }
 102   boolean hasSpace(int num) {
 103     return bits.length * 64 - numbits >= num;
 104   }
 105   boolean add(long data, int num) {
 106     if (!hasSpace(num)) return false;
 107     int entry = ((numbits + start) / 64) % bits.length;
 108     int off = (numbits + start) % 64;
 109     int maxadd = 64 - off;
 110     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
 111     bits[entry] = (bits[entry] & mask) | (data << off);
 112     if (num > maxadd) {
 113       numbits += maxadd;
 114       return add(data >>> maxadd, num - maxadd);
 115     } else {
 116       numbits += num;
 117       return true;
 118     }
 119   }
 120   long get(int num) {
 121     assert size() >= num : "too few bits in storage";
 122     int entry = start / 64;
 123     int off = start % 64;
 124     int max = 64 - off;
 125     int n = num > max ? max : num;
 126     long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
 127     long res = (bits[entry] >>> off) & mask;
 128     int oldstart = start;
 129     if (n < num) {
 130       int n2 = num - n;
 131       long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
 132       res |= (bits[(entry + 1) % bits.length] & mask2) << n;
 133     }
 134     start = (start + num) % (64 * bits.length);
 135     numbits -= num;
 136     return res;
 137   }
 138   int capacity() {
 139     return 64 * bits.length;
 140   }
 141   // Test code for BitStorage
 142   static void test3(String[] args) {
 143       BitStorage bs = new BitStorage(37);
 144       Random rand = new Random();
 145       Vector ins = new Vector();
 146       Vector ret = new Vector();
 147       StringBuffer sbi = new StringBuffer();
 148       StringBuffer sbr = new StringBuffer();
 149       System.out.println("==== Test #3 ====");
 150       System.out.println("inserting...");
 151       long data = rand.nextLong();
 152       bs.add(data, 0);
 153       ins.add(new Integer(0));
 154       data = rand.nextLong();
 155       int num = rand.nextInt(37);
 156       int s = bs.size();
 157       bs.add(data, num);
 158       assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 159       ins.add(new Integer(num));
 160       add(sbi, data, num);
 161       print(data, num);
 162       System.out.println("\nretrieving...");
 163       num = bs.size();
 164       data = bs.get(num);
 165       ret.add(new Integer(num));
 166       add(sbr, data, num);
 167       print(data, num);
 168       System.out.println("\ninsertion sequence:");
 169       for (int i = 0; i < ins.size(); i++) {
 170           System.out.print(" " + ins.get(i));
 171       }
 172       System.out.println("\nretrieval sequence:");
 173       for (int i = 0; i < ret.size(); i++) {
 174           System.out.print(" " + ret.get(i));
 175       }
 176       System.out.println();
 177       check(sbi, sbr);
 178   }
 179   static void test2(String[] args) {
 180       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 181       BitStorage bs = new BitStorage(37 * iters);
 182       Random rand = new Random();
 183       Vector ins = new Vector();
 184       Vector ret = new Vector();
 185       StringBuffer sbi = new StringBuffer();
 186       StringBuffer sbr = new StringBuffer();
 187       System.out.println("==== Test #2 ====");
 188       for (int i = 0; i < iters; i++) {
 189           long data = rand.nextLong();
 190           int num = rand.nextInt(37);
 191           int s = bs.size();
 192           bs.add(data, num);
 193           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 194           ins.add(new Integer(num));
 195           add(sbi, data, num);
 196           num = rand.nextInt(Math.min(37, bs.size()));
 197           s = bs.size();
 198           data = bs.get(num);
 199           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 200           ret.add(new Integer(num));
 201           add(sbr, data, num);
 202       }
 203       //for (int i = 0; i < iters; i++) {
 204       while (bs.size() > 0) {
 205           int num = Math.min(rand.nextInt(37), bs.size());
 206           //int num = Math.min(33, bs.size());
 207           int s = bs.size();
 208           long data = bs.get(num);
 209           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 210           ret.add(new Integer(num));
 211           add(sbr, data, num);
 212       }
 213       System.out.println("inserted:");
 214       System.out.println(sbi);
 215       System.out.println("retrieved:");
 216       System.out.println(sbr);
 217       System.out.println("insertion sequence:");
 218       for (int i = 0; i < ins.size(); i++) {
 219           System.out.print(" " + ins.get(i));
 220       }
 221       System.out.println("\nretrieval sequence:");
 222       for (int i = 0; i < ret.size(); i++) {
 223           System.out.print(" " + ret.get(i));
 224       }
 225       System.out.println();
 226       check(sbi, sbr);
 227   }
 228   static void test1(String[] args) {
 229       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 230       BitStorage bs = new BitStorage(37 * iters);
 231       Random rand = new Random();
 232       Vector ins = new Vector();
 233       Vector ret = new Vector();
 234       StringBuffer sbi = new StringBuffer();
 235       StringBuffer sbr = new StringBuffer();
 236       System.out.println("==== Test #1 ====");
 237       System.out.println("inserting...");
 238       for (int i = 0; i < iters; i++) {
 239           long data = rand.nextLong();
 240           int num = rand.nextInt(37);
 241           int s = bs.size();
 242           bs.add(data, num);
 243           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 244           ins.add(new Integer(num));
 245           add(sbi, data, num);
 246           print(data, num);
 247       }
 248       System.out.println("\nretrieving...");
 249       //for (int i = 0; i < iters; i++) {
 250       while (bs.size() > 0) {
 251           int num = Math.min(rand.nextInt(37), bs.size());
 252           //int num = Math.min(33, bs.size());
 253           int s = bs.size();
 254           long data = bs.get(num);
 255           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 256           ret.add(new Integer(num));
 257           add(sbr, data, num);
 258           print(data, num);
 259       }
 260       System.out.println("\ninsertion sequence:");
 261       for (int i = 0; i < ins.size(); i++) {
 262           System.out.print(" " + ins.get(i));
 263       }
 264       System.out.println("\nretrieval sequence:");
 265       for (int i = 0; i < ret.size(); i++) {
 266           System.out.print(" " + ret.get(i));
 267       }
 268       System.out.println();
 269       check(sbi, sbr);
 270   }
 271   static void print(long data, int num) {
 272       for (int i = 0; i < num; i++) {
 273           System.out.print((data >>> i) & 0x1);
 274       }
 275   }
 276   static void add(StringBuffer sb, long data, int num) {
 277       for (int i = 0; i < num; i++) {
 278           sb.append((int) ((data >>> i) & 0x1));
 279       }
 280   }
 281   static void check(StringBuffer sb1, StringBuffer sb2) {
 282       int len = sb2.length();
 283       if (len > sb1.length()) {
 284           System.out.println("error: retrieval sequence is longer than insertion sequence");
 285           len = sb1.length();
 286       }
 287       for (int i = 0; i < sb2.length(); i++) {
 288           if (sb1.charAt(i) != sb2.charAt(i)) {
 289               System.out.println("error: bit at position " + i + " does not match");
 290           }
 291       }
 292   }
 293 }
 294
 295 // Run BitStorage tests
 296 public static void main(String[] args) {
 297     BitStorage.test1(args);
 298     BitStorage.test2(args);
 299     BitStorage.test3(args);
 300 }
 301
 302 // Ship implementation
 303 private Packet selector;
 304 private static final int MAXBITS = 128;
 305 private static final int WORDSIZE = 37;
 306 private BitStorage bits = new BitStorage(MAXBITS);
 307
 308 public void service() {
 309   if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
 310   if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
 311     long data = box_inEnqueue.removeDataForShip();
 312     bits.add(data, WORDSIZE);
 313   }
 314   if (selector == null && !box_inEnqueueOp.dataReadyForShip()) return;
 315   if (selector == null) selector = box_inEnqueueOp.removePacketForShip();
 316
 317   String port = selector.destination.getDestinationName();
 318   long val = selector.value; // check if <= 37?
 319
 320   if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
 321     val = 37 - val;
 322   }
 323   if (val < bits.size()) {
 324     return;
 325   }
 326
 327   if (port.startsWith("take")) {
 328     if (!box_outDequeue.readyForDataFromShip()) return;
 329     long data = bits.get((int) val);
 330     if (port.endsWith("FillOnes")) {
 331       data |= (-1L << val);
 332     } else if (port.endsWith("SignExtend")) {
 333       data = (data << (64 - val)) >> (64 - val);
 334     }
 335     box_outDequeue.addDataFromShip(data);
 336     selector = null;
 337     return;
 338   } else {
 339     bits.get((int) val);
 340     selector = null;
 341     return;
 342   }
 343 }
 344
 345 == FleetSim ==============================================================
 346
 347 == FPGA ==============================================================
 348
 349 == Contributors =========================================================
 350 Amir Kamil <kamil@cs.berkeley.edu>