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 == Fleeterpreter ====================================================
  22 // Internal storage
  23 private static class BitStorage {
  24   long[] bits;
  25   int numbits = 0;
  26   int start = 0;
  27   BitStorage(int size) {
  28     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
  29   }
  30   int size() {
  31     return numbits;
  32   }
  33   boolean hasSpace(int num) {
  34     return bits.length * 64 - numbits >= num;
  35   }
  36   boolean add(long data, int num) {
  37     if (!hasSpace(num)) return false;
  38     int entry = ((numbits + start) / 64) % bits.length;
  39     int off = (numbits + start) % 64;
  40     int maxadd = 64 - off;
  41     bits[entry] = (bits[entry] & (-1L >>> maxadd)) | (data << off);
  42     if (num > maxadd) {
  43       numbits += maxadd;
  44       return add(data >>> maxadd, num - maxadd);
  45     } else {
  46       numbits += num;
  47       return true;
  48     }
  49   }
  50   long get(int num) {
  51     assert size() >= num : "too few bits in storage";
  52     int entry = start / 64;
  53     int off = start % 64;
  54     int max = 64 - off;
  55     int n = num > max ? max : num;
  56     long res = (bits[entry] >>> off) & (-1L >>> (64 - n));
  57     int oldstart = start;
  58     if (n < num) {
  59       int n2 = num - n;
  60       res |= (bits[(entry + 1) % bits.length] & (-1L >>> (64 - n2))) << n;
  61     }
  62     start = (start + num) % (64 * bits.length);
  63     numbits -= num;
  64     return res;
  65   }
  66   int capacity() {
  67     return 64 * bits.length;
  68   }
  69   // Test code for BitStorage
  70   static void test2(String[] args) {
  71       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
  72       BitStorage bs = new BitStorage(37 * iters);
  73       Random rand = new Random();
  74       Vector ins = new Vector();
  75       Vector ret = new Vector();
  76       StringBuffer sbi = new StringBuffer();
  77       StringBuffer sbr = new StringBuffer();
  78       System.out.println("==== Test #2 ====");
  79       for (int i = 0; i < iters; i++) {
  80           long data = rand.nextLong();
  81           int num = rand.nextInt(37);
  82           int s = bs.size();
  83           bs.add(data, num);
  84           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
  85           ins.add(new Integer(num));
  86           add(sbi, data, num);
  87           num = rand.nextInt(Math.min(37, bs.size()));
  88           s = bs.size();
  89           data = bs.get(num);
  90           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
  91           ret.add(new Integer(num));
  92           add(sbr, data, num);
  93       }
  94       //for (int i = 0; i < iters; i++) {
  95       while (bs.size() > 0) {
  96           int num = Math.min(rand.nextInt(37), bs.size());
  97           //int num = Math.min(33, bs.size());
  98           int s = bs.size();
  99           long data = bs.get(num);
 100           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 101           ret.add(new Integer(num));
 102           add(sbr, data, num);
 103       }
 104       System.out.println("inserted:");
 105       System.out.println(sbi);
 106       System.out.println("retrieved:");
 107       System.out.println(sbr);
 108       System.out.println("insertion sequence:");
 109       for (int i = 0; i < ins.size(); i++) {
 110           System.out.print(" " + ins.get(i));
 111       }
 112       System.out.println("\nretrieval sequence:");
 113       for (int i = 0; i < ret.size(); i++) {
 114           System.out.print(" " + ret.get(i));
 115       }
 116       System.out.println();
 117       check(sbi, sbr);
 118   }
 119   static void test1(String[] args) {
 120       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
 121       BitStorage bs = new BitStorage(37 * iters);
 122       Random rand = new Random();
 123       Vector ins = new Vector();
 124       Vector ret = new Vector();
 125       StringBuffer sbi = new StringBuffer();
 126       StringBuffer sbr = new StringBuffer();
 127       System.out.println("==== Test #1 ====");
 128       System.out.println("inserting...");
 129       for (int i = 0; i < iters; i++) {
 130           long data = rand.nextLong();
 131           int num = rand.nextInt(37);
 132           int s = bs.size();
 133           bs.add(data, num);
 134           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
 135           ins.add(new Integer(num));
 136           add(sbi, data, num);
 137           print(data, num);
 138       }
 139       System.out.println("\nretrieving...");
 140       //for (int i = 0; i < iters; i++) {
 141       while (bs.size() > 0) {
 142           int num = Math.min(rand.nextInt(37), bs.size());
 143           //int num = Math.min(33, bs.size());
 144           int s = bs.size();
 145           long data = bs.get(num);
 146           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
 147           ret.add(new Integer(num));
 148           add(sbr, data, num);
 149           print(data, num);
 150       }
 151       System.out.println("\ninsertion sequence:");
 152       for (int i = 0; i < ins.size(); i++) {
 153           System.out.print(" " + ins.get(i));
 154       }
 155       System.out.println("\nretrieval sequence:");
 156       for (int i = 0; i < ret.size(); i++) {
 157           System.out.print(" " + ret.get(i));
 158       }
 159       System.out.println();
 160       check(sbi, sbr);
 161   }
 162   static void print(long data, int num) {
 163       for (int i = 0; i < num; i++) {
 164           System.out.print((data >>> i) & 0x1);
 165       }
 166   }
 167   static void add(StringBuffer sb, long data, int num) {
 168       for (int i = 0; i < num; i++) {
 169           sb.append((int) ((data >>> i) & 0x1));
 170       }
 171   }
 172   static void check(StringBuffer sb1, StringBuffer sb2) {
 173       int len = sb2.length();
 174       if (len > sb1.length()) {
 175           System.out.println("error: retrieval sequence is longer than insertion sequence");
 176           len = sb1.length();
 177       }
 178       for (int i = 0; i < sb2.length(); i++) {
 179           if (sb1.charAt(i) != sb2.charAt(i)) {
 180               System.out.println("error: bit at position " + i + " does not match");
 181           }
 182       }
 183   }
 184 }
 185
 186 // Run BitStorage tests
 187 public static void main(String[] args) {
 188     BitStorage.test1(args);
 189     BitStorage.test2(args);
 190 }
 191
 192 // Ship implementation
 193 private Packet selector;
 194 private static final int MAXBITS = 128;
 195 private static final int WORDSIZE = 37;
 196 private BitStorage bits = new BitStorage(MAXBITS);
 197
 198 public void service() {
 199   if (!box_out.readyForDataFromShip() && !box_in.dataReadyForShip()) return;
 200   if (box_in.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
 201     long data = box_in.removeDataForShip();
 202     bits.add(data, WORDSIZE);
 203   }
 204   if (selector == null && !box_cmd.dataReadyForShip()) return;
 205   if (selector == null) selector = box_cmd.removePacketForShip();
 206
 207   String port = selector.destination.getDestinationName();
 208   long val = selector.value; // check if <= 37?
 209
 210   if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
 211     val = 37 - val;
 212   }
 213   if (val < bits.size()) {
 214     return;
 215   }
 216
 217   if (port.startsWith("take")) {
 218     if (!box_out.readyForDataFromShip()) return;
 219     long data = bits.get((int) val);
 220     if (port.endsWith("FillOnes")) {
 221       data |= (-1L << val);
 222     } else if (port.endsWith("SignExtend")) {
 223       data = (data << (64 - val)) >> (64 - val);
 224     }
 225     box_out.addDataFromShip(data);
 226     selector = null;
 227     return;
 228   } else {
 229     bits.get((int) val);
 230     selector = null;
 231     return;
 232   }
 233 }
 234
 235 == FleetSim ==============================================================
 236
 237 == FPGA ==============================================================
 238
 239 == Contributors =========================================================
 240 Amir Kamil <kamil@cs.berkeley.edu>