examples/zran.c

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