bitfifo notes
[fleet.git] / 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>