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 == Sample Code ======================================================
  15
  16
  17 == Constants ========================================================
  18
  19 == TeX ==============================================================
  20
  21 \begin{verbatim}
  22 +-------------+   +---------------+   +------------+
  23 | inEnqueue   |-->|               |-->| outDequeue |
  24 +-------------+   |               |   +------------+
  25                   |    BitFifo    |
  26 +-------------+   |               |   +-------------+
  27 | inEnqueueOp |-->|               |<--| inDequeueOp |
  28 +-------------+   +---------------+   +-------------+
  29 \end{verbatim}
  30
  31 \section*{inEnqueueOp}
  32 \setlength{\bitwidth}{6mm}
  33 {\tt\footnotesize
  34 \begin{bytefield}{14}
  35   \bitheader[b]{0,5,6,11,12,13}\\
  36   \bitbox{1}{Rev}
  37   \bitbox{1}{Inv}
  38   \bitbox{6}{Count}
  39   \bitbox{6}{Offset}
  40 \end{bytefield}
  41 }
  42
  43 \begin{itemize}
  44    \item [\tt Rev]    ({\bf Reverse Before Enqueue})
  45    \item [\tt Inv]    ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
  46    \item [\tt Count]  ({\bf Count of Bits To Enqueue})
  47    \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
  48 \end{itemize}
  49
  50 By default, bits are enqueued {\it most significant bit first} (bits
  51 in Sun byte order).  If {\tt Rev=1}, the bits are reversed before
  52 performing the directions below.
  53
  54 If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
  55 was actually {\tt 37-Offset-Count} for all directions below.
  56
  57
  58
  59 \pagebreak
  60
  61 \section*{inDequeueOp}
  62 \setlength{\bitwidth}{6mm}
  63 {\tt\scriptsize
  64 \begin{bytefield}{23}
  65   \bitheader[b]{0,5,6,11-21,22}\\
  66   \bitbox{2}{Until}
  67   \bitbox{1}{Sort}
  68   \bitbox{1}{Get}
  69   \bitbox{1}{Rev}
  70   \bitbox{1}{Inv}
  71   \bitbox{1}{Rst}
  72   \bitbox{2}{Left\\ Fill}
  73   \bitbox{2}{Right\\ Fill}
  74   \bitbox{6}{Count}
  75   \bitbox{6}{Offset}
  76 \end{bytefield}
  77 }
  78
  79 \begin{itemize}
  80    \item [\tt Until]       ({\bf Shift until you see a (0, 1)})
  81    \item [\tt Sort]        ({\bf Sort the Bits})
  82    \item [\tt Get]         ({\bf Get the value of the counter})
  83    \item [\tt Rev]         ({\bf Reverse Before Enqueue})
  84    \item [\tt Inv]         ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
  85    \item [\tt Rst]         ({\bf Reset Counter Before Operation})
  86    \item [\tt Left Fill]   ({\bf Left Fill (0, 1, sign)})
  87    \item [\tt Right Fill]  ({\bf Right Fill (0, 1, sign)})
  88    \item [\tt Count]       ({\bf Count of Bits To Dequeue})
  89    \item [\tt Offset]      ({\bf Offset of Bits To Dequeue})
  90 \end{itemize}
  91
  92
  93 == Fleeterpreter ====================================================
  94 // Internal storage
  95 static class BitStorage {
  96   long[] bits;
  97   int numbits = 0;
  98   int start = 0;
  99   BitStorage(int size) {
 100     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
 101   }
 102   int size() {
 103     return numbits;
 104   }
 105   boolean hasSpace(int num) {
 106     return bits.length * 64 - numbits >= num;
 107   }
 108   boolean add(long data, int num) {
 109     if (!hasSpace(num)) return false;
 110     int entry = ((numbits + start) / 64) % bits.length;
 111     int off = (numbits + start) % 64;
 112     int maxadd = 64 - off;
 113     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
 114     bits[entry] = (bits[entry] & mask) | (data << off);
 115     if (num > maxadd) {
 116       numbits += maxadd;
 117       return add(data >>> maxadd, num - maxadd);
 118     } else {
 119       numbits += num;
 120       return true;
 121     }
 122   }
 123   long get(int num) {
 124     assert size() >= num : "too few bits in storage";
 125     int entry = start / 64;
 126     int off = start % 64;
 127     int max = 64 - off;
 128     int n = num > max ? max : num;
 129     long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
 130     long res = (bits[entry] >>> off) & mask;
 131     int oldstart = start;
 132     if (n < num) {
 133       int n2 = num - n;
 134       long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
 135       res |= (bits[(entry + 1) % bits.length] & mask2) << n;
 136     }
 137     start = (start + num) % (64 * bits.length);
 138     numbits -= num;
 139     return res;
 140   }
 141   int capacity() {
 142     return 64 * bits.length;
 143   }
 144   // Test code for BitStorage
 145   static void test3(String[] args) {
 146       BitStorage bs = new BitStorage(37);
 147       Random rand = new Random();
 148       Vector ins = new Vector();
 149       Vector ret = new Vector();
 150       StringBuffer sbi = new StringBuffer();
 151       StringBuffer sbr = new StringBuffer();
 152       System.out.println("==== Test #3 ====");
 153       System.out.println("inserting...");
 154       long data = rand.nextLong();
 155       bs.add(data, 0);
 156       ins.add(new Integer(0));
 157       data = rand.nextLong();
 158       int num = rand.nextInt(37);
 159       int s = bs.size();
 160       bs.add(data, num);
 161       assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 162       ins.add(new Integer(num));
 163       add(sbi, data, num);
 164       print(data, num);
 165       System.out.println("\nretrieving...");
 166       num = bs.size();
 167       data = bs.get(num);
 168       ret.add(new Integer(num));
 169       add(sbr, data, num);
 170       print(data, num);
 171       System.out.println("\ninsertion sequence:");
 172       for (int i = 0; i < ins.size(); i++) {
 173           System.out.print(" " + ins.get(i));
 174       }
 175       System.out.println("\nretrieval sequence:");
 176       for (int i = 0; i < ret.size(); i++) {
 177           System.out.print(" " + ret.get(i));
 178       }
 179       System.out.println();
 180       check(sbi, sbr);
 181   }
 182   static void test2(String[] args) {
 183       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 184       BitStorage bs = new BitStorage(37 * iters);
 185       Random rand = new Random();
 186       Vector ins = new Vector();
 187       Vector ret = new Vector();
 188       StringBuffer sbi = new StringBuffer();
 189       StringBuffer sbr = new StringBuffer();
 190       System.out.println("==== Test #2 ====");
 191       for (int i = 0; i < iters; i++) {
 192           long data = rand.nextLong();
 193           int num = rand.nextInt(37);
 194           int s = bs.size();
 195           bs.add(data, num);
 196           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 197           ins.add(new Integer(num));
 198           add(sbi, data, num);
 199           num = rand.nextInt(Math.min(37, bs.size()));
 200           s = bs.size();
 201           data = bs.get(num);
 202           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 203           ret.add(new Integer(num));
 204           add(sbr, data, num);
 205       }
 206       //for (int i = 0; i < iters; i++) {
 207       while (bs.size() > 0) {
 208           int num = Math.min(rand.nextInt(37), bs.size());
 209           //int num = Math.min(33, bs.size());
 210           int s = bs.size();
 211           long data = bs.get(num);
 212           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 213           ret.add(new Integer(num));
 214           add(sbr, data, num);
 215       }
 216       System.out.println("inserted:");
 217       System.out.println(sbi);
 218       System.out.println("retrieved:");
 219       System.out.println(sbr);
 220       System.out.println("insertion sequence:");
 221       for (int i = 0; i < ins.size(); i++) {
 222           System.out.print(" " + ins.get(i));
 223       }
 224       System.out.println("\nretrieval sequence:");
 225       for (int i = 0; i < ret.size(); i++) {
 226           System.out.print(" " + ret.get(i));
 227       }
 228       System.out.println();
 229       check(sbi, sbr);
 230   }
 231   static void test1(String[] args) {
 232       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 233       BitStorage bs = new BitStorage(37 * iters);
 234       Random rand = new Random();
 235       Vector ins = new Vector();
 236       Vector ret = new Vector();
 237       StringBuffer sbi = new StringBuffer();
 238       StringBuffer sbr = new StringBuffer();
 239       System.out.println("==== Test #1 ====");
 240       System.out.println("inserting...");
 241       for (int i = 0; i < iters; i++) {
 242           long data = rand.nextLong();
 243           int num = rand.nextInt(37);
 244           int s = bs.size();
 245           bs.add(data, num);
 246           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 247           ins.add(new Integer(num));
 248           add(sbi, data, num);
 249           print(data, num);
 250       }
 251       System.out.println("\nretrieving...");
 252       //for (int i = 0; i < iters; i++) {
 253       while (bs.size() > 0) {
 254           int num = Math.min(rand.nextInt(37), bs.size());
 255           //int num = Math.min(33, bs.size());
 256           int s = bs.size();
 257           long data = bs.get(num);
 258           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 259           ret.add(new Integer(num));
 260           add(sbr, data, num);
 261           print(data, num);
 262       }
 263       System.out.println("\ninsertion sequence:");
 264       for (int i = 0; i < ins.size(); i++) {
 265           System.out.print(" " + ins.get(i));
 266       }
 267       System.out.println("\nretrieval sequence:");
 268       for (int i = 0; i < ret.size(); i++) {
 269           System.out.print(" " + ret.get(i));
 270       }
 271       System.out.println();
 272       check(sbi, sbr);
 273   }
 274   static void print(long data, int num) {
 275       for (int i = 0; i < num; i++) {
 276           System.out.print((data >>> i) & 0x1);
 277       }
 278   }
 279   static void add(StringBuffer sb, long data, int num) {
 280       for (int i = 0; i < num; i++) {
 281           sb.append((int) ((data >>> i) & 0x1));
 282       }
 283   }
 284   static void check(StringBuffer sb1, StringBuffer sb2) {
 285       int len = sb2.length();
 286       if (len > sb1.length()) {
 287           System.out.println("error: retrieval sequence is longer than insertion sequence");
 288           len = sb1.length();
 289       }
 290       for (int i = 0; i < sb2.length(); i++) {
 291           if (sb1.charAt(i) != sb2.charAt(i)) {
 292               System.out.println("error: bit at position " + i + " does not match");
 293           }
 294       }
 295   }
 296 }
 297
 298 // Run BitStorage tests
 299 public static void main(String[] args) {
 300     BitStorage.test1(args);
 301     BitStorage.test2(args);
 302     BitStorage.test3(args);
 303 }
 304
 305 // Ship implementation
 306 private Packet selector;
 307 private static final int MAXBITS = 128;
 308 private static final int WORDSIZE = 37;
 309 private BitStorage bits = new BitStorage(MAXBITS);
 310
 311 // dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
 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     return;
 318   }
 319   if (box_outDequeue.readyForDataFromShip() && bits.size() > 0) {
 320     long data = bits.get(1) == 0 ? 0L : 0x1FFFFFFFFFL;
 321     box_outDequeue.addDataFromShip(data);
 322     return;
 323   }
 324 }
 325
 326 /*
 327 public void service() {
 328   if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
 329   if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
 330     long data = box_inEnqueue.removeDataForShip();
 331     bits.add(data, WORDSIZE);
 332   }
 333   if (selector == null && !box_inEnqueueOp.dataReadyForShip()) return;
 334   if (selector == null) selector = box_inEnqueueOp.removePacketForShip();
 335
 336   String port = selector.destination.getDestinationName();
 337   long val = selector.value; // check if <= 37?
 338
 339   if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
 340     val = 37 - val;
 341   }
 342   if (val < bits.size()) {
 343     return;
 344   }
 345
 346   if (port.startsWith("take")) {
 347     if (!box_outDequeue.readyForDataFromShip()) return;
 348     long data = bits.get((int) val);
 349     if (port.endsWith("FillOnes")) {
 350       data |= (-1L << val);
 351     } else if (port.endsWith("SignExtend")) {
 352       data = (data << (64 - val)) >> (64 - val);
 353     }
 354     box_outDequeue.addDataFromShip(data);
 355     selector = null;
 356     return;
 357   } else {
 358     bits.get((int) val);
 359     selector = null;
 360     return;
 361   }
 362 }
 363 */
 364
 365 == FleetSim ==============================================================
 366
 367 == FPGA ==============================================================
 368   reg [73:0] bitstorage;
 369   reg [7:0] bitstorage_count;          initial bitstorage_count = 0;
 370
 371   always @(posedge clk) begin
 372     if (bitstorage_count == 0) begin
 373       `onread(inEnqueue_r, inEnqueue_a)
 374         bitstorage       <= inEnqueue_d;
 375         bitstorage_count <= 37;
 376         outDequeue_d     <= (inEnqueue_d[0] ? 37'b1111111111111111111111111111111111111 : 0);
 377       end
 378     end else begin
 379       `onwrite(outDequeue_r, outDequeue_a)
 380         bitstorage_count <= bitstorage_count - 1;
 381         outDequeue_d     <= (bitstorage[1] ? 37'b1111111111111111111111111111111111111 : 0);
 382         bitstorage       <= bitstorage >> 1;
 383       end
 384     end
 385   end
 386
 387
 388 == Test ==============================================================
 389
 390 // expected output
 391 #expect 137438953471
 392 #expect 137438953471
 393 #expect 0
 394 #expect 0
 395 #expect 0
 396 #expect 137438953471
 397 #expect 137438953471
 398 #expect 0
 399 #expect 0
 400 #expect 0
 401 #expect 0
 402 #expect 0
 403 #expect 0
 404 #expect 0
 405 #expect 0
 406 #expect 0
 407 #expect 0
 408 #expect 0
 409 #expect 0
 410 #expect 0
 411 #expect 0
 412 #expect 0
 413 #expect 0
 414 #expect 0
 415 #expect 0
 416 #expect 0
 417 #expect 0
 418 #expect 0
 419 #expect 0
 420 #expect 0
 421 #expect 0
 422 #expect 0
 423 #expect 0
 424 #expect 0
 425 #expect 0
 426 #expect 0
 427 #expect 0
 428
 429 // ships required in order to run this code
 430 #ship debug        : Debug
 431 #ship bitfifo      : BitFifo
 432
 433 debug.in:           [*] take, deliver;
 434 99:                 sendto bitfifo.inEnqueue;
 435 bitfifo.inEnqueue:  take, deliver;
 436 bitfifo.outDequeue: [*] take, sendto debug.in;
 437
 438 == Contributors =========================================================
 439 Amir Kamil <kamil@cs.berkeley.edu>
 440 Adam Megacz <megacz@cs.berkeley.edu>