diff options
Diffstat (limited to 'chilbert/detail')
| -rw-r--r-- | chilbert/detail/BitVecIndex.hpp | 51 | ||||
| -rw-r--r-- | chilbert/detail/BitVecIterator.hpp | 100 | ||||
| -rw-r--r-- | chilbert/detail/BitVecMask.hpp | 74 | ||||
| -rw-r--r-- | chilbert/detail/MultiBitVec.hpp | 383 | ||||
| -rw-r--r-- | chilbert/detail/gray_code_rank.hpp | 182 | ||||
| -rw-r--r-- | chilbert/detail/operations.hpp | 168 | ||||
| -rw-r--r-- | chilbert/detail/traits.hpp | 39 |
7 files changed, 997 insertions, 0 deletions
diff --git a/chilbert/detail/BitVecIndex.hpp b/chilbert/detail/BitVecIndex.hpp new file mode 100644 index 0000000..e7b385e --- /dev/null +++ b/chilbert/detail/BitVecIndex.hpp @@ -0,0 +1,51 @@ +/* + Copyright (C) 2018 David Robillard <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef CHILBERT_BITVECINDEX_HPP +#define CHILBERT_BITVECINDEX_HPP + +#include <cassert> +#include <climits> +#include <cstddef> + +namespace chilbert { +namespace detail { + +/// Index into a multi-rack bit vector +template <class BitVec> +struct BitVecIndex +{ + using Rack = typename BitVec::Rack; + + static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; + + BitVecIndex(const size_t bits) + : rack{bits / bits_per_rack} + , bit{bits - rack * bits_per_rack} + { + assert(bit < bits_per_rack); + } + + size_t rack; + size_t bit; +}; + +} // namespace detail +} // namespace chilbert + +#endif diff --git a/chilbert/detail/BitVecIterator.hpp b/chilbert/detail/BitVecIterator.hpp new file mode 100644 index 0000000..8902747 --- /dev/null +++ b/chilbert/detail/BitVecIterator.hpp @@ -0,0 +1,100 @@ +/* + Copyright (C) 2018 David Robillard <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef CHILBERT_BITVECITERATOR_HPP +#define CHILBERT_BITVECITERATOR_HPP + +#include "chilbert/detail/BitVecMask.hpp" + +#include <cstddef> + +namespace chilbert { +namespace detail { + +template <class BitVec> +class BitVecIteratorBase : public BitVecMask<typename BitVec::Rack> +{ +public: + using Mask = typename BitVec::Mask; + + BitVecIteratorBase& operator++() + { + Mask::operator++(); + return *this; + } + + BitVecIteratorBase& operator--() + { + Mask::operator--(); + return *this; + } + + bool operator==(const BitVecIteratorBase& rhs) const + { + return m_vec == rhs.m_vec && Mask::operator==(rhs); + } + + bool operator!=(const BitVecIteratorBase& rhs) const + { + return !operator==(rhs); + } + + bool operator*() const { return m_vec->test(*this); } + +protected: + BitVecIteratorBase(BitVec& vec, const size_t index) + : Mask{index} + , m_vec{&vec} + { + } + + BitVec* m_vec; +}; + +template <class BitVec> +class BitVecIterator : public BitVecIteratorBase<BitVec> +{ +public: + void set() { this->m_vec->set(*this); } + void reset() { this->m_vec->reset(*this); } + +private: + friend BitVec; + + BitVecIterator(BitVec& vec, const size_t index) + : BitVecIteratorBase<BitVec>{vec, index} + { + } +}; + +template <class BitVec> +class ConstBitVecIterator : public BitVecIteratorBase<const BitVec> +{ +private: + friend BitVec; + + ConstBitVecIterator(const BitVec& vec, const size_t index) + : BitVecIteratorBase<const BitVec>{vec, index} + { + } +}; + +} // namespace detail +} // namespace chilbert + +#endif diff --git a/chilbert/detail/BitVecMask.hpp b/chilbert/detail/BitVecMask.hpp new file mode 100644 index 0000000..03eaf5f --- /dev/null +++ b/chilbert/detail/BitVecMask.hpp @@ -0,0 +1,74 @@ +/* + Copyright (C) 2018 David Robillard <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef CHILBERT_BITVECMASK_HPP +#define CHILBERT_BITVECMASK_HPP + +#include <climits> +#include <cstddef> + +namespace chilbert { +namespace detail { + +/** Mask for a bit that can be incremented like an index. + * + * This enables fast iteration while setting or resetting bits since it is + * internally stored as a mask which avoids repeated index math. + */ +template <class Rack> +struct BitVecMask +{ + static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; + + BitVecMask(const size_t index) + : rack{index / bits_per_rack} + , mask{Rack{1} << (index - rack * bits_per_rack)} + { + } + + void operator++() + { + if ((mask <<= 1) == 0) { + mask = 1; + ++rack; + } + } + + void operator--() + { + if ((mask >>= 1) == 0) { + mask = Rack{1} << (bits_per_rack - 1); + --rack; + } + } + + bool operator==(const BitVecMask& rhs) const + { + return rack == rhs.rack && mask == rhs.mask; + } + + bool operator!=(const BitVecMask& rhs) const { return !operator==(rhs); } + + size_t rack; + Rack mask; +}; + +} // namespace detail +} // namespace chilbert + +#endif 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 <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#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 <cassert> +#include <climits> +#include <cstdint> +#include <cstring> + +namespace chilbert { +namespace detail { + +template <class Derived> +class MultiBitVec +{ +public: + using Rack = uintptr_t; + using Mask = BitVecMask<Rack>; + + using iterator = BitVecIterator<MultiBitVec<Derived>>; + using const_iterator = ConstBitVecIterator<MultiBitVec<Derived>>; + + 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<size_t>(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<size_t>(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>; + + Derived* self() { return static_cast<Derived*>(this); } + const Derived* self() const { return static_cast<const Derived*>(this); } +}; + +template <class Derived> +void +gray_code(MultiBitVec<Derived>& value) +{ + typename MultiBitVec<Derived>::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<Derived>::bits_per_rack - 1)); + s = t; + } +} + +template <class Derived> +void +gray_code_inv(MultiBitVec<Derived>& value) +{ + typename MultiBitVec<Derived>::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 diff --git a/chilbert/detail/gray_code_rank.hpp b/chilbert/detail/gray_code_rank.hpp new file mode 100644 index 0000000..815519e --- /dev/null +++ b/chilbert/detail/gray_code_rank.hpp @@ -0,0 +1,182 @@ +/* + Copyright (C) 2018 David Robillard <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef CHILBERT_GRAYCODERANK_HPP +#define CHILBERT_GRAYCODERANK_HPP + +#include <cassert> +#include <cstddef> +#include <numeric> + +namespace chilbert { +namespace detail { + +// This is the bulk of the cost in calculating +// a Compact Hilbert Index. It compresses a previously +// calculated index when provided the rotation +// at each level of precision. +template <class H, class HC> +inline void +compact_index(const size_t* const ms, + const size_t* const ds, + const size_t n, + const size_t m, + H& h, + HC& hc) +{ + assert(h.size() >= n * m); + assert(hc.size() >= std::accumulate(ms, ms + n, size_t(0))); + + reset_bits(hc); + + auto hm = h.mask(0); + auto hcm = hc.mask(0); + + // Run through the levels of precision + for (size_t i = 0; i < m; i++) { + // Run through the dimensions + size_t j = ds[i]; + do { + // This dimension contributes a bit? + if (ms[j] > i) { + if (h.test(hm)) { + hc.set(hcm); + } + ++hcm; + } + + if (++j == n) { + j = 0; + } + ++hm; + } while (j != ds[i]); + } +} + +template <class I> +inline void +gray_code_rank(const I& mask, const I& gi, const size_t n, I& r) +{ + assert(mask.size() == n); + assert(gi.size() == n); + assert(r.size() == n); + + r.reset(); + + auto mi = mask.begin(); + auto gii = gi.begin(); + auto ri = r.begin(); + + for (size_t i = 0; i < n; ++i, ++mi, ++gii) { + if (*mi) { + if (*gii) { + ri.set(); + } + ++ri; + } + } +} + +template <class I> +inline void +gray_code_rank_inv(const I& mask, + const I& ptrn, + const I& r, + const size_t n, + const size_t b, + I& g, + I& gi) +{ + assert(mask.size() == n); + assert(ptrn.size() == n); + assert(r.size() == n); + assert(g.size() == n); + assert(gi.size() == n); + + g.reset(); + gi.reset(); + + auto m = mask.mask(n - 1); + auto ri = r.begin(b - 1); + + typename I::Rack gi0 = 0; + typename I::Rack gi1 = 0; + typename I::Rack g0 = 0; + + for (size_t i = 0; i < n; ++i) { + if (mask.test(m)) { // Unconstrained bit + gi1 = gi0; + gi0 = *ri; + g0 = gi0 ^ gi1; + if (gi0) { + gi.set(m); + } + if (g0) { + g.set(m); + } + --ri; + } else { // Constrained bit + g0 = (ptrn.test(m) > 0); + gi1 = gi0; + gi0 = g0 ^ gi1; + if (gi0) { + gi.set(m); + } + if (g0) { + g.set(m); + } + } + + --m; + } +} + +template <class I> +inline void +extract_mask(const size_t* const ms, + const size_t n, + const size_t d, + const size_t i, + I& mask, + size_t& b) +{ + assert(0 <= d && d < n); + assert(mask.size() == n); + + mask.reset(); + b = 0; + + auto mi = mask.begin(); + size_t j = d; // #D j = (d==n-1) ? 0 : d+1; + do { + if (ms[j] > i) { + mi.set(); + ++b; + } + + ++mi; + if (++j == n) { + j = 0; + } + } while (j != d); +} + +} // namespace detail +} // namespace chilbert + +#endif diff --git a/chilbert/detail/operations.hpp b/chilbert/detail/operations.hpp new file mode 100644 index 0000000..94635b4 --- /dev/null +++ b/chilbert/detail/operations.hpp @@ -0,0 +1,168 @@ +/* + Copyright (C) 2018 David Robillard <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef CHILBERT_OPERATIONS_HPP +#define CHILBERT_OPERATIONS_HPP + +#include "chilbert/detail/traits.hpp" +#include "chilbert/operators.hpp" + +#include <cassert> +#include <climits> +#include <cstddef> +#include <cstdint> +#include <type_traits> + +namespace chilbert { +namespace detail { + +/// Reset all bits in `field` +template <typename T> +std::enable_if_t<std::is_integral<T>::value> +reset_bits(T& field) +{ + field = static_cast<T>(0); +} + +/// Reset all bits in `field` +template <typename T> +std::enable_if_t<is_bitvec_v<T>> +reset_bits(T& field) +{ + field.reset(); +} + +/// Return the `index`th bit in `field` +template <typename T> +std::enable_if_t<std::is_integral<T>::value, bool> +test_bit(const T& field, const size_t index) +{ + assert(size_t(index) < sizeof(field) * CHAR_BIT); + return field & (T{1} << index); +} + +/// Return the `index`th bit in `field` +template <typename T> +std::enable_if_t<is_bitvec_v<T>, bool> +test_bit(const T& field, const size_t index) +{ + return field.test(index); +} + +/// Set the `index`th bit in `field` +template <typename T> +std::enable_if_t<std::is_integral<T>::value> +set_bit(T& field, const size_t index) +{ + assert(size_t(index) < sizeof(field) * CHAR_BIT); + field |= (T{1} << index); + assert(test_bit(field, index)); +} + +/// Set the `index`th bit in `field` to `value` +template <typename T> +std::enable_if_t<std::is_integral<T>::value> +set_bit(T& field, const size_t index, const bool value) +{ + assert(size_t(index) < sizeof(field) * CHAR_BIT); + field ^= (-T{value} ^ field) & (T{1U} << index); + assert(test_bit(field, index) == value); +} + +/// Set the `index`th bit in `field` +template <typename T> +std::enable_if_t<is_bitvec_v<T>> +set_bit(T& field, const size_t index) +{ + field.set(index); +} + +/// Set the `index`th bit in `field` to `value` +template <typename T> +std::enable_if_t<is_bitvec_v<T>> +set_bit(T& field, const size_t index, const bool value) +{ + field.set(index, value); +} + +/// Return 1 + the index of the least significant 1-bit of `field`, or zero +template <typename T> +int pop_count(const T& field); + +template <> +int +pop_count<unsigned long>(const unsigned long& field) +{ + return __builtin_popcountl(field); +} + +template <> +int +pop_count<unsigned long long>(const unsigned long long& field) +{ + return __builtin_popcountll(field); +} + +/// Return 1 + the index of the least significant 1-bit of `field`, or zero +template <typename T> +int find_first(const T field); + +template <> +int +find_first<unsigned long>(const unsigned long field) +{ + return __builtin_ffsl(static_cast<long>(field)); +} + +template <> +int +find_first<unsigned long long>(const unsigned long long field) +{ + return __builtin_ffsll(static_cast<long long>(field)); +} + +/// Calculates the Gray Code of `value` in place +template <typename T> +std::enable_if_t<is_bitvec_v<T>> gray_code(T& value); + +/// Implementation of grayCode for any integral type +template <typename T> +std::enable_if_t<std::is_integral<T>::value> +gray_code(T& value) +{ + value ^= (value >> 1); +} + +/// Calculates the inverse Gray Code of `value` in place +template <typename T> +std::enable_if_t<is_bitvec_v<T>> gray_code_inv(T& value); + +/// Implementation of gray_code_inv for any integral type +template <typename T> +std::enable_if_t<std::is_integral<T>::value> +gray_code_inv(T& value) +{ + for (T shift = 1; shift < sizeof(T) * CHAR_BIT; shift <<= 1) { + value ^= (value >> shift); + } +} + +} // namespace detail +} // namespace chilbert + +#endif diff --git a/chilbert/detail/traits.hpp b/chilbert/detail/traits.hpp new file mode 100644 index 0000000..0cb0f03 --- /dev/null +++ b/chilbert/detail/traits.hpp @@ -0,0 +1,39 @@ +/* + Copyright (C) 2018 David Robillard <d@drobilla.net> + Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef CHILBERT_TRAITS_HPP +#define CHILBERT_TRAITS_HPP + +namespace chilbert { +namespace detail { + +/// Member `value` is true iff T is a chilbert bitset +template <class T> +struct is_bitvec +{ + static constexpr bool value = false; +}; + +/// True iff T is a chilbert bitset +template <class T> +static constexpr bool is_bitvec_v = is_bitvec<T>::value; + +} // namespace detail +} // namespace chilbert + +#endif |