3 == Ports ===========================================================
6 constant rev: .......................1.............
7 constant inv: ........................1............
8 constant count: .........................nnnnnn......
9 constant offset: ...............................nnnnnn
14 == Constants ========================================================
16 == TeX ==============================================================
19 +-------------+ +---------------+ +------------+
20 | inEnqueue |-->| |-->| outDequeue |
21 +-------------+ | | +------------+
23 +-------------+ | | +-------------+
24 | inEnqueueOp |-->| |<--| inDequeueOp |
25 +-------------+ +---------------+ +-------------+
28 \section*{inEnqueueOp}
29 \setlength{\bitwidth}{6mm}
32 \bitheader[b]{0,5,6,11,12,13}\\
41 \item [\tt Rev] ({\bf Reverse Before Enqueue})
42 \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
43 \item [\tt Count] ({\bf Count of Bits To Enqueue})
44 \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
47 By default, bits are enqueued {\it most significant bit first} (bits
48 in Sun byte order). If {\tt Rev=1}, the bits are reversed before
49 performing the directions below.
51 If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
52 was actually {\tt 37-Offset-Count} for all directions below.
58 \section*{inDequeueOp}
59 \setlength{\bitwidth}{6mm}
62 \bitheader[b]{0,5,6,11-21,22}\\
69 \bitbox{2}{Left\\ Fill}
70 \bitbox{2}{Right\\ Fill}
77 \item [\tt Until] ({\bf Shift until you see a (0, 1)})
78 \item [\tt Sort] ({\bf Sort the Bits})
79 \item [\tt Get] ({\bf Get the value of the counter})
80 \item [\tt Rev] ({\bf Reverse Before Enqueue})
81 \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
82 \item [\tt Rst] ({\bf Reset Counter Before Operation})
83 \item [\tt Left Fill] ({\bf Left Fill (0, 1, sign)})
84 \item [\tt Right Fill] ({\bf Right Fill (0, 1, sign)})
85 \item [\tt Count] ({\bf Count of Bits To Enqueue})
86 \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
90 == Fleeterpreter ====================================================
92 static class BitStorage {
96 BitStorage(int size) {
97 bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
102 boolean hasSpace(int num) {
103 return bits.length * 64 - numbits >= num;
105 boolean add(long data, int num) {
106 if (!hasSpace(num)) return false;
107 int entry = ((numbits + start) / 64) % bits.length;
108 int off = (numbits + start) % 64;
109 int maxadd = 64 - off;
110 long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
111 bits[entry] = (bits[entry] & mask) | (data << off);
114 return add(data >>> maxadd, num - maxadd);
121 assert size() >= num : "too few bits in storage";
122 int entry = start / 64;
123 int off = start % 64;
125 int n = num > max ? max : num;
126 long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
127 long res = (bits[entry] >>> off) & mask;
128 int oldstart = start;
131 long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
132 res |= (bits[(entry + 1) % bits.length] & mask2) << n;
134 start = (start + num) % (64 * bits.length);
139 return 64 * bits.length;
141 // Test code for BitStorage
142 static void test3(String[] args) {
143 BitStorage bs = new BitStorage(37);
144 Random rand = new Random();
145 Vector ins = new Vector();
146 Vector ret = new Vector();
147 StringBuffer sbi = new StringBuffer();
148 StringBuffer sbr = new StringBuffer();
149 System.out.println("==== Test #3 ====");
150 System.out.println("inserting...");
151 long data = rand.nextLong();
153 ins.add(new Integer(0));
154 data = rand.nextLong();
155 int num = rand.nextInt(37);
158 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
159 ins.add(new Integer(num));
162 System.out.println("\nretrieving...");
165 ret.add(new Integer(num));
168 System.out.println("\ninsertion sequence:");
169 for (int i = 0; i < ins.size(); i++) {
170 System.out.print(" " + ins.get(i));
172 System.out.println("\nretrieval sequence:");
173 for (int i = 0; i < ret.size(); i++) {
174 System.out.print(" " + ret.get(i));
176 System.out.println();
179 static void test2(String[] args) {
180 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
181 BitStorage bs = new BitStorage(37 * iters);
182 Random rand = new Random();
183 Vector ins = new Vector();
184 Vector ret = new Vector();
185 StringBuffer sbi = new StringBuffer();
186 StringBuffer sbr = new StringBuffer();
187 System.out.println("==== Test #2 ====");
188 for (int i = 0; i < iters; i++) {
189 long data = rand.nextLong();
190 int num = rand.nextInt(37);
193 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
194 ins.add(new Integer(num));
196 num = rand.nextInt(Math.min(37, bs.size()));
199 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
200 ret.add(new Integer(num));
203 //for (int i = 0; i < iters; i++) {
204 while (bs.size() > 0) {
205 int num = Math.min(rand.nextInt(37), bs.size());
206 //int num = Math.min(33, bs.size());
208 long data = bs.get(num);
209 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
210 ret.add(new Integer(num));
213 System.out.println("inserted:");
214 System.out.println(sbi);
215 System.out.println("retrieved:");
216 System.out.println(sbr);
217 System.out.println("insertion sequence:");
218 for (int i = 0; i < ins.size(); i++) {
219 System.out.print(" " + ins.get(i));
221 System.out.println("\nretrieval sequence:");
222 for (int i = 0; i < ret.size(); i++) {
223 System.out.print(" " + ret.get(i));
225 System.out.println();
228 static void test1(String[] args) {
229 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
230 BitStorage bs = new BitStorage(37 * iters);
231 Random rand = new Random();
232 Vector ins = new Vector();
233 Vector ret = new Vector();
234 StringBuffer sbi = new StringBuffer();
235 StringBuffer sbr = new StringBuffer();
236 System.out.println("==== Test #1 ====");
237 System.out.println("inserting...");
238 for (int i = 0; i < iters; i++) {
239 long data = rand.nextLong();
240 int num = rand.nextInt(37);
243 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
244 ins.add(new Integer(num));
248 System.out.println("\nretrieving...");
249 //for (int i = 0; i < iters; i++) {
250 while (bs.size() > 0) {
251 int num = Math.min(rand.nextInt(37), bs.size());
252 //int num = Math.min(33, bs.size());
254 long data = bs.get(num);
255 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
256 ret.add(new Integer(num));
260 System.out.println("\ninsertion sequence:");
261 for (int i = 0; i < ins.size(); i++) {
262 System.out.print(" " + ins.get(i));
264 System.out.println("\nretrieval sequence:");
265 for (int i = 0; i < ret.size(); i++) {
266 System.out.print(" " + ret.get(i));
268 System.out.println();
271 static void print(long data, int num) {
272 for (int i = 0; i < num; i++) {
273 System.out.print((data >>> i) & 0x1);
276 static void add(StringBuffer sb, long data, int num) {
277 for (int i = 0; i < num; i++) {
278 sb.append((int) ((data >>> i) & 0x1));
281 static void check(StringBuffer sb1, StringBuffer sb2) {
282 int len = sb2.length();
283 if (len > sb1.length()) {
284 System.out.println("error: retrieval sequence is longer than insertion sequence");
287 for (int i = 0; i < sb2.length(); i++) {
288 if (sb1.charAt(i) != sb2.charAt(i)) {
289 System.out.println("error: bit at position " + i + " does not match");
295 // Run BitStorage tests
296 public static void main(String[] args) {
297 BitStorage.test1(args);
298 BitStorage.test2(args);
299 BitStorage.test3(args);
302 // Ship implementation
303 private Packet selector;
304 private static final int MAXBITS = 128;
305 private static final int WORDSIZE = 37;
306 private BitStorage bits = new BitStorage(MAXBITS);
308 public void service() {
309 if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
310 if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
311 long data = box_inEnqueue.removeDataForShip();
312 bits.add(data, WORDSIZE);
314 if (selector == null && !box_inEnqueueOp.dataReadyForShip()) return;
315 if (selector == null) selector = box_inEnqueueOp.removePacketForShip();
317 String port = selector.destination.getDestinationName();
318 long val = selector.value; // check if <= 37?
320 if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
323 if (val < bits.size()) {
327 if (port.startsWith("take")) {
328 if (!box_outDequeue.readyForDataFromShip()) return;
329 long data = bits.get((int) val);
330 if (port.endsWith("FillOnes")) {
331 data |= (-1L << val);
332 } else if (port.endsWith("SignExtend")) {
333 data = (data << (64 - val)) >> (64 - val);
335 box_outDequeue.addDataFromShip(data);
345 == FleetSim ==============================================================
347 == FPGA ==============================================================
349 == Contributors =========================================================
350 Amir Kamil <kamil@cs.berkeley.edu>