Re: [PATCH v6 13/15] crypto: iaa - Add support for deflate-iaa-canned compression algorithm

[Tom Zanussi]

Hi Herbert,
 
Sorry for the delayed response, I was out on vacation.

On Fri, 2023-06-16 at 18:55 +0800, Herbert Xu wrote:
> On Mon, Jun 05, 2023 at 03:15:34PM -0500, Tom Zanussi wrote:
> > Add support for a 'canned' compression mode using the IAA
> > compression
> > mode in-kernel API.
> > 
> > The IAA 'canned' compression mode is added alongside the existing
> > 'fixed' compression mode and a crypto algorithm named
> > 'deflate-iaa-canned' is registered using it.
> 
> So you said that canned is not compatible with the generic deflate
> algorithm.  Does that mean that there is no way for it to decompress
> something compressed by the generic deflate algorithm, and vice versa
> its compressed output cannot be decompressed by generic deflate?
> 

Yes, for the most part...

In canned mode, the header portion of the deflate block is stored
separately from the body of the compressed data, but the header and
body are both compliant with the deflate standard.  It can be
decompressed with any software deflate decompressor by performing
a	pre-processing step (basically prepending a deflate block header and
the description of the codes before the first symbol).  The current
code doesn’t do that, but it could.
 
IAA canned mode can’t however decompress output generated by generic
deflate, that is true.
 
Below [1] are some more clarifying details in case you’re interested.

> We don't add an algorithm to the Crypto API if the only
> implementation
> is by hardware.  IOW if you are adding a new algorithm, then a
> software version must be the first patch.
> 
 
One possibility for supporting canned mode might be to, as mentioned
above, change the code to prepend the deflate block header and
description of the codes before the first symbol so that it could be
decompressed using only generic deflate in software; in that case,
there would never be a worry about the canned data compressed by the
IAA hardware being unrecoverable in case of hardware failure.  I’m not
sure if that would be acceptable or how that would work within the
crypto framework - please let us know your thoughts on that.
 
If that’s not an option, then I’d propose just dropping the canned
algorithm for now and resubmitting with fixed mode only for a v7 of
this series, and later following up with an additional series
consisting of this patch and a software-only implementation of canned
mode, as you suggest. Does that make sense?  Please let us know your
thoughts...
 
Thanks,
 
Tom
 
 
[1] [From Vinodh Gopal] Deflate https://www.ietf.org/rfc/rfc1951.txt is
an LZ77 style algorithm combined with Huffman encoding. LZ77 algorithms
look for matching strings within a history-window. Deflate defines that
maximal window to be 32KB. A typical software implementation such as
zlib/gzip with default settings, would use 32KB as the history-window.
IAA is a light-weight implementation that only supports a history-
window of 4KB. There are advanced settings in many Software
libraries/applications to limit history when compressing; if we limit a
Software compressor to 4KB history, then any input compressed with such
Software can always be decompressed by IAA. A special exception is that
Software compression with default settings that works on a data input
whose size is <= 4KB will always generate an output that can be
decompressed with IAA; since the original input itself is no bigger
than 4KB, the larger window of 32KB becomes irrelevant. This is the
case with the ZSWAP/ZRAM usage and 4KB page compression.
 
The LZ77 symbols in a deflate block can be encoded with 2 styles of
Huffman codes. In the fixed mode, a predefined Huffman code from the
standard is used for the encoding. The deflate block header specifies
the type of block as fixed or dynamic (or stored, for incompressible
data stored as raw bytes). Dynamic Huffman codes require a compact
description of the code used for that block, before the encoded symbols
representing the compressed data. IAA supports these types of codes.
The choice of codes is made during the compression; the decompressor
parses the deflate block header to determine the type of codes and does
not need such information from another context.
 
In addition, IAA defines a "canned mode", where the code is stored
separately from the compressed bitstream. Here the compressed blob
would start at the very first encoded symbol. The decompressor needs
additional context to know what codes were used by the compressor. This
context is provided to the IAA decompressor when it needs to process a
canned-mode compressed stream. This can also be decompressed with any
software deflate decompressor, by performing a pre-processing step
(basically prepending a deflate block header and the description of the
codes before the first symbol)

> Thanks,