erofs-utils: add a built-in DEFLATE compressor
As Apple documentation written "If you require interoperability with
non-Apple devices, use COMPRESSION_ZLIB. [1]", DEFLATE is a popular
generic-purpose compression algorithm for a quite long time (many
advanced formats like zlib, gzip, zip, png are all based on that),
which is made of LZ77 as well as Huffman coding, fully documented as
RFC1951 [2] and quite easy to understand, implement.
There are several hardware on-market DEFLATE accelerators as well,
such as (s390) DFLTCC, (Intel) IAA/QAT, (HiSilicon) ZIP accelerator,
etc. Therefore, it's useful to support DEFLATE compression in order
to use these for async I/Os and get benefits from these.
Since there is _no fixed-sized output DEFLATE compression appoach_
available in public (fitblk is somewhat ineffective) and the original
zlib is quite slowly developping, let's work out one for our use cases.
Fortunately, it's only less than 1.5kLOC with lazy matching to just
match the full zlib abilities. Besides, near-optimal block splitting
(based on price function) doesn't support since it's no rush to us.
In the future, there might be more built-in optimizers landed to
fulfill our needs even further (especially for other popular algorithms
without native fixed-sized output support). In addition, I'd be quite
happy to see more popular encoders to support native fixed-sized output
compression too.
[1] https://developer.apple.com/documentation/compression/compression_algorithm
[2] https://datatracker.ietf.org/doc/html/rfc1951
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20230710110251.89464-2-hsiangkao@linux.alibaba.com
2 files changed
