[PPL-devel] [GIT] ppl/ppl(master): Uniformed, improved and moved to a better place implementation of clz/ctz.
Abramo Bagnara
abramo.bagnara at gmail.com
Wed Feb 22 13:17:21 CET 2012
Module: ppl/ppl
Branch: master
Commit: 754dcbd68b32c262d39d7d5dba3ed01a9f816b6c
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=754dcbd68b32c262d39d7d5dba3ed01a9f816b6c
Author: Abramo Bagnara <abramo.bagnara at 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_cast<std::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
More information about the PPL-devel
mailing list