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

Author: Abramo Bagnara abramo.bagnara@gmail.com Date: Wed Feb 22 13:17:14 2012 +0100

Uniformed, improved and moved to a better place implementation of clz/ctz.

---

src/Bit_Row.inlines.hh | 118 +++---------------------------------- src/Float.inlines.hh | 34 +----------- src/assert.hh | 2 - src/compiler.hh | 149 ++++++++++++++++++++++++++++++++++++++++++++++++ src/globals.inlines.hh | 3 +- 5 files changed, 162 insertions(+), 144 deletions(-)

diff --git a/src/Bit_Row.inlines.hh b/src/Bit_Row.inlines.hh index 0fb51b7..50e919c 100644 --- a/src/Bit_Row.inlines.hh +++ b/src/Bit_Row.inlines.hh @@ -24,6 +24,7 @@ site: http://bugseng.com/products/ppl/ . */ #ifndef PPL_Bit_Row_inlines_hh #define PPL_Bit_Row_inlines_hh 1

+#include "compiler.hh" #include "globals.defs.hh" #include "assert.hh"

@@ -160,15 +161,12 @@ Bit_Row::difference_assign(const Bit_Row& x, const Bit_Row& y) {

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) { - PPL_ASSERT(u != 0); - return __builtin_ctz(u); + return ctz(u); }

/*! \brief @@ -177,8 +175,7 @@ first_one(unsigned int u) { */ inline unsigned int first_one(unsigned long ul) { - PPL_ASSERT(ul != 0); - return __builtin_ctzl(ul); + return ctz(ul); }

/*! \brief @@ -187,65 +184,16 @@ first_one(unsigned long ul) { */ inline unsigned int first_one(unsigned long long ull) { - PPL_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; + return ctz(ull); } -#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) { - PPL_ASSERT(u != 0); - return sizeof(unsigned int)*CHAR_BIT - 1 - __builtin_clz(u); + return static_cast<unsigned int>(sizeof_to_bits(sizeof(u))) + - 1U - clz(u); }

/*! \brief @@ -254,8 +202,8 @@ last_one(unsigned int u) { */ inline unsigned int last_one(unsigned long ul) { - PPL_ASSERT(ul != 0); - return sizeof(unsigned long)*CHAR_BIT - 1 - __builtin_clzl(ul); + return static_cast<unsigned int>(sizeof_to_bits(sizeof(ul))) + - 1U - clz(ul); }

/*! \brief @@ -264,56 +212,10 @@ last_one(unsigned long ul) { */ inline unsigned int last_one(unsigned long long ull) { - PPL_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) { - PPL_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; + return static_cast<unsigned int>(sizeof_to_bits(sizeof(ull))) + - 1U - clz(ull); }

-#endif // !defined(__GNUC__) - } // namespace Implementation

/*! \relates Bit_Row */ diff --git a/src/Float.inlines.hh b/src/Float.inlines.hh index 6d851db..ce371e0 100644 --- a/src/Float.inlines.hh +++ b/src/Float.inlines.hh @@ -466,42 +466,10 @@ is_less_precise_than(Floating_Point_Format f1, Floating_Point_Format f2) { return f1 < f2; }

-#if defined(__GNUC__) inline unsigned int msb_position(unsigned long long v) { - PPL_ASSERT(v != 0); - return static_cast<unsigned>(__builtin_clzll(v)) ^ (sizeof(v)*8 - 1); + return static_cast<unsigned int>(sizeof_to_bits(sizeof(v))) - 1U - clz(v); } -#else -unsigned int -msb_position(unsigned long long v) { - PPL_ASSERT(v != 0); - unsigned r = 0; - if (v >= 0x100000000ULL) { - v >>= 32; - r += 32; - } - if (v >= 0x10000) { - v >>= 16; - r += 16; - } - if (v >= 0x100) { - v >>= 8; - r += 8; - } - if (v >= 0x10) { - v >>= 4; - r += 4; - } - if (v >= 4) { - v >>= 2; - r += 2; - } - if (v >= 2) - r++; - return r; -} -#endif

template <typename FP_Interval_Type> inline void diff --git a/src/assert.hh b/src/assert.hh index 29b103b..09c84a1 100644 --- a/src/assert.hh +++ b/src/assert.hh @@ -24,8 +24,6 @@ site: http://bugseng.com/products/ppl/ . */ #ifndef PPL_assert_hh #define PPL_assert_hh 1

-#include "globals.defs.hh" - // The PPL_UNREACHABLE_MSG macro flags a program point as unreachable. // Argument `msg__' is added to output when assertions are turned on. #if defined(NDEBUG) diff --git a/src/compiler.hh b/src/compiler.hh index eb34db2..7544710 100644 --- a/src/compiler.hh +++ b/src/compiler.hh @@ -24,6 +24,11 @@ site: http://bugseng.com/products/ppl/ . */ #ifndef PPL_compiler_hh #define PPL_compiler_hh 1

