diff options
| -rwxr-xr-x[-rw-r--r--] | src/corelib/tools/qalgorithms.h | 125 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/corelib/tools/qalgorithms.qdoc | 70 | ||||
| -rwxr-xr-x[-rw-r--r--] | tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp | 107 |
3 files changed, 302 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. + */ diff --git a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp index 9bce948140..99e5c4c85d 100644..100755 --- a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp +++ b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp @@ -31,6 +31,7 @@ ** ****************************************************************************/ +#include "../../../../../src/corelib/tools/qalgorithms.h" #include <QtTest/QtTest> #include <iostream> @@ -80,6 +81,24 @@ private slots: void popCount32() { popCount_impl<quint32>(); } void popCount64() { popCount_impl<quint64>(); } + void countTrailing08_data() { countTrailing_data_impl(sizeof(quint8 )); } + void countTrailing16_data() { countTrailing_data_impl(sizeof(quint16)); } + void countTrailing32_data() { countTrailing_data_impl(sizeof(quint32)); } + void countTrailing64_data() { countTrailing_data_impl(sizeof(quint64)); } + void countTrailing08() { countTrailing_impl<quint8 >(); } + void countTrailing16() { countTrailing_impl<quint16>(); } + void countTrailing32() { countTrailing_impl<quint32>(); } + void countTrailing64() { countTrailing_impl<quint64>(); } + + void countLeading08_data() { countLeading_data_impl(sizeof(quint8 )); } + void countLeading16_data() { countLeading_data_impl(sizeof(quint16)); } + void countLeading32_data() { countLeading_data_impl(sizeof(quint32)); } + void countLeading64_data() { countLeading_data_impl(sizeof(quint64)); } + void countLeading08() { countLeading_impl<quint8 >(); } + void countLeading16() { countLeading_impl<quint16>(); } + void countLeading32() { countLeading_impl<quint32>(); } + void countLeading64() { countLeading_impl<quint64>(); } + private: #if Q_TEST_PERFORMANCE void performance(); @@ -87,6 +106,14 @@ private: void popCount_data_impl(size_t sizeof_T_Int); template <typename T_Int> void popCount_impl(); + + void countTrailing_data_impl(size_t sizeof_T_Int); + template <typename T_Int> + void countTrailing_impl(); + + void countLeading_data_impl(size_t sizeof_T_Int); + template <typename T_Int> + void countLeading_impl(); }; class TestInt @@ -1084,6 +1111,86 @@ void tst_QAlgorithms::popCount_impl() QCOMPARE(qPopulationCount(value), expected); } +void tst_QAlgorithms::countTrailing_data_impl(size_t sizeof_T_Int) +{ + using namespace QTest; + addColumn<quint64>("input"); + addColumn<uint>("expected"); + + int nibs = sizeof_T_Int*2; + + newRow(("0x"+QByteArray::number(0,16).rightJustified(nibs,'0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + const quint64 input = Q_UINT64_C(1) << i; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << i; + } + + quint64 type_mask; + if (sizeof_T_Int>=8) + type_mask = ~Q_UINT64_C(0); + else + type_mask = (Q_UINT64_C(1) << (sizeof_T_Int*8))-1; + + // and some random ones: + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary + const quint64 r = quint64(qrand()) << 32 | quint32(qrand()); + const quint64 b = Q_UINT64_C(1) << i; + const quint64 mask = ((~(b-1)) ^ b) & type_mask; + const quint64 input = (r&mask) | b; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << i; + } + } +} + +template <typename T_Int> +void tst_QAlgorithms::countTrailing_impl() +{ + QFETCH(quint64, input); + QFETCH(uint, expected); + + const T_Int value = static_cast<T_Int>(input); + + QCOMPARE(qCountTrailingZeroBits(value), expected); +} + +void tst_QAlgorithms::countLeading_data_impl(size_t sizeof_T_Int) +{ + using namespace QTest; + addColumn<quint64>("input"); + addColumn<uint>("expected"); + + int nibs = sizeof_T_Int*2; + + newRow(("0x"+QByteArray::number(0,16).rightJustified(nibs,'0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + const quint64 input = Q_UINT64_C(1) << i; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << uint(sizeof_T_Int*8-i-1); + } + + // and some random ones: + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary + const quint64 r = quint64(qrand()) << 32 | quint32(qrand()); + const quint64 b = Q_UINT64_C(1) << i; + const quint64 mask = b-1; + const quint64 input = (r&mask) | b; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << uint(sizeof_T_Int*8-i-1); + } + } +} + +template <typename T_Int> +void tst_QAlgorithms::countLeading_impl() +{ + QFETCH(quint64, input); + QFETCH(uint, expected); + + const T_Int value = static_cast<T_Int>(input); + + QCOMPARE(qCountLeadingZeroBits(value), expected); +} + QTEST_APPLESS_MAIN(tst_QAlgorithms) #include "tst_qalgorithms.moc" |