Module: ppl/ppl Branch: master Commit: 0dbad6c0854d82ebeed8d0ab04bd915f3699a005 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0dbad6c0854d8...

Author: Roberto Bagnara bagnara@cs.unipr.it Date: Mon Apr 20 22:06:33 2009 +0200

Bit_Row iterators reimplemented more efficiently.

---

src/Bit_Row.cc | 77 +-------------------- src/Bit_Row.defs.hh | 6 -- src/Bit_Row.inlines.hh | 172 ++++++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 165 insertions(+), 90 deletions(-)

diff --git a/src/Bit_Row.cc b/src/Bit_Row.cc index 4cece3a..1983f21 100644 --- a/src/Bit_Row.cc +++ b/src/Bit_Row.cc @@ -28,75 +28,6 @@ site: http://www.cs.unipr.it/ppl/ . */

namespace PPL = Parma_Polyhedra_Library;

-#if !PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT -unsigned int -PPL::Bit_Row::first_one(mp_limb_t w) { - unsigned int r = 0; - w = w & -w; -#if PPL_SIZEOF_MP_LIMB_T == 8 - if ((w & 0xffffffff) == 0) { - w >>= 32; - r += 32; - } -#elif PPL_SIZEOF_MP_LIMB_T != 4 -#error "Size of mp_limb_t not supported by Bit_Row::first_one(mp_limb_t w)." -#endif - if ((w & 0xffff) == 0) { - w >>= 16; - r += 16; - } - if ((w & 0xff) == 0) { - w >>= 8; - r += 8; - } - if (w & 0xf0) - r += 4; - if (w & 0xcc) - r += 2; - if (w & 0xaa) - r += 1; - return r; -} -#endif // !PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT - -unsigned int -PPL::Bit_Row::last_one(mp_limb_t w) { - unsigned int r = 0; -#if PPL_SIZEOF_MP_LIMB_T == 8 - if (w & -#if PPL_SIZEOF_LONG == 8 - 0xffffffff00000000 -#else - 0xffffffff00000000LL -#endif - ) { - w >>= 32; - r += 32; - } -#elif PPL_SIZEOF_MP_LIMB_T != 4 -#error "Size of mp_limb_t not supported by Bit_Row::last_one(mp_limb_t w)." -#endif - if (w & 0xffff0000) { - w >>= 16; - r += 16; - } - if (w & 0xff00) { - w >>= 8; - r += 8; - } - if (w & 0xf0) { - w >>= 4; - r += 4; - } - if (w & 0xc) { - w >>= 2; - r += 2; - } - if (w & 0x2) - r += 1; - return r; -} - unsigned long PPL::Bit_Row::first() const { const mp_size_t vec_size = vec->_mp_size; @@ -106,7 +37,7 @@ PPL::Bit_Row::first() const { for (; li < vec_size; ++li, ++p) { const mp_limb_t limb = *p; if (limb != 0) - return li*PPL_BITS_PER_GMP_LIMB + first_one(limb); + return li*PPL_BITS_PER_GMP_LIMB + Implementation::first_one(limb); } return ULONG_MAX; } @@ -136,7 +67,7 @@ PPL::Bit_Row::next(unsigned long position) const {

