Chris@43: /* fitblk.c: example of fitting compressed output to a specified size Chris@43: Not copyrighted -- provided to the public domain Chris@43: Version 1.1 25 November 2004 Mark Adler */ Chris@43: Chris@43: /* Version history: Chris@43: 1.0 24 Nov 2004 First version Chris@43: 1.1 25 Nov 2004 Change deflateInit2() to deflateInit() Chris@43: Use fixed-size, stack-allocated raw buffers Chris@43: Simplify code moving compression to subroutines Chris@43: Use assert() for internal errors Chris@43: Add detailed description of approach Chris@43: */ Chris@43: Chris@43: /* Approach to just fitting a requested compressed size: Chris@43: Chris@43: fitblk performs three compression passes on a portion of the input Chris@43: data in order to determine how much of that input will compress to Chris@43: nearly the requested output block size. The first pass generates Chris@43: enough deflate blocks to produce output to fill the requested Chris@43: output size plus a specfied excess amount (see the EXCESS define Chris@43: below). The last deflate block may go quite a bit past that, but Chris@43: is discarded. The second pass decompresses and recompresses just Chris@43: the compressed data that fit in the requested plus excess sized Chris@43: buffer. The deflate process is terminated after that amount of Chris@43: input, which is less than the amount consumed on the first pass. Chris@43: The last deflate block of the result will be of a comparable size Chris@43: to the final product, so that the header for that deflate block and Chris@43: the compression ratio for that block will be about the same as in Chris@43: the final product. The third compression pass decompresses the Chris@43: result of the second step, but only the compressed data up to the Chris@43: requested size minus an amount to allow the compressed stream to Chris@43: complete (see the MARGIN define below). That will result in a Chris@43: final compressed stream whose length is less than or equal to the Chris@43: requested size. Assuming sufficient input and a requested size Chris@43: greater than a few hundred bytes, the shortfall will typically be Chris@43: less than ten bytes. Chris@43: Chris@43: If the input is short enough that the first compression completes Chris@43: before filling the requested output size, then that compressed Chris@43: stream is return with no recompression. Chris@43: Chris@43: EXCESS is chosen to be just greater than the shortfall seen in a Chris@43: two pass approach similar to the above. That shortfall is due to Chris@43: the last deflate block compressing more efficiently with a smaller Chris@43: header on the second pass. EXCESS is set to be large enough so Chris@43: that there is enough uncompressed data for the second pass to fill Chris@43: out the requested size, and small enough so that the final deflate Chris@43: block of the second pass will be close in size to the final deflate Chris@43: block of the third and final pass. MARGIN is chosen to be just Chris@43: large enough to assure that the final compression has enough room Chris@43: to complete in all cases. Chris@43: */ Chris@43: Chris@43: #include Chris@43: #include Chris@43: #include Chris@43: #include "zlib.h" Chris@43: Chris@43: #define local static Chris@43: Chris@43: /* print nastygram and leave */ Chris@43: local void quit(char *why) Chris@43: { Chris@43: fprintf(stderr, "fitblk abort: %s\n", why); Chris@43: exit(1); Chris@43: } Chris@43: Chris@43: #define RAWLEN 4096 /* intermediate uncompressed buffer size */ Chris@43: Chris@43: /* compress from file to def until provided buffer is full or end of Chris@43: input reached; return last deflate() return value, or Z_ERRNO if Chris@43: there was read error on the file */ Chris@43: local int partcompress(FILE *in, z_streamp def) Chris@43: { Chris@43: int ret, flush; Chris@43: unsigned char raw[RAWLEN]; Chris@43: Chris@43: flush = Z_NO_FLUSH; Chris@43: do { Chris@43: def->avail_in = fread(raw, 1, RAWLEN, in); Chris@43: if (ferror(in)) Chris@43: return Z_ERRNO; Chris@43: def->next_in = raw; Chris@43: if (feof(in)) Chris@43: flush = Z_FINISH; Chris@43: ret = deflate(def, flush); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: } while (def->avail_out != 0 && flush == Z_NO_FLUSH); Chris@43: return ret; Chris@43: } Chris@43: Chris@43: /* recompress from inf's input to def's output; the input for inf and Chris@43: the output for def are set in those structures before calling; Chris@43: return last deflate() return value, or Z_MEM_ERROR if inflate() Chris@43: was not able to allocate enough memory when it needed to */ Chris@43: local int recompress(z_streamp inf, z_streamp def) Chris@43: { Chris@43: int ret, flush; Chris@43: unsigned char raw[RAWLEN]; Chris@43: Chris@43: flush = Z_NO_FLUSH; Chris@43: do { Chris@43: /* decompress */ Chris@43: inf->avail_out = RAWLEN; Chris@43: inf->next_out = raw; Chris@43: ret = inflate(inf, Z_NO_FLUSH); Chris@43: assert(ret != Z_STREAM_ERROR && ret != Z_DATA_ERROR && Chris@43: ret != Z_NEED_DICT); Chris@43: if (ret == Z_MEM_ERROR) Chris@43: return ret; Chris@43: Chris@43: /* compress what was decompresed until done or no room */ Chris@43: def->avail_in = RAWLEN - inf->avail_out; Chris@43: def->next_in = raw; Chris@43: if (inf->avail_out != 0) Chris@43: flush = Z_FINISH; Chris@43: ret = deflate(def, flush); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: } while (ret != Z_STREAM_END && def->avail_out != 0); Chris@43: return ret; Chris@43: } Chris@43: Chris@43: #define EXCESS 256 /* empirically determined stream overage */ Chris@43: #define MARGIN 8 /* amount to back off for completion */ Chris@43: Chris@43: /* compress from stdin to fixed-size block on stdout */ Chris@43: int main(int argc, char **argv) Chris@43: { Chris@43: int ret; /* return code */ Chris@43: unsigned size; /* requested fixed output block size */ Chris@43: unsigned have; /* bytes written by deflate() call */ Chris@43: unsigned char *blk; /* intermediate and final stream */ Chris@43: unsigned char *tmp; /* close to desired size stream */ Chris@43: z_stream def, inf; /* zlib deflate and inflate states */ Chris@43: Chris@43: /* get requested output size */ Chris@43: if (argc != 2) Chris@43: quit("need one argument: size of output block"); Chris@43: ret = strtol(argv[1], argv + 1, 10); Chris@43: if (argv[1][0] != 0) Chris@43: quit("argument must be a number"); Chris@43: if (ret < 8) /* 8 is minimum zlib stream size */ Chris@43: quit("need positive size of 8 or greater"); Chris@43: size = (unsigned)ret; Chris@43: Chris@43: /* allocate memory for buffers and compression engine */ Chris@43: blk = malloc(size + EXCESS); Chris@43: def.zalloc = Z_NULL; Chris@43: def.zfree = Z_NULL; Chris@43: def.opaque = Z_NULL; Chris@43: ret = deflateInit(&def, Z_DEFAULT_COMPRESSION); Chris@43: if (ret != Z_OK || blk == NULL) Chris@43: quit("out of memory"); Chris@43: Chris@43: /* compress from stdin until output full, or no more input */ Chris@43: def.avail_out = size + EXCESS; Chris@43: def.next_out = blk; Chris@43: ret = partcompress(stdin, &def); Chris@43: if (ret == Z_ERRNO) Chris@43: quit("error reading input"); Chris@43: Chris@43: /* if it all fit, then size was undersubscribed -- done! */ Chris@43: if (ret == Z_STREAM_END && def.avail_out >= EXCESS) { Chris@43: /* write block to stdout */ Chris@43: have = size + EXCESS - def.avail_out; Chris@43: if (fwrite(blk, 1, have, stdout) != have || ferror(stdout)) Chris@43: quit("error writing output"); Chris@43: Chris@43: /* clean up and print results to stderr */ Chris@43: ret = deflateEnd(&def); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: free(blk); Chris@43: fprintf(stderr, Chris@43: "%u bytes unused out of %u requested (all input)\n", Chris@43: size - have, size); Chris@43: return 0; Chris@43: } Chris@43: Chris@43: /* it didn't all fit -- set up for recompression */ Chris@43: inf.zalloc = Z_NULL; Chris@43: inf.zfree = Z_NULL; Chris@43: inf.opaque = Z_NULL; Chris@43: inf.avail_in = 0; Chris@43: inf.next_in = Z_NULL; Chris@43: ret = inflateInit(&inf); Chris@43: tmp = malloc(size + EXCESS); Chris@43: if (ret != Z_OK || tmp == NULL) Chris@43: quit("out of memory"); Chris@43: ret = deflateReset(&def); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: Chris@43: /* do first recompression close to the right amount */ Chris@43: inf.avail_in = size + EXCESS; Chris@43: inf.next_in = blk; Chris@43: def.avail_out = size + EXCESS; Chris@43: def.next_out = tmp; Chris@43: ret = recompress(&inf, &def); Chris@43: if (ret == Z_MEM_ERROR) Chris@43: quit("out of memory"); Chris@43: Chris@43: /* set up for next reocmpression */ Chris@43: ret = inflateReset(&inf); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: ret = deflateReset(&def); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: Chris@43: /* do second and final recompression (third compression) */ Chris@43: inf.avail_in = size - MARGIN; /* assure stream will complete */ Chris@43: inf.next_in = tmp; Chris@43: def.avail_out = size; Chris@43: def.next_out = blk; Chris@43: ret = recompress(&inf, &def); Chris@43: if (ret == Z_MEM_ERROR) Chris@43: quit("out of memory"); Chris@43: assert(ret == Z_STREAM_END); /* otherwise MARGIN too small */ Chris@43: Chris@43: /* done -- write block to stdout */ Chris@43: have = size - def.avail_out; Chris@43: if (fwrite(blk, 1, have, stdout) != have || ferror(stdout)) Chris@43: quit("error writing output"); Chris@43: Chris@43: /* clean up and print results to stderr */ Chris@43: free(tmp); Chris@43: ret = inflateEnd(&inf); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: ret = deflateEnd(&def); Chris@43: assert(ret != Z_STREAM_ERROR); Chris@43: free(blk); Chris@43: fprintf(stderr, Chris@43: "%u bytes unused out of %u requested (%lu input)\n", Chris@43: size - have, size, def.total_in); Chris@43: return 0; Chris@43: }