[RFC] CryptoAPI & Compression

[Artem B. Bityuckiy]

Hello Herbert and others,

I'm working on cleaning-up the JFFS3 compression stuff. JFFS3 contains a
number of compressors which actually shouldn't be there as they are
platform-independent and generic. So we want to move them to the generic
part of the Linux kernel instead of storing them in fs/jffs2/. And we
were going to use CryptoAPI to access the compressors.

But I've hit on a problem - CryptoAPI's compression method isn't
flexible enough for us.

CryptoAPI's compress method is:

int crypto_compress(struct crypto_tfm *tfm,
const u8 *src, unsigned int slen,
u8 *dst, unsigned int *dlen);

*src - input data;
slen - input data length;
*dst - output data;
*dlen - on input - output buffer length, on output - the length of the
compressed data;

The crypto_compress() API call either compresses all the input data or
returns error.

In JFFS2 we need something more flexible. Te following is what we want:

int crypto_compress_ext(struct crypto_tfm *tfm,
const u8 *src, unsigned int *slen,
u8 *dst, unsigned int *dlen);

*src - input data;
*slen - on input - input data length, on output - the amount of data
that were actually compressed.
*dst - output data;
*dlen - on input - output buffer length, on output - the length of the
compressed data;

This would allow us (and we really need this) to provide a large input
data buffer, a small output data buffer and to ask the compressor to
compress as much input data as it can to fit (in the compressed form) to
the output buffer. To put it differently, we often have a large input,
and several smalloutput buffers, and we want to compress the input data
to them.

I offer to extend the CryptoAPI and add an "extended compress" API call
with the above mentioned capabilities. We might as well just change the
crypto_compress() and all its users.

Alternatively, we may create some kind of "Compression API" but I don't
like this idea...

Comments?
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to ***@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/



-------------------------------------------------------------------------------
Achtung: diese Newsgruppe ist eine unidirektional gegatete Mailingliste.
Antworten nur per Mail an die im Reply-To-Header angegebene Adresse.
Fragen zum Gateway -> ***@inka.de.
-------------------------------------------------------------------------------

[Herbert Xu]

Post by Artem B. Bityuckiy
I'm working on cleaning-up the JFFS3 compression stuff. JFFS3 contains a
number of compressors which actually shouldn't be there as they are
platform-independent and generic. So we want to move them to the generic
part of the Linux kernel instead of storing them in fs/jffs2/. And we
were going to use CryptoAPI to access the compressors.

Sounds good.

Post by Artem B. Bityuckiy
int crypto_compress_ext(struct crypto_tfm *tfm,
const u8 *src, unsigned int *slen,
u8 *dst, unsigned int *dlen);

Compressing part of the input could be significantly different from
compressing all of the input depending on the algorithm. In particular
it could be most costly to do so and/or result in worse compression.

So while I'm happy to add such an interface I think we should keep
crypto_comp_compress as well for full compression.

I've whipped up something quick and called it crypto_comp_pcompress.
How does this interface look to you?

Cheers,

[Artem B. Bityuckiy]

Post by Herbert Xu
I've whipped up something quick and called it crypto_comp_pcompress.
How does this interface look to you?

Thanks for the patch. At the first glance it looks OK. I'll try to use
it and add the deflate method which in fact is already implemented in
JFFS2. I'll send you my results.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to ***@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/



-------------------------------------------------------------------------------
Achtung: diese Newsgruppe ist eine unidirektional gegatete Mailingliste.
Antworten nur per Mail an die im Reply-To-Header angegebene Adresse.
Fragen zum Gateway -> ***@inka.de.
-------------------------------------------------------------------------------

[Artem B. Bityuckiy]

Post by Herbert Xu
I've whipped up something quick and called it crypto_comp_pcompress.
How does this interface look to you?

Hello Herbert,

I've done some work. Here are 2 patches:
1. pcompress-deflate-1.diff
2. uncompress-1.diff
(should be applied in that order). And I also imply your patch is
applied as well.

The first patch is the implementation of the deflate_pcompress()
function. It was ported from JFFS2 with some changes.
The second patch is my implementation of the deflate_decompr() function
and I'd like to hear some comments on this.

I made the changes to deflate_decompr() because the old version doesn't
work properly for me. There are 2 changes.

1. I've added the following code:

------------------------------------------------------------------------
if (slen > 2 && !(src[1] & PRESET_DICT) /* No preset dictionary */
&& ((src[0] & 0x0f) == Z_DEFLATED) /* Comp. method byte is OK */
&& !(((src[0] << 8) + src[1]) % 31)) { /* CMF*256 + FLG */
stream->next_in += 2;
stream->avail_in -= 2;
}
------------------------------------------------------------------------

