I think we could use this way first for the new Zstd support (if they don't have
bandwidth to add a offical fixed-sized output approach), but considering deflate
algorithm is quite easy for me to understand so at least I could have a simple
built-in one to avoid external dependency (mainly considering zlib since it's
quite outdated). Since EROFS is actually offline compression so the compressed
data correctness can always be checked in advance before image release.
Writing an optimized compressor, especially one that implements high compression
levels, is very hard. Are you sure it's something you want to implement and
maintain in erofs-utils?
Also I have more ideas to optimize the last symbol from matchfinders (even lazy
matching) for fixed-sized output approaches to get even better compression
ratios (especially for smaller filesystem cluster like 4kb.)
Yes, there are some tricks that compressors that natively support
fixed-size-output mode could use in order to avoid redundant work.
smart way (binary search + heuristics). Also, it would easily work with every
compressor, and it would always produce the optimal input size.
I wrote a proof-of-concept patch that implements this idea in the benchmark
program in libdeflate. It finds the optimal input size in about 8 attempts on
average for a target output size of 4096, or about 13 for a target output size
of 65536. Note, if an optimal solution is not needed, it could be sped up
slightly by stopping when the output size is at, or just under (if desired), the
target output size. Also keep in mind that any compression level can be used.
The full code I tested is currently at
https://github.com/ebiggers/libdeflate/tree/fixed-output-size, but below is the
actual algorithm:
If libdeflate officically supports this mode, I'm very happy to integrate
libdeflate in this way as an alternative encoder (if you could merge this), and
if the compression speed is improved, I could switch it to the default encoder
then. In the other words, I really hope there could be an official deflate
encoder to support this mode as well. Also I think the in-kernel zlib
decompression is somewhat slow just due to some non-technical reasons, I might
need to improve this eveutually but it's no rush for us compared to support
DEFLATE format first as well.
/*
* Compresses the largest prefix of 'in', with maximum size 'in_nbytes', whose
* compressed output is at most 'target_output_size' bytes. The compressed
size
* is returned as the return value, and the uncompressed size is returned in
* *actual_in_nbytes_ret. The output buffer 'out' has size
'out_nbytes_avail',
* which should be at least 'target_output_size + 9'. 'tmpbuf' must be a
buffer
* the same size as 'out'.
*/
static size_t
do_compress_withfixedoutputsize(struct compressor *c,
const u8 *in, size_t in_nbytes,
u8 *out, size_t out_nbytes_avail,
size_t target_output_size,
size_t last_uncompressed_size,
u8 *tmpbuf,
size_t *actual_in_nbytes_ret)
{
size_t l = 0; /* largest input that fits so far */
size_t l_csize = 0;
size_t r = in_nbytes + 1; /* smallest input that doesn't fit so far */
size_t m;
if (last_uncompressed_size)
m = last_uncompressed_size * 15 / 16;
else
m = target_output_size * 4;
for (;;) {
size_t csize;
m = MAX(m, l + 1);
m = MIN(m, r - 1);
csize = do_compress(c, in, m, tmpbuf, out_nbytes_avail);
if (csize > 0 && csize <= target_output_size) {
/* Fits */
memcpy(out, tmpbuf, csize);
l = m;
l_csize = csize;
if (r <= l + 1)
break;
/*
* Estimate needed input prefix size based on current
* compression ratio.
*/
m = (target_output_size * m) / csize;
} else {
/* Doesn't fit */
r = m;
if (r <= l + 1)
break;
m = (l + r) / 2;
}
}
*actual_in_nbytes_ret = l;
return l_csize;
}
What do you think?
Thank you for the time and your efforts, I much appreciate if it could be
supported so I could add a alternative encoder for this.
Native fixed-size-output size support in libdeflate is something I'll think
about. However, the point I'm making is that it's unclear how valuable native
fixed-size-output size support in compressors is, given that the search
algorithm I described above actually seems to work fairly well, and it can
produce the optimal solution.
Here's a quick proof of concept patch for mkfs.erofs:
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 553b387..f58a684 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -45,3 +45,4 @@ liberofs_la_SOURCES += compressor_liblzma.c
endif
liberofs_la_SOURCES += kite_deflate.c compressor_deflate.c
+liberofs_la_LDFLAGS = -ldeflate
diff --git a/lib/compressor_deflate.c b/lib/compressor_deflate.c
index ad76b7c..d7a5e90 100644
--- a/lib/compressor_deflate.c
+++ b/lib/compressor_deflate.c
@@ -6,6 +6,7 @@
#include "erofs/internal.h"
#include "erofs/print.h"
#include "erofs/config.h"
+#include "libdeflate.h"
#include "compressor.h"
void *kite_deflate_init(int level, unsigned int dict_size);
@@ -13,16 +14,64 @@ void kite_deflate_end(void *s);
int kite_deflate_destsize(void *s, const u8 *in, u8 *out,
unsigned int *srcsize, unsigned int target_dstsize);
+#define USE_LIBDEFLATE
+
static int deflate_compress_destsize(const struct erofs_compress *c,
const void *src, unsigned int *srcsize,
void *dst, unsigned int dstsize)
{
+#ifdef USE_LIBDEFLATE
+ static size_t last_uncompressed_size = 0;
+ size_t l = 0; /* largest input that fits so far */
+ size_t l_csize = 0;
+ size_t r = *srcsize + 1; /* smallest input that doesn't fit so far */
+ size_t m;
+ u8 tmpbuf[dstsize + 9];
+
+ if (last_uncompressed_size)
+ m = last_uncompressed_size * 15 / 16;
+ else
+ m = dstsize * 4;
+ for (;;) {
+ size_t csize;
+
+ m = max(m, l + 1);
+ m = min(m, r - 1);
+
+ csize = libdeflate_deflate_compress(c->private_data, src, m,
tmpbuf, dstsize + 9);
+ /*printf("Tried %zu => %zu\n", m, csize);*/
+ if (csize > 0 && csize <= dstsize) {
+ /* Fits */
+ memcpy(dst, tmpbuf, csize);
+ l = m;
+ l_csize = csize;
+ if (r <= l + 1 || csize + (22 -
2*(int)c->compression_level) >= dstsize)
+ break;
+ /*
+ * Estimate needed input prefix size based on current
+ * compression ratio.
+ */
+ m = (dstsize * m) / csize;
+ } else {
+ /* Doesn't fit */
+ r = m;
+ if (r <= l + 1)
+ break;
+ m = (l + r) / 2;
+ }
+ }
+ /*printf("Choosing %zu => %zu\n", l, l_csize);*/
+ *srcsize = l;
+ last_uncompressed_size = l;
+ return l_csize;
+#else
int rc = kite_deflate_destsize(c->private_data, src, dst,
srcsize, dstsize);
if (rc <= 0)
return -EFAULT;
return rc;
+#endif
}
static int compressor_deflate_exit(struct erofs_compress *c)
@@ -30,7 +79,11 @@ static int compressor_deflate_exit(struct erofs_compress *c)
if (!c->private_data)
return -EINVAL;
+#ifdef USE_LIBDEFLATE
+ libdeflate_free_compressor(c->private_data);
+#else
kite_deflate_end(c->private_data);
+#endif
return 0;
}
@@ -47,8 +100,13 @@ static int compressor_deflate_init(struct erofs_compress *c)
static int erofs_compressor_deflate_setlevel(struct erofs_compress *c,
int compression_level)
{
- void *s;
+ if (compression_level < 0)
+ compression_level = erofs_compressor_deflate.default_level;
+#ifdef USE_LIBDEFLATE
+ libdeflate_free_compressor(c->private_data);
+ c->private_data = libdeflate_alloc_compressor(compression_level);
+#else
if (c->private_data) {
kite_deflate_end(c->private_data);
c->private_data = NULL;
@@ -57,11 +115,13 @@ static int erofs_compressor_deflate_setlevel(struct
erofs_compress *c,
if (compression_level < 0)
compression_level = erofs_compressor_deflate.default_level;
- s = kite_deflate_init(compression_level, cfg.c_dict_size);
+ void *s = kite_deflate_init(compression_level, cfg.c_dict_size);
if (IS_ERR(s))
return PTR_ERR(s);
c->private_data = s;
+#endif
+
c->compression_level = compression_level;
return 0;
}
@@ -69,7 +129,11 @@ static int erofs_compressor_deflate_setlevel(struct
erofs_compress *c,
const struct erofs_compressor erofs_compressor_deflate = {
.name = "deflate",
.default_level = 1,
+#ifdef USE_LIBDEFLATE
+ .best_level = 12,
+#else
.best_level = 9,
+#endif
.init = compressor_deflate_init,
.exit = compressor_deflate_exit,
.setlevel = erofs_compressor_deflate_setlevel,
Here are some quick benchmarks I did of mkfs.erofs showing the size of the
resulting filesystem and the time it took for mkfs.erofs to run:
-zdeflate,1
kite_deflate: 10772480 bytes in 0.474s
libdeflate: 10366976 bytes in 0.468s
-zdeflate,3
kite_deflate: 10203136 bytes in 0.511s
libdeflate: 10092544 bytes in 0.702s
-zdeflate,5
kite_deflate: 10080256 bytes in 0.596s
libdeflate: 9973760 bytes in 0.896s
-zdeflate,6
kite_deflate: 9977856 bytes in 0.650s
libdeflate: 9936896 bytes in 0.981s
-zdeflate,7
kite_deflate: 9969664 bytes in 0.690s
libdeflate: 9920512 bytes in 1.187s
-zdeflate,9
kite_deflate: 9945088 bytes in 0.986s
libdeflate: 9871360 bytes in 2.041s
-zdeflate,12
kite_deflate: N/A
libdeflate: 9740288 bytes in 28.080s
So it seems my "naive" search algorithm, when combined with libdeflate, actually
does about as well as kite_deflate... Plus it automatically brings in support
for higher compression levels.
