3 == Ports ===========================================================
8 constant rev: .......................1.............
9 constant inv: ........................1............
10 constant count: .........................nnnnnn......
11 constant offset: ...............................nnnnnn
16 == Sample Code ======================================================
19 == Constants ========================================================
21 == TeX ==============================================================
24 +-------------+ +---------------+ +------------+
25 | inEnqueue |-->| |-->| outDequeue |
26 +-------------+ | | +------------+
28 +-------------+ | | +-------------+
29 | inEnqueueOp |-->| |<--| inDequeueOp |
30 +-------------+ +---------------+ +-------------+
33 \section*{inEnqueueOp}
34 \setlength{\bitwidth}{6mm}
37 \bitheader[b]{0,5,6,11,12,13}\\
46 \item [\tt Rev] ({\bf Reverse Before Enqueue})
47 \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
48 \item [\tt Count] ({\bf Count of Bits To Enqueue})
49 \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
52 By default, bits are enqueued {\it most significant bit first} (bits
53 in Sun byte order). If {\tt Rev=1}, the bits are reversed before
54 performing the directions below.
56 If {\tt Inv=1}, then the {\tt Count} field is treated as if its value
57 was actually {\tt 37-Offset-Count} for all directions below.
63 \section*{inDequeueOp}
64 \setlength{\bitwidth}{6mm}
67 \bitheader[b]{0,5,6,11-21,22}\\
74 \bitbox{2}{Left\\ Fill}
75 \bitbox{2}{Right\\ Fill}
82 \item [\tt Until] ({\bf Shift until you see a (0, 1)})
83 \item [\tt Sort] ({\bf Sort the Bits})
84 \item [\tt Get] ({\bf Get the value of the counter})
85 \item [\tt Rev] ({\bf Reverse Before Enqueue})
86 \item [\tt Inv] ({\bf Invert Count}) -- treat {\tt Count} as {\tt 37-Offset-Count}
87 \item [\tt Rst] ({\bf Reset Counter Before Operation})
88 \item [\tt Left Fill] ({\bf Left Fill (0, 1, sign)})
89 \item [\tt Right Fill] ({\bf Right Fill (0, 1, sign)})
90 \item [\tt Count] ({\bf Count of Bits To Enqueue})
91 \item [\tt Offset] ({\bf Offset of Bits To Enqueue})
95 == Fleeterpreter ====================================================
97 static class BitStorage {
101 BitStorage(int size) {
102 bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
107 boolean hasSpace(int num) {
108 return bits.length * 64 - numbits >= num;
110 boolean add(long data, int num) {
111 if (!hasSpace(num)) return false;
112 int entry = ((numbits + start) / 64) % bits.length;
113 int off = (numbits + start) % 64;
114 int maxadd = 64 - off;
115 long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
116 bits[entry] = (bits[entry] & mask) | (data << off);
119 return add(data >>> maxadd, num - maxadd);
126 assert size() >= num : "too few bits in storage";
127 int entry = start / 64;
128 int off = start % 64;
130 int n = num > max ? max : num;
131 long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
132 long res = (bits[entry] >>> off) & mask;
133 int oldstart = start;
136 long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
137 res |= (bits[(entry + 1) % bits.length] & mask2) << n;
139 start = (start + num) % (64 * bits.length);
144 return 64 * bits.length;
146 // Test code for BitStorage
147 static void test3(String[] args) {
148 BitStorage bs = new BitStorage(37);
149 Random rand = new Random();
150 Vector ins = new Vector();
151 Vector ret = new Vector();
152 StringBuffer sbi = new StringBuffer();
153 StringBuffer sbr = new StringBuffer();
154 System.out.println("==== Test #3 ====");
155 System.out.println("inserting...");
156 long data = rand.nextLong();
158 ins.add(new Integer(0));
159 data = rand.nextLong();
160 int num = rand.nextInt(37);
163 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
164 ins.add(new Integer(num));
167 System.out.println("\nretrieving...");
170 ret.add(new Integer(num));
173 System.out.println("\ninsertion sequence:");
174 for (int i = 0; i < ins.size(); i++) {
175 System.out.print(" " + ins.get(i));
177 System.out.println("\nretrieval sequence:");
178 for (int i = 0; i < ret.size(); i++) {
179 System.out.print(" " + ret.get(i));
181 System.out.println();
184 static void test2(String[] args) {
185 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
186 BitStorage bs = new BitStorage(37 * iters);
187 Random rand = new Random();
188 Vector ins = new Vector();
189 Vector ret = new Vector();
190 StringBuffer sbi = new StringBuffer();
191 StringBuffer sbr = new StringBuffer();
192 System.out.println("==== Test #2 ====");
193 for (int i = 0; i < iters; i++) {
194 long data = rand.nextLong();
195 int num = rand.nextInt(37);
198 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
199 ins.add(new Integer(num));
201 num = rand.nextInt(Math.min(37, bs.size()));
204 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
205 ret.add(new Integer(num));
208 //for (int i = 0; i < iters; i++) {
209 while (bs.size() > 0) {
210 int num = Math.min(rand.nextInt(37), bs.size());
211 //int num = Math.min(33, bs.size());
213 long data = bs.get(num);
214 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
215 ret.add(new Integer(num));
218 System.out.println("inserted:");
219 System.out.println(sbi);
220 System.out.println("retrieved:");
221 System.out.println(sbr);
222 System.out.println("insertion sequence:");
223 for (int i = 0; i < ins.size(); i++) {
224 System.out.print(" " + ins.get(i));
226 System.out.println("\nretrieval sequence:");
227 for (int i = 0; i < ret.size(); i++) {
228 System.out.print(" " + ret.get(i));
230 System.out.println();
233 static void test1(String[] args) {
234 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
235 BitStorage bs = new BitStorage(37 * iters);
236 Random rand = new Random();
237 Vector ins = new Vector();
238 Vector ret = new Vector();
239 StringBuffer sbi = new StringBuffer();
240 StringBuffer sbr = new StringBuffer();
241 System.out.println("==== Test #1 ====");
242 System.out.println("inserting...");
243 for (int i = 0; i < iters; i++) {
244 long data = rand.nextLong();
245 int num = rand.nextInt(37);
248 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
249 ins.add(new Integer(num));
253 System.out.println("\nretrieving...");
254 //for (int i = 0; i < iters; i++) {
255 while (bs.size() > 0) {
256 int num = Math.min(rand.nextInt(37), bs.size());
257 //int num = Math.min(33, bs.size());
259 long data = bs.get(num);
260 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
261 ret.add(new Integer(num));
265 System.out.println("\ninsertion sequence:");
266 for (int i = 0; i < ins.size(); i++) {
267 System.out.print(" " + ins.get(i));
269 System.out.println("\nretrieval sequence:");
270 for (int i = 0; i < ret.size(); i++) {
271 System.out.print(" " + ret.get(i));
273 System.out.println();
276 static void print(long data, int num) {
277 for (int i = 0; i < num; i++) {
278 System.out.print((data >>> i) & 0x1);
281 static void add(StringBuffer sb, long data, int num) {
282 for (int i = 0; i < num; i++) {
283 sb.append((int) ((data >>> i) & 0x1));
286 static void check(StringBuffer sb1, StringBuffer sb2) {
287 int len = sb2.length();
288 if (len > sb1.length()) {
289 System.out.println("error: retrieval sequence is longer than insertion sequence");
292 for (int i = 0; i < sb2.length(); i++) {
293 if (sb1.charAt(i) != sb2.charAt(i)) {
294 System.out.println("error: bit at position " + i + " does not match");
300 // Run BitStorage tests
301 public static void main(String[] args) {
302 BitStorage.test1(args);
303 BitStorage.test2(args);
304 BitStorage.test3(args);
307 // Ship implementation
308 private Packet selector;
309 private static final int MAXBITS = 128;
310 private static final int WORDSIZE = 37;
311 private BitStorage bits = new BitStorage(MAXBITS);
313 public void service() {
314 if (!box_outDequeue.readyForDataFromShip() && !box_inEnqueue.dataReadyForShip()) return;
315 if (box_inEnqueue.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
316 long data = box_inEnqueue.removeDataForShip();
317 bits.add(data, WORDSIZE);
319 if (selector == null && !box_inEnqueueOp.dataReadyForShip()) return;
320 if (selector == null) selector = box_inEnqueueOp.removePacketForShip();
322 String port = selector.destination.getDestinationName();
323 long val = selector.value; // check if <= 37?
325 if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
328 if (val < bits.size()) {
332 if (port.startsWith("take")) {
333 if (!box_outDequeue.readyForDataFromShip()) return;
334 long data = bits.get((int) val);
335 if (port.endsWith("FillOnes")) {
336 data |= (-1L << val);
337 } else if (port.endsWith("SignExtend")) {
338 data = (data << (64 - val)) >> (64 - val);
340 box_outDequeue.addDataFromShip(data);
350 == FleetSim ==============================================================
352 == FPGA ==============================================================
354 == Contributors =========================================================
355 Amir Kamil <kamil@cs.berkeley.edu>