This peace of code checks if there are 2 header bytes (see RFC-1950)
present in the stream to be inflated. If they are present, we should
skip them because we use a negative windowBits parameter when we
initialize inflate. When this "undocumented" feature is used, zlib
ignores the stream header and doesn't check the adler32 checksum (I've
found this roughly exploring the inflate source code). If we don't skip
the first 2 bytes, inflate will treat them as the part of the input data
and will work incorrectly.

I don't know how deflate_decompr() worked before, it shouldn't have
worked AFAICS. So, I'm in doubt and would like to see your or James'
comments.

2. I've removed the "strange" (for me) uncompress sequence:

------------------------------------------------------------------------
ret = zlib_inflate(stream, Z_SYNC_FLUSH);
/*
* Work around a bug in zlib, which sometimes wants to taste an extra
* byte when being used in the (undocumented) raw deflate mode.
* (From USAGI).
*/
if (ret == Z_OK && !stream->avail_in && stream->avail_out) {
u8 zerostuff = 0;
stream->next_in = &zerostuff;
stream->avail_in = 1;
ret = zlib_inflate(stream, Z_FINISH);
}
------------------------------------------------------------------------

and have changed it to the following:

------------------------------------------------------------------------
ret = zlib_inflate(stream, Z_FINISH);
if (ret != Z_STREAM_END)
return -EINVAL;
------------------------------------------------------------------------

I made this because the old sequence didn't uncompress data compressed
by my deflate_pcompress(). Frankly, I just don't understand the meaning
of that replaced part and changed it to what seems correct and obvious
for me. My argument is the documentation of zlib_inflate() from
include/linux/zlib.h:

------------------------------------------------------------------------
inflate() should normally be called until it returns Z_STREAM_END or an
error. However if all decompression is to be performed in a single step
(a single call of inflate), the parameter flush should be set to
Z_FINISH. In this case all pending input is processed and all pending
output is flushed; avail_out must be large enough to hold all the
uncompressed data.
------------------------------------------------------------------------

I don't know anything about the declared bug "(From USAGI)".
So I'd like to hear some comment on this as well.

Also I've simplified error handling a bit.

The stuff I'm sending works for me. I also run the tcrypt.c test module,
and the deflate/inflate tests passed.

[Herbert Xu]

Post by Artem B. Bityuckiy
The first patch is the implementation of the deflate_pcompress()

Thanks for the patch. I'll comment on the second patch later.

Are you sure that 12 bytes is enough for all cases? It would seem
to be safer to use the formula in deflateBound/compressBound from
later versions (> 1.2) of zlib to calculate the reserve.

Post by Artem B. Bityuckiy
+ while (stream->total_in < *slen
+ && stream->total_out < *dlen - DEFLATE_PCOMPR_RESERVE) {

We normally put the operator on the preceding line, i.e.,

while (foo &&
bar) {

Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <***@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to ***@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/



-------------------------------------------------------------------------------
Achtung: diese Newsgruppe ist eine unidirektional gegatete Mailingliste.
Antworten nur per Mail an die im Reply-To-Header angegebene Adresse.
Fragen zum Gateway -> ***@inka.de.
-------------------------------------------------------------------------------

[Artem B. Bityuckiy]

Post by Herbert Xu
Are you sure that 12 bytes is enough for all cases? It would seem
to be safer to use the formula in deflateBound/compressBound from
later versions (> 1.2) of zlib to calculate the reserve.

I'm not sure. David Woodhouse (the author) said that this is probably
enough in any case but a lot of time has gone since the code was written
and he doesn't remember for sure. I have also seen some magic number "12"
somewhere in zlib, but I'm not sure.

At least my practice shows that 12 is Ok for JFFS2 where we compress fewer
then 4K a a time. I'll explore this.

Post by Herbert Xu
We normally put the operator on the preceding line, i.e.,
while (foo &&
bar) {

If this is the the common practice for Linux, then OK. My argument is the
GNU Coding style which recommends:

----------------------------------------------------------------------
When you split an expression into multiple lines, split it before an
operator, not after one. Here is the right way:

if (foo_this_is_long && bar > win (x, y, z)
&& remaining_condition)
----------------------------------------------------------------------

while the Linux coding style doesn't mention this AFAIR. And of course,
Linux doesn't have to obey that rule.

Ok. This is not the final patch but more like RFC and I can re-format and
re-send it. :-) Please, feel free to re-format it as you would like
yourself.

And one more thing I wanted to offer. In the
deflate_[compress|uncompress|pcompress] functions we call the
zlib_[in|de]flateReset function at the beginning. This is OK. But when we
unload the deflate module we don't call zlib_[in|de]flateEnd to free all
the zlib internal data. It looks like a bug for me. Please, consider the
attached patch.

--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.