From ac65326242af579d6e1a7bd71730f1c78c8bde9b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 19 Aug 2018 18:22:26 +0200 Subject: Reorganize headers to make a clear public/private distinction --- chilbert/detail/MultiBitVec.hpp | 383 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 383 insertions(+) create mode 100644 chilbert/detail/MultiBitVec.hpp (limited to 'chilbert/detail/MultiBitVec.hpp') diff --git a/chilbert/detail/MultiBitVec.hpp b/chilbert/detail/MultiBitVec.hpp new file mode 100644 index 0000000..4bf5085 --- /dev/null +++ b/chilbert/detail/MultiBitVec.hpp @@ -0,0 +1,383 @@ +/* + Copyright (C) 2018 David Robillard + Copyright (C) 2006-2007 Chris Hamilton + + This program is free software: you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free Software + Foundation, either version 2 of the License, or (at your option) any later + version. + + This program is distributed in the hope that it will be useful, but WITHOUT + ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + details. + + You should have received a copy of the GNU General Public License along with + this program. If not, see . +*/ + +#ifndef CHILBERT_MULTIBITVEC_HPP +#define CHILBERT_MULTIBITVEC_HPP + +#include "chilbert/detail/BitVecIndex.hpp" +#include "chilbert/detail/BitVecIterator.hpp" +#include "chilbert/detail/BitVecMask.hpp" +#include "chilbert/detail/operations.hpp" + +#include +#include +#include +#include + +namespace chilbert { +namespace detail { + +template +class MultiBitVec +{ +public: + using Rack = uintptr_t; + using Mask = BitVecMask; + + using iterator = BitVecIterator>; + using const_iterator = ConstBitVecIterator>; + + static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; + + /// Return the value of the bit covered by `mask` + bool test(const Mask mask) const { return rack(mask.rack) & mask.mask; } + + /// Return the value of the `index`th bit + bool test(const size_t index) const { return test(mask(index)); } + + /// Set all bits to one + Derived& set() + { + if (size()) { + memset(data(), 0xFF, data_size()); + self()->truncate(); + } + + return *self(); + } + + /// Set the bit covered by `mask` to 1 + Derived& set(const Mask mask) + { + rack(mask.rack) |= mask.mask; + return *self(); + } + + /// Set the `index`th bit to 1 + Derived& set(const size_t index) { return set(mask(index)); } + + /// Set the bit covered by `mask` to `value` + Derived& set(const Mask mask, const bool value) + { + auto& r = rack(mask.rack); + r ^= (-Rack{value} ^ r) & mask.mask; + return *self(); + } + + /// Set the `index`th bit to `value` + Derived& set(const size_t index, const bool value) + { + return set(mask(index), value); + } + + /// Set all bits to zero + Derived& reset() + { + memset(data(), 0, data_size()); + return *self(); + } + + /// Reset the bit covered by `mask` to 0 + Derived& reset(const Mask mask) + { + rack(mask.rack) &= ~mask.mask; + return *self(); + } + + /// Reset the `index`th bit to 0 + Derived& reset(const size_t index) { return reset(mask(index)); } + + /// Flip all bits (one's complement) + Derived& flip() + { + for (size_t i = 0; i < num_racks(); ++i) { + rack(i) = ~rack(i); + } + return *self(); + } + + /// Flip the value of the bit covered by `mask` + Derived& flip(const Mask mask) + { + rack(mask.rack) ^= mask.mask; + return *self(); + } + + /// Flip the value of the `index`th bit + Derived& flip(const size_t index) { return flip(mask(index)); } + + /// Clear any bits in storage outside the valid range if necessary + void truncate() + { + if (const auto pad = num_racks() * bits_per_rack - size()) { + rack(num_racks() - 1) &= ~Rack{0} >> pad; + } + } + + /// Right-rotate by `bits` positions + Derived& rotr(const size_t bits) + { + assert(bits <= size()); + if (bits == 0 || bits == size()) { + return *self(); + } + + Derived t1(*self()); + *self() >>= bits; + t1 <<= (size() - bits); + *self() |= t1; + + truncate(); + return *self(); + } + + /// Left-rotate by `bits` positions + Derived& rotl(const size_t bits) + { + assert(bits <= size()); + if (bits == 0 || bits == size()) { + return *self(); + } + + Derived t1(*self()); + *self() <<= bits; + t1 >>= (size() - bits); + *self() |= t1; + + truncate(); + return *self(); + } + + /// Return true iff all bits are zero + bool none() const + { + for (size_t i = 0; i < num_racks(); ++i) { + if (rack(i)) { + return false; + } + } + return true; + } + + /// Return 1 + the index of the first set bit, or 0 if there are none + size_t find_first() const + { + for (size_t i = 0; i < num_racks(); ++i) { + const int j = chilbert::detail::find_first(rack(i)); + if (j) { + return (i * bits_per_rack) + static_cast(j); + } + } + return 0; + } + + /// Return the number of set bits + size_t count() const + { + size_t c = 0; + for (size_t i = 0; i < num_racks(); ++i) { + c += static_cast(pop_count(rack(i))); + } + return c; + } + + /// Return a mask that covers the bit with index `i` + Mask mask(const size_t i = 0) const + { + assert(i <= size()); + return Mask{i}; + } + + bool operator==(const Derived& vec) const + { + return (num_racks() == vec.num_racks() && + (num_racks() == 0 || + !memcmp(data(), vec.data(), num_racks() * sizeof(Rack)))); + } + + bool operator!=(const Derived& vec) const { return !(*this == vec); } + + bool operator<(const Derived& vec) const + { + assert(size() == vec.size()); + + for (size_t ri = 0; ri < num_racks(); ++ri) { + size_t i = num_racks() - ri - 1; + if (rack(i) < vec.rack(i)) { + return true; + } else if (rack(i) > vec.rack(i)) { + return false; + } + } + return false; + } + + Derived& operator&=(const Derived& vec) + { + for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { + rack(i) &= vec.rack(i); + } + + return *self(); + } + + Derived& operator|=(const Derived& vec) + { + for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { + rack(i) |= vec.rack(i); + } + + return *self(); + } + + Derived& operator^=(const Derived& vec) + { + for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { + rack(i) ^= vec.rack(i); + } + + return *self(); + } + + Derived& operator<<=(const size_t bits) + { + if (bits == 0) { + return *self(); + } else if (bits >= size()) { + reset(); + return *self(); + } + + const Index index{bits}; + + if (index.rack > 0) { + // Shift entire racks + for (size_t i = num_racks() - 1; i >= index.rack; --i) { + rack(i) = rack(i - index.rack); + } + for (size_t i = 0; i < index.rack; ++i) { + rack(i) = 0; + } + } + + if (index.bit > 0) { + // Shift bits within racks + size_t bi = bits_per_rack - index.bit; + size_t i; + for (i = num_racks() - 1; i >= index.rack + 1; --i) { + rack(i) <<= index.bit; + rack(i) |= rack(i - 1) >> bi; + } + rack(i) <<= index.bit; + } + + return *self(); + } + + Derived& operator>>=(const size_t bits) + { + if (bits == 0) { + return *self(); + } else if (bits >= size()) { + reset(); + return *self(); + } + + const Index index{bits}; + + if (index.rack > 0) { + // Shift entire racks + size_t i; + for (i = 0; i < num_racks() - index.rack; ++i) { + rack(i) = rack(i + index.rack); + } + for (; i < num_racks(); ++i) { + rack(i) = 0; + } + } + + if (index.bit > 0) { + // Shift bits within racks + size_t bi = bits_per_rack - index.bit; + size_t i; + for (i = 0; i < num_racks() - index.rack - 1; ++i) { + rack(i) >>= index.bit; + rack(i) |= rack(i + 1) << bi; + } + rack(i) >>= index.bit; + } + + return *self(); + } + + auto begin(const size_t i = 0) { return iterator(*self(), i); } + auto end() { return iterator(*self(), size()); } + auto begin(const size_t i = 0) const { return const_iterator(*self(), i); } + auto end() const { return const_iterator(self(), size()); } + + const Rack& rack(const size_t index) const { return self()->rack(index); } + Rack& rack(const size_t index) { return self()->rack(index); } + Rack* data() { return self()->data(); } + const Rack* data() const { return self()->data(); } + size_t num_racks() const { return self()->num_racks(); } + size_t size() const { return self()->size(); } + size_t data_size() const { return self()->data_size(); } + +private: + using Index = detail::BitVecIndex; + + Derived* self() { return static_cast(this); } + const Derived* self() const { return static_cast(this); } +}; + +template +void +gray_code(MultiBitVec& value) +{ + typename MultiBitVec::Rack s = 0; + + for (size_t ri = 0; ri < value.num_racks(); ++ri) { + const size_t i = value.num_racks() - ri - 1; + const auto t = value.rack(i) & 1; + gray_code(value.rack(i)); + value.rack(i) ^= (s << (MultiBitVec::bits_per_rack - 1)); + s = t; + } +} + +template +void +gray_code_inv(MultiBitVec& value) +{ + typename MultiBitVec::Rack s = 0; + + for (size_t ri = 0; ri < value.num_racks(); ++ri) { + const size_t i = value.num_racks() - ri - 1; + auto& rack = value.rack(i); + gray_code_inv(rack); + if (s) { + rack = ~rack; + } + s = rack & 1; + } +} + +} // namespace detail +} // namespace chilbert + +#endif -- cgit v1.2.1