zlib.h

[Andrea Crotti]

Hi everyone, I would like to compress some data, in practice some ip
packets that have to be compressed and then sent chunked and sent over
the network.

I've seen zlib.h and it looks nice, but I have some trouble
understanding how ti works.

I tried to understand the zpipe example and modified for me and I got
something like
(where the struct is)
--8<---------------cut here---------------start------------->8---
typdef struct {
unsigned char *stream;
int len;
} payload_t;
--8<---------------cut here---------------end--------------->8---

--8<---------------cut here---------------start------------->8---
// compress original data in the given result
int payload_compress(payload_t data, payload_t *result) {
int ret, flush;
unsigned have;
z_stream strm;

/* allocate deflate state */
strm.zalloc = Z_NULL;
strm.zfree = Z_NULL;
strm.opaque = Z_NULL;
ret = deflateInit(&strm, LEVEL);
if (ret != Z_OK)
return ret;

// is this thing enough for it?
strm.next_in = data.stream;

ret = deflate(&strm, Z_FINISH); /* no bad return value */
// the initialization was successful
assert(ret != Z_STREAM_ERROR); /* state not clobbered */

deflateEnd(&strm);
return Z_OK;
}
--8<---------------cut here---------------end--------------->8---

what I don't understand is:
- is it just setting "next_in" enough to give the data to the compression?
- how do write to my "result" object?
- why does it say (here http://www.zlib.net/zlib_how.html)
" CHUNK is simply the buffer size for feeding data to and pulling data
from the zlib routines."
does that mean that it should not be the dimension of the packet to
compress but just the max pool where it should work??

And last thing, where do I get how much is the actual data compressed?

I was used too well , in python it was just
data = zlib.compress(data)

Thanks a lot!

 

[Andrea Crotti]

In the end I luckily found the man page, and I think I understood something:

--8<---------------cut here---------------start------------->8---
int payload_compress(payload_t data, payload_t result) {
int ret;
z_stream strm;
// maybe out should be bigger
unsigned char *in = (unsigned char *) data.stream;
unsigned char *out = (unsigned char *) result.stream;

/* allocate deflate state */
// initialize the structures
strm.zalloc = Z_NULL;
strm.zfree = Z_NULL;
strm.opaque = Z_NULL;
ret = deflateInit(&strm, LEVEL);
// if initialized correctly
if (ret != Z_OK)
return ret;

strm.avail_in = data.len;
strm.avail_out = data.len;

// is this thing enough for it?
strm.next_in = in;
strm.next_out = out;
ret = deflate(&strm, Z_NO_FLUSH); /* no bad return value */
printf("now ret in and out = %d, %d, %d\n", ret, strm.avail_in, strm.avail_out);
// the initialization was successful
assert(ret != Z_STREAM_ERROR); /* state not clobbered */

return Z_OK;
}
--8<---------------cut here---------------end--------------->8---

The thing is that I wanted to compress only ONCE, the data is normally
max 1000 bytes, so I don't really think I need to chunk more.

But a very strange thing is happening, testing this function apparently
works BUT I get a SIGSEV (or sometimes a BUS error) when the program
quits (on return 0 in main), and I get no other errors before...

 

[Ersek, Laszlo]

Hi everyone, I would like to compress some data, in practice some ip
packets that have to be compressed and then sent chunked and sent over
the network.

I've seen zlib.h and it looks nice, but I have some trouble
understanding how ti works.

See the manual [0].

The basic idea is this: you provide "input data" in

*next_in .. *(next_in + avail_in - 1)

(inclusive), and provide "output space" in

*next_out .. *(next_out + avail_out - 1)

(inclusive). You call the corresponding (compression or decompression)
routine. In the most common case, the routine returns due to one of these
(normal) conditions:
- output space ran out,
- input data ran out,
- (theoretically possible) both of these at the same time.

You need to "fix" all these conditions before calling the function again
(ie. provide more input if needed, *and* provide more output space if
needed).

The whole loop resembles (to me at least) how iconv() is used, and to some
extent, select(). In some sense, you don't call the (de)compression
function so that it serves you. You rather set an automaton in motion and
care for its needs. It just happens to spit out (de)compressed data. It
resembles "event driven programming", ie. the automaton is a black box and
returns "events" for you to handle ("add more input", "provide more output
space"). You need to look at the input and the output independently.

Disclaimer: I wrote the above mostly from memory, based on what I remember
from the libbzip2 (not zlib) API. Sorry. Still, "[t]he structure of
libbzip2's interfaces is similar to that of Jean-loup Gailly's and Mark
Adler's excellent zlib library" [1].

If you need an upper bound on the compressed size of the plaintext data
before actually doing a single-shot compression (you mentioned Z_FINISH),
see deflateBound() [2] in the zlib docs.

For "packet compression", you might want to consider LZO [3] [4]. For
example, OpenVPN employs "fast LZO compression" -- search [5] for
"comp-lzo".

I'll also mention QuickLZ [6] (their words: "QuickLZ is the world's
fastest compression library (really)"). I didn't test QuickLZ itself, but
tamp [7] is based on it, and tamp was actually faster than anything else
I've seen (for the compression efficiency it provided).

lacos

[0] http://zlib.net/manual.html
[1] http://bzip.org/1.0.5/bzip2-manual-1.0.5.html#top-level
[2] http://zlib.net/manual.html#Advanced
[3] http://www.oberhumer.com/opensource/lzo/#abstract
[4] http://www.oberhumer.com/opensource/lzo/#lzop
[5] http://www.openvpn.net/index.php/open-source/documentation/manuals/69-openvpn-21.html
[6] http://www.quicklz.com/
[7] http://blogs.sun.com/timc/entry/tamp_a_lightweight_multi_threaded

 

[Andrea Crotti]

See the manual [0].

The basic idea is this: you provide "input data" in

*next_in .. *(next_in + avail_in - 1)

(inclusive), and provide "output space" in

*next_out .. *(next_out + avail_out - 1)

(inclusive). You call the corresponding (compression or decompression)
routine. In the most common case, the routine returns due to one of
these (normal) conditions:
- output space ran out,
- input data ran out,
- (theoretically possible) both of these at the same time.

You need to "fix" all these conditions before calling the function
again (ie. provide more input if needed, *and* provide more output
space if needed).

The whole loop resembles (to me at least) how iconv() is used, and to
some extent, select(). In some sense, you don't call the
(de)compression function so that it serves you. You rather set an
automaton in motion and care for its needs. It just happens to spit
out (de)compressed data. It resembles "event driven programming",
ie. the automaton is a black box and returns "events" for you to
handle ("add more input", "provide more output space"). You need to
look at the input and the output independently.

Thanks a lot for the nice explanation, a couple of more questions.

What if I know I want to compress in only one shot, why do I still need
to have a loop?

And do I really need to do a deflateEnd/inflateEnd or is not compulsory?
I mean of course I don't free everything without, but I don't think is
that the reason of my segfaulting...

 

[Tom St Denis]

For "packet compression", you might want to consider LZO [3] [4]. For
example, OpenVPN employs "fast LZO compression" -- search [5] for
"comp-lzo".

I'll also mention QuickLZ [6] (their words: "QuickLZ is the world's
fastest compression library (really)"). I didn't test QuickLZ itself, but
tamp [7] is based on it, and tamp was actually faster than anything else
I've seen (for the compression efficiency it provided).

QuickLZ-C reminds me of LZRW1 from yesteryear. I've actually used
LZRW1 in a NES emulator for the GBA where I compressed saved games
instead of using their default RLE.

LZRW1 is also free for all purposes [unlike QLZ].

Tom

 

[Andrea Crotti]

What if I know I want to compress in only one shot, why do I still need
to have a loop?

And do I really need to do a deflateEnd/inflateEnd or is not compulsory?
I mean of course I don't free everything without, but I don't think is
that the reason of my segfaulting...

Mm I guess I'm doing something wrong with the pointers then, I pass to
compress something like:

...
unsigned char *in = (unsigned char *) data.stream;
unsigned char *out = (unsigned char *) result.stream;
...
strm.next_in = in;
strm.next_out = out;


where the stream is something like
--8<---------------cut here---------------start------------->8---
stream_t *data_msg = malloc(sizeof(stream_t) * size);
stream_t *result_msg = malloc(sizeof(stream_t) * size);
stream_t *compr_msg = malloc(sizeof(stream_t) * size);
--8<---------------cut here---------------end--------------->8---

And the size of the output is equal to the input.
It looks very simple where could be the mistake?

 

[Ersek, Laszlo]

What if I know I want to compress in only one shot, why do I still need
to have a loop?

You don't. The loop should be necessary if at least one of the following
was unknown to you in advance: size of input, size of processed output.

And do I really need to do a deflateEnd/inflateEnd or is not compulsory?
I mean of course I don't free everything without, but I don't think is
that the reason of my segfaulting...

----v----
If the parameter flush is set to Z_FINISH, pending input is processed,
pending output is flushed and deflate returns with Z_STREAM_END if there
was enough output space; if deflate returns with Z_OK, this function must
be called again with Z_FINISH and more output space (updated avail_out)
but no more input data, until it returns with Z_STREAM_END or an error.
After deflate has returned Z_STREAM_END, the only possible operations on
the stream are deflateReset or deflateEnd.
----^----

Beside deflateReset(), you might want to look at Z_FULL_FLUSH (instead of
Z_FINISH).

lacos

 

[Andrea Crotti]

You don't. The loop should be necessary if at least one of the
following was unknown to you in advance: size of input, size of
processed output.



----v----
If the parameter flush is set to Z_FINISH, pending input is processed,
pending output is flushed and deflate returns with Z_STREAM_END if
there was enough output space; if deflate returns with Z_OK, this
function must be called again with Z_FINISH and more output space
(updated avail_out) but no more input data, until it returns with
Z_STREAM_END or an error. After deflate has returned Z_STREAM_END, the
only possible operations on the stream are deflateReset or deflateEnd.
----^----

Beside deflateReset(), you might want to look at Z_FULL_FLUSH (instead
of Z_FINISH).

lacos

MM looking at the doc Z_FINISH looks better to me, anyway IT WORKS!!
It's a bit brutal since I do assertions to check that one pass was
enough
assert(ret == Z_STREAM_END);
but it's perfectly fine for now.

For who could be interested here is the code
http://gist.github.com/492738

And of course any advice on style or just bugs is welcome

 

[Ersek, Laszlo]

Mm I guess I'm doing something wrong with the pointers then, I pass to
compress something like:

...
unsigned char *in = (unsigned char *) data.stream;
unsigned char *out = (unsigned char *) result.stream;
...
strm.next_in = in;
strm.next_out = out;


where the stream is something like
--8<---------------cut here---------------start------------->8---
stream_t *data_msg = malloc(sizeof(stream_t) * size);
stream_t *result_msg = malloc(sizeof(stream_t) * size);
stream_t *compr_msg = malloc(sizeof(stream_t) * size);
--8<---------------cut here---------------end--------------->8---

And the size of the output is equal to the input.
It looks very simple where could be the mistake?

Unless you can instruct any compiler that will compile the code to lay out
"stream_t" in a specific way, ie. padding, byte order and encoding, the
above seems very wrong. The usual steps should be:

- architecture-dependent C language structs
- architecture-independent, serialized wire format ("byte array")
- compressed bit-stream

Your code seems to lack the middle phase when providing input for
compression, and then it seems to store the compressed bit-stream
erroneously. The latter can't be treated as anything else than "array of
char unsigned", so the explicit pointer conversion when assigning to "out"
("next_out") is immediately suspicious.

Furthermore, you should avoid defining type names ending with "_t" if
you're on a POSIX/UNIX platform [0].

lacos

[0] http://www.opengroup.org/onlinepubs/9699919799/functions/V2_chap02.html#tag_15_02_02

 

[Andrea Crotti]

Unless you can instruct any compiler that will compile the code to lay

out "stream_t" in a specific way, ie. padding, byte order and
encoding, the above seems very wrong. The usual steps should be:

- architecture-dependent C language structs
- architecture-independent, serialized wire format ("byte array")
- compressed bit-stream

Your code seems to lack the middle phase when providing input for
compression, and then it seems to store the compressed bit-stream
erroneously. The latter can't be treated as anything else than "array
of char unsigned", so the explicit pointer conversion when assigning
to "out" ("next_out") is immediately suspicious.

Furthermore, you should avoid defining type names ending with "_t" if
you're on a POSIX/UNIX platform [0].

lacos

[0] http://www.opengroup.org/onlinepubs/9699919799/functions/V2_chap02.html#tag_15_02_02

Well I understood that those types while compatible are just how
represent the data, so it should not be a problem.

I'm not sure why I need the second phase at all... And more important
what does it mean practically in code?

After all stream_t has to be put as a payload of some network packets
and then reconstructed in the other side (which works nicely now without
the compression at least).

I had done some stupid mistakes before, now it seems to work, I
generate random data, I compress it, decompress and assert that it's
still the same.

Thanks a lot!

 

[Ersek, Laszlo]

I'm not sure why I need the second phase at all...

Consider:

#include <stdio.h>
#include <stdlib.h>

int
main(void)
{
const long unsigned lu = 1LU;
size_t s;

for (s = 0u; s < sizeof lu; ++s) {
(void)fprintf(stdout, "%s%02X", 0u == s ? "" : " ",
(unsigned)((const char unsigned *)&lu));
}
(void)fprintf(stdout, "\n");
return EOF == fflush(stdout) ? EXIT_FAILURE : EXIT_SUCCESS;
}

ELF 32-bit LSB executable, Intel 80386 : 01 00 00 00
ELF 32-bit MSB executable SPARC32PLUS Version 1 : 00 00 00 01
ELF 64-bit LSB executable, x86-64 : 01 00 00 00 00 00 00 00
ELF 64-bit MSB executable SPARCV9 Version 1 : 00 00 00 00 00 00 00 01

And more important what does it mean practically in code?

Something like (not standard C anymore):

#define _XOPEN_SOURCE 500 /* SUSv2 */

#include <stdio.h> /* fprintf() */
#include <stdlib.h> /* EXIT_FAILURE */
#include <inttypes.h> /* uint64_t */
#include <limits.h> /* CHAR_BIT */
#include <arpa/inet.h> /* htonl() */

#if 8 != CHAR_BIT
# error "8 != CHAR_BIT"
#endif

int
main(void)
{
const uint64_t u64 = 1u;
uint32_t u32s[2];
size_t s;

/* network byte order is MSB */
u32s[0] = htonl(u64 >> 32);
u32s[1] = htonl(u64);

for (s = 0u; s < sizeof u32s; ++s) {
(void)fprintf(stdout, "%s%02X", 0u == s ? "" : " ",
(unsigned)((const char unsigned *)u32s));
}
(void)fprintf(stdout, "\n");
return EOF == fflush(stdout) ? EXIT_FAILURE : EXIT_SUCCESS;
}

ELF 32-bit LSB executable, Intel 80386 : 00 00 00 00 00 00 00 01
ELF 32-bit MSB executable SPARC32PLUS Version 1 : 00 00 00 00 00 00 00 01
ELF 64-bit LSB executable, x86-64 : 00 00 00 00 00 00 00 01
ELF 64-bit MSB executable SPARCV9 Version 1 : 00 00 00 00 00 00 00 01

After all stream_t has to be put as a payload of some network packets
and then reconstructed in the other side (which works nicely now without
the compression at least).

Imagine sending the first "lu" variable over the network, perhaps as part
of your "stream_t" structure, from a 32-bit LSB architecture to a 32-bit
MSB architecture, or a 64-bit architecture.

Cheers,
lacos

 

[Andrea Crotti]

Imagine sending the first "lu" variable over the network, perhaps as

part of your "stream_t" structure, from a 32-bit LSB architecture to a
32-bit MSB architecture, or a 64-bit architecture.

Cheers,
lacos

Yes sure you're perfectly right, I discussed with my collegues but
they say that using stream_t, which is "unsigned char" we should not
need it, since it's always just one byte.

Is that not correct?

We didn't get any kind of errors until now, using 32 and 64 bit machines
but all linux.

Another thing, we have a 3 bytes header on top of the compressed chunk
of data, now we see that for SOME data (random or already compressed)
compressing could make it bigger.

It's not a big deal of course, but is a stupid idea to add another field
to say to the other end if the packet is compressed or not?

Thanks

 

[Ersek, Laszlo]

they say that using stream_t, which is "unsigned char"

Oh. So "stream_t" is "char unsigned"? I guess knowing that I would have
written my previous followup very differently. Also, I seem to remember
"sizeof(stream_t)" expressions in your malloc() arguments. That's
completely superfluous -- sizeof(any character type) is per definition
((size_t)1). Why invent a new (and I'd risk, misleading, and also
non-SUS-conformant) name for "char unsigned"?

Another thing, we have a 3 bytes header on top of the compressed chunk
of data, now we see that for SOME data (random or already compressed)
compressing could make it bigger.

There exists no losless compression algorithm that makes every input
strictly shorter.

Off the top of my head, I'm not sure if a stronger claim can be proven,
but in practice, you'll see plenty of inflation due to compression.
Usually the compression library provides a function -- or the
documentation comes with a formula -- that computes an upper bound on the
compressed size, given the uncompressed input size. This formula considers
the worst case, and thus returns almost certainly a value that is bigger
than the input value, but what matters is only that the returned value is
finite and can be obtained in advance, without actually doing the
compression.

It's not a big deal of course, but is a stupid idea to add another field
to say to the other end if the packet is compressed or not?

It is not. See eg. "--comp-noadapt" in the OpenVPN manual.

lacos

 

[Mark Adler]

Andrea,

In order to use a single deflate() or inflate() call successfully for a
complete compression or complete decompression, you need to know ahead
of time the largest amount of space needed for the output and provide
that amount of space. If you don't, the operation won't complete and
you will lose data. For compression (deflate), that's not too much of
a problem, since there is a maximum expansion of the data of a small
fraction of a percent plus a few bytes. The function deflateBound()
provides the upper limit for your buffer allocation given the input
data size.

However for decompression (inflate), the maximum expansion is the
maximum compression ratio of deflation. That ratio is a little over a
thousand (1,032 to be exact). So when all you know is the compressed
data size, it is usually impractical to allocate a buffer that large
for the output. To do decompression in a single step, you generally
need to have some foreknowledge of the size of the uncompressed data,
either by design (e.g. a fixed packet size) or the uncompressed length
stored in the input somewhere ahead of the compressed data.

In your compression routine you have an assert(ret == Z_STREAM_END)
after calling deflate. It is even more important to have that same
assert() after calling inflate. That will check not only that you
really did have enough output space, but will also check that inflate
verified the integrity of the data.

Lastly, if you are calling these routines very frequently, you can
avoid the overhead of the Init and End routines, mostly a lot of
allocation and deallocation of memory, by keeping the allocated
structures around for reuse. Each time you use them, instead of Init
you call Reset, e.g. deflateReset or inflateReset, to reuse that
structure. Then your program just needs to allocate them with Init
once at the start, and free them with End once when you're done.

Mark

 

[Mark Adler]

Do I still need the (deflate|inflate)Init right?

Yes you need to init at least once, but now you don't appear to have
deflateEnd or inflateEnd. If those aren't called somewhere, you have a
giant memory leak. If you are trying to implement what I mentioned
about the use of deflateReset and inflateReset, you have not done that.
That would look like:

whenyourprogramstarts:
deflateInit(&strm, ...)
<then hold on to strm for reuse>

repeatthisasmanytimesasyoulike:
deflateReset(&strm)
ret = deflate(&strm, ...)
assert(ret == Z_STREAM_END)

whenyourprogramends:
deflateEnd(&strm)

Check inside this module if the resulting data is really smaller and if
it's not just return the original data.

You would then need to mark it as such, since it is possible for the
raw data to actually be a compressed stream. You can't simply rely on
decompression failing to indicate raw data. There would need to be a
leading bit or byte saying if it's compressed or not.

In any case, that is unnecessary. deflate already detects
incompressible data, and uses its "store" method, which adds very
little overhead to mark the data.

Mark

 

[Andrea Crotti]

Yes you need to init at least once, but now you don't appear to have
deflateEnd or inflateEnd. If those aren't called somewhere, you have
a giant memory leak. If you are trying to implement what I mentioned
about the use of deflateReset and inflateReset, you have not done
that. That would look like:

whenyourprogramstarts:
deflateInit(&strm, ...)
<then hold on to strm for reuse>

repeatthisasmanytimesasyoulike:
deflateReset(&strm)
ret = deflate(&strm, ...)
assert(ret == Z_STREAM_END)

whenyourprogramends:
deflateEnd(&strm)

Yes Init was there
--8<---------------cut here---------------start------------->8---
case COMPRESS:
deflateInit(&strm, LEVEL);
ret = deflate(&strm, Z_FINISH);
--8<---------------cut here---------------end--------------->8---
But not end, now I will add it to the closing function...
But then from what I understand I should have two different stream for
compression and decompression in this way, is that correct? (not a big
problem of course).

You would then need to mark it as such, since it is possible for the
raw data to actually be a compressed stream. You can't simply rely on
decompression failing to indicate raw data. There would need to be a
leading bit or byte saying if it's compressed or not.

In any case, that is unnecessary. deflate already detects
incompressible data, and uses its "store" method, which adds very
little overhead to mark the data.

Mark

Yes it's a bad idea, but about the auto-detection I still got sometimes
105-110% of the original size, maybe adding one marker byte is still
faster?

 

[Andrea Crotti]

Ok now is changed in something like this
http://gist.github.com/504341

Now I use two z_stream variables, and I reset them only once at startup
of the program (is that correct?)

--8<---------------cut here---------------start------------->8---
strm->zalloc = Z_NULL;
strm->zfree = Z_NULL;
strm->opaque = Z_NULL;
--8<---------------cut here---------------end--------------->8---

Now it does:
init_compression()

.... compress & decompress

close_compression()

But with valgrind I still have a memory leak
--8<---------------cut here---------------start------------->8---
7 allocs, 6 frees
--8<---------------cut here---------------end--------------->8---
but on my side there and I close everything, what could that be?

Thanks!

 

[Mark Adler]

Yes it's a bad idea, but about the auto-detection I still got sometimes
105-110% of the original size, maybe adding one marker byte is still
faster?

For small packets the overhead is more, since there is a fixed 11 or so
bytes added. So in this case, putting in your own not-compressed
marker would be more efficient.

Ok now is changed in something like this
http://gist.github.com/504341

Now I use two z_stream variables, and I reset them only once at startup
of the program (is that correct?)

No. If you use zlib_manage multiple times and close_compression once,
you will have a massive memory leak. You are still not using
deflateReset and inflateReset. You need to read zlib.h.

Mark

 

[Andrea Crotti]

For small packets the overhead is more, since there is a fixed 11 or
so bytes added. So in this case, putting in your own not-compressed
marker would be more efficient.

I see then if it's only for small packets that I get the overhead is
rather useless this flag..

No. If you use zlib_manage multiple times and close_compression once,
you will have a massive memory leak. You are still not using
deflateReset and inflateReset. You need to read zlib.h.

Mark

Ok now I close every time and also reset, isn't it fine now?
http://gist.github.com/504879

But what I don't get then is why I have to use the reset if every time I
call also the deflateEnd?
Maybe because then is faster and I don't need to re-set the attributes
and the level of compression?

Still I get one allocation more than the frees, mmm

 

[Andrea Crotti]

Ok now I close every time and also reset, isn't it fine now?
http://gist.github.com/504879

But what I don't get then is why I have to use the reset if every time I
call also the deflateEnd?
Maybe because then is faster and I don't need to re-set the attributes
and the level of compression?

Still I get one allocation more than the frees, mmm

Maybe I finally got it, reset has to be used after
--8<---------------cut here---------------start------------->8---
case COMPRESS:
strm = &strm_compress;
_setup_zstream(strm, &data, result);
ret = deflate(strm, Z_FINISH);
deflateReset(&strm_compress);
break;
--8<---------------cut here---------------end--------------->8---

as above.
initialize -> use -> reset -> use -> reset -> close

should be then, now I only need to find the missing free and I'm fine...