ships/BitFifo.ship

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