2 files changed, 67 insertions, 5 deletions

diff --git a/cacount.cpp b/cacount.cpp
index 3cd755c..8590eb0 100644
--- a/cacount.cpp
+++ b/cacount.cpp
@@ -13,15 +13,17 @@
 
 #include <sys/mman.h>
 
+#include "packed_array.hpp"
+
 using namespace std;
 
 #ifndef BIT_WIDTH
 #define BIT_WIDTH 31
 #endif
 
-typedef uint32_t State;
+typedef uint64_t State;
 const State logState = BIT_WIDTH;
-const State maxState = 1 << logState;
+const State maxState = (State) 1 << logState;
 
 // # of bits of largest memory fetch issued; machine-specific; used to
 // garantue that sub-byte sized access of different threads never
@@ -40,12 +42,12 @@ State update(State s) {
   return r;
 }
 
-typedef array<State, maxState> Trans;
+typedef packed_array<State, maxState, BIT_WIDTH> Trans;
 
 void iterState(function<void(int)> f, bool parallel = false) {
   int numThreads=1;
   if (parallel) {
-    numThreads = min(thread::hardware_concurrency(),
+    numThreads = min((State) thread::hardware_concurrency(),
 		     maxState / maxWordSize);
   }
   list<thread*> tasks;
@@ -87,7 +89,7 @@ void findCycle(Trans &t, Trans &c, bitset<maxState> &reachable) {
   iterState([&](int s) { 
       c[s] = t[s]; }, true);
   iterTrans(logState, [&](int s) {
-      c[s] = min(c[s], c[t[s]]);
+      c[s] = min<State>(c[s], c[t[s]]);
       t[s] = t[t[s]]; }, (char*) "cycles: ");
 }
 
diff --git a/packed_array.hpp b/packed_array.hpp
new file mode 100644
index 0000000..9fb2c59
--- /dev/null
+++ b/packed_array.hpp
@@ -0,0 +1,60 @@
+#pragma once
+
+#include <inttypes.h>
+#include <sys/types.h>
+
+template<typename T> struct bit_size;
+
+template<typename T, size_t count, size_t bit_sz = bit_size<T>::size>
+struct packed_array {
+  typedef packed_array<T, count, bit_sz> packed_array_t;
+  typedef uint64_t word_t;
+  const size_t word_sz = 8 * sizeof(word_t);
+  uint8_t data[(count * bit_sz + 7) / 8];
+
+  /// element access
+
+  struct element {
+    element(word_t *base, uint shift) : base(base), shift(shift) {}
+
+    T operator= (T val) {
+      word_t mask = ~(((((word_t) 1) << bit_sz) - 1) << shift);
+      *base &= mask;
+      *base ^= val << shift;
+      return val;
+    }
+
+    operator T() {
+      word_t mask = (((((word_t) 1) << bit_sz) - 1) << shift);
+      return static_cast<T>((*base & mask) >> shift);
+    }
+
+    T operator() () {
+      return (T) (*this);
+    }
+
+    word_t *base;
+    uint shift;
+  };
+
+  element operator[] (size_t i) {
+    size_t bit_addr = i * bit_sz;
+    return element((word_t*) (data + (bit_addr / 8)),
+		   bit_addr % 8);
+  }
+
+  /// simple iteration (for for-all loops)
+
+  struct iterator {
+    packed_array_t &a;
+    size_t i;
+
+    iterator(packed_array_t &a, size_t i) : a(a), i(i) {}
+    iterator& operator++() { ++i; return *this; }
+    element operator*() { return a[i]; }
+    bool operator != (iterator &o) { return (i != o.i) && (&a != &(o.a)); }
+  };
+
+  iterator begin() { return iterator(*this, 0);     }
+  iterator end()   { return iterator(*this, count); }
+};