update tests
[fleet.git] / 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
11 out:  out
12 in:   outOp
13   constant lsbFirst:   ....................................1
14   constant msbFirst:   ....................................0
15   constant signExtend: ...................................1.
16   constant drop:       .............................uuuuuu..
17   constant take:       ......................0uuuuuu........
18   constant copy:       ......................1uuuuuu........
19
20   
21 == TeX ==============================================================
22
23 The BitFifo internally stores some number of bits in a fifo structure.
24 Its capacity is guaranteed to be at least two full machine words or
25 more.
26
27 \subsection*{Enqueueing}
28
29 Bits are enqueued by providing a word at the {\tt in} port and a code
30 word at the {\tt inOp} port (ports are named this way to take
31 advantage of the switch fabric opcode mechanism \cite{am25}).  As
32 shown in the constant diagram, this code word has fields {\tt
33 lsbFirst}, {\tt msbFirst}, {\tt drop}, and {\tt take}.
34
35 When a word is consumed from {\tt in}, it is ``oriented'' in either
36 Most Significant Bit First ({\tt msbFirst}) or Least Significant Bit
37 First ({\tt lsbFirst}) depending on whether or not these flags are
38 set.  Based on this orientation, the first {\tt drop} bits are
39 discarded.  Then the next {\tt take} bits are enqueued into the fifo.
40 Any remaining bits are discarded.  Attempting to drop or take beyond
41 the end of a word produces undefined results.
42
43 \subsection*{Dequeueing}
44
45 Bits are dequeued by providing a code word at the {\tt outOp} port
46 (despite its name, this is actually an {\it input port}).  As shown in
47 the constant diagram, this code word has fields {\tt lsbFirst}, {\tt
48 msbFirst}, {\tt signExtend}, {\tt drop}, {\tt take}, and {\tt copy}
49 fields.
50
51 Before additional processing, {\tt drop} bits are discarded from the
52 head of the fifo.  Next, bits are dequeued into an empty word-width
53 register.  If the {\tt msbFirst} flag is set, bits will be deposited
54 into this register starting with the most significant bit of the
55 register and working towards the least significant bit.  If the {\tt
56 lsbFirst} flag is set, bits will be deposited into this register
57 starting with the {\it least} significant bit of the register and
58 working towards the {\it most} significant bit.  The number of bits
59 dequeued is specified by the {\tt take} field.  If the {\tt copy}
60 field is specified instead, the bits will be {\it copied} out of the
61 fifo rather than being removed.
62
63 Finally, if the {\tt signExtend} bit is set, all bits in the register
64 which were not filled by bits dequeued from the fifo will be filled
65 with a copy of {\it the last bit dequeued from the fifo}.
66
67 As a final addendum to the above, whenever a request arrives at {\tt
68 outOp} which requires more bits than are available in the fifo, the
69 operation will wait until enough bits are present.
70
71 \subsection*{To Do}
72
73 The text above regarding sign extending and dequeueing
74 msbFirst/lsbFirst is wrong.
75
76
77 == Fleeterpreter ====================================================
78 // Internal storage
79 static class BitStorage {
80   long[] bits;
81   int numbits = 0;
82   int start = 0;
83   BitStorage(int size) {
84     bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
85   }
86   int size() {
87     return numbits;
88   }
89   boolean hasSpace(int num) {
90     return bits.length * 64 - numbits >= num;
91   }
92   boolean peekTailBit() {
93     int entry = (((numbits-1) + start) / 64) % bits.length;
94     int off = ((numbits-1) + start) % 64;
95     int maxadd = 64 - off;
96     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
97     return (bits[entry] & ~mask) != 0;
98   }
99   boolean add(long data, int num) {
100     if (!hasSpace(num)) return false;
101     int entry = ((numbits + start) / 64) % bits.length;
102     int off = (numbits + start) % 64;
103     int maxadd = 64 - off;
104     long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
105     bits[entry] = (bits[entry] & mask) | (data << off);
106     if (num > maxadd) {
107       numbits += maxadd;
108       return add(data >>> maxadd, num - maxadd);
109     } else {
110       numbits += num;
111       return true;
112     }
113   }
114   long get(int num) {
115     assert size() >= num : "too few bits in storage";
116     int entry = start / 64;
117     int off = start % 64;
118     int max = 64 - off;
119     int n = num > max ? max : num;
120     long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
121     long res = (bits[entry] >>> off) & mask;
122     int oldstart = start;
123     if (n < num) {
124       int n2 = num - n;
125       long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
126       res |= (bits[(entry + 1) % bits.length] & mask2) << n;
127     }
128     start = (start + num) % (64 * bits.length);
129     numbits -= num;
130     return res;
131   }
132   int capacity() {
133     return 64 * bits.length;
134   }
135   // Test code for BitStorage
136   static void test3(String[] args) {
137       BitStorage bs = new BitStorage(37);
138       Random rand = new Random();
139       Vector ins = new Vector();
140       Vector ret = new Vector();
141       StringBuffer sbi = new StringBuffer();
142       StringBuffer sbr = new StringBuffer();
143       System.out.println("==== Test #3 ====");
144       System.out.println("inserting...");
145       long data = rand.nextLong();
146       bs.add(data, 0);
147       ins.add(new Integer(0));
148       data = rand.nextLong();
149       int num = rand.nextInt(37);
150       int s = bs.size();
151       bs.add(data, num);
152       assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
153       ins.add(new Integer(num));
154       add(sbi, data, num);
155       print(data, num);
156       System.out.println("\nretrieving...");
157       num = bs.size();
158       data = bs.get(num);
159       ret.add(new Integer(num));
160       add(sbr, data, num);
161       print(data, num);
162       System.out.println("\ninsertion sequence:");
163       for (int i = 0; i < ins.size(); i++) {
164           System.out.print(" " + ins.get(i));
165       }
166       System.out.println("\nretrieval sequence:");
167       for (int i = 0; i < ret.size(); i++) {
168           System.out.print(" " + ret.get(i));
169       }
170       System.out.println();
171       check(sbi, sbr);
172   }
173   static void test2(String[] args) {
174       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
175       BitStorage bs = new BitStorage(37 * iters);
176       Random rand = new Random();
177       Vector ins = new Vector();
178       Vector ret = new Vector();
179       StringBuffer sbi = new StringBuffer();
180       StringBuffer sbr = new StringBuffer();
181       System.out.println("==== Test #2 ====");
182       for (int i = 0; i < iters; i++) {
183           long data = rand.nextLong();
184           int num = rand.nextInt(37);
185           int s = bs.size();
186           bs.add(data, num);
187           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
188           ins.add(new Integer(num));
189           add(sbi, data, num);
190           num = rand.nextInt(Math.min(37, bs.size()));
191           s = bs.size();
192           data = bs.get(num);
193           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
194           ret.add(new Integer(num));
195           add(sbr, data, num);
196       }
197       //for (int i = 0; i < iters; i++) {
198       while (bs.size() > 0) {
199           int num = Math.min(rand.nextInt(37), bs.size());
200           //int num = Math.min(33, bs.size());
201           int s = bs.size();
202           long data = bs.get(num);
203           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
204           ret.add(new Integer(num));
205           add(sbr, data, num);
206       }
207       System.out.println("inserted:");
208       System.out.println(sbi);
209       System.out.println("retrieved:");
210       System.out.println(sbr);
211       System.out.println("insertion sequence:");
212       for (int i = 0; i < ins.size(); i++) {
213           System.out.print(" " + ins.get(i));
214       }
215       System.out.println("\nretrieval sequence:");
216       for (int i = 0; i < ret.size(); i++) {
217           System.out.print(" " + ret.get(i));
218       }
219       System.out.println();
220       check(sbi, sbr);
221   }
222   static void test1(String[] args) {
223       int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
224       BitStorage bs = new BitStorage(37 * iters);
225       Random rand = new Random();
226       Vector ins = new Vector();
227       Vector ret = new Vector();
228       StringBuffer sbi = new StringBuffer();
229       StringBuffer sbr = new StringBuffer();
230       System.out.println("==== Test #1 ====");
231       System.out.println("inserting...");
232       for (int i = 0; i < iters; i++) {
233           long data = rand.nextLong();
234           int num = rand.nextInt(37);
235           int s = bs.size();
236           bs.add(data, num);
237           assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
238           ins.add(new Integer(num));
239           add(sbi, data, num);
240           print(data, num);
241       }
242       System.out.println("\nretrieving...");
243       //for (int i = 0; i < iters; i++) {
244       while (bs.size() > 0) {
245           int num = Math.min(rand.nextInt(37), bs.size());
246           //int num = Math.min(33, bs.size());
247           int s = bs.size();
248           long data = bs.get(num);
249           assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
250           ret.add(new Integer(num));
251           add(sbr, data, num);
252           print(data, num);
253       }
254       System.out.println("\ninsertion sequence:");
255       for (int i = 0; i < ins.size(); i++) {
256           System.out.print(" " + ins.get(i));
257       }
258       System.out.println("\nretrieval sequence:");
259       for (int i = 0; i < ret.size(); i++) {
260           System.out.print(" " + ret.get(i));
261       }
262       System.out.println();
263       check(sbi, sbr);
264   }
265   static void print(long data, int num) {
266       for (int i = 0; i < num; i++) {
267           System.out.print((data >>> i) & 0x1);
268       }
269   }
270   static void add(StringBuffer sb, long data, int num) {
271       for (int i = 0; i < num; i++) {
272           sb.append((int) ((data >>> i) & 0x1));
273       }
274   }
275   static void check(StringBuffer sb1, StringBuffer sb2) {
276       int len = sb2.length();
277       if (len > sb1.length()) {
278           System.out.println("error: retrieval sequence is longer than insertion sequence");
279           len = sb1.length();
280       }
281       for (int i = 0; i < sb2.length(); i++) {
282           if (sb1.charAt(i) != sb2.charAt(i)) {
283               System.out.println("error: bit at position " + i + " does not match");
284           }
285       }
286   }
287 }
288
289 // Run BitStorage tests
290 public static void main(String[] args) {
291     BitStorage.test1(args);
292     BitStorage.test2(args);
293     BitStorage.test3(args);
294 }
295
296 // Ship implementation
297 private Packet selector;
298 private static final int MAXBITS = 128;
299 private static final int WORDSIZE = 37;
300 private Queue bits = new LinkedList<Boolean>();
301 boolean last = false;
302
303 // dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
304 private void add(boolean bit) {
305   bits.add(bit);
306   last = bit;
307 }
308 private boolean get() {
309   return ((Boolean)bits.remove());
310 }
311 boolean haveBoxOutOp;
312 long  boxOutOp;
313 public void service() {
314   if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
315     long op    = box_inOp.removeDataForShip();
316     long data  = box_in.removeDataForShip();
317
318     boolean rev = (op & 1) != 0;
319     int drop    = (int)((op >> 2) & (~(0xffffffffL << 6)));
320     int take    = (int)((op >> 8) & (~(0xffffffffL << 6)));
321     if (take==0) { add(last); return; }
322
323     if (!rev)
324       for(long i=take-1-drop; i>=0; i--)
325         add( (data & (1L<<i)) != 0);
326     if (rev)
327       for(long i=WORDSIZE-take+drop; i<WORDSIZE; i++)
328         add( (data & (1L<<i)) != 0);
329     return;
330   }
331
332   if (!haveBoxOutOp && box_outOp.dataReadyForShip()) {
333      boxOutOp = box_outOp.removeDataForShip();
334      haveBoxOutOp = true;
335   }
336
337   if (haveBoxOutOp && box_out.readyForDataFromShip()) {
338     long op = boxOutOp;
339     boolean rev  = (op & 1) != 0;
340     boolean sign = (op & 2) != 0;
341     boolean copy = (op & (1<<8)) != 0;
342     int drop     = (int)((op >> 2) & (~(0xffffffffL << 6)));
343     int take     = (int)((op >> 8) & (~(0xffffffffL << 6)));
344     if (bits.size() >= take+drop) {
345       // FIXME: copy
346       for(int i=0; i<drop; i++) get();
347       long ret = 0;
348       if (!rev) {
349         for(long i=take-1; i>=0; i--)
350           if (get()) ret |= 1L<<i;
351         if (sign && (ret & (1L<<(take-1)))!=0)
352           ret |= (0xffffffffffffffffL << take);
353       } else {
354         for(long i=WORDSIZE-take; i<WORDSIZE; i++)
355           if (get()) ret |= 1L<<i;
356         // FIXME: sign-extend!
357       }
358       box_out.addDataFromShip(ret);
359       haveBoxOutOp = false;
360     }
361   }
362 }
363
364
365 == FPGA ==============================================================
366 `define BITSTORAGE_SIZE 148
367 `define BITSTORAGE_BITS 16
368 `define OP_SIGNEXT 1
369 `define OP_LSBFIRST 0
370 `define OP_COUNT 13:8
371 `define OP_DROP  7:2
372   reg [(`BITSTORAGE_SIZE-1):0] bitstorage;
373   reg [(`BITSTORAGE_BITS-1):0] bitstorage_count;
374   reg [(`BITSTORAGE_BITS-1):0] dequeue_remaining;
375   reg [(`BITSTORAGE_BITS-1):0] enqueue_remaining;
376   initial dequeue_remaining = 0;
377   initial enqueue_remaining = 0;
378   initial bitstorage_count = 0;
379
380   always @(posedge clk) begin
381     if (!rst) begin
382       bitstorage_count <= 0;
383       enqueue_remaining <= 0;
384       dequeue_remaining <= 0; 
385       `reset
386     end else begin
387     if (!in_r    && in_a)     in_a    <= 0;
388     if (!inOp_r  && inOp_a)   inOp_a  <= 0;
389     if (!outOp_r && outOp_a)  outOp_a <= 0;
390
391     if (out_r    && out_a)    out_r   <= 0;
392
393     if (dequeue_remaining > 0) begin
394       if (dequeue_remaining <= outOp_d[`OP_COUNT])
395       begin
396         if (outOp_d[`OP_LSBFIRST]) begin
397           out_d[`DATAWIDTH-1-(dequeue_remaining-1)] <= bitstorage[0];
398         end else begin
399           out_d[              dequeue_remaining-1 ] <= bitstorage[0];
400         end
401       end
402       bitstorage[(`BITSTORAGE_SIZE-2):0] <= bitstorage[(`BITSTORAGE_SIZE-1):1];
403       bitstorage_count  <= bitstorage_count - 1;
404       if (dequeue_remaining == 1) begin
405         out_r   <= 1;
406         outOp_a <= 1;
407       end
408       dequeue_remaining <= dequeue_remaining - 1;
409
410     end else if (enqueue_remaining > 0) begin
411       bitstorage[bitstorage_count] <=
412          inOp_d[`OP_LSBFIRST]
413          ?  in_d[`DATAWIDTH-1-(inOp_d[`OP_DROP]+enqueue_remaining-1)]
414          :  in_d[              inOp_d[`OP_DROP]+enqueue_remaining-1 ];
415       bitstorage_count  <= bitstorage_count + 1;
416       if (enqueue_remaining == 1) begin
417         in_a   <= 1;
418         inOp_a <= 1;
419       end
420       enqueue_remaining <= enqueue_remaining - 1;
421
422     end else if (in_r && !in_a && inOp_r && !inOp_a && `BITSTORAGE_SIZE > bitstorage_count + inOp_d[`OP_COUNT]) begin
423       // FIXME: zero count => lockup
424       enqueue_remaining <= inOp_d[`OP_COUNT];
425
426     end else if (!out_r && !out_a && outOp_r && !outOp_a && (bitstorage_count >= (outOp_d[`OP_COUNT]+outOp_d[`OP_DROP]))) begin
427       dequeue_remaining <= outOp_d[`OP_COUNT] + outOp_d[`OP_DROP];
428       out_d <= (outOp_d[`OP_SIGNEXT] && bitstorage[outOp_d[`OP_DROP]]) ? 37'b1111111111111111111111111111111111111 : 0;
429
430     end
431     end
432   end
433
434
435 == Test ==============================================================
436
437 // FIXME: this test case is woefully inadequate!!!!!
438
439 // expected output
440 #expect 1
441 #expect 68719476736
442 //#expect 12
443 //#expect 13
444
445 // ships required in order to run this code
446 #ship debug        : Debug
447 #ship bitfifo      : BitFifo
448
449 bitfifo.outOp:      literal BitFifo.outOp[take=37]; [*] deliver;
450 bitfifo.out:        [*] take, sendto debug.in;
451 debug.in:           [*] take, deliver;
452 bitfifo.in:         literal 1; load repeat counter with 2; deliver;
453
454 bitfifo.inOp:
455   literal BitFifo.inOp[take=37];
456   deliver;
457   literal BitFifo.inOp[take=37,lsbFirst];
458   deliver;
459
460
461 == Contributors =========================================================
462 Amir Kamil <kamil@cs.berkeley.edu>
463 Adam Megacz <megacz@cs.berkeley.edu>