1 files changed, 35 insertions, 26 deletions

diff --git a/cacount.cpp b/cacount.cpp
index 27e25ae..368e325 100644
--- a/cacount.cpp
+++ b/cacount.cpp
@@ -42,8 +42,21 @@ State update(State s) {
   return r;
 }
 
-typedef array<State,   numState> Trans;
-typedef array<uint8_t, numState> pbitset;
+State canonize(State s) {
+  State cs = s;
+  for (int i=0; i<logState; i++)
+    cs = min<State>(cs, (((s<<i) | (s>>(logState-i))) & maxState));
+  return cs;
+};
+
+StateIter acanonize(State s) {
+  StateIter cs = canonize(s);
+  return (cs << 1) | ((StateIter(s) == cs) ? 0 : 1);
+}
+
+typedef array<State,     numState> Trans;
+typedef array<StateIter, numState> Color;
+typedef array<uint8_t,   numState> pbitset;
 
 bool iterStateP(function<void(State, bool&)> f, optional<string> msg = optional<string>(), bool parallel = false, bool skipWorkTest = false) {
   PerfPrinter perfPrinter(msg);
@@ -85,15 +98,15 @@ void iterTrans(int times, function<void(State)> f, optional<string> msg = option
   iterTransP(times, [=](State s, bool &) { f(s); }, msg, parallel, true);
 }
 
-void init(Trans &t, Trans &c, pbitset &reachable) {
+void init(Trans &t, Color &c, pbitset &reachable) {
   iterState([&](State s) {
       t[s] = update(s);
-      c[s] = s;
+      c[s] = acanonize(s);
       reachable[t[s]] = 1;
     }, (string) "single step transition table", true);
 }
 
-void findCycle(Trans &t, Trans &c) {
+void findCycle(Trans &t, Color &c) {
   // forward to t=numState; now every state is in a cycle
   iterTransP(logState, [&](State s, bool &worked) {
       State n = t[s];
@@ -110,15 +123,7 @@ void findCycle(Trans &t, Trans &c) {
     }, (string) "fix transient cycle id", true);
 }
 
-State canonize(State s) {
-  // TODO: test if a variant base on clz is faster
-  State cs = s;
-  for (int i=0; i<logState; i++)
-    cs = min<State>(cs, (((s<<i) | (s>>(logState-i))) & maxState));
-  return cs;
-};
-
-void cycleStat(Trans &t, Trans &c, pbitset &reachable) {
+void cycleStat(Trans &t, Color &c, pbitset &reachable) {
   struct Stat {
     StateIter basin, len, eden, totalBasin;
     explicit Stat() : basin(0), len(0), eden(0), totalBasin(0) {}
@@ -131,11 +136,12 @@ void cycleStat(Trans &t, Trans &c, pbitset &reachable) {
   // How many garden of eden states does it contain?
   { PerfPrinter perfPrinter((string) "cycle count");
   iterState([&](State s) {
-    auto cyc = c[s];
-    auto canonCyc = canonize(cyc);
-    auto &stat = cycStat[canonCyc];
+    auto lcyc = c[s];
+    auto cyc = lcyc >> 1;
+    auto isCanon = (lcyc & 1) == 0;
+    auto &stat = cycStat[cyc];
     stat.totalBasin++;
-    if (cyc == canonCyc) {
+    if (isCanon) {
       stat.basin++;
       if (!reachable[s])
 	stat.eden++;
@@ -156,15 +162,17 @@ void cycleStat(Trans &t, Trans &c, pbitset &reachable) {
   }}
 
   // print it
+  cerr << "\nelement\tdup\tc-len\tbasin\teden\telement" << endl;
   for (auto &i : cycStat) {
     auto &s = i.second;
     assert(s.totalBasin % s.basin == 0);
     cout << bitset<logState>(i.first) << "\t"
-	 << (s.totalBasin / s.basin) << "\t"
-	 << s.len << "\t"
-	 << s.basin << "\t"
-	 << s.eden  << "\t"
-	 << i.first << endl;
+	 << (uint64_t) (s.totalBasin / s.basin) << "\t"
+	 << (uint64_t) s.len << "\t"
+	 << (uint64_t) s.basin << "\t"
+	 << (uint64_t) s.eden  << "\t"
+	 << (uint64_t) i.first << "\t"
+	 << endl;
   }
 }
 
@@ -175,7 +183,7 @@ void print(Trans &t) {
 
 void printTraj(State s, int count) {
   while (count--) {
-    cout << bitset<logState>(s) << endl;
+    cout << bitset<logState>(s) << " " << (uint64_t) s << "\t" << (uint64_t) canonize(s) << endl;
     s = update(s);
   }
 }
@@ -188,11 +196,12 @@ int main(int argc, char **argv) {
     printTraj(atoi(argv[3]), atoi(argv[4]));
   }
   if (!strcmp(argv[2], "cycle")) {
-    Trans *t, *c;
+    Trans *t;
+    Color *c;
     pbitset *r;
     { PerfPrinter perfPrinter((string) "allocating memory");
       t = mmalloc<Trans>();
-      c = mmalloc<Trans>();
+      c = mmalloc<Color>();
       r = mmalloc<pbitset>();
     }
     init(*t, *c, *r);