Implement ordered dithering for image format conversions

QImage::convertToFormat was ignoring its conversion flag argument, only
performing dithering when converting to indexed formats.

This patch updates the documentation and implements ordered dithering
for other conversions.

Change-Id: I807353d61669694185b7e595ef262d80d9fbb3f1
Reviewed-by: Gunnar Sletta <gunnar@sletta.org>

6 files changed, 222 insertions, 53 deletions

diff --git a/src/corelib/global/qnamespace.qdoc b/src/corelib/global/qnamespace.qdoc
index dfa7112043..03ebc1d106 100644
--- a/src/corelib/global/qnamespace.qdoc
+++ b/src/corelib/global/qnamespace.qdoc
@@ -737,27 +737,25 @@
     \value MonoOnly The pixmap becomes monochrome. If necessary,
            it is dithered using the chosen dithering algorithm.
 
-    Dithering mode preference for RGB channels:
+    Dithering mode preference:
 
-    \value DiffuseDither (default) - A high-quality dither.
-    \value OrderedDither A faster, more ordered dither.
+    \value DiffuseDither (default) - A high-quality dither using error diffusion.
+    \value OrderedDither A faster, ordered dither.
     \value ThresholdDither No dithering; closest color is used.
 
-    Dithering mode preference for alpha channel:
+    Dithering mode preference for 1-bit alpha masks:
 
     \value ThresholdAlphaDither (default) - No dithering.
-    \value OrderedAlphaDither A faster, more ordered dither.
-    \value DiffuseAlphaDither A high-quality dither.
+    \value OrderedAlphaDither A faster, ordered dither.
+    \value DiffuseAlphaDither A high-quality dither using error diffusion.
     \omitvalue NoAlpha
 
     Color matching versus dithering preference:
 
-    \value PreferDither (default when converting to a pixmap) - Always dither
-           32-bit images when the image is converted to 8 bits.
-    \value AvoidDither (default when converting for the purpose of saving to
-           file) - Dither 32-bit images only if the image has more than 256
-           colors and it is being converted to 8 bits.
-    \omitvalue AutoDither
+    \value PreferDither Always dither images when converting to smaller color-spaces.
+    \value AvoidDither Only dither to indexed formats if the source image uses more
+           different colors than the size of the color table of the destination format.
+    \value AutoDither (default) - Only dither when down-converting to 1 or 8-bit indexed formats.
 
     \omitvalue ColorMode_Mask
     \omitvalue Dither_Mask
diff --git a/src/gui/image/qimage_conversions.cpp b/src/gui/image/qimage_conversions.cpp
index d2f92dbe73..41b4807671 100644
--- a/src/gui/image/qimage_conversions.cpp
+++ b/src/gui/image/qimage_conversions.cpp
@@ -128,7 +128,7 @@ extern const uint *QT_FASTCALL convertRGB32FromARGB32PM_sse4(uint *buffer, const
                                                              const QVector<QRgb> *, QDitherInfo *);
 #endif
 
-void convert_generic(QImageData *dest, const QImageData *src, Qt::ImageConversionFlags)
+void convert_generic(QImageData *dest, const QImageData *src, Qt::ImageConversionFlags flags)
 {
     // Cannot be used with indexed formats.
     Q_ASSERT(dest->format > QImage::Format_Indexed8);
@@ -159,14 +159,20 @@ void convert_generic(QImageData *dest, const QImageData *src, Qt::ImageConversio
                 convertFromARGB32PM = convertRGB32FromARGB32PM;
         }
     }
+    QDitherInfo dither;
+    QDitherInfo *ditherPtr = 0;
+    if ((flags & Qt::PreferDither) && (flags & Qt::Dither_Mask) != Qt::ThresholdDither)
+        ditherPtr = &dither;
 
     for (int y = 0; y < src->height; ++y) {
+        dither.y = y;
         int x = 0;
         while (x < src->width) {
+            dither.x = x;
             int l = qMin(src->width - x, buffer_size);
             const uint *ptr = fetch(buffer, srcData, x, l);
-            ptr = convertToARGB32PM(buffer, ptr, l, 0, 0);
-            ptr = convertFromARGB32PM(buffer, ptr, l, 0, 0);
+            ptr = convertToARGB32PM(buffer, ptr, l, 0, ditherPtr);
+            ptr = convertFromARGB32PM(buffer, ptr, l, 0, ditherPtr);
             store(destData, ptr, x, l);
             x += l;
         }
@@ -175,7 +181,7 @@ void convert_generic(QImageData *dest, const QImageData *src, Qt::ImageConversio
     }
 }
 
