diff options
Diffstat (limited to 'src/corelib')
| -rwxr-xr-x[-rw-r--r--] | src/corelib/tools/qalgorithms.h | 125 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/corelib/tools/qalgorithms.qdoc | 70 |
2 files changed, 195 insertions, 0 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h index ff4d5a3ebd..57fbdf0eba 100644..100755 --- 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<quint32>(v); + return x ? qCountTrailingZeroBits(x) + : 32 + qCountTrailingZeroBits(static_cast<quint32>(v >> 32)); +#endif +} + +Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(unsigned long v) Q_DECL_NOTHROW +{ + return qCountTrailingZeroBits(QIntegerForSizeof<long>::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<quint8>(~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<quint16>(~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<long>::Unsigned(v)); +} + QT_WARNING_POP QT_END_NAMESPACE diff --git a/src/corelib/tools/qalgorithms.qdoc b/src/corelib/tools/qalgorithms.qdoc index 193042e017..dac353fa70 100644..100755 --- 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 <QtAlgorithms> + \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 <QtAlgorithms> + \since 5.6 + \overload + */ + +/*! + \fn uint qCountTrailingZeroBits(quint32 v) + \relates <QtAlgorithms> + \since 5.6 + \overload + */ + +/*! + \fn uint qCountTrailingZeroBits(quint64 v) + \relates <QtAlgorithms> + \since 5.6 + \overload + */ + +/*! + \fn uint qCountLeadingZeroBits(quint8 v) + \relates <QtAlgorithms> + \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 <QtAlgorithms> + \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 <QtAlgorithms> + \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 <QtAlgorithms> + \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. + */ |