3 == Ports ===========================================================
14 == Constants ========================================================
15 == TeX ==============================================================
17 {\tt Alu3} is a three-input adder which produces a pair of outputs in
18 carry-save form. It has no opcode input.
20 This ship also contains a private ``bit fifo'' similar to the {\tt
21 BitFifo} ship, except that only the dequeueing (output) interface is
22 exposed to the programmer. Each addition operation performed causes
23 the lowest bit of the {\it save} output to be enqueued into the bit
24 fifo. This can be used to produce a very efficient multiplier; see
25 the test case for this ship for more details.
27 \subsection*{Semantics}
29 When a value is present at each of {\tt in1}, {\tt in2} and {\tt in3},
30 these three values are consumed. The {\it carry} result of carry-save
31 addition is placed in {\tt out1}, and the {\it save} result of
32 carry-save addition is placed in {\tt out2}.
36 Is the second output supposed to be shifted?
38 Provide a way to clear/flush the internal bitfifo.
40 Do we even need this? Can we do the same thing with {\tt Lut3} and
41 {\tt BitFifo} together?
44 == Fleeterpreter ====================================================
45 static class BitStorage {
49 BitStorage(int size) {
50 bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
55 boolean hasSpace(int num) {
56 return bits.length * 64 - numbits >= num;
58 boolean peekTailBit() {
59 int entry = (((numbits-1) + start) / 64) % bits.length;
60 int off = ((numbits-1) + start) % 64;
61 int maxadd = 64 - off;
62 long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
63 return (bits[entry] & ~mask) != 0;
65 boolean add(long data, int num) {
66 if (!hasSpace(num)) return false;
67 int entry = ((numbits + start) / 64) % bits.length;
68 int off = (numbits + start) % 64;
69 int maxadd = 64 - off;
70 long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
71 bits[entry] = (bits[entry] & mask) | (data << off);
74 return add(data >>> maxadd, num - maxadd);
81 assert size() >= num : "too few bits in storage";
82 int entry = start / 64;
85 int n = num > max ? max : num;
86 long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
87 long res = (bits[entry] >>> off) & mask;
91 long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
92 res |= (bits[(entry + 1) % bits.length] & mask2) << n;
94 start = (start + num) % (64 * bits.length);
99 return 64 * bits.length;
101 // Test code for BitStorage
102 static void test3(String[] args) {
103 BitStorage bs = new BitStorage(37);
104 Random rand = new Random();
105 Vector ins = new Vector();
106 Vector ret = new Vector();
107 StringBuffer sbi = new StringBuffer();
108 StringBuffer sbr = new StringBuffer();
109 System.out.println("==== Test #3 ====");
110 System.out.println("inserting...");
111 long data = rand.nextLong();
113 ins.add(new Integer(0));
114 data = rand.nextLong();
115 int num = rand.nextInt(37);
118 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
119 ins.add(new Integer(num));
122 System.out.println("\nretrieving...");
125 ret.add(new Integer(num));
128 System.out.println("\ninsertion sequence:");
129 for (int i = 0; i < ins.size(); i++) {
130 System.out.print(" " + ins.get(i));
132 System.out.println("\nretrieval sequence:");
133 for (int i = 0; i < ret.size(); i++) {
134 System.out.print(" " + ret.get(i));
136 System.out.println();
139 static void test2(String[] args) {
140 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
141 BitStorage bs = new BitStorage(37 * iters);
142 Random rand = new Random();
143 Vector ins = new Vector();
144 Vector ret = new Vector();
145 StringBuffer sbi = new StringBuffer();
146 StringBuffer sbr = new StringBuffer();
147 System.out.println("==== Test #2 ====");
148 for (int i = 0; i < iters; i++) {
149 long data = rand.nextLong();
150 int num = rand.nextInt(37);
153 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
154 ins.add(new Integer(num));
156 num = rand.nextInt(Math.min(37, bs.size()));
159 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
160 ret.add(new Integer(num));
163 //for (int i = 0; i < iters; i++) {
164 while (bs.size() > 0) {
165 int num = Math.min(rand.nextInt(37), bs.size());
166 //int num = Math.min(33, bs.size());
168 long data = bs.get(num);
169 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
170 ret.add(new Integer(num));
173 System.out.println("inserted:");
174 System.out.println(sbi);
175 System.out.println("retrieved:");
176 System.out.println(sbr);
177 System.out.println("insertion sequence:");
178 for (int i = 0; i < ins.size(); i++) {
179 System.out.print(" " + ins.get(i));
181 System.out.println("\nretrieval sequence:");
182 for (int i = 0; i < ret.size(); i++) {
183 System.out.print(" " + ret.get(i));
185 System.out.println();
188 static void test1(String[] args) {
189 int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
190 BitStorage bs = new BitStorage(37 * iters);
191 Random rand = new Random();
192 Vector ins = new Vector();
193 Vector ret = new Vector();
194 StringBuffer sbi = new StringBuffer();
195 StringBuffer sbr = new StringBuffer();
196 System.out.println("==== Test #1 ====");
197 System.out.println("inserting...");
198 for (int i = 0; i < iters; i++) {
199 long data = rand.nextLong();
200 int num = rand.nextInt(37);
203 assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
204 ins.add(new Integer(num));
208 System.out.println("\nretrieving...");
209 //for (int i = 0; i < iters; i++) {
210 while (bs.size() > 0) {
211 int num = Math.min(rand.nextInt(37), bs.size());
212 //int num = Math.min(33, bs.size());
214 long data = bs.get(num);
215 assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
216 ret.add(new Integer(num));
220 System.out.println("\ninsertion 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 print(long data, int num) {
232 for (int i = 0; i < num; i++) {
233 System.out.print((data >>> i) & 0x1);
236 static void add(StringBuffer sb, long data, int num) {
237 for (int i = 0; i < num; i++) {
238 sb.append((int) ((data >>> i) & 0x1));
241 static void check(StringBuffer sb1, StringBuffer sb2) {
242 int len = sb2.length();
243 if (len > sb1.length()) {
244 System.out.println("error: retrieval sequence is longer than insertion sequence");
247 for (int i = 0; i < sb2.length(); i++) {
248 if (sb1.charAt(i) != sb2.charAt(i)) {
249 System.out.println("error: bit at position " + i + " does not match");
254 boolean mode = false;
255 BitStorage outBits = new BitStorage(74);
256 public void service() {
257 if (outBits.size() >= 37) {
258 if (box_outBits.readyForDataFromShip()) {
259 box_outBits.addDataFromShip(outBits.get(37));
262 if (box_in1.dataReadyForShip() &&
263 box_in2.dataReadyForShip() &&
264 box_in3.dataReadyForShip() &&
265 outBits.hasSpace(1) &&
266 box_out1.readyForDataFromShip() &&
267 box_out2.readyForDataFromShip()) {
268 long v1 = box_in1.removeDataForShip();
269 long v2 = box_in2.removeDataForShip();
270 long v3 = box_in3.removeDataForShip();
272 o1 = ((v1 & v2) | (v2 & v3) | (v1 & v3))/* << 1*/;
273 o2 = (v1 ^ v2 ^ v3) >> 1;
274 outBits.add((v1 ^ v2 ^ v3) & 0x1L, 1);
275 box_out1.addDataFromShip(o1);
276 box_out2.addDataFromShip(o2);
280 == FleetSim ==============================================================
282 == FPGA ==============================================================
284 reg [73:0] bitstorage; initial bitstorage = 0;
285 reg [7:0] bitstorage_count; initial bitstorage_count = 0;
287 always @(posedge clk) begin
291 bitstorage_count <= 0;
293 if (out1_r && out1_a) out1_r <= 0;
294 if (out2_r && out2_a) out2_r <= 0;
295 if (outBits_r && outBits_a) outBits_r <= 0;
296 if (!in1_r && in1_a) in1_a <= 0;
297 if (!in2_r && in2_a) in2_a <= 0;
298 if (!in3_r && in3_a) in3_a <= 0;
299 if (!out1_r && !out2_r && !outBits_r && in1_r && in2_r && in3_r) begin
300 out1_d <= { ((in1_d & in2_d)
302 | (in1_d & in3_d)) };
303 out2_d <= { 1'b0, (in1_d[(`DATAWIDTH-1):1] ^
304 in2_d[(`DATAWIDTH-1):1] ^
305 in3_d[(`DATAWIDTH-1):1]) };
306 if (bitstorage_count >= `DATAWIDTH-1) begin
307 outBits_d <= bitstorage[(`DATAWIDTH-1):0];
309 bitstorage_count <= 0;
310 bitstorage <= bitstorage >> `DATAWIDTH;
312 bitstorage[bitstorage_count] <= (in1_d[0] ^ in2_d[0] ^ in3_d[0]);
313 bitstorage_count <= bitstorage_count+1;
325 == Test ========================================================================
331 #ship rotator : Rotator
337 // 0: 100100100111110000000
338 // sel 011110100001001000000
339 // 1: 111000101000011000011
340 // r: 111000100110111000000
342 alu3.in1: literal 1; deliver; load repeat counter with 36; deliver;
343 alu3.in2: literal 0; deliver; literal 1; load repeat counter with 36; deliver;
344 alu3.in3: literal 4; deliver; load repeat counter with 36; deliver;
346 alu3.out1: take; sendto debug.in; [*] take;
347 alu3.out2: take; wait; sendto debug.in; [*] take;
348 alu3.outBits: take; wait; sendto debug.in;
358 == Contributors =========================================================
359 Amir Kamil <kamil@cs.berkeley.edu>
360 Adam Megacz <megacz@cs.berkeley.edu>