-bool convert_generic_inplace(QImageData *data, QImage::Format dst_format, Qt::ImageConversionFlags)
+bool convert_generic_inplace(QImageData *data, QImage::Format dst_format, Qt::ImageConversionFlags flags)
 {
     // Cannot be used with indexed formats or between formats with different pixel depths.
     Q_ASSERT(dst_format > QImage::Format_Indexed8);
@@ -208,14 +214,20 @@ bool convert_generic_inplace(QImageData *data, QImage::Format dst_format, Qt::Im
                 convertFromARGB32PM = convertRGB32FromARGB32PM;
         }
     }
+    QDitherInfo dither;
+    QDitherInfo *ditherPtr = 0;
+    if ((flags & Qt::PreferDither) && (flags & Qt::Dither_Mask) != Qt::ThresholdDither)
+        ditherPtr = &dither;
 
     for (int y = 0; y < data->height; ++y) {
+        dither.y = y;
         int x = 0;
         while (x < data->width) {
+            dither.x = x;
             int l = qMin(data->width - x, buffer_size);
             const uint *ptr = fetch(buffer, srcData, x, l);
-            ptr = convertToARGB32PM(buffer, ptr, l, 0, 0);
-            ptr = convertFromARGB32PM(buffer, ptr, l, 0, 0);
+            ptr = convertToARGB32PM(buffer, ptr, l, 0, ditherPtr);
+            ptr = convertFromARGB32PM(buffer, ptr, l, 0, ditherPtr);
             // The conversions might be passthrough and not use the buffer, in that case we are already done.
             if (srcData != (const uchar*)ptr)
                 store(srcData, ptr, x, l);
diff --git a/src/gui/image/qpixmap_raster.cpp b/src/gui/image/qpixmap_raster.cpp
index 7cf8d026d1..45047f556c 100644
--- a/src/gui/image/qpixmap_raster.cpp
+++ b/src/gui/image/qpixmap_raster.cpp
@@ -335,7 +335,7 @@ void QRasterPlatformPixmap::createPixmapForImage(QImage &sourceImage, Qt::ImageC
     } else if (inPlace && sourceImage.d->convertInPlace(format, flags)) {
         image = sourceImage;
     } else {
-        image = sourceImage.convertToFormat(format);
+        image = sourceImage.convertToFormat(format, flags);
     }
 
     if (image.d) {
diff --git a/src/gui/painting/qdrawhelper.cpp b/src/gui/painting/qdrawhelper.cpp
index 716ac94654..b452019251 100644
--- a/src/gui/painting/qdrawhelper.cpp
+++ b/src/gui/painting/qdrawhelper.cpp
@@ -336,48 +336,110 @@ static const QRgba64 *QT_FASTCALL convertARGBPMToARGB64PM(QRgba64 *buffer, const
 
 template<QImage::Format Format, bool fromRGB>
 static const uint *QT_FASTCALL convertRGBFromARGB32PM(uint *buffer, const uint *src, int count,
-                                                      const QVector<QRgb> *, QDitherInfo *)
+                                                      const QVector<QRgb> *, QDitherInfo *dither)
 {
-    Q_CONSTEXPR uint rMask = ((1 << redWidth<Format>()) - 1);
-    Q_CONSTEXPR uint gMask = ((1 << greenWidth<Format>()) - 1);
-    Q_CONSTEXPR uint bMask = ((1 << blueWidth<Format>()) - 1);
+    Q_CONSTEXPR uchar rWidth = redWidth<Format>();
+    Q_CONSTEXPR uchar gWidth = greenWidth<Format>();
+    Q_CONSTEXPR uchar bWidth = blueWidth<Format>();
 
-    Q_CONSTEXPR uchar rRightShift = 24 - redWidth<Format>();
-    Q_CONSTEXPR uchar gRightShift = 16 - greenWidth<Format>();
-    Q_CONSTEXPR uchar bRightShift =  8 - blueWidth<Format>();
+    // RGB32 -> RGB888 is not a precision loss.
+    if (!dither || (rWidth == 8 && gWidth == 8 && bWidth == 8)) {
+        Q_CONSTEXPR uint rMask = (1 << rWidth) - 1;
+        Q_CONSTEXPR uint gMask = (1 << gWidth) - 1;
+        Q_CONSTEXPR uint bMask = (1 << bWidth) - 1;
 
-    for (int i = 0; i < count; ++i) {
-        const uint c = fromRGB ? src[i] : qUnpremultiply(src[i]);
-        const uint r = ((c >> rRightShift) & rMask) << redShift<Format>();
-        const uint g = ((c >> gRightShift) & gMask) << greenShift<Format>();
-        const uint b = ((c >> bRightShift) & bMask) << blueShift<Format>();
-        buffer[i] = r | g | b;
+        Q_CONSTEXPR uchar rRightShift = 24 - rWidth;
+        Q_CONSTEXPR uchar gRightShift = 16 - gWidth;
+        Q_CONSTEXPR uchar bRightShift =  8 - bWidth;
+
+        for (int i = 0; i < count; ++i) {
+            const uint c = fromRGB ? src[i] : qUnpremultiply(src[i]);
+            const uint r = ((c >> rRightShift) & rMask) << redShift<Format>();
+            const uint g = ((c >> gRightShift) & gMask) << greenShift<Format>();
+            const uint b = ((c >> bRightShift) & bMask) << blueShift<Format>();
+            buffer[i] = r | g | b;
+        }
+    } else {
+        // We do ordered dither by using a rounding conversion, but instead of
+        // adding half of input precision, we add the adjusted result from the
+        // bayer matrix before narrowing.
+        // Note: Rounding conversion in itself is different from the naive
+        // conversion we do above for non-dithering.
+        const uint *bayer_line = qt_bayer_matrix[dither->y & 15];
+        for (int i = 0; i < count; ++i) {
+            const uint c = fromRGB ? src[i] : qUnpremultiply(src[i]);
+            const int d = bayer_line[(dither->x + i) & 15];
+            const int dr = d - ((d + 1) >> rWidth);
+            const int dg = d - ((d + 1) >> gWidth);
+            const int db = d - ((d + 1) >> bWidth);
+            int r = qRed(c);
+            int g = qGreen(c);
+            int b = qBlue(c);
+            r = (r + ((dr - r) >> rWidth) + 1) >> (8 - rWidth);
+            g = (g + ((dg - g) >> gWidth) + 1) >> (8 - gWidth);
+            b = (b + ((db - b) >> bWidth) + 1) >> (8 - bWidth);
+            buffer[i] = (r << redShift<Format>())
+                      | (g << greenShift<Format>())
+                      | (b << blueShift<Format>());
+        }
     }
     return buffer;
 }
 
 template<QImage::Format Format, bool fromRGB>
 static const uint *QT_FASTCALL convertARGBPMFromARGB32PM(uint *buffer, const uint *src, int count,
-                                                         const QVector<QRgb> *, QDitherInfo *)
+                                                         const QVector<QRgb> *, QDitherInfo *dither)
 {
-    Q_CONSTEXPR uint aMask = ((1 << alphaWidth<Format>()) - 1);
-    Q_CONSTEXPR uint rMask = ((1 << redWidth<Format>()) - 1);
-    Q_CONSTEXPR uint gMask = ((1 << greenWidth<Format>()) - 1);
-    Q_CONSTEXPR uint bMask = ((1 << blueWidth<Format>()) - 1);
+    Q_CONSTEXPR uchar aWidth = alphaWidth<Format>();
+    Q_CONSTEXPR uchar rWidth = redWidth<Format>();
+    Q_CONSTEXPR uchar gWidth = greenWidth<Format>();
+    Q_CONSTEXPR uchar bWidth = blueWidth<Format>();
 
-    Q_CONSTEXPR uchar aRightShift = 32 - alphaWidth<Format>();
-    Q_CONSTEXPR uchar rRightShift = 24 - redWidth<Format>();
-    Q_CONSTEXPR uchar gRightShift = 16 - greenWidth<Format>();
-    Q_CONSTEXPR uchar bRightShift =  8 - blueWidth<Format>();
+    if (!dither) {
+        Q_CONSTEXPR uint aMask = (1 << aWidth) - 1;
+        Q_CONSTEXPR uint rMask = (1 << rWidth) - 1;
+        Q_CONSTEXPR uint gMask = (1 << gWidth) - 1;
+        Q_CONSTEXPR uint bMask = (1 << bWidth) - 1;
 
-    Q_CONSTEXPR uint aOpaque = (0xff & aMask) << alphaShift<Format>();
-    for (int i = 0; i < count; ++i) {
-        const uint c = src[i];
-        const uint a = fromRGB ? aOpaque : (((c >> aRightShift) & aMask) << alphaShift<Format>());
-        const uint r = ((c >> rRightShift) & rMask) << redShift<Format>();
-        const uint g = ((c >> gRightShift) & gMask) << greenShift<Format>();
-        const uint b = ((c >> bRightShift) & bMask) << blueShift<Format>();
-        buffer[i] = a | r | g | b;
+        Q_CONSTEXPR uchar aRightShift = 32 - aWidth;
+        Q_CONSTEXPR uchar rRightShift = 24 - rWidth;
+        Q_CONSTEXPR uchar gRightShift = 16 - gWidth;
+        Q_CONSTEXPR uchar bRightShift =  8 - bWidth;
+
+        Q_CONSTEXPR uint aOpaque = aMask << alphaShift<Format>();
+        for (int i = 0; i < count; ++i) {
+            const uint c = src[i];
+            const uint a = fromRGB ? aOpaque : (((c >> aRightShift) & aMask) << alphaShift<Format>());
+            const uint r = ((c >> rRightShift) & rMask) << redShift<Format>();
+            const uint g = ((c >> gRightShift) & gMask) << greenShift<Format>();
+            const uint b = ((c >> bRightShift) & bMask) << blueShift<Format>();
+            buffer[i] = a | r | g | b;
+        }
+    } else {
+        const uint *bayer_line = qt_bayer_matrix[dither->y & 15];
+        for (int i = 0; i < count; ++i) {
+            const uint c = src[i];
+            const int d = bayer_line[(dither->x + i) & 15];
+            const int da = d - ((d + 1) >> aWidth);
+            const int dr = d - ((d + 1) >> rWidth);
+            const int dg = d - ((d + 1) >> gWidth);
+            const int db = d - ((d + 1) >> bWidth);
+            int a = qAlpha(c);
+            int r = qRed(c);
+            int g = qGreen(c);
+            int b = qBlue(c);
+            if (fromRGB)
+                a = (1 << aWidth) - 1;
+            else
+                a = (a + ((da - a) >> aWidth) + 1) >> (8 - aWidth);
+            r = (r + ((dr - r) >> rWidth) + 1) >> (8 - rWidth);
+            g = (g + ((dg - g) >> gWidth) + 1) >> (8 - gWidth);
+            b = (b + ((db - b) >> bWidth) + 1) >> (8 - bWidth);
+            buffer[i] = (a << alphaShift<Format>())
+                      | (r << redShift<Format>())
+                      | (g << greenShift<Format>())
+                      | (b << blueShift<Format>());
+        }
     }
     return buffer;
 }
@@ -640,10 +702,28 @@ static const uint *QT_FASTCALL convertRGBXFromARGB32PM(uint *buffer, const uint
 
 template<QtPixelOrder PixelOrder>
 static const uint *QT_FASTCALL convertA2RGB30PMToARGB32PM(uint *buffer, const uint *src, int count,
-                                                          const QVector<QRgb> *, QDitherInfo *)
+                                                          const QVector<QRgb> *, QDitherInfo *dither)
 {
-    for (int i = 0; i < count; ++i)
-        buffer[i] = qConvertA2rgb30ToArgb32<PixelOrder>(src[i]);
+    if (!dither) {
+        for (int i = 0; i < count; ++i)
+            buffer[i] = qConvertA2rgb30ToArgb32<PixelOrder>(src[i]);
+    } else {
+        for (int i = 0; i < count; ++i) {
+            const uint c = src[i];
+            short d10 = (qt_bayer_matrix[dither->y & 15][(dither->x + i) & 15] << 2);
+            short a10 = (c >> 30) * 0x155;
+            short r10 = ((c >> 20) & 0x3ff);
+            short g10 = ((c >> 10) & 0x3ff);
+            short b10 = (c & 0x3ff);
+            if (PixelOrder == PixelOrderBGR)
+                std::swap(r10, b10);
+            short a8 = (a10 + ((d10 - a10) >> 8)) >> 2;
+            short r8 = (r10 + ((d10 - r10) >> 8)) >> 2;
+            short g8 = (g10 + ((d10 - g10) >> 8)) >> 2;
+            short b8 = (b10 + ((d10 - b10) >> 8)) >> 2;
+            buffer[i] = qRgba(r8, g8, b8, a8);
+        }
+    }
     return buffer;
 }
 
diff --git a/src/gui/painting/qdrawhelper_p.h b/src/gui/painting/qdrawhelper_p.h
index a163037205..fa550541d3 100644
--- a/src/gui/painting/qdrawhelper_p.h
+++ b/src/gui/painting/qdrawhelper_p.h
@@ -1171,7 +1171,10 @@ inline int comp_func_Plus_one_pixel(uint d, const uint s)
 #undef MIX
 #undef AMIX
 
-struct QDitherInfo;
+struct QDitherInfo {
+    int x;
+    int y;
+};
 
 typedef const uint *(QT_FASTCALL *ConvertFunc)(uint *buffer, const uint *src, int count,
                                                const QVector<QRgb> *clut, QDitherInfo *dither);
diff --git a/tests/auto/gui/image/qimage/tst_qimage.cpp b/tests/auto/gui/image/qimage/tst_qimage.cpp
index cc75846fdd..90b88d0992 100644
--- a/tests/auto/gui/image/qimage/tst_qimage.cpp
+++ b/tests/auto/gui/image/qimage/tst_qimage.cpp
@@ -195,6 +195,9 @@ private slots:
     void pixelColor();
     void pixel();
 
+    void ditherGradient_data();
+    void ditherGradient();
+
 private:
     const QString m_prefix;
 };
@@ -3106,5 +3109,78 @@ void tst_QImage::pixel()
     }
 }
 
+void tst_QImage::ditherGradient_data()
+{
+    QTest::addColumn<QImage>("image");
+    QTest::addColumn<QImage::Format>("format");
+    QTest::addColumn<int>("flags");
+    QTest::addColumn<int>("minimumExpectedGradient");
+
+    QImage rgb32(256, 16, QImage::Format_RGB32);
+    QLinearGradient gradient(QRectF(rgb32.rect()).topLeft(), QRectF(rgb32.rect()).topRight());
+    gradient.setColorAt(0.0, QColor(0, 0, 0));
+    gradient.setColorAt(1.0, QColor(255, 255, 255));
+    QPainter p;
+    p.begin(&rgb32);
+    p.fillRect(rgb32.rect(), gradient);
+    p.end();
+
+    QTest::newRow("rgb32 -> rgb444 (no dither)") << rgb32 << QImage::Format_RGB444 << 0 << 16;
+    QTest::newRow("rgb32 -> rgb444 (dithering)") << rgb32 << QImage::Format_RGB444 << int(Qt::PreferDither | Qt::OrderedDither) << 33;
+    QTest::newRow("rgb32 -> argb4444pm (dithering)") << rgb32 << QImage::Format_ARGB4444_Premultiplied << int(Qt::PreferDither | Qt::OrderedDither) << 33;
+    QTest::newRow("rgb32 -> rgb16 (no dither)") << rgb32 << QImage::Format_RGB16 << 0 << 32;
+    QTest::newRow("rgb32 -> rgb16 (dithering)") << rgb32 << QImage::Format_RGB16 << int(Qt::PreferDither | Qt::OrderedDither) << 65;
+    QTest::newRow("rgb32 -> rgb666 (no dither)") << rgb32 << QImage::Format_RGB666 << 0 << 64;
+    QTest::newRow("rgb32 -> rgb666 (dithering)") << rgb32 << QImage::Format_RGB666 << int(Qt::PreferDither | Qt::OrderedDither) << 129;
+
+    // Test we get the same results for opaque input in the ARGBPM implementation.
+    rgb32 = qMove(rgb32).convertToFormat(QImage::Format_ARGB32_Premultiplied);
+    QTest::newRow("argb32pm -> argb4444pm (no dither)") << rgb32 << QImage::Format_ARGB4444_Premultiplied << 0 << 16;
+    QTest::newRow("argb32pm -> rgb444 (dithering)") << rgb32 << QImage::Format_RGB444 << int(Qt::PreferDither | Qt::OrderedDither) << 33;
+    QTest::newRow("argb32pm -> argb4444pm (dithering)") << rgb32 << QImage::Format_ARGB4444_Premultiplied << int(Qt::PreferDither | Qt::OrderedDither) << 33;
+    QTest::newRow("argb32pm -> argb8565pm (no dither)") << rgb32 << QImage::Format_ARGB8565_Premultiplied << 0 << 32;
+    QTest::newRow("argb32pm -> argb8565pm (dithering)") << rgb32 << QImage::Format_ARGB8565_Premultiplied << int(Qt::PreferDither | Qt::OrderedDither) << 65;
+    QTest::newRow("argb32pm -> argb6666pm (no dither)") << rgb32 << QImage::Format_ARGB6666_Premultiplied << 0 << 64;
+    QTest::newRow("argb32pm -> argb6666pm (dithering)") << rgb32 << QImage::Format_ARGB6666_Premultiplied << int(Qt::PreferDither | Qt::OrderedDither) << 129;
+
+    QImage rgb30(1024, 16, QImage::Format_RGB30);
+    QLinearGradient gradient30(QRectF(rgb30.rect()).topLeft(), QRectF(rgb30.rect()).topRight());
+    gradient30.setColorAt(0.0, QColor(0, 0, 0));
+    gradient30.setColorAt(1.0, QColor(255, 255, 255));
+    p.begin(&rgb30);
+    p.fillRect(rgb30.rect(), gradient30);
+    p.end();
+
+    QTest::newRow("rgb30 -> rgb32 (no dither)") << rgb30 << QImage::Format_RGB32 << 0 << 256;
+    QTest::newRow("rgb30 -> rgb32 (dithering)") << rgb30 << QImage::Format_RGB32 << int(Qt::PreferDither | Qt::OrderedDither) << 513;
+    QTest::newRow("rgb30 -> rgb888 (no dither)") << rgb30 << QImage::Format_RGB888 << 0 << 256;
+    QTest::newRow("rgb30 -> rgb888 (dithering)") << rgb30 << QImage::Format_RGB888 << int(Qt::PreferDither | Qt::OrderedDither) << 513;
+}
+
+void tst_QImage::ditherGradient()
+{
+    QFETCH(QImage, image);
+    QFETCH(QImage::Format, format);
+    QFETCH(int, flags);
+    QFETCH(int, minimumExpectedGradient);
+
+    QImage converted = image.convertToFormat(format, (Qt::ImageConversionFlags)flags);
+    int observedGradientSteps = 0;
+    int lastTotal = -1;
+    for (int i = 0; i < converted.width(); ++i) {
+        int total = 0;
+        for (int j = 0; j < converted.height(); ++j) {
+            uint c = converted.pixel(i, j);
+            QCOMPARE(qAlpha(c), 255);
+            total += qRed(c);
+        }
+        if (total > lastTotal) {
+            observedGradientSteps++;
+            lastTotal = total;
+        }
+    }
+    QVERIFY(observedGradientSteps >= minimumExpectedGradient);
+}
+
 QTEST_GUILESS_MAIN(tst_QImage)
 #include "tst_qimage.moc"