From b5fb5c3fbd78684f1b686b21a3bad6aac80f2dc0 Mon Sep 17 00:00:00 2001
From: Jan Huwald <jh@sotun.de>
Date: Thu, 27 Nov 2014 23:44:19 +0100
Subject: find optimal solution, fix timing information from spec, make bit
 width a param, print solution asm


diff --git a/gen_demultiplexer.cpp b/gen_demultiplexer.cpp
index edf4acd..d554c7f 100644
--- a/gen_demultiplexer.cpp
+++ b/gen_demultiplexer.cpp
@@ -1,7 +1,10 @@
 #include <array>
 #include <map>
+#include <set>
 #include <string>
 
+#include <boost/dynamic_bitset.hpp>
+#include <boost/lexical_cast.hpp>
 
 #include <gecode/driver.hh>
 #include <gecode/int.hh>
@@ -10,6 +13,8 @@
 
 using namespace std;
 using namespace Gecode;
+using boost::dynamic_bitset;
+using boost::lexical_cast;
 
 string S() {
   return "";
@@ -28,14 +33,18 @@ struct Op {
   int delay;
 };
 
-struct Demultiplexer : public Space {
-  
+struct Demultiplexer : public MinimizeScript {
   IntVarArray op_times;
+  IntVarArray timeDistortions;
+  IntVar maxTimeDistortion;
   array<Op, 17> ops;
   uint opCount;
 
-  Demultiplexer(vector<bool> bits) 
-    : op_times(*this, 17, 0, 16)
+  Demultiplexer(dynamic_bitset<> bits)
+    : op_times(*this, 17, 0, 16),
+      timeDistortions(*this, bits.size(), 0, 170),
+      maxTimeDistortion(*this, 0, 170),
+      opCount(0)
   {
     /// post the problem (the instructions and their temporal
     /// dependencies)
@@ -51,12 +60,18 @@ struct Demultiplexer : public Space {
     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); }
+      int optTime;
+      if (bits[i]) { after(rise, fall, 8, 12); optTime = 112; }
+      else         { after(rise, fall, 3, 6 ); optTime = 56;  }
       after(fall, jump);
       at(rise, i);
+
+      rel(*this, abs((*(fall.v) - *(rise.v)) * 10 - optTime) == timeDistortions[i]);
     }
 
+    // track the worst time distortion
+    max(*this, timeDistortions, maxTimeDistortion);
+
     // load next jump location
     after(op(2, "  ld %ZH, %[data_ptr]+"), jump);
 
@@ -69,7 +84,12 @@ struct Demultiplexer : public Space {
     branch(*this, op_times, INT_VAR_SIZE_MIN, INT_VAL_MIN);
   }
 
+  IntVar cost() const {
+    return maxTimeDistortion;
+  }
+
   Op& op(int delay, string inst) {
+    assert(opCount < ops.size());
     Op &o = ops[opCount];
     o.inst  = inst;
     o.v     = &(op_times[opCount]);
@@ -111,11 +131,13 @@ struct Demultiplexer : public Space {
 
   /// gecode boilerplate
   Demultiplexer(bool share, Demultiplexer &o)
-    : Space(share, o),
+    : MinimizeScript(share, o),
       ops(o.ops),
       opCount(o.opCount)
   {
-    op_times.update(*this, share, o.op_times);
+    op_times         .update(*this, share, o.op_times         );
+    timeDistortions  .update(*this, share, o.timeDistortions  );
+    maxTimeDistortion.update(*this, share, o.maxTimeDistortion);
   }
 
   virtual Space* copy(bool share) {
@@ -136,21 +158,69 @@ struct Demultiplexer : public Space {
   }
 };
 
+void printDev(double dev) {
+  cout << int(ceil(dev * 1000 / 160))
+       << " ns (" << dev / 10 << " cycles)" << 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";
+  if (argc != 2) {
+    cout << "Usage:\n" << argv[0] << " number-of-channels" << endl;
+    return 1;
   }
+
+  auto bits = lexical_cast<uint>(argv[1]);
+  set<dynamic_bitset<>> noSolutions;
+  double maxDev{0};
+
+  // find the optimal solution (legal instruction sequence with
+  // minimal deviation from WS2812 specs central delay value)
+  for (uint i=0; i < uint(1)<<bits; i++) {
+    dynamic_bitset<> pattern(bits, i);
+    Demultiplexer init(pattern),
+      *best = nullptr, *cur;
+
+    BAB<Demultiplexer> search(&init);
+    while (cur = search.next()) {
+      if (best) delete best;
+      best = cur;
+    }
+    if (best) {
+      auto dev = double(best->cost().min());
+      maxDev = max(maxDev, dev);
+
+      cout << ".ws2812_mux" << bits << "_pat" << pattern << ":\n; max. time deviation: ";
+      printDev(dev);
+      cout << "; ind. deviations: " << best->timeDistortions << " (decicycles)\n";
+      best->print(cout, false);
+      cout << endl;
+
+      delete best;
+    }else{
+      noSolutions.insert(pattern);
+    }
+  }
+
+  // terminate if not all solutions have been found
+  if (!noSolutions.empty()) {
+    cerr << "No solutions found for:\n";
+    for (auto p : noSolutions)
+      cerr << "  " << p << endl;
+    cerr << "Total: no solution for " << noSolutions.size()
+	 << " of " << (1<<bits) << endl;
+    return 1;
+  }
+
+
+  // print jump table
+  cout << ".ws2812_mux" << bits << "_jt:\n";
+  for (uint i=0; i < uint(1)<<bits; i++)
+    cout << "  jmp .ws2812_mux" << bits << "_pat" << dynamic_bitset<>(bits, i) << endl;
+
+  // print statistics
+  cout << ";\n; Maximal deviation of all patterns: ";
+  printDev(maxDev);
+
+
+  return 0;
 }
-- 
cgit v0.10.1