3 == Ports ===========================================================
8 data in: cmd.takeFillZeros
9 data in: cmd.takeInvFillZeros
10 data in: cmd.takeFillOnes
11 data in: cmd.takeInvFillOnes
12 data in: cmd.takeSignExtend
13 data in: cmd.takeInvSignExtend
17 == Constants ========================================================
19 == TeX ==============================================================
21 +------+ +--------------+ +-------+
22 |inData|---| |---|outData|
23 +------+ | | +-------+
25 +------+ | | +-------+
26 | inOp |---| |---| outOp |
27 +------+ +--------------+ +-------+
31 | | -- reverse before enqueue
33 | | -- count := (37-offset-count)
41 | | -- offset (6 bits)
50 | | -- shift until you see a "Z" (2 bits)
52 | | -- sort the digits
54 | | -- give me the count
56 | | -- reverse after dequeue
58 | | -- count := 37-off-count
60 | | -- reset the counter before operation
62 | | -- fill left with (1,0,sign) (2 bits)
64 | | -- fill right with (1,0,sign) (2 bits)
72 | | -- offset (6 bits)
80 == Fleeterpreter ====================================================
82 private static class BitStorage {
86 BitStorage(int size) {
87 bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
92 boolean hasSpace(int num) {
93 return bits.length * 64 - numbits >= num;
95 boolean add(long data, int num) {
96 if (!hasSpace(num)) return false;
97 int entry = ((numbits + start) / 64) % bits.length;
98 int off = (numbits + start) % 64;
99 int maxadd = 64 - off;
100 bits[entry] = (bits[entry] & (-1L >>> maxadd)) | (data << off);
103 return add(data >>> maxadd, num - maxadd);
110 assert size() >= num : "too few bits in storage";
111 int entry = start / 64;
112 int off = start % 64;
114 int n = num > max ? max : num;
115 long res = (bits[entry] >>> off) & (-1L >>> (64 - n));
116 int oldstart = start;
119 res |= (bits[(entry + 1) % bits.length] & (-1L >>> (64 - n2))) << n;
121 start = (start + num) % (64 * bits.length);
126 return 64 * bits.length;
128 // Test code for BitStorage
129 static void test2(String[] args) {
130 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
131 BitStorage bs = new BitStorage(37 * iters);
132 Random rand = new Random();
133 Vector ins = new Vector();
134 Vector ret = new Vector();
135 StringBuffer sbi = new StringBuffer();
136 StringBuffer sbr = new StringBuffer();
137 System.out.println("==== Test #2 ====");
138 for (int i = 0; i < iters; i++) {
139 long data = rand.nextLong();
140 int num = rand.nextInt(37);
143 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
144 ins.add(new Integer(num));
146 num = rand.nextInt(Math.min(37, bs.size()));
149 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
150 ret.add(new Integer(num));
153 //for (int i = 0; i < iters; i++) {
154 while (bs.size() > 0) {
155 int num = Math.min(rand.nextInt(37), bs.size());
156 //int num = Math.min(33, bs.size());
158 long data = bs.get(num);
159 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
160 ret.add(new Integer(num));
163 System.out.println("inserted:");
164 System.out.println(sbi);
165 System.out.println("retrieved:");
166 System.out.println(sbr);
167 System.out.println("insertion sequence:");
168 for (int i = 0; i < ins.size(); i++) {
169 System.out.print(" " + ins.get(i));
171 System.out.println("\nretrieval sequence:");
172 for (int i = 0; i < ret.size(); i++) {
173 System.out.print(" " + ret.get(i));
175 System.out.println();
178 static void test1(String[] args) {
179 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
180 BitStorage bs = new BitStorage(37 * iters);
181 Random rand = new Random();
182 Vector ins = new Vector();
183 Vector ret = new Vector();
184 StringBuffer sbi = new StringBuffer();
185 StringBuffer sbr = new StringBuffer();
186 System.out.println("==== Test #1 ====");
187 System.out.println("inserting...");
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));
198 System.out.println("\nretrieving...");
199 //for (int i = 0; i < iters; i++) {
200 while (bs.size() > 0) {
201 int num = Math.min(rand.nextInt(37), bs.size());
202 //int num = Math.min(33, bs.size());
204 long data = bs.get(num);
205 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
206 ret.add(new Integer(num));
210 System.out.println("\ninsertion sequence:");
211 for (int i = 0; i < ins.size(); i++) {
212 System.out.print(" " + ins.get(i));
214 System.out.println("\nretrieval sequence:");
215 for (int i = 0; i < ret.size(); i++) {
216 System.out.print(" " + ret.get(i));
218 System.out.println();
221 static void print(long data, int num) {
222 for (int i = 0; i < num; i++) {
223 System.out.print((data >>> i) & 0x1);
226 static void add(StringBuffer sb, long data, int num) {
227 for (int i = 0; i < num; i++) {
228 sb.append((int) ((data >>> i) & 0x1));
231 static void check(StringBuffer sb1, StringBuffer sb2) {
232 int len = sb2.length();
233 if (len > sb1.length()) {
234 System.out.println("error: retrieval sequence is longer than insertion sequence");
237 for (int i = 0; i < sb2.length(); i++) {
238 if (sb1.charAt(i) != sb2.charAt(i)) {
239 System.out.println("error: bit at position " + i + " does not match");
245 // Run BitStorage tests
246 public static void main(String[] args) {
247 BitStorage.test1(args);
248 BitStorage.test2(args);
251 // Ship implementation
252 private Packet selector;
253 private static final int MAXBITS = 128;
254 private static final int WORDSIZE = 37;
255 private BitStorage bits = new BitStorage(MAXBITS);
257 public void service() {
258 if (!box_out.readyForDataFromShip() && !box_in.dataReadyForShip()) return;
259 if (box_in.dataReadyForShip() && bits.hasSpace(WORDSIZE)) {
260 long data = box_in.removeDataForShip();
261 bits.add(data, WORDSIZE);
263 if (selector == null && !box_cmd.dataReadyForShip()) return;
264 if (selector == null) selector = box_cmd.removePacketForShip();
266 String port = selector.destination.getDestinationName();
267 long val = selector.value; // check if <= 37?
269 if (port.startsWith("takeInv") || port.startsWith("dropInv")) {
272 if (val < bits.size()) {
276 if (port.startsWith("take")) {
277 if (!box_out.readyForDataFromShip()) return;
278 long data = bits.get((int) val);
279 if (port.endsWith("FillOnes")) {
280 data |= (-1L << val);
281 } else if (port.endsWith("SignExtend")) {
282 data = (data << (64 - val)) >> (64 - val);
284 box_out.addDataFromShip(data);
294 == FleetSim ==============================================================
296 == FPGA ==============================================================
298 == Contributors =========================================================
299 Amir Kamil <kamil@cs.berkeley.edu>