ships/BitFifo.ship

   1 ship: BitFifo
   2
   3 == Ports ===========================================================
   4 data  in:   in
   5
   6 data  in:   cmd.drop
   7 data  in:   cmd.dropInv
   8 data  in:   cmd.takeFillZeros
   9 data  in:   cmd.takeInvFillZeros
  10 data  in:   cmd.takeFillOnes
  11 data  in:   cmd.takeInvFillOnes
  12 data  in:   cmd.takeSignExtend
  13 data  in:   cmd.takeInvSignExtend
  14
  15 data  out:  out
  16
  17 == Constants ========================================================
  18
  19 == TeX ==============================================================
  20
  21 +------+   +--------------+   +-------+
  22 |inData|---|              |---|outData|
  23 +------+   |              |   +-------+
  24            |              |
  25 +------+   |              |   +-------+
  26 | inOp |---|              |---| outOp |
  27 +------+   +--------------+   +-------+
  28
  29 inOp
  30 +---+
  31 |   |  -- reverse before enqueue
  32 +---+
  33 |   |  -- count := (37-offset-count)
  34 +---+
  35 |   |  -- count (6 bits)
  36 |   |
  37 |   |
  38 |   |
  39 |   |
  40 +---+
  41 |   |  -- offset (6 bits)
  42 |   |
  43 |   |
  44 |   |
  45 |   |
  46 +---+
  47
  48 outOp
  49 +---+
  50 |   |  -- shift until you see a "Z" (2 bits)
  51 +---+
  52 |   |  -- sort the digits
  53 +---+
  54 |   |  -- give me the count
  55 +---+
  56 |   |  -- reverse after dequeue
  57 +---+
  58 |   |  -- count := 37-off-count
  59 +---+
  60 |   |  -- reset the counter before operation
  61 +---+
  62 |   |  -- fill left with (1,0,sign)  (2 bits)
  63 +---+
  64 |   |  -- fill right with (1,0,sign)  (2 bits)
  65 +---+
  66 |   |  -- count (6 bits)
  67 |   |
  68 |   |
  69 |   |
  70 |   |
  71 +---+
  72 |   |  -- offset (6 bits)
  73 |   |
  74 |   |
  75 |   |
  76 |   |
  77 +---+
  78
  79
  80 == Fleeterpreter ====================================================
  81 // Internal storage
  82 private static class BitStorage {
  83   long[] bits;
  84   int numbits = 0;
  85   int start = 0;
  86   BitStorage(int size) {
  87     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  88   }
  89   int size() {
  90     return numbits;
  91   }
  92   boolean hasSpace(int num) {
  93     return bits.length * 64 - numbits >= num;
  94   }
  95   boolean add(long data, int num) {
  96     if (!hasSpace(num)) return false;
  97     int entry = ((numbits + start) / 64) % bits.length;
  98     int off = (numbits + start) % 64;
  99     int maxadd = 64 - off;
 100     bits[entry] = (bits[entry] & (-1L >>> maxadd)) | (data << off);
 101     if (num > maxadd) {
 102       numbits += maxadd;
 103       return add(data >>> maxadd, num - maxadd);
 104     } else {
 105       numbits += num;
 106       return true;
 107     }
 108   }
 109   long get(int num) {
 110     assert size() >= num : "too few bits in storage";
 111     int entry = start / 64;
 112     int off = start % 64;
 113     int max = 64 - off;
 114     int n = num > max ? max : num;
 115     long res = (bits[entry] >>> off) & (-1L >>> (64 - n));
 116     int oldstart = start;
 117     if (n < num) {
 118       int n2 = num - n;
 119       res |= (bits[(entry + 1) % bits.length] & (-1L >>> (64 - n2))) << n;
 120     }
 121     start = (start + num) % (64 * bits.length);
 122     numbits -= num;
 123     return res;
 124   }
 125   int capacity() {
 126     return 64 * bits.length;
 127   }
 128   // Test code for BitStorage
 129   static void test2(String[] args) {
 130       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 131       BitStorage bs = new BitStorage(37 * iters);
 132       Random rand = new Random();
 133       Vector ins = new Vector();
 134       Vector ret = new Vector();
 135       StringBuffer sbi = new StringBuffer();
 136       StringBuffer sbr = new StringBuffer();
 137       System.out.println("==== Test #2 ====");
 138       for (int i = 0; i < iters; i++) {
 139           long data = rand.nextLong();
 140           int num = rand.nextInt(37);
 141           int s = bs.size();
 142           bs.add(data, num);
 143           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 144           ins.add(new Integer(num));
 145           add(sbi, data, num);
 146           num = rand.nextInt(Math.min(37, bs.size()));
 147           s = bs.size();
 148           data = bs.get(num);
 149           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 150           ret.add(new Integer(num));
 151           add(sbr, data, num);
 152       }
 153       //for (int i = 0; i < iters; i++) {
 154       while (bs.size() > 0) {
 155           int num = Math.min(rand.nextInt(37), bs.size());
 156           //int num = Math.min(33, bs.size());
 157           int s = bs.size();
 158           long data = bs.get(num);
 159           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 160           ret.add(new Integer(num));
 161           add(sbr, data, num);
 162       }
 163       System.out.println("inserted:");
 164       System.out.println(sbi);
 165       System.out.println("retrieved:");
 166       System.out.println(sbr);
 167       System.out.println("insertion sequence:");
 168       for (int i = 0; i < ins.size(); i++) {
 169           System.out.print(" " + ins.get(i));
 170       }
 171       System.out.println("\nretrieval sequence:");
 172       for (int i = 0; i < ret.size(); i++) {
 173           System.out.print(" " + ret.get(i));
 174       }
 175       System.out.println();
 176       check(sbi, sbr);
 177   }
 178   static void test1(String[] args) {
 179       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 180       BitStorage bs = new BitStorage(37 * iters);
 181       Random rand = new Random();
 182       Vector ins = new Vector();
 183       Vector ret = new Vector();
 184       StringBuffer sbi = new StringBuffer();
 185       StringBuffer sbr = new StringBuffer();
 186       System.out.println("==== Test #1 ====");
 187       System.out.println("inserting...");
 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           print(data, num);
 197       }
 198       System.out.println("\nretrieving...");
 199       //for (int i = 0; i < iters; i++) {
 200       while (bs.size() > 0) {
 201           int num = Math.min(rand.nextInt(37), bs.size());
 202           //int num = Math.min(33, bs.size());
 203           int s = bs.size();
 204           long data = bs.get(num);
 205           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 206           ret.add(new Integer(num));
 207           add(sbr, data, num);
 208           print(data, num);
 209       }
 210       System.out.println("\ninsertion sequence:");
 211       for (int i = 0; i < ins.size(); i++) {
 212           System.out.print(" " + ins.get(i));
 213       }
 214       System.out.println("\nretrieval sequence:");
 215       for (int i = 0; i < ret.size(); i++) {
 216           System.out.print(" " + ret.get(i));
 217       }
 218       System.out.println();
 219       check(sbi, sbr);
 220   }
 221   static void print(long data, int num) {
 222       for (int i = 0; i < num; i++) {
 223           System.out.print((data >>> i) & 0x1);
 224       }
 225   }
 226   static void add(StringBuffer sb, long data, int num) {
 227       for (int i = 0; i < num; i++) {
 228           sb.append((int) ((data >>> i) & 0x1));
 229       }
 230   }
 231   static void check(StringBuffer sb1, StringBuffer sb2) {
 232       int len = sb2.length();
 233       if (len > sb1.length()) {
 234           System.out.println("error: retrieval sequence is longer than insertion sequence");
 235           len = sb1.length();
 236       }
 237       for (int i = 0; i < sb2.length(); i++) {
 238           if (sb1.charAt(i) != sb2.charAt(i)) {
 239               System.out.println("error: bit at position " + i + " does not match");
 240           }
 241       }
 242   }
 243 }
 244
 245 // Run BitStorage tests
 246 public static void main(String[] args) {
 247     BitStorage.test1(args);
 248     BitStorage.test2(args);
 249 }
 250
 251 // Ship implementation
 252 private Packet selector;
 253 private static final int MAXBITS = 128;
 254 private static final int WORDSIZE = 37;
 255 private BitStorage bits = new BitStorage(MAXBITS);
 256
 257 public void service() {
 258   if (!box_out.readyForDataFromShip() && !box_in.dataReadyForShip()) return;
 259   if (box_in.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
 260     long data = box_in.removeDataForShip();
 261     bits.add(data, WORDSIZE);
 262   }
 263   if (selector == null && !box_cmd.dataReadyForShip()) return;
 264   if (selector == null) selector = box_cmd.removePacketForShip();
 265
 266   String port = selector.destination.getDestinationName();
 267   long val = selector.value; // check if <= 37?
 268
 269   if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
 270     val = 37 - val;
 271   }
 272   if (val < bits.size()) {
 273     return;
 274   }
 275
 276   if (port.startsWith("take")) {
 277     if (!box_out.readyForDataFromShip()) return;
 278     long data = bits.get((int) val);
 279     if (port.endsWith("FillOnes")) {
 280       data |= (-1L << val);
 281     } else if (port.endsWith("SignExtend")) {
 282       data = (data << (64 - val)) >> (64 - val);
 283     }
 284     box_out.addDataFromShip(data);
 285     selector = null;
 286     return;
 287   } else {
 288     bits.get((int) val);
 289     selector = null;
 290     return;
 291   }
 292 }
 293
 294 == FleetSim ==============================================================
 295
 296 == FPGA ==============================================================
 297
 298 == Contributors =========================================================
 299 Amir Kamil <kamil@cs.berkeley.edu>