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>

7 files changed, 214 insertions, 62 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));
 
diff --git a/src/gui/opengl/qopengltexturecache.cpp b/src/gui/opengl/qopengltexturecache.cpp
index f4aa29ac0f..d8b44016b9 100644
--- a/src/gui/opengl/qopengltexturecache.cpp
+++ b/src/gui/opengl/qopengltexturecache.cpp
@@ -40,6 +40,7 @@
 ****************************************************************************/
 
 #include "qopengltexturecache_p.h"
+#include <qmath.h>
 #include <qopenglfunctions.h>
 #include <private/qopenglcontext_p.h>
 #include <private/qimagepixmapcleanuphooks_p.h>
@@ -129,20 +130,6 @@ GLuint QOpenGLTextureCache::bindTexture(QOpenGLContext *context, const QPixmap &
     return id;
 }
 
-// returns the highest number closest to v, which is a power of 2
-// NB! assumes 32 bit ints
-static int qt_next_power_of_two(int v)
-{
-    v--;
-    v |= v >> 1;
-    v |= v >> 2;
-    v |= v >> 4;
-    v |= v >> 8;
-    v |= v >> 16;
-    ++v;
-    return v;
-}
-
 GLuint QOpenGLTextureCache::bindTexture(QOpenGLContext *context, const QImage &image)
 {
     if (image.isNull())
@@ -164,8 +151,8 @@ GLuint QOpenGLTextureCache::bindTexture(QOpenGLContext *context, const QImage &i
         // Scale the pixmap if needed. GL textures needs to have the
         // dimensions 2^n+2(border) x 2^m+2(border), unless we're using GL
         // 2.0 or use the GL_TEXTURE_RECTANGLE texture target
-        int tx_w = qt_next_power_of_two(image.width());
-        int tx_h = qt_next_power_of_two(image.height());
+        int tx_w = qNextPowerOfTwo(image.width() - 1);
+        int tx_h = qNextPowerOfTwo(image.height() - 1);
         if (tx_w != image.width() || tx_h != image.height()) {
             img = img.scaled(tx_w, tx_h);
         }
diff --git a/src/gui/painting/qtextureglyphcache.cpp b/src/gui/painting/qtextureglyphcache.cpp
index 83edeb41a6..fb8c23835d 100644
--- a/src/gui/painting/qtextureglyphcache.cpp
+++ b/src/gui/painting/qtextureglyphcache.cpp
@@ -50,20 +50,6 @@ QT_BEGIN_NAMESPACE
 
 // #define CACHE_DEBUG
 
-// returns the highest number closest to v, which is a power of 2
-// NB! assumes 32 bit ints
-static inline int qt_next_power_of_two(int v)
-{
-    v--;
-    v |= v >> 1;
-    v |= v >> 2;
-    v |= v >> 4;
-    v |= v >> 8;
-    v |= v >> 16;
-    ++v;
-    return v;
-}
-
 int QTextureGlyphCache::calculateSubPixelPositionCount(glyph_t glyph) const
 {
     // Test 12 different subpixel positions since it factors into 3*4 so it gives
@@ -199,7 +185,7 @@ bool QTextureGlyphCache::populate(QFontEngine *fontEngine, int numGlyphs, const
         if (fontEngine->maxCharWidth() <= QT_DEFAULT_TEXTURE_GLYPH_CACHE_WIDTH)
             m_w = QT_DEFAULT_TEXTURE_GLYPH_CACHE_WIDTH;
         else
-            m_w = qt_next_power_of_two(fontEngine->maxCharWidth());
+            m_w = qNextPowerOfTwo(qCeil(fontEngine->maxCharWidth()) - 1);
     }
 
     // now actually use the coords and paint the wanted glyps into cache.
@@ -261,9 +247,9 @@ void QTextureGlyphCache::fillInPendingGlyphs()
 
     if (isNull() || requiredHeight > m_h || requiredWidth > m_w) {
         if (isNull())
-            createCache(qt_next_power_of_two(requiredWidth), qt_next_power_of_two(requiredHeight));
+            createCache(qNextPowerOfTwo(requiredWidth - 1), qNextPowerOfTwo(requiredHeight - 1));
         else
-            resizeCache(qt_next_power_of_two(requiredWidth), qt_next_power_of_two(requiredHeight));
+            resizeCache(qNextPowerOfTwo(requiredWidth - 1), qNextPowerOfTwo(requiredHeight - 1));
     }
 
     {
diff --git a/src/opengl/qgl.cpp b/src/opengl/qgl.cpp
index 8223536608..d1417cfde5 100644
--- a/src/opengl/qgl.cpp
+++ b/src/opengl/qgl.cpp
@@ -1868,20 +1868,6 @@ QImage qt_gl_read_texture(const QSize &size, bool alpha_format, bool include_alp
     return img;
 }
 
-// returns the highest number closest to v, which is a power of 2
-// NB! assumes 32 bit ints
-int qt_next_power_of_two(int v)
-{
-    v--;
-    v |= v >> 1;
-    v |= v >> 2;
-    v |= v >> 4;
-    v |= v >> 8;
-    v |= v >> 16;
-    ++v;
-    return v;
-}
-
 Q_GLOBAL_STATIC(QGLTextureCache, qt_gl_texture_cache)
 
 QGLTextureCache::QGLTextureCache()
@@ -2462,8 +2448,8 @@ QGLTexture* QGLContextPrivate::bindTexture(const QImage &image, GLenum target, G
     // Scale the pixmap if needed. GL textures needs to have the
     // dimensions 2^n+2(border) x 2^m+2(border), unless we're using GL
     // 2.0 or use the GL_TEXTURE_RECTANGLE texture target
-    int tx_w = qt_next_power_of_two(image.width());
-    int tx_h = qt_next_power_of_two(image.height());
+    int tx_w = qNextPowerOfTwo(image.width() - 1);
+    int tx_h = qNextPowerOfTwo(image.height() - 1);
 
     QImage img = image;
 
diff --git a/tests/auto/corelib/kernel/qmath/tst_qmath.cpp b/tests/auto/corelib/kernel/qmath/tst_qmath.cpp
index 24934ac138..8d6964cbcd 100644
--- a/tests/auto/corelib/kernel/qmath/tst_qmath.cpp
+++ b/tests/auto/corelib/kernel/qmath/tst_qmath.cpp
@@ -54,6 +54,14 @@ private slots:
     void degreesToRadians();
     void radiansToDegrees_data();
     void radiansToDegrees();
+    void qNextPowerOfTwo32S_data();
+    void qNextPowerOfTwo32S();
+    void qNextPowerOfTwo64S_data();
+    void qNextPowerOfTwo64S();
+    void qNextPowerOfTwo32U_data();
+    void qNextPowerOfTwo32U();
+    void qNextPowerOfTwo64U_data();
+    void qNextPowerOfTwo64U();
 };
 
 void tst_QMath::fastSinCos()
@@ -137,6 +145,117 @@ void tst_QMath::radiansToDegrees()
     QCOMPARE(qRadiansToDegrees(radiansDouble), degreesDouble);
 }
 
+
+void tst_QMath::qNextPowerOfTwo32S_data()
+{
+    QTest::addColumn<qint32>("input");
+    QTest::addColumn<quint32>("output");
+
+    QTest::newRow("0") << 0 << 1U;
+    QTest::newRow("1") << 1 << 2U;
+    QTest::newRow("2") << 2 << 4U;
+    QTest::newRow("17") << 17 << 32U;
+    QTest::newRow("128") << 128 << 256U;
+    QTest::newRow("65535") << 65535 << 65536U;
+    QTest::newRow("65536") << 65536 << 131072U;
+    QTest::newRow("2^30") << (1 << 30) << (1U << 31);
+    QTest::newRow("2^30 + 1") << (1 << 30) + 1 << (1U << 31);
+    QTest::newRow("2^31 - 1") << 0x7FFFFFFF << (1U<<31);
+    QTest::newRow("-1") << -1 << 0U;
+    QTest::newRow("-128") << -128 << 0U;
+    QTest::newRow("-(2^31)") << int(0x80000000) << 0U;
+}
+
+void tst_QMath::qNextPowerOfTwo32S()
+{
+    QFETCH(qint32, input);
+    QFETCH(quint32, output);
+
+    QCOMPARE(qNextPowerOfTwo(input), output);
+}
+
+void tst_QMath::qNextPowerOfTwo32U_data()
+{
+    QTest::addColumn<quint32>("input");
+    QTest::addColumn<quint32>("output");
+
+    QTest::newRow("0") << 0U << 1U;
+    QTest::newRow("1") << 1U << 2U;
+    QTest::newRow("2") << 2U << 4U;
+    QTest::newRow("17") << 17U << 32U;
+    QTest::newRow("128") << 128U << 256U;
+    QTest::newRow("65535") << 65535U << 65536U;
+    QTest::newRow("65536") << 65536U << 131072U;
+    QTest::newRow("2^30") << (1U << 30) << (1U << 31);
+    QTest::newRow("2^30 + 1") << (1U << 30) + 1 << (1U << 31);
+    QTest::newRow("2^31 - 1") << 2147483647U << 2147483648U;
+    QTest::newRow("2^31") << 2147483648U << 0U;
+    QTest::newRow("2^31 + 1") << 2147483649U << 0U;
+}
+
+void tst_QMath::qNextPowerOfTwo32U()
+{
+    QFETCH(quint32, input);
+    QFETCH(quint32, output);
+
+    QCOMPARE(qNextPowerOfTwo(input), output);
+}
+
+void tst_QMath::qNextPowerOfTwo64S_data()
+{
+    QTest::addColumn<qint64>("input");
+    QTest::addColumn<quint64>("output");
+
+    QTest::newRow("0") << Q_INT64_C(0) << Q_UINT64_C(1);
+    QTest::newRow("1") << Q_INT64_C(1) << Q_UINT64_C(2);
+    QTest::newRow("2") << Q_INT64_C(2) << Q_UINT64_C(4);
+    QTest::newRow("17") << Q_INT64_C(17) << Q_UINT64_C(32);
+    QTest::newRow("128") << Q_INT64_C(128) << Q_UINT64_C(256);
+    QTest::newRow("65535") << Q_INT64_C(65535) << Q_UINT64_C(65536);
+    QTest::newRow("65536") << Q_INT64_C(65536) << Q_UINT64_C(131072);
+    QTest::newRow("2^31 - 1") << Q_INT64_C(2147483647) << Q_UINT64_C(0x80000000);
+    QTest::newRow("2^31") << Q_INT64_C(2147483648) << Q_UINT64_C(0x100000000);
+    QTest::newRow("2^31 + 1") << Q_INT64_C(2147483649) << Q_UINT64_C(0x100000000);
+    QTest::newRow("2^63 - 1") << Q_INT64_C(0x7FFFFFFFFFFFFFFF) << Q_UINT64_C(0x8000000000000000);
+    QTest::newRow("-1") << Q_INT64_C(-1) << Q_UINT64_C(0);
+    QTest::newRow("-128") << Q_INT64_C(-128) << Q_UINT64_C(0);
+    QTest::newRow("-(2^31)") << -Q_INT64_C(0x80000000) << Q_UINT64_C(0);
+    QTest::newRow("-(2^63)") << (qint64)Q_INT64_C(0x8000000000000000) << Q_UINT64_C(0);
+}
+
+void tst_QMath::qNextPowerOfTwo64S()
+{
+    QFETCH(qint64, input);
+    QFETCH(quint64, output);
+
+    QCOMPARE(qNextPowerOfTwo(input), output);
+}
+
+void tst_QMath::qNextPowerOfTwo64U_data()
+{
+    QTest::addColumn<quint64>("input");
+    QTest::addColumn<quint64>("output");
+
+    QTest::newRow("0") << Q_UINT64_C(0) << Q_UINT64_C(1);
+    QTest::newRow("1") << Q_UINT64_C(1) << Q_UINT64_C(2);
+    QTest::newRow("2") << Q_UINT64_C(2) << Q_UINT64_C(4);
+    QTest::newRow("17") << Q_UINT64_C(17) << Q_UINT64_C(32);
+    QTest::newRow("128") << Q_UINT64_C(128) << Q_UINT64_C(256);
+    QTest::newRow("65535") << Q_UINT64_C(65535) << Q_UINT64_C(65536);
+    QTest::newRow("65536") << Q_UINT64_C(65536) << Q_UINT64_C(131072);
+    QTest::newRow("2^63 - 1") << Q_UINT64_C(0x7FFFFFFFFFFFFFFF)  << Q_UINT64_C(0x8000000000000000);
+    QTest::newRow("2^63") << Q_UINT64_C(0x8000000000000000) << Q_UINT64_C(0);
+    QTest::newRow("2^63 + 1") << Q_UINT64_C(0x8000000000000001) << Q_UINT64_C(0);
+}
+
+void tst_QMath::qNextPowerOfTwo64U()
+{
+    QFETCH(quint64, input);
+    QFETCH(quint64, output);
+
+    QCOMPARE(qNextPowerOfTwo(input), output);
+}
+
 QTEST_APPLESS_MAIN(tst_QMath)
 
 #include "tst_qmath.moc"