diff options
| -rw-r--r-- | chilbert/BigBitVec.hpp | 142 | ||||
| -rw-r--r-- | chilbert/FixBitVec.hpp | 41 | ||||
| -rw-r--r-- | chilbert/Hilbert.ipp | 21 | ||||
| -rw-r--r-- | test/test_bitvec.cpp | 24 |
4 files changed, 96 insertions, 132 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp index 29d9a5a..7fe260e 100644 --- a/chilbert/BigBitVec.hpp +++ b/chilbert/BigBitVec.hpp @@ -85,7 +85,7 @@ public: explicit CBigBitVec(const size_t bits) : m_pcRacks{make_racks(num_racks(bits))} - , m_iRacks{bits == 0 ? 0 : num_racks(bits)} + , m_size{bits} { } @@ -96,31 +96,38 @@ public: } CBigBitVec(const CBigBitVec& vec) - : m_pcRacks{make_racks(vec.m_iRacks)} - , m_iRacks{vec.m_iRacks} + : m_pcRacks{make_racks(vec.rackCount())} + , m_size{vec.m_size} { if (vec.m_pcRacks) { memcpy( - m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks); + m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * rackCount()); } } CBigBitVec(CBigBitVec&& vec) = default; /// Return the size in bits - size_t size() const { return m_iRacks * bits_per_rack; } + size_t size() const { return m_size; } /// Set all bits to zero CBigBitVec& reset() { - memset(m_pcRacks.get(), 0, sizeof(Rack) * m_iRacks); + memset(m_pcRacks.get(), 0, sizeof(Rack) * rackCount()); return *this; } /// Set all bits to one CBigBitVec& set() { - memset(m_pcRacks.get(), 0xFF, sizeof(Rack) * m_iRacks); + if (m_size) { + memset(m_pcRacks.get(), 0xFF, sizeof(Rack) * rackCount()); + const auto pad = m_size % bits_per_rack; + if (pad) { + m_pcRacks[rackCount() - 1] |= ~Rack{0} >> pad; + } + } + return *this; } @@ -131,7 +138,7 @@ public: m_pcRacks[m.m_rack] &= (m.m_mask - 1); - for (size_t i = m.m_rack + 1; i < m_iRacks; ++i) { + for (size_t i = m.m_rack + 1; i < rackCount(); ++i) { m_pcRacks[i] = 0; } @@ -151,8 +158,8 @@ public: { assert(size() == vec.size()); - for (size_t ri = 0; ri < m_iRacks; ++ri) { - size_t i = m_iRacks - ri - 1; + for (size_t ri = 0; ri < rackCount(); ++ri) { + size_t i = rackCount() - ri - 1; if (m_pcRacks[i] < vec.m_pcRacks[i]) { return true; } else if (m_pcRacks[i] > vec.m_pcRacks[i]) { @@ -162,20 +169,19 @@ public: return false; } - /// Non-resizing assignment CBigBitVec& operator=(const CBigBitVec& vec) { - if (m_iRacks < vec.m_iRacks) { - m_iRacks = vec.m_iRacks; - m_pcRacks = make_racks(m_iRacks); + if (rackCount() < vec.rackCount()) { + m_pcRacks = make_racks(vec.rackCount()); + m_size = vec.m_size; memcpy( - m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks); - } else if (vec.m_iRacks > 0) { - m_iRacks = vec.m_iRacks; + m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * rackCount()); + } else if (vec.rackCount() > 0) { + m_size = vec.m_size; memcpy( - m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks); + m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * rackCount()); } else { - m_iRacks = 0; + m_size = 0; m_pcRacks.reset(); } @@ -239,7 +245,7 @@ public: CBigBitVec& operator&=(const CBigBitVec& vec) { - for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + for (size_t i = 0; i < std::min(rackCount(), vec.rackCount()); ++i) { m_pcRacks[i] &= vec.m_pcRacks[i]; } @@ -256,7 +262,7 @@ public: CBigBitVec& operator|=(const CBigBitVec& vec) { - for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + for (size_t i = 0; i < std::min(rackCount(), vec.rackCount()); ++i) { m_pcRacks[i] |= vec.m_pcRacks[i]; } @@ -273,7 +279,7 @@ public: CBigBitVec& operator^=(const CBigBitVec& vec) { - for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + for (size_t i = 0; i < std::min(rackCount(), vec.rackCount()); ++i) { m_pcRacks[i] ^= vec.m_pcRacks[i]; } @@ -308,7 +314,7 @@ public: if (index.rack > 0) { // Shift entire racks - for (size_t i = m_iRacks - 1; i >= index.rack; --i) { + for (size_t i = rackCount() - 1; i >= index.rack; --i) { m_pcRacks[i] = m_pcRacks[i - index.rack]; } for (size_t i = 0; i < index.rack; ++i) { @@ -320,7 +326,7 @@ public: // Shift bits within racks size_t bi = bits_per_rack - index.bit; size_t i; - for (i = m_iRacks - 1; i >= index.rack + 1; --i) { + for (i = rackCount() - 1; i >= index.rack + 1; --i) { m_pcRacks[i] <<= index.bit; m_pcRacks[i] |= m_pcRacks[i - 1] >> bi; } @@ -351,10 +357,10 @@ public: if (index.rack > 0) { // Shift entire racks size_t i; - for (i = 0; i < m_iRacks - index.rack; ++i) { + for (i = 0; i < rackCount() - index.rack; ++i) { m_pcRacks[i] = m_pcRacks[i + index.rack]; } - for (; i < m_iRacks; ++i) { + for (; i < rackCount(); ++i) { m_pcRacks[i] = 0; } } @@ -363,7 +369,7 @@ public: // Shift bits within racks size_t bi = bits_per_rack - index.bit; size_t i; - for (i = 0; i < m_iRacks - index.rack - 1; ++i) { + for (i = 0; i < rackCount() - index.rack - 1; ++i) { m_pcRacks[i] >>= index.bit; m_pcRacks[i] |= m_pcRacks[i + 1] << bi; } @@ -380,56 +386,42 @@ public: return t; } - /// Right-rotate the least significant `width` bits by `bits` positions - CBigBitVec& rotr(const size_t bits, size_t width) + /// Right-rotate by `bits` positions + CBigBitVec& rotr(const size_t bits) { - // Fill in the width, if necessary. - if (width <= 0) { - width = size(); - } - - // Modulo the number of bits. - assert(bits < width); - if (bits == 0) { + assert(bits <= size()); + if (bits == 0 || bits == size()) { return *this; } - // Ensure we are truncated appropriately. - truncate(width); + truncate(size()); CBigBitVec t1(*this); (*this) >>= bits; - t1 <<= (width - bits); + t1 <<= (size() - bits); (*this) |= t1; - truncate(width); + truncate(size()); return *this; } - /// Left-rotate the least significant `width` bits by `bits` positions - CBigBitVec& rotl(const size_t bits, size_t width) + /// Left-rotate by `bits` positions + CBigBitVec& rotl(const size_t bits) { - // Fill in the width, if necessary. - if (width <= 0) { - width = size(); - } - - // Modulo the number of bits. - assert(bits < width); - if (bits == 0) { + assert(bits <= size()); + if (bits == 0 || bits == size()) { return *this; } - // Ensure we are truncated appropriately. - truncate(width); + truncate(size()); CBigBitVec t1(*this); (*this) <<= bits; - t1 >>= (width - bits); + t1 >>= (size() - bits); (*this) |= t1; - truncate(width); + truncate(size()); return *this; } @@ -437,7 +429,7 @@ public: /// Return true iff all bits are zero bool none() const { - for (size_t i = 0; i < m_iRacks; ++i) { + for (size_t i = 0; i < rackCount(); ++i) { if (m_pcRacks[i]) { return false; } @@ -448,7 +440,7 @@ public: /// 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 < m_iRacks; ++i) { + for (size_t i = 0; i < rackCount(); ++i) { const int j = ffs(m_pcRacks[i]); if (j) { return (i * bits_per_rack) + static_cast<size_t>(j); @@ -461,7 +453,7 @@ public: size_t count() const { size_t c = 0; - for (size_t i = 0; i < m_iRacks; ++i) { + for (size_t i = 0; i < rackCount(); ++i) { c += static_cast<size_t>(pop_count(m_pcRacks[i])); } return c; @@ -470,7 +462,7 @@ public: /// Flip all bits (one's complement) CBigBitVec& flip() { - for (size_t i = 0; i < m_iRacks; ++i) { + for (size_t i = 0; i < rackCount(); ++i) { m_pcRacks[i] = ~m_pcRacks[i]; } return *this; @@ -485,7 +477,7 @@ public: const Rack* racks() const { return m_pcRacks.get(); } /// Return the number of racks - size_t rackCount() const { return m_iRacks; } + size_t rackCount() const { return num_racks(m_size); } template <class BitVec> class iterator_base : public Mask @@ -600,36 +592,8 @@ private: return RacksPtr{static_cast<Rack*>(calloc(n, sizeof(Rack)))}; } - // Right rotates entire racks (in place). - void rackRotr(const size_t k) - { - assert(k < m_iRacks); - - if (k == 0) { - return; - } - - size_t c = 0; - for (size_t v = 0; c < m_iRacks; ++v) { - size_t t = v; - size_t tp = v + k; - const Rack tmp = m_pcRacks[v]; - c++; - while (tp != v) { - m_pcRacks[t] = m_pcRacks[tp]; - t = tp; - tp += k; - if (tp >= m_iRacks) { - tp -= m_iRacks; - } - c++; - } - m_pcRacks[t] = tmp; - } - } - RacksPtr m_pcRacks; - size_t m_iRacks; + size_t m_size; }; template <> diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp index 0dab483..f9ce94a 100644 --- a/chilbert/FixBitVec.hpp +++ b/chilbert/FixBitVec.hpp @@ -79,25 +79,27 @@ public: Rack m_mask; }; - CFixBitVec(const size_t bits = bits_per_rack) + explicit CFixBitVec(const size_t bits) : m_rack{0} + , m_size{bits} { assert(bits <= bits_per_rack); } CFixBitVec(const size_t bits, const Rack value) : m_rack{value} + , m_size{bits} { assert(bits <= bits_per_rack); } /// Return the size in bits - size_t size() const { return bits_per_rack; } + size_t size() const { return m_size; } /// Set all bits to one CFixBitVec& set() { - m_rack = FBV1S; + m_rack = FBV1S & FBVN1S(size()); return *this; } @@ -255,32 +257,26 @@ public: return t; } - /// Right-rotate the least significant `width` bits by `bits` positions - CFixBitVec& rotr(const size_t bits, const size_t width) + /// Right-rotate by `bits` positions + CFixBitVec& rotr(const size_t bits) { if (bits) { - assert(width > 0); - assert(bits < width); - assert(bits < bits_per_rack); - assert((width - bits) < bits_per_rack); - m_rack &= FBVN1S(width); - m_rack = (m_rack >> bits) | (m_rack << (width - bits)); - m_rack &= FBVN1S(width); + assert(bits <= bits_per_rack); + m_rack &= FBVN1S(size()); + m_rack = (m_rack >> bits) | (m_rack << (size() - bits)); + m_rack &= FBVN1S(size()); } return *this; } - /// Left-rotate the least significant `width` bits by `bits` positions - CFixBitVec& rotl(const size_t bits, const size_t width) + /// Left-rotate by `bits` positions + CFixBitVec& rotl(const size_t bits) { if (bits > 0) { - assert(width > 0); - assert(bits < width); - assert(bits < bits_per_rack); - assert((width - bits) < bits_per_rack); - m_rack &= FBVN1S(width); - m_rack = (m_rack << bits) | (m_rack >> (width - bits)); - m_rack &= FBVN1S(width); + assert(bits <= bits_per_rack); + m_rack &= FBVN1S(size()); + m_rack = (m_rack << bits) | (m_rack >> (size() - bits)); + m_rack &= FBVN1S(size()); } return *this; } @@ -401,7 +397,8 @@ private: static_assert(8 * sizeof(Rack) == bits_per_rack, ""); static_assert((sizeof(Rack) == 4) || (sizeof(Rack) == 8), ""); - Rack m_rack{}; + Rack m_rack{}; + size_t m_size{}; }; template <> diff --git a/chilbert/Hilbert.ipp b/chilbert/Hilbert.ipp index 523bfec..92a2f0e 100644 --- a/chilbert/Hilbert.ipp +++ b/chilbert/Hilbert.ipp @@ -77,8 +77,9 @@ template <class I> inline void transform(const I& e, const size_t d, const size_t n, I& a) { + assert(a.size() == n); a ^= e; - a.rotr(d, n); //#D d+1, n ); + a.rotr(d); } // Inverse 'transforms' a point. @@ -86,7 +87,8 @@ template <class I> inline void transformInv(const I& e, const size_t d, const size_t n, I& a) { - a.rotl(d, n); //#D d+1, n ); + assert(a.size() == n); + a.rotl(d); a ^= e; } @@ -206,7 +208,7 @@ coordsToIndex(const P* const p, // [in ] point if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - _coordsToIndex<P, H, CFixBitVec>(p, m, n, h, CFixBitVec{}); + _coordsToIndex<P, H, CFixBitVec>(p, m, n, h, CFixBitVec(n)); } else { // Otherwise, they must be BigBitVecs _coordsToIndex<P, H, CBigBitVec>(p, m, n, h, CBigBitVec(n)); @@ -277,7 +279,7 @@ indexToCoords(P* const p, // [out] point if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - _indexToCoords<P, H, CFixBitVec>(p, m, n, h, CFixBitVec{}); + _indexToCoords<P, H, CFixBitVec>(p, m, n, h, CFixBitVec(n)); } else { // Otherwise, they must be BigBitVecs _indexToCoords<P, H, CBigBitVec>(p, m, n, h, CBigBitVec(n)); @@ -320,7 +322,7 @@ _coordsToCompactIndex(const P* const p, _coordsToIndex<P, CBigBitVec, I>(p, m, n, h, std::move(scratch), ds); compactIndex<CBigBitVec, HC>(ms, ds, n, m, h, hc); } else { - CFixBitVec h; + CFixBitVec h(mn); _coordsToIndex<P, CFixBitVec, I>(p, m, n, h, std::move(scratch), ds); compactIndex<CFixBitVec, HC>(ms, ds, n, m, h, hc); } @@ -347,7 +349,7 @@ coordsToCompactIndex( if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width? _coordsToCompactIndex<P, HC, CFixBitVec>( - p, ms, n, hc, CFixBitVec{}, M, m); + p, ms, n, hc, CFixBitVec(n), M, m); } else { // Otherwise, they must be BigBitVecs. _coordsToCompactIndex<P, HC, CBigBitVec>( @@ -403,7 +405,8 @@ _compactIndexToCoords(P* const p, size_t b = 0; extractMask<I>(ms, n, d, static_cast<size_t>(i), mask, b); ptrn = e; - ptrn.rotr(d, n); //#D ptrn.Rotr(d+1,n); + assert(ptrn.size() == n); + ptrn.rotr(d); // Get the Hilbert index bits M -= b; @@ -447,9 +450,9 @@ compactIndexToCoords( { if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - CFixBitVec scratch; + CFixBitVec scratch(n); _compactIndexToCoords<P, HC, CFixBitVec>( - p, ms, n, hc, CFixBitVec{}, M, m); + p, ms, n, hc, std::move(scratch), M, m); } else { // Otherwise, they must be BigBitVecs CBigBitVec scratch(n); diff --git a/test/test_bitvec.cpp b/test/test_bitvec.cpp index 2fa62ca..178b39a 100644 --- a/test/test_bitvec.cpp +++ b/test/test_bitvec.cpp @@ -200,13 +200,13 @@ void test_left_rotate(Context& ctx) { const T v = make_random_bitvec<T, N>(ctx); - for (size_t width = 0; width < std::min(N, size_t(128)); ++width) { - for (size_t bits = 0; bits <= width; ++bits) { - T r = v; - r.rotl(bits, width); + for (size_t bits = 0; bits <= N; ++bits) { + T r = v; + r.rotl(bits); - for (size_t i = 0; i < width; ++i) { - assert(r.test((i + bits) % width) == v.test(i)); + if (N > 0) { + for (size_t i = 0; i < N; ++i) { + assert(r.test((i + bits) % N) == v.test(i)); } } } @@ -217,13 +217,13 @@ void test_right_rotate(Context& ctx) { const T v = make_random_bitvec<T, N>(ctx); - for (size_t width = 0; width < std::min(N, size_t(128)); ++width) { - for (size_t bits = 0; bits <= width; ++bits) { - T r = v; - r.rotr(bits, width); + for (size_t bits = 0; bits <= N; ++bits) { + T r = v; + r.rotr(bits); - for (size_t i = 0; i < width; ++i) { - assert(r.test(i) == v.test((i + bits) % width)); + if (N > 0) { + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == v.test((i + bits) % N)); } } } |