3 == Ports ===========================================================
6 constant rev: .......................1.............
7 constant inv: ........................1............
8 constant count: .........................nnnnnn......
9 constant offset: ...............................nnnnnn
14 == Sample Code ======================================================
17 == Constants ========================================================
19 == TeX ==============================================================
22 +-------------+ +---------------+ +------------+
23 | inEnqueue |-->| |-->| outDequeue |
24 +-------------+ | | +------------+
26 +-------------+ | | +-------------+
27 | inEnqueueOp |-->| |<--| inDequeueOp |
28 +-------------+ +---------------+ +-------------+
31 \section*{inEnqueueOp}
32 \setlength{\bitwidth}{6mm}
35 \bitheader[b]{0,5,6,11,12,13}\\
44 \item [\tt Rev] ({\bf Reverse Before Enqueue})
45 \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
46 \item [\tt Count] ({\bf Count of Bits To Enqueue})
47 \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
50 By default, bits are enqueued {\it most significant bit first} (bits
51 in Sun byte order). If {\tt Rev=1}, the bits are reversed before
52 performing the directions below.
54 If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
55 was actually {\tt 37-Offset-Count} for all directions below.
61 \section*{inDequeueOp}
62 \setlength{\bitwidth}{6mm}
65 \bitheader[b]{0,5,6,11-21,22}\\
72 \bitbox{2}{Left\\ Fill}
73 \bitbox{2}{Right\\ Fill}
80 \item [\tt Until] ({\bf Shift until you see a (0, 1)})
81 \item [\tt Sort] ({\bf Sort the Bits})
82 \item [\tt Get] ({\bf Get the value of the counter})
83 \item [\tt Rev] ({\bf Reverse Before Enqueue})
84 \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
85 \item [\tt Rst] ({\bf Reset Counter Before Operation})
86 \item [\tt Left Fill] ({\bf Left Fill (0, 1, sign)})
87 \item [\tt Right Fill] ({\bf Right Fill (0, 1, sign)})
88 \item [\tt Count] ({\bf Count of Bits To Dequeue})
89 \item [\tt Offset] ({\bf Offset of Bits To Dequeue})
93 == Fleeterpreter ====================================================
95 static class BitStorage {
99 BitStorage(int size) {
100 bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
105 boolean hasSpace(int num) {
106 return bits.length * 64 - numbits >= num;
108 boolean add(long data, int num) {
109 if (!hasSpace(num)) return false;
110 int entry = ((numbits + start) / 64) % bits.length;
111 int off = (numbits + start) % 64;
112 int maxadd = 64 - off;
113 long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
114 bits[entry] = (bits[entry] & mask) | (data << off);
117 return add(data >>> maxadd, num - maxadd);
124 assert size() >= num : "too few bits in storage";
125 int entry = start / 64;
126 int off = start % 64;
128 int n = num > max ? max : num;
129 long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
130 long res = (bits[entry] >>> off) & mask;
131 int oldstart = start;
134 long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
135 res |= (bits[(entry + 1) % bits.length] & mask2) << n;
137 start = (start + num) % (64 * bits.length);
142 return 64 * bits.length;
144 // Test code for BitStorage
145 static void test3(String[] args) {
146 BitStorage bs = new BitStorage(37);
147 Random rand = new Random();
148 Vector ins = new Vector();
149 Vector ret = new Vector();
150 StringBuffer sbi = new StringBuffer();
151 StringBuffer sbr = new StringBuffer();
152 System.out.println("==== Test #3 ====");
153 System.out.println("inserting...");
154 long data = rand.nextLong();
156 ins.add(new Integer(0));
157 data = rand.nextLong();
158 int num = rand.nextInt(37);
161 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
162 ins.add(new Integer(num));
165 System.out.println("\nretrieving...");
168 ret.add(new Integer(num));
171 System.out.println("\ninsertion sequence:");
172 for (int i = 0; i < ins.size(); i++) {
173 System.out.print(" " + ins.get(i));
175 System.out.println("\nretrieval sequence:");
176 for (int i = 0; i < ret.size(); i++) {
177 System.out.print(" " + ret.get(i));
179 System.out.println();
182 static void test2(String[] args) {
183 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
184 BitStorage bs = new BitStorage(37 * iters);
185 Random rand = new Random();
186 Vector ins = new Vector();
187 Vector ret = new Vector();
188 StringBuffer sbi = new StringBuffer();
189 StringBuffer sbr = new StringBuffer();
190 System.out.println("==== Test #2 ====");
191 for (int i = 0; i < iters; i++) {
192 long data = rand.nextLong();
193 int num = rand.nextInt(37);
196 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
197 ins.add(new Integer(num));
199 num = rand.nextInt(Math.min(37, bs.size()));
202 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
203 ret.add(new Integer(num));
206 //for (int i = 0; i < iters; i++) {
207 while (bs.size() > 0) {
208 int num = Math.min(rand.nextInt(37), bs.size());
209 //int num = Math.min(33, bs.size());
211 long data = bs.get(num);
212 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
213 ret.add(new Integer(num));
216 System.out.println("inserted:");
217 System.out.println(sbi);
218 System.out.println("retrieved:");
219 System.out.println(sbr);
220 System.out.println("insertion sequence:");
221 for (int i = 0; i < ins.size(); i++) {
222 System.out.print(" " + ins.get(i));
224 System.out.println("\nretrieval sequence:");
225 for (int i = 0; i < ret.size(); i++) {
226 System.out.print(" " + ret.get(i));
228 System.out.println();
231 static void test1(String[] args) {
232 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
233 BitStorage bs = new BitStorage(37 * iters);
234 Random rand = new Random();
235 Vector ins = new Vector();
236 Vector ret = new Vector();
237 StringBuffer sbi = new StringBuffer();
238 StringBuffer sbr = new StringBuffer();
239 System.out.println("==== Test #1 ====");
240 System.out.println("inserting...");
241 for (int i = 0; i < iters; i++) {
242 long data = rand.nextLong();
243 int num = rand.nextInt(37);
246 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
247 ins.add(new Integer(num));
251 System.out.println("\nretrieving...");
252 //for (int i = 0; i < iters; i++) {
253 while (bs.size() > 0) {
254 int num = Math.min(rand.nextInt(37), bs.size());
255 //int num = Math.min(33, bs.size());
257 long data = bs.get(num);
258 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
259 ret.add(new Integer(num));
263 System.out.println("\ninsertion sequence:");
264 for (int i = 0; i < ins.size(); i++) {
265 System.out.print(" " + ins.get(i));
267 System.out.println("\nretrieval sequence:");
268 for (int i = 0; i < ret.size(); i++) {
269 System.out.print(" " + ret.get(i));
271 System.out.println();
274 static void print(long data, int num) {
275 for (int i = 0; i < num; i++) {
276 System.out.print((data >>> i) & 0x1);
279 static void add(StringBuffer sb, long data, int num) {
280 for (int i = 0; i < num; i++) {
281 sb.append((int) ((data >>> i) & 0x1));
284 static void check(StringBuffer sb1, StringBuffer sb2) {
285 int len = sb2.length();
286 if (len > sb1.length()) {
287 System.out.println("error: retrieval sequence is longer than insertion sequence");
290 for (int i = 0; i < sb2.length(); i++) {
291 if (sb1.charAt(i) != sb2.charAt(i)) {
292 System.out.println("error: bit at position " + i + " does not match");
298 // Run BitStorage tests
299 public static void main(String[] args) {
300 BitStorage.test1(args);
301 BitStorage.test2(args);
302 BitStorage.test3(args);
305 // Ship implementation
306 private Packet selector;
307 private static final int MAXBITS = 128;
308 private static final int WORDSIZE = 37;
309 private BitStorage bits = new BitStorage(MAXBITS);
311 // dummy routine used for Alu3 test -- FIXME later but keep this functionality somehow!
312 public void service() {
313 if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
314 if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
315 long data = box_inEnqueue.removeDataForShip();
316 bits.add(data, WORDSIZE);
319 if (box_outDequeue.readyForDataFromShip() && bits.size() > 0) {
320 long data = bits.get(1) == 0 ? 0L : 0x1FFFFFFFFFL;
321 box_outDequeue.addDataFromShip(data);
327 public void service() {
328 if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
329 if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
330 long data = box_inEnqueue.removeDataForShip();
331 bits.add(data, WORDSIZE);
333 if (selector == null && !box_inEnqueueOp.dataReadyForShip()) return;
334 if (selector == null) selector = box_inEnqueueOp.removePacketForShip();
336 String port = selector.destination.getDestinationName();
337 long val = selector.value; // check if <= 37?
339 if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
342 if (val < bits.size()) {
346 if (port.startsWith("take")) {
347 if (!box_outDequeue.readyForDataFromShip()) return;
348 long data = bits.get((int) val);
349 if (port.endsWith("FillOnes")) {
350 data |= (-1L << val);
351 } else if (port.endsWith("SignExtend")) {
352 data = (data << (64 - val)) >> (64 - val);
354 box_outDequeue.addDataFromShip(data);
365 == FleetSim ==============================================================
367 == FPGA ==============================================================
368 reg [73:0] bitstorage;
369 reg [7:0] bitstorage_count; initial bitstorage_count = 0;
371 always @(posedge clk) begin
372 if (bitstorage_count == 0) begin
373 `onread(inEnqueue_r, inEnqueue_a)
374 bitstorage <= inEnqueue_d;
375 bitstorage_count <= 37;
376 outDequeue_d <= (inEnqueue_d[0] ? 37'b1111111111111111111111111111111111111 : 0);
379 `onwrite(outDequeue_r, outDequeue_a)
380 bitstorage_count <= bitstorage_count - 1;
381 outDequeue_d <= (bitstorage[1] ? 37'b1111111111111111111111111111111111111 : 0);
382 bitstorage <= bitstorage >> 1;
388 == Test ==============================================================
429 // ships required in order to run this code
431 #ship bitfifo : BitFifo
433 debug.in: [*] take, deliver;
434 99: sendto bitfifo.inEnqueue;
435 bitfifo.inEnqueue: take, deliver;
436 bitfifo.outDequeue: [*] take, sendto debug.in;
438 == Contributors =========================================================
439 Amir Kamil <kamil@cs.berkeley.edu>
440 Adam Megacz <megacz@cs.berkeley.edu>