diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | include/salticidae/ref.h | 1 | ||||
| -rw-r--r-- | include/salticidae/stream.h | 66 | ||||
| -rw-r--r-- | include/salticidae/type.h | 17 | ||||
| -rw-r--r-- | test/.gitignore | 1 | ||||
| -rw-r--r-- | test/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | test/test_stream.cpp | 79 |
7 files changed, 149 insertions, 19 deletions
@@ -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; +} |