1
/* fitblk.c: example of fitting compressed output to a specified size
2
Not copyrighted -- provided to the public domain
3
Version 1.1 25 November 2004 Mark Adler */
6
1.0 24 Nov 2004 First version
7
1.1 25 Nov 2004 Change deflateInit2() to deflateInit()
8
Use fixed-size, stack-allocated raw buffers
9
Simplify code moving compression to subroutines
10
Use assert() for internal errors
11
Add detailed description of approach
14
/* Approach to just fitting a requested compressed size:
16
fitblk performs three compression passes on a portion of the input
17
data in order to determine how much of that input will compress to
18
nearly the requested output block size. The first pass generates
19
enough deflate blocks to produce output to fill the requested
20
output size plus a specfied excess amount (see the EXCESS define
21
below). The last deflate block may go quite a bit past that, but
22
is discarded. The second pass decompresses and recompresses just
23
the compressed data that fit in the requested plus excess sized
24
buffer. The deflate process is terminated after that amount of
25
input, which is less than the amount consumed on the first pass.
26
The last deflate block of the result will be of a comparable size
27
to the final product, so that the header for that deflate block and
28
the compression ratio for that block will be about the same as in
29
the final product. The third compression pass decompresses the
30
result of the second step, but only the compressed data up to the
31
requested size minus an amount to allow the compressed stream to
32
complete (see the MARGIN define below). That will result in a
33
final compressed stream whose length is less than or equal to the
34
requested size. Assuming sufficient input and a requested size
35
greater than a few hundred bytes, the shortfall will typically be
38
If the input is short enough that the first compression completes
39
before filling the requested output size, then that compressed
40
stream is return with no recompression.
42
EXCESS is chosen to be just greater than the shortfall seen in a
43
two pass approach similar to the above. That shortfall is due to
44
the last deflate block compressing more efficiently with a smaller
45
header on the second pass. EXCESS is set to be large enough so
46
that there is enough uncompressed data for the second pass to fill
47
out the requested size, and small enough so that the final deflate
48
block of the second pass will be close in size to the final deflate
49
block of the third and final pass. MARGIN is chosen to be just
50
large enough to assure that the final compression has enough room
51
to complete in all cases.
61
/* print nastygram and leave */
62
local void quit(char *why)
64
fprintf(stderr, "fitblk abort: %s\n", why);
68
#define RAWLEN 4096 /* intermediate uncompressed buffer size */
70
/* compress from file to def until provided buffer is full or end of
71
input reached; return last deflate() return value, or Z_ERRNO if
72
there was read error on the file */
73
local int partcompress(FILE *in, z_streamp def)
76
unsigned char raw[RAWLEN];
80
def->avail_in = fread(raw, 1, RAWLEN, in);
86
ret = deflate(def, flush);
87
assert(ret != Z_STREAM_ERROR);
88
} while (def->avail_out != 0 && flush == Z_NO_FLUSH);
92
/* recompress from inf's input to def's output; the input for inf and
93
the output for def are set in those structures before calling;
94
return last deflate() return value, or Z_MEM_ERROR if inflate()
95
was not able to allocate enough memory when it needed to */
96
local int recompress(z_streamp inf, z_streamp def)
99
unsigned char raw[RAWLEN];
104
inf->avail_out = RAWLEN;
106
ret = inflate(inf, Z_NO_FLUSH);
107
assert(ret != Z_STREAM_ERROR && ret != Z_DATA_ERROR &&
109
if (ret == Z_MEM_ERROR)
112
/* compress what was decompresed until done or no room */
113
def->avail_in = RAWLEN - inf->avail_out;
115
if (inf->avail_out != 0)
117
ret = deflate(def, flush);
118
assert(ret != Z_STREAM_ERROR);
119
} while (ret != Z_STREAM_END && def->avail_out != 0);
123
#define EXCESS 256 /* empirically determined stream overage */
124
#define MARGIN 8 /* amount to back off for completion */
126
/* compress from stdin to fixed-size block on stdout */
127
int main(int argc, char **argv)
129
int ret; /* return code */
130
unsigned size; /* requested fixed output block size */
131
unsigned have; /* bytes written by deflate() call */
132
unsigned char *blk; /* intermediate and final stream */
133
unsigned char *tmp; /* close to desired size stream */
134
z_stream def, inf; /* zlib deflate and inflate states */
136
/* get requested output size */
138
quit("need one argument: size of output block");
139
ret = strtol(argv[1], argv + 1, 10);
141
quit("argument must be a number");
142
if (ret < 8) /* 8 is minimum zlib stream size */
143
quit("need positive size of 8 or greater");
144
size = (unsigned)ret;
146
/* allocate memory for buffers and compression engine */
147
blk = malloc(size + EXCESS);
151
ret = deflateInit(&def, Z_DEFAULT_COMPRESSION);
152
if (ret != Z_OK || blk == NULL)
153
quit("out of memory");
155
/* compress from stdin until output full, or no more input */
156
def.avail_out = size + EXCESS;
158
ret = partcompress(stdin, &def);
160
quit("error reading input");
162
/* if it all fit, then size was undersubscribed -- done! */
163
if (ret == Z_STREAM_END && def.avail_out >= EXCESS) {
164
/* write block to stdout */
165
have = size + EXCESS - def.avail_out;
166
if (fwrite(blk, 1, have, stdout) != have || ferror(stdout))
167
quit("error writing output");
169
/* clean up and print results to stderr */
170
ret = deflateEnd(&def);
171
assert(ret != Z_STREAM_ERROR);
174
"%u bytes unused out of %u requested (all input)\n",
179
/* it didn't all fit -- set up for recompression */
184
inf.next_in = Z_NULL;
185
ret = inflateInit(&inf);
186
tmp = malloc(size + EXCESS);
187
if (ret != Z_OK || tmp == NULL)
188
quit("out of memory");
189
ret = deflateReset(&def);
190
assert(ret != Z_STREAM_ERROR);
192
/* do first recompression close to the right amount */
193
inf.avail_in = size + EXCESS;
195
def.avail_out = size + EXCESS;
197
ret = recompress(&inf, &def);
198
if (ret == Z_MEM_ERROR)
199
quit("out of memory");
201
/* set up for next reocmpression */
202
ret = inflateReset(&inf);
203
assert(ret != Z_STREAM_ERROR);
204
ret = deflateReset(&def);
205
assert(ret != Z_STREAM_ERROR);
207
/* do second and final recompression (third compression) */
208
inf.avail_in = size - MARGIN; /* assure stream will complete */
210
def.avail_out = size;
212
ret = recompress(&inf, &def);
213
if (ret == Z_MEM_ERROR)
214
quit("out of memory");
215
assert(ret == Z_STREAM_END); /* otherwise MARGIN too small */
217
/* done -- write block to stdout */
218
have = size - def.avail_out;
219
if (fwrite(blk, 1, have, stdout) != have || ferror(stdout))
220
quit("error writing output");
222
/* clean up and print results to stderr */
224
ret = inflateEnd(&inf);
225
assert(ret != Z_STREAM_ERROR);
226
ret = deflateEnd(&def);
227
assert(ret != Z_STREAM_ERROR);
230
"%u bytes unused out of %u requested (%lu input)\n",
231
size - have, size, def.total_in);