aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDeterminant <[email protected]>2018-07-13 14:35:03 -0400
committerDeterminant <[email protected]>2018-07-13 14:35:03 -0400
commitd8e500b2d785b6c8e12ceb25efe68c32aad46a8b (patch)
treeb91a58b9e6e112f32c23d9aee866631131bf4fd6
parentb98265d732bad274f66de66cb93d891e9c41a112 (diff)
finish Bits impl
-rw-r--r--.gitignore1
-rw-r--r--include/salticidae/ref.h1
-rw-r--r--include/salticidae/stream.h66
-rw-r--r--include/salticidae/type.h17
-rw-r--r--test/.gitignore1
-rw-r--r--test/CMakeLists.txt3
-rw-r--r--test/test_stream.cpp79
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;
+}