From d4faafd820a54955fa3946ddcb42a9df261fc997 Mon Sep 17 00:00:00 2001 From: Amir Kamil Date: Fri, 15 Jun 2007 07:08:18 +0100 Subject: [PATCH] BitFifo ship --- ships/BitFifo.ship | 240 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 240 insertions(+) create mode 100644 ships/BitFifo.ship diff --git a/ships/BitFifo.ship b/ships/BitFifo.ship new file mode 100644 index 0000000..1373b36 --- /dev/null +++ b/ships/BitFifo.ship @@ -0,0 +1,240 @@ +ship: BitFifo + +== Ports =========================================================== +data in: in + +data in: cmd.drop +data in: cmd.dropInv +data in: cmd.takeFillZeros +data in: cmd.takeInvFillZeros +data in: cmd.takeFillOnes +data in: cmd.takeInvFillOnes +data in: cmd.takeSignExtend +data in: cmd.takeInvSignExtend + +data out: out + +== Constants ======================================================== + +== TeX ============================================================== + +== Fleeterpreter ==================================================== +// Internal storage +private 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 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; + bits[entry] = (bits[entry] & (-1L >>> maxadd)) | (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 res = (bits[entry] >>> off) & (-1L >>> (64 - n)); + int oldstart = start; + if (n < num) { + int n2 = num - n; + res |= (bits[(entry + 1) % bits.length] & (-1L >>> (64 - n2))) << n; + } + start = (start + num) % (64 * bits.length); + numbits -= num; + return res; + } + int capacity() { + return 64 * bits.length; + } + // Test code for BitStorage + 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"); + } + } + } +} + +// Run BitStorage tests +public static void main(String[] args) { + BitStorage.test1(args); + BitStorage.test2(args); +} + +// Ship implementation +private Packet selector; +private static final int MAXBITS = 128; +private static final int WORDSIZE = 37; +private BitStorage bits = new BitStorage(MAXBITS); + +public void service() { + if (!box_out.readyForDataFromShip() && !box_in.dataReadyForShip()) return; + if (box_in.dataReadyForShip() && bits.hasSpace(WORDSIZE)) { + long data = box_in.removeDataForShip(); + bits.add(data, WORDSIZE); + } + if (selector == null && !box_cmd.dataReadyForShip()) return; + if (selector == null) selector = box_cmd.removePacketForShip(); + + String port = selector.destination.getDestinationName(); + long val = selector.value; // check if <= 37? + + if (port.startsWith("takeInv") || port.startsWith("dropInv")) { + val = 37 - val; + } + if (val < bits.size()) { + return; + } + + if (port.startsWith("take")) { + if (!box_out.readyForDataFromShip()) return; + long data = bits.get((int) val); + if (port.endsWith("FillOnes")) { + data |= (-1L << val); + } else if (port.endsWith("SignExtend")) { + data = (data << (64 - val)) >> (64 - val); + } + box_out.addDataFromShip(data); + selector = null; + return; + } else { + bits.get((int) val); + selector = null; + return; + } +} + +== FleetSim ============================================================== + +== FPGA ============================================================== + +== Contributors ========================================================= +Amir Kamil -- 1.7.10.4