1*44bedb31SLionel Sambuc /* $NetBSD: fitblk.c,v 1.1.1.1 2006/01/14 20:11:08 christos Exp $ */
2*44bedb31SLionel Sambuc
3*44bedb31SLionel Sambuc /* fitblk.c: example of fitting compressed output to a specified size
4*44bedb31SLionel Sambuc Not copyrighted -- provided to the public domain
5*44bedb31SLionel Sambuc Version 1.1 25 November 2004 Mark Adler */
6*44bedb31SLionel Sambuc
7*44bedb31SLionel Sambuc /* Version history:
8*44bedb31SLionel Sambuc 1.0 24 Nov 2004 First version
9*44bedb31SLionel Sambuc 1.1 25 Nov 2004 Change deflateInit2() to deflateInit()
10*44bedb31SLionel Sambuc Use fixed-size, stack-allocated raw buffers
11*44bedb31SLionel Sambuc Simplify code moving compression to subroutines
12*44bedb31SLionel Sambuc Use assert() for internal errors
13*44bedb31SLionel Sambuc Add detailed description of approach
14*44bedb31SLionel Sambuc */
15*44bedb31SLionel Sambuc
16*44bedb31SLionel Sambuc /* Approach to just fitting a requested compressed size:
17*44bedb31SLionel Sambuc
18*44bedb31SLionel Sambuc fitblk performs three compression passes on a portion of the input
19*44bedb31SLionel Sambuc data in order to determine how much of that input will compress to
20*44bedb31SLionel Sambuc nearly the requested output block size. The first pass generates
21*44bedb31SLionel Sambuc enough deflate blocks to produce output to fill the requested
22*44bedb31SLionel Sambuc output size plus a specfied excess amount (see the EXCESS define
23*44bedb31SLionel Sambuc below). The last deflate block may go quite a bit past that, but
24*44bedb31SLionel Sambuc is discarded. The second pass decompresses and recompresses just
25*44bedb31SLionel Sambuc the compressed data that fit in the requested plus excess sized
26*44bedb31SLionel Sambuc buffer. The deflate process is terminated after that amount of
27*44bedb31SLionel Sambuc input, which is less than the amount consumed on the first pass.
28*44bedb31SLionel Sambuc The last deflate block of the result will be of a comparable size
29*44bedb31SLionel Sambuc to the final product, so that the header for that deflate block and
30*44bedb31SLionel Sambuc the compression ratio for that block will be about the same as in
31*44bedb31SLionel Sambuc the final product. The third compression pass decompresses the
32*44bedb31SLionel Sambuc result of the second step, but only the compressed data up to the
33*44bedb31SLionel Sambuc requested size minus an amount to allow the compressed stream to
34*44bedb31SLionel Sambuc complete (see the MARGIN define below). That will result in a
35*44bedb31SLionel Sambuc final compressed stream whose length is less than or equal to the
36*44bedb31SLionel Sambuc requested size. Assuming sufficient input and a requested size
37*44bedb31SLionel Sambuc greater than a few hundred bytes, the shortfall will typically be
38*44bedb31SLionel Sambuc less than ten bytes.
39*44bedb31SLionel Sambuc
40*44bedb31SLionel Sambuc If the input is short enough that the first compression completes
41*44bedb31SLionel Sambuc before filling the requested output size, then that compressed
42*44bedb31SLionel Sambuc stream is return with no recompression.
43*44bedb31SLionel Sambuc
44*44bedb31SLionel Sambuc EXCESS is chosen to be just greater than the shortfall seen in a
45*44bedb31SLionel Sambuc two pass approach similar to the above. That shortfall is due to
46*44bedb31SLionel Sambuc the last deflate block compressing more efficiently with a smaller
47*44bedb31SLionel Sambuc header on the second pass. EXCESS is set to be large enough so
48*44bedb31SLionel Sambuc that there is enough uncompressed data for the second pass to fill
49*44bedb31SLionel Sambuc out the requested size, and small enough so that the final deflate
50*44bedb31SLionel Sambuc block of the second pass will be close in size to the final deflate
51*44bedb31SLionel Sambuc block of the third and final pass. MARGIN is chosen to be just
52*44bedb31SLionel Sambuc large enough to assure that the final compression has enough room
53*44bedb31SLionel Sambuc to complete in all cases.
54*44bedb31SLionel Sambuc */
55*44bedb31SLionel Sambuc
56*44bedb31SLionel Sambuc #include <stdio.h>
57*44bedb31SLionel Sambuc #include <stdlib.h>
58*44bedb31SLionel Sambuc #include <assert.h>
59*44bedb31SLionel Sambuc #include "zlib.h"
60*44bedb31SLionel Sambuc
61*44bedb31SLionel Sambuc #define local static
62*44bedb31SLionel Sambuc
63*44bedb31SLionel Sambuc /* print nastygram and leave */
quit(char * why)64*44bedb31SLionel Sambuc local void quit(char *why)
65*44bedb31SLionel Sambuc {
66*44bedb31SLionel Sambuc fprintf(stderr, "fitblk abort: %s\n", why);
67*44bedb31SLionel Sambuc exit(1);
68*44bedb31SLionel Sambuc }
69*44bedb31SLionel Sambuc
70*44bedb31SLionel Sambuc #define RAWLEN 4096 /* intermediate uncompressed buffer size */
71*44bedb31SLionel Sambuc
72*44bedb31SLionel Sambuc /* compress from file to def until provided buffer is full or end of
73*44bedb31SLionel Sambuc input reached; return last deflate() return value, or Z_ERRNO if
74*44bedb31SLionel Sambuc there was read error on the file */
partcompress(FILE * in,z_streamp def)75*44bedb31SLionel Sambuc local int partcompress(FILE *in, z_streamp def)
76*44bedb31SLionel Sambuc {
77*44bedb31SLionel Sambuc int ret, flush;
78*44bedb31SLionel Sambuc unsigned char raw[RAWLEN];
79*44bedb31SLionel Sambuc
80*44bedb31SLionel Sambuc flush = Z_NO_FLUSH;
81*44bedb31SLionel Sambuc do {
82*44bedb31SLionel Sambuc def->avail_in = fread(raw, 1, RAWLEN, in);
83*44bedb31SLionel Sambuc if (ferror(in))
84*44bedb31SLionel Sambuc return Z_ERRNO;
85*44bedb31SLionel Sambuc def->next_in = raw;
86*44bedb31SLionel Sambuc if (feof(in))
87*44bedb31SLionel Sambuc flush = Z_FINISH;
88*44bedb31SLionel Sambuc ret = deflate(def, flush);
89*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
90*44bedb31SLionel Sambuc } while (def->avail_out != 0 && flush == Z_NO_FLUSH);
91*44bedb31SLionel Sambuc return ret;
92*44bedb31SLionel Sambuc }
93*44bedb31SLionel Sambuc
94*44bedb31SLionel Sambuc /* recompress from inf's input to def's output; the input for inf and
95*44bedb31SLionel Sambuc the output for def are set in those structures before calling;
96*44bedb31SLionel Sambuc return last deflate() return value, or Z_MEM_ERROR if inflate()
97*44bedb31SLionel Sambuc was not able to allocate enough memory when it needed to */
recompress(z_streamp inf,z_streamp def)98*44bedb31SLionel Sambuc local int recompress(z_streamp inf, z_streamp def)
99*44bedb31SLionel Sambuc {
100*44bedb31SLionel Sambuc int ret, flush;
101*44bedb31SLionel Sambuc unsigned char raw[RAWLEN];
102*44bedb31SLionel Sambuc
103*44bedb31SLionel Sambuc flush = Z_NO_FLUSH;
104*44bedb31SLionel Sambuc do {
105*44bedb31SLionel Sambuc /* decompress */
106*44bedb31SLionel Sambuc inf->avail_out = RAWLEN;
107*44bedb31SLionel Sambuc inf->next_out = raw;
108*44bedb31SLionel Sambuc ret = inflate(inf, Z_NO_FLUSH);
109*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR && ret != Z_DATA_ERROR &&
110*44bedb31SLionel Sambuc ret != Z_NEED_DICT);
111*44bedb31SLionel Sambuc if (ret == Z_MEM_ERROR)
112*44bedb31SLionel Sambuc return ret;
113*44bedb31SLionel Sambuc
114*44bedb31SLionel Sambuc /* compress what was decompresed until done or no room */
115*44bedb31SLionel Sambuc def->avail_in = RAWLEN - inf->avail_out;
116*44bedb31SLionel Sambuc def->next_in = raw;
117*44bedb31SLionel Sambuc if (inf->avail_out != 0)
118*44bedb31SLionel Sambuc flush = Z_FINISH;
119*44bedb31SLionel Sambuc ret = deflate(def, flush);
120*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
121*44bedb31SLionel Sambuc } while (ret != Z_STREAM_END && def->avail_out != 0);
122*44bedb31SLionel Sambuc return ret;
123*44bedb31SLionel Sambuc }
124*44bedb31SLionel Sambuc
125*44bedb31SLionel Sambuc #define EXCESS 256 /* empirically determined stream overage */
126*44bedb31SLionel Sambuc #define MARGIN 8 /* amount to back off for completion */
127*44bedb31SLionel Sambuc
128*44bedb31SLionel Sambuc /* compress from stdin to fixed-size block on stdout */
main(int argc,char ** argv)129*44bedb31SLionel Sambuc int main(int argc, char **argv)
130*44bedb31SLionel Sambuc {
131*44bedb31SLionel Sambuc int ret; /* return code */
132*44bedb31SLionel Sambuc unsigned size; /* requested fixed output block size */
133*44bedb31SLionel Sambuc unsigned have; /* bytes written by deflate() call */
134*44bedb31SLionel Sambuc unsigned char *blk; /* intermediate and final stream */
135*44bedb31SLionel Sambuc unsigned char *tmp; /* close to desired size stream */
136*44bedb31SLionel Sambuc z_stream def, inf; /* zlib deflate and inflate states */
137*44bedb31SLionel Sambuc
138*44bedb31SLionel Sambuc /* get requested output size */
139*44bedb31SLionel Sambuc if (argc != 2)
140*44bedb31SLionel Sambuc quit("need one argument: size of output block");
141*44bedb31SLionel Sambuc ret = strtol(argv[1], argv + 1, 10);
142*44bedb31SLionel Sambuc if (argv[1][0] != 0)
143*44bedb31SLionel Sambuc quit("argument must be a number");
144*44bedb31SLionel Sambuc if (ret < 8) /* 8 is minimum zlib stream size */
145*44bedb31SLionel Sambuc quit("need positive size of 8 or greater");
146*44bedb31SLionel Sambuc size = (unsigned)ret;
147*44bedb31SLionel Sambuc
148*44bedb31SLionel Sambuc /* allocate memory for buffers and compression engine */
149*44bedb31SLionel Sambuc blk = malloc(size + EXCESS);
150*44bedb31SLionel Sambuc def.zalloc = Z_NULL;
151*44bedb31SLionel Sambuc def.zfree = Z_NULL;
152*44bedb31SLionel Sambuc def.opaque = Z_NULL;
153*44bedb31SLionel Sambuc ret = deflateInit(&def, Z_DEFAULT_COMPRESSION);
154*44bedb31SLionel Sambuc if (ret != Z_OK || blk == NULL)
155*44bedb31SLionel Sambuc quit("out of memory");
156*44bedb31SLionel Sambuc
157*44bedb31SLionel Sambuc /* compress from stdin until output full, or no more input */
158*44bedb31SLionel Sambuc def.avail_out = size + EXCESS;
159*44bedb31SLionel Sambuc def.next_out = blk;
160*44bedb31SLionel Sambuc ret = partcompress(stdin, &def);
161*44bedb31SLionel Sambuc if (ret == Z_ERRNO)
162*44bedb31SLionel Sambuc quit("error reading input");
163*44bedb31SLionel Sambuc
164*44bedb31SLionel Sambuc /* if it all fit, then size was undersubscribed -- done! */
165*44bedb31SLionel Sambuc if (ret == Z_STREAM_END && def.avail_out >= EXCESS) {
166*44bedb31SLionel Sambuc /* write block to stdout */
167*44bedb31SLionel Sambuc have = size + EXCESS - def.avail_out;
168*44bedb31SLionel Sambuc if (fwrite(blk, 1, have, stdout) != have || ferror(stdout))
169*44bedb31SLionel Sambuc quit("error writing output");
170*44bedb31SLionel Sambuc
171*44bedb31SLionel Sambuc /* clean up and print results to stderr */
172*44bedb31SLionel Sambuc ret = deflateEnd(&def);
173*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
174*44bedb31SLionel Sambuc free(blk);
175*44bedb31SLionel Sambuc fprintf(stderr,
176*44bedb31SLionel Sambuc "%u bytes unused out of %u requested (all input)\n",
177*44bedb31SLionel Sambuc size - have, size);
178*44bedb31SLionel Sambuc return 0;
179*44bedb31SLionel Sambuc }
180*44bedb31SLionel Sambuc
181*44bedb31SLionel Sambuc /* it didn't all fit -- set up for recompression */
182*44bedb31SLionel Sambuc inf.zalloc = Z_NULL;
183*44bedb31SLionel Sambuc inf.zfree = Z_NULL;
184*44bedb31SLionel Sambuc inf.opaque = Z_NULL;
185*44bedb31SLionel Sambuc inf.avail_in = 0;
186*44bedb31SLionel Sambuc inf.next_in = Z_NULL;
187*44bedb31SLionel Sambuc ret = inflateInit(&inf);
188*44bedb31SLionel Sambuc tmp = malloc(size + EXCESS);
189*44bedb31SLionel Sambuc if (ret != Z_OK || tmp == NULL)
190*44bedb31SLionel Sambuc quit("out of memory");
191*44bedb31SLionel Sambuc ret = deflateReset(&def);
192*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
193*44bedb31SLionel Sambuc
194*44bedb31SLionel Sambuc /* do first recompression close to the right amount */
195*44bedb31SLionel Sambuc inf.avail_in = size + EXCESS;
196*44bedb31SLionel Sambuc inf.next_in = blk;
197*44bedb31SLionel Sambuc def.avail_out = size + EXCESS;
198*44bedb31SLionel Sambuc def.next_out = tmp;
199*44bedb31SLionel Sambuc ret = recompress(&inf, &def);
200*44bedb31SLionel Sambuc if (ret == Z_MEM_ERROR)
201*44bedb31SLionel Sambuc quit("out of memory");
202*44bedb31SLionel Sambuc
203*44bedb31SLionel Sambuc /* set up for next reocmpression */
204*44bedb31SLionel Sambuc ret = inflateReset(&inf);
205*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
206*44bedb31SLionel Sambuc ret = deflateReset(&def);
207*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
208*44bedb31SLionel Sambuc
209*44bedb31SLionel Sambuc /* do second and final recompression (third compression) */
210*44bedb31SLionel Sambuc inf.avail_in = size - MARGIN; /* assure stream will complete */
211*44bedb31SLionel Sambuc inf.next_in = tmp;
212*44bedb31SLionel Sambuc def.avail_out = size;
213*44bedb31SLionel Sambuc def.next_out = blk;
214*44bedb31SLionel Sambuc ret = recompress(&inf, &def);
215*44bedb31SLionel Sambuc if (ret == Z_MEM_ERROR)
216*44bedb31SLionel Sambuc quit("out of memory");
217*44bedb31SLionel Sambuc assert(ret == Z_STREAM_END); /* otherwise MARGIN too small */
218*44bedb31SLionel Sambuc
219*44bedb31SLionel Sambuc /* done -- write block to stdout */
220*44bedb31SLionel Sambuc have = size - def.avail_out;
221*44bedb31SLionel Sambuc if (fwrite(blk, 1, have, stdout) != have || ferror(stdout))
222*44bedb31SLionel Sambuc quit("error writing output");
223*44bedb31SLionel Sambuc
224*44bedb31SLionel Sambuc /* clean up and print results to stderr */
225*44bedb31SLionel Sambuc free(tmp);
226*44bedb31SLionel Sambuc ret = inflateEnd(&inf);
227*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
228*44bedb31SLionel Sambuc ret = deflateEnd(&def);
229*44bedb31SLionel Sambuc assert(ret != Z_STREAM_ERROR);
230*44bedb31SLionel Sambuc free(blk);
231*44bedb31SLionel Sambuc fprintf(stderr,
232*44bedb31SLionel Sambuc "%u bytes unused out of %u requested (%lu input)\n",
233*44bedb31SLionel Sambuc size - have, size, def.total_in);
234*44bedb31SLionel Sambuc return 0;
235*44bedb31SLionel Sambuc }
236