From 046f3254838715079b853ab4e15eed4ef464fb30 Mon Sep 17 00:00:00 2001 From: Glen Mabey Date: Sat, 7 Feb 2015 21:11:22 -0600 Subject: Adds qFindFirstSetBit() and qFindLastSetBit(). Two new function families have been added: qFindFirstSetBit() and qFindLastSetBit() for a variety of integer sizes. Fast implementations are included for most platforms. [ChangeLog][QtCore][QtAlgorithms] Added qFindFirstSetBit() and qFindLastSetBit(). Change-Id: I89d9d1637ea26070aee5a60be95be1b51bfc84dc Reviewed-by: Thiago Macieira --- src/corelib/tools/qalgorithms.h | 125 +++++++++++++++++++++++++++++++++++++ src/corelib/tools/qalgorithms.qdoc | 70 +++++++++++++++++++++ 2 files changed, 195 insertions(+) mode change 100644 => 100755 src/corelib/tools/qalgorithms.h mode change 100644 => 100755 src/corelib/tools/qalgorithms.qdoc (limited to 'src') diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h old mode 100644 new mode 100755 index ff4d5a3ebd..57fbdf0eba --- a/src/corelib/tools/qalgorithms.h +++ b/src/corelib/tools/qalgorithms.h @@ -584,6 +584,131 @@ Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qPopulationCount(long unsigne #undef QALGORITHMS_USE_BUILTIN_POPCOUNT #endif +Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint32 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_ctz(v) : 32U; +#else + // see http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel + unsigned int c = 32; // c will be the number of zero bits on the right + v &= -signed(v); + if (v) c--; + if (v & 0x0000FFFF) c -= 16; + if (v & 0x00FF00FF) c -= 8; + if (v & 0x0F0F0F0F) c -= 4; + if (v & 0x33333333) c -= 2; + if (v & 0x55555555) c -= 1; + return c; +#endif +} + +Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint8 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_ctz(v) : 8U; +#else + unsigned int c = 8; // c will be the number of zero bits on the right + v &= -signed(v); + if (v) c--; + if (v & 0x0000000F) c -= 4; + if (v & 0x00000033) c -= 2; + if (v & 0x00000055) c -= 1; + return c; +#endif +} + +Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint16 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_ctz(v) : 16U; +#else + unsigned int c = 16; // c will be the number of zero bits on the right + v &= -signed(v); + if (v) c--; + if (v & 0x000000FF) c -= 8; + if (v & 0x00000F0F) c -= 4; + if (v & 0x00003333) c -= 2; + if (v & 0x00005555) c -= 1; + return c; +#endif +} + +Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint64 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_ctzll(v) : 64; +#else + quint32 x = static_cast(v); + return x ? qCountTrailingZeroBits(x) + : 32 + qCountTrailingZeroBits(static_cast(v >> 32)); +#endif +} + +Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(unsigned long v) Q_DECL_NOTHROW +{ + return qCountTrailingZeroBits(QIntegerForSizeof::Unsigned(v)); +} + +Q_DECL_CONSTEXPR inline uint qCountLeadingZeroBits(quint32 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_clz(v) : 32U; +#else + // Hacker's Delight, 2nd ed. Fig 5-16, p. 102 + v = v | (v >> 1); + v = v | (v >> 2); + v = v | (v >> 4); + v = v | (v >> 8); + v = v | (v >> 16); + return qPopulationCount(~v); +#endif +} + +Q_DECL_CONSTEXPR inline uint qCountLeadingZeroBits(quint8 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_clz(v)-24U : 8U; +#else + v = v | (v >> 1); + v = v | (v >> 2); + v = v | (v >> 4); + return qPopulationCount(static_cast(~v)); +#endif +} + +Q_DECL_CONSTEXPR inline uint qCountLeadingZeroBits(quint16 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_clz(v)-16U : 16U; +#else + v = v | (v >> 1); + v = v | (v >> 2); + v = v | (v >> 4); + v = v | (v >> 8); + return qPopulationCount(static_cast(~v)); +#endif +} + +Q_DECL_CONSTEXPR inline uint qCountLeadingZeroBits(quint64 v) Q_DECL_NOTHROW +{ +#if defined(Q_CC_GNU) + return v ? __builtin_clzll(v) : 64U; +#else + v = v | (v >> 1); + v = v | (v >> 2); + v = v | (v >> 4); + v = v | (v >> 8); + v = v | (v >> 16); + v = v | (v >> 32); + return qPopulationCount(~v); +#endif +} + +Q_DECL_CONSTEXPR inline uint qCountLeadingZeroBits(unsigned long v) Q_DECL_NOTHROW +{ + return qCountLeadingZeroBits(QIntegerForSizeof::Unsigned(v)); +} + QT_WARNING_POP QT_END_NAMESPACE diff --git a/src/corelib/tools/qalgorithms.qdoc b/src/corelib/tools/qalgorithms.qdoc old mode 100644 new mode 100755 index 193042e017..dac353fa70 --- a/src/corelib/tools/qalgorithms.qdoc +++ b/src/corelib/tools/qalgorithms.qdoc @@ -785,3 +785,73 @@ \since 5.2 \overload */ + +/*! + \fn uint qCountTrailingZeroBits(quint8 v) + \relates + \since 5.6 + + Returns the number of consecutive zero bits in \a v, when searching from the LSB. + For example, qCountTrailingZeroBits(1) returns 0 and qCountTrailingZeroBits(8) returns 3. + */ + +/*! + \fn uint qCountTrailingZeroBits(quint16 v) + \relates + \since 5.6 + \overload + */ + +/*! + \fn uint qCountTrailingZeroBits(quint32 v) + \relates + \since 5.6 + \overload + */ + +/*! + \fn uint qCountTrailingZeroBits(quint64 v) + \relates + \since 5.6 + \overload + */ + +/*! + \fn uint qCountLeadingZeroBits(quint8 v) + \relates + \since 5.6 + + Returns the number of consecutive zero bits in \a v, when searching from the MSB. + For example, qCountLeadingZeroBits(quint8(1)) returns 7 and + qCountLeadingZeroBits(quint8(8)) returns 4. + */ + +/*! + \fn uint qCountLeadingZeroBits(quint16 v) + \relates + \since 5.6 + + Returns the number of consecutive zero bits in \a v, when searching from the MSB. + For example, qCountLeadingZeroBits(quint16(1)) returns 15 and + qCountLeadingZeroBits(quint16(8)) returns 12. + */ + +/*! + \fn uint qCountLeadingZeroBits(quint32 v) + \relates + \since 5.6 + + Returns the number of consecutive zero bits in \a v, when searching from the MSB. + For example, qCountLeadingZeroBits(quint32(1)) returns 31 and + qCountLeadingZeroBits(quint32(8)) returns 28. + */ + +/*! + \fn uint qCountLeadingZeroBits(quint64 v) + \relates + \since 5.6 + + Returns the number of consecutive zero bits in \a v, when searching from the MSB. + For example, qCountLeadingZeroBits(quint64(1)) returns 63 and + qCountLeadingZeroBits(quint64(8)) returns 60. + */ -- cgit v1.2.3