while (true) { if (limb != 0) - return li*PPL_BITS_PER_GMP_LIMB + first_one(limb); + return li*PPL_BITS_PER_GMP_LIMB + Implementation::first_one(limb); ++li; if (li == vec_size) break; @@ -156,7 +87,7 @@ PPL::Bit_Row::last() const { const mp_srcptr p = vec->_mp_d + li; const mp_limb_t limb = *p; assert(limb != 0); - return li*PPL_BITS_PER_GMP_LIMB + last_one(limb); + return li*PPL_BITS_PER_GMP_LIMB + Implementation::last_one(limb); }

unsigned long @@ -189,7 +120,7 @@ PPL::Bit_Row::prev(unsigned long position) const {

while (true) { if (limb != 0) - return li*PPL_BITS_PER_GMP_LIMB + last_one(limb); + return li*PPL_BITS_PER_GMP_LIMB + Implementation::last_one(limb); if (li == 0) break; --li; diff --git a/src/Bit_Row.defs.hh b/src/Bit_Row.defs.hh index ce278c9..ee1c98e 100644 --- a/src/Bit_Row.defs.hh +++ b/src/Bit_Row.defs.hh @@ -203,12 +203,6 @@ private: Upon entry, \p vec must have allocated enough space to contain the result. */ void union_helper(const Bit_Row& x, const Bit_Row& y); - - //! Assuming \p w is nonzero, returns the index of the first set bit in \p w. - static unsigned int first_one(mp_limb_t w); - - //! Assuming \p w is nonzero, returns the index of the last set bit in \p w. - static unsigned int last_one(mp_limb_t w); };

namespace std { diff --git a/src/Bit_Row.inlines.hh b/src/Bit_Row.inlines.hh index 5084a64..2ad8a19 100644 --- a/src/Bit_Row.inlines.hh +++ b/src/Bit_Row.inlines.hh @@ -91,8 +91,9 @@ Bit_Row::clear_from(const unsigned long k) {

inline unsigned long Bit_Row::count_ones() const { - assert(vec->_mp_size >= 0); - return vec->_mp_size == 0 ? 0 : mpn_popcount(vec->_mp_d, vec->_mp_size); + mp_size_t x_size = vec->_mp_size; + assert(x_size >= 0); + return x_size == 0 ? 0 : mpn_popcount(vec->_mp_d, x_size); }

inline bool @@ -120,15 +121,6 @@ Bit_Row::total_memory_in_bytes() const { return sizeof(*this) + external_memory_in_bytes(); }

-#if PPL_HAVE_DECL_FFS && PPL_SIZEOF_MP_LIMB_T == PPL_SIZEOF_INT - -inline unsigned int -Bit_Row::first_one(mp_limb_t w) { - return ffs(w)-1; -} - -#endif - /*! \relates Bit_Row */ inline void set_union(const Bit_Row& x, const Bit_Row& y, Bit_Row& z) { @@ -160,6 +152,164 @@ set_difference(const Bit_Row& x, const Bit_Row& y, Bit_Row& z) { mpz_and(z.vec, x.vec, complement_y.get_mpz_t()); }

+namespace Implementation { + +#if defined(__GNUC__) + +/*! \brief + Assuming \p u is nonzero, returns the index of the first set bit in \p u. +*/ +inline unsigned int +first_one(unsigned int u) { + assert(u != 0); + return __builtin_ctz(u); +} + +/*! \brief + Assuming \p ul is nonzero, returns the index of the first set bit in + \p ul. +*/ +inline unsigned int +first_one(unsigned long ul) { + assert(ul != 0); + return __builtin_ctzl(ul); +} + +/*! \brief + Assuming \p ull is nonzero, returns the index of the first set bit in + \p ull. +*/ +inline unsigned int +first_one(unsigned long long ull) { + assert(ull != 0); + return __builtin_ctzll(ull); +} + +#elif PPL_HAVE_DECL_FFS && PPL_SIZEOF_MP_LIMB_T == PPL_SIZEOF_INT + +/*! \brief + Assuming \p w is nonzero, returns the index of the first set bit in \p w. +*/ +inline unsigned int +first_one(mp_limb_t w) { + return ffs(w)-1; +} + +#else + +/*! \brief + Assuming \p w is nonzero, returns the index of the first set bit in \p w. +*/ +inline unsigned int +first_one(mp_limb_t w) { + unsigned int r = 0; + w = w & -w; +#if PPL_SIZEOF_MP_LIMB_T == 8 + if ((w & 0xffffffff) == 0) { + w >>= 32; + r += 32; + } +#elif PPL_SIZEOF_MP_LIMB_T != 4 +#error "size of mp_limb_t not supported by first_one(mp_limb_t w)." +#endif + if ((w & 0xffff) == 0) { + w >>= 16; + r += 16; + } + if ((w & 0xff) == 0) { + w >>= 8; + r += 8; + } + if (w & 0xf0) + r += 4; + if (w & 0xcc) + r += 2; + if (w & 0xaa) + r += 1; + return r; +} +#endif // !defined(__GNUC__) + // && (!PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT) + +#if defined(__GNUC__) + +/*! \brief + Assuming \p u is nonzero, returns the index of the last set bit in \p u. +*/ +inline unsigned int +last_one(unsigned int u) { + assert(u != 0); + return sizeof(unsigned int)*CHAR_BIT - 1 - __builtin_clz(u); +} + +/*! \brief + Assuming \p ul is nonzero, returns the index of the last set bit in + \p ul. +*/ +inline unsigned int +last_one(unsigned long ul) { + assert(ul != 0); + return sizeof(unsigned long)*CHAR_BIT - 1 - __builtin_clzl(ul); +} + +/*! \brief + Assuming \p ull is nonzero, returns the index of the last set bit in + \p ull. +*/ +inline unsigned int +last_one(unsigned long long ull) { + assert(ull != 0); + return sizeof(unsigned long long)*CHAR_BIT - 1 - __builtin_clzll(ull); +} + +#else // !defined(__GNUC__) + +/*! \brief + Assuming \p w is nonzero, returns the index of the last set bit in \p w. +*/ +inline unsigned int +last_one(mp_limb_t w) { + assert(w != 0); + unsigned int r = 0; +#if PPL_SIZEOF_MP_LIMB_T == 8 + if (w & +#if PPL_SIZEOF_LONG == 8 + 0xffffffff00000000 +#else + 0xffffffff00000000LL +#endif + ) { + w >>= 32; + r += 32; + } +#elif PPL_SIZEOF_MP_LIMB_T != 4 +#error "size of mp_limb_t not supported by last_one(mp_limb_t w)." +#endif + if (w & 0xffff0000) { + w >>= 16; + r += 16; + } + if (w & 0xff00) { + w >>= 8; + r += 8; + } + if (w & 0xf0) { + w >>= 4; + r += 4; + } + if (w & 0xc) { + w >>= 2; + r += 2; + } + if (w & 0x2) + r += 1; + return r; +} + +#endif // !defined(__GNUC__) + +} // namespace Implementation + } // namespace Parma_Polyhedra_Library