zlib/examples/zran.c

   1 /* zran.c -- example of zlib/gzip stream indexing and random access
   2  * Copyright (C) 2005 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4    Version 1.0  29 May 2005  Mark Adler */
   5
   6 /* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary()
   7    for random access of a compressed file.  A file containing a zlib or gzip
   8    stream is provided on the command line.  The compressed stream is decoded in
   9    its entirety, and an index built with access points about every SPAN bytes
  10    in the uncompressed output.  The compressed file is left open, and can then
  11    be read randomly, having to decompress on the average SPAN/2 uncompressed
  12    bytes before getting to the desired block of data.
  13
  14    An access point can be created at the start of any deflate block, by saving
  15    the starting file offset and bit of that block, and the 32K bytes of
  16    uncompressed data that precede that block.  Also the uncompressed offset of
  17    that block is saved to provide a referece for locating a desired starting
  18    point in the uncompressed stream.  build_index() works by decompressing the
  19    input zlib or gzip stream a block at a time, and at the end of each block
  20    deciding if enough uncompressed data has gone by to justify the creation of
  21    a new access point.  If so, that point is saved in a data structure that
  22    grows as needed to accommodate the points.
  23
  24    To use the index, an offset in the uncompressed data is provided, for which
  25    the latest accees point at or preceding that offset is located in the index.
  26    The input file is positioned to the specified location in the index, and if
  27    necessary the first few bits of the compressed data is read from the file.
  28    inflate is initialized with those bits and the 32K of uncompressed data, and
  29    the decompression then proceeds until the desired offset in the file is
  30    reached.  Then the decompression continues to read the desired uncompressed
  31    data from the file.
  32
  33    Another approach would be to generate the index on demand.  In that case,
  34    requests for random access reads from the compressed data would try to use
  35    the index, but if a read far enough past the end of the index is required,
  36    then further index entries would be generated and added.
  37
  38    There is some fair bit of overhead to starting inflation for the random
  39    access, mainly copying the 32K byte dictionary.  So if small pieces of the
  40    file are being accessed, it would make sense to implement a cache to hold
  41    some lookahead and avoid many calls to extract() for small lengths.
  42
  43    Another way to build an index would be to use inflateCopy().  That would
  44    not be constrained to have access points at block boundaries, but requires
  45    more memory per access point, and also cannot be saved to file due to the
  46    use of pointers in the state.  The approach here allows for storage of the
  47    index in a file.
  48  */
  49
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53 #include "zlib.h"
  54
  55 #define local static
  56
  57 #define SPAN 1048576L       /* desired distance between access points */
  58 #define WINSIZE 32768U      /* sliding window size */
  59 #define CHUNK 16384         /* file input buffer size */
  60
  61 /* access point entry */
  62 struct point {
  63     off_t out;          /* corresponding offset in uncompressed data */
  64     off_t in;           /* offset in input file of first full byte */
  65     int bits;           /* number of bits (1-7) from byte at in - 1, or 0 */
  66     unsigned char window[WINSIZE];  /* preceding 32K of uncompressed data */
  67 };
  68
  69 /* access point list */
  70 struct access {
  71     int have;           /* number of list entries filled in */
  72     int size;           /* number of list entries allocated */
  73     struct point *list; /* allocated list */
  74 };
  75
  76 /* Deallocate an index built by build_index() */
  77 local void free_index(struct access *index)
  78 {
  79     if (index != NULL) {
  80         free(index->list);
  81         free(index);
  82     }
  83 }
  84
  85 /* Add an entry to the access point list.  If out of memory, deallocate the
  86    existing list and return NULL. */
  87 local struct access *addpoint(struct access *index, int bits,
  88     off_t in, off_t out, unsigned left, unsigned char *window)
  89 {
  90     struct point *next;
  91
  92     /* if list is empty, create it (start with eight points) */
  93     if (index == NULL) {
  94         index = malloc(sizeof(struct access));
  95         if (index == NULL) return NULL;
  96         index->list = malloc(sizeof(struct point) << 3);
  97         if (index->list == NULL) {
  98             free(index);
  99             return NULL;
 100         }
 101         index->size = 8;
 102         index->have = 0;
 103     }
 104
 105     /* if list is full, make it bigger */
 106     else if (index->have == index->size) {
 107         index->size <<= 1;
 108         next = realloc(index->list, sizeof(struct point) * index->size);
 109         if (next == NULL) {
 110             free_index(index);
 111             return NULL;
 112         }
 113         index->list = next;
 114     }
 115
 116     /* fill in entry and increment how many we have */
 117     next = index->list + index->have;
 118     next->bits = bits;
 119     next->in = in;
 120     next->out = out;
 121     if (left)
 122         memcpy(next->window, window + WINSIZE - left, left);
 123     if (left < WINSIZE)
 124         memcpy(next->window + left, window, WINSIZE - left);
 125     index->have++;
 126
 127     /* return list, possibly reallocated */
 128     return index;
 129 }
 130
 131 /* Make one entire pass through the compressed stream and build an index, with
 132    access points about every span bytes of uncompressed output -- span is
 133    chosen to balance the speed of random access against the memory requirements
 134    of the list, about 32K bytes per access point.  Note that data after the end
 135    of the first zlib or gzip stream in the file is ignored.  build_index()
 136    returns the number of access points on success (>= 1), Z_MEM_ERROR for out
 137    of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a
 138    file read error.  On success, *built points to the resulting index. */
 139 local int build_index(FILE *in, off_t span, struct access **built)
 140 {
 141     int ret;
 142     off_t totin, totout;        /* our own total counters to avoid 4GB limit */
 143     off_t last;                 /* totout value of last access point */
 144     struct access *index;       /* access points being generated */
 145     z_stream strm;
 146     unsigned char input[CHUNK];
 147     unsigned char window[WINSIZE];
 148
 149     /* initialize inflate */
 150     strm.zalloc = Z_NULL;
 151     strm.zfree = Z_NULL;
 152     strm.opaque = Z_NULL;
 153     strm.avail_in = 0;
 154     strm.next_in = Z_NULL;
 155     ret = inflateInit2(&strm, 47);      /* automatic zlib or gzip decoding */
 156     if (ret != Z_OK)
 157         return ret;
 158
 159     /* inflate the input, maintain a sliding window, and build an index -- this
 160        also validates the integrity of the compressed data using the check
 161        information at the end of the gzip or zlib stream */
 162     totin = totout = last = 0;
 163     index = NULL;               /* will be allocated by first addpoint() */
 164     strm.avail_out = 0;
 165     do {
 166         /* get some compressed data from input file */
 167         strm.avail_in = fread(input, 1, CHUNK, in);
 168         if (ferror(in)) {
 169             ret = Z_ERRNO;
 170             goto build_index_error;
 171         }
 172         if (strm.avail_in == 0) {
 173             ret = Z_DATA_ERROR;
 174             goto build_index_error;
 175         }
 176         strm.next_in = input;
 177
 178         /* process all of that, or until end of stream */
 179         do {
 180             /* reset sliding window if necessary */
 181             if (strm.avail_out == 0) {
 182                 strm.avail_out = WINSIZE;
 183                 strm.next_out = window;
 184             }
 185
 186             /* inflate until out of input, output, or at end of block --
 187                update the total input and output counters */
 188             totin += strm.avail_in;
 189             totout += strm.avail_out;
 190             ret = inflate(&strm, Z_BLOCK);      /* return at end of block */
 191             totin -= strm.avail_in;
 192             totout -= strm.avail_out;
 193             if (ret == Z_NEED_DICT)
 194                 ret = Z_DATA_ERROR;
 195             if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR)
 196                 goto build_index_error;
 197             if (ret == Z_STREAM_END)
 198                 break;
 199
 200             /* if at end of block, consider adding an index entry (note that if
 201                data_type indicates an end-of-block, then all of the
 202                uncompressed data from that block has been delivered, and none
 203                of the compressed data after that block has been consumed,
 204                except for up to seven bits) -- the totout == 0 provides an
 205                entry point after the zlib or gzip header, and assures that the
 206                index always has at least one access point; we avoid creating an
 207                access point after the last block by checking bit 6 of data_type
 208              */
 209             if ((strm.data_type & 128) && !(strm.data_type & 64) &&
 210                 (totout == 0 || totout - last > span)) {
 211                 index = addpoint(index, strm.data_type & 7, totin,
 212                                  totout, strm.avail_out, window);
 213                 if (index == NULL) {
 214                     ret = Z_MEM_ERROR;
 215                     goto build_index_error;
 216                 }
 217                 last = totout;
 218             }
 219         } while (strm.avail_in != 0);
 220     } while (ret != Z_STREAM_END);
 221
 222     /* clean up and return index (release unused entries in list) */
 223     (void)inflateEnd(&strm);
 224     index = realloc(index, sizeof(struct point) * index->have);
 225     index->size = index->have;
 226     *built = index;
 227     return index->size;
 228
 229     /* return error */
 230   build_index_error:
 231     (void)inflateEnd(&strm);
 232     if (index != NULL)
 233         free_index(index);
 234     return ret;
 235 }
 236
 237 /* Use the index to read len bytes from offset into buf, return bytes read or
 238    negative for error (Z_DATA_ERROR or Z_MEM_ERROR).  If data is requested past
 239    the end of the uncompressed data, then extract() will return a value less
 240    than len, indicating how much as actually read into buf.  This function
 241    should not return a data error unless the file was modified since the index
 242    was generated.  extract() may also return Z_ERRNO if there is an error on
 243    reading or seeking the input file. */
 244 local int extract(FILE *in, struct access *index, off_t offset,
 245                   unsigned char *buf, int len)
 246 {
 247     int ret, skip;
 248     z_stream strm;
 249     struct point *here;
 250     unsigned char input[CHUNK];
 251     unsigned char discard[WINSIZE];
 252
 253     /* proceed only if something reasonable to do */
 254     if (len < 0)
 255         return 0;
 256
 257     /* find where in stream to start */
 258     here = index->list;
 259     ret = index->have;
 260     while (--ret && here[1].out <= offset)
 261         here++;
 262
 263     /* initialize file and inflate state to start there */
 264     strm.zalloc = Z_NULL;
 265     strm.zfree = Z_NULL;
 266     strm.opaque = Z_NULL;
 267     strm.avail_in = 0;
 268     strm.next_in = Z_NULL;
 269     ret = inflateInit2(&strm, -15);         /* raw inflate */
 270     if (ret != Z_OK)
 271         return ret;
 272     ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET);
 273     if (ret == -1)
 274         goto extract_ret;
 275     if (here->bits) {
 276         ret = getc(in);
 277         if (ret == -1) {
 278             ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR;
 279             goto extract_ret;
 280         }
 281         (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits));
 282     }
 283     (void)inflateSetDictionary(&strm, here->window, WINSIZE);
 284
 285     /* skip uncompressed bytes until offset reached, then satisfy request */
 286     offset -= here->out;
 287     strm.avail_in = 0;
 288     skip = 1;                               /* while skipping to offset */
 289     do {
 290         /* define where to put uncompressed data, and how much */
 291         if (offset == 0 && skip) {          /* at offset now */
 292             strm.avail_out = len;
 293             strm.next_out = buf;
 294             skip = 0;                       /* only do this once */
 295         }
 296         if (offset > WINSIZE) {             /* skip WINSIZE bytes */
 297             strm.avail_out = WINSIZE;
 298             strm.next_out = discard;
 299             offset -= WINSIZE;
 300         }
 301         else if (offset != 0) {             /* last skip */
 302             strm.avail_out = (unsigned)offset;
 303             strm.next_out = discard;
 304             offset = 0;
 305         }
 306
 307         /* uncompress until avail_out filled, or end of stream */
 308         do {
 309             if (strm.avail_in == 0) {
 310                 strm.avail_in = fread(input, 1, CHUNK, in);
 311                 if (ferror(in)) {
 312                     ret = Z_ERRNO;
 313                     goto extract_ret;
 314                 }
 315                 if (strm.avail_in == 0) {
 316                     ret = Z_DATA_ERROR;
 317                     goto extract_ret;
 318                 }
 319                 strm.next_in = input;
 320             }
 321             ret = inflate(&strm, Z_NO_FLUSH);       /* normal inflate */
 322             if (ret == Z_NEED_DICT)
 323                 ret = Z_DATA_ERROR;
 324             if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR)
 325                 goto extract_ret;
 326             if (ret == Z_STREAM_END)
 327                 break;
 328         } while (strm.avail_out != 0);
 329
 330         /* if reach end of stream, then don't keep trying to get more */
 331         if (ret == Z_STREAM_END)
 332             break;
 333
 334         /* do until offset reached and requested data read, or stream ends */
 335     } while (skip);
 336
 337     /* compute number of uncompressed bytes read after offset */
 338     ret = skip ? 0 : len - strm.avail_out;
 339
 340     /* clean up and return bytes read or error */
 341   extract_ret:
 342     (void)inflateEnd(&strm);
 343     return ret;
 344 }
 345
 346 /* Demonstrate the use of build_index() and extract() by processing the file
 347    provided on the command line, and the extracting 16K from about 2/3rds of
 348    the way through the uncompressed output, and writing that to stdout. */
 349 int main(int argc, char **argv)
 350 {
 351     int len;
 352     off_t offset;
 353     FILE *in;
 354     struct access *index = NULL;
 355     unsigned char buf[CHUNK];
 356
 357     /* open input file */
 358     if (argc != 2) {
 359         fprintf(stderr, "usage: zran file.gz\n");
 360         return 1;
 361     }
 362     in = fopen(argv[1], "rb");
 363     if (in == NULL) {
 364         fprintf(stderr, "zran: could not open %s for reading\n", argv[1]);
 365         return 1;
 366     }
 367
 368     /* build index */
 369     len = build_index(in, SPAN, &index);
 370     if (len < 0) {
 371         fclose(in);
 372         switch (len) {
 373         case Z_MEM_ERROR:
 374             fprintf(stderr, "zran: out of memory\n");
 375             break;
 376         case Z_DATA_ERROR:
 377             fprintf(stderr, "zran: compressed data error in %s\n", argv[1]);
 378             break;
 379         case Z_ERRNO:
 380             fprintf(stderr, "zran: read error on %s\n", argv[1]);
 381             break;
 382         default:
 383             fprintf(stderr, "zran: error %d while building index\n", len);
 384         }
 385         return 1;
 386     }
 387     fprintf(stderr, "zran: built index with %d access points\n", len);
 388
 389     /* use index by reading some bytes from an arbitrary offset */
 390     offset = (index->list[index->have - 1].out << 1) / 3;
 391     len = extract(in, index, offset, buf, CHUNK);
 392     if (len < 0)
 393         fprintf(stderr, "zran: extraction failed: %s error\n",
 394                 len == Z_MEM_ERROR ? "out of memory" : "input corrupted");
 395     else {
 396         fwrite(buf, 1, len, stdout);
 397         fprintf(stderr, "zran: extracted %d bytes at %llu\n", len, offset);
 398     }
 399
 400     /* clean up and exit */
 401     free_index(index);
 402     fclose(in);
 403     return 0;
 404 }