path: root/gen_demultiplexer.cpp

#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>
#include <gecode/gist.hh>
#include <gecode/minimodel.hh>

using namespace std;
using namespace Gecode;
using boost::dynamic_bitset;
using boost::lexical_cast;

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 MinimizeScript {
  IntVarArray op_times;
  IntVarArray timeDistortions;
  IntVar maxTimeDistortion;
  array<Op, 17> ops;
  uint opCount;

  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)

    // 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"));
      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);

    // 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);
  }

  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]);
    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)
    : MinimizeScript(share, o),
      ops(o.ops),
      opCount(o.opCount)
  {
    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) {
    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;
    }
  }
};

void printDev(double dev) {
  cout << int(ceil(dev * 1000 / 160))
       << " ns (" << dev / 10 << " cycles)" << endl;
}

int main(int argc, char **argv) {
  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;
}