go to 64-bit State, use bit-packed array

1 files changed, 60 insertions, 0 deletions

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