Unduplicate the implementations of next power of two

Qtbase contains four identical implementations of next power of two,
these should be shared and the implementation made available to other
qt modules, as it is also used many places outside of qtbase.

[ChangeLog][QtCore][QtMath] Introduced qNextPowerOfTwo methods.

Change-Id: Id23fbe5ad6bae647b30d5a4212c0330e48a50278
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

3 files changed, 87 insertions, 13 deletions

diff --git a/src/corelib/kernel/qmath.h b/src/corelib/kernel/qmath.h
index 21e23b9eb0..e29285a0d7 100644
--- a/src/corelib/kernel/qmath.h
+++ b/src/corelib/kernel/qmath.h
@@ -49,6 +49,7 @@
 #include <math.h>
 
 #include <QtCore/qglobal.h>
+#include <QtCore/qcompilerdetection.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -286,6 +287,57 @@ Q_DECL_CONSTEXPR inline double qRadiansToDegrees(double radians)
     return radians * (180 / M_PI);
 }
 
+
+#if defined(Q_CC_GNU)
+// clz instructions exist in at least MIPS, ARM, PowerPC and X86, so we can assume this builtin always maps to an efficient instruction.
+inline quint32 qNextPowerOfTwo(quint32 v)
+{
+    if (v == 0)
+        return 1;
+    return 2U << (31 ^ __builtin_clz(v));
+}
+
+inline quint64 qNextPowerOfTwo(quint64 v)
+{
+    if (v == 0)
+        return 1;
+    return Q_UINT64_C(2) << (63 ^ __builtin_clzll(v));
+}
+#else
+inline quint32 qNextPowerOfTwo(quint32 v)
+{
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    ++v;
+    return v;
+}
+
+inline quint64 qNextPowerOfTwo(quint64 v)
+{
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v |= v >> 32;
+    ++v;
+    return v;
+}
+#endif
+
+inline quint32 qNextPowerOfTwo(qint32 v)
+{
+    return qNextPowerOfTwo(quint32(v));
+}
+
+inline quint64 qNextPowerOfTwo(qint64 v)
+{
+    return qNextPowerOfTwo(quint64(v));
+}
+
 QT_END_NAMESPACE
 
 #endif // QMATH_H
diff --git a/src/corelib/kernel/qmath.qdoc b/src/corelib/kernel/qmath.qdoc
index 04dbbb0a3b..430a420eeb 100644
--- a/src/corelib/kernel/qmath.qdoc
+++ b/src/corelib/kernel/qmath.qdoc
@@ -215,4 +215,37 @@
     \snippet code/src_corelib_kernel_qmath.cpp 3
 
     \sa qDegreesToRadians()
+
+/*!
+    \fn quint32 qNextPowerOfTwo(quint32 value)
+    \relates <QtMath>
+    \since 5.4
+
+    This function returns the nearest power of two greater than \a value. For 0 it returns 1, and for values larger than or equal to 2^31 it returns 0.
+*/
+
+/*!
+    \fn quint32 qNextPowerOfTwo(qint32 value)
+    \relates <QtMath>
+    \since 5.4
+    \overload
+
+    This function returns the nearest power of two greater than \a value. For negative values it returns 0.
+*/
+
+/*!
+    \fn quint64 qNextPowerOfTwo(quint64 value)
+    \relates <QtMath>
+    \since 5.4
+
+    This function returns the nearest power of two greater than \a value. For 0 it returns 1, and for values larger than or equal to 2^63 it returns 0.
+*/
+
+/*!
+    \fn quint64 qNextPowerOfTwo(qint64 value)
+    \relates <QtMath>
+    \since 5.4
+    \overload
+
+    This function returns the nearest power of two greater than \a value. For negative values it returns 0.
 */
diff --git a/src/corelib/tools/qbytearray.cpp b/src/corelib/tools/qbytearray.cpp
index 7ca47961c0..52af67c86a 100644
--- a/src/corelib/tools/qbytearray.cpp
+++ b/src/corelib/tools/qbytearray.cpp
@@ -48,6 +48,7 @@
 #include "qlocale_p.h"
 #include "qscopedpointer.h"
 #include <qdatastream.h>
+#include <qmath.h>
 
 #ifndef QT_NO_COMPRESS
 #include <zlib.h>
@@ -72,19 +73,7 @@ int qAllocMore(int alloc, int extra) Q_DECL_NOTHROW
     Q_ASSERT(alloc >= 0 && extra >= 0);
     Q_ASSERT_X(alloc < (1 << 30) - extra, "qAllocMore", "Requested size is too large!");
 
-    unsigned nalloc = alloc + extra;
-
-    // Round up to next power of 2
-
-    // Assuming container is growing, always overshoot
-    //--nalloc;
-
-    nalloc |= nalloc >> 1;
-    nalloc |= nalloc >> 2;
-    nalloc |= nalloc >> 4;
-    nalloc |= nalloc >> 8;
-    nalloc |= nalloc >> 16;
-    ++nalloc;
+    unsigned nalloc = qNextPowerOfTwo(alloc + extra);
 
     Q_ASSERT(nalloc > unsigned(alloc + extra));