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 /src/corelib/tools/qbitarray.cpp | |
| 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>
Diffstat (limited to 'src/corelib/tools/qbitarray.cpp')
| -rw-r--r-- | src/corelib/tools/qbitarray.cpp | 11 |
1 files changed, 3 insertions, 8 deletions
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))) |