ships/BitFifo.ship

   1 ship: BitFifo
   2
   3 == Ports ===========================================================
   4 in:   in
   5 in:   inOp
   6   constant lsbFirst: ....................................1
   7   constant msbFirst: ....................................0
   8   constant drop:     .............................uuuuuu..
   9   constant take:     .......................uuuuuu........
  10 out:  out
  11 in:   outOp
  12   constant lsbFirst:   ....................................1
  13   constant msbFirst:   ....................................0
  14   constant signExtend: ...................................1.
  15   constant drop:       .............................uuuuuu..
  16   constant take:       ......................0uuuuuu........
  17   constant copy:       ......................1uuuuuu........
  18
  19
  20 == TeX ==============================================================
  21
  22 The BitFifo internally stores some number of bits in a fifo structure.
  23 Its capacity is guaranteed to be at least two full machine words or
  24 more.
  25
  26 Bits are enqueued by providing a word at the {\tt in} port and a count
  27 at the {\tt inOp} port (ports are named this way to take advantage of
  28 the switch fabric opcode mechanism).  The {\tt inOp} count may be
  29 positive, negative, or zero.
  30
  31 If the {\tt inOp} count is positive, a word will be taken from the
  32 {\tt in} port and its {\tt count} least significant bits will be
  33 enqueued most-significant-bit first.
  34
  35 If the {\tt inOp} count is zero, a word will be {\it discarded} from
  36 the {\tt in} port and a duplicate copy of the bit at the {\it tail} of
  37 the fifo is enqueued.  If the fifo is empty, an undefined bit will be
  38 enqueued.  This mechanism is used for sign-extending words.
  39
  40 If the {\tt inOp} count is negative, a word will be taken from the
  41 {\tt in} port and its {\tt |count|} most significant bits will be
  42 enqueued least-significant-bit first.
  43
  44 Whenever a full word is present in the fifo, it will be made available
  45 for dequeueing at the {\tt out} port.
  46
  47 \begin{verbatim}
  48 FIXMEs
  49 - previously I noted that it would be nice to be able to dequeue bits
  50   without consuming them (ie copy-out).  What was this needed for?
  51 \end{verbatim}
  52
  53
  54 == Fleeterpreter ====================================================
  55 // Internal storage
  56 static class BitStorage {
  57   long[] bits;
  58   int numbits = 0;
  59   int start = 0;
  60   BitStorage(int size) {
  61     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  62   }
  63   int size() {
  64     return numbits;
  65   }
  66   boolean hasSpace(int num) {
  67     return bits.length * 64 - numbits >= num;
  68   }
  69   boolean peekTailBit() {
  70     int entry = (((numbits-1) + start) / 64) % bits.length;
  71     int off = ((numbits-1) + start) % 64;
  72     int maxadd = 64 - off;
  73     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
  74     return (bits[entry] & ~mask) != 0;
  75   }
  76   boolean add(long data, int num) {
  77     if (!hasSpace(num)) return false;
  78     int entry = ((numbits + start) / 64) % bits.length;
  79     int off = (numbits + start) % 64;
  80     int maxadd = 64 - off;
  81     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
  82     bits[entry] = (bits[entry] & mask) | (data << off);
  83     if (num > maxadd) {
  84       numbits += maxadd;
  85       return add(data >>> maxadd, num - maxadd);
  86     } else {
  87       numbits += num;
  88       return true;
  89     }
  90   }
  91   long get(int num) {
  92     assert size() >= num : "too few bits in storage";
  93     int entry = start / 64;
  94     int off = start % 64;
  95     int max = 64 - off;
  96     int n = num > max ? max : num;
  97     long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
  98     long res = (bits[entry] >>> off) & mask;
  99     int oldstart = start;
 100     if (n < num) {
 101       int n2 = num - n;
 102       long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
 103       res |= (bits[(entry + 1) % bits.length] & mask2) << n;
 104     }
 105     start = (start + num) % (64 * bits.length);
 106     numbits -= num;
 107     return res;
 108   }
 109   int capacity() {
 110     return 64 * bits.length;
 111   }
 112   // Test code for BitStorage
 113   static void test3(String[] args) {
 114       BitStorage bs = new BitStorage(37);
 115       Random rand = new Random();
 116       Vector ins = new Vector();
 117       Vector ret = new Vector();
 118       StringBuffer sbi = new StringBuffer();
 119       StringBuffer sbr = new StringBuffer();
 120       System.out.println("==== Test #3 ====");
 121       System.out.println("inserting...");
 122       long data = rand.nextLong();
 123       bs.add(data, 0);
 124       ins.add(new Integer(0));
 125       data = rand.nextLong();
 126       int num = rand.nextInt(37);
 127       int s = bs.size();
 128       bs.add(data, num);
 129       assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 130       ins.add(new Integer(num));
 131       add(sbi, data, num);
 132       print(data, num);
 133       System.out.println("\nretrieving...");
 134       num = bs.size();
 135       data = bs.get(num);
 136       ret.add(new Integer(num));
 137       add(sbr, data, num);
 138       print(data, num);
 139       System.out.println("\ninsertion sequence:");
 140       for (int i = 0; i < ins.size(); i++) {
 141           System.out.print(" " + ins.get(i));
 142       }
 143       System.out.println("\nretrieval sequence:");
 144       for (int i = 0; i < ret.size(); i++) {
 145           System.out.print(" " + ret.get(i));
 146       }
 147       System.out.println();
 148       check(sbi, sbr);
 149   }
 150   static void test2(String[] args) {
 151       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 152       BitStorage bs = new BitStorage(37 * iters);
 153       Random rand = new Random();
 154       Vector ins = new Vector();
 155       Vector ret = new Vector();
 156       StringBuffer sbi = new StringBuffer();
 157       StringBuffer sbr = new StringBuffer();
 158       System.out.println("==== Test #2 ====");
 159       for (int i = 0; i < iters; i++) {
 160           long data = rand.nextLong();
 161           int num = rand.nextInt(37);
 162           int s = bs.size();
 163           bs.add(data, num);
 164           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 165           ins.add(new Integer(num));
 166           add(sbi, data, num);
 167           num = rand.nextInt(Math.min(37, bs.size()));
 168           s = bs.size();
 169           data = bs.get(num);
 170           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 171           ret.add(new Integer(num));
 172           add(sbr, data, num);
 173       }
 174       //for (int i = 0; i < iters; i++) {
 175       while (bs.size() > 0) {
 176           int num = Math.min(rand.nextInt(37), bs.size());
 177           //int num = Math.min(33, bs.size());
 178           int s = bs.size();
 179           long data = bs.get(num);
 180           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 181           ret.add(new Integer(num));
 182           add(sbr, data, num);
 183       }
 184       System.out.println("inserted:");
 185       System.out.println(sbi);
 186       System.out.println("retrieved:");
 187       System.out.println(sbr);
 188       System.out.println("insertion sequence:");
 189       for (int i = 0; i < ins.size(); i++) {
 190           System.out.print(" " + ins.get(i));
 191       }
 192       System.out.println("\nretrieval sequence:");
 193       for (int i = 0; i < ret.size(); i++) {
 194           System.out.print(" " + ret.get(i));
 195       }
 196       System.out.println();
 197       check(sbi, sbr);
 198   }
 199   static void test1(String[] args) {
 200       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 201       BitStorage bs = new BitStorage(37 * iters);
 202       Random rand = new Random();
 203       Vector ins = new Vector();
 204       Vector ret = new Vector();
 205       StringBuffer sbi = new StringBuffer();
 206       StringBuffer sbr = new StringBuffer();
 207       System.out.println("==== Test #1 ====");
 208       System.out.println("inserting...");
 209       for (int i = 0; i < iters; i++) {
 210           long data = rand.nextLong();
 211           int num = rand.nextInt(37);
 212           int s = bs.size();
 213           bs.add(data, num);
 214           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 215           ins.add(new Integer(num));
 216           add(sbi, data, num);
 217           print(data, num);
 218       }
 219       System.out.println("\nretrieving...");
 220       //for (int i = 0; i < iters; i++) {
 221       while (bs.size() > 0) {
 222           int num = Math.min(rand.nextInt(37), bs.size());
 223           //int num = Math.min(33, bs.size());
 224           int s = bs.size();
 225           long data = bs.get(num);
 226           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 227           ret.add(new Integer(num));
 228           add(sbr, data, num);
 229           print(data, num);
 230       }
 231       System.out.println("\ninsertion sequence:");
 232       for (int i = 0; i < ins.size(); i++) {
 233           System.out.print(" " + ins.get(i));
 234       }
 235       System.out.println("\nretrieval sequence:");
 236       for (int i = 0; i < ret.size(); i++) {
 237           System.out.print(" " + ret.get(i));
 238       }
 239       System.out.println();
 240       check(sbi, sbr);
 241   }
 242   static void print(long data, int num) {
 243       for (int i = 0; i < num; i++) {
 244           System.out.print((data >>> i) & 0x1);
 245       }
 246   }
 247   static void add(StringBuffer sb, long data, int num) {
 248       for (int i = 0; i < num; i++) {
 249           sb.append((int) ((data >>> i) & 0x1));
 250       }
 251   }
 252   static void check(StringBuffer sb1, StringBuffer sb2) {
 253       int len = sb2.length();
 254       if (len > sb1.length()) {
 255           System.out.println("error: retrieval sequence is longer than insertion sequence");
 256           len = sb1.length();
 257       }
 258       for (int i = 0; i < sb2.length(); i++) {
 259           if (sb1.charAt(i) != sb2.charAt(i)) {
 260               System.out.println("error: bit at position " + i + " does not match");
 261           }
 262       }
 263   }
 264 }
 265
 266 // Run BitStorage tests
 267 public static void main(String[] args) {
 268     BitStorage.test1(args);
 269     BitStorage.test2(args);
 270     BitStorage.test3(args);
 271 }
 272
 273 // Ship implementation
 274 private Packet selector;
 275 private static final int MAXBITS = 128;
 276 private static final int WORDSIZE = 37;
 277 private Queue bits = new LinkedList<Boolean>();
 278 boolean last = false;
 279
 280 // dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
 281 private void add(boolean bit) {
 282   bits.add(bit);
 283   last = bit;
 284 }
 285 private boolean get() {
 286   return ((Boolean)bits.remove());
 287 }
 288 boolean haveBoxOutOp;
 289 long  boxOutOp;
 290 public void service() {
 291   if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
 292     long op    = box_inOp.removeDataForShip();
 293     long data  = box_in.removeDataForShip();
 294
 295     boolean rev = (op & 1) != 0;
 296     int drop    = (int)((op >> 2) & (~(0xffffffffL << 6)));
 297     int take    = (int)((op >> 8) & (~(0xffffffffL << 6)));
 298     if (take==0) { add(last); return; }
 299
 300     if (!rev)
 301       for(long i=take-1-drop; i>=0; i--)
 302         add( (data & (1L<<i)) != 0);
 303     if (rev)
 304       for(long i=WORDSIZE-take+drop; i<WORDSIZE; i++)
 305         add( (data & (1L<<i)) != 0);
 306     return;
 307   }
 308
 309   if (!haveBoxOutOp && box_outOp.dataReadyForShip()) {
 310      boxOutOp = box_outOp.removeDataForShip();
 311      haveBoxOutOp = true;
 312   }
 313
 314   if (haveBoxOutOp && box_out.readyForDataFromShip()) {
 315     long op = boxOutOp;
 316     boolean rev  = (op & 1) != 0;
 317     boolean sign = (op & 2) != 0;
 318     boolean copy = (op & (1<<8)) != 0;
 319     int drop     = (int)((op >> 2) & (~(0xffffffffL << 6)));
 320     int take     = (int)((op >> 8) & (~(0xffffffffL << 6)));
 321     if (bits.size() >= take+drop) {
 322       // FIXME: copy
 323       for(int i=0; i<drop; i++) get();
 324       long ret = 0;
 325       if (!rev) {
 326         for(long i=take-1; i>=0; i--)
 327           if (get()) ret |= 1L<<i;
 328         if (sign && (ret & (1L<<(take-1)))!=0)
 329           ret |= (0xffffffffffffffffL << take);
 330       } else {
 331         for(long i=WORDSIZE-take; i<WORDSIZE; i++)
 332           if (get()) ret |= 1L<<i;
 333         // FIXME: sign-extend!
 334       }
 335       box_out.addDataFromShip(ret);
 336       haveBoxOutOp = false;
 337     }
 338   }
 339 }
 340
 341
 342 == FPGA ==============================================================
 343   reg [73:0] bitstorage;
 344   reg [7:0] bitstorage_count;          initial bitstorage_count = 0;
 345
 346   always @(posedge clk) begin
 347     if (bitstorage_count == 0) begin
 348       `onread(in_r, in_a)
 349         bitstorage       <= in_d;
 350         bitstorage_count <= 37;
 351         out_d            <= (in_d[0] ? 37'b1111111111111111111111111111111111111 : 0);
 352       end
 353     end else begin
 354       `onwrite(out_r, out_a)
 355         bitstorage_count <= bitstorage_count - 1;
 356         out_d            <= (bitstorage[1] ? 37'b1111111111111111111111111111111111111 : 0);
 357         bitstorage       <= bitstorage >> 1;
 358       end
 359     end
 360   end
 361
 362
 363 == Test ==============================================================
 364
 365 // expected output
 366 #expect 1
 367 #expect 68719476736
 368 #expect 12
 369 #expect 13
 370
 371 // ships required in order to run this code
 372 #ship debug        : Debug
 373 #ship bitfifo      : BitFifo
 374
 375 BitFifo.outOp[take=37]: sendto bitfifo.outOp;
 376 bitfifo.outOp:          take; [*] deliver;
 377
 378 // FIXME: test the drop capability
 379
 380 // enqueue
 381 1:                      sendto bitfifo.in;
 382 BitFifo.inOp[take=37]:  sendto bitfifo.inOp;
 383
 384 // enqueue reversed
 385 1:                          sendto bitfifo.in;
 386 BitFifo.inOp[take=37,lsbFirst]: sendto bitfifo.inOp;
 387
 388 // test copy-last-bit
 389 0:                      sendto bitfifo.in;
 390 BitFifo.inOp[take=33]: sendto bitfifo.inOp;
 391 1:                      sendto bitfifo.in;
 392 BitFifo.inOp[take=1]: sendto bitfifo.inOp;
 393 1:                      sendto bitfifo.in;
 394 BitFifo.inOp[take=0]: sendto bitfifo.inOp;
 395 0:                      sendto bitfifo.in;
 396 BitFifo.inOp[take=1]: sendto bitfifo.inOp;
 397 1:                      sendto bitfifo.in;
 398 BitFifo.inOp[take=0]: sendto bitfifo.inOp;
 399
 400 // ordering
 401 0:                      sendto bitfifo.in;
 402 BitFifo.inOp[take=33]: sendto bitfifo.inOp;
 403 13:                     sendto bitfifo.in;
 404 BitFifo.inOp[take=4]: sendto bitfifo.inOp;
 405
 406 bitfifo.in:         [*] take, deliver;
 407 bitfifo.inOp:       [*] take, deliver;
 408 bitfifo.out:        [*] take, sendto debug.in;
 409 debug.in:           [*] take, deliver;
 410
 411
 412 == Contributors =========================================================
 413 Amir Kamil <kamil@cs.berkeley.edu>
 414 Adam Megacz <megacz@cs.berkeley.edu>