RCC: Add support for Zstandard compression

[ChangeLog][RCC] RCC now supports compressing content using the
Zstandard (https://zstd.net) algorithm. Compared to zlib, it compresses
better for the same CPU time, so this algorithm is the default. To go
back to the previous algorithm, pass command-line option
--compress-algo=zlib. Compression levels range from 1 (fastest, least
compression) to 19 (slowest, best compression). Level 0 tells the
library to choose an implementation-defined default.
\
The default compression level is "heuristic" (level -1): under this
mode, RCC will attempt a very fast compression (level 1) and check if
the file was sufficiently compressed. If it was, then RCC will compress
again using an implementation-defined level.

The following are the 4 biggest files we store as resources in qtbase:
 Orig Size Name
   2197605 src/corelib/mimetypes/mime/packages/freedesktop.org.xml
   2462423 tests/auto/corelib/tools/qchar/data/NormalizationTest.txt
   6878748 tests/auto/other/qcomplextext/data/BidiCharacterTest.txt
   7959972 tests/auto/other/qcomplextext/data/BidiTest.txt

The current RCC (zlib, level -1 "default" and level 9), produces for
those files:
                        L(-1)    Compr.   L9      Compr.    Decomp.
 Name                   Ratio  CPU time   Ratio  CPU time   CPU time
BidiCharacterTest.txt   16.9:1  106.1ms   17.2:1  789.3ms     5.1ms
BidiTest.txt             6.3:1  228.0ms    6.1:1 1646.3ms    10.9ms
freedesktop.org.xml      7.0:1   17.5ms    7.1:1   53.6ms     2.6ms
NormalizationTest.txt    5.8:1   41.2ms    5.9:1  256.4ms     3.4ms

Zstandard produces the following for levels 1 ("check"), 14 ("store")
and 19 ("best"):
                       L1     Compr.   L14    Compr.    L19    Compr.     Decomp
 Name                  Ratio  time     Ratio  time      Ratio  CPU time   time
BidiCharacterTest.txt  15.8:1  8.0ms   26.1:1 168.9ms   49.2:1 2504.7ms    3.8ms
BidiTest.txt            8.2:1 17.0ms    8.7:1 323.9ms   14.9:1 1700.9ms   12.1ms
freedesktop.org.xml     6.7:1  4.0ms    8.7:1  63.3ms    9.5:1  642.5ms    1.7ms
NormalizationTest.txt   5.7:1  5.0ms    7.5:1  54.0ms    8.4:1  447.3ms    3.0ms

This shows use of zstd at the default RCC level settings always produce
smaller outputs compared to the current zlib-based defaults, with
roughly 50% CPU increase. It also produces better results at less CPU
time than the best compression zlib has to offer.

More importantly, the decompression time reduces in all cases (the
numbers listed are for max compression, with slightly better results for
the defaults).

For the sake of comparison, the same files compressed with libxz at
levels 3 and 6:
                        Level 3         Level 6           Decompr.
 Name                   Ratio   CPU     Ratio  CPU        time
BidiCharacterTest.txt   28.5:1 109.1ms  42.9:1 1390.5ms   16.7ms
BidiTest.txt            10.7:1 281.0ms  18.4:1 2333.1ms   43.6ms
freedesktop.org.xml      9.1:1  62.0ms  10.2:1  499.1ms   12.0ms
NormalizationTest.txt   10.2:1  75.5ms  13.2:1  417.6ms   14.7ms

LZMA at level 3 consumes roughly the same CPU time as Zstd at level 14
and produces incrementally smaller results, but the decompression time
increases considerably. It's not a good trade-off for the Qt resource
system.

Change-Id: I343f2beed55440a7ac0bfffd1562d754bd71d964
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@qt.io>

4 files changed, 95 insertions, 3 deletions

diff --git a/src/tools/rcc/main.cpp b/src/tools/rcc/main.cpp
index 0defb03057..71836b81bd 100644
--- a/src/tools/rcc/main.cpp
+++ b/src/tools/rcc/main.cpp
@@ -128,7 +128,11 @@ int runRcc(int argc, char *argv[])
     QCommandLineOption rootOption(QStringLiteral("root"), QStringLiteral("Prefix resource access path with root path."), QStringLiteral("path"));
     parser.addOption(rootOption);
 
-#if !defined(QT_NO_COMPRESS)
+#if QT_CONFIG(zstd) && !defined(QT_NO_COMPRESS)
+#  define ALGOS     "[zstd], zlib, none"
+#elif QT_CONFIG(zstd)
+#  define ALGOS     "[zstd], none"
+#elif !defined(QT_NO_COMPRESS)
 #  define ALGOS     "[zlib], none"
 #else
 #  define ALGOS     "[none]"
diff --git a/src/tools/rcc/rcc.cpp b/src/tools/rcc/rcc.cpp
index a73220d05c..dfa62cea1b 100644
--- a/src/tools/rcc/rcc.cpp
+++ b/src/tools/rcc/rcc.cpp
@@ -42,6 +42,10 @@
 
 #include <algorithm>
 
+#if QT_CONFIG(zstd)
+#  include <zstd.h>
+#endif
+
 // Note: A copy of this file is used in Qt Designer (qttools/src/designer/src/lib/shared/rcc.cpp)
 
 QT_BEGIN_NAMESPACE
@@ -49,10 +53,14 @@ QT_BEGIN_NAMESPACE
 enum {
     CONSTANT_USENAMESPACE = 1,
     CONSTANT_COMPRESSLEVEL_DEFAULT = -1,
+    CONSTANT_ZSTDCOMPRESSLEVEL_CHECK = 1,   // Zstd level to check if compressing is a good idea
+    CONSTANT_ZSTDCOMPRESSLEVEL_STORE = 14,  // Zstd level to actually store the data
     CONSTANT_COMPRESSTHRESHOLD_DEFAULT = 70
 };
 
-#if !defined(QT_NO_COMPRESS)
+#if QT_CONFIG(zstd)
+#  define CONSTANT_COMPRESSALGO_DEFAULT     RCCResourceLibrary::CompressionAlgorithm::Zstd
+#elif !defined(QT_NO_COMPRESS)
 #  define CONSTANT_COMPRESSALGO_DEFAULT     RCCResourceLibrary::CompressionAlgorithm::Zlib
 #else
 #  define CONSTANT_COMPRESSALGO_DEFAULT     RCCResourceLibrary::CompressionAlgorithm::None
@@ -97,7 +105,8 @@ public:
         // must match qresource.cpp
         NoFlags = 0x00,
         Compressed = 0x01,
-        Directory = 0x02
+        Directory = 0x02,
+        CompressedZstd = 0x04
     };
 
     RCCFileInfo(const QString &name = QString(), const QFileInfo &fileInfo = QFileInfo(),
@@ -248,6 +257,49 @@ qint64 RCCFileInfo::writeDataBlob(RCCResourceLibrary &lib, qint64 offset,
 
     // Check if compression is useful for this file
     if (data.size() != 0) {
+#if QT_CONFIG(zstd)
+        if (m_compressAlgo == RCCResourceLibrary::CompressionAlgorithm::Zstd) {
+            if (lib.m_zstdCCtx == nullptr)
+                lib.m_zstdCCtx = ZSTD_createCCtx();
+            qsizetype size = data.size();
+            size = ZSTD_COMPRESSBOUND(size);
+
+            int compressLevel = m_compressLevel;
+            if (compressLevel < 0)
+                compressLevel = CONSTANT_ZSTDCOMPRESSLEVEL_CHECK;
+
+            QByteArray compressed(size, Qt::Uninitialized);
+            char *dst = const_cast<char *>(compressed.constData());
+            size_t n = ZSTD_compressCCtx(lib.m_zstdCCtx, dst, size,
+                                         data.constData(), data.size(),
+                                         compressLevel);
+            if (n * 100.0 < data.size() * 1.0 * (100 - m_compressThreshold) ) {
+                // compressing is worth it
+                if (m_compressLevel < 0) {
+                    // heuristic compression, so recompress
+                    n = ZSTD_compressCCtx(lib.m_zstdCCtx, dst, size,
+                                          data.constData(), data.size(),
+                                          CONSTANT_ZSTDCOMPRESSLEVEL_STORE);
+                }
+                if (ZSTD_isError(n)) {
+                    QString msg = QString::fromLatin1("%1: error: compression with zstd failed: %2\n")
+                            .arg(m_name, QString::fromUtf8(ZSTD_getErrorName(n)));
+                    lib.m_errorDevice->write(msg.toUtf8());
+                } else if (lib.verbose()) {
+                    QString msg = QString::fromLatin1("%1: note: compressed using zstd (%2 -> %3)\n")
+                            .arg(m_name).arg(data.size()).arg(n);
+                    lib.m_errorDevice->write(msg.toUtf8());
+                }
+
+                m_flags |= CompressedZstd;
+                data = std::move(compressed);
+                data.truncate(n);
+            } else if (lib.verbose()) {
+                QString msg = QString::fromLatin1("%1: note: not compressed\n").arg(m_name);
+                lib.m_errorDevice->write(msg.toUtf8());
+            }
+        }
+#endif
 #ifndef QT_NO_COMPRESS
         if (m_compressAlgo == RCCResourceLibrary::CompressionAlgorithm::Zlib) {
             QByteArray compressed =
@@ -384,11 +436,17 @@ RCCResourceLibrary::RCCResourceLibrary(quint8 formatVersion)
     m_formatVersion(formatVersion)
 {
     m_out.reserve(30 * 1000 * 1000);
+#if QT_CONFIG(zstd)
+    m_zstdCCtx = nullptr;
+#endif
 }
 
 RCCResourceLibrary::~RCCResourceLibrary()
 {
     delete m_root;
+#if QT_CONFIG(zstd)
+    ZSTD_freeCCtx(m_zstdCCtx);
+#endif
 }
 
 enum RCCXmlTag {
@@ -772,6 +830,12 @@ RCCResourceLibrary::CompressionAlgorithm RCCResourceLibrary::parseCompressionAlg
 #else
         return CompressionAlgorithm::Zlib;
 #endif
+    } else if (value == QLatin1String("zstd")) {
+#if QT_CONFIG(zstd)
+        return CompressionAlgorithm::Zstd;
+#else
+        *errorMsg = QLatin1String("Zstandard support not compiled in");
+#endif
     } else if (value != QLatin1String("none")) {
         *errorMsg = QString::fromLatin1("Unknown compression algorithm '%1'").arg(value);
     }
@@ -791,6 +855,12 @@ int RCCResourceLibrary::parseCompressionLevel(CompressionAlgorithm algo, const Q
             if (c >= 1 && c <= 9)
                 return c;
             break;
+        case CompressionAlgorithm::Zstd:
+#if QT_CONFIG(zstd)
+            if (c >= 0 && c <= ZSTD_maxCLevel())
+                return c;
+#endif
+            break;
         }
     }
 
diff --git a/src/tools/rcc/rcc.h b/src/tools/rcc/rcc.h
index 5c6823e56f..fe8ed21fb3 100644
--- a/src/tools/rcc/rcc.h
+++ b/src/tools/rcc/rcc.h
@@ -36,6 +36,8 @@
 #include <qhash.h>
 #include <qstring.h>
 
+typedef struct ZSTD_CCtx_s ZSTD_CCtx;
+
 QT_BEGIN_NAMESPACE
 
 class RCCFileInfo;
@@ -80,6 +82,7 @@ public:
 
     enum class CompressionAlgorithm {
         Zlib,
+        Zstd,
 
         None = -1
     };
@@ -138,6 +141,10 @@ private:
     void writeByteArray(const QByteArray &);
     void write(const char *, int len);
 
+#if QT_CONFIG(zstd)
+    ZSTD_CCtx *m_zstdCCtx;
+#endif
+
     const Strings m_strings;
     RCCFileInfo *m_root;
     QStringList m_fileNames;
diff --git a/src/tools/rcc/rcc.pro b/src/tools/rcc/rcc.pro
index 208ec54a73..ae55b5d8af 100644
--- a/src/tools/rcc/rcc.pro
+++ b/src/tools/rcc/rcc.pro
@@ -8,3 +8,14 @@ SOURCES += main.cpp
 
 QMAKE_TARGET_DESCRIPTION = "Qt Resource Compiler"
 load(qt_tool)
+
+# RCC is a bootstrapped tool, so qglobal.h #includes qconfig-bootstrapped.h
+# and that has a #define saying zstd isn't present (for qresource.cpp, which is
+# part of the bootstrap lib). So we inform the presence of the feature in the
+# command-line.
+qtConfig(zstd):!cross_compile {
+    DEFINES += QT_FEATURE_zstd=1
+    QMAKE_USE_PRIVATE += zstd
+} else {
+    DEFINES += QT_FEATURE_zstd=-1
+}