+#include "assert.hh" + +#include <cstddef> +#include <climits> + namespace Parma_Polyhedra_Library {

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS @@ -73,6 +78,150 @@ struct Suppress_Uninitialized_Warnings_Type { type name #endif

+inline std::size_t +sizeof_to_bits(std::size_t size) { + return size * static_caststd::size_t(CHAR_BIT); +} + +#if !defined(__GNUC__) + +inline unsigned int clz32(u_int32_t w) { + unsigned int r = 31; + if ((w & 0xffffffff00000000ULL) != 0) { + w = (w >> 31) >> 1; + r -= 32; + } + if ((w & 0xffff0000U) != 0) { + w >>= 16; + r -= 16; + } + if ((w & 0xff00U) != 0) { + w >>= 8; + r -= 8; + } + if ((w & 0xf0U) != 0) { + w >>= 4; + r -= 4; + } + if ((w & 0xcU) != 0) { + w >>= 2; + r -= 2; + } + if ((w & 0x2U) != 0) + r -= 1; + return r; +} + +inline unsigned int clz64(u_int64_t w) { + if ((w & 0xffffffff00000000ULL) == 0) + return clz32(static_cast<u_int32_t>(w)) + 32; + else + return clz32(static_cast<u_int32_t>(w >> 32)); +} + +inline unsigned int ctz32(u_int32_t w) { + static const unsigned int mod37_table[] = { + 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, + 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, + 5, 20, 8, 19, 18 + }; + return mod37_table[(w & -w) % 37]; +} + +inline unsigned int ctz64(u_int64_t w) { + if ((w & 0x00000000ffffffffULL) == 0) + return ctz32(static_cast<u_int32_t>(w >> 32)) + 32; + else + return ctz32(static_cast<u_int32_t>(w)); +} + +#endif + +inline unsigned int +clz(unsigned int u) { + PPL_ASSERT(u != 0); +#if defined(__GNUC__) + return static_cast<unsigned int>(__builtin_clz(u)); +#elif PPL_SIZEOF_INT == 4 + return clz32(u); +#elif PPL_SIZEOF_INT == 8 + return clz64(u); +#else + #error "Unsupported unsigned int size" +#endif +} + +inline unsigned int +clz(unsigned long ul) { + PPL_ASSERT(ul != 0); +#if defined(__GNUC__) + return static_cast<unsigned int>(__builtin_clzl(ul)); +#elif PPL_SIZEOF_LONG == 4 + return clz32(u); +#elif PPL_SIZEOF_LONG == 8 + return clz64(u); +#else + #error "Unsupported unsigned long size" +#endif +} + +inline unsigned int +clz(unsigned long long ull) { + PPL_ASSERT(ull != 0); +#if defined(__GNUC__) + return static_cast<unsigned int>(__builtin_clzll(ull)); +#elif PPL_SIZEOF_LONG_LONG == 4 + return clz32(u); +#elif PPL_SIZEOF_LONG_LONG == 8 + return clz64(u); +#else + #error "Unsupported unsigned long long size" +#endif +} + + +inline unsigned int +ctz(unsigned int u) { + PPL_ASSERT(u != 0); +#if defined(__GNUC__) + return static_cast<unsigned int>(__builtin_ctz(u)); +#elif PPL_SIZEOF_INT == 4 + return ctz32(u); +#elif PPL_SIZEOF_INT == 8 + return ctz64(u); +#else + #error "Unsupported unsigned int size" +#endif +} + +inline unsigned int +ctz(unsigned long ul) { + PPL_ASSERT(ul != 0); +#if defined(__GNUC__) + return static_cast<unsigned int>(__builtin_ctzl(ul)); +#elif PPL_SIZEOF_LONG == 4 + return ctz32(u); +#elif PPL_SIZEOF_LONG == 8 + return ctz64(u); +#else + #error "Unsupported unsigned long size" +#endif +} + +inline unsigned int +ctz(unsigned long long ull) { + PPL_ASSERT(ull != 0); +#if defined(__GNUC__) + return static_cast<unsigned int>(__builtin_ctzll(ull)); +#elif PPL_SIZEOF_LONG_LONG == 4 + return ctz32(u); +#elif PPL_SIZEOF_LONG_LONG == 8 + return ctz64(u); +#else + #error "Unsupported unsigned long long size" +#endif +} + } // namespace Parma_Polyhedra_Library

#endif // !defined(PPL_compiler_hh) diff --git a/src/globals.inlines.hh b/src/globals.inlines.hh index 97bde3f..513ec2e 100644 --- a/src/globals.inlines.hh +++ b/src/globals.inlines.hh @@ -27,6 +27,7 @@ site: http://bugseng.com/products/ppl/ . */ #include <limits> #include <cassert> #include <cctype> +#include "compiler.hh"

namespace Parma_Polyhedra_Library {

@@ -48,7 +49,7 @@ Weightwatch_Traits::get() {

inline bool Weightwatch_Traits::less_than(const Threshold& a, const Threshold& b) { - return b - a < (1ULL << (sizeof(Threshold)*8 - 1)); + return b - a < (1ULL << (sizeof_to_bits(sizeof(Threshold)) - 1)); }

inline void