diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2012-05-18 20:12:35 +0200 |
---|---|---|
committer | The Qt Project <gerrit-noreply@qt-project.org> | 2013-04-03 11:38:35 +0200 |
commit | 76e0223619da02911d02813961ef631a5e02d826 (patch) | |
tree | 0fafdd9293508a89c7baed92b8d269dc93a36670 | |
parent | 6e7b8f79cb852ee1a6262a22aabd328b0e1b6dc0 (diff) |
Add qPopulationCount() function, extracted from QBitArray
This functionality is used in multiple places in Qt itself, so it makes
sense to have a global function for this. This also allows to map this
onto specialized assembler instructions, should an architecture provide
them, later on.
Also added comprehensive tests, using a 4-bit lookup-table implementation
as a reference.
Change-Id: I8c4ea72cce54506ebb9fbe61141dbb5f1b7a660f
Reviewed-by: Stephen Kelly <stephen.kelly@kdab.com>
-rw-r--r-- | src/corelib/tools/qalgorithms.h | 38 | ||||
-rw-r--r-- | src/corelib/tools/qalgorithms.qdoc | 31 | ||||
-rw-r--r-- | src/corelib/tools/qbitarray.cpp | 11 | ||||
-rw-r--r-- | src/platformsupport/eglconvenience/qxlibeglintegration.cpp | 17 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp | 80 |
5 files changed, 154 insertions, 23 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h index e3b76886f1..2658cfc2c2 100644 --- a/src/corelib/tools/qalgorithms.h +++ b/src/corelib/tools/qalgorithms.h @@ -516,6 +516,44 @@ Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator } //namespace QAlgorithmsPrivate +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint32 v) +{ + // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint8 v) +{ + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint16 v) +{ + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint64 v) +{ + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(long unsigned int v) +{ + return qPopulationCount(static_cast<quint64>(v)); +} + QT_END_NAMESPACE #endif // QALGORITHMS_H diff --git a/src/corelib/tools/qalgorithms.qdoc b/src/corelib/tools/qalgorithms.qdoc index cc544af868..7c3aa1a3b2 100644 --- a/src/corelib/tools/qalgorithms.qdoc +++ b/src/corelib/tools/qalgorithms.qdoc @@ -635,3 +635,34 @@ of \a value in the variable passed as a reference in argument \a n. \sa {qLess()}{qLess<T>()} */ + + +/*! + \fn uint qPopulationCount(quint8 v) + \relates <QtAlgorithms> + \since 5.2 + + Returns the number of bits set in \a v. This number also called + the Hamming Weight of \a v. + */ + +/*! + \fn uint qPopulationCount(quint16 v) + \relates <QtAlgorithms> + \since 5.2 + \overload + */ + +/*! + \fn uint qPopulationCount(quint32 v) + \relates <QtAlgorithms> + \since 5.2 + \overload + */ + +/*! + \fn uint qPopulationCount(quint64 v) + \relates <QtAlgorithms> + \since 5.2 + \overload + */ diff --git a/src/corelib/tools/qbitarray.cpp b/src/corelib/tools/qbitarray.cpp index 2b459b2b1b..4949476f25 100644 --- a/src/corelib/tools/qbitarray.cpp +++ b/src/corelib/tools/qbitarray.cpp @@ -40,6 +40,7 @@ ****************************************************************************/ #include "qbitarray.h" +#include <qalgorithms.h> #include <qdatastream.h> #include <qdebug.h> #include <string.h> @@ -159,24 +160,18 @@ int QBitArray::count(bool on) const for (int i = 0; i < len; ++i) numBits += testBit(i); #else - // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel const quint8 *bits = reinterpret_cast<const quint8 *>(d.data()) + 1; while (len >= 32) { quint32 v = quint32(bits[0]) | (quint32(bits[1]) << 8) | (quint32(bits[2]) << 16) | (quint32(bits[3]) << 24); - quint32 c = ((v & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; - c += (((v & 0xfff000) >> 12) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; - c += ((v >> 24) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; len -= 32; bits += 4; - numBits += int(c); + numBits += int(qPopulationCount(v)); } while (len >= 24) { quint32 v = quint32(bits[0]) | (quint32(bits[1]) << 8) | (quint32(bits[2]) << 16); - quint32 c = ((v & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; - c += (((v & 0xfff000) >> 12) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; len -= 24; bits += 3; - numBits += int(c); + numBits += int(qPopulationCount(v)); } while (len >= 0) { if (bits[len / 8] & (1 << ((len - 1) & 7))) diff --git a/src/platformsupport/eglconvenience/qxlibeglintegration.cpp b/src/platformsupport/eglconvenience/qxlibeglintegration.cpp index 58f24c0a04..80453816fc 100644 --- a/src/platformsupport/eglconvenience/qxlibeglintegration.cpp +++ b/src/platformsupport/eglconvenience/qxlibeglintegration.cpp @@ -41,17 +41,6 @@ #include "qxlibeglintegration_p.h" -static int countBits(unsigned long mask) -{ - int count = 0; - while (mask != 0) { - if (mask & 1) - ++count; - mask >>= 1; - } - return count; -} - VisualID QXlibEglIntegration::getCompatibleVisualId(Display *display, EGLDisplay eglDisplay, EGLConfig config) { VisualID visualId = 0; @@ -92,9 +81,9 @@ VisualID QXlibEglIntegration::getCompatibleVisualId(Display *display, EGLDisplay return visualId; } - int visualRedSize = countBits(chosenVisualInfo->red_mask); - int visualGreenSize = countBits(chosenVisualInfo->green_mask); - int visualBlueSize = countBits(chosenVisualInfo->blue_mask); + int visualRedSize = qPopulationCount(chosenVisualInfo->red_mask); + int visualGreenSize = qPopulationCount(chosenVisualInfo->green_mask); + int visualBlueSize = qPopulationCount(chosenVisualInfo->blue_mask); int visualAlphaSize = -1; // Need XRender to tell us the alpha channel size bool visualMatchesConfig = false; diff --git a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp index 72bf5c58ca..c18ba4d05c 100644 --- a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp +++ b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp @@ -78,10 +78,22 @@ private slots: void qCountContainer() const; void binaryFindOnLargeContainer() const; -#if Q_TEST_PERFORMANCE + void popCount08_data() { popCount_data_impl(sizeof(quint8 )); } + void popCount16_data() { popCount_data_impl(sizeof(quint16)); } + void popCount32_data() { popCount_data_impl(sizeof(quint32)); } + void popCount64_data() { popCount_data_impl(sizeof(quint64)); } + void popCount08() { popCount_impl<quint8 >(); } + void popCount16() { popCount_impl<quint16>(); } + void popCount32() { popCount_impl<quint32>(); } + void popCount64() { popCount_impl<quint64>(); } + private: +#if Q_TEST_PERFORMANCE void performance(); #endif + void popCount_data_impl(size_t sizeof_T_Int); + template <typename T_Int> + void popCount_impl(); }; class TestInt @@ -1007,6 +1019,72 @@ void tst_QAlgorithms::binaryFindOnLargeContainer() const QCOMPARE(foundIt.pos(), 1073987655); } +// alternative implementation of qPopulationCount for comparison: +static const uint bitsSetInNibble[] = { + 0, 1, 1, 2, 1, 2, 2, 3, + 1, 2, 2, 3, 2, 3, 3, 4, +}; +Q_STATIC_ASSERT(sizeof bitsSetInNibble / sizeof *bitsSetInNibble == 16); + +static Q_DECL_CONSTEXPR uint bitsSetInByte(quint8 byte) +{ + return bitsSetInNibble[byte & 0xF] + bitsSetInNibble[byte >> 4]; +} +static Q_DECL_CONSTEXPR uint bitsSetInShort(quint16 word) +{ + return bitsSetInByte(word & 0xFF) + bitsSetInByte(word >> 8); +} +static Q_DECL_CONSTEXPR uint bitsSetInInt(quint32 word) +{ + return bitsSetInShort(word & 0xFFFF) + bitsSetInShort(word >> 16); +} +static Q_DECL_CONSTEXPR uint bitsSetInInt64(quint64 word) +{ + return bitsSetInInt(word & 0xFFFFFFFF) + bitsSetInInt(word >> 32); +} + + +void tst_QAlgorithms::popCount_data_impl(size_t sizeof_T_Int) +{ + using namespace QTest; + addColumn<quint64>("input"); + addColumn<uint>("expected"); + + for (uint i = 0; i < UCHAR_MAX; ++i) { + const uchar byte = static_cast<uchar>(i); + const uint bits = bitsSetInByte(byte); + const quint64 value = static_cast<quint64>(byte); + const quint64 input = value << ((i % sizeof_T_Int) * 8U); + newRow(qPrintable(QString().sprintf("0x%016llx", input))) << input << bits; + } + + // and some random ones: + if (sizeof_T_Int >= 8) + for (size_t i = 0; i < 1000; ++i) { + const quint64 input = quint64(qrand()) << 32 | quint32(qrand()); + newRow(qPrintable(QString().sprintf("0x%016llx", input))) << input << bitsSetInInt64(input); + } + else if (sizeof_T_Int >= 2) + for (size_t i = 0; i < 1000 ; ++i) { + const quint32 input = qrand(); + if (sizeof_T_Int >= 4) + newRow(qPrintable(QString().sprintf("0x%08x", input))) << quint64(input) << bitsSetInInt(input); + else + newRow(qPrintable(QString().sprintf("0x%04x", quint16(input & 0xFFFF)))) << quint64(input & 0xFFFF) << bitsSetInShort(input & 0xFFFF); + } +} + +template <typename T_Int> +void tst_QAlgorithms::popCount_impl() +{ + QFETCH(quint64, input); + QFETCH(uint, expected); + + const T_Int value = static_cast<T_Int>(input); + + QCOMPARE(qPopulationCount(value), expected); +} + QTEST_APPLESS_MAIN(tst_QAlgorithms) #include "tst_qalgorithms.moc" |