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.
Hi Artem:
On Fri, Mar 25, 2005 at 04:08:20PM +0000, Artem B. Bityuckiy wrote:
>
> 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.
> 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);
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,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Sat, 2005-03-26 at 15:44 +1100, Herbert Xu wrote:
> 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.
On Sat, 2005-03-26 at 15:44 +1100, Herbert Xu wrote:
> 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.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Hi Artem:
On Mon, Mar 28, 2005 at 05:22:36PM +0000, Artem B. Bityuckiy wrote:
>
> 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.
> + 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~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
> 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.
> 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.
Hi Artem:
On Tue, Mar 29, 2005 at 12:55:11PM +0100, Artem B. Bityuckiy wrote:
>
> 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.
The crypto API needs to operate on buffers that's bigger than that so
we need to have a correct upper bound the maximum expansion.
> > 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:
The GNU coding style is completely different from Linux.
> 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.
Please reformat it when you fix up the overhead calculation.
> 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.
Good catch. I'll apply this one.
Thanks,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Mon, Mar 28, 2005 at 05:22:36PM +0000, Artem B. Bityuckiy wrote:
>
> 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;
> }
> ------------------------------------------------------------------------
The reason you need to add this is because the window bits that
was used to produce the compressed data is positive while the window
bits crypto/deflate is using to perform the decompression isn't.
So what we should do here is turn window bits into a configurable
parameter.
Once you supply the correct window bits information, the above is
then simply an optimisation.
Rather than keeping the above optimisation, JFFS should simply do
the compression with a negative window bits value.
Of course to maintain backwards compatibility you'll need to do this
as a new compression type.
> 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).
> */
I believe this bit of code originally came from FreeS/WAN and was
written by Svenning S?rensen. Maybe he or Yoshifuji-san can tell
us why?
Unless we're sure that zlib has been fixed we should leave it in.
It should be a no-op if zlib has been fixed. So this probably
isn't causing the breakage that you saw.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Hello Herbert,
> The GNU coding style is completely different from Linux.
Ok, NP.
> Please reformat it when you fix up the overhead calculation.
Sure.
> Good catch. I'll apply this one.
Only one small note: I've spotted this but didn't test. I didn't make
sure this is OK if we haven't ever used the compression and remove the
deflate module. (i.e, in this case we call zlib_[in|de]flateEnd() while
we haven't ever called zlib_[in|de]flate()). Although I believe it must
be OK, we need to try it.
So please, test it or wait while I'll do it.
> The crypto API needs to operate on buffers that's bigger than that so
> we need to have a correct upper bound the maximum expansion.
Well, I'm still not sure. I guess that we call deflate with Z_SYNC_FLUSH
so most data is already in the output buffer and we only need to provide
some room for end markers and the like at the final Z_FINISH call. And I
guess 12 bytes is enough. But again, this is only my guess. I need to
delve into zlib internals to explore this.
So, it seems I can't just port the JFFS2 stuff. I need to explore zlib
more closely. Thus, I need some time. I'll inform you about my results.
> I believe this bit of code originally came from FreeS/WAN and was
> written by Svenning Srensen. Maybe he or Yoshifuji-san can tell
> us why?
If you find some information about the issue, please, let me know.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Artem B. Bityuckiy <[email protected]> wrote:
>
>> Good catch. I'll apply this one.
> Only one small note: I've spotted this but didn't test. I didn't make
> sure this is OK if we haven't ever used the compression and remove the
> deflate module. (i.e, in this case we call zlib_[in|de]flateEnd() while
> we haven't ever called zlib_[in|de]flate()). Although I believe it must
> be OK, we need to try it.
It's OK because deflateReset == deflateEnd + deflateInit. Feel free
to test it though. You can find my tree at
bk://herbert.bkbits.net/cryptodev-2.6
> So, it seems I can't just port the JFFS2 stuff. I need to explore zlib
> more closely. Thus, I need some time. I'll inform you about my results.
For the default zlib parameters (which crypto/deflate.c does not use)
the maximum overhead is 5 bytes every 16KB plus 6 bytes. So for input
streams less than 16KB the figure of 12 bytes is correct. However,
in general the overhead needs to grow proportionally to the number of
blocks in the input.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Hi Herbert,
> For the default zlib parameters (which crypto/deflate.c does not use)
> the maximum overhead is 5 bytes every 16KB plus 6 bytes. So for input
> streams less than 16KB the figure of 12 bytes is correct. However,
> in general the overhead needs to grow proportionally to the number of
> blocks in the input.
I've explored the issue a bit. According RFC-1950 and RFC-1951, zlib
stream is:
2bytes zstream header, block1, block2, ... 4bytes adler32.
Each block has one 1-byte "end-of-block" marker and a prefix of max len =
1 byte.
In our code we do zlib_deflate(stream, Z_SYNC_FLUSH), so we always flush
the output. So the final zlib_deflate(stream, Z_FINISH) requires 1 byte
for the EOB marker and 4 bytes for adler32 (5 bytes total). Thats all. If
we compress a huge buffer, then we still need to output those 5 bytes as
well. I.e, the overhead of each block *is not accumulated* ! I even need
to make the reserved space less then 12 bytes!
Anyway, don't apply that patch please, I'll send a new one.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Fri, 2005-04-01 at 15:36 +0100, Artem B. Bityuckiy wrote:
> In our code we do zlib_deflate(stream, Z_SYNC_FLUSH), so we always flush
> the output. So the final zlib_deflate(stream, Z_FINISH) requires 1 byte
> for the EOB marker and 4 bytes for adler32 (5 bytes total). Thats all. If
> we compress a huge buffer, then we still need to output those 5 bytes as
> well. I.e, the overhead of each block *is not accumulated* ! I even need
> to make the reserved space less then 12 bytes!
Hm. Could we avoid using Z_SYNC_FLUSH and stick with a larger amount?
That would give us better compression.
--
dwmw2
David Woodhouse wrote:
> Hm. Could we avoid using Z_SYNC_FLUSH and stick with a larger amount?
> That would give us better compression.
Yes, the compression will be better. But the implementation will be more
complicated.
We can try to use the "bound" functions to predict how many bytes to
pass to the deflate's input, but there is no guarantee they'll fit into
the output buffer. In this case we'll need to try again.
Possibly, we may do something like this:
Try good compression using the prediction technique.
If we didn't fit the output buffer, use the old but determined algorithm.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Fri, 2005-04-01 at 18:57 +0400, Artem B. Bityuckiy wrote:
> Yes, the compression will be better. But the implementation will be more
> complicated.
> We can try to use the "bound" functions to predict how many bytes to
> pass to the deflate's input, but there is no guarantee they'll fit into
> the output buffer. In this case we'll need to try again.
Can we not predict the maximum number of bytes it'll take to flush the
stream when we're not using Z_SYNC_FLUSH?
--
dwmw2
David Woodhouse wrote:
> On Fri, 2005-04-01 at 18:57 +0400, Artem B. Bityuckiy wrote:
>
>>Yes, the compression will be better. But the implementation will be more
>>complicated.
>>We can try to use the "bound" functions to predict how many bytes to
>>pass to the deflate's input, but there is no guarantee they'll fit into
>>the output buffer. In this case we'll need to try again.
>
>
> Can we not predict the maximum number of bytes it'll take to flush the
> stream when we're not using Z_SYNC_FLUSH?
AFAIU, no. Zlib may eat a lot of input and do not produce much output, but
on Z_FINISH it may ask an undetermined amount of additional output space.
So, we must even regulate the amount of input we pass to zlib_deflate().
In case of Z_SYNC_FLUSH, things are more determined.
Another question, does JFFSx *really* need the peaces of a 4K page to be
independently uncompressable? It it wouldn't be required, we would achieve
better compression if we have saved the zstream state. :-) But it is too
late to change things at least for JFFS2.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Fri, Apr 01, 2005 at 03:36:23PM +0100, Artem B. Bityuckiy wrote:
>
> In our code we do zlib_deflate(stream, Z_SYNC_FLUSH), so we always flush
> the output. So the final zlib_deflate(stream, Z_FINISH) requires 1 byte
> for the EOB marker and 4 bytes for adler32 (5 bytes total). Thats all. If
> we compress a huge buffer, then we still need to output those 5 bytes as
> well. I.e, the overhead of each block *is not accumulated* ! I even need
> to make the reserved space less then 12 bytes!
I thought stored blocks (incompressible blocks) were limited to 64K
in size, no? Please double check zlib_deflate/deflate.c and
zlib_deflate/deftree.c.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Fri, 1 April 2005 16:22:50 +0100, Artem B. Bityuckiy wrote:
>
> Another question, does JFFSx *really* need the peaces of a 4K page to be
> independently uncompressable? It it wouldn't be required, we would achieve
> better compression if we have saved the zstream state. :-) But it is too
> late to change things at least for JFFS2.
Absolutely. You can argue that 4KiB is too small and 8|16|32|64|...
would be much better, yielding in better compression ratio. But
having to read and uncompress the whole file when appending a few
bytes is utter madness.
J?rn
--
I don't understand it. Nobody does.
-- Richard P. Feynman
> I thought stored blocks (incompressible blocks) were limited to 64K
> in size, no?
Blocks are limited in size by 64K, true. But why it matters for us?
Suppose we compress 1 GiB of input, and have a 70K output buffer. We
reserve 5 bytes at the end and start calling zlib_deflate(stream,
Z_SYNCK_FLUSH) recurrently. It puts one 64K block, puts its end marker,
then puts a part of a second block. Then we call zlib_deflate(strem,
Z_FINISH) and it puts the end marker of the second block and the adler32
checksum of the entire stream. So I don't see any problem albeit I didn't
try yet :-) But I'll do.
> Please double check zlib_deflate/deflate.c and
> zlib_deflate/deftree.c.
Surely I'll check. I'll even test the new implementation (which I didn't
actually do) with a large input before sending it next time.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Fri, Apr 01, 2005 at 04:41:44PM +0100, Artem B. Bityuckiy wrote:
>
> Suppose we compress 1 GiB of input, and have a 70K output buffer. We
The question is what happens when you compress 1 1GiB input buffer into
a 1GiB output buffer.
> Surely I'll check. I'll even test the new implementation (which I didn't
> actually do) with a large input before sending it next time.
It'd be a good idea to use /dev/urandom as your input.
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
> The question is what happens when you compress 1 1GiB input buffer into
> a 1GiB output buffer.
If user provides 1 GB output buffer then either we successfully compress
all the 1 GB input or we compress just a part of it.
In the former case user may provide a second output buffer and
crypto_comp_pcompress() will compress the rest of the input to it. And
the user will have two independently de-compressible buffers.
The latter case is possible if the input isn't compressible and it is up
to user to detect that handle this situation properly (i.e., just not to
compress this). So, IMO, there are no problems here at least for the
crypto_comp_pcompress() function.
In case of crypto_comp_pcompress() if the input isn't compressible,
error will be returned.
If somebody needs a more flexible compression interface, he may think
about implementing an deflate-like Crypto API interface. Or something
else like crypto_comp_compress() which saves its internal state between
calls and may be called several times with more input/output. I didn't
think on it but we might as well.
> It'd be a good idea to use /dev/urandom as your input.
Yes, this is what I think about. I'm going to extend the tcrypt.ko test.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Artem B. Bityuckiy wrote:
> In the former case user may provide a second output buffer and
s/former/latter/
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Sorry :-)
Artem B. Bityuckiy wrote:
> In case of crypto_comp_pcompress() if the input isn't compressible,
s/crypto_comp_pcompress()/crypto_comp_compress()/
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, Apr 03, 2005 at 12:22:12PM +0400, Artem B. Bityuckiy wrote:
>
> The latter case is possible if the input isn't compressible and it is up
> to user to detect that handle this situation properly (i.e., just not to
> compress this). So, IMO, there are no problems here at least for the
> crypto_comp_pcompress() function.
Surely that defeats the purpose of pcompress? I thought the whole point
was to compress as much of the input as possible into the output?
So 1G into 1G doesn't make sense here. But 1G into 1M does and you
want to put as much as you can in there. Otherwise we might as well
delete crypto_comp_pcompress :)
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
J?rn Engel wrote:
> Absolutely. You can argue that 4KiB is too small and 8|16|32|64|...
> would be much better, yielding in better compression ratio. But
> having to read and uncompress the whole file when appending a few
> bytes is utter madness.
>
Dear Joern,
I meant that JFFS2 always reads by portions of PAGE_SIZE bytes due to
the Page Cache. Consequently, nodes cotaining the peaces of the same
page don't have to be independently uncompressible. Yes, there are some
difficulties. But this is off-topic anyway and I don't think it is worth
to discuss this here :-)
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Herbert Xu wrote:
> Surely that defeats the purpose of pcompress? I thought the whole point
> was to compress as much of the input as possible into the output?
Absolutely correct.
> So 1G into 1G doesn't make sense here.
I thought you are afraid about the case of a totally random input which
may *grow* after it has been compressed.
> But 1G into 1M does and you
> want to put as much as you can in there. Otherwise we might as well
> delete crypto_comp_pcompress :)
Err, it looks like we've lost the conversation flow. :-) I commented
your phrase: "The question is what happens when you compress 1 1GiB
input buffer into a 1GiB output buffer."
Then could you please in a nutshell write what worries you or what issue
you would like to clarify?
IIRC, you worried that in case of a large input and output 12 bytes
won't be enough. I argued it should. I'm even going to check this soon :-)
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Herbert Xu wrote:
> On Sun, Apr 03, 2005 at 12:22:12PM +0400, Artem B. Bityuckiy wrote:
>
>>The latter case is possible if the input isn't compressible and it is up
>>to user to detect that handle this situation properly (i.e., just not to
>>compress this). So, IMO, there are no problems here at least for the
>>crypto_comp_pcompress() function.
>
I meant here, that user a-priori doesn't always know how good will his
data be compressed. So, he *may* provide the output buffer of the same
size as the input buffer (as you wrote, both are of 1GiB). So, if the
input data *grows* after the compression, then crypto_comp_pcompress()
will fill the output buffer fully and return OK, indicating that not all
the input was compressed. And it is up to user to handle this situation.
Probably he will just leave his data uncompressed. Probably he will
provide more output buffers. I just wanted to say, that
crypto_comp_pcompress() will work OK even in the case of uncompressible
data because I thought something worries you in this case :-)
> Surely that defeats the purpose of pcompress? I thought the whole point
> was to compress as much of the input as possible into the output?
>
> So 1G into 1G doesn't make sense here. But 1G into 1M does and you
> want to put as much as you can in there. Otherwise we might as well
> delete crypto_comp_pcompress :)
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, Apr 03, 2005 at 12:59:23PM +0400, Artem B. Bityuckiy wrote:
>
> Err, it looks like we've lost the conversation flow. :-) I commented
> your phrase: "The question is what happens when you compress 1 1GiB
> input buffer into a 1GiB output buffer."
>
> Then could you please in a nutshell write what worries you or what issue
> you would like to clarify?
>
> IIRC, you worried that in case of a large input and output 12 bytes
> won't be enough. I argued it should. I'm even going to check this soon :-)
You can't compress 1M-12bytes into 1M using zlib when the block size
is 64K.
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
> You can't compress 1M-12bytes into 1M using zlib when the block size
> is 64K.
Here is a cite from RFC-1951 (page 4):
A compressed data set consists of a series of blocks, corresponding
to successive blocks of input data. The block sizes are arbitrary,
except that non-compressible blocks are limited to 65,535 bytes.
Thus,
1. 64K is only applied to non-compressible data, in which case zlib just
copies it as it is, adding a 1-byte header and a 1-byte EOB marker.
2. 64K is just the *upper limit*, and blocks may be shorter.
3. If zlib compressed data (i.e., applied LZ77 & Huffman), blocks may
have arbitrary length.
So, I don't see any reason why I can't.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, Apr 03, 2005 at 01:45:58PM +0400, Artem B. Bityuckiy wrote:
>
> Here is a cite from RFC-1951 (page 4):
>
> A compressed data set consists of a series of blocks, corresponding
> to successive blocks of input data. The block sizes are arbitrary,
> except that non-compressible blocks are limited to 65,535 bytes.
>
> Thus,
>
> 1. 64K is only applied to non-compressible data, in which case zlib just
> copies it as it is, adding a 1-byte header and a 1-byte EOB marker.
I think the overhead could be higher. But even if it is 2 bytes
per block, then for 1M of incompressible input the total overhead is
2 * 1048576 / 65536 = 32
bytes.
Also I'm not certain if it will actually create 64K blocks. It might
be as low as 16K according to the zlib documentation.
> 3. If zlib compressed data (i.e., applied LZ77 & Huffman), blocks may
> have arbitrary length.
Actually there is a limit on that too but that's not relevant to
this discussion.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Sun, 2005-04-03 at 20:00 +1000, Herbert Xu wrote:
> > 1. 64K is only applied to non-compressible data, in which case zlib just
> > copies it as it is, adding a 1-byte header and a 1-byte EOB marker.
>
> I think the overhead could be higher. But even if it is 2 bytes
> per block, then for 1M of incompressible input the total overhead is
>
> 2 * 1048576 / 65536 = 32
We're not interested in the _total_ overhead, in this context. We're
interested in the number of bytes we have to have available in the
output buffer in order to let zlib finish its stream.
In the case of a 1MiB input generating 32 uncompressable 64KiB blocks,
the end markers for the first 31 blocks are going to be in our output
buffer already, so we don't need to leave space for them.
--
dwmw2
On Sun, Apr 03, 2005 at 11:06:01AM +0100, David Woodhouse wrote:
>
> We're not interested in the _total_ overhead, in this context. We're
> interested in the number of bytes we have to have available in the
> output buffer in order to let zlib finish its stream.
>
> In the case of a 1MiB input generating 32 uncompressable 64KiB blocks,
> the end markers for the first 31 blocks are going to be in our output
> buffer already, so we don't need to leave space for them.
You might be right. But I'm not sure yet.
If we use the current code and supply zlib_deflate with 1048576-12 bytes
of (incompressible) input and 1048576 bytes of output buffer, wouldn't
zlib keep writing incompressible blocks and return when it can't do that
anymore because the output buffer has been exhausted?
When it does return it has to finish writing the last block it's on.
So if the total overhead is 32 bytes then the last block would need
another 20 bytes of output space which we don't have, no?
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
> On Sun, Apr 03, 2005 at 01:45:58PM +0400, Artem B. Bityuckiy wrote:
> I think the overhead could be higher.
IIUC, not. But I'll check this in practice.
> But even if it is 2 bytes
Ok, suppose.
> per block, then for 1M of incompressible input the total overhead is
>
> 2 * 1048576 / 65536 = 32
>
> bytes.
I've given an example why is this OK.
Shortly, because we need to reserve space only for the EOB marker of the
*last* block (1 byte) and for the adler32 (4 bytes).
Look closer to the algorithm. It consists of 2 parts.
1. We reserve 12 bytes And compress as much as possible to the output
buffer with Z_SYNC_FLUSH. Zlib produces:
| stream header | Block 1 (<header, 64 K, EOB>) | -> more
| Block 2 (<header, 64 K, EOB>) | ... etc ... | -> more
| Block N (<header, 64 K, EOB>) | -> more
| Last block (<header, 25K
Here zlib stops on, say 25 KiB because there is no more room for output.
2. We call zlib_deflate() with Z_FINISH and provide additional 12 bytes.
After zlib_deflate() has finished, the output stream is:
| stream header | Block 1 (<header, 64 K, EOB>) | -> more
| Block 2 (<header, 64 K, EOB>) | ... etc ... | -> more
| Block N (<header, 64 K, EOB>) | -> more
| Last block (<header, 25K, EOB>) | adler32 |
And all is OK.
> Actually there is a limit on that too but that's not relevant to
> this discussion.
Agreed :-)
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Herbert Xu wrote:
> You might be right. But I'm not sure yet.
>
> If we use the current code and supply zlib_deflate with 1048576-12 bytes
> of (incompressible) input and 1048576 bytes of output buffer, wouldn't
> zlib keep writing incompressible blocks and return when it can't do that
> anymore because the output buffer has been exhausted?
It must not. Look at the algoritm closer.
stream->next_in = (u8 *)src;
stream->next_out = dst;
while (stream->total_in < *slen
&& stream->total_out < *dlen - DEFLATE_PCOMPR_RESERVE) {
stream->avail_out = *dlen - DEFLATE_PCOMPR_RESERVE -
stream->total_out;
stream->avail_in = min((unsigned int)(*slen -
stream->total_in), stream->avail_out);
ret = zlib_deflate(stream, Z_SYNC_FLUSH);
if (ret != Z_OK)
return -EINVAL;
}
stream->avail_out += DEFLATE_PCOMPR_RESERVE;
stream->avail_in = 0; /* <------ no more input ! ---------- */
ret = zlib_deflate(stream, Z_FINISH);
if (ret != Z_STREAM_END)
return -EINVAL;
>
> When it does return it has to finish writing the last block it's on.
No, it must only put EOB and adler32, we won't give it more input.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, 2005-04-03 at 20:17 +1000, Herbert Xu wrote:
> You might be right. But I'm not sure yet.
>
> If we use the current code and supply zlib_deflate with 1048576-12
> bytes of (incompressible) input and 1048576 bytes of output buffer,
> wouldn't zlib keep writing incompressible blocks and return when it
> can't do that anymore because the output buffer has been exhausted?
>
> When it does return it has to finish writing the last block it's on.
>
> So if the total overhead is 32 bytes then the last block would need
> another 20 bytes of output space which we don't have, no?
Right. We shouldn't feed 1048576-12 bytes into zlib and expect the
output to fit into our 1048576-byte buffer. We could get away with that
kind of thing when we were using Z_SYNC_FLUSH but we can't now.
But now we're not using Z_SYNC_FLUSH it doesn't matter if we feed the
input in smaller chunks. We can calculate a conservative estimate of the
amount we'll fit, and keep feeding it input till the amount of space
left in the output buffer is 12 bytes.
--
dwmw2
Herbert,
I also wonder, does it at all correct to use negative windowBits in
crypto API? I mean, if windowBits is negative, zlib doesn't produce the
proper zstream header, which is incorrect according to RFC-1950. It also
doesn't calculate adler32.
For example, if we work over an IP network (RFC-2384), the receiving
side may be confused by such a "stripped" zstream.
Isn't it conceptually right to produce *correct* zstream, with the
header and the proper adler32 ?
Yes, for JFFS2 we would like to have no adler32, we anyway protect our
data by CRC32. But I suppose this should be an additional feature.
Comments?
Herbert Xu wrote:
>>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;
>>}
>>------------------------------------------------------------------------
>
> The reason you need to add this is because the window bits that
> was used to produce the compressed data is positive while the window
> bits crypto/deflate is using to perform the decompression isn't.
>
> So what we should do here is turn window bits into a configurable
> parameter.
>
> Once you supply the correct window bits information, the above is
> then simply an optimisation.
>
> Rather than keeping the above optimisation, JFFS should simply do
> the compression with a negative window bits value.
>
> Of course to maintain backwards compatibility you'll need to do this
> as a new compression type.
>
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, Apr 03, 2005 at 12:19:17PM +0100, David Woodhouse wrote:
>
> But now we're not using Z_SYNC_FLUSH it doesn't matter if we feed the
> input in smaller chunks. We can calculate a conservative estimate of the
> amount we'll fit, and keep feeding it input till the amount of space
> left in the output buffer is 12 bytes.
Yes that's what we should do. In fact newer versions of zlib carries
a deflateBound function which we can invert to calculate the conservative
estimate.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Sun, Apr 03, 2005 at 02:23:42PM +0400, Artem B. Bityuckiy wrote:
>
> It must not. Look at the algoritm closer.
This relies on implementation details within zlib_deflate, which may
or may not be the case.
It should be easy to test though. Just write a user-space program
which does exactly this and feed it something from /dev/urandom.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Sun, Apr 03, 2005 at 03:41:07PM +0400, Artem B. Bityuckiy wrote:
>
> I also wonder, does it at all correct to use negative windowBits in
> crypto API? I mean, if windowBits is negative, zlib doesn't produce the
It's absolutely correct for IPComp. For other uses it may or may not
be correct.
For instance for JFFS2 it's absolutely incorrect since it breaks
compatibility. Incidentally, JFFS should create a new compression
type that doesn't include the zlib header so that we don't need the
head-skipping speed hack.
> proper zstream header, which is incorrect according to RFC-1950. It also
Can you please point me to the paragraph in RFC 1950 that says this?
> Isn't it conceptually right to produce *correct* zstream, with the
> header and the proper adler32 ?
Not really. However it should be possible if the user needs it which
is why we should make windowBits configurable.
> Yes, for JFFS2 we would like to have no adler32, we anyway protect our
> data by CRC32. But I suppose this should be an additional feature.
Yes, I'd love to see a patch that makes windowBits configurable in
crypto/deflate.c.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
> Can you please point me to the paragraph in RFC 1950 that says this?
Ok, if to do s/correct/compliant/, here it is:
Section 2.3, page 7
-----------------------------------------------------------------------
A compliant compressor must produce streams with correct CMF, FLG and
ADLER32, but need not support preset dictionaries.
...
A compliant decompressor must check CMF, FLG, and ADLER32, and
provide an error indication if any of these have incorrect values.
A compliant decompressor must give an error indication if CM is
not one of the values defined in this specification (only the
value 8 is permitted in this version), since another value could
indicate the presence of new features that would cause subsequent
data to be interpreted incorrectly
-----------------------------------------------------------------------
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, Apr 03, 2005 at 03:53:40PM +0400, Artem B. Bityuckiy wrote:
> Herbert Xu wrote:
> >Can you please point me to the paragraph in RFC 1950 that says this?
>
> Ok, if to do s/correct/compliant/, here it is:
>
> Section 2.3, page 7
Sorry, I thought you were referring to an RFC that defined IPComp/deflate.
RFC 1950 only defines what a zlib compressed data stream should
look like, it does not define what a deflate compressed data
stream is.
RFC 2394 which defines IPComp/deflate only refers to the deflate
document, and not zlib.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
> On Sun, Apr 03, 2005 at 03:41:07PM +0400, Artem B. Bityuckiy wrote:
>
>>I also wonder, does it at all correct to use negative windowBits in
>>crypto API? I mean, if windowBits is negative, zlib doesn't produce the
>
>
> It's absolutely correct for IPComp. For other uses it may or may not
> be correct.
I've looked through RFC-2394 quickly, but didn't found any mention about
non-complient zstreams. I suppose they must be complient by default.
Although I'm far not an expert in the area.
> For instance for JFFS2 it's absolutely incorrect since it breaks
> compatibility. Incidentally, JFFS should create a new compression
> type that doesn't include the zlib header so that we don't need the
> head-skipping speed hack.
Anyway, in JFFS2 we may do that "hack" before calling pcompress(), so it
isn't big problem.
> Yes, I'd love to see a patch that makes windowBits configurable in
> crypto/deflate.c.
I wonder, do we really want this?
Imagine we have 100 different compressors, and each is differently
configurable. It may make cryptoAPI messy. May be it is better to stand
that user must use deflate (and the other 99 compressors) directly if he
wants something not standard/compliant?
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Sun, Apr 03, 2005 at 04:01:19PM +0400, Artem B. Bityuckiy wrote:
>
> >For instance for JFFS2 it's absolutely incorrect since it breaks
> >compatibility. Incidentally, JFFS should create a new compression
> >type that doesn't include the zlib header so that we don't need the
> >head-skipping speed hack.
>
> Anyway, in JFFS2 we may do that "hack" before calling pcompress(), so it
> isn't big problem.
It still makes sense to use a negative window bits for JFFS since it
means that you don't have to calculate the adler checksum in the
first place AND you don't have to store the zlib header/trailer on
disk.
BTW, that hack can only be applied when there is no preset dictionary.
Although the Linux implementation of JFFS probably never used a preset
dictionary, it is theoretically possible that someone out there may
have generated a JFFS image which contains a compressed stream that has
a preset dictionary.
In that case if you don't set the window bits to a postive value it
won't work at all.
> >Yes, I'd love to see a patch that makes windowBits configurable in
> >crypto/deflate.c.
>
> I wonder, do we really want this?
Yes since the the window bits determines the compression quality and
the amount of memory used. This is going to differ depending on the
application.
> Imagine we have 100 different compressors, and each is differently
> configurable. It may make cryptoAPI messy. May be it is better to stand
> that user must use deflate (and the other 99 compressors) directly if he
> wants something not standard/compliant?
Each crypto/deflate user gets their own private zlib instance.
Where is the problem?
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
> Each crypto/deflate user gets their own private zlib instance.
> Where is the problem?
Hmm, OK. No problems, that was just RFC. :-)
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Herbert Xu wrote:
> This relies on implementation details within zlib_deflate, which may
> or may not be the case.
>
> It should be easy to test though. Just write a user-space program
> which does exactly this and feed it something from /dev/urandom.
>
Well, Herbert, you're right. In case of non-compressible data things
are bad. I'll continue investigating this.
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Hello,
Well, with Mark Adler's help I've realized that extending zlib isn't
than simple task.
Herbert Xu wrote:
> What I was suggesting is to invert the calculation that deflateBound
> is doing so that it gives a lower bound on the input buffer size
> that does not exceed a given output buffer size.
Actually, for JFFS2 we need to leave the uncompressable data
uncompressed. So if the pcompress interface have only been for JFFS2,
I'd just return an error rather then expand data. Is such behavior
acceptable for common Linux's parts pike CryptoAPI ?
And more, frankly, I don't like the "independent" partial compression
approach in JFFS2 and in JFFS3 (if it will ever happen) I'd make these
pieces dependent. For this purpose we'd need some deflate-like CryptoAPI
interface. I'm not going to implement it at the moment, I'm just curious
- what do you guys think about a generalized deflate-like CryptoAPI
compression interface?
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
Please keep [email protected] in the loop.
On Mon, Apr 18, 2005 at 07:09:29PM +0400, Artem B. Bityuckiy wrote:
>
> Actually, for JFFS2 we need to leave the uncompressable data
> uncompressed. So if the pcompress interface have only been for JFFS2,
> I'd just return an error rather then expand data. Is such behavior
> acceptable for common Linux's parts pike CryptoAPI ?
You mean you no longer need pcompress and we can get rid of it?
That's fine by me.
> And more, frankly, I don't like the "independent" partial compression
> approach in JFFS2 and in JFFS3 (if it will ever happen) I'd make these
> pieces dependent. For this purpose we'd need some deflate-like CryptoAPI
> interface. I'm not going to implement it at the moment, I'm just curious
> - what do you guys think about a generalized deflate-like CryptoAPI
> compression interface?
Well if you can show me what such an interface looks like then we can
discuss it.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu wrote:
>>Actually, for JFFS2 we need to leave the uncompressable data
>>uncompressed. So if the pcompress interface have only been for JFFS2,
>>I'd just return an error rather then expand data. Is such behavior
>>acceptable for common Linux's parts pike CryptoAPI ?
> You mean you no longer need pcompress and we can get rid of it?
> That's fine by me.
Pardon Herbert, I didn't say anything about getting rid yet :-) I've
just reread what I wrote and didn't find a drop of that :-) But if I was
fuzzy, I'm sorry.
I meant there are 2 situations:
1. input data is compressible;
2. input data isn't compressible.
JFFS2 wants the following from pcompress():
1. compressible data: compress it; the offered formerly algorithm works
just fine here.
2. non-compressible data: do not compress it, leave it uncompressed; the
offered algorithm works fine here too - it returns an error.
So, the essence of the question was: the offered algorithm is OK for
JFFS2 (but need some refining). May we preserve it and don't bother
about predicting how much buffer space we need to reserve in case the
input data is non-compressible?
--
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.
On Tue, Apr 19, 2005 at 04:51:56PM +0400, Artem B. Bityuckiy wrote:
>
> JFFS2 wants the following from pcompress():
> 1. compressible data: compress it; the offered formerly algorithm works
> just fine here.
Yes but the existing JFFS algorithm does a lot more than that. It tries
to pack as much data as possible into the output buffer.
> 2. non-compressible data: do not compress it, leave it uncompressed; the
> offered algorithm works fine here too - it returns an error.
If all you need is to compress what's compressible you don't need
pcompress at all. You just need to call the normal compress method
with the input length clamped by the output buffer size. If the
function returns OK then it's compressible, otherwise it isn't.
You can even do the existing JFFS loop this way too.
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt