== Fleeterpreter ====================================================
+static class BitStorage {
+ long[] bits;
+ int numbits = 0;
+ int start = 0;
+ BitStorage(int size) {
+ bits = new long[size / 64 + (size % 64 != 0 ? 1 : 0)];
+ }
+ int size() {
+ return numbits;
+ }
+ boolean hasSpace(int num) {
+ return bits.length * 64 - numbits >= num;
+ }
+ boolean peekTailBit() {
+ int entry = (((numbits-1) + start) / 64) % bits.length;
+ int off = ((numbits-1) + start) % 64;
+ int maxadd = 64 - off;
+ long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
+ return (bits[entry] & ~mask) != 0;
+ }
+ boolean add(long data, int num) {
+ if (!hasSpace(num)) return false;
+ int entry = ((numbits + start) / 64) % bits.length;
+ int off = (numbits + start) % 64;
+ int maxadd = 64 - off;
+ long mask = maxadd < 64 ? (-1L >>> maxadd) : 0L;
+ bits[entry] = (bits[entry] & mask) | (data << off);
+ if (num > maxadd) {
+ numbits += maxadd;
+ return add(data >>> maxadd, num - maxadd);
+ } else {
+ numbits += num;
+ return true;
+ }
+ }
+ long get(int num) {
+ assert size() >= num : "too few bits in storage";
+ int entry = start / 64;
+ int off = start % 64;
+ int max = 64 - off;
+ int n = num > max ? max : num;
+ long mask = n > 0 ? (-1L >>> (64 - n)) : 0L;
+ long res = (bits[entry] >>> off) & mask;
+ int oldstart = start;
+ if (n < num) {
+ int n2 = num - n;
+ long mask2 = n2 > 0 ? (-1L >>> (64 - n2)) : 0L;
+ res |= (bits[(entry + 1) % bits.length] & mask2) << n;
+ }
+ start = (start + num) % (64 * bits.length);
+ numbits -= num;
+ return res;
+ }
+ int capacity() {
+ return 64 * bits.length;
+ }
+ // Test code for BitStorage
+ static void test3(String[] args) {
+ BitStorage bs = new BitStorage(37);
+ Random rand = new Random();
+ Vector ins = new Vector();
+ Vector ret = new Vector();
+ StringBuffer sbi = new StringBuffer();
+ StringBuffer sbr = new StringBuffer();
+ System.out.println("==== Test #3 ====");
+ System.out.println("inserting...");
+ long data = rand.nextLong();
+ bs.add(data, 0);
+ ins.add(new Integer(0));
+ data = rand.nextLong();
+ int num = rand.nextInt(37);
+ int s = bs.size();
+ bs.add(data, num);
+ assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
+ ins.add(new Integer(num));
+ add(sbi, data, num);
+ print(data, num);
+ System.out.println("\nretrieving...");
+ num = bs.size();
+ data = bs.get(num);
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ print(data, num);
+ System.out.println("\ninsertion sequence:");
+ for (int i = 0; i < ins.size(); i++) {
+ System.out.print(" " + ins.get(i));
+ }
+ System.out.println("\nretrieval sequence:");
+ for (int i = 0; i < ret.size(); i++) {
+ System.out.print(" " + ret.get(i));
+ }
+ System.out.println();
+ check(sbi, sbr);
+ }
+ static void test2(String[] args) {
+ int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
+ BitStorage bs = new BitStorage(37 * iters);
+ Random rand = new Random();
+ Vector ins = new Vector();
+ Vector ret = new Vector();
+ StringBuffer sbi = new StringBuffer();
+ StringBuffer sbr = new StringBuffer();
+ System.out.println("==== Test #2 ====");
+ for (int i = 0; i < iters; i++) {
+ long data = rand.nextLong();
+ int num = rand.nextInt(37);
+ int s = bs.size();
+ bs.add(data, num);
+ assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
+ ins.add(new Integer(num));
+ add(sbi, data, num);
+ num = rand.nextInt(Math.min(37, bs.size()));
+ s = bs.size();
+ data = bs.get(num);
+ assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ }
+ //for (int i = 0; i < iters; i++) {
+ while (bs.size() > 0) {
+ int num = Math.min(rand.nextInt(37), bs.size());
+ //int num = Math.min(33, bs.size());
+ int s = bs.size();
+ long data = bs.get(num);
+ assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ }
+ System.out.println("inserted:");
+ System.out.println(sbi);
+ System.out.println("retrieved:");
+ System.out.println(sbr);
+ System.out.println("insertion sequence:");
+ for (int i = 0; i < ins.size(); i++) {
+ System.out.print(" " + ins.get(i));
+ }
+ System.out.println("\nretrieval sequence:");
+ for (int i = 0; i < ret.size(); i++) {
+ System.out.print(" " + ret.get(i));
+ }
+ System.out.println();
+ check(sbi, sbr);
+ }
+ static void test1(String[] args) {
+ int iters = (args.length > 0 ? Integer.parseInt(args[0]) : 10);
+ BitStorage bs = new BitStorage(37 * iters);
+ Random rand = new Random();
+ Vector ins = new Vector();
+ Vector ret = new Vector();
+ StringBuffer sbi = new StringBuffer();
+ StringBuffer sbr = new StringBuffer();
+ System.out.println("==== Test #1 ====");
+ System.out.println("inserting...");
+ for (int i = 0; i < iters; i++) {
+ long data = rand.nextLong();
+ int num = rand.nextInt(37);
+ int s = bs.size();
+ bs.add(data, num);
+ assert bs.size() - s == num : "bad size: " + s + " + " + num + " != " + bs.size();
+ ins.add(new Integer(num));
+ add(sbi, data, num);
+ print(data, num);
+ }
+ System.out.println("\nretrieving...");
+ //for (int i = 0; i < iters; i++) {
+ while (bs.size() > 0) {
+ int num = Math.min(rand.nextInt(37), bs.size());
+ //int num = Math.min(33, bs.size());
+ int s = bs.size();
+ long data = bs.get(num);
+ assert s - bs.size() == num : "bad size: " + s + " - " + num + " != " + bs.size();
+ ret.add(new Integer(num));
+ add(sbr, data, num);
+ print(data, num);
+ }
+ System.out.println("\ninsertion sequence:");
+ for (int i = 0; i < ins.size(); i++) {
+ System.out.print(" " + ins.get(i));
+ }
+ System.out.println("\nretrieval sequence:");
+ for (int i = 0; i < ret.size(); i++) {
+ System.out.print(" " + ret.get(i));
+ }
+ System.out.println();
+ check(sbi, sbr);
+ }
+ static void print(long data, int num) {
+ for (int i = 0; i < num; i++) {
+ System.out.print((data >>> i) & 0x1);
+ }
+ }
+ static void add(StringBuffer sb, long data, int num) {
+ for (int i = 0; i < num; i++) {
+ sb.append((int) ((data >>> i) & 0x1));
+ }
+ }
+ static void check(StringBuffer sb1, StringBuffer sb2) {
+ int len = sb2.length();
+ if (len > sb1.length()) {
+ System.out.println("error: retrieval sequence is longer than insertion sequence");
+ len = sb1.length();
+ }
+ for (int i = 0; i < sb2.length(); i++) {
+ if (sb1.charAt(i) != sb2.charAt(i)) {
+ System.out.println("error: bit at position " + i + " does not match");
+ }
+ }
+ }
+}
boolean mode = false;
-BitFifo.BitStorage outBits = new BitFifo.BitStorage(74);
+BitStorage outBits = new BitStorage(74);
public void service() {
if (outBits.size() >= 37) {
if (box_outBits.readyForDataFromShip()) {
== FPGA ==============================================================
- reg mode; initial mode = 0;
- reg have_in1; initial have_in1 = 0;
- reg have_in2; initial have_in2 = 0;
- reg have_in3; initial have_in3 = 0;
- reg [(`DATAWIDTH-1):0] keep_in1; initial keep_in1 = 0;
- reg [(`DATAWIDTH-1):0] keep_in2; initial keep_in2 = 0;
- reg [(`DATAWIDTH-1):0] keep_in3; initial keep_in3 = 0;
- reg have_out1; initial have_out1 = 0;
- reg have_out2; initial have_out2 = 0;
- reg [73:0] bitstorage; initial bitstorage = 0;
+ reg [73:0] bitstorage; initial bitstorage = 0;
reg [7:0] bitstorage_count; initial bitstorage_count = 0;
- reg wrote; initial wrote = 0;
always @(posedge clk) begin
- wrote = 0;
- if (bitstorage_count >= `DATAWIDTH) begin
- outBits_d = bitstorage[(`DATAWIDTH-1):0];
- `onwrite(outBits_r, outBits_a)
- bitstorage_count <= 0;
- bitstorage = bitstorage >> `DATAWIDTH;
- end
- end else if (have_out1) begin
- `onwrite(out1_r, out1_a) have_out1 <= 0; end
- end else if (have_out2) begin
- `onwrite(out2_r, out2_a) have_out2 <= 0; end
- end else if (!have_in1) begin
- `onread(in1_r, in1_a) have_in1 <= 1; keep_in1 <= in1_d; end
- end else if (!have_in2) begin
- `onread(in2_r, in2_a) have_in2 <= 1; keep_in2 <= in2_d; end
- end else if (!have_in3) begin
- `onread(in3_r, in3_a) have_in3 <= 1; keep_in3 <= in3_d; end
+ if (!rst) begin
+ `reset
+ bitstorage <= 0;
+ bitstorage_count <= 0;
end else begin
- out1_d <= { ((keep_in1 & keep_in2) | (keep_in2 & keep_in3) | (keep_in1 & keep_in3)) };
- out2_d <= { 1'b0, (keep_in1[(`DATAWIDTH-1):1] ^
- keep_in2[(`DATAWIDTH-1):1] ^
- keep_in3[(`DATAWIDTH-1):1]) };
- bitstorage[bitstorage_count] = (keep_in1[0] ^ keep_in2[0] ^ keep_in3[0]);
+ if (out1_r && out1_a) out1_r <= 0;
+ if (out2_r && out2_a) out2_r <= 0;
+ if (outBits_r && outBits_a) outBits_r <= 0;
+ if (!in1_r && in1_a) in1_a <= 0;
+ if (!in2_r && in2_a) in2_a <= 0;
+ if (!in3_r && in3_a) in3_a <= 0;
+ if (!out1_r && !out2_r && !outBits_r && in1_r && in2_r && in3_r) begin
+ out1_d <= { ((in1_d & in2_d)
+ | (in2_d & in3_d)
+ | (in1_d & in3_d)) };
+ out2_d <= { 1'b0, (in1_d[(`DATAWIDTH-1):1] ^
+ in2_d[(`DATAWIDTH-1):1] ^
+ in3_d[(`DATAWIDTH-1):1]) };
+ if (bitstorage_count >= `DATAWIDTH-1) begin
+ outBits_d <= bitstorage[(`DATAWIDTH-1):0];
+ outBits_r <= 1;
+ bitstorage_count <= 0;
+ bitstorage <= bitstorage >> `DATAWIDTH;
+ end
+ bitstorage[bitstorage_count] <= (in1_d[0] ^ in2_d[0] ^ in3_d[0]);
bitstorage_count <= bitstorage_count+1;
- have_out1 <= 1;
- have_out2 <= 1;
- have_in1 <= 0;
- have_in2 <= 0;
- have_in3 <= 0;
+ out1_r <= 1;
+ out2_r <= 1;
+ in1_a <= 1;
+ in2_a <= 1;
+ in3_a <= 1;
+ end
end
-
end
#skip
#ship alu3 : Alu3
#ship lut3 : Lut3
-#ship bitfifo : BitFifo
#ship debug : Debug
#ship fifo : Fifo
+#ship rotator : Rotator
-#expect -66848683
-#expect 18682
+#expect 0
+#expect 2
+#expect 1
// 0: 100100100111110000000
// sel 011110100001001000000
// 1: 111000101000011000011
// r: 111000100110111000000
-bitfifo.in:
- deliver; // deliver a junk word
- literal 10000;
- [37] deliver; // deliver it 37 times (once per bit)
- literal 0;
- [38] deliver; // deliver it 37 times
-
-// insert bits in lsb order
-bitfifo.inOp:
- literal BitFifo.inOp[lsbFirst,take=37];
- [*] deliver;
-
-// toss out 37 bits, take one, repeat. sign extend the result
-bitfifo.outOp:
- literal BitFifo.outOp[drop=37,take=1,signExtend];
- [*] deliver;
-
-bitfifo.out: [*] wait, take, sendto lut3.in2;
-lut3.in2: [4] notify bitfifo.out;
- [74] take, deliver, notify bitfifo.out;
-
-// mux on second input
-lut3.inLut: literal 226;
- [74] deliver;
-
-lut3.in1: literal 18683;
- [37] deliver;
- literal 0;
- [37] deliver;
-
-lut3.in3: literal 12000;
- [37] deliver;
- literal 0;
- [37] deliver;
-
-lut3.out: [*] wait, take, sendto alu3.in2;
-
-alu3.in1: literal 0; deliver; [*] take, deliver;
-alu3.in2: [1] notify lut3.out; [*] take, deliver, notify lut3.out;
-alu3.in3: literal 0; deliver; [*] take, deliver;
-alu3.out1: [74] take, sendto alu3.in1;
-alu3.out2: [74] take, sendto alu3.in3;
-alu3.outBits: [*] take, sendto debug.in;
+alu3.in1: literal 1; deliver; load repeat counter with 36; deliver;
+alu3.in2: literal 0; deliver; literal 1; load repeat counter with 36; deliver;
+alu3.in3: literal 4; deliver; load repeat counter with 36; deliver;
+alu3.out1: take; sendto debug.in; [*] take;
+alu3.out2: take; wait; sendto debug.in; [*] take;
+alu3.outBits: take; wait; sendto debug.in;
-debug.in: [*] take, deliver;
+debug.in:
+ take, deliver;
+ notify alu3.out2;
+ take, deliver;
+ notify alu3.outBits;
+ take, deliver;
== Contributors =========================================================