3 == Ports ===========================================================
6 constant lsbFirst: ....................................1
7 constant msbFirst: ....................................0
8 constant drop: .............................uuuuuu..
9 constant take: .......................uuuuuu........
12 constant lsbFirst: ....................................1
13 constant msbFirst: ....................................0
14 constant signExtend: ...................................1.
15 constant drop: .............................uuuuuu..
16 constant take: ......................0uuuuuu........
17 constant copy: ......................1uuuuuu........
20 == TeX ==============================================================
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
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.
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.
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.
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.
44 Whenever a full word is present in the fifo, it will be made available
45 for dequeueing at the {\tt out} port.
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?
54 == Fleeterpreter ====================================================
56 static class BitStorage {
60 BitStorage(int size) {
61 bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
66 boolean hasSpace(int num) {
67 return bits.length * 64 - numbits >= num;
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;
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);
85 return add(data >>> maxadd, num - maxadd);
92 assert size() >= num : "too few bits in storage";
93 int entry = start / 64;
96 int n = num > max ? max : num;
97 long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
98 long res = (bits[entry] >>> off) & mask;
102 long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
103 res |= (bits[(entry + 1) % bits.length] & mask2) << n;
105 start = (start + num) % (64 * bits.length);
110 return 64 * bits.length;
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();
124 ins.add(new Integer(0));
125 data = rand.nextLong();
126 int num = rand.nextInt(37);
129 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
130 ins.add(new Integer(num));
133 System.out.println("\nretrieving...");
136 ret.add(new Integer(num));
139 System.out.println("\ninsertion sequence:");
140 for (int i = 0; i < ins.size(); i++) {
141 System.out.print(" " + ins.get(i));
143 System.out.println("\nretrieval sequence:");
144 for (int i = 0; i < ret.size(); i++) {
145 System.out.print(" " + ret.get(i));
147 System.out.println();
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);
164 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
165 ins.add(new Integer(num));
167 num = rand.nextInt(Math.min(37, bs.size()));
170 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
171 ret.add(new Integer(num));
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());
179 long data = bs.get(num);
180 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
181 ret.add(new Integer(num));
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));
192 System.out.println("\nretrieval sequence:");
193 for (int i = 0; i < ret.size(); i++) {
194 System.out.print(" " + ret.get(i));
196 System.out.println();
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);
214 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
215 ins.add(new Integer(num));
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());
225 long data = bs.get(num);
226 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
227 ret.add(new Integer(num));
231 System.out.println("\ninsertion sequence:");
232 for (int i = 0; i < ins.size(); i++) {
233 System.out.print(" " + ins.get(i));
235 System.out.println("\nretrieval sequence:");
236 for (int i = 0; i < ret.size(); i++) {
237 System.out.print(" " + ret.get(i));
239 System.out.println();
242 static void print(long data, int num) {
243 for (int i = 0; i < num; i++) {
244 System.out.print((data >>> i) & 0x1);
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));
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");
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");
266 // Run BitStorage tests
267 public static void main(String[] args) {
268 BitStorage.test1(args);
269 BitStorage.test2(args);
270 BitStorage.test3(args);
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;
280 // dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
281 private void add(boolean bit) {
285 private boolean get() {
286 return ((Boolean)bits.remove());
288 boolean haveBoxOutOp;
290 public void service() {
291 if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
292 long op = box_inOp.removeDataForShip();
293 long data = box_in.removeDataForShip();
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; }
301 for(long i=take-1-drop; i>=0; i--)
302 add( (data & (1L<<i)) != 0);
304 for(long i=WORDSIZE-take+drop; i<WORDSIZE; i++)
305 add( (data & (1L<<i)) != 0);
309 if (!haveBoxOutOp && box_outOp.dataReadyForShip()) {
310 boxOutOp = box_outOp.removeDataForShip();
314 if (haveBoxOutOp && box_out.readyForDataFromShip()) {
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) {
323 for(int i=0; i<drop; i++) get();
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);
331 for(long i=WORDSIZE-take; i<WORDSIZE; i++)
332 if (get()) ret |= 1L<<i;
333 // FIXME: sign-extend!
335 box_out.addDataFromShip(ret);
336 haveBoxOutOp = false;
342 == FPGA ==============================================================
343 `define BITSTORAGE_SIZE 148
344 `define BITSTORAGE_BITS 16
346 `define OP_LSBFIRST 0
347 `define OP_COUNT 13:8
349 reg [(`BITSTORAGE_SIZE-1):0] bitstorage;
350 reg [(`BITSTORAGE_BITS-1):0] bitstorage_count;
351 reg [(`BITSTORAGE_BITS-1):0] dequeue_remaining;
352 reg [(`BITSTORAGE_BITS-1):0] enqueue_remaining;
353 initial dequeue_remaining = 0;
354 initial enqueue_remaining = 0;
355 initial bitstorage_count = 0;
357 always @(posedge clk) begin
358 if (!in_r && in_a) in_a <= 0;
359 if (!inOp_r && inOp_a) inOp_a <= 0;
360 if (!outOp_r && outOp_a) outOp_a <= 0;
362 if (out_r && out_a) out_r <= 0;
364 if (dequeue_remaining > 0) begin
365 if (dequeue_remaining <= outOp_d[`OP_COUNT])
367 if (outOp_d[`OP_LSBFIRST]) begin
368 out_d[`DATAWIDTH-1-(dequeue_remaining-1)] <= bitstorage[0];
370 out_d[ dequeue_remaining-1 ] <= bitstorage[0];
373 bitstorage[(`BITSTORAGE_SIZE-2):0] <= bitstorage[(`BITSTORAGE_SIZE-1):1];
374 bitstorage_count <= bitstorage_count - 1;
375 if (dequeue_remaining == 1) begin
379 dequeue_remaining <= dequeue_remaining - 1;
381 end else if (enqueue_remaining > 0) begin
382 bitstorage[bitstorage_count] <=
384 ? in_d[`DATAWIDTH-1-(inOp_d[`OP_DROP]+enqueue_remaining-1)]
385 : in_d[ inOp_d[`OP_DROP]+enqueue_remaining-1 ];
386 bitstorage_count <= bitstorage_count + 1;
387 if (enqueue_remaining == 1) begin
391 enqueue_remaining <= enqueue_remaining - 1;
393 end else if (in_r && !in_a && inOp_r && !inOp_a && `BITSTORAGE_SIZE > bitstorage_count + inOp_d[`OP_COUNT]) begin
394 // FIXME: zero count => lockup
395 enqueue_remaining <= inOp_d[`OP_COUNT];
397 end else if (!out_r && !out_a && outOp_r && !outOp_a && (bitstorage_count >= (outOp_d[`OP_COUNT]+outOp_d[`OP_DROP]))) begin
398 dequeue_remaining <= outOp_d[`OP_COUNT] + outOp_d[`OP_DROP];
399 out_d <= (outOp_d[`OP_SIGNEXT] && bitstorage[outOp_d[`OP_DROP]]) ? 37'b1111111111111111111111111111111111111 : 0;
405 == Test ==============================================================
407 // FIXME: this test case is woefully inadequate!!!!!
415 // ships required in order to run this code
417 #ship bitfifo : BitFifo
419 bitfifo.outOp: literal BitFifo.outOp[take=37]; [*] deliver;
420 bitfifo.out: [*] take, sendto debug.in;
421 debug.in: [*] take, deliver;
422 bitfifo.in: literal 1; [2] deliver;
425 literal BitFifo.inOp[take=37];
427 literal BitFifo.inOp[take=37,lsbFirst];
431 == Contributors =========================================================
432 Amir Kamil <kamil@cs.berkeley.edu>
433 Adam Megacz <megacz@cs.berkeley.edu>