finish Bits impl

7 files changed, 149 insertions, 19 deletions

diff --git a/.gitignore b/.gitignore
index 475a195..0b0d2ec 100644
--- a/.gitignore
+++ b/.gitignore
@@ -14,3 +14,4 @@ src/*.swp
 *.so
 *.gch
 /Makefile
+core
diff --git a/include/salticidae/ref.h b/include/salticidae/ref.h
index c0b77a3..7239402 100644
--- a/include/salticidae/ref.h
+++ b/include/salticidae/ref.h
@@ -131,6 +131,7 @@ class BoxObj<T[], D>: public _BoxObj<T, D> {
     BoxObj(BoxObj<T_[]> &&other): base_t(std::move(other)) {}
 
     T &operator[](size_t idx) { return base_t::obj[idx]; }
+    const T &operator[] (size_t idx) const { return base_t::obj[idx]; }
 };
 
 template<typename T, typename D = default_delete<T>, typename T_, typename D_>
diff --git a/include/salticidae/stream.h b/include/salticidae/stream.h
index b5e0757..5b7e936 100644
--- a/include/salticidae/stream.h
+++ b/include/salticidae/stream.h
@@ -271,36 +271,36 @@ class Blob {
 };
 
 template<typename T = uint64_t>
-class Bits {
+class _Bits {
     using _impl_type = T;
-    static const size_t bit_per_datum = sizeof(_impl_type) * 8;
+    static const uint32_t bit_per_datum = sizeof(_impl_type) * 8;
+    static const uint32_t shift_per_datum = log2<bit_per_datum>::value;
     BoxObj<_impl_type[]> data;
-    size_t nbits;
-    size_t ndata;
+    uint32_t nbits;
+    uint32_t ndata;
 
     public:
 
-    Bits(): data(nullptr) {}
-    Bits(const bytearray_t &arr) {
+    _Bits(): data(nullptr) {}
+    _Bits(const bytearray_t &arr) {
         load(&*arr.begin(), arr.size());
     }
 
-    Bits(const uint8_t *arr, size_t len) { load(arr, len); }
-    Bits(size_t nbits): nbits(nbits) {
+    _Bits(const uint8_t *arr, uint32_t len) { load(arr, len); }
+    _Bits(uint32_t nbits): nbits(nbits) {
         ndata = (nbits + bit_per_datum - 1) / bit_per_datum;
         data = new _impl_type[ndata];
     }
 
-    ~Bits() {}
+    ~_Bits() {}
 
-    void load(const uint8_t *arr, size_t len) {
+    void load(const uint8_t *arr, uint32_t len) {
         nbits = len * 8;
-        ndata = (len + sizeof(_impl_type) - 1) /
-                        sizeof(_impl_type);
+        ndata = (nbits + bit_per_datum - 1) / bit_per_datum;
         data = new _impl_type[ndata];
 
         uint8_t *end = arr + len;
-        for (_impl_type *ptr = data; ptr < data + ndata;)
+        for (_impl_type *ptr = data.get(); ptr < data.get() + ndata;)
         {
             _impl_type x = 0;
             for (unsigned j = 0, k = 0; j < sizeof(_impl_type); j++, k += 8)
@@ -317,24 +317,24 @@ class Bits {
         s << htole(nbits);
         if (data)
         {
-            for (const _impl_type *ptr = data; ptr < data + ndata; ptr++)
+            for (const _impl_type *ptr = data.get(); ptr < data.get() + ndata; ptr++)
                 s << htole(*ptr);
         }
         else
         {
-            for (const _impl_type *ptr = data; ptr < data + ndata; ptr++)
+            for (const _impl_type *ptr = data.get(); ptr < data.get() + ndata; ptr++)
                 s << htole((_impl_type)0);
         }
     }
 
     void unserialize(DataStream &s) {
-        _impl_type x;
-        s >> x;
-        nbits = letoh(x);
+        s >> nbits;
+        nbits = letoh(nbits);
         ndata = (nbits + bit_per_datum - 1) / bit_per_datum;
         data = new _impl_type[ndata];
-        for (_impl_type *ptr = data; ptr < data + ndata; ptr++)
+        for (_impl_type *ptr = data.get(); ptr < data.get() + ndata; ptr++)
         {
+            _impl_type x;
             s >> x;
             *ptr = letoh(x);
         }
@@ -345,8 +345,36 @@ class Bits {
         s << *this;
         return std::move(s);
     }
+
+    uint8_t get(uint32_t idx) const {
+        return (data[idx >> shift_per_datum] >>
+                    (idx & (bit_per_datum - 1))) & 1;
+    }
+
+    void set(uint32_t idx) {
+        auto i = idx >> shift_per_datum;
+        auto pos = idx & (bit_per_datum - 1);
+        data[i] ^= ((data[i] >> pos) ^ 1) << pos;
+    }
+
+    void unset(uint32_t idx) {
+        auto i = idx >> shift_per_datum;
+        auto pos = idx & (bit_per_datum - 1);
+        data[i] ^= (data[i] >> pos) << pos;
+    }
+
+    void flip(uint32_t idx) {
+        auto i = idx >> shift_per_datum;
+        auto pos = idx & (bit_per_datum - 1);
+        data[i] ^= ((_impl_type)1) << pos;
+    }
+   
+    uint8_t operator[](uint32_t idx) const { return get(idx); }
+
+    uint32_t size() const { return nbits; }
 };
 
+using Bits = _Bits<>;
 
 const size_t ENT_HASH_LENGTH = 256 / 8;
 
diff --git a/include/salticidae/type.h b/include/salticidae/type.h
index d5834a5..13975a5 100644
--- a/include/salticidae/type.h
+++ b/include/salticidae/type.h
@@ -65,6 +65,23 @@ struct is_ranged<T,
     void_t<decltype(std::declval<T>().begin()),
             decltype(std::declval<T>().end())>> : std::true_type {};
 
+template<size_t N>
+struct log2 {
+    enum {
+        value = 1 + log2<N / 2>::value
+    };
+};
+
+template<>
+struct log2<0> {
+   enum { value = 0 };
+};
+
+template<>
+struct log2<1> {
+   enum { value = 0 };
+};
+
 }
 
 #endif
diff --git a/test/.gitignore b/test/.gitignore
index b308815..9b5c5f5 100644
--- a/test/.gitignore
+++ b/test/.gitignore
@@ -1,2 +1,3 @@
 test_msg
+test_stream
 Makefile
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 423229b..bedaaa3 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -22,3 +22,6 @@
 
 add_executable(test_msg test_msg.cpp)
 target_link_libraries(test_msg salticidae)
+
+add_executable(test_stream test_stream.cpp)
+target_link_libraries(test_stream salticidae)
diff --git a/test/test_stream.cpp b/test/test_stream.cpp
new file mode 100644
index 0000000..0e05146
--- /dev/null
+++ b/test/test_stream.cpp
@@ -0,0 +1,79 @@
+/**
+ * Copyright (c) 2018 Cornell University.
+ *
+ * Author: Ted Yin <[email protected]>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy of
+ * this software and associated documentation files (the "Software"), to deal in
+ * the Software without restriction, including without limitation the rights to
+ * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+ * of the Software, and to permit persons to whom the Software is furnished to do
+ * so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <vector>
+#include "salticidae/stream.h"
+
+using salticidae::DataStream;
+using salticidae::get_hash;
+using salticidae::get_hex;
+using salticidae::Bits;
+
+void print(const Bits &a, int n) {
+    for (int i = 0; i < n; i++)
+        printf("%d", a.get(i));
+    puts("");
+}
+
+int main() {
+    int n = 80;
+    Bits a(n);
+    for (int i = 0; i < n; i++)
+    {
+        a.set(i);
+        print(a, n);
+    }
+    for (int i = n - 1; i >= 0; i--)
+    {
+        a.unset(i);
+        print(a, n);
+    }
+    std::vector<int> idxs;
+    for (int i = 0; i < 1000; i++)
+    {
+        idxs.push_back(rand() % n);
+        a.flip(idxs.back());
+        print(a, n);
+    }
+    for (auto idx: idxs)
+    {
+        a.flip(idx);
+        print(a, n);
+    }
+    for (int i = 0; i < n; i++)
+        if (i & 1) a.set(i);
+    print(a, n);
+    for (int i = 0; i < n; i++)
+        if (i & 1) a.unset(i);
+        else a.set(i);
+    print(a, n);
+    printf("%s size: %d\n", get_hex(a).c_str(), a.size());
+    DataStream s;
+    s << a;
+    Bits b;
+    s >> b;
+    printf("%s\n", get_hex(b).c_str());
+    print(b, b.size());
+    return 0;
+}