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