ships/BitFifo.ship

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