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>

3 files changed, 72 insertions, 8 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)))