partial implementation of gen_demultiplexer

2 files changed, 160 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..022e5a0
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,4 @@
+CXX=g++ -std=c++11 -ggdb -Wall -Wextra
+LDFLAGS=-lgecodedriver -lgecodesearch -lgecodeminimodel -lgecodeint -lgecodekernel -lgecodesupport -lgecodegist
+
+all: gen_demultiplexer
diff --git a/gen_demultiplexer.cpp b/gen_demultiplexer.cpp
new file mode 100644
index 0000000..edf4acd
--- /dev/null
+++ b/gen_demultiplexer.cpp
@@ -0,0 +1,156 @@
+#include <array>
+#include <map>
+#include <string>
+
+
+#include <gecode/driver.hh>
+#include <gecode/int.hh>
+#include <gecode/gist.hh>
+#include <gecode/minimodel.hh>
+
+using namespace std;
+using namespace Gecode;
+
+string S() {
+  return "";
+}
+
+template<typename T, typename... Ts>
+string S(T v, Ts... vs) {
+  stringstream ss;
+  ss << v << S(vs...);
+  return ss.str();
+}
+
+struct Op {
+  string inst;
+  IntVar *v;
+  int delay;
+};
+
+struct Demultiplexer : public Space {
+  
+  IntVarArray op_times;
+  array<Op, 17> ops;
+  uint opCount;
+
+  Demultiplexer(vector<bool> bits) 
+    : op_times(*this, 17, 0, 16)
+  {
+    /// post the problem (the instructions and their temporal
+    /// dependencies)
+
+    // only one op per time slice
+    distinct(*this, op_times);
+
+    // the final jump
+    auto &jump = op(2, "  ijmp");
+    at(jump, 15);
+
+    // rising flanks
+    for (uint i=0; i<bits.size(); i++) {
+      auto &rise = op(1, S("  out %", i, ", 1"));
+      auto &fall = op(1, S("  out %", i, ", 0"));
+      if (bits[i]) { after(rise, fall, 4, 6 ); }
+      else         { after(rise, fall, 8, 13); }
+      after(fall, jump);
+      at(rise, i);
+    }
+
+    // load next jump location
+    after(op(2, "  ld %ZH, %[data_ptr]+"), jump);
+
+    // add nops until we have enough instructions to fill the time
+    // slice
+    while (opCount < ops.size())
+      op(1, "  nop");
+
+    /// branching
+    branch(*this, op_times, INT_VAR_SIZE_MIN, INT_VAL_MIN);
+  }
+
+  Op& op(int delay, string inst) {
+    Op &o = ops[opCount];
+    o.inst  = inst;
+    o.v     = &(op_times[opCount]);
+    o.delay = delay;
+    opCount++;
+
+    // add pseudo-op to encode instructions that take more than one
+    // cycle
+    if (delay > 1) {
+      auto nextOp = op(delay - 1, "; 1 clock cycle delay");
+      rel(*this, *(o.v) + 1 == *(nextOp.v));
+    }
+   
+    return o;
+  }
+
+  /// helper for constraint formulation
+
+  void after(Op& pre, Op& post, int delay_min=0, int delay_max=-1) {
+    rel(*this, *(pre.v) + pre.delay + delay_min <= *(post.v));
+    if (delay_max >= 0)
+      rel(*this, *(pre.v) + pre.delay + delay_max >= *(post.v));
+  }
+
+  void at(Op& op, int time_min, int time_max=-1) {
+    if (time_max == -1)
+      time_max = time_min;
+    rel(*this, *(op.v) >= time_min);
+    rel(*this, *(op.v) <= time_max);
+  }
+
+  /// return resulting instruction stream
+
+  string print() {
+    stringstream ss;
+    print(ss, false);
+    return ss.str();
+  }
+
+  /// gecode boilerplate
+  Demultiplexer(bool share, Demultiplexer &o)
+    : Space(share, o),
+      ops(o.ops),
+      opCount(o.opCount)
+  {
+    op_times.update(*this, share, o.op_times);
+  }
+
+  virtual Space* copy(bool share) {
+    return new Demultiplexer(share, *this);
+  }
+
+  void print(ostream &o, bool printTimes=true) const {
+    multimap<int, int> timedOps;
+    for (uint i=0; i<ops.size(); i++)
+      timedOps.insert(make_pair(op_times[i].min(), i));
+    for (auto i : timedOps) {
+      auto &op = ops[i.second];
+      o << op.inst;
+      if (printTimes)
+	o << "\t; " << *(op.v);
+      o << endl;
+    }
+  }
+};
+
+int main(int argc, char **argv) {
+  Demultiplexer *d = new Demultiplexer({0,1,0,1,0});
+
+  // Gist::Print<Demultiplexer> gp("print solution");
+  // Gist::Options go;
+  // go.inspect.click(&gp);
+  // Gist::dfs(d, go);
+
+  DFS<Demultiplexer> e(d);
+  delete d;
+  d = e.next();
+  if (d) {
+    cout << d->print();
+    delete d;
+  }else{
+    cerr << "no instruction sequence found";
+  